Systematizing Consensus in the Age of Blockchains

We are at a crucial point in the evolution of blockchains, and the biggest hurdle in their widespread adoption is improving their performance and scalability. These properties are deeply related to the consensus protocol used—the core component of the blockchain allowing multiple nodes to agree on the data to be sealed in the chain. This week we published a pre-print of the first comprehensive systematization of blockchain consensus protocols. This blog post discusses the motivation for this study, the challenges in systematization, and a summary of the key contributions.

Consensus is an old well-studied problem in computer science. The distributed systems community has studied it for decades, and developed robust and practical protocols that can tolerate faulty and malicious nodes. However, these protocols were designed for small closed groups and cannot be directly applied to blockchains that require consensus in very large peer-to-peer open participation settings.

The Bitcoin Consensus Protocol

Bitcoin’s main innovation was to enable consensus among an open, decentralized group of nodes. This involves a leader election based on proof-of-work: all nodes attempt to find the solution to a hash puzzle and the node that wins adds the next block to the blockchain. A downside of its probabilistic leader election process, combined with performance variations in decentralized networks, is that Bitcoin offers only weak consistency. Different nodes might end up having different views of the blockchain leading to forks. Moreover, Bitcoin suffers from poor performance which cannot be fixed without fundamental redesign, and its proof-of-work consumes a huge amount of energy.

Improved Blockchain Consensus Protocols

Because of these issues, over the last few years a plethora of designs for new consensus protocols have been proposed. Some replace Bitcoin’s proof-of-work with more energy-efficient alternatives, while others modify Bitcoin’s original design for better performance. To achieve strong consistency and similar performance as mainstream payment processing systems like Visa and PayPal, another vein of work proposes to repurpose classical consensus protocols for use in blockchains. As a result of these various design proposals, the area has become too complex to see the big picture.

Systematization Challenges

To date there exists no systematic and comprehensive study of blockchain consensus protocols. Such a study is challenging because of two reasons. First, a comprehensive survey of blockchains would be incomplete without a discussion of classical consensus protocols. But the literature is vast and complex, which makes it hard to be tailored to blockchains. Second, conducting a survey of consensus protocols in blockchains has its own difficulties. Though the field is young, it is both high-volume and fast-paced. The figure above shows the number of papers published on blockchains each year since Bitcoin’s inception in 2008 (sourced from CABRA).  One might consider only accounting for work published in reputable venues, but this approach is not feasible in the case of blockchains because the bulk of the work is published in non peer-reviewed venues and as white papers for industrial platforms.

Systematization of Blockchain Consensus Protocols

To fill this gap, this week we published a pre-print of the first comprehensive systematization of blockchain consensus protocols—mapping out their evolution from the classical distributed systems use case to their application to blockchains. After first discussing key themes in classical consensus protocols, we describe: (i) protocols based on proof-of-work, (ii) proof-of-X protocols that replace proof-of-work with more energy-efficient alternatives, and (iii) hybrid protocols that are compositions or variations of classical consensus protocols. We developed a framework to evaluate their performance, security and design properties, and used it to systematize key themes in different protocol categories. This work highlighted a number of open areas and challenges related to gaps between classical consensus protocols and blockchains, security vs performance tradeoffs, incentives, and privacy. We hope that this longitudinal perspective will inspire the design of new and faster consensus protocols that can cater to varying security and privacy requirements.

Leave a Reply

Your e-mail address will not be published. Required fields are marked *