Abstract
We improve the fundamental security threshold of Proof-of-Stake (PoS) blockchain protocols, reflecting for the first time the positive effect of rounds with multiple honest leaders. Current analyses of the longest-chain rule in PoS blockchain protocols reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three probabilities:
• pA, the probability that a round has at least one adversarial leader;
• ph, the probability that a round has a single honest leader; and
• pH, the probability that a round has multiple, but honest, leaders.
We present a consistency analysis that achieves the optimal threshold ph + pH > pA. This is a first in the literature and can be applied to both the simple synchronous setting and the setting with bounded delays.Moreover, we achieve the optimal consistency error e−Θ(k) where k is the confirmation time. The consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that the probability of a uniquely honest round exceeds that of the other two events combined (i.e., ph − pH > pA); the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that a uniquely honest round is more likely than an adversarial round (i.e., ph > pA). Thus existing analyses either incur a penalty for multiply honest rounds, or treat them neutrally. In addition, previous analyses completely break down when uniquely honest rounds become less frequent, i.e., ph < pA. Our new results can be directly applied to improve consistency of these existing protocols. We emphasize that these thresholds determine the critical tradeoff between honest majority, network delays, and consistency error. We complement our results with a consistency analysis in the setting where uniquely honest slots are rare, even letting ph = 0, under the added assumption that honest players adopt a consistent chain selection rule. Our analysis provides a direct connection between the Ouroboros analysis by Blum et al. (SODA 2020) focusing on “relative margin” and the Sleepy consensus analysis focusing on “strong pivots.”
• pA, the probability that a round has at least one adversarial leader;
• ph, the probability that a round has a single honest leader; and
• pH, the probability that a round has multiple, but honest, leaders.
We present a consistency analysis that achieves the optimal threshold ph + pH > pA. This is a first in the literature and can be applied to both the simple synchronous setting and the setting with bounded delays.Moreover, we achieve the optimal consistency error e−Θ(k) where k is the confirmation time. The consistency analyses in Ouroboros Praos (Eurocrypt 2018) and Genesis (CCS 2018) assume that the probability of a uniquely honest round exceeds that of the other two events combined (i.e., ph − pH > pA); the analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto 2019) assume that a uniquely honest round is more likely than an adversarial round (i.e., ph > pA). Thus existing analyses either incur a penalty for multiply honest rounds, or treat them neutrally. In addition, previous analyses completely break down when uniquely honest rounds become less frequent, i.e., ph < pA. Our new results can be directly applied to improve consistency of these existing protocols. We emphasize that these thresholds determine the critical tradeoff between honest majority, network delays, and consistency error. We complement our results with a consistency analysis in the setting where uniquely honest slots are rare, even letting ph = 0, under the added assumption that honest players adopt a consistent chain selection rule. Our analysis provides a direct connection between the Ouroboros analysis by Blum et al. (SODA 2020) focusing on “relative margin” and the Sleepy consensus analysis focusing on “strong pivots.”
| Original language | English |
|---|---|
| Title of host publication | 2020 40th IEEE International Conference on Distributed Computing Systems (ICDCS) |
| Publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| Pages | 776 - 786 |
| Number of pages | 11 |
| ISBN (Electronic) | 978-1-7281-7002-2 |
| ISBN (Print) | 978-1-7281-7003-9 |
| DOIs | |
| Publication status | Published - 23 Feb 2021 |
| Event | 40th IEEE International Conference on Distributed Computing Systems - , Singapore Duration: 8 Jul 2020 → 10 Jul 2020 https://icdcs2020.sg/ |
Publication series
| Name | |
|---|---|
| Publisher | IEEE |
| ISSN (Print) | 1063-6927 |
| ISSN (Electronic) | 2575-8411 |
Conference
| Conference | 40th IEEE International Conference on Distributed Computing Systems |
|---|---|
| Abbreviated title | ICDCS 2020 |
| Country/Territory | Singapore |
| Period | 8/07/20 → 10/07/20 |
| Internet address |
Keywords
- Proof-of-Stake blockchains
- security
- consistency
- concurrent honest slot leaders