Paper 2020/041

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

Aggelos Kiayias, Saad Quader, and Alexander Russell

Abstract

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.

Note: Fixed a bug in Fact 1, thanks to Peter Gaži (IOHK).