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

Abstract

We improve the fundamental security threshold of eventual consensus\nProof-of-Stake (PoS) blockchain protocols under the longest-chain rule by\nshowing, for the first time, the positive effect of rounds with concurrent\nhonest leaders.\n Current security analyses reduce consistency to the dynamics of an abstract,\nround-based block creation process that is determined by three events\nassociated with a round: (i) event $A$: at least one adversarial leader, (ii)\nevent $S$: a single honest leader, and (iii) event $M$: multiple, but honest,\nleaders. We present an asymptotically optimal consistency analysis assuming\nthat an honest round is more likely than an adversarial round (i.e., $\\Pr[S] +\n\\Pr[M] > \\Pr[A]$); this threshold is optimal. This is a first in the literature\nand can be applied to both the simple synchronous communication as well as\ncommunication with bounded delays.\n In all existing consistency analyses, event $M$ is either penalized or\ntreated neutrally. Specifically, the consistency analyses in Ouroboros Praos\n(Eurocrypt 2018) and Genesis (CCS 2018) assume that $\\Pr[S] - \\Pr[M] > \\Pr[A]$;\nthe analyses in Sleepy Consensus (Asiacrypt 2017) and Snow White (Fin. Crypto\n2019) assume that $\\Pr[S] > \\Pr[A]$. Moreover, all existing analyses completely\nbreak down when $\\Pr[S] < \\Pr[A]$. These thresholds determine the critical\ntrade-off between the honest majority, network delays, and consistency error.\n Our new results can be directly applied to improve the security guarantees of\nthe existing protocols. We also provide an efficient algorithm to explicitly\ncalculate these error probabilities in the synchronous setting. Furthermore, we\ncomplement these results by analyzing the setting where $S$ is rare, even\nallowing $\\Pr[S] = 0$, under the added assumption that honest players adopt a\nconsistent chain selection rule.\n