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: p_Ah, the probability that a round has a single honest leader; and p_H, the probability that a round has multiple, but honest, leaders.

We present a consistency analysis that achieves the optimal threshold p_h + p_H > p_A. 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., p_h - p_H > p_A); 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., p_h > p_A). In addition, previous analyses completely break down when uniquely honest rounds become less frequent, i.e., p_h < p_A. 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 p_h= 0, under the added assumption that honest players adopt a consistent chain selection rule.