The blockchain is a distributed, peer-to-peer system with no central authority. While decentralization prevents corruption from any single party, it requires a reliable consensus protocol for decision-making. In computer science, this is a classic problem, called the Byzantine Generals Problem (BGP), which is encountered by distributed systems. In this article, we will lay out the BGP and survey several popular consensus mechanisms in current blockchain networks.
Byzantine Generals Problem
The Byzantine Generals Problem (BGP) describes a problem, whereby a group of generals wishes to formulate a plan for attacking a city. The generals are far away from each other and rely on messengers for communication. To succeed, they must agree on a time of coordinated attack or retreat. However, some messengers or even generals could be traitors. How can the rest of the loyal generals act despite the malicious actors passing around the wrong information? The loyal generals must depend on some rules so that they can reach the same course of action, despite the existence of a small number of traitors. This is the same problem as that encountered in a distributed and trustless network like blockchain, where one or more nodes might attempt to use the invalid information to influence for monetary gain, for example, and, double-spending. The consensus protocols, therefore, need to be able to deal with such situation, which means that they have to be Byzantine fault-tolerant (BFT).
There are two categories of Byzantine Fault-Tolerant protocols:
- Proof of X: The first category is generally called the proof of X. It uses a proof or qualification to decide on a leader who can validate and propose a new block, which is then propagated through the network. There also exist some conflict resolution mechanisms, if needed.
- Byzantine Agreement (BA): BA is the more traditional way to reach consensus. Nodes on the network validate new transactions individually, and when a quorum is reached (meaning, a sufficient set of nodes agrees on the validities of all of the transactions), then they will be packaged into a block to be included in the blockchain. This requires the majority of nodes being honest.
Since blockchain technology is still in an early phase of design and experiment, there are many varieties of proposed Byzantine fault-tolerant solutions. We will cover in more detail two protocols: Proof of Work and Proof of Stake, as well as briefly touching on nine others.
Proof of Work (PoW)
Many decentralized digital currencies were invented prior to Bitcoin, but they failed because they did not have a good answer to the Byzantine Generals Problem. It was not until Satoshi Nakamoto integrated Proof of Work (PoW) into the Bitcoin’s blockchain which (along with other cryptographic and distributed computing technologies) started the cryptocurrency craze we see today. PoW is also known as the Nakamoto consensus.
Without one central entity maintaining the ledger, the nodes in the Bitcoin network need to follow an algorithm that ensures the validity of transactions accepted into the shared ledger (also known as the Bitcoin blockchain). The blockchain contains blocks, and each block contains multiple transactions. Every node in the system can propose a new block composed of recent transactions, but the network as a whole needs to reach a consensus on which block to trust and to incorporate into the blockchain. Mining is the process that some nodes (called the miners) undertake to validate a set of transactions into a valid block. All miners compete to be the first to solve the computationally-intensive artificial problem based on some information from the latest valid block and the new candidate block. While it is difficult to discover the solution to this problem, it is very easy to check, once it is discovered, whether the solution is the correct one.
The computationally-intensive artificial ‘work’ uses brute force to find an answer to a variable (called a nonce) in the new block header such that hash of the new block will begin with a set number of leading zeros. The hash of the block is calculated by applying SHA-256 twice on this nonce and other variables in the block, such as version, the hash of the previous block, Merkle root, timestamp,
and difficulty in bits, etc.
SHA-256(SHA-256(nonce+other values)) = ‘000000….’
The number of leading zero required is determined by the variable ‘difficulty.’ The resulting hash needs to be smaller than the difficulty; hence the leading zeros. A nonce that meets this requirement is often called the ‘golden nonce.’ The reverse-hash problem of discovering the golden nonce is difficult, but once
it is found, the verification can be done in less than a second.When a miner discovers the solution, he/she becomes the leader and can propose the new block. He/She also receives some bitcoins as the reward. This is one of the major reasons that there are so many miners doing the ‘work.’ The intensity of the computational ‘work’ deters miners to include dishonest transactions, as they will have to compete with the valid chain of transactions supported by the computing power of the rest of the honest nodes. In addition, for those with a lot of computation power, PoW is set up such that it is in their economic advantage to act honestly and gain the mining and the transaction fees, rather than losing money on blocks that would eventually be rejected by the network.
If there are any questionable blocks in the system, the blocks in the ‘longest chain’ are picked. The longest chain is the chain whose sum of difficulties for its constituent blocks is the largest. And thus, the consensus is reached.
Proof of Stake (PoS)
While Proof of Work (PoW) is proven to be an effective consensus protocol, there is a major drawback brought about by its worldwide popularity. There are so many miners working towards each block that this results in tremendous wasted computing power and electricity. There is also the concern that Bitcoin mining might not be as decentralized as originally anticipated because, in practice, the top four or five Bitcoin mining pools own more than 50% of the computing power.
The energy consumption of the Bitcoin network is similar to the entire energy consumption of Switzerland. The electricity consumed for a single transaction can power 32.34 U.S. households for an entire day.This has caused great concern for developers in the cryptocurrency space, notably Ethereum’s founder, Vitalik Buterin. The Ethereum network is planning to convert Ethereum from PoW to Proof of Stake (PoS) in late 2018. Unlike PoW, where the fastest node (miner) becomes the leader, in PoS, a leader is pseudo-randomly selected. In order to be selected as the leader, each node must raise a ‘stake.’ If the leader acts maliciously, then he or she will lose all of his/her stake as well as the privilege of participating in the future. The honest leader will be rewarded by transaction fees, and there is no mining in PoS networks.
Some other notable cryptocurrencies that are using PoS are DASH, NEO, PIVX, OkCash, NAV Coin, Stratis, and Reddcoin.
We have just discussed the general PoS protocol, and the current reality is that there are many variations of PoS. This will remain true for most of these protocols, as we are only at the beginning of cryptocurrency era.
Casper
Ethereum has chosen a PoS protocol called Casper as its future consensus protocol. In Casper, a participating node, called a bonded validator, has to first place a security deposit, calling bonding. After bonding, the validator can bet on which block will be included next. If the block is accepted into the blockchain, the validator will then receive a reward in proportion to his/her bet. If the validator bets against the consensus, he/she will lose his/her bet. If this validator becomes dishonest, then all of his/her deposit will also get deleted.
Delegated Proof of Stake
Delegated Proof of Stake (DPoS) was invented by Daniel Larimer to use voting to reach consensus. The stakeholders (owners of network coins) elect delegates and witnesses. The delegates are unpaid and their responsibilities are to maintain and tune network parameters, such as fee schedules, block intervals, and transaction sizes, etc. The delegates can also propose other types of changes to the network and their proposals are distributed to be voted on by all stakeholders. On the other hand, the witnesses are responsible for validating transactions and creating blocks. Selection of the leader, who will produce the next block, is deterministic and turn-based with their turns being shuffled periodically. Witnesses are paid per block generation. If a witness fails to produce a block, they may lose their privileges.
Some notable cryptocurrencies using DPoS are Ark, BitShares, EOS, Lisk, Rise, and Oxycoin.
Proof-of-Authority
Proof of Authority, (PoA) coined by Gavin Wood, evolved from PoS and uses validators’ reputation as the stake. The reason for this evolution is that an equal amount of coin ownership does not necessarily translate into equal motivation towards ensuring the honesty of the network because every coin owner’s real-world net worth is different. On the other hand, everyone has one and only one reputation, therefore, this is a better choice as the ‘stake.’ Not only does reputation normalize the playing field, but it also serves as an intrinsic incentive for the validator. The assumption is that once a reputation is gone, it is very difficult to restore it. It is not surprising that the privilege of becoming a validator in a PoA network is difficult to obtain because the validator’s identity will be cross-checked in the real world, such as requiring him or her to hold an active notary public license.
PoA networks have high throughput but are centrally-controlled by the validators.
Some notable cryptocurrencies that use PoA are POA Network, Oracles Network, and Kovan Testnet of Ethereum.
Proof of Capacity (Proof of Space)
Proof of Capacity (PoC) or Proof of Space (PoSpace) is an alternative to PoW. Instead of using miners’ computing power to solve cryptographic puzzles, the miners use their hard drive space to store and look up solutions to puzzles. Instead of doing computing-intensive work in real time to discover the answer to the puzzle for each block as in PoW, the miners first work on a process called “plotting” ahead of the time. This process loads up their hard drives with many possible solutions to different puzzles. Some solutions solve the puzzle faster than others, so the miner who can solve the fastest becomes the leader and receives the block reward. Miners with more hard drive space have more potential solutions and therefore a higher chance to discover the fastest solutions.
PoC is designed as being a fairer and greener alternative to PoW because storage is cheaper, consumes less energy and the whole process requires less computing power. Some people have even tried mining a PoC network using their mobile phones. However, there is still the concern that a rich player, such as a nation state or a big corporation, could potentially employ a large amount of storage and get to sign most blocks.
Proof of Elapsed Time (PoET)
Proof of Elapsed Time was contributed by Intel for the permission-ed (meaning private and invite-only) Hyperledger Sawtooth blockchain project. PoET is a lottery-design consensus protocol that builds on trusted execution environments provided by Intel’s SGX CPUs. SGX allows user-level code to allocate private regions of memory, called enclaves, which are protected from processes running at higher privilege levels. Instead of solving cryptographic puzzles, the system uses randomly-generated wait times to determine the leader among a large population of participants.
PoET essentially works as follows: 1. Every validator requests a wait time from an enclave (a trusted function).
2. The validator with the shortest wait time for a particular transaction block is elected as the leader.
While the PoET solution looks very elegant, a major concern is that it is locked-in with Intel’s hardware. Researchers have also pointed out that SGX is not without security flaws.
We have discussed several of the first set of Byzantine fault-tolerant consensus protocols. In the next section, we will discuss the second category of Byzantine Agreement protocols. We will discuss the following protocols in the context of the cryptocurrency that employed them.
Algorand
Algorand was invented by Turing Award winner and MIT cryptography professor Silvio Micali. It is similar to PoS in that account holders with larger shares have higher chances of becoming a leader. After the previous block is officially added to the chain, the one-time committee of block proposers is selected using a cryptographic algorithm. The selection process is the intriguing part.
First, the users have to automatically opt-in. Those who are opted-in can find out, on their own and without contacting anyone else on the network, that they have become part of the committee. This is achieved using a program that takes information from the previous block as the input, and which then outputs to the user whether he or she is in or not. For the user, it is like scratching a lottery ticket to find out if she has won or not. Those that are selected then verify the transactions and propagate the new information of the new block to the network. The identities of the committee are only released after the block has been confirmed.
Here are the steps from committee selection to block generation: 1. A random leader is selected and she proposes and circulates a new block.
2. A randomly-selected committee is chosen and reaches a Byzantine agreement on the block proposed by the leader.
3. The agreed-upon block is digitally-signed by a certain number of committee members.
4. The digital signatures and the identities of the signers, as well as the hash of the new block, are circulated so that everyone on the network can authenticate the new block.
Compared with PoW, Algorand requires minimal computation power and it does not fork with overwhelmingly high probability. A block that is entered into the blockchain is considered final.
XRP Ledger Consensus Protocol (XLCP) from Ripple
In the Ripple network, the nodes are called tracking nodes, and they can distribute transactions from clients and respond to queries about the ledger. A small set of tracking nodes are also validator nodes and they contribute to advancing the ledger sequence. Anyone can launch a validator node, but they are recommended to register with Ripple and be open about their identity.
Here is how XLCP works: 1. A transaction is submitted by a client to a node in the network.
2. This node accepts it as a candidate transaction and then relays it to other nodes in the network.
3. Each node subscribes to a set of validator nodes and makes its approval decision based on the recommendation of the validators to which they subscribe.
4. When a supermajority (80%) of nodes approves this candidate transaction, this transaction will be included in the new “last validated ledger.”
Stellar Consensus Protocol (SCP) from Stellar
SCP was invented by Professor David Mazières from Stanford and constructed as a Federated Byzantine Agreement (FBA). Instead of reaching a quorum from all nodes in the system, each node selects a quorum slice, which is a subset of other nodes that it trusts. The node waits for consensus from its trusted nodes, and not every node. This essentially leaves the bad actors out of the circles of trust and the rest of the honest nodes can reach consensus very quickly.
Practical Byzantine Fault Tolerance (PBFT) from HyperLedger Fabric v0.6
In HyperLedger Fabric v0.6 where Practical Byzantine Fault Tolerance is implemented, every node in this private network receives every transaction to validate. However, not all transactions reach all nodes in the same sequence. The network randomly chooses a leader that proposes the sequence. All the rest of the nodes then communicate with each other about the sequence until a consensus is reached.
Delegated Byzantine Fault Tolerance (dBFT) from NEO
Delegated Byzantine Fault Tolerant leverages proxy voting. In dBFT, delegates are called bookkeepers and they can validate transactions. NEO token owners pick the bookkeepers they support via voting. When the selected bookkeepers reach a consensus on a set of transactions, a new block can be generated. Voting, and therefore the selection of bookkeepers, happens continuously. Bookkeepers are required to register their identities with the NEO network.