Chapter 5 Consensus Algorithms

Mastering Blockchain Chapter 5, Consensus Algorithms Outline • Introducing the consensus problem • Consensus mechanism analysis and design • Classification • Types of algorithm • Choosing an algorithm Consensus problem • The problem has been studied extensively in distributed systems research since the late 1970s • This resulted in a rapid evolution of blockchain technology, and more research in novel methods of consensus has been ongoing • Conversion of traditional (classical) distributed consensus mechanisms into their blockchain variants has taken place • Here, we’ll analyze existing and novel consensus protocols The Byzantine generals problem The famous Byzantine generals problem was formulated by Lamport et al. in their paper: Lamport, L., Shostak, R. and Pease, M., 1982. The Byzantine Generals Problem. ACM Transactions on Programming Languages and Systems, 4(3), pp.382-401. Retre ? at Atta ? ck Attac k? Atta ? ck Retre? at Fault tolerance 1. Types of fault tolerance: • Crash Fault Tolerance (CFT) • Byzantine Fault Tolerance (BFT) 1. How to achieve fault tolerance: • Replication: Active/Passive • State machine replication 1. Limitations and results: Fault tolerance: Is at the heart of distributed systems—especially blockchain systems— Due to: ● Networks fail, ● Servers crash, and sometimes ● malicious actors join. CFT vs. BFT helps to pick the right level of protection for the system. Replication, whether active or passive, implements fault tolerance in practice, and state machine replication is a common pattern in consensus algorithms. Theoretical limitations (FLP impossibility, lower/upper bounds) confirm that no single approach can handle all scenarios under all conditions; the system design must balance practicality, performance, and safety. • FLP impossibility Where F = number of faults: • Lower bounds • In the case of CFT, at least 2F + 1 number of nodes is required to achieve consensus. • Upper bounds • In the case of BFT, at least 3F + 1 number of nodes is required to achieve consensus. Analysis and design Designing and analyzing consensus mechanisms requires a model that can be used to study and explore system properties, and make designs more logical. A model consists of: • Processes • Timing assumptions • Synchrony • Asynchrony • Partial synchrony Classification of Consensus Since the invention of Bitcoin, which introduced lottery-based consensus algorithms, there are two main types of consensus: • Traditional Consensus • Examples: Paxos, Raft, and classical Byzantine Fault Tolerance (BFT) algorithms (e.g., PBFT). • Characteristics: • Rely on explicit messaging and deterministic protocols to select leaders or order requests. • Typically designed for smaller, closed sets of participants (like in corporate data centers). • Emphasize agreement and consistency among known nodes. • Lottery-Based Consensus • Example: Proof of Work (PoW), as first popularized by Bitcoin. • Characteristics: • Effectively “randomly” selects a leader (the winner of the “lottery”) based on computational puzzles or other forms of resource commitment (in PoW, it’s hashing power). • Allows large, open participation where anyone can try to solve the puzzle. • Introduces probabilistic finality: it becomes exponentially unlikely (but never outright impossible) to rewrite the chain as more blocks are built on top. Consensus correctness properties These properties are essential to ensure: ● Security (through safety): The blockchain remains trustworthy and unalterable. ● Availability (through liveness): Transactions are eventually confirmed, and the network doesn’t halt. Safety: Ensures that nothing bad happens (The system doesn’t reach an incorrect or inconsistent state) Agreement ● All non-faulty (honest) nodes must agree on the same value (the same block or transaction order). ● No two correct nodes should decide on different values. Validity ● If all honest nodes propose the same value, then any value decided must be that same value. ● The agreed-upon value must be valid according to protocol rules (a block must have valid transactions). Integrity ● A node should not decide on the same value more than once. ● Once a decision is made, it must not be changed or repeated. Liveness: ensures that something good eventually happens (the system continues to make progress). Termination ● All non-faulty nodes must eventually reach a decision. Algorithms Each category addresses different fault assumptions and system environments, but all aim to ensure a consistent ledger (or state) among distributed participants. CFT (Crash Fault Tolerance) ○ Paxos / Raft: Both are designed to tolerate “crash” failures—where processes can fail silently but do not behave maliciously. They rely on leader election and quorum‐based decision‐making to ensure consistency among replicas. BFT (Byzantine Fault Tolerance) ○ PBFT, IBFT, Tendermint, HotStuff: These tolerate “Byzantine” or arbitrary/malicious failures. They use more complex messaging and voting phases to ensure correct consensus, even with a fraction of nodes acting maliciously. Nakamoto and Post‐Nakamoto Consensus ○ PoW (Proof of Work): As introduced by Bitcoin, it randomly selects block proposers based on computational puzzles (the “work”). ○ PoS (Proof of Stake): A newer approach where block proposers are chosen in proportion to their stake (e.g., coins locked or bonded) rather than computing power, reducing the energy Proof of Work A node that proposes a block has to find a nonce such that: H (nonce || previous hash || Tx || Tx|| . . . ||Tx) < Threshold value. PoS Types of PoS include: • Chain-based PoS • Committee-based PoS • Delegated PoS Here, a stake calculator function is used to calculate the amount of staked funds and, based on that, select a new proposer: PoS mechanism Choosing an algorithm When selecting a consensus algorithm, several key properties come into play. Balancing these factors is key. If you need strict finality and high throughput in a known, trusted group, a classical BFT approach might be best. For global, decentralized settings where anyone can participate, you might consider Proof of Work or Proof of Stake, understanding their trade‐offs in speed, security, and energy usage. 1. Finality ○ How quickly and definitively the system confirms that a decision or block will not be reversed. ○ Example: Classical BFT protocols often have immediate finality once enough signatures are collected, while Proof of Work offers probabilistic finality (the deeper a block is in the chain, the safer it is assumed to be). 2. Speed ○ How quickly the network can produce the next block or reach a new consensus state. ○ Trade‐off: Faster block times can boost throughput but may increase the risk of forks or require stronger network assumptions. 3. Performance ○ Overall throughput (transactions per second), latency (time to finalize a transaction), and resource usage. ○ Considerations: Some protocols demand less network overhead or computing power, while others might require more communication rounds or higher hardware capacity. 4. Scalability ○ How well the algorithm handles growth in the number of nodes or transaction volume. ○ Implications: Protocols that work fine for a handful of nodes may struggle or become too costly with hundreds or thousands of participants. Summary In this presentation, we covered: • Prominent protocols in blockchain and traditional distributed system consensus. • Proof of Work. • Proof of Stake. • Traditional BFT protocols. • Some more recent protocols, such as HotStuff.