Consensus

The con­sen­sus pro­to­col describes how a network’s nodes reach agree­ment on what to do next. In a blockchain con­text, it reg­u­lates things like trans­ac­tion valid­i­ty, inclu­sion of new nodes and deal­ing with mali­cious nodes (sybil con­trol), block pro­duc­tion, or reward dis­tri­b­u­tion. Any run­ning system’s con­sen­sus can poten­tial­ly be affect­ed by tiny changes in the node soft­ware, caus­ing vol­un­tary or invol­un­tary chain splits or chain stalls as the par­tic­i­pat­ing nodes can no longer reach agree­ment on how to proceed. 

List of Consensus Protocols

Work in progress. This entry only deals with high-lev­el dif­fer­ences of the var­i­ous con­sen­sus pro­to­cols. While sybil con­trol is an essen­tial part of any fault tol­er­ant con­sen­sus sys­tem, actu­al con­sen­sus-find­ing mech­a­nisms and sybil con­trol mech­a­nisms can to a cer­tain extent be com­bined freely. The two con­cepts should not be confused.

• Nakamo­to-Style Con­sen­sus: The orig­i­nal blockchain con­sen­sus mod­el pro­posed by Satoshi Nakamo­to ran­dom­ly selects block pro­duc­ers via proof of work min­ing. Nakamo­to nodes will always track the heav­i­est chain (the one with the most accu­mu­lat­ed work). Avail­abil­i­ty is pri­or­i­tized over con­sis­ten­cy. Chain reor­ga­ni­za­tions, espe­cial­ly near the chain tip, can hap­pen as a heav­ier chain gets pro­duced by mali­cious or well-mean­ing nodes. Nakamo­to con­sen­sus remains reli­able as long as the num­ber of mali­cious nodes in the net­work does not exceed 50%. Slow­ness, and high resource usage due to min­ing are com­mon issues of Nakamo­to-style consensus.
• Ten­der­mint: In this round-based con­sen­sus mech­a­nism, a block pro­pos­er sug­gests a new block and the network’s val­ida­tor nodes then try to reach 75% agree­ment on that new block. If the agree­ment process fails, the round reverts to the block pro­pos­al phase. Ten­der­mint reach­es instant final­i­ty of trans­ac­tions on block inclu­sion, at the cost of avail­abil­i­ty, since the chain will not be extend­ed if the val­ida­tors are unable to reach 75% con­sen­sus. Ten­der­mint has been imple­ment­ed as part of the Cos­mos fed­er­at­ed chain ecosys­tem. Ten­der­mint works well with PoS-based sybil con­trol mech­a­nisms. Because the pro­to­col requires 75% con­sen­sus to pro­duce a new block, actu­al imple­men­ta­tions will tend to improve com­mu­ni­ca­tion effi­cien­cy by oper­at­ing with a rel­a­tive­ly small set of (del­e­gat­ed) val­ida­tor nodes.
• Algo­rand: Algo­rand solves the leader (block pro­pos­er) selec­tion prob­lem by emit­ting an unpre­dictable selec­tion seed with each new block. This allows for a sys­tem that is effi­cient thanks to its abil­i­ty to select a rea­son­ably small val­ida­tor group for each block, yet egal­i­tar­i­an, since any par­tic­i­pat­ing node in the net­work has a chance to become a block pro­duc­er. This con­sen­sus pro­to­col elim­i­nates the need to invest work to achieve ran­dom leader selec­tion. Imple­ment­ed by the Algo­rand blockchain, it is com­bined with proof of stake as a sybil con­trol mech­a­nism. Sim­i­lar to Ten­der­mint, blocks are set­tled in a propose/vote/confirm round, requir­ing 75% agree­ment to achieve instant final­i­ty on block production.
• Snow (Avalanche): Pro­posed by researchers at Cor­nell Uni­ver­si­ty and imple­ment­ed as part of the AVA dis­trib­uted ledger tech­nol­o­gy, the Snow pro­to­col suite estab­lish­es node con­sen­sus via a net­work sam­pling strat­e­gy: indi­vid­ual nodes do not com­mu­ni­cate with all nodes in the net­work. Instead, they form their opin­ion on the network’s state by repeat­ed­ly com­mu­ni­cat­ing with ran­dom sub-sam­ples of nodes. This approach enables high­er par­al­lelism, low­er resource usage and faster through­put. The Snow pro­to­col suite reach­es metasta­bil­i­ty of state as the network’s nodes grad­u­al­ly con­verge towards the desired out­come. Pos­si­ble crit­i­cal issues of this approach are fail­ure to reach con­sen­sus, and safe­ty con­cerns relat­ed to the asyn­chro­nous prop­er­ties of the pro­to­col (e.g. mes­sage reordering/delaying attacks). 

Sources

• https://files.avalabs.org/papers/consensus.pdf
• https://btcmanager.com/avalanche-protocolnew-age-consensus/
• https://www.algorand.com/what-we-do/technology/core-blockchain-innovation