Congratulations on making this far! We’ve come a long way with a lot of information under our belt. In this chapter, we summarize some important topics. We will also look at some latest research and ideas and touch upon some more consensus protocols. An important aspect in consensus protocol research is formal design and verification of the algorithms. We briefly explain this important area in this chapter. Also, we compare some of the most common consensus protocols from different angles and introduce some important research directions.
Introduction
Consensus protocols are the backbone of distributed systems and especially blockchains. Throughout this book, we discussed several protocols and relevant topics. Currently, a blockchain is the most common candidate for implementing consensus protocols. In fact, they are at the core of the blockchain. With the blockchain, novel schemes are being introduced which address various problems including node scalability, transaction throughput, consensus efficiency, fault tolerance, interoperability, and various security aspects.
Distributed consensus is used almost everywhere between networked devices, not only in classical distributed systems that we are used to. This includes the Internet of Things, multiagent systems, distributed real-time systems, embedded systems, and lightweight devices. With the evolution of the blockchain, blockchain consensus adoption is expected to grow in all these systems too.
Other Protocols
In this section, we briefly introduce protocols that we did not cover before. As it is a vast area, a brief introduction only is given.
PoET
The proof of elapsed time algorithm was introduced by Intel in 2016. Remember we discussed earlier in Chapter 5 that a key purpose that PoW fulfills is the passage of some time until the network can converge to a canonical chain. Also, the leader, the miner whose block is accepted, wins the right to do so by solving PoW. PoET is fundamentally a leader election algorithm which utilizes trusted hardware to ensure that a certain time has elapsed before the next leader is selected for block proposal. The fundamental idea in PoET is to provide a mechanism of leader election by waiting randomly to be elected as a leader for proposing new blocks.
PoET in fact emulates the passage of time that would be consumed by PoW mining. The core idea is that every node randomly waits for some time before producing a block. The random waiting process runs inside a Trusted execution environment (TEE) to ensure that true time has indeed passed. For this purpose, Intel SGX or ARM TrustZone can be used. As TEEs provide confidentiality and integrity, the network in turn trusts the block producers. PoET tolerates up to 50% faulty TEE nodes. However, there is a possibility of Sybil attacks where an actor can run many TEE nodes, which can result in shortening the random waiting time. This can result in the creation of a malicious chain if more than 50% of TEEs become malicious. Another limitation is the stale chip problem highlighted by Ittay Eyal. This limitation results in hardware wastage, which results in resource wastage. The stale chip problem stems from the idea that it is financially beneficial for malicious actors to collect many old SGX chips, which increases their odds of becoming the producer of the next block. For example, adversarial actors can collect many old SGX chips to build mining rigs. It serves only one purpose, that is, mining, instead of buying modern CPUs with SGX, which will help in PoET consensus and be useful for general computation. Instead, they can choose to collect as many old SGX-enabled chips as they can and increase their chances of winning the mining lottery. Also, old SGX-enabled CPUs are cheap and can increase the use of old, inefficient CPUs. It is like Bitcoin miners racing to get as many fast ASICs as possible to increase their chances of becoming elected miners. However, it results in hardware wastage. There is also the possibility of hacking the chip's hardware. If an SGX chip is compromised, the malicious node can win the mining round every time, resulting in complete system compromise and undeserved incentivization of miners. This problem is called the broken chip problem.
Proof of Authority
We can think of PoA as a specific kind of proof of stake where the validators stake with their identity instead of economic tokens. The identity of a validator depicts the authority associated with the validator. A usual process of earning authority involves identity verification, reputation building, and a publicly scrutinized assessment process. The resultant group becomes a highly trusted set of validators to participate in the consensus protocol and produce blocks. Any violation by a validator of the rules of the protocol or inability to justify the earned right to produce blocks results in the removal of the dishonest validator by other validators and users on the network. It’s used in Rinkeby and Kovan Ethereum test nets. PoA provides good security as we have trusted validators in the network, but the network is somewhat centralized. The resilience against collusion and other security threats depends on the consensus algorithm used by the validators. If it’s a BFT variant, then usual BFT guarantees of 33% fault tolerance apply.
HoneyBadger BFT
HoneyBadger BFT (HBBFT) is a leaderless and randomized consensus protocol that works under asynchrony. It is the first practical asynchronous Byzantine consensus protocol. Generally, in distributed system theory, randomized algorithms are thought to be impractical. The HoneyBadger protocol authors claim to refute this belief. The approach taken to build this protocol is to improve efficiency by fine-tuning existing primitives and introducing new encryption techniques. These techniques result in removing bottlenecks in the protocol.
The first limitation to address is the leader bottleneck, for example, in PBFT and other variants there’s a standard reliable broadcast mechanism used to disseminate information from the leader to other nodes. This results in significant bandwidth consumption, for example, on the order of O(nB) where b is the blocks. To address this limitation, erasure coding can be used which allows the leader to send only erasure codes to the nodes. Then each node sends the erasure code stripe received to other nodes. This way, there is less load on the leader. Then all nodes simply reconstruct the message. This reduces the leader bandwidth to O(n). Transactions are processed in batches in HBBFT, which increases the throughput.
It is fundamentally an atomic broadcast protocol based on the multivalue Byzantine agreement and agreement on common subset. HoneyBadger uses several techniques developed previously, including erasure-coded reliable broadcast and common coin–based asynchronous Byzantine agreement. It also uses a threshold public key encryption (signatures) to provide common coins for the randomized ABA protocol.
HBBFT implements the total order using the asynchronous common subset (ACS). ACS is implemented using two other protocols, reliable broadcast (RBC) and asynchronous binary Byzantine agreement (ABA).
Reliable broadcast was introduced in 1987 by Bracha, commonly known as Bracha’s broadcast. This protocol tolerates f Byzantine faulty nodes where n = 3f + 1. It provides two guarantees, when a designated node (leader, broadcaster) broadcasts a message to all nodes. If any honest node delivers a message m broadcast by the broadcaster, then all correct nodes deliver m. Secondly, if the broadcasting node is correct, then every honest node delivers the message broadcast by the broadcaster node. Due to the message being echoed from all nodes to all, the communication complexity of this protocol becomes O(n2m), which is ok for smaller size networks, but in the blockchain world with 1000s of nodes, it is impractical.
The agreement on a common subset protocol for multiparty computation (ACS for MPC) was proposed by Ben-Or. ACS was used as a consensus primitive for multiparty computation under an asynchronous network. Multiparty computation (MPC) aims to create a mechanism to compute a function jointly over their inputs, while the inputs are kept private. ACS achieves an agreement on a common subset of at least n – f correct inputs. ACS uses RBC and ABA which enables a single bit agreement between parties.
Due to the communication complexity of RBC, HBBFT implements a different bandwidth-efficient broadcast mechanism called AVID by Cachin et.al., which uses erasure coding and cross checksums to reduce the communication complexity to O(nm). Here, the message m is erasure coded into different slices, and then each slice is hashed to produce a cross checksum. The broadcaster sends a slice and cross checksum to a node, and that node then echoes these to all other nodes. Once all slices reach all nodes, each node reconstructs the original message from these slices. This way, less bandwidth is consumed.
In summary, HBBFT solves consensus under asynchrony by using the asynchronous common subset protocol (ACS) and reliable broadcast (RBC), where each node proposes its value, and finally an asynchronous binary agreement protocol (ABA) runs, which decides on each proposal.
Avalanche
This new paradigm of consensus protocols achieves an agreement through random network sampling. The Avalanche family of protocols allow for a more relaxed form of agreement as compared to a deterministic agreement. However, it provides stronger safety than PoW and enjoys the node scalability of the Nakamoto consensus. We can think of it as a probabilistic version of the traditional quorum-based protocol but without explicit intersections in voting. The key idea is to combine the best of Nakamoto family with the best of classical family.
Safety: No two correct nodes accept conflicting transactions.
Liveness: Every correct node will eventually accept any transaction by an honest client.
This family has several protocols that build up the complete Avalanche protocol. The protocol is built gradually, starting from the so-called slush protocol, which provides metastability, snowflake, the BFT protocol, Snowball, which affirms the state by adding confidence to the decision; and, finally, Avalanche, which adds the DAG structure to improve efficiency.
With these innovations, the protocol provides quick finality, low latency, high throughput, and scalability.
DAG-Based Consensus Protocols
Usually, a blockchain is a linear structure; however, another class of algorithms has been proposed with nonlinear blockchain structures. The primary aim is efficiency, and these protocols are based on the premise that instead of relying on a limited and slow, linearly growing chain, the ledger should be able to expand in all directions, like a DAG, which can result in improved performance, high scalability, and fast transaction confirmation. DAGs require less communication, computation, and storage, thus increasing the performance. There are two types of DAG-based ledgers: block-based DAG and transaction-based DAG.
Block-Based DAG
Every vertex of a blockDAG contains a block. Each block can be a child of multiple blocks, instead of only one parent in linear designs, SPECTRE, PHANTOM, and Meshcash.
Transaction-Based DAG
Each vertex of a transaction-based DAG contains a transaction. IOTA Tangle, Byteball, Graphchain, and Avalanche are some examples of a transaction-based DAG.
Hashgraph is a permissioned graph–based blockchain with a BFT-type consensus protocol.
Ebb-and-Flow Protocols
This work is a response to a liveness issue found in Gasper. Gasper is a PoS-based consensus mechanism proposed for Ethereum’s beacon chain. It is a combination of Casper FFG, the finality gadget, and LMD GHOST, the fork choice rule. In this work, “snap-and-chat” protocols are proposed that are provably secure.
Nakamoto-style protocols provide liveness under network partitions and dynamic network participation, but they sacrifice safety over liveness. BFT protocols, on the other hand, provide safety (finality) under network partitions and low participation (participants less than <3f +1) but sacrifice liveness. It has been shown that it is impossible for a protocol to be both live under dynamic participation and safe under network partitions. This work answers the question of whether there exists a consensus mechanism that guarantees both availability and safety. The key idea is exquisite and proposes to create two ledgers instead of one. Remember, no protocol can ensure safety and liveness under network partitions and dynamic partitions with a single ledger. In other words, longest chain–style mechanisms favor liveness over safety and provide dynamic availability under different participation levels; however, BFT protocols favor safety over liveness and provide finality. This problem is called the availability-finality dilemma, as a single ledger cannot provide both properties. Therefore, the proposal is to create two ledgers. The first is an “available full ledger” that is always live but safe only without network partitions, similar to “longest chain–type PoW protocol.” The other ledger, called the “finalized prefix ledger,” is always safe but not live in low participation scenarios. This concept is the same as traditional BFT–style protocols, for example, PBFT, which stalls unless a threshold of participants is available. As the finalized prefix ledger is the prefix of the available full ledger, both ledgers eventually converge as a single authentic chain of history. In other words, the finalized prefix ledger is safe under network partitions and if less than one-third of participants are faulty.
Moreover, the available full ledger is live under dynamic (low) participation and if <50% of active players are Byzantine. This technique of combining BFT-style with Nakamoto-style protocols and creating so-called nested ledgers has been named the “Ebb-and-Flow” property. The so-called “snap-and-chat” protocols are developed to achieve the “Ebb-and-Flow” property. The finalized ledger is always the prefix of the available ledger, thus creating a combined proper single chain. At a high level, this mechanism works by ordering transactions into a chain of blocks by using some longest chain–type protocol, for example, PoW. Next, snapshots of prefixes from this blockchain feed into a partially synchronous BFT-style protocol for example, PBFT, which produces a chain containing multiple chains of blocks. Next, any duplicates or invalid transactions are removed, which creates a finalized prefix ledger. This finalized prefix ledger is added before the output of the PoW-style protocol, and any duplicates or invalid transactions are removed. This process finally creates an available single ledger.
There is a myriad of consensus protocols that exist, but we cannot cover all of them. However, we did explore quite a few covering different types and classes including randomized, deterministic, CFT, BFT, and Nakamoto-style protocols.
Let’s now turn our attention to formal verification which allows us to ensure the correctness of all these different consensus protocols.
Formal Verification
With all the activity in blockchain consensus research, we can now appreciate that it is such an active area of research. Many new protocols have been proposed to solve consensus problems in innovative ways. For example, some address efficiency, some look at scalability problems, some try to reduce message complexity, some modify the existing classical protocols to make them suitable for the blockchain, some try to speed up the consensus mechanism, and many other improvements and novelties are claimed. Here, a question arises: How do we ensure that these consensus protocols are correct and perform as we intend them to? For this purpose, usually researchers write research papers with proofs and arguments about the correctness of the protocols. Moreover, formal methods are used to ensure protocol correctness.
Formal methods are techniques used to model systems as mathematical objects. In other words, these are mathematically rigorous methods used to specify, design, and verify software or hardware systems. Such techniques include writing specifications in a formal logic and verifying them using model checking and formal proofs. Formal methods are divided into two broad domains called formal specification and formal verification. The first domain deals with writing precise and concrete specifications, and the latter concerns the development of proofs to prove the correctness of a specification.
A formal specification is a well-defined mathematical logic statement, whereas verification is the process of checking the specification by logic deductions, which is done mechanically. In other words, the specification is formally defined and then verified using a model checker or a theorem prover.
The reason why formal methods provide value is that they can symbolically check the entire state space of a design and ascertain the correctness of the design.
Create a formal model of the system to be checked.
Write a formal specification of the properties desired to be satisfied by our model.
Mechanically check the model to ensure that the model satisfies the specification.
Two categories of techniques are commonly used for verification: state exploration–based approaches and proof-based approaches. State exploration–based methods are automatic but are inefficient and difficult to scale. For example, a usual problem is state explosion, where the number of states to check grows so exponentially large that the model does not fit in a computer's memory. This is the reason the model must be finite, so that it can be efficiently verified. On the other hand, proof-based approaches (i.e., theorem proving) are more precise and less memory consuming but require human interaction and more in-depth knowledge of the proofs and relevant techniques. Proof-based techniques are the most elegant way of reasoning about properties of a system without any limit on the size of the spec. This is in contrast with model checking where there must be a limit on the size of the model. With proof-based techniques, you can reason about the system states and prove that with any input the system will always work as intended. Proof assistants such as Isabelle are used to help with reasoning about systems by allowing automated theorem proving.
A model checking mechanism consists of a formal specification language and a model checker. Model checking verifies systems formally using automated tools. This approach is gaining popularity among blockchain researchers to check formal specifications of a consensus protocol and ensure its correctness. The automated checker checks for the conditions to be satisfied and then confirms if the conditions are satisfied; otherwise, it produces counter examples (i.e., exceptions).
A flowchart of the model checking mechanism. The flow starts with requirements and system and ends at satisfied and counter example.
Model checking
TLA+ (temporal logic for actions) is a specification language designed by Leslie Lamport for describing and reasoning about concurrent systems. TLC is a model checker for design specifications written in TLA+. Another model checker is SPIN which checks specifications written in the Promela specification language.
A distributed blockchain consensus algorithm is usually evaluated against two classes of correctness properties: safety and liveness. Safety generally means “nothing bad will happen,” whereas liveness suggests “something good will eventually occur.” Both these properties have some subproperties, depending on the requirements. Usually, for consensus mechanisms, we have agreement, integrity, and validity conditions under the safety property, and termination is required for liveness. Consensus algorithms are mostly model checked under a system model by specifying how many nodes are in the system and what timing assumptions are made about the system. The model is then run to explore each state of the system and check if there is an execution that doesn’t terminate. Usually, this is done under a four-node model, based on the formula of 3f+1, which we’ve seen before.
A program is correct if, in all possible executions, the program behaves correctly according to the specification.
Impossibility Results
Unsolvability results in distributed systems show that certain problems cannot be solved. Lower bound results show that certain problems cannot be solved if resources are insufficient; in other words, these lower bound results show that certain problems are only solvable if a certain threshold of sufficient resources is available, that is, minimum resources required to solve a problem.
Consensus problem impossibility results
Crash Faults | Byzantine Faults | |
|---|---|---|
Synchronous | Consensus possible if f < n At least f + 1 rounds required where f < n >f network connectivity | f ≥ n/3 impossible >2f network connectivity minimum f < n/2 possible f + 1 rounds |
Asynchronous | Deterministic consensus impossible | Deterministic consensus impossible |
Partially synchronous | Impossible if n ≤ 2f | Impossible if n ≤ 3f >2f network connectivity f + 1 rounds |
The results in Table 10-1 are standard impossibility results. However, there are many others.
With the innovative research on blockchains, some new results have emerged. Andrew Lewis-Pye and Tim Roughgarden announced a fascinating new impossibility result similar to the CAP theorem where we can simultaneously choose only two of three properties. It states that no blockchain protocol can operate in the unconstrained environment (e.g., PoW), is live under a synchronous environment with significant and sharp dynamic changes in network resources (e.g., participant numbers), and satisfies probabilistic finality (consistency) in the partially synchronous environment. We can only choose two properties simultaneously out of the three properties stated earlier.
For example, in an unsized environment such as Bitcoin, imagine a node stops receiving any new blocks. Now the node cannot differentiate between whether the other nodes have lost their resources and cannot produce blocks anymore and if the block messages are delayed. Now if the node stops producing blocks and other nodes are low on resources and not producing blocks, it violates the liveness property, because this node must keep producing blocks even if others don’t. However, if it keeps producing blocks but the block messages are just delayed, then it is violating the consistency property, because there could be other conflicting blocks which are just delayed.
Complexity and Performance
A consensus algorithm can be evaluated from a communication complexity point of view. This involves calculations such as if the protocol is running in normal mode (no failures), then how many messages are required to be exchanged to reach consensus. Also, in case of leader failure when a view change occurs, how many messages are exchanged? Such metrics can help to understand how the algorithm behaves practically, which helps to estimate the efficiency of the algorithm.
Message delays can be defined as the number of messages required by an algorithm that cannot be sent before the previous message is received. In other words, it’s a message which is sent only after the previous one has been received. An algorithm requires n message delay; if some execution contains a chain of n messages, each of which cannot be sent before receiving the previous one.
To evaluate the cost associated with an algorithm, we can think of different complexity traits. There are three costs associated with a consensus algorithm: message complexity, communication complexity, and time complexity.
Message Complexity
Message complexity denotes the total number of messages that are required to be exchanged by the algorithm to reach consensus. For example, imagine an algorithm where all processes broadcast to all other nodes. This means that n(n − 1) messages will be received. This means this algorithm has O(n2) message complexity.
Communication Complexity (Bit Complexity)
Communication complexity is concerned with the total number of bits required to be exchanged by the algorithm. Think of the same algorithm we imagined about in the context of message complexity. If each message contains t bits, the algorithm exchanges tn(n − 1) bits, which means that the communication complexity is o(tn2) bits, that is, all to all.
Time Complexity
Time complexity is concerned with the amount of time needed to complete the execution of the algorithm. The time taken to execute the algorithm also depends on the time it takes to deliver the messages in the protocol. The time to deliver messages is quite large as compared to the local computation on the message. Time can be then thought of as the number of consecutive message delays. The same algorithm from the previous example running on a faultless network has O(1) time complexity.
Space Complexity
Space complexity deals with the total amount of space required for the algorithm to run. Space complexity is mostly relevant in a shared memory framework.
In message-passing distributed systems, such as blockchains, mostly message complexity is considered. Bit complexity is not so much relevant; however, if the size of the messages is big, then this can become another complexity measure to take into consideration.
Message complexity orders
Protocol | Normal Mode | View Change | Message Delays |
|---|---|---|---|
Paxos | O(n) | O(n2) | 4 |
PBFT | O(n2) | O(n3) | 5 |
Tendermint | O(n2) | O(n2) | 5 |
HotStuff | O(n) | O(n) | 10 |
DLS | O(n2) | O(n4) | O(n) rounds |
HoneyBadger | O(n) | − | − |
PoW | O(n) | − | − |
With these costs in mind, we can think of several bottlenecks in blockchain consensus protocols that result in poor performance. For example, the choice of all-to-all messages will inevitably result in more complexity.
Several techniques such as erasure coding can be used to reduce message complexity. Another technique called star topology (one to all – all to one), instead of mesh topology (all-to-all communication), can also reduce message complexity. Both these techniques are used in HoneyBadger and HotStuff, respectively.
Another class of algorithms that aims to improve performance and scalability of the consensus algorithms is to allow multiple nodes to act as leaders in parallel, that is, parallel leaders. Under this paradigm, multiple leaders can propose concurrently, which results in alleviating the CPU and bandwidth costs by distributing load evenly across all leaders. There are several algorithms in this category like HoneyBadger, Hashgraph, and RedBelly. However, it is possible that request duplication might occur with parallel leaders, which has been addressed in the Mir-BFT protocol.
Sharding is another technique that improves consensus performance. It allows breaking up the system state and validators into smaller sections. Each shard is responsible for a small subset of the entire state, and only a smaller subset of the global validator set is required to achieve consensus on that part of the state. This way, in parallel many shards exist, and by allowing consensus to run on smaller parts, great efficiency is achieved. To achieve a final state, some cross-shard communication and consolidation mechanism is also required.
Another technique to improve throughput is to offload data from the main chain to layer 2. Some techniques are developed in this regard, such as payment channels, lightning network for Bitcoin, commit chains, and Plasma. Techniques such as zero knowledge are used to provide evidence of off-chain execution. Prism and Bitcoin-NG are some of the techniques to improve consensus performance.
DAG-based consensus discussed earlier aims to improve performance by introducing graph-based structures that allow for non-interdependent commands to be committed in parallel.
Parallel execution of commands/smart contracts are also a technique that is proposed to improve performance. Parallel smart contracts (called Sealevel) are supported in the Solana blockchain.
Comparison of Protocols
Comparison of the main consensus algorithms
Property | POW | POS | POA | RAFT | PBFT |
|---|---|---|---|---|---|
Safety | Probabilistic | Probabilistic | Deterministic | Deterministic | Deterministic |
Adversary | Computational power control | Stake amount | Collusion/Byzantine | Collusion/crash | Collusion/Byzantine |
Method | Math puzzle solving | Value deposit | Authority | Leader-follower | Primary backup |
Network model | Synchronous | Synchronous | Synchronous | Partially synchronous | Partially synchronous |
Incentive | Yes | Yes | No | No | No |
Access control | Public | Public | Permissioned | Permissioned | Permissioned |
Block validation | Block header check/PoW valid | Staking rules | Identify check | Seal check | Seal check |
Finality | Probabilistic | Economic | Deterministic >50% validator agreement | Immediate | Immediate |
Misbehavior control | CPU/memory resources | Stake penalty | BFT | CFT | BFT |
Election type | Lottery | Lottery | Voting | Voting | Voting |
Liveness | Probabilistic | Probabilistic | Deterministic | Deterministic | Deterministic |
CAP | A over C | A over C | A over C | P over C | P over C |
Transaction capacity | 10s | 100s | 10s | 1000s | 1000s |
Fault tolerance | BFT | BFT | BFT | CFT | BFT |
Forking | Yes | Yes | No | No | No |
Special hardware | Yes | No | No | No | No |
Example | Bitcoin | Tezos | Rinkeby | GoQuorum | Sawtooth |
Dynamic membership | Yes | Yes | No | Yes | No |
PoA is assumed to be BFT based.
While only a single example is given, there are many, for example, Ethereum uses PoW too.
PBFT and RAFT both are state machine replication protocols with a leader-follower architecture, also called a primary backup. Usually, for PBFT a primary backup is used in the literature; however, for RAFT leader-follower terms are used. Fundamentally, they serve the same purpose.
Network Model
We can model a blockchain network in several ways, as shown in the following. Fundamentally, the networks are either synchronous, asynchronous, or partially synchronous. However, in literature several terms are used and as such explained as follows.
Synchronous
All messages are delivered within delta Δ time.
Eventual Synchrony
After an unknown global stabilization time (GST), all messages are delivered within delta Δ time.
Partial Synchrony
A protocol does not know what delta Δ is.
Weak Synchrony
Δ varies with time. In practice, the Δ increases systematically until liveness is achieved. However, the delays are not expected to grow exponentially.
Asynchronous
All messages are eventually delivered but have no fixed upper bound on message delivery time. The message delivery delay is finite, but no time bound is assumed on it.
Adversaries are primarily of two types, a static adversary and an adaptive adversary. A static adversary performs corruption before the protocol executes, whereas an adaptive adversary can cause corruption anytime during the execution of the protocol. There are two crash models, a crash failure model and a Byzantine failure model. Round-based algorithms have a send step, receive step, and compute step, which make one round.
Fault tolerance/resilience level: BFT or CFT.
Time complexity: How long the protocol takes to run and how many message delays.
Message complexity: What is the message complexity of the protocol in terms of the number of messages exchanged?
Trusted setup: Does the protocol need any setup like PKI or no dealer is required?
What is the adversary strength assumed in the model? Is it bounded or unbounded? What is the adversary corruption model? Is it static or adaptive?
What is the network model? Synchronous, asynchronous, or partially synchronous and its variations.
Is the protocol probabilistic or deterministic?
Does it use any cryptography?
Computational assumptions: Information-theoretic security or computational security.
Membership: Dynamic or fixed, permissioned, or public.
Such questions are useful to ask when analyzing a consensus protocol.
- 1.
Consensus algorithms aim to reach consensus on a single value, whereas SMR uses a consensus algorithm to decide on a sequence of operations for replication.
- 2.
Remember that PoW is not a consensus algorithm. It is a Sybil resistance mechanism; the consensus is reached via the choice of longest chain. Similarly, PoS is not a consensus algorithm. It is also a Sybil resistance mechanism, but decision on the canonical truth (choice of fork) is made by a BFT-style algorithm. We can think of it as a coupled mechanism where PoS is a Sybil control mechanism, whereas fork selection and finalization are done via a BFT-style algorithm. Similarly, PoH in Solana is a sequencing of events mechanism (an event orderer) which also allows for leader selection in a trustless manner; however, the decision on the final chain is made by voting on forks by a BFT-style algorithm called TowerBFT.
Research Directions
Most blockchain protocols, especially permissioned blockchain protocols, are based on PBFT. However, the world is evolving, and since 1999, when PBFT was introduced, a lot has changed. There have been attempts to use PBFT in blockchains by modifying it to blockchain needs, and it does work, but efficiency and scalability are still issues that need to be addressed. The future of the blockchain is multichain and heterogeneous. Also, there will be all sorts of different devices ranging from computers to lightweight resource-constrained IoT systems or mobile devices. Such a heterogeneous network requires another consensus mechanism that can withstand millions of heterogeneous devices with an asynchronous network. Cross-chain transactions and consensus are another aspect that needs further research. Some research on asynchronous BFT protocols has resulted in HoneyBadger BFT and BEAT, and, of course, we can do more. Similarly, Casper FFG, Casper CBC, GRANDPA, and BABE are the steps in the right direction for a multichain heterogeneous future. However, significant work still needs to be done.
As the blockchain technology evolves, so do the adversaries. There is a possibility of novel attack techniques, which, due to possible economic incentives on blockchains, can manifest sooner rather than later. This is so because concerned parties are willing to invest with the hope that new novel techniques for hacking blockchain networks will result in immediate revenue.
The use of quantum computing to enhance the classical results is an interesting topic. For example, a quantum computer can run in parallel with a classical distributed network or a blockchain. The quantum computer can elect a leader using the W state–based quantum leader election algorithm (discussed in Chapter 9) and pass the result on to the classical blockchain/distributed network. Such techniques can improve the security and efficiency of existing classical networks.
Classical permissioned network–related results cannot be directly applied to the permissionless settings; therefore, a need to modify those protocols to suit the blockchain world is needed. Some work is already done, for example, Casper FFG is inspired by PBFT.
Scalability and privacy of consensus protocols is an area of extreme importance. Privacy has two facets in the blockchain world: transaction value confidentiality and hiding users’ identities participating on the network. Scalability is concerned with node scalability as well as transaction throughput.
Mechanism design is a branch of microeconomics and built on the concept of game theory that studies how to design protocols that use incentivization to encourage rational actors to behave correctly. It is also called reverse game theory. It starts with an outcome and studies how entities in the system can work collaboratively to achieve a desired goal. As blockchains are cryptoeconomic incentive systems, much can be learned from the field of mechanism design. We can apply techniques and methods from the field of mechanism design to develop novel blockchain protocols that are robust.
Summary
In this last chapter, we summarized what we learned throughout this book. We also covered the algorithms that we did not before, especially new consensus protocols such as Avalanche and Ebb-and-Flow protocols. We also touched upon some research directions which require further work. We have come a long way from the Byzantine generals problem to Nakamoto consensus and now multichain consensus protocols. This is such a ripe area for research that we’ll only see more progress in it with more innovative ideas in the future.
In this book, we have explored the foundations of a blockchain and distributed consensus. We learned what impact quantum computing can have on distributed consensus and how an agreement could be achieved in quantum networks. Blockchain consensus is possibly the strongest area for research in the blockchain.
Thank you for staying with me in this wonderful journey. You are now capable of applying the knowledge from this book as a blockchain researcher and continuing your learning and research in the field of blockchain consensus.
Bibliography
- 1.
Decentralized thoughts: https://decentralizedthoughts.github.io
- 2.
Xiao, Y., Zhang, N., Lou, W., and Hou, Y.T., 2020. A survey of distributed consensus protocols for blockchain networks. IEEE Communications Surveys & Tutorials, 22(2), pp. 1432–1465.
- 3.
Miller, A., Xia, Y., Croman, K., Shi, E., and Song, D., 2016, October. The honeybadger of BFT protocols. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security (pp. 31–42).
- 4.
Lewis-Pye, A. and Roughgarden, T., 2020. Resource pools and the cap theorem. arXiv preprint arXiv:2006.10698.
- 5.
Neu, J., Tas, E.N., and Tse, D., 2021, May. Ebb-and-flow protocols: A resolution of the availability-finality dilemma. In 2021 IEEE Symposium on Security and Privacy (SP) (pp. 446–465). IEEE.
- 6.
Tim Roughgarden Lectures on foundations of blockchains: https://youtu.be/EfsSV7ni2ZM
- 7.
Fokkink, W., 2018. Distributed algorithms: an intuitive approach. MIT Press.
- 8.
More on mechanism design and blockchains here: https://medium.com/blockchannel/a-crash-course-in-mechanism-design-for-cryptoeconomic-applications-a9f06ab6a976