EC Finality Calculator (FRC-0089)

[jsoares]

A Finality Calculator for Expected Consensus

FRC: https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0089.md
authors: @guy-goren, @jsoares

Summary

Filecoin's Expected Consensus (EC) comes with probabilistic finality and a 900-epoch soft finality threshold, intended to achieve a finality guarantee (tipset replacement probability) of $2^{-30}$. While network participants (e.g. exchanges, L2 operators, application developers) use different confirmation thresholds, they pessimistically wait between 100-900 epochs before considering a transaction final, leading to delays in the order of hours.

Instead of naively counting the number of epochs, we propose a finality calculator that considers what takes place during those epochs and, under expected operating conditions, can attain the same level of certainty in fewer epochs. For example, consider two cases: in case A, the chain grew by 5 blocks per epoch over the last 50 epochs; in case B, the chain grew by a mere 2 blocks per epoch over the same 50 epochs. The probability of a chain reconfiguration longer than 50 epochs is much smaller in case A than in case B, allowing us to make an earlier finality determination.

We embark on an analysis of Filecoin's finality, i.e., the probabilistic guarantees that a given tipset will always be in the canonical chain. The analysis involves distributed computing and stochastic arguments and provides upper bounds for the error probabilities, i.e., the probability that a reorg would override a given tipset. We show that, in real operating conditions, the same error probability $2^{-30}$ can be achieved in ~30 epochs (15 minutes) -- a 30x improvement.

This algorithm is practical, only requires access to a node's local view, and can be implemented by clients or off-chain applications without requiring any changes to the protocol. We plan to propose an FRC outlining the recommended procedure for finality calculation.

Motivation

This proposal has two main goals:

• To provide finality guarantees grounded on clear formal reasoning
• To reduce the delays experienced by Filecoin users

Users and applications (e.g. exchanges, IPC subnets) that choose to implement these recommendations won't need to wait a fixed period of up to 900 epochs; they can benefit from faster finalization times and increased visibility into the security guarantees they are receiving.

F3 will also address these points (with even faster finality). This work does not conflict with F3 and independently provides several benefits:

1. It requires no change to client code and, therefore, no agreement process. Instead, it is a simple algorithm that any node can run separately from the "mining process". The algorithm takes as input the observed history of the chain and outputs a measure of safety.
2. It does not change the incentive considerations of Filecoin, which remains a longest-chain blockchain, similar to Bitcoin and Ethereum. Since no extra work is mandatory, the algorithm's execution (or no execution) does not affect the safety of Filecoin.
3. It is an algorithm and not a protocol. Its execution is local, and the result does not depend on other nodes executing the algorithm. For the same reason, it requires no additional communication and is infinitely scalable.
4. In case F3 halts and the network falls back on EC finality, it can reduce the degradation experienced by users.

Notably, (1) implies that our proposal can be an interim solution for Filecoin until F3 goes live on the network.

Proposal

Our analysis draws inspiration from techniques developed in an AFT’22 paper combined with techniques from an ICDCS’20 paper and applying them to the observed chain history of Filecoin (when possible). In summary, we consider an observed addition of $k$ blocks on top of the target tipset produced at epoch $s$. We then look at:

1. Distant past: potential adversarial lead at epoch $s$, with respect to the local heaviest chain
2. Recent past: blocks produced by the adversary between epoch $s$ and the current epoch $c$
3. Future: potential lead created by the adversary after current epoch $c$, with respect to blocks produced by honest validators slowed by the adversary

We then use the data from the three stages to determine the probability that the adversary will overtake the observed chain. The analysis detailing how we bound the finality of a given input can be found here. We aim to provide a more digestible version soon.

A Python prototype is available here. This implementation tries to translate the specification with minimal changes rather than optimize for performance. As an application-side optimization with no interoperability requirement, implementers in different clients and languages may freely diverge from the prototype.

Evaluation

We have run our algorithm on past chain data from the Filecoin mainnet. The periods analyzed are heights 3,349,680 to 3,433,200, a typical healthy state, and heights 2,684,400 to 2,773,680, at the tail end of which there is a particularly unhealthy period. The figures below show the results of quantifying the finality of tipsets after a 30-epoch delay. The potential adversarial power we considered is 30%. We note that one may choose other questions to analyze, such as when a specific tipset reaches a given finality threshold.

The figure below shows the results of applying the analysis to a typical healthy chain period, when tipsets are almost full (5 blocks) on average. On the $x$-axis we have the epoch numbers. We have a double $y$-axis: on the right axis, we have the number of blocks in tipsets (plotted in green, as well as the moving average), and on the left axis we have the error probabilities after 30 epochs (plotted in blue). It is mostly below $10^{-10}$, implying that a reorg of this tipset is, at most, a once in 10,000 years event. It is clear how a higher number of blocks per epoch typically results in better finality measurement (smaller error probability).

The figure below shows the results of applying the analysis on a period when the Filecoin blockchain was less healthy (around the end of March 2023). Starting around epoch 2,750,000, tipsets show, on average, fewer blocks than expected --- often falling to below 4 blocks per tipset when averaged over 30 epochs. As expected, the finality measurement is worse than in the typical "good case"; that is, the error probabilities are higher by several orders of magnitude at times.

Security

• From the network perspective, the proposed algorithm provides more transparency on the security guarantees Filecoin provides without impacting them.
• From the client/user perspective, a transaction can now be considered final once a desired security guarantee is met. While, on the surface, it may seem riskier to finalize transactions 30x faster, this is merely the result of replacing a loose worst-case assumption by a more accurate determination based on actual network conditions.
• It is possible to misuse the algorithm and accept an error probability that is too high while attempting to over-optimize for latency. This is akin to picking an insufficient number of epochs in the current paradigm, with the key difference that the error probability can be easily interpreted, whereas the certainty provided by a fixed number of epochs is variable and opaque.

[f8-ptrk]

it would be beneficial to link filecoins EC specs in the first line

[jsoares]

Forgot to reply but link added, thanks :)

[nicola]

Please attach the google doc as a PDF or in the markdown so that if we ever lose it, its content survives!

[jsoares]

I replaced the link with a pdf attachment. Note that we're working on a cleaner latex version of this that we'll either attach or embed in the actual FRC, so that one will be the true keeper.

[jsoares]

Selected Q&A from Slack

[jsoares]

How do you get around considering the worst attack, for which previous simulations lead to 900 epochs?

The way to "get around that" is by considering the worst case only where needed. That is, when we know that the worst case did not occur, then we don't need to consider it. For example, if at some point we see that in the previous 30 epochs, every tipset was full (on average), then we do not need to consider that the past 30 epochs had tipsets that were only 2/5 full (which is close to the worst case). Instead, we know that something better happened, and therefore, we use it to our advantage.

Note, however, that sometimes we cannot get around the worst case. For example, in the analysis part that considers the future. Since the future is unknown, we have to consider the worst case there.

Finally, our calculator is more complex than simply plugging in a fixed epoch_delay number. It outputs a finality guarantee based on the specific condition of the Filecoin chain at the time. Thus, it typically results in (much) faster delay times but could also output a very long delay if the chain is in a particularly bad condition.

cc @nicola

[jsoares]

Can you quantify “unhealthy” as used in this post? Is it just about # of blocks dropping below a consistent average of ~5? And can you explain why this happens, and also what are the pressures involved that are pushing toward that ~5?

Indeed, the definition of unhealthy that we're using here is just «#blocks/tipset dropping below 5 for some time», given that's what's key for the purposes of finality calculation -- there are, of course, other possible definitions of chain health. The 5 is not just a healthy average but a network target.

The determination of winning tickets uses a Poisson random variable parametrised with ExpectedLeadersPerEpoch=5 . The most efficient description of the mechanism is found at the beginning of section 3.1 (bottom of page 5) in this paper, and expanded on in section 4.1.3.2.1 of the spec.

While some variation is expected due to the probabilistic mechanism, what's more interesting is what can cause the average to drop below 5 for an extended period of time. Potential causes include network delays (e.g. blocks not being delivered in time for inclusion) or shifts in storage power (e.g. a sufficiently large share of network power not upgrading in time and therefore not producing blocks for their winning tickets), as well as transient power splitting across different forks.

Selected examples:

• the expedited nv19/20 upgrade was caused by deal settlement in f05 cron taking up too much space and increasing validation times, which led to block productions taking longer than normal (>5-10sec)
• mpoolselect in lotus client is not optimized, which leads to long message selection periods which further impacts block formation performance

cc @rvagg @jennijuju

[jsoares]

FRC PR created: #941

[jsoares]

We also gave a brief presentation at Core Devs 66. Recording here.

[masih]

Links in the Evaluation section seem to return 404?

[jsoares]

@masih fixed, sorry about that

[masih]

No worries, many thanks

[jsoares]

In any case, not that the actual FRC has more information and a few updates

https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0089.md