Hashgraph: a Byzantine fault-tolerant state‑driven, history‑interpreting consensus algorithm

State-driven and history-interpreting distributed system algorithms accumulate state into a local data structure and make decisions by interpreting that structure. Global state emerges based on a trusted and ever-expanding history of the system.

Achieving consensus in asynchronous, adversarial networks is a tough challenge. Any algorithm must tolerate faulty actors that might introduce favourable state to mislead and skew a result in their favour. Hashgraph achieves deterministic agreement without coordination.

By contrast, protocol-driven algorithms, such as Raft and Paxos, do not interpret history, rather state is disseminated through message exchange and decisions are made based on that exchange. Such decisions are discrete, and are produced when the protocol's message-exchange rules are satisfied, which is often at the end of a round. This type of algorithm is not considered here.

This article explains how gossip communication and the properties of a directed, acyclic graph can yield deterministic consensus.

The stated goal of Hashgraph is fast, fair, deterministic asynchronous Byzantine-fault-tolerant consensus. Nodes reach agreement by interpreting a local directed acyclic graph (DAG) of events that is not only known to be shared everywhere, but all other nodes are aware that a consensus-defining DAG has been shared.

Hashgraph is the work of others. The algorithm is publicly available through Hedera (hedera.com), and the company responsible for developing and maintaining the algorithm is Swirlds (swirlds.com, operating under Hedera Hashgraph, LLC).

Hashgraph

This section outlines how Hashgraph works, focusing on the kinds of guarantees afforded by the fundamental behaviours that are required to enable a state-driven distributed algorithm to work.

The Hashgraph design is described by covering:

• nodes with private keys
• gossip communication
• DAG data trust
• decision quorums
• "seeing", "strong-seeing", rounds, "witnesses", and "fame", to reach consensus finality

while tolerating asynchronous Byzantine failure.

Hashgraph fundamentals

A Hashgraph network consists of a number of nodes, \(N\).

The node

A node is a process that participates in the Hashgraph consensus algorithm.

Every node has a private cryptographic key that is used to sign data before it is sent to another node, and a node persists its local DAG.

If a node crashes, the node reloads its local DAG on restart.

The design of Hashgraph is such that all the information required to correctly operate the algorithm is available either in the DAG or can be computed from the DAG. As all information is in the DAG, there is no need to run a separate message exchange.

No global state is available and there is no shared notion of time.

This defines the run-time environment in which gossip is performed.

Gossip

Hashgraph’s only communication primitive is gossip.

Gossiping leads to:

• nodes contacting other nodes pairwise at random, i.e., aschrnously with respect to each other
• no need for distributed coordination: to select a leader or keep to a global schedule
• eventual consistency through repeated data exchanges

Gossiping is a good approach for failure tolerance. It gracefully handles node crashes, delays, partitions, and Byzantine nodes.

A Byzantine node is a participant in a distributed system that behaves arbitrarily. One that might send false, inconsistent, or malicious messages, in a way that breaks the assumptions correct nodes rely on to reach consensus.

If a Hashgraph network becomes physically partitioned, the two partitions will not reach the same consensus. Each partition will produce its own internally valid sequence of events, but these sequences will diverge because nodes in one partition cannot determine whether any events in the other partition should be taken into account in its sequence.

Therefore, each partition independently produces a valid ordering, but the orderings on either side of the partition will differ because the partitions cannot agree on which relevant events are globally visible across the whole network.

Nodes disseminate their event data through gossip. In an adversarial distributed system where some nodes may be working to subvert a result, it is essential that a node can trust the data it receives.

DAG trust

The local DAG can be trusted when at least 2/3 of nodes are operating correctly, and in this case the algorithm can make safe forward progress.

Hashgraph can tolerate a maximum of 1/3 nodes that are not operating correctly.

Should this become greater than 1/3, the Hashgraph algorithm will not make forward progress and the network of nodes will not converge on consensus. Data will continue to be exchanged, computation will take place, but no useful result will occur.

2/3 of nodes and Byzantine errors

In Hashgraph, a number of non-faulty nodes is required to reliably make a decision so that the decision cannot be superseded by a group of faulty nodes. The ratio of non-faulty to faulty in the entire network must be at least 2:1.

If 2/3 of nodes are non-faulty, the ratio of non-faulty to faulty is 2:1. In a network of 120 nodes, 2/3 are required to be non-faulty: 80 nodes. The other 40 nodes can be faulty. This is a non-faulty to faulty ratio of 2:1.

In a distributed system, a node may occupy one of three categories:

• correct: that node follows the Hashgraph protocol exactly
• crash-faulty: the node may stop, drop messages, or send partial or corrupted messages
• Byzantine: the node may behave arbitrarily by lying, forging, equivocating, selectively omitting, replaying, or fabricating data

Equivocating is when a node sends two or more conflicting messages or events to different nodes, such that no single consistent history can explain all of them.

The difference between crash-faulty and Byzantine is intent. A Byzantine node is one that has been created to deliberately try to subvert the Hashgraph network and its protocols such that a consensus outcome is in its favour, and not in the favour of correct nodes.

As it crashes, a crash-faulty node may exhibit the same behaviour as a Byzantine node but if it does, this is a coincidence that has occurred only from how it failed. There is no intent on behalf of that code's author to have a crash-faulty node fail in a way that subverts the correct behaviour of the Hashgraph algorithm.

In the rest of this article, faulty refers to a node that exhibits behaviour that does not follow exactly the Hashgraph protocol. A faulty node may be crash-faulty or Byzantine.

Quorums in distributed systems

For a distributed system of N nodes to make forward progress, the total number of nodes must be greater than or equal to three times the number of faulty nodes plus one.

For Hashgraph, forward progress ensures the algorithm will eventually reach consensus.

The global network constraint for Byzantine fault tolerance is:

\(N \ge 3f + 1\)

This is required as it is the only way to prevent faulty nodes from creating contradictory decisions.

In distributed systems a subset of the N nodes can be used to make a decision but that subset must have enough non-faulty nodes in it. Intuitively, this is so that the decision reached by the non-faulty nodes is not contradicted by the faulty ones.

f is the number of faulty nodes in the network of N nodes. By rewriting \(N \ge 3f + 1\) for f we have:

\(f \le \frac{N - 1}{3}\)

A quorum is the subset of N nodes used to make a decision. For that decision to be sound assuming a number of faulty processes, the number of correct participants inside that quorum must outnumber the faulty participants by at least one.

\(q = 2f + 1\)

In a network of 121 nodes (\(N = 121\)), f is \(\frac{121 - 1}{3} = \frac{120}{3}\) so \(f = 40\).

A whole Hashgraph network of 121 nodes can tolerate a maximum of 40 faulty nodes.

The size of any Hashgraph quorum (a subset of \(N\)) must be \(2f + 1\) which is 81 nodes, of which up to 40 can be faulty.

When a subset of the 121 nodes is used to reach a decision, that subset (the quorum) must have 81 nodes in it.

Given it is assumed that there is a maximum of 40 faulty nodes in the whole network, it is never possible to create a \(2f + 1\) quorum that will have more faulty nodes than non-faulty nodes.

And, importantly, any two quorums of size \(2f + 1\) must always share at least one correct (non‑faulty) node. It is this single correct node in the overlap that prevents contradictory decisions.

Given \(N \ge 3f + 1\), the overall number of nodes must be \(\ge 3f\) because three disjoint groups of size f must be tolerated to cover all the ways Byzantine behaviour can break consensus:

• f nodes that may lie or equivocate
• a separate group of f nodes may be isolated or misled by those lies

and given the above:

• \(N\) must be greater than another group of f nodes so that two quorums overlap with one correct node to prevent contradictory decisions

The \(+1\) ensures that the "correct overlap" cannot be contradicted by the faulty ones.

In 121 nodes there are a max of 40 faulty ones, and two blocks of 40 correct nodes, plus a single extra correct node.

It is the second block of 40 correct nodes that ensures the network cannot be partitioned into two "truth islands".

Why one non-faulty node must be shared by two \(2f + 1\) quorums

A quorum has size \(2f + 1\).

At most f nodes in the entire system can be faulty.

Therefore each quorum contains at least \(f + 1\) correct nodes.

In such a system, if you form two quorums, each of size:

\(2f + 1\)

then, for these two quorums to not share any nodes (which would mean two decisions made by disjoint quorums that share no nodes), two lots of \(2f + 1\) nodes would be required:

\(2\times{2f + 1} = 4f + 2\)

But the system only has:

\(N = 3f + 1\) nodes.

Since \(3f + 1 < 4f + 2\) it is mathematically impossible for two quorums to be disjoint.

And because there are only f faulty nodes total, the overlap cannot consist entirely of faulty nodes.

Therefore the overlap must contain at least one correct node.

And it is this single correct node in the overlap that prevents contradictory decisions.

The next section describes the algorithm mechanics: how the steps fit together to turn a gossip DAG into a single agreed order.

The algorithm is tolerant of Byzantine faults assuming that both \(N = 3f + 1\) and \(q = 2f + 1\) hold.

The following algorithm executes in a distributed system of \(N\) nodes, each of which gossip data that can be trusted by any other node.

The algorithm

Hashgraph is a state‑driven, history‑interpreting consensus algorithm.

A Hashgraph node disseminates events. An event contains:

• creator ID: verifies which node created the event
• timestamp: verifies the creator’s claimed local time of creation
• self‑parent hash: verifies the event’s position in the creator’s own chain
• other‑parent hash: verifies the event’s position relative to another node’s chain
• transaction payload: verifies the application data included in the event
• gossip metadata: verifies auxiliary information used for gossip propagation
• signature: verifies the event was authentically created by the claimed creator
• event hash: verifies the integrity of all other fields (immutability)

containing cryptographically authenticated parent references, that forms a per-node eventually consistent directed acyclic graph that encodes the full causal history of communication.

It is these references that allow other Hashgraph nodes to construct an identical DAG regardless of communicated event ordering. A receiving node can trust each reference as each one is cryptographically signed.

Gossip Communication

Gossip communication disseminates data pairwise, randomly, and eventually to all nodes.

In a distributed system, this approach leads to:

• nodes contacting random peers
• there being no need for distributed coordination: to select a leader, or stick to a global schedule
• repeated data exchanges that ensure eventual consistency
• gossip working even with crashes, delays, partitions, and Byzantine nodes. This is a property of eventual consistency

A Byzantine node is a participant in a distributed system that behaves arbitrarily. One that might send false, inconsistent, or malicious messages, in a way that breaks the assumptions honest nodes rely on for correct coordination.

Data dissemination

In between gossip exchanges, a Hashgraph node will accumulate a set (S) of new events that originate from two sources: locally created events, and events received from remote nodes during the previous gossip exchange.

When a node, A, gossips with another node, B, node A selects a subset of the events from S and sends them to B.

When B receives that set of events, it adds those that it has not seen before into its local DAG. Determining what has not been seen before is done by B checking event hashes.

B constructs its local DAG using the event references. In this way, over time all nodes will build the same DAG.

Building the same DAG

Each Hashgraph node builds the same DAG because each event contains parent references and it is the reference that determine the structure of the graph. Event arrival order of A's events at B cannot change the shape of the DAG at B.

Hashgraph events contain enough information:

• creator ID
• self‑parent hash
• other‑parent hash
• event hash
• signature

so that every node can verify:

• which node created the event
• exactly which two earlier events an event references
• that the event has not been tampered with
• that the parent references are authentic
• that the event belongs in one and only one place in the DAG

The DAG structure is fully determined by the events and as the references are cryptographically hashed, receiving nodes can verify that the references are genuine.

The fundamental Hashgraph data layer

All of the above Hashgraph features provide the necessary security and eventual consistency properties that an asynchronous, Byzantine fault-tolerant distributed consensus algorithm can be built on top.

Without the above design, the following could not be built as the necessary system behaviour properties would not exist to enable a secure, distributed systems consensus algorithm.

The above Hashgraph system ensures that both the same DAG state and the same DAG structure are eventually available at every Hashgraph node.

The sections below describe how the DAG is interpreted to achieve consensus.

Seeing

The most basic relation is seeing. A node’s event x sees another event y in the local DAG if:

y is an ancestor of x, i.e., y happened before x.

y is an ancestor of x if there is a path of parent references from x to y.

This is a simple reachability relation. Can y be reached from x by following only parent references?

This is something that can be determined by the node purely with respect to its local DAG: no additional communication, voting, or protocol rounds are required.

Seeing is the foundation for all higher‑level consensus guarantees.

Strong seeing

Strong‑seeing strengthens the notion of seeing by adding a condition at a node that is also true at a minimum number of other nodes. This condition is known as a quorum condition.

A quorum is a large‑enough subset of participants whose agreement is sufficient to safely make a decision.

Event x strong‑sees event y if:

x sees y, and

x sees y through ≥ 2/3 of the nodes’ event chains

That is to say:

x sees y via a supermajority of distinct creators, i.e., the node that contains x knows that ≥ 2/3 of all nodes also see y.

This does not imply the other nodes strong-see y. The local node can only rely on knowing that it strong-sees y and that 2/3 of other nodes can also see y.

The node that contains x can conclude that y is known by a supermajority (≥ 2/3) of all nodes, and therefore no non-correct minority can hide y, suppress y, or create a conflicting view of history that excludes y.

Strong‑seeing allows correct nodes to detect when an event is known by enough correct nodes that a correct node can be confident enough other correct nodes also see it so that witness and fame decisions can be safely made.

Seeing and strong‑seeing tell a node what it knows and how widely that knowledge has spread. But they do not tell the node when the network has collectively reached a safe point to advance consensus.

Rounds add a deterministic boundary in the DAG. Every node independently computes the same round number for every event. This creates a shared notion of progress without reference to shared time or protocol rounds.

Hashgraph needs a moment, derived entirely from the local DAG where a node can safely conclude that enough information has propagated that consensus can be advanced, and every non-faulty node will reach the same conclusion.

Rounds

Rounds are not communication rounds. They are state computed from the DAG so the algorithm can ensure progress that is not based on time or message order.

Each Hashgraph node assigns a 'round' number deterministically, such that:

The first event created by each node is in round 1.

An event is in round r if it does not strongly‑see enough witnesses from round r; otherwise it is in round r+1.

This rule ensures:

• rounds advance only when enough information has propagated
• all nodes compute the same round numbers

Rounds are the backbone for witness detection and fame voting.

Witness detection and fame voting are the two mechanisms Hashgraph uses to turn the raw DAG into final consensus.

Seeing and strong‑seeing tell you which nodes know what. Witnesses and fame tell you which knowledge becomes consensus.

Witness detection

Witness detection reveals the set of events that will participate in consensus voting for a given round.

A witness is:

• the first event a node creates in a round
• deterministically identified from the DAG
• visible once enough gossip has propagated

Witness detection from the local DAG gives:

• the consensus voters
• the structure of the voting round
• the boundaries between rounds so one round can be distinguished from another

In summary, witness detection and fame voting are a pair, in the same way seeing and strong-seeing are.

The first (seeing and witness detection), is local knowledge, and the second of each pair (strong-seeing and fame) is supermajority‑validated knowledge. And to move from the first to the second, more gossip communication is required.

At the end of witness detection the Hashgraph algorithm is aware who will vote and which events represent each node’s voting knowledge.

But each node still does not know:

• which witnesses are widely known (supermajority-validated)
• which witnesses are safe to define consensus
• which witnesses will be used to timestamp events
• which witnesses will define the total order

Witness detection alone does not give consensus. It only sets up the voting that is determined by fame and it is fame that gives consensus.

Fame

In Hashgraph, consensus requires:

• A set of voters. These are the witnesses
• A set of voters known to \(2f + 1\) nodes. These are the famous witnesses
• A deterministic ordering derived from them. This is an agreed total order

The set of voters represent each node’s knowledge at that round boundary.

A set of voters known to \(2f + 1\) nodes are famous voters that can be safely relied upon. because quorum overlap guarantees all correct nodes will agree on them.

Based on these famous voters, a deterministic ordering is derived from them which is an agreed total order. This is the final consensus output.

Every event gets a consensus timestamp calculated by the median of timestamps from famous witnesses that see that event.

Events are sorted by that timestamp and ties are broken deterministically such that two nodes will break a tie in the same way.

Deterministic tie‑breaking happens after consensus timestamps are assigned. If two events end up with the same consensus timestamp, Hashgraph applies a strict, deterministic ordering rule so every node breaks the tie in exactly the same way.

All nodes compute the same total order.

By this stage, each node has a latent consensus agreement which is only a property of the local DAG.

In the final stage, an event becomes permanently ordered and that order cannot be overturned by any future gossip. When all \(N\) nodes have this, consensus is agreed - not just known - across all nodes.

Finality transition

Once a round’s famous witnesses are known, every node can:

• compute the same ordering of events
• know that no future gossip can change that ordering
• know that every other node will compute the same ordering

When this happens, consensus becomes explicit and agreed across the \(N\) nodes.

To achieve this, Hashgraph marks all events in earlier rounds as final.

Before this marking:

• nodes have the same DAG
• nodes could compute the same order

but nodes do not yet know that the order is final. This is the latent consensus.

After the marking:

• nodes know the order is final
• nodes know other nodes know the same order is final
• nodes know that no future gossip can change the finality of this order

Therefore, each node can safely act on this result, such as commit a transaction.

Hashgraph’s transition to consensus finality occurs when witness fame is decided, making the event order immutable in all \(N\) nodes, and each node knows that such an order is immutable at all other nodes. This turns the implicit DAG agreement and latent consensus into an explicit, safe consensus.

Conclusion

Hashgraph demonstrates that distributed consensus does not need leaders, rounds, or protocol‑driven coordination to produce a single, agreed‑upon history.

By relying entirely on gossip and a state‑interpreting DAG, Hashgraph shows that a network can reach fair, deterministic agreement even in the presence of Byzantine behaviour.

Consensus can be achieved through information propagation rather than message choreography.

Deterministic finality is a property of the data structure and the fair ordering that it depends on is mathematically enforced.

Hashgraph’s model shows that a distributed system can be both asynchronous and Byzantine‑fault‑tolerant while still delivering a single global order that cannot be overturned.

This expands the design space for distributed algorithms where state, causality, and finality emerge directly from the structure of shared history.

Hashgraph offers consensus as a property of an interpreted event history, not through a negotiated protocol.

Hashgraph expands the design space for distributed systems by showing that consensus can emerge from interpreted history rather than a negotiated protocol.

Read next: Preventing Double‑Spend: Idempotency, Internal IDs, and the Discipline of State Before Side‑Effects
A precise look at how disciplined state handling prevents data corruption.

Related Articles