A Finality Calculator for Filecoin’s Expected Consensus

Guy Goren and Jorge M. Soares

Technical Report PL-TechRep-2024-001

2024.02.01

A Finality Calculator for Filecoin’s Expected Consensus

GUY GOREN and JORGE M. SOARES, Protocol Labs

We propose a finality calculator for Filecoin’s Expected consensus that considers what takes place during epochs and can attain, under normal operating conditions, an error probability of 2^{−30} in 30 epochs (15 minutes) - a 30x improvement over the current 900-epoch threshold. It depends only on a node’s local view and can be implemented without protocol changes.

CCS Concepts: • Security and privacy → Distributed systems security.

1 INTRODUCTION

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}[4]. 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. 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, and 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 visibility to blocks produced by honest miners, and can be implemented by clients or off-chain applications without requiring any changes to the protocol. This document serves as a theoretical companion to FRC-0089. Please refer to the FRC for more background, motivation, and implementation information.

2 PRELIMINARY CONSIDERATIONS

2.1 Randomness

Consider a chain with:

• : number of validators

• f1 : adversarial fraction
• ℎ: honest fraction (1 − f1)

Denote -f[A] the random variable that represents the number of blocks won by the adversary in round A. Similarly, -ℎ[A] denotes the number of honest blocks. Bin(k; n,p) is the Binomial distribution where n is the number of trials and p is the probability of success for each trial, k is the number of successes (value of a random variable). In our system, we have n = # and p = . Therefore:

• 4: expected number of blocks per round.

This approximation is good provided n is large and n · p ≤ 4 ≪ n.

3 ANALYSING THE PROBABILITY OF ERRORS

Our analysis draws inspiration from techniques developed in [1] combined with techniques from [3], which we apply to the observed chain history of Filecoin. We denote by 𝐺 the good addition, i.e. the number of blocks observed in the local heaviest chain (lh-chain) between target epoch B and current epoch 2. We then split the analysis into three time spans:

• Distant past: The random variable ! describes the adversarial lead at epoch B.
• Recent past: The random variable 𝐵 describes the blocks produced by the adversary between epoch B and the current epoch 2.
• Future: The random variable " describes the blocks expected to be produced by the adversary minus the number of blocks produced by honest validators.

Our analysis is based on the two lemmas below. Roughly, they establish that all chains that end with an honest block are visible to the user.

Lemma 3.1

Let 1ℎ be a block produced by an honest validator at round A. Then the tipset chain ending at parent(1ℎ) is known to all honest validators by round A + 1.

Lemma 3.2

Let 2 be the current round. Let C0[E8] be the "best" tipset chain of which validator E8 is aware (and would choose as parent), which ends in round 0, and let C1 [E8] be the "best-competitor" tipset chain of which E8 is aware, which ends in round 1.

Recall that the fork choice rule in Filecoin is based on chain validity and weight, where:

1. Validity is determined by a set of rules that govern the correct construction of blocks.
2. Weight incorporates the number of blocks mined and a factor related to the storage in the power table.

We can now start to derive the probabilities for each of the time spans.

3.1 Span 1: Distant past

Let B be the epoch for which the finality probability is being evaluated, and 2 be the current epoch (2 > B). The random variable ! describes the adversarial (secret) lead gained from the last final tipset until epoch B.

For each epoch 8 ∈[2 − 900 + 1,B], the step expectation is 5 · 4 − 2ℎ08= [8]. This changes the analysis somewhat since we cannot use the classic random walk model.

We can look at a reverse process that starts at the tipset of interest of epoch B and moves backwards in time.

3.2 Span 2: Recent past

The random variable 𝐵 is independent from ! and follows a simple binomial distribution. For ease of computation, we approximate the binomial distribution by a Poisson one.

3.4 Error probability

For an observed good addition 𝐺 = : , the safety violation event happens only if one of the three mutually exclusive events occurs:

1. ! ≥ :
2. ! < : but ! + 𝐵 ≥ :
3. ! + 𝐵 < : but ! + 𝐵 + " ≥ :

Knowing that

P r(L+B≥k|L<k)=∑_{l=0}^{k−1}P r(L=l)⋅P r(B+l≥k),

We would like to thank all the community members who provided input and reviews for this work, including Alejandro Ranjal-Pedrosa, Irene Giacomelli, Juan Cianci, and Marko Vukolić.

REFERENCES

[1] Dongning Guo and Ling Ren. 2023. Bitcoin’s Latency–Security Analysis Made Simple. In Proceedings of the 4th ACM Conference on Advances in Financial Technologies (Cambridge, MA, USA) (AFT ’22). Association for Computing Machinery, New York, NY, USA, 244–253. https://doi.org/10.1145/3558535.3559791
[2] Guy Goren and Alfonso de la Rocha. 2023. FRC-0051: Synchronous Consistent Block Broadcast for EC Security. https://github.com/filecoin-project/FIPs/blob/master/FRCs/frc-0051.md[Online; accessed 05-February-2024].
[3] Aggelos Kiayias, Saad Quader, and Alexander Russell. 2020. Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders. In 2020 IEEE 40th International Conference on Distributed Computing Systems (ICDCS). IEEE Computer Society, Los Alamitos, CA, USA, 776–786.https://doi.org/10.1109/ICDCS47774.2020.00065
[4] Xuechao Wang, Sarah Azouvi, and Marko Vukolić. 2023. Security Analysis of Filecoin’s Expected Consensus in the Byzantine vs Honest Model. In 5th Conference on Advances in Financial Technologies (AFT 2023) (Leibniz International Proceedings in Informatics (LIPIcs)), Joseph Bonneau and S. Matthew Weinberg (Eds.), Vol. 282. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 5:1–5:21.https://doi.org/10.4230/LIPIcs.AFT.2023.5
[5] Wikipedia contributors. 2023. Skellam distribution — Wikipedia, The Free Encyclopedia.https://en.wikipedia.org/w/index.php?title=Skellam_distribution&oldid=1161277886[Online; accessed 31-January-2024].