Concurrent Honest Slot Leaders in Proof-of-Stake Blockchains

A Proof-of-Stake blockchain execution where honest blocks have double borders and adversarial blocks have single borders. The nodes are labeled with their round numbers. Note that there are multiple adversarial blocks at rounds 2 and 4. Also, there are multiple honest blocks at rounds 6 and 9. These latter rounds were treated sub-optimally in all previous analyses, in part because the adversary could possibly use them to create inconsistent views for honest nodes. Our new paper closes this gap by putting forth a stronger analysis.

Consider the eventual consensus Proof-of-Stake (PoS) blockchains under the longest-chain rule such as Ouroboros, Ouroboros Praos, Sleepy Consensus, Snow White, etc. All existing analyses use a sub-optimal honest majority assumption in that if multiple honest nodes win the block-creation lottery in the same round, the analysis either treats it as a bad event or, at best, a neutral event.

In our paper, we put forth a consistency analysis that takes advantage of these events and thus achieves an asymptotically optimal consistency error under the optimal honest majority assumption; this is a first in the literature. The analysis applies to both synchronous communication and communications with a bounded delay.

This improvement is important since a sub-optimal honest majority assumption leads to weak security parameters for the blockchain system. The paper is going to appear at the prestigious conference IEEE ICDCS 2020. We posted the full version of our paper at



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s