Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders
We improve the fundamental security threshold of eventual consensus Proof-of-Stake (PoS) blockchain protocols under longest-chain rule, reflecting for the first time the positive effect of rounds with concurrent honest leaders. Current analyses of these protocols reduce consistency to the dynamics of an abstract, round-based block creation process that is determined by three probabilities: pAh, 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. We also provide an efficient algorithm to explicitly calculate these error probabilities in the synchronous setting.
All existing consistency analyses either incur a penalty for rounds with concurrent honest leaders, or treat them neutrally. Specifically, 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). In addition, previous analyses completely break down when uniquely honest rounds become less frequent, i.e., ph < pA. These thresholds determine the critical trade-off between the honest majority, network delays, and consistency error.
Our new results can be directly applied to improve consistency of the existing protocols. We complement these 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.
