Proof of Stake and the History of Distributed Consensus: Part 1, Nakamoto Consensus, Byzantine Fault Tolerance, Hybrid Consensus, Thunderella
The Historical Context of Hybrid Consensus
At present, Blockchains threaten to disrupt major industries like finance, law, and computing. Bitcoin was a technological breakthrough that brought people together by allowing them to achieve decentralized and censorship-resistant money.
Bitcoin constituted a serious technological advance as the first distributed system simultaneously able to tolerate pure permissionless consensus in the presence of up to 50% Byzantine faults, be totally ordered, DoS resistant, Sybil resistant, and use incentives to encourage honest participation. It provided a simple and elegant way to have a decentralized and truly permissionless distributed system.
Unfortunately, what Bitcoin has gained in robustness and security, it has given up in performance. Bitcoin is painfully slow. Ironically, chip companies and miners have spent billions on faster and faster chips in order to crack an algorithm that intentionally kept consensus slow. All the while, the hash puzzles completed for Proof of Work (PoW) produced large amounts of waste.
As a result, Bitcoin researchers began exploring different routes to reduce waste and achieve speed and scalability. The most obvious choice was to remove the intentionally wasteful process of PoW from Bitcoin. The earliest solutions, including Proof of Stake (PoS), have tried to replicate the longest-chain dynamics of Bitcoin’s Nakamoto consensus, without the brute force PoW hash puzzles of BTC.
These systems simulate PoW as a random oracle. PoW, essentially, is a way to randomly choose a different miner to propose every block, based on that miner’s portion of the total hash rate. These PoW protocols were pioneered by members of early Bitcoin forums. Later, these were expounded by other more formal research works that have manifested in sleeker protocols which are closer to deployment in public blockchains, such as Ouroboros Genesis and Snow White.
Unfortunately, although these chain-based systems may cut out much of the waste of PoW, in order to work they are required to be slow, even if not wasteful. For a protocol to tolerate up to 49% of the nodes being malicious, like Bitcoin, it must have a block interval that is many times greater than the maximum network delay. A number of research papers co-authored by cryptography Professor Rafael Pass and Elaine Shi at Cornell have expressed and proven this result, including Analysis of the Blockchain Protocol in Asynchronous Networks, and The Sleepy Model of Consensus.
As a result of the above limitation, although chain-based protocols gracefully eliminated the problem of PoW waste, issues with transaction speed and network scalability remained unsolved.
Over the past few years, more academics have joined the space and, armed with a rich, decades-long history of scholarly literature studying consensus in the presence of distributed, unstable, and potentially adversarial environments, brought with them a whole host of ideas about how to resolve scalability problems through alternative consensus systems.
These systems, called classical asynchronous Byzantine Fault Tolerant (BFT) consensus algorithms, are similar to Bitcoin in that they allow for agreement amongst many different parties. Some of these systems are also meant to work in decentralized settings and were made to handle significant attacks.
The fastest of these, known as asynchronous BFT protocols, include asynchronous versions of systems like Paxos and PBFT, which have been used in large-scale deployments in the past. Their speed is achieved because they require a small number of messages to be passed. These protocols normally confirm transactions in a constant O(1) of round trips. Because they are asynchronous, there is no need to wait for any a-priori set block interval or synchronous round; they run as fast as the network delivers messages.
This is why many top projects, such as Ethereum and Cosmos, started developing BFT consensus algorithms for use in blockchains.
On the surface, these BFT protocols sound ideal to replace Nakamoto consensus in blockchains. However, a number of academics, found these BFT systems alone to be inadequate for blockchain settings and sought to formalize that intuition. Chiefly, these classical BFT systems were not meant to handle permissionless consensus and did not scale well to a large number of nodes. As Professors Rafael Pass and Elaine Shi explain in Rethinking Large Scale Consensus,
A permissionless network is distinct from classical models considered in the distributed systems and cryptography literature in the following respects: 1. nodes can join and leave the protocol freely at any time, and participation is open, i.e., there is no access control mechanism that decides who can join and who cannot; 2. nodes are not aware of other protocol participants a-priori, and the network delivery mechanism does not provide sender authentication, i.e., there is no authenticated channels; 3. the protocol may not even be aware of the exact number of nodes participating in the protocol; and 4. more generally, the number of nodes may vary over time.
As the Professors note, these asynchronous classical BFT algorithms are not suitable for truly permissionless environments. Worse still, they decrease the number of attackers that PoW blockchains can tolerate from ½ of the network to ⅓.
When these algorithms’ assumptions are not fulfilled (on the number of adversarial nodes, or on the availability of honest nodes), many tend to shut down, falling back to extremely complicated asynchronous recovery mechanisms. In distributed systems language, they lack strong livenessguarantees when assumptions are violated.
The single greatest challenge for blockchains thus remained: how to achieve the speed of BFT algorithms and the robustness of Nakamoto consensus. There needed to be some way to reconcile purely permissionless algorithms and permissioned ones. This need motivated researchers to try to design such a protocol. As a result, several works, like Algorand, Hybrid Consensus, andSnow White, created methods by which to take a class of “permissioned” consensus protocols and make them reconfigurable, such that they can be deployed in a permissionless setting.
Perhaps the most obvious and simple of these was Hybrid Consensus. As its name suggests, it relies on periodically selecting a provably fair committee election on a blockchain “slow chain,” with a fast-path asynchronous PBFT-style committee running on top of it.

This seems to get the make use of both worlds: it’s permissionless, it’s scalable to a large number nodes, it’s “asynchronous,” and users need not even wait for a single block interval because the fast-path is responsive.
Though “Hybrid Consensus” posed a novel solution and solved many of the open questions, still some room for improvement remained.
In the next post, we will go into improvements on the Hybrid Consensus framework, including Thunderella, which is ThunderCore’s consensus model.
-zk
Acknowledgements: I would like to thank Elaine Shi, Bauer Wann, Greg Swan, and Ivan Perez for their collaboration in writing this post.

