THE SWIRLDS HASHGRAPH CONSENSUS ALGORITHM: FAIR, FAST, BYZANTINE FAULT TOLERANCE
đź“ś 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-of-work, eventual consensus with probability one, and high speed in the absence of 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 a hashgraph reflecting all of the gossip events. This allows Byzantine agreement to be achieved through virtual voting. Alice does not send Bob a vote over the Internet. Instead, Bob calculates what vote Alice would have sent, based on 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.
✨ Summary
Summary
The paper proposes the Swirlds hashgraph consensus algorithm for replicated state machines operating under strong Byzantine assumptions: fewer than one-third of members may be malicious, colluding, and able to delay or delete messages, while messages repeatedly sent between honest members eventually get through. The protocol is asynchronous and nondeterministic, achieving consensus with probability one rather than relying on deterministic termination.
Its central data structure is a directed acyclic graph of signed events. Each event records a creator, payload, timestamp, self-parent, and other-parent. Members repeatedly use random-peer gossip, while the events record the history of that communication—“gossip about gossip.” Because participants reconstruct the same ancestry and communication relationships, they can infer one another’s votes locally. This virtual voting eliminates separate vote messages and is intended to keep communication overhead close to the cost of disseminating the transactions themselves.
The algorithm assigns events to rounds and identifies the first event created by each member in a round as a witness. Virtual elections determine whether witnesses are famous. Periodic coin rounds provide nondeterministic progress when an adversary keeps votes divided. Famous witnesses then act as judges: an event receives a consensus round when all unique famous witnesses in that round have received it, and its consensus timestamp is calculated as a median of the relevant member timestamps. Events are ordered first by received round, then by consensus timestamp, and finally by a deterministic signature-based tie-breaker.
The Byzantine-fault argument depends on the definition of “strongly seeing.” If an event strongly sees one branch of a fork through events created by more than two-thirds of members, no event in a consistent hashgraph can strongly see the other branch. This prevents a Byzantine member from using a fork to make honest members derive incompatible virtual votes. The paper concludes that every event created by an honest member eventually receives a fixed position in the total order with probability one, assuming the stated communication, signature, and hash-function conditions.
The paper also describes weighted, proof-of-stake generalizations; signed consensus states that permit historical data to be discarded after checkpointing; bandwidth optimizations; faster election behavior under normal network conditions; and implementation techniques for efficiently testing strong visibility.
Influence and subsequent use
- Later distributed-ledger surveys identify the paper as an early asynchronous Byzantine-fault-tolerant protocol based on a DAG, gossip about gossip, and virtual voting. (doi.org)
- Subsequent DAG-consensus research, including the Teegraph work, cites the paper as prior work while developing related DAG-based consensus mechanisms for IoT data sharing. (mdpi.com)
- In industry, Hedera identifies this document as the original Hashgraph consensus paper and implements the hashgraph approach in its public distributed ledger. (hedera.com)
- On January 19, 2022, the Hedera Governing Council announced that it had voted to purchase the hashgraph algorithm’s intellectual-property rights from Swirlds and committed to open-sourcing the consensus code. (hedera.com)