THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM:
FAIR, FAST, BYZANTINE FAULT TOLERANCELEEMON BAIRD
MAY 31, 2016
SWIRLDS TECH REPORT SWIRLDS-TR-2016-01

Abstract. A new system, the Swirlds hashgraph consensus algorithm, is proposed for replicated state machines with guaranteed Byzantine fault tolerance.
It achieves fairness, in the sense that it is difficult for an attacker to manipulate which of two transactions will be chosen to be first in the consensus
order. It has complete asynchrony, no leaders, no round robin, no proof-ofwork, eventual consensus with probability one, and high speed in the absenceof faults. It is based on a gossip protocol, in which the participants don’t
just gossip about transactions. They gossip about gossip. They jointly build ahashgraph reflecting all of the gossip events. This allows Byzantine agreement
to be achieved through virtual 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 agreement
on a total order for all transactions, with very little communication overhead
beyond the transactions themselves.

Keywords: Byzantine, Byzantine agreement, Byzantine fault tolerance, replicatedstate machine, fair, fairness, hashgraph, gossip about gossip, virtual voting, Swirlds
Contents
List of Figures
1. Introduction
2. Core concepts
3. Gossip about gossip: the hashgraph
4. Consensus algorithm
5. Proof of Byzantine fault tolerance
6. Fairness
7. Generalizations and enhancements
8. Conclusions
References
9. Appendix A: Consensus algorithm in functional form

1

Revision date: March 18, 2018
1

2
2
4
5
6
11
19
20
24
25
26

2

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

List of Figures
1

Gossip history as a directed graph

52

The hashgraph data structure

73

Illustration of strongly seeing.

94

Pseudocode: the Swirlds hashgraph consensus algorithm

125

Pseudocode: the divideRounds procedure

126

Pseudocode: the decideFame procedure

13

7

Pseudocode: the finalOrder procedure14

1. Introduction
Distributed databases are often required to be replicated state machines with
Byzantine fault tolerance. Some authors have used the term “Byzantine” in a weaksense, such as assuming that attackers will not collude, or that communication is
weakly asynchronous [1]. In this paper, “Byzantine” will be used in the strong
sense of its original definition [2]: up to just under 1/3 of the members can be
attackers, they can collude, and they can delete or delay messages between honest
members with no bounds on the message delays. The attackers can control the
network to delay and delete any messages, though at any time, if an honest member
repeatedly sends messages to another member, the attackers must eventually allow
one through. It is assumed that secure digital signatures exist, so attackers cannot
undetectably modify messages. It is assumed that secure hash functions exist, forwhich collisions will never be found. This paper proposes and describes the Swirlds
hashgraph consensus algorithm, and proves Byzantine fault tolerance, under thestrong definition.
No deterministic Byzantine system can be completely asynchronous, with unbounded message delays, and still guarantee consensus, by the FLP theorem [3].
But it is possible for a nondeterministic system to achieve consensus with probability one. The hashgraph consensus algorithm is completely asynchronous, isnondeterministic, and achieves Byzantine agreement with probability one.
Some 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 might
better be described as “Byzantine fault survivable” rather than “Byzantine fault
tolerant”. Hashgraph consensus does not use a leader, and is resilient to denial ofservice attacks on small subsets of the members.
Other systems, such as Bitcoin, are based on proof-of-work blockchains [8]. Thisavoids all the above problems. However, such systems cannot be Byzantine, because
a 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 mined
simultaneously, then the chain will fork until the community can agree on whichbranch to extend. If the blocks are added slowly, then the community can always
add 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 senseTHE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

3

that 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 can
jointly prune branches faster than new branches sprout. That is the purpose of theproof-of-work. By requiring that the miners solve difficult computation problems
to mine a block, it can ensure that the entire network will have sufficiently long
delays between mining events, on average. The hashgraph consensus algorithm isequivalent to a block chain in which the “chain” is constantly branching, without
any 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% efficiency.
Proof-of-work blockchains also require that electricity be wasted on extra computations, and perhaps that expensive mining rigs be bought. 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 were
doing proof-of-work computations. However, that requires that all participants
trust 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 solely
on the hardware RDRAND instruction for secure random numbers, because “wecannot trust them any more” [10].
Byzantine agreement systems have been developed for Byzantine agreement thatavoid the above problems. These systems typically exchange many messages forthe members to vote. For n members to decide a single YES/NO question, somesystems can require O(n) messages to be sent across the network. Other systems
can require O(n2 ), or even O(n3 ) messages crossing the network per binary decision[11]. An algorithm for a single YES/NO decision can then be extended to deciding
a total order on a set of transactions, which may further increase the vote traffic.
Hashgraph sends no votes at all over the network, because all voting is virtual.

4

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

2. Core concepts
The hashgraph consensus algorithm is based on the following core concepts.
• Transactions - any member can create a signed transaction at any time. All
members get a copy of it, and the community reaches Byzantine agreementon the order of those transactions.
• Fairness - it should be difficult for a small group of attackers to unfairly
influence the order of transactions that is chosen as the consensus.
• Gossip - information spreads by each member repeatedly choosing anothermember at random, and telling them all they know
• Hashgraph - a data structure that records who gossiped to whom, and inwhat order.
• Gossip about gossip - the hashgraph is spread through the gossip protocol.
The information being gossiped is the history of the gossip itself, so it is“gossip about gossip”. This uses very little bandwidth overhead beyond
simply gossiping the transactions alone.
• Virtual voting - every member has a copy of the hashgraph, so Alice cancalculate what vote Bob would have sent her, if they had been runninga traditional Byzantine agreement protocol that involved sending votes.
So Bob doesn’t need to actually her the vote. Every member can reach
Byzantine agreement on any number of decisions, without a single voteever being sent. The hashgraph alone is sufficient. So zero bandwidth isused, beyond simply gossiping the hashgraph.
• Famous witnesses - The community could put a list of n transactions into
order by running separate Byzantine agreement protocols on O(n log n)different yes/no questions of the form “did event x come before event y?” A
much faster approach is to pick just a few events (vertices in the hashgraph),to be called witnesses, and define a witness to be famous if the hashgraphshows that most members received it fairly soon after it was created. Thenit’s sufficient to run the Byzantine agreement protocol only for witnesses,
deciding for each witness the single question “is this witness famous?” Once
Byzantine agreement is reached on the exact set of famous witnesses, it iseasy to derive from the hashgraph a fair total order for all events.
• Strongly seeing - given any two vertices x and y in the hashgraph, it canbe immediately calculated whether x can strongly see y, which is defined
to be true if they are connected by multiple directed paths passing throughenough members. This concept allows the key lemma to be proved: that
if Alice and Bob are both able to calculate Carol’s virtual vote on a given
question, then Alice and Bob get the same answer. That lemma forms thefoundation for the rest of the mathematical proof of Byzantine agreementwith probability one.

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

Alice!

Bob!

Carol!

Dave!

5

Ed!

Time!

Figure 1. Gossip history as a directed graph. The history of any
gossip protocol can be represented by a graph where each member
is one column of vertices. When Alice receives gossip from Bob,
telling her everything he knows, that gossip event is represented
by a vertex in the Alice column, with two edges going downward
to the immediately-preceding gossip events by Alice and Bob.
3. Gossip about gossip: the hashgraph
Hashgraph consensus uses a gossip protocol. This means that a member suchas Alice will choose another member at random, such as Bob, and then Alice willtell Bob all of the information she knows so far. Alice then repeats with a different
random member. Bob repeatedly does the same, and all other members do thesame. In this way, if a single member becomes aware of new information, it will
spread exponentially fast through the community until every member is aware ofit.
The history of any gossip protocol can be illustrated by a directed graph like
Figure 1. Each vertex in the Alice column represents a gossip event. For example,
the top event in the Alice column represents Bob performing a gossip sync to Alicein which Bob sent her all of the information that he knew. That vertex has two
downward edges, connecting to the immediately-preceding gossips for Alice andBob. Time flows up the graph, so lower vertices represent earlier events in history.
In a typical gossip protocol, a diagram such as this is merely used to discuss the
protocol; there is no actual graph like that stored in memory anywhere.
In hashgraph consensus, that graph is an actual data structure. Figure 2 illustrates this data structure. Each event (vertex) is stored in memory as a sequence ofbytes, signed by its creator. For example, one event by Alice (red) records the factthat Bob performed a gossip sync in which he sent her everything he knew. This
event is created by Alice and signed by her, and contains the hashes of two otherevents: her last event and Bob’s last event prior to that gossip sync. The red event
can also contain a payload of any transactions that Alice chooses to create at thatmoment, and perhaps a timestamp which is the time and date that Alice claims tohave created it. The other ancestors of that event (gray) are not contained within
it, but are determined by the set of cryptographic hashes. Data structures withgraphs of hashes have been used for other purposes, such as in Git where the vertices are versions of a file tree, and the edges represent changes. But Git stores no

6

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

record of how members communicated. The hashgraph is for a different purpose.
It records the history of how the members communicated.
Gossip protocols are widely used to transfer a variety of types of information.
They can involve gossiping about user identities, or gossiping about transactions, orgossiping about blockchain blocks, or gossiping about any other information thatneeds to be distributed. But what if the protocol were to gossip about gossip?
What if the members were gossiping to transfer the hashgraph itself? When Bob
gossiped to Alice, he would give her all of the events which he knew and she didnot.
Gossiping a hashgraph gives the participants a great deal of information. If a
new transaction is placed in the payload of an event, it will quickly spread to allmembers, until every member knows it. Alice will learn of the transaction. And
she will know exactly when Bob learned of the transaction. And she will know
exactly when Carol learned of the fact that Bob had learned of that transaction.
Deep chains of such reasoning become possible when all members have a copy ofthe hashgraph. As the hashgraph grows upward, the different members may haveslightly different subsets of the new events near the top, but they will quickly converge to having exactly the same events lower down in the hashgraph. Furthermore,
if Alice and Bob happen to both have a given event, then they are guaranteed toalso both have all its ancestors. And they will agree on all the edges in the subgraphof those ancestors. All of this allows powerful algorithms to run locally, includingfor Byzantine fault tolerance.
This power comes with very little communication overhead. If a community issimply gossiping signed transactions that they create, there is a certain amount of
bandwidth required. If they instead gossip a hashgraph, and if there are enoughtransactions that a typical event contains at least one transaction, then the overhead
is minimal. Instead of Alice signing a transaction she creates, she will sign theevent she creates to contain that transaction. Either way, she is only sending one
signature. And either way, she must send the transaction itself. The only extra
overhead is that she must send the two hashes. But even that can be greatlycompressed. In figure 2, Alice will not send Carol the red event until Carol alreadyhas all its earlier ancestors (either from Alice, or from an earlier sync with someoneelse). So Alice does not need to send the two hashes of the two blue parent events.
It is sufficient to tell Carol that this event is the next one by Alice, and that its
other-parent is the third one by Bob. With appropriate compression, this can besent in very few bytes, adding only a few percent to the size of the message beingsent.
4. Consensus algorithm
It is not enough to ensure that every member knows every event. It is also
necessary to agree on a linear ordering of the events, and thus of the transactions
recorded inside the events. Most Byzantine fault tolerance protocols without aleader depend on members sending each other votes. So for n members to agree
on a single YES/NO question might require O(n2 ) voting messages to be sent overthe network, as every member tells every other member their vote. Some of these
protocols require receipts on votes sent to everyone, making them O(n3 ). And they
may require multiple rounds of voting, which further increases the number of voting
messages sent.

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

Alice!

Bob!

Carol!

Dave!

7

Ed!

Figure 2. The hashgraph data structure. Alice creates an event(red) recording the occurrence of Bob doing a gossip sync to her
and telling her everything he knows. The event contains a hash of
two parent events (blue): the self-parent (dark blue) by the same
creator Alice, and the other-parent (light blue) by Bob. It also
contains a payload of any new transactions that Alice chooses tocreate at that moment, and a digital signature by Alice. The otherancestor events (gray) are not stored in the red event, but they
are determined by all the hashes. The other self-ancestors (darkgray) are those reachable by sequences of self-parent links, and theothers (light gray) are not.
Hashgraph consensus does not require any votes to be sent. Every member has a
copy of the hashgraph. If Alice and Bob both have the same hashgraph, then they
can calculate a total order on the events according to any deterministic function ofthat hashgraph, and they will both get the same answer. Therefore, consensus isachieved, even without sending vote messages.
Of course, Alice and Bob may not have exactly the same hashgraph at any given
moment. They will typically match in the older events. But for the very recent
events, each may have events that the other has not yet seen. Furthermore, there
may occasionally be a new event released to the community that should be placedin a lower (earlier) location in the hashgraph. The hashgraph consensus algorithm
deals with these issue using a system that is best thought of as virtual voting.
Suppose Alice has hashgraph A and Bob hash hashgraph B. These hashgraphs
may be slightly different at any given moment, but they will always be consistent.
Consistent means that if A and B both contain event x, then they will both containexactly the same set of ancestors for x, and will both contain exactly the same setof edges between those ancestors. If Alice knows of x and Bob does not, and both ofthem are honest and actively participating, then we would expect Bob to learn of x
fairly quickly, through the gossip protocol. The consensus algorithm assumes thatwill happen eventually, but does not make any assumptions about how fast it will
happen. The protocol is completely asynchronous, and does not make assumptions
about timeout periods, or the speed of gossip, or the rate at which progress is made.
Alice will calculate a total order on the events in A by calculating a series ofelections. In each election, some of the events in A will be considered to cast a
vote, and some of the events in A will be considered to receive that vote. Alice will

8

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

calculate multiple elections, and a given event might participate in some elections
but not others, and might cast different votes in different elections. If the event
was created by Bob, we will talk of Bob voting a certain way in a given election.
But the actual member Bob is not involved. This is purely a calculation that Aliceis performing locally, where she is calculating what vote Bob would have sent her,if the real Bob were actually sending votes over the internet to her.
This virtual voting has several benefits. In addition to saving bandwidth, it
ensures that members always calculate their votes according to the rules. If Aliceis honest, she will calculate virtual votes for the virtual Bob that are honest. Even
if the real Bob is a cheater, he cannot attack Alice by making the virtual Bob voteincorrectly.
Bob can try to cheat in a different way. Suppose Bob creates an event x with acertain self-parent hash pointing to his previous event z. Then Bob creates a newevent y, but gives it a self-parent hash of z, instead of giving it a self-parent hash ofx as he should. This means that the events by Bob in the hashgraph will no longer
be a chain, as they should be. They will now be a tree, because he has created afork. If Bob gossips x to Alice and y to Carol, then for a while, Alice and Carol
may not be aware of the fork. And Alice may calculate a virtual vote for x thatis different from Carol’s virtual vote for y. So it is possible for a fork to be spread
across consistent hashgraphs. In this case, there may be a moment when Alice has
a hashgraph containing x but not y, and Carol has a hashgraph with y and not x,
and so a fork exists, but neither member is yet aware of the fact that it is a fork.
The hashgraph consensus algorithm prevents this attack by using the conceptof one state seeing another, and the concept of one state strongly seeing another.
These are based on definitions of ancestor and self-ancestor such that every event
is considered to be both an ancestor and self-ancestor of itself.
If Bob creates two events x and y, neither of which is a self-ancestor of the other,
then Bob has cheated by forking. If some event w has x as an ancestor but doesn’t
have y as an ancestor, then the event w can see event x. However, if both x and y
are ancestors of w, then w is defined to not see either of them, nor any other eventby the same creator. In other words, w can see x if x is known to it, and no forks
by that creator are known to it.
If there are n members (n > 1), then an event w can strongly see an event x,
if w can see more than 2n/3 events by different members, each of which can see
x. This concept is illustrated in Figure 3. Four copies of the same hashgraph are
shown, each with a different event on the bottom row colored orange. In (d), theyellow event at the top can see 4 red events by different members, each of which
can see the orange event at the bottom. This is also true in (a), (b), and (c), with(a) actually having 5 red events. But only 4 are needed for strongly seeing, because
this example has n = 5 members, and the least integer greater than 2n/3 is 4.
This concept allows an agreement protocol to achieve Byzantine fault tolerance
without any actual voting, just through local virtual voting.
In virtual voting, when event x votes on some YES/NO question (e.g., whether
some other event is famous), the vote is calculated purely as a function of theancestors of x. That vote is only considered to be sent from x to its descendant
event w if w can strongly see x. It is proved in section 5 that if x and y are on
different branches of an illegal fork, then w can strongly see at most one of x andy, but not both. Furthermore, if hashgraphs A and B are consistent, then it is notTHE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

(a)!

(b)!

(c)!

9

(d)!

Figure 3. Illustration of strongly seeing. In each hashgraph, theyellow event at the top can strongly see one of the orange eventson the bottom row. There are n = 5 members, so the least integer
greater than 2n/3 is 4. In (d), one event (orange) is an ancestorof each of 4 intermediate events by different creators (red), eachof which is an ancestor of the yellow event. Therefore, the yellow
event can strongly see the orange event. Each of the other hashgraphs is colored to show the same for a different orange event on
the bottom row, which the yellow event see through at least 4 red
events. If all 4 orange events and both parents of the yellow event
have a created round of r, then yellow is created in round r + 1,
because it can strongly see more than 2n/3 witnesses created bydifferent members in round r. Note that every event is defined to
be both an ancestor and a self-ancestor of itself.
possible for one event to strongly see x in A and another event strongly see y in
B. That lemma is the cornerstone of the Byzantine proof. It ensures that even
if an attacker tries to cheat by forking, they will still be unable to cause different
members to decide on different orders. Historically, some Byzantine agreement
algorithms have required members to send out “receipts” to everyone for each votethey receive, to defend against Alice sending inconsistent votes to Bob and Carol.
There are some similarities between that attack and a hashgraph forking attack,and between the use of receipts and the use of strongly seeing.
Given those definitions, the complete hashgraph consensus protocol can be givenby the algorithms in Figures 4, 5, 6, and 7.
The main algorithm in Figure 4 shows that the communication is very simple:
Alice randomly picks another member Bob, and gossips to him all the events thatshe knows. Bob then creates a new event to record the fact of that gossip.
That simple gossip protocol is sufficient for Byzantine Fault Tolerance and correctness. But it can be extended in various ways to improve efficiency.For example,
Alice and Bob might tell each other which events they already know, then Alicesends Bob all the events that she knows that he doesn’t. The protocol might require that Alice send those events in topological order, so Bob will always have an
event’s parents before receiving the event. The protocol might even say that after
Alice syncs to Bob, then Bob will immediately sync back to Alice. Multiple syncs
can happen at once, so Alice might be syncing to several members at the same timeseveral members are syncing to her. These and other optimizations can all be used,
but this simple one is sufficient.
After each sync, the member calls the three procedures to determine the consensus order for as many events as possible. These involve no communication; purely

10

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

local computations are sufficient. In these procedures, each f or loop visits eventsin topological order, where an event is always visited after its parents. In the firstf or loop of the algorithm, if x is the first event in all of history, then it won’t haveparents or previous rounds, so it should be set to x.round=1 and x.witness=TRUE.
The algorithm also uses a constant n, which is the number of members in the entire
population (n > 1), and c ,which is a small integer constant greater than 2, suchas c = 10. In the following algorithm, Byzantine agreement is guaranteed withprobability one.
It is useful to define a round number for each event as a function of its ancestors.
In divideRounds (Figure 5), every known event is assigned an integer round number(definition 5.2) as a function of the round numbers of its ancestors. The hashgraphs
in Figure 3 show how this is done. If all the events on the bottom row were roundr, then all the rest of the events in those figures would also be round r, except for
the yellow event, which would be round r + 1. The yellow event is advanced to thenext round, r + 1, because it is able to strongly see more than 2n/3 events fromround r. The first event in history is defined to be round 1, so all future rounds
are determined by this. Every event will eventually have both a round created anda round received number. The round created is also called the round or roundnumber.
For any given member, the first event they create in each round is called awitness. It is only the witness events that send and receive the virtual votes. Thisoccurs in the decideFame procedure shown in Figure 6. This procedure is where
the Byzantine agreement occurs. For each witness, it decides whether it is famous.
A witness is famous if many of the witnesses in the next round can see it, and it is
not famous if many can’t. The Byzantine agreement protocol runs an election foreach witness, to determine if it is famous. For a witness x in round r, each witness
in round r + 1 will vote that x is famous if it can see it. If more than 2n/3 agree on
whether it is famous, then the community has decided, and the election is over. If
the vote is more balanced, then it continues for as many rounds as necessary, witheach witness in a normal round voting according to the majority of the witnesses
that it can strongly see in the previous round. To defend against attackers who
can control the internet, there are periodic coin rounds where witnesses can votepseudorandomly. This means that even if an attacker can control all the messages
going over the internet to keep the votes carefully split, there is still a chancethat the community will randomly cross the 2n/3 threshold. And so agreement is
eventually reached, with probability one.
In Figure 6, the algorithm would continue to work if the line “if d=1” werechanged to “if d=2”. In that revised algorithm, each election would start one round
later. It would even continue to work if the two were combined in the following
hybrid algorithm. In each round, first run all its elections with the “d=1” check.
If the fame of every witness in that round is decided, and 2n/3 or fewer members
created famous witnesses in that round, then the elections for just that round are
all re-run, using a d = 2 check. For this hybrid algorithm, all of the theorems in thispaper would continue to be true, including the proof of Byzantine Fault Tolerance.
For rounds that trigger the new elections, the time to consensus would increaseslightly (by perhaps 20%). But that would happen very rarely in practice, andwhen it did, it might increase the number of famous witnesses, to ensure fairness.

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

11

Once consensus has been reached on whether each witness in a given round isfamous, it is then easy to use that to determine a consensus timestamp and aconsensus total order on older events. This is done by procedure findOrder, foundin Figure 7.
First, the received round is calculated. Event x has a received round of r if thatis the first round in which all the unique famous witnesses were descendants of it,
and the fame of every witness is decided for rounds less than or equal to r. (Theset of unique famous witnesses in a round is defined to be the same as the set of
famous witnesses, except that all famous witness from a given member are removed
if that member had more than one famous witness in that round).
Then, the received time is calculated. Suppose event x has a received round ofr, and Alice created a unique famous witness y in round r. The algorithm finds z,
the earliest self-ancestors of y that had learned of x. Let t be the timestamp that
Alice put inside z when she created z. Then t can be considered the time at which
Alice claims to have first learned of x. The received time for x is the median of all
such timestamps, for all the creators of the unique famous witnesses in round r.
Then the consensus order is calculated. All events are sorted by their received
round. If two events have the same received round, then they are sorted by theirreceived time. If there are still ties, they are broken by simply sorting by signature,
after the signature is whitened by XORing with the signatures of all the uniquefamous witnesses in the received round.
5. Proof of Byzantine fault toleranceThis section provides a number of useful definitions, followed by several proofs,
building up from the Strongly Seeing Lemma (lemma 5.12) to the Byzantine Fault
Tolerance Theorem (theorem 5.19). In the proofs it is assumed that there aren members (n > 1), more than 2n/3 of which are honest, and less than n/3 ofwhich are not honest. It is also assumed that the digital signatures and cryptographic hashes are secure, so signatures cannot be forged, signed messages cannot
be changed without detection, and hash collisions can never be found. The syncing
gossip protocol is assumed to ensure that when Alice sends Bob all the events she
knows, Bob accepts only those that have a valid signature and contain valid hashes
corresponding to events that he has. The system is totally asynchronous. It is
assumed that for any honest members Alice and Bob, Alice will eventually try tosync with Bob, and if Alice repeatedly tries to send Bob a message, she will eventually succeed. No other assumptions are made about network reliability or network
speed or timeout periods. Specifically, the attacker is allowed to completely control
the network, deleting and delaying messages arbitrarily, subject to the constraintthat a message between honest members that is sent repeatedly must eventually
have a copy of it get through.
Definition 5.1. An event x is defined to be an ancestor of event y if x is y, or aparent of y, or a parent of a parent of y, and so on. It is also a self-ancestor of y if
x is y, or a self-parent of y, or a self-parent of a self-parent of y and so on.
Definition 5.2. The round created number (or round) of an event x is defined to
be r + i, where r is the maximum round number of the parents of x (or 1 if it has
no parents), and i is defined to be 1 if x can strongly see more than 2n/3 witnesses
in round r (or 0 if it can’t).

12

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

run two loops in parallel:
loop
sync all known events to a random member
end looploop
receive a sync
create a new event
call divideRounds
call decideFame
call findOrderend loop
Figure 4. The Swirlds hashgraph consensus algorithm. Eachmember repeatedly calls other members chosen at random, andsyncs to them. In parallel with the outgoing syncs, each member
receives incoming syncs. When Alice syncs to Bob, she sends all
events that she knows that Bob doesn’t. Bob adds these eventsto the hashgraph, accepting only events with valid signatures containing valid hashes of parent events he has. All known events
are then divided into rounds. Then the first events by each member in each round (the “witnesses”) are decided as being famousor not, through purely local Byzantine agreement with virtual voting. Then the total order is found on those events for which enoughinformation is available. If two members independently assign aposition in history to an event, they are guaranteed to assign thesame position, and guaranteed to never change it, even as more information comes in. Furthermore, each event is eventually assigned
such a position, with probability one.
procedure divideRounds
for each event x
r ← max round of parents of x ( or 1 if none exist )if x can strongly see more than 2n/3 round r witnesses
x . round ← r + 1
else
x . round ← r
x . witness ← ( x has no self parent )or ( x . round > x . selfParent . round )Figure 5. The divideRounds procedure. As soon as an event x
is known, it is assigned a round number x.round, and the boolean
value x.witness is calculated, indicating whether it is a “witness”,
the first event that a member created in that round.

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

13

procedure decideFame
for each event x in order from earlier rounds to laterx . famous ← UNDECIDED
for each event y in order from earlier rounds to later
if x . witness and y . witness and y . round>x . roundd ← y . round - x . rounds ← the set of witness events in roundy . round -1 that y can strongly seev ← majority vote in s ( is TRUE for a tie )t ← number of events in s with a vote of v
if d = 1// first round of the election
y . vote ← can y see x ?
else
if d mod c > 0// this is a normal round
if t > 2* n /3// if supermajority, then decide
x . famous ← v
y . vote ← v
break out of the y loopelse// else, just votey . vote ← v
else// this is a coin round
if t > 2* n /3// if supermajority, then votey . vote ← v
else// else flip a coiny . vote ← middle bit of y . signature
Figure 6. The decideFame procedure. For each witness event(i.e., an event x where x.witness is true), decide whether it is famous (i.e., assign a boolean to x.famous). This decision is done
by a Byzantine agreement protocol based on virtual voting. Eachmember runs it locally, on their own copy of the hashgraph, withno additional communication. It treats the events in the hashgraphas if they were sending votes to each other, though the calculation
is purely local to a member’s computer. The member assigns votes
to the witnesses of each round, for several rounds, until more than
2/3 of the population agrees. To find the fame of x, re-run thisrepeatedly on the growing hashgraph until x.famous receives avalue.

Definition 5.3. The round received number (or round received) of an event x isdefined to be the first round where all unique famous witnesses are descendants ofx.

14

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

procedure findOrderfor each event x
if there is a round r such that there is no event y
in or before round r that has y . witness = TRUE
and y . famous = UNDECIDED
and x is an ancestor of every round r unique famous
witnessand this is not true of any round earlier than r
thenx . roundReceived ← rs ← set of each event z such that z isa self - ancestor of a round r unique famous
witness , and x is an ancestor of z but notof the self - parent of z
x . co ns en su sT im es ta mp ← median of thetimestamps of all the events in s
return all events that have roundReceived not UNDECIDED ,sorted by roundReceived , then ties sorted byconsensusTimestamp , then by whitened signature
Figure 7. The findOrder procedure. Once all the witnesses inround r have their fame decided, find the set of famous witnesses
in that round, then remove from that set any famous witness thathas the same creator as any other in that set. The remaining
famous witnesses are the unique famous witnesses. They act as
the judges to assign earlier events a round received and consensus timestamp. An event is said to be “received” in the first roundwhere all the unique famous witnesses have received it, if all earlier
rounds have the fame of all witnesses decided. Its timestamp is themedian of the timestamps of those events where each of those members first received it. Once these have been calculated, the events
are sorted by round received. Any ties are subsorted by consensus
timestamp. Any remaining ties are subsorted by whitened signature. The whitened signature is the signature XORed with thesignatures of all unique famous witnesses in the received round.

Definition 5.4. The pair of events (x, y) is a fork if x and y have the same creator,
but neither is a self-ancestor of the other.
Definition 5.5. An honest member tries to sync infinitely often with every othermember, creates a valid event after each sync (with hashes of the latest self-parent
and other-parent), and never creates two events that are forks with each other.

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

15

Definition 5.6. An event x can see event y if y is an ancestor of x, and theancestors of x do not include a fork by the creator of y.
Definition 5.7. An event x can strongly see event y if x can see y and there is a
set S of events by more than 2/3 of the members such that x can see every event
in S, and every event in S can see y.
Definition 5.8. A witness is the first event created by a member in a round.
Definition 5.9. A famous witness is a witness that has been decided to be famousby the community, using the algorithms described here. Informally, the community
tends to decide that a witness is famous if many members see it by the start of
the next round. A unique famous witness is a famous witness that does not havethe same creator as any other famous witness created in the same round. In theabsence of forking, each famous witness is also a unique famous witness.
Definition 5.10. Hashgraphs A and B are consistent iff for any event x containedin both hashgraphs, both contain the same set of ancestors for x, with the same
parent and self-parent edges between those ancestors.
Lemma 5.11. All members have consistent hashgraphs.
Proof: If two members have hashgraphs containing event x, then they have the sametwo hashes contained within x. A member will not accept an event during a sync
unless that member already has both parents for that event, so both hashgraphs
must contain both parents for x. The cryptographic hashes are assumed to be
secure, therefore the parents must be the same. By induction, all ancestors of x
must be the same. Therefore the two hashgraphs are consistent.
The purpose of the concept of strongly seeing is to make the following lemma true.
This lemma is the foundation of the entire proof, because it allows for consistentvoting, and for guarantees that different members will never calculate inconsistent
results, even with purely virtual voting.
Lemma 5.12 (Strongly Seeing Lemma). If the pair of events (x, y) is a fork, andx is strongly seen by event z in hashgraph A, then y will not be strongly seen byany event in any hashgraph B that is consistent with A.
Proof: The proof is by contradiction. Suppose event w in B can strongly see y.
By the definition of strongly seeing, there must exist a set SA of events in A thatz can see, and that all can see x. There must be a set SB of events in B that w
can see, and which all see y. Then SA must contain events created by more than
2n/3 members, and so must SB , therefore there must be an overlap of more thann/3 members who created events in both sets. It is assumed that less than n/3
members are not honest, so there must be at least one honest member who created
events in both SA and SB . Let m be such a member, and their events qA ∈ SA
and qB ∈ SB . Because m is honest, qA and qB cannot be forks with each other,so one must be the self-ancestor of the other. Without loss of generality, let qA be
the self-ancestor of qB . The hashgraphs A and B are consistent, and qB is in B, so
its ancestor qA must also be in B. Then in B, x is an ancestor of qA , which is anancestor of qB , so x is an ancestor of qB . But y is also an ancestor of qB . So bothx and y are ancestors of qB and are forks of each other, so qB cannot see eitherof them. But that contradicts the assumption that qB can see y in B. That is acontradiction, so the lemma is proved.
16

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

At every moment, all members will have consistent hashgraphs. If two hashgraphs are consistent, and both contain an event x, then they will both contain thesame set of ancestors for x. This will cause them to agree on every property of xthat is purely a function of its ancestors. That includes its round created, whether
it is a witness, what events it can see, what events it can strongly see, and how
it will vote in each election (if it’s a witness). For most of these properties, thisfollows directly from the definition. The following lemma proves that it is also true
for the round created.
Lemma 5.13. If hashgraphs A and B are consistent and both contain event x,
then both will assign the same round created number to x.
Proof: If the consistent hashgraphs both contain x, then they both contain thesame set of all its ancestors, including the first event in history. Then the proof
is by induction: they agree on the round number of that first event, which is 1 bydefinition. And if they both contain an arbitrary state y, and agree on the roundnumbers of all its ancestors, then they will agree on the maximum round number
r of the parents of y, and will agree on whether y can strongly see more than 2n/3
witnesses created in round r by different members, and therefore will agree on theround number of y. Therefore they will agree on the round number of all events
they share, including x.
If a witness x in round r can strongly see a witness y in round r − 1, then for any
given election, we say that y sends a vote to x, and that x collects a vote from y.
This is purely virtual voting, which is calculated from the hashgraph itself. Different
members may have slightly different hashgraphs, and so may have slightly different
elections. However, all the votes will be consistent. If one hashgraph shows Alice
sending Bob a given vote in a given round for a given election, then any consistenthashgraph must show either the same vote, or no vote at all from Alice to Bob inthat round. It is impossible for two consistent hashgraphs to show two different
votes for Alice in that round. This is shown in the following lemma.
Lemma 5.14. If hashgraphs A and B are consistent, and the algorithm running
on A shows for a given election that a round r witness by member m0 sends a vote
vA to a witness created by member m1 in round r + 1, and the algorithm runningon B shows that a round r witness by member m0 sends a vote vB to a witness bymember m1 in round r + 1, then vA = vB .
Proof: The algorithm only sends a vote from event x to event y if y can strongly see
x. It is not possible for consistent hashgraphs to have two events that are forks ofeach other and that are both strongly seen, by the Strongly Seeing lemma (lemma5.12). Therefore, the two votes must be coming from the same event x in both
hashgraphs. An event’s vote is calculated purely as a function of its ancestors, so
the two hashgraphs must agree on the vote, and vA = vB .

Byzantine agreement on a particular YES/NO question is achieved by multiple
rounds of virtual voting. A given member will end their election calculations inround r if it is a normal round (not a coin round) and some round r + 1 eventstrongly sees more than 2n/3 of the members voting the same way in round r. If
that happens, then every active member will end their election in round r or r + 1(or r + 2 if r + 1 is a coin round), and will decide the same way. In other words,

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

17

the following lemma proves that if anyone decides on a YES/NO question, theneveryone achieves Byzantine consensus almost immediately thereafter.
Lemma 5.15. If hashgraphs A and B are consistent, and A decides a Byzantine
agreement election with result v in round r and B has not decided prior to r, thenB will decide v in round r + 2 or before.
Proof: Decisions can’t happen in coin rounds, so r must be a regular round. If A
decides a vote v, that means some witness in round r received votes of v from a setof members S that contains more than 2n/3 members. Because voting is consistent(by the previous lemma), all other round r events in A and B will receive votes
from more than 2n/3 members, a majority of whom will also be in S, because
two subsets of size greater than 2n/3 drawn from a set of size n must each havea majority of their elements in common with the other. Therefore, every round r
witness in both A and B will vote for v (and some may decide v). If round r + 1 isa regular round, then every event in A and B in that round will receive unanimous
votes of v and will decide v. If round r + 1 is a coin round, then all will receive
unanimous votes of v, so none will flip coins, and all will vote v, and then all will
decide v in round r + 2.

The following theorem shows that Byzantine fault tolerance is achieved for any
single YES/NO question.
Theorem 5.16. For any single YES/NO question, consensus is achieved eventually with probability 1.
Proof: If any member decides the question, then all members will decide the same
way within 2 rounds, by the last lemma. So the only way consensus could fail is if
no member ever decides, because no witness ever receives more than 2n/3 matching
votes. However, in a coin round, if such a supermajority has not yet been achieved,
then all the honest members randomly choose their vote, and will have a nonzero
probability of all choosing the same vote. Coin rounds occur periodically forever,so eventually the honest members will become unanimous, with probability one,and then consensus will be reached within 2 rounds.
In the hashgraph consensus algorithm, Byzantine agreement is used to decide
whether each witness in a given round is famous or not. Every round is guaranteed
to have at least one witness that is famous, by the following lemma.
Lemma 5.17. For any round number r, for any hashgraph that has at least one
event in round r +3, there will be at least one witness in round r that will be decided
to be famous by the consensus algorithm, and this decision will be made by every
witness in round r + 3, or earlier.
Proof: Let Sr+3 be a set containing a single witness in round r + 3, in a hashgraphthat has at least one such witness. For each i < r + 3, let Si be the set of all
witnesses in round i that are each strongly seen by at least one witness in Si+1 .
It must be the case that 2n/3 < |Si | ≤ n for all i ≤ r + 2, because the existenceof an event in round i + 1 guarantees more than 2n/3 are strongly seen in roundi, and none of the n members can create more than one witness in a given roundthat is strongly seen (by the Strongly Seeing lemma, lemma 5.12). Strongly seeing
implies seeing, so each event in Sr+1 sees more than two thirds of the events in
Sr . Therefore, on average, each event in Sr is seen by more than two thirds of

18

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

the events in Sr+1 . They can’t all be below average, so there must be at least one
event in Sr (call it x) that is seen by more than two thirds of the events in Sr+1 .
So more than two thirds of Sr+1 will vote YES in the election for x being famous.
Therefore, every event in Sr+2 will receive more YES votes than NO votes for thefame of x, and will therefore vote for x being famous (and may or may not decidethat x is famous). Therefore, the event in Sr+3 will receive unanimous votes forx being famous, which will cause it to decide that x is famous. Therefore, every
member with an event in round r + 3 will first decide that x is famous in either
round r + 2 or r + 3.
Lemma 5.18. If hashgraph A does not contain event x, but does contain all theparents of x, and hashgraph B is the result of adding x to A, and x is a witness
created in round r, and A has at least one witness in round r whose fame has been
decided (as either famous or as not famous), then x will be decided as “not famous”
in B.
Proof: Let w be a witness in A that decided the fame for one of the witnesses inround r. None of the ancestors of w can see x, because there is no x in A. So
they will also not see x in B, because they have the same ancestors in consistenthashgraphs. Therefore the ancestors of w that are witnesses in round r + 1 will all
vote NO on the fame of x in B. So an ancestor of w in r + 2 will decide that x is
not famous in B.

Given the last 3 lemmas/theorems, we know that every round will eventually
have all its witnesses classified as famous or not famous by universal consensus,
with at least one of the witnesses being famous. After that, the set of famous
witnesses for that round will never change, even if more events are added to thehashgraph. This set of famous witnesses can therefore act as a judge, to define a
total order on all the events that have reached them, and a consensus timestamp
on every event.
Theorem 5.19 (Byzantine Fault Tolerance Theorem). Each event x created by anhonest member will eventually be assigned a consensus position in the total orderof events, with probability 1.
Proof: All honest members will eventually learn of x, by the definition of honest
and the assumptions that the attackers who control the internet must eventually
allow any two honest members to communicate. Therefore, there will eventually
be a round where all the unique famous witnesses are descendants of x. Therefore
in that round, or possibly earlier, there will be a round r where all the famous
witnesses are descendants of x. Then x is assigned a received round of r, and aconsensus timestamp of the median of when those members first received it, andits consensus place in history will be fixed. Furthermore, it is not possible to later
discover a new event y that will come before x in the consensus order. Because, tocome earlier in the consensus history, y would have to have a received round lessthan or equal to r. That would mean that all the famous witnesses in round r musthave received y. But once the set of famous witnesses is known for a round, all of
their ancestors are also known, so there is no way to discover new ancestors for themin the future as the hashgraph grows. Furthermore, it isn’t possible for a roundto gain new famous witnesses in the future, once the famousness of all the known
witnesses in that round are known. Any new round r witness that is discovered inTHE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

19

the future will not be an ancestor of the known round r + 1 witnesses (of which
there are more than 2n/3), and so the consensus will immediately be reached that
it is not famous. Therefore, once an event is assigned a place in the total order, it
will never change its position, neither by swapping with another known event, nor
by new events being discovered later and being inserted before it.

6. Fairness
Most existing systems for distributed consensus can fail to be “fair” in theirconsensus ordering of transactions. To see this, first consider a stock market thatis run by a single server. Alice and Bob each submit a bid to that server, with
Alice submitting it just before Bob. If the server is fair, then it will count Alice’s
transaction as occurring before Bob’s. For some applications, the exact order does
not matter, but for a stock market it can be critically important that this decision
be made fairly.
Now consider a distributed peer-to-peer system, where there is no single server,
but there is a community that will reach consensus on whose transaction was first.
It may still be critically important that the consensus decision is fair. But whatshould be the definition of “fair”?
The “fair” decision on transaction order could be defined as favoring whichevertransaction was created first. But that would be bad. Alice might have created
her transaction one second before Bob, while she was in a cabin in the woods,
disconnected from the internet. Then the community would only hear of Bob’s
transaction, and would assume that Bob was first. A year later, when Alice finally
emerges from the woods and rejoins the internet, the community would have torevise history in order to be “fair”. That would cause a host of problems. So thatwouldn’t be an ideal definition of fairness. There needs to be a requirement thatthe transaction actually be sent to the community, in order to count as being first.
The “fair” decision could be defined as reflecting the order in which the transactions reached the current leader. But that would also be bad. The leader might
be a member chosen by the Paxos algorithm. Or it might be whichever member
currently has a turn in a round-robin system. In a proof-of-work system, it would
be whichever miner manages to solve a puzzle first. In any case, the leader could
arbitrarily decide to ignore either Alice’s or Bob’s transaction for a period of time,delaying one of them, to force their transaction to come after the other. If the goalis distributed trust, then no single individual can be trusted.
The “fair” decision could be defined as reflecting when each transaction firstreached a certain fraction of the entire community. This is a little better. The
community is then ordering transactions by when the transactions first reached avirtual server, where “reaching the server” means reaching some fraction of thecommunity as a whole. However, there are still issues. If the fair choice is defined
as whichever transaction reached at least half of the community first, then there
will be problems if Carol saw Alice first, Dave saw Bob first, and everyone else isevenly split on the question. This fails if Carol and Dave are both attackers whoturn off their computers permanently before telling the community what they saw.
In that case, the community could never reach a fair consensus, because they would
be waiting forever on Carol and Dave to vote.
A better definition might be to say it is “fair” to consider Alice as being first if asignificant fraction of the community received Alice’s transaction before Bob’s, and20

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

that fraction of the community then went on to communicate with most of the others
quickly. Under this definition, if Alice and Bob are releasing their transactions to
the gossip network at almost the same time, and both spread at about the samerate, then the consensus could go either way, and still be considered fair. However,
if Alice gossips her transaction before Bob, beating him by just over the durationof a single gossip sync, then it might be expected that as both transactions spread
exponentially, doubling the number of members reached on each sync, in the end
over 2/3 of the population will hear of Alice before Bob, and less than 1/3 will favor
Bob. So in that case, it would be fair to favor Alice over Bob in the consensus. The
hashgraph consensus algorithm is fair in this sense. The members who are online
and regularly participating will generate a set of events called famous witnesses, andthe consensus decision will be that the “first” transaction is whichever transaction
reached the majority of that set first. If a small set of members are offline, or
are partitioned so that they cannot communicate with the rest, then they will nothave famous witnesses, and so having a transaction reach them will not count as
having reached the community as a whole. But if the members in that set arecommunicating with the rest, then they will count as famous witnesses, and they
will help decide who reached “the community” first.
There are attacks against this system that would be not be considered to bea failure of the consensus system, because they would be equally effective against
a single-server solution. For example, the Byzantine proofs assume the attackers
control the internet, and can delay arbitrary messages. If attackers actually hadthat power, they could simply disconnect Alice from the internet for as long as it
takes for Bob to send a transaction and have it recorded. This could be done on thereal internet by launching a denial of service attack, flooding every computer withpackets from Bob in an attempt to prevent Alice from communicating. Of course,
this would also be effective if Alice were communicating with a central server, so it
could be considered more a failure of the internet than a failure of the consensus
system.
Similarly, Bob could gain an advantage over Alice by buying more bandwidth, sothat his gossips reach more people, faster. If he has 8 times the bandwidth of Alice,so that he can send his transaction initially to 8 members in the time Alice sends
to 1, then he can gain an advantage of the time of about 3 gossip syncs. This is notconsidered a failure. If his message actually reaches the world before hers, then heshould have the credit for it. This is similar to the current stock markets, wherecompanies spend large sums of money for slightly faster connections, in order toreach the central server faster. So the consensus algorithm would not be considered“unfair” in this case, because it is behaving the same as a central server.
7. Generalizations and enhancements
7.1. proof-of-stake. So far, it has been assumed that every member is equal. The
above algorithms refer to things depending on “more than 2n/3 of the members”
and “at least half of the famous witness events”. They also use the idea of a“median” of a set of numbers. The proof shows Byzantine convergence when morethan 2n/3 of the members are honest.
It is easy to modify the algorithm to allow members to be unequal. Each member
can be assumed to have some positive integer associated with them, known as their“stake”. Then, the votes would be replaced with weighted voting, and the medians

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

21

with weighted medians, where votes are weighted proportional to the voter’s stake.
In all of the above definitions, algorithms, and proofs, define “more than 2n/3
members” to mean “a set of members whose total stake is more than 2n/3, where
n is the total stake of all members”. The “median of the timestamps of events in
S” would become “the weighted median of the timestamps in S, weighted by the
stake of the creator of each event in S”. The weighted median can be thought of as
taking each event y in S, and putting multiple copies of the timestamp of y into
a bag, where the number of copies equals the stake of the member who created y.
Then take the median of the timestamps in the bag.
The Byzantine proof applied as long as the attackers constituted less than 1/3of the population. With these new definitions, it will now apply when the attackers
together have a stake that is less than 1/3 of the total stake of all members.
This new proof-of-stake system is more general than the unweighted system.
It can still be used to implement the unweighted system, by simply giving every
member a stake of 1. But it can also be used to provide better behavior. For
example, the stake might be proportional to the degree to which a member istrusted. Perhaps members who have been investigated in some way should betrusted more than others. Or it could be used to give greater weight to members who
have a greater interest in the system as a whole working properly. A cryptocurrency
might use each member’s number of coins as their stake, on the grounds that thosewith more coins have a greater interest in ensuring the system runs smoothly. Or
a community could be started by a group of members with mutual trust, each ofwhich is given an equal stake. Then, each existing member could be allowed to invite
arbitrarily many new members to join, subject to the constraint that the inviter
must split their stake with the invitee. This would discourage a Sybil attack, where
one member invites a huge number of sock puppet accounts, in order to control thevoting.
The “stake record” is the list of members and the amount of stake owned by eachmember. So far, it has been assumed that the stake record is universally known,
and is unchanging. It is easy to relax that assumption.
Assume that there is a particular form of transaction that changes the stakerecord. The community might set up rules at the beginning, governing which suchtransactions are valid. For example, each member could be allowed to invite othermembers, up to a total of at most 10 new members. Or perhaps anyone invitinga new member must simultaneously give the new member a portion of their own
stake. The validity of such a transaction might depend on the exact order of thetransactions in the consensus order. For example, if the rule is that only one newmember can be invited, and Alice invites Carol at the same time Bob invites Dave,then then whichever invitation comes first in the consensus order will succeed, andthe other will fail.
All of this can be accommodated. When the consensus algorithm finishes deciding the question of which round r firsts are famous, at that moment it becomes
possible to find exactly which events will have a received round of r, and to calculate
their exact position in the consensus order. At that time, each of the transactionsin those events can be processed, and the rules can be consulted to see which arevalid, and the valid transactions can be applied. This may change the stake record.
If the stake record does change, then the algorithm should be re-run for all
events in round r and later. This may change the calculations of which events are

22

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

strongly seen, of event round numbers, of which events are witnesses, and of which
are famous witnesses.
Note that when deciding which round r witnesses are famous, the calculations
are done using the old stake record. The voting for round r may continue several
rounds into the future, all using the old stake record. Once round r is settled, thefuture rounds will reshuffle, and the calculations for round r + 1 famous witnesses
will be done using the new stake record.
This approach allows all members to be in agreement on exactly what stakerecord is being used for any given calculation. That ensures that they will always
agree on the results of those calculations. And Byzantine agreement will still be
guaranteed with probability one.
7.2. signed state. Another enhancement to the system is to have signed states.
Once consensus has been reached on whether each witness in round r is famousor not, a total order can be calculated for every event in history with a received
round of r or less. It is also guaranteed that all other events (including any thatare still unknown) will have a received round greater than r. In other words,
at this point, history is frozen and immutable for all events up to round r. A
member can therefore take all the transactions from those events, and feed theminto a database in the consensus order, and calculate the state that is reached after
processing those transactions. Every member will calculate the same consensus
order, so every member will calculate the same state. This is a consensus state.
Each member can take the hash of this state and digitally sign it, and put thesignature into a new transaction. Soon after, every member will have received bygossip many signatures for the consensus state. Once signatures are collected fromat least 1/3 of the population, that consensus state, along with the set of signatures,constitutes a signed state that is an official consensus state for the system at thestart of round r. It can be given to people outside the community, and they cancheck the signatures, and therefore trust the state. At this point, a member canfeel free to delete all the transactions that were used to create the state, and delete
all the events that contained those transactions. Only the state itself needs to be
kept. It might be possible to do this every few minutes, so there will never be ahuge number of transactions and events stored. Only the consensus state itself. Of
course, a member is free to preserve the old events, transactions, and states, perhaps
for archive or audit purposes. But the system is still immutable and secure, evenif everyone discards that old information.
Given the assumption that less than 1/3 of the population is dishonest, the signed
state is guaranteed to have at least one honest signature, and so can be trusted torepresent the community consensus, as found by the consensus algorithm. If theset of members (or their stake) can change over time, then that stake record (andits history) will also be part of the state. The threshold of 1/3 could be replacedwith something else, such as more than 2/3, and the system would still work.
7.3. Efficient gossip. The gossip protocol makes very efficient use of bandwidth.
Suppose there are enough transactions being created that every event contains
at least one transaction. In any replicated state machine, using a point-to-point
network such as the internet, it will be necessary for each member to receive eachsigned transaction once, and to also send each signed transaction on average once.
For the hashgraph gossip, the same is true, except that the signature is for theTHE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

23

event containing the transaction, rather than for the transaction itself. The only
additional overhead is the two hashes and the timestamp, plus the array of counts
at the start of the sync. However, the hashes themselves don’t have to be sent overthe internet. It is sufficient to merely send the identity of the creator of the event,and the sequence number of its other-parent.
For example, suppose the 100th event created by Alice has an other-parent thatis Ed’s 50th event. If this event by Alice is sent from Bob to Carol during a sync,
Bob could skip sending Carol the two hashes in the event. Instead, he could tell
Carol that this is an event by Alice, and that the other-parent is Ed’s 50th event.
Since Bob is only sending Carol events she doesn’t have according to their initialcounts, Carol will know that this must be Alice’s 100th event, since the last one
she knows about by Alice is Alice’s 99th event. So Bob doesn’t have to send thehash of that self-parent, and doesn’t have to send the sequence number 100. He
just has to send the fact that it is by Alice. Similarly, he must send that the otherparent is by Ed, and that it is Ed’s 50th event. So instead of two, large hashes,
Bob is simply sending the triplet (Alice, Ed, 50). With some care, the identities
and sequence numbers can be compressed to a byte or two each, so the triplet will
required only 3 to 6 bytes. This is small overhead compared to the signature (which
is 64 bytes for a 512-bit signature) and the transactions within the event (perhaps
averaging 100 bytes or more). So if each event contains at least one transaction,then there is almost no overhead for gossiping a hashgraph, beyond simply gossiping
the transactions themselves.
And because voting is virtual, there is no other bandwidth cost at all in order toachieve consensus. In this sense, the bandwidth required for hashgraph consensus isvery close to the theoretical limit, which would be the bandwidth needed to simply
send the signed and dated transactions themselves.
A system that merely sent the transactions could save bandwidth by not attaching timestamps to the transactions, if the application didn’t need timestamps.
Hashgraph consensus can do the same. In that case, the “timestamp” within an
event would simply be an integer that is its self-parent’s “timestamp” plus one.
When Bob sends an event to Carol, that sequence number can be calculated by
Carol, so there is no need for Bob to actually send it over the internet.
A system that only sent transactions could also save bandwidth by grouping
together several transactions by the same creator, and attaching only a single signature to the list, rather than one per transaction. Hashgraph can do the same,by putting several transactions into a single event, and so having only a single
signature for the list.
So the bandwidth requirements of hashgraph consensus are very close to thetheoretical minimum in all cases.
7.4. Fast elections. That second part of the algorithm is a Byzantine agreement
step for deciding fame. It has an interesting property. When a group of members are
all online and all participating regularly, the Byzantine agreement will be applied
to a set of elections where almost all the voters start with identical votes. That is
because a round r + 1 witness will strongly see many of the round r witnesses, so around might be expected to last about two “gossip periods”, where a gossip period
is the time it takes for a message to propagate through the entire community. Thisshould be the time to do log2 (n) syncs, when there are n members online. For around r + 1 witness x to vote YES on the fame of a round r witness y, it isn’t

24

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

necessary for x to strongly see y. It can merely see y. It would be expected thaty would propagate to all the online members in a single gossip period. So there
is an overwhelmingly high probability it will propagate to them within two gossip
periods. So in practice, when everyone is online and participating, the fame of
witnesses is almost always decided immediately, without the need for many roundsof voting.
Similarly, if y is a round r witness, but was created by a member who was asleep
and then awoke just before the end of round r , then it is likely that almost all
round r+1 witnesses will vote NO on y, and the election will again end immediately.
There is a small window of time, on the order of the duration of a single sync, inwhich a member awakening and creating y can cause the round r + 1 witnesses
to start with a close to even vote split. If the online members are all choosing
each other randomly and syncing frequently, then such a result will converge to adecision in about 3 rounds, with a probability of only a few percent for more than 3
rounds, and of less than a tenth of a percent for more than 6 rounds. If an attacker
completely controls the internet, they can cause this to drag on for exponentiallymany rounds. This can be reduced to a constant expected number of rounds byusing a cryptographic “shared coin” protocol, rather than the “middle bit of thesignature” described in the above algorithm. The middle bit is intended to be likeeach member having an independent random coin flip that the attacker couldn’t
predict ahead of time. A shared coin protocol is the same, but ensures all members
end up with the same “random” result. This addition would reduce the theoreticalworst-case expected time. But such an addition seems unlikely to be worth theeffort in practice. If an attacker can truly control the internet enough to keep thehonest members from synching randomly with each other for a long period, thenthe attacker likely has the power to simply block the honest users from accessing
the internet at all. So a shared coin seems to be of only theoretical interest here.
But using a shared coin is always an option.
7.5. Efficient calculations. The first part step of the algorithm is to assign around of either r or r + 1 to an event, based on whether it can strongly see enoughround r events. So it is necessary to calculate whether a round r witness event x
can be strongly seen by an arbitrary event y. The following is one way to calculatethat answer.
Give each event a sequence number that is one greater than the sequence numberof its self-parent. Store an array for y and an array for x. The y array remembers
the sequence number of the last event by each member that is an ancestor of y. The
array for x remembers the sequence number of the earliest event by each memberthat is a descendant of x. Compare the two arrays, and find how many elements inthe y array are greater than or equal to the corresponding element of the x array. If
there are more than 2n/3 such matches, then y strongly sees x. The comparison of
the x and y arrays can be sped up by multithreading (to use more cores), packing
multiple elements into one integer (to use the ALU more efficiently), using assembly
language (to access the CPU vector instructions) or using the GPU (for more vector
parallelism).
8. Conclusions
A new system has been presented, based on the Swirlds hashgraph data structure, and the Swirlds hashgraph consensus algorithm. It is fair, fast, Byzantine

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

25

fault tolerant, and extremely bandwidth efficient due to virtual voting. The algorithm is given in pseudocode in the figures, using an imperative language, but it
is also very natural to describe it in a functional form. The appendix gives thealgorithm in a functional form, which is concise, and may be of interest.
References[1] Miguel Castro and Barbara Liskov. Practical byzantine fault tolerance. In Proceedings of
the Third Symposium on Operating Systems Design and Implementation, OSDI ’99, pages
173–186, Berkeley, CA, USA, 1999. USENIX Association.
[2] Leslie Lamport, Robert Shostak, and Marshall Pease. The byzantine generals problem. ACM
Trans. Program. Lang. Syst., 4(3):382–401, July 1982.
[3] Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. Impossibility of distributed
consensus with one faulty process. J. ACM, 32(2):374–382, April 1985.
[4] Leslie Lamport. The part-time parliament. ACM Trans. Comput. Syst., 16(2):133–169, May
1998.
[5] Diego Ongaro and John Ousterhout. In search of an understandable consensus algorithm. In
2014 USENIX Annual Technical Conference (USENIX ATC 14), pages 305–319, Philadelphia, PA, June 2014. USENIX Association.
[6] Andrew Miller, Yu Xia, Kyle Croman, Elaine Shi, and Dawn Song. The honey badger of bft
protocols. Cryptology ePrint Archive, Report 2016/199, 2016. http://eprint.iacr.org/.
[7] Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin, and Mirco Marchetti. Making
byzantine fault tolerant systems tolerate byzantine faults. In Proceedings of the 6th USENIX
Symposium on Networked Systems Design and Implementation, NSDI’09, pages 153–168,
Berkeley, CA, USA, 2009. USENIX Association.
[8] Satoshi Nakamoto. Bitcoin: A peer-to-peer electronic cash system. posted to the internet
November, 2008, 2008. http://bitcoin.org/bitcoin.pdf.
[9] Giulio Prisco. Intel develops ‘Sawtooth Lake’ distributed ledger technology for the Hyperledger project. Bitcoin Magazine, April 2016.
[10] Dag-Erling Smorgrav. FreeBSD quarterly status report. Posted on FreeBSD.org, 2013. http://www.freebsd.org/news/status/report-2013-09-devsummit.html#Security.
[11] Miguel Miguel Correia, Giuliana Santos Veronese, Nuno Ferreira Neves, and Paulo Verissimo. Byzantine consensus in asynchronous message-passing systems: a survey. International
Journal of Critical Computer-Based Systems, 2(2):141–161, 2011.

26

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

9. Appendix A: Consensus algorithm in functional form
An event is a tuple e = {p, h, t, i, s} where:
p
h
t
i
s

= payload(e)= hashes(e)= time(e)= creator(e)= sig(e)parents(x) =selfParent(x) =
n =
c =
d =
E =
E0 =
T =
B =
N =
parents
selfParent
ancestor
selfAncestor
manyCreatorsseestronglySee
selfParentRoundroundwitness
diff
votes
fractTrue
decidecopyVotevotefamousuniqueFamousroundsDecided
roundReceived
timeReceived= the “payload” data, such as a list of transactions= a list of hashes of the event’s parents, self-parent first= creator’s claimed date and time of the event’s creation= creator’s ID number= creator’s digital signature of {p, h, t, i}
set of events that are parents of event x
the self-parent of event x, or ∅ if none
the number of members in the population
frequency of coin rounds (such as c = 10)
rounds delayed before start of election (such as d = 1)
the set of all events in the hashgraphE ∪ {∅}
set of all possible (time, date) pairs{true, f alse}{1, 2, 3, ...}
: E → 2E
: E → E0
: E×E →B
: E×E →B
: 2E → B: E×E →B
: E×E →B
: E→N
: E→N
: E→B
: E×E →I
: E×E×B→N: E×E →R
: E×E →B
: E×E →B
: E×E →B
: E→B
: E→B
: N→B
: E→N
: E→T

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

27

ancestor(x, y) = true if x can reach y by following 0 or more parent edges
selfAncestor(x, y) = true if x can reach y by following 0 or more selfParent edges
manyCreators(S) = true if the set of events S has more than 2n/3 events,
and all have distinct creators?
see(x, y) = true if y is an ancestor of x, but no fork of y is anancestor of x
stronglySee(x, y) = true if x can see events by more than 2n/3 creators, each ofwhich sees yselfParentRound(x) = the maximum created round of all parents of x (or 1 if
there are none)round(x) = the created round of x
witness(x) = true if x has a greater created round than its selfParentdiff(x, y) = round(x) - round(y)votes(x, y, v) = the number of votes equal to v about the fame of
witness y collected by witness x from witnesses in theprevious roundfractTrue(x, y) = fraction of votes equal to true, regarding the fame of
witness y, collected by witness x, from witnesses in
the previous round
decide(x, y) = true if x (or its self ancestor) "decided" for the election
for witness y (and therefore that member will never change
its vote about y again)
copyVote(x, y) = true if x should simply copy its selfParent’s vote about thefame of witness y (or x is not a witness, or has already
decided earlier)vote(x, y) = the vote by witness x about the fame of witness y (true forfamous, false for not)famous(x) = true if x is famous (i.e., has had its fame decided by someone,
and their vote was true)
uniqueFamous(x) = true if x is famous and is the only famous witness in that roundby that creatorroundsDecided(r) = true if all known witnesses had their fame decided, for bothround r and all earlier rounds
roundReceived(x) = the round received for event x
timeReceived(x) = the consensus timestamp for event x

28

THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM - SWIRLDS-TR-2016-01

ancestor(x, y)= x = y ∨ ∃z ∈parents(x), ancestor(z, y)selfAncestor(x, y)= x = y ∨ (selfParent(x) 6= ∅ ∧ selfAncestor(selfParent(x), y))

manyCreators(S)= |S| > 2n/3 ∧ ∀x, y ∈ S, (x 6= y =⇒ creator(x) 6= creator(y))

see(x, y)=ancestor(x, y) ∧ ¬(∃a, b ∈ E, creator(y) = creator(a) = creator(b)∧ancestor(x, a) ∧ ancestor(x, b) ∧ ¬ selfAncestor(a, b) ∧ ¬ selfAncestor(b, a))stronglySee(x, y)=see(x, y) ∧ (∃S ⊆ E, manyCreators(S)∧(z ∈ S =⇒ (see(x, z) ∧ see(z, y))))(selfParentRound(x) =1round(selfParent(x))

if selfParent(x) = ∅otherwiseround(x)= max({selfParentRound(x)} ∪ {r + 1 | ∃S ⊆ E, manyCreators(S)∧(∀y ∈ S, round(y) = r ∧ stronglySee(x, y))})witness(x)=diff(x, y)= round(x) − round(y)votes(x, y, v)= |{z ∈ E | diff(x, z) = 1 ∧ witness(z)∧ stronglySee(x, z) ∧ vote(z, y) = v}|

fractTrue(x, y)=decide(x, y)= (selfParent(x) 6= ∅ ∧ decide(selfParent(x), y)) ∨(witness(x) ∧ witness(y)∧ diff(x, y) > d ∧ (diff(x, y) mod c > 0) ∧ (∃v ∈ B, votes(x, y, v) > 2n3 )))copyVote(x, y)= (¬ witness(x)) ∨ (selfParent(x) 6= ∅ ∧ decide(selfParent(x), y)vote(x, y)vote(selfParent(x), y)





see(x, y)1 = middleBit(signature(x))
=









fractTrue(x, y) ≥ 21

famous(x)= ∃y ∈ E, decide(y, x) ∧ vote(y, x)

uniqueFamous(x)= famous(x) ∧ ¬∃y ∈ E, y 6= x ∧ famous(y)∧ round(x) = round(y) ∧ creator(x) = creator(y)roundsDecided(r)= ∀x ∈ E, ((round(x) ≤ r ∧ witness(x)) =⇒ ∃y ∈ E, decide(y, x))roundReceived(x)=timeReceived(x)= median({time(y) | y ∈ E ∧ ancestor(y, x)∧(∃z ∈ E, round(z) = roundReceived(x) ∧ uniqueFamous(z)∧ selfAncestor(z, y}) ∧ ¬(∃w ∈ E, selfAncestor(y, w) ∧ ancestor(w, x))})(selfParent(x) = ∅) ∨ (round(x) > round(selfParent(x))

votes(x,y,true)max(1,votes(x,y,true)+votes(x,y,f alse))

if copyVote(x, y)
if ¬ copyVote(x, y) ∧ diff(x, y) = d
if ¬ copyVote(x, y) ∧ diff(x, y) 6= d
∧ (diff(x, y) mod c = 0)
∧ ( 31 ≤ fractTrue(x, y) ≤ 23 )otherwisemin({r ∈ N | roundsDecided(r) ∧ (∀y ∈ E,
(round(y) = r ∧ uniqueFamous(y)) =⇒ ancestor(y, x))})