THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, …

1 THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCELEEMON BAIRDMAY 31, 2016 SWIRLDS TECH REPORT new system, theSwirlds HASHGRAPH CONSENSUS algorithm, is pro-posed for replicated state machines with guaranteed Byzantine fault achievesfairness, in the sense that it is difficult for an attacker to manip-ulate which of two transactions will be chosen to be first in the consensusorder. It has complete asynchrony, no leaders, no round robin, no proof-of-work, eventual CONSENSUS with probability one, and high speed in the absenceof faults.

2 It is based on a gossip protocol, in which the participants don tjust gossip about transactions. Theygossip about gossip. They jointly build ahashgraphreflecting all of the gossip events. This allows Byzantine agreementto be achieved throughvirtual voting. Alice does not send Bob a vote overthe Internet. Instead, Bob calculates what vote Alice would have sent, basedon his knowledge of what Alice knows. This yields fair Byzantine agreementon a total order for all transactions, with very little communication overheadbeyond the transactions : Byzantine, Byzantine agreement, Byzantine fault tolerance, replicatedstate machine, fair, fairness, HASHGRAPH , gossip about gossip, virtual voting, SwirldsContentsList of Figures21.

3 Introduction22. Core concepts43. Gossip about gossip: the hashgraph54. CONSENSUS algorithm65. Proof of Byzantine fault tolerance116. Fairness197. Generalizations and enhancements208. Conclusions24 References259. Appendix A: CONSENSUS algorithm in functional form261 Revision date: March 18, 201812 THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS -TR-2016-01 List of Figures1 Gossip history as a directed graph52 The HASHGRAPH data structure73 Illustration of strongly Pseudocode: the SWIRLDS HASHGRAPH CONSENSUS algorithm125 Pseudocode: the divideRounds procedure126 Pseudocode: the decideFame procedure137 Pseudocode.

4 The finalOrder databases are often required to be replicated state machines withByzantine fault tolerance. Some authors have used the term Byzantine in a weaksense, such as assuming that attackers will not collude, or that communication isweakly asynchronous [1]. In this paper, Byzantine will be used in the strongsense of its original definition [2]: up to just under 1/3 of the members can beattackers, they can collude, and they can delete or delay messages between honestmembers with no bounds on the message delays.

5 The attackers can control thenetwork to delay and delete any messages, though at any time, if an honest memberrepeatedly sends messages to another member, the attackers must eventually allowone through. It is assumed that secure digital signatures exist, so attackers cannotundetectably modify messages. It is assumed that secure hash functions exist, forwhich collisions will never be found. This paper proposes and describes the Swirldshashgraph CONSENSUS algorithm, and proves Byzantine fault tolerance, under thestrong deterministic Byzantine system can be completely asynchronous, with un-bounded message delays, and still guarantee CONSENSUS , by the FLP theorem [3].

6 But it is possible for a nondeterministic system to achieve CONSENSUS with prob-ability one. The HASHGRAPH CONSENSUS algorithm is completely asynchronous, isnondeterministic, and achieves Byzantine agreement with probability systems, such as Paxos [4] or Raft [5] use a leader, which can make themvulnerable to large delays if an attacker launches a denial of service attack on thecurrent leader [6]. Many systems can even be delayed by just a single bad client[7]. In fact, the latter paper suggests that systems with such vulnerabilities mightbetter be described as Byzantine fault survivable rather than Byzantine faulttolerant.

7 HASHGRAPH CONSENSUS does not use a leader, and is resilient to denial ofservice attacks on small subsets of the systems, such as Bitcoin, are based on proof-of-work blockchains [8]. Thisavoids all the above problems. However, such systems cannot be Byzantine, becausea member never knows for sure when CONSENSUS has been achieved; they only havea probability of confidence that continues to rise over time. If two blocks are minedsimultaneously, then the chain will fork until the community can agree on whichbranch to extend.

8 If the blocks are added slowly, then the community can alwaysadd to the longer branch, and eventually the other branch will stop growing, and canbe pruned and discarded because it is stale . This leads to inefficiency, in the senseTHE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS -TR-2016-013that some blocks are mined properly, but discarded anyway. It also means that itis necessary to slow down how fast blocks are mined, so that the community canjointly prune branches faster than new branches sprout.

9 That is the purpose of theproof-of-work. By requiring that the miners solve difficult computation problemsto mine a block, it can ensure that the entire network will have sufficiently longdelays between mining events, on average. The HASHGRAPH CONSENSUS algorithm isequivalent to a block chain in which the chain is constantly branching, withoutany pruning, where no blocks are ever stale, and where each miner is allowed tomine many new blocks per second, without proof-of-work, and with 100% blockchains also require that electricity be wasted on extra compu-tations, and perhaps that expensive mining rigs be bought.

10 A proof-of-expired-timesystem [9] can avoid the wasted electricity (though perhaps not the cost of miningrigs) by using trusted hardware chips that delay for long periods, as if they weredoing proof-of-work computations. However, that requires that all participantstrust the company that created the chip. Such trust in chip venders exists in somesituations, but not in others, such as when FreeBSD was changed to not rely solelyon the hardware RDRAND instruction for secure random numbers, because wecannot trust them any more [10].