Hashgraph Consensus Explained

‍

Extracted from the MiCA Crypto Alliance HBAR whitepaper

‍

Gossip protocol and event structure

‍

The Hedera network uses the hashgraph consensus algorithm, which relies on Proof of Stake. Like other DLTs, the system starts with broadcasting of data packets through a “gossip protocol”, i.e. a system where nodes (computers) enter in contact with each other in a random fashion, sync (they share all their information or updates with each other), and continue to broadcast information to/sync with other nodes, resulting in an exponential growth in the dissemination of information and, as a result, an eventual convergence in knowledge about the transactions being submitted in the network.

‍

However, the data packets in the hashgraph are not mere transactions but “events” (gossip syncs are also events). Events in the hashgraph include not just the transactions itself, its timestamp, and the hash of the previous event (“self-parent”) – like in any other DLT – but also a second hash: The hash of the last event from the immediately preceding gossip by another node (i.e. the last event of the other node prior to the gossip sync event, “other-parent”). By including this additional information overhead, nodes are not just gossiping about transactions, but engaging in “gossip about gossip”. That is, by including the other-parent, a node is not only gossiped the information about the transactions received in themselves, but also about their ordering: When the other node learned about this transaction, and what the ancestors of each event are for each node. As a result, nodes are not merely receiving loose transactions but the graph of the transactions – the “hashgraph”, which each node stores.

‍

Leaderless consensus via virtual voting

‍

After the transactions have been broadcast, DLTs will usually require a voting system, a leader-system, or a combination of both to achieve consensus. To achieve an agreement of what transactions are permanently stored, and in what order, nodes submit messages with their votes in this regard, or a leader node (block proposer) that will make this decision is selected by the protocol (through a system that could be mining, staking, others), or messages containing votes about electing a leader node. None of this happens in the hashgraph. Thanks to the initial overhead submitted in the form of the two hashes, all nodes have a copy of the hashgraph and can calculate a total order of the events getting the same answer. Furthermore, all broadcast transactions are accepted as long as they are valid, with no node being allowed to exercise a leader’s discretion.

‍

As a result of this architecture, copies of the hashgraph are always necessarily consistent, by definition. Due to asynchronicity, these copies may not be identical if a node has “seen” events that another node has not yet seen – although eventually this will happen – but the consistency of the ordering is ensured. If two nodes have a given event, they are guaranteed to also have all its ancestors.

‍

Rounds, received times and fair ordering

‍

This ordering is calculated in rounds of elections, but these elections do not have messages sending votes. Instead, each node is able to locally apply the protocol’s voting algorithm to calculate what vote another node would have sent if it were actually sending votes over the internet. In each of these voting rounds, each node votes (i.e. is simulated to vote) on the events they can “strongly see”. Strongly seeing an X event is having in storage multiple independent Y events which contain event X as their ancestor.

‍

This data structure not only saves bandwidth by not requiring voting messages, but also strongly mitigates dishonest behaviour, as through virtual voting even malicious nodes vote honestly. As a form of malicious behaviour consists in sending inconsistent votes to other nodes, other DLTs require messages with “receipts” of each vote received, which entails additional overhead that the hashgraph does not require.

‍

The content of the voting is always the response to a YES/NO question (e.g. whether an event is famous, whether an event is a witness to another event, etc.), which is calculated in a purely algorithmic manner. In voting rounds, the “received round” is also calculated, as well as the “received time”. If two events are recorded in the same round, they are ordered based on their received time If there is still a tie, the tie is resolved by arranging them according to their signatures. This has a unique implication: Fair ordering of transactions.

‍

Every distributed ledger faces the problem of not just arranging what transactions are stored, but also in what order. Furthermore, it is also crucial that this order is “fair”, which in the Hedera network is defined as follows: A transaction has been received by the network once it has reached a significant fraction of the entire community of nodes; once a transaction has been received by the network, it is fair that this transaction is placed after all the transactions received before itself, and before all the transactions received after itself. In hashgraph, this is achieved by calculating the median timestamp of an event (the median of the times at which each node says it first received an event). This ensures fair timestamping and fair ordering of transactions.

‍

Permissioning, Proof of Stake and Sybil resistance

‍

Nevertheless, this system would be vulnerable to numerous nodes joining the network, colluding and biassing the median in their favour. In this scenario, the hashgraphs would still be consistent, but ordering would not be fair. To avoid this, the Hedera network started as a permissioned network with trusted nodes run only by identifiable, highly reputable world-leading organisations who have a reputation to protect and are therefore unlikely to collude. As the network matures and it progresses towards a permissionless architecture, a Proof of Stake system is introduced into the virtual voting algorithm, such that e.g. the median timestamp becomes a weighted median, whereby nodes’ votes are valid by the percentage of the stake held by each node.

‍

As a result, if a Sybil attack is attempted (an attack in which a malicious actor seeks to manipulate a vote by creating numerous fake identities casting the votes), it would not succeed unless the attacker has amassed a very significant fraction of the total stake (⅓). The coin distribution schedule and the managed path to depermissioning in accordance to the maturity of the network mitigates this possibility, as the Hedera Council makes sure to make decisions on coin economics and permissioning in a safe way.

‍

Staking is optional. Tokens remain fully liquid, with no lock-up period, and there is no fixed minimum or maximum amount that an individual account must stake. To be eligible for rewards, an account must be staked for a minimum of 24 hours.

‍

Each node has a configurable maximum stake threshold which sets an upper limit on the amount of weight a node can contribute to consensus. Any stake above this threshold does not increase the node's influence or the proportion of rewards distributed. This cap is designed to prevent any single node from accumulating excessive influence, supporting fair transaction processing and Sybil resistance. The maximum stake per node is currently fixed at 450 million HBAR, and both this value and the minimum of 0 (zero) HBAR can be updated through network governance.

‍

Rewards for accounts staking on the Hedera network are distributed from the staking reward account (ID: 0.0.800), which has no keys and cannot return funds. Any community member can contribute HBAR to this account.

‍

The Hedera Council sets the reward rate and may update it over time. The reward rate is currently capped at a maximum of 2.5% annually. Rewards are calculated based on several factors including the amount staked to a given node, the total amount stakes on the network and node performance, and accrue in full-HBAR units.

‍

Indirect staking is also supported: If one account stakes to another that is itself staked to a node, both balances count towards the node’s weight, but only the directly staked account receives rewards. Accounts may also stake without opting into receiving rewards.

‍

Leaderlesness

‍

Other networks address the problem of transaction ordering by simply taking turns to elect a leader (block proposer) that will select the batch of transactions added to the shared ledger, with the consensus timestamp being the timestamp decided by the leader. This however results in a transaction ordering that is not only not fair by definition, but potentially also corrupted: If leaders collect fees and may decide which transactions are added to the ledger earlier than others, there is an incentive to bribe the leaders to front-run transactions ahead of others, which introduces all sorts of negative possibilities in the network’s landscape.

‍

Leader-based systems are also vulnerable to other attacks, e.g. attacks that concentrate on shutting down each leader’s turn and “follow the leader” once the leader changes. The hashgraph, in turn, is leaderless and does not have these problems.

‍

Signed state and immutability guarantees

‍

In addition, in the hashgraph, once sufficient consensus is reached on a round and history can be considered immutable for all events up to the round. This ensures that all subsequent events (even those yet to be discovered) are assigned to later rounds. A member can then compile all transactions from these events, input them into a database in their agreed-upon order, and compute the resulting state from these transactions. Since every member adheres to the same order, they will all arrive at the identical state. This is a consensus state, which each member can hash and digitally sign the hash, putting the signature into a new transaction. When signatures from at least one-third of the population are gathered, this collection, along with the consensus state, forms a signed state that represents the official consensus for the system at the beginning of the round.

‍

This signed state can be shared with individuals outside of the community, who can then verify the signatures and, as a result, trust the authenticity of the state. At this point, all previous transactions could be deleted (they may also be kept) without any negative consequence, as the system is still immutable and secure and the state can be trusted. This feature of the consensus is called a “signed state” and is another advantage over alternative architectures. Other DLTs cannot guarantee consensus in this fashion, even by resorting to leaders, but only approximate it probabilistically while building in inefficiencies.

‍

For instance, in Bitcoin’s proof of work it is possible that two blocks are mined almost simultaneously or that, for any other reason, the community starts building on two branches of the transaction history at the same time. While eventually one branch will be abandoned and can be discarded, as the other branch accumulates more “work”, this is inefficient as many honest transactions could be discarded.

‍

Furthermore, at no particular point in time it is really known that consensus has been achieved. Rather, there is a probability of confidence that increases over time. In turn, in the hashgraph there is full confidence in consensus and furthermore, no transactions need to be discarded, and no branches are pruned.

‍