While most of my time interacting with Web 3.0 applications is on Solana (due to the excellent speed and user-facing apps, e.g. Phantom, Jupiter, Birdeye, etc), Hedera has come up in the enterprise context a few times, and wanted to understand why this network exists, what a hashgraph is, and how this solution compares to other proof-of-stake systems.

Hedera runs EVM-compatible smart contracts (making it easier to leverage existing Solidity developers), and the Hedera 'ledger' is a "decentralized, open-source, proof-of-stake public ledger that utilizes the leaderless, asynchronous Byzantine Fault Tolerance (aBFT) hashgraph consensus algorithm."

A few terms first - a 'byzantine fault' is a failure due to a malicious actor in a decentralized network, where they claim to act in one way, but actually act in another. Wikipedia is illustrative here, where the 'decentralized network' is a group of generals planning a joint assault. If all the generals attack together, they'll succeed. But, if the generals all announce they will attack together, but a few leave - the battle is lost. This is the 'malicious' aspect of a byzantine fault:

'Leaderless' in this context refers to Hedera's ability to reach consensus without electing a 'leader' node to order transactions or otherwise coordinate the consensus process. Specifically, this relates to the way Hedera's proof-of-stake aspects operate, where holders of HBAR token (the native Hedera token) can stake it with validator nodes to increase the weight of that node's input in achieving consensus. Fundamentally, this 'leaderless' validation is different from other distributed ledgers (like Solana, which currently uses Leader Rotation, where technically, a malicious leader could censor certain events - which is why Solana rotates leaders every 1.6 seconds / every block).

Example nodes gossiping, from Patent 10375037. Events sent between nodes are thin lines

'Asynchronous' applied to Byzantine Fault Tolerance also relates to the Hedera Gossip Protocol, and the ability for Hedera to achieve BFT without synchronous communication between nodes. The hope is that as the number of nodes scales up, aBFT prevents negative performance impacts that would otherwise exist with synchronous BFT (as synchronizing state between more nodes before reaching consensus necessarily takes more time).  The 'staking' aspect of Hedera also comes into play here: "transactions are placed into consensus after they're validated by nodes representing an aggregate stake of over two-thirds of the network’s total supply of hbars." So, as nodes gossip, state is shared between nodes. Once nodes containing over 2/3 of the staked HBAR have equal hashgraphs up to a certain event / time (which may be close to 2/3 of nodes, assuming they all hold similar amounts of staked HBAR), events up to that time are considered to have reached consensus.

Essentially, aBFT refers to Hedera's ability to 'allow for honest nodes of a network to guarantee to agree on the timing and order of a set of transactions fairly and securely'. An independent (CMU) Coq proof exists for this aBFT claim as well - and formal verification is a great result to see in this space. As an aside, Leslie Lamport invented TLA+, a popular formal specification language for distributed systems - Lamport is the name given to the smallest unit of native token on Solana as well, as Lamport is Solana's "biggest technical influence".

The Hashgraph

From "What is hashgraph consensus?"

Notably, despite being 'open source', the hashgraph algorithm is protected by a variety of patents, which are instructive in explaining various aspects of how the network operates to distribute data.

The 'hashgraph' term captures a key concept behind Hedera - that data recorded on the network (specifically, individual 'events') are 'hashed', and shared between nodes in a directed acyclic graph (DAG), so that hashes of series of events are propagated between different nodes in the network. A key goal here is to achieve consensus for data stored in a 'distributed database' (which is what the hashgraph ultimately is - a set of nodes that seek to store an eventually consistent event log). While algorithms like Paxos (and Raft, and so on) exist and accomplish this goal, Paxos requires a server within the distributed database to be a 'leader', which then decides the order of events. Hedera attempts to resolve this event ordering issue without a centralized server.

In Hedera, an 'event' contains:

  • d= Payload data
  • h = Hashes (a list of hashes of the events two parents - the 'self parent' and the 'other parent')
  • t = Event creation time
  • c = Event Creator ID
  • s  = Event creator signature (signing the above fields d, h, t, c)

In a nutshell, assume that each node in the network contains a distributed database of 'events', and a given node (e.g. node A) communicates these events to other similar nodes. The gossip protocol ensures that Node A randomly selects another node (say, "Node B") and communicate all information received so far with that other node. This is referred to as gossip sync, which is finalized by each member of the 'gossip sync' creating a special event. This event follows the structure above - and the hashes being created by each node effectively capture the 'current state' up to that point. As more events propagate, a 'graph' of these hashes (a 'hashgraph') emerges - every node keeps a local copy of the hashgraph, and it continues to update as the gossip sync continues to propagate new messages between nodes.

Gossip about Gossip

We glossed over this aspect above, but recall that the gossip sync includes two parent hashes (the 'self-parent' and 'other-parent' hash). By hashing both our own 'previous' state and the 'incoming' previous state, we're effectively 'building up' a history - and future hashes will be applied with these hashes as part of the input, continuing to build up a consistent hash history. Because events also contain a timestamp, the hashes in an event tell us not only what state the parent (self or other) hashgraph was at, but at what time the parent had that hashgraph state. So, all nodes are propagating state, as well as when they receive that state. 

When nodes share state, they also receive state from the node they are sharing with - this is the 'gossip about gossip' aspect, and represents events propagating through the network (through an arbitrary number of gossiped intermediate nodes).

Notice we haven't used 'voting' anywhere in this article. Thats because voting is not part of the Hedera Hashgraph. There is no step where validators all stop and 'agree on a block' before moving forward (and there are also no 'blocks'). This is where the consensus mechanism for Hedera differs significantly from other distributed ledgers - and we see that Hedera is not a blockchain. This has significant implications for node scalability - because consensus can be reached asynchronously, the time to reach consensus scales sublinearly as the number of nodes increases.

This is a critical takeaway - Hedera's 'Gossip about Gossip' introduces 'virtual voting', to achieve the same consensus result as traditional consensus voting, but without a time-consuming voting step. There are no ballots, no receipts, and no validation leaders in Hedera.

Rounds and Witnesses

Every node eventually receives the same set of ancestors for any event X, and the same set of edges between those ancestor vertices. Hedera implements 'virtual voting' to agree on ordering of these events in three steps:

  1. Divide Rounds
  2. Decide Fame
  3. Find Order

Rather than focusing on the same breakdown in the documentation, we'll look at the unique terminology emplyoed by Hedera. A "witness" refers to a special kind of event.

The first (earliest) event for a given node is referred to as the 'first witness' for that node, and represents the beginning of the first round for that node. Until a new witness (first event seen for a new node) is encountered, all events remain part of this 'first round'. A witness is only created if 2/3 of the existing witnesses in the current round are 'strongly seen' by the new event (witness).

This is another way of saying 'we only consider a node to be part of the hashgraph for a given round if an event generated by that node can trace its ancestry back through 2/3 of the existing nodes in the network in the previous round". 

Once a new witness is identified, that witness becomes the first event in the next round for the node.

A witness (event) is labeled 'famous' if many future witnesses (in the next round) can see it, where 'many' is 2/3 of the witnesses. Since the hashgraph is acyclic (one-way), 'seeing an event' is always 'looking into the past' - so a famous witness is famous if witnesses in an upcoming round see the 'famous witness' in their ancestry.

Now, we've got all the witnesses for a given round, as well labels for whether they are 'famous' or 'not famous'. We can finally calculate the order of events from this information, by calculating (from the docs):

  1. The round received for all events that have yet to be ordered and that have occurred before a round where the fame of all witnesses has been decided. The event’s round received is the first round where all famous witnesses of that round can see (or are descendants of) the event in question.
  2. The timestamp for each event. This is done by gathering the earliest ancestors of the famous witnesses of the round received that are also descendants of the event in question, and taking the median timestamp of those gathered events.
  3. The ordering of events first by: round received, consensus timestamp, then signature.

If you're more of a visual learner, check out this deep dive video from Hedera.

Client Interactions

Now we generally understand what the hashgraph is, but how does actual userdata fit in? From the docs, a client (application) might submit a transaction via an API call, which specifies:Which node to submit the query or transaction to (Node Account)

  • Transaction ID (two-part ID, showing the account ID of the paying account and the start time of the transaction)
  • Transaction Fee (max fee to pay for this transaction)
  • Valid Duration (how long to consider this transaction valid before expiring it without executing it)
  • Memo (100 byte optional string)
  • Transaction Type (smart contract call, HBAR transfer)
  • Signatures (at least the signature of the paying account)

The client SDKs for submitting transactions typically auto-select the node, and the client can then wait to see if the transaction was received successfully. The transaction is propagated through the hashgraph (it is an 'event' seen by the receiving node and added to its local copy of the hashgraph, so eventually, via the gossip protocol, other nodes will know about it as well).

From Hedera "Core Concepts"

In addition to transactions, clients can submit queries, which do not modify state, and do not propagate through the hashgraph. Instead, the client can opt to pay a fee, and ask the node to perform a lookup on the hashgraph. A simple query is checking for when a transaction reaches confirmation state - meaning it is officially part of the ledger (the hashgraph has reached consensus regarding this transaction). 

Decentralization

Notably - the hashgraph is only stored on the participating nodes, and Hedera does not currently support community nodes/validators, and only supports permissioned, 'official' nodes (of which there are currently ~30, generally run by the Governing Members). In contrast, Solana currently has 1700+ mainnet validators, providing a much greater level of decentralization than Hedera.

Hedera seems aware of the issue here, and has published a Path to Decentralization paper, but time will tell if the 'Governing Members' will ever reach that state - the 'trigger' for moving foward (to additional permissioned nodes, a stepping stone towards fully permissionless nodes) is a fairly ambiguous "when we decide it is time" statement:

"When the Hedera network’s security, stability, and incentives are determined to be sufficient by the Hedera Governing Council, peripheral parties and organizations will be invited to join the Hedera mainnet as permissioned consensus node operators and earn hbar cryptocurrency"