[Resource Topic] 2020/041: Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders

Welcome to the resource topic for 2020/041

Consistency of Proof-of-Stake Blockchains with Concurrent Honest Slot Leaders

Authors: Aggelos Kiayias, Saad Quader, Alexander Russell


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_A, the probability that a round has at least one adversarial leader; p_h, 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^{-\Theta(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 the consistency guarantees 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.

ePrint: https://eprint.iacr.org/2020/041

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .