Hashgraph consensus explained
The hashgraph data structure and consensus algorithm provides a new platform for distributed consensus. This introduction gives an overview of how hashgraph works, and some of its properties. The goal of a distributed consensus algorithm is to allow a community of users to come to an agreement on the order in which some of the users generated transactions, when no single member is trusted by everyone. In this way, it is a system for generating trust, when individuals do not already trust each other. Hashgraph achieves this in a fundamentally new way.
A blockchain is like a tree that is continuously pruned as it grows – this pruning is necessary to keep the branches of blocks from growing out of control and to ensure the ledger consists of just one chain of blocks. In hashgraph, rather than pruning new growth, such growth is woven back into the body of the ledger.
In both blockchain and hashgraph ledgers, any user can create a transaction, which will eventually be put into a container (the “block”) and will then spread throughout the distributed network.
In blockchain, those “blocks” of containers are intended to form a single, long chain. If two blocks are created at the same time, the network nodes will eventually choose one chain to continue and discard the other one, lest the blockchain “fork” into two different chains. It is like a growing tree that is constantly having all but one of its branches chopped off.
In hashgraph, every container of transactions is incorporated into the ledger — none are discarded — so it is more efficient than blockchains. All the branches continue to exist forever, and are woven together into a single whole.
Furthermore, blockchain fails if the new containers arrive too quickly, because new branches sprout faster than they can be pruned. That is why blockchain needs proof-of-work or some other mechanism to artificially slow down the growth. In hashgraph, though, nothing is thrown away. There is no harm in the hashgraph data structure growing quickly. Every member can create transactions and containers whenever they want.
Finally, because the hashgraph does not require pruning of would-be “forks” (as every container of transactions is incorporated into the ledger), hashgraph allows more powerful mathematical guarantees, such as Byzantine agreement and fairness. Distributed databases such as Paxos are Byzantine, but do not guarantee fairness in the ordering of transactions. Blockchain is neither Byzantine nor fair. The hashgraph algorithm accomplishes being fair, fast, Byzantine, ACID compliant, efficient, inexpensive, timestamped, and DoS resistant.
Hashgraph is incredibly energy efficient and performant
A hashgraph distributed ledger is inexpensive to operate compared to blockchain distributed ledgers, as it avoids energy-intensive proof-of-work. Individuals and organizations who want to run hashgraph nodes will not need to purchase expensive custom mining rigs. Instead, they will be able to run hashgraph nodes via readily available hardware that is less expensive than such specialized mining rigs.
The hashgraph is 100% efficient, as that term is used in the blockchain community. In blockchain, work is sometimes wasted mining a block that later is considered stale and is discarded by the network of nodes. In hashgraph, the equivalent of a “block” of transactions never becomes stale. Hashgraph is also efficient in its use of bandwidth. Whatever the amount of bandwidth required to inform all the nodes of a given transaction (even without achieving consensus on a timestamp for that transaction), hashgraph adds only a very small overhead of additional bandwidth to achieve a consensus timestamp and put the transactions into order. Additionally, the hashgraph voting algorithm does not require any additional messages be sent in order for nodes to vote on validating transactions (or those votes to be counted) beyond those messages by which the network nodes learned of the transaction itself.
The hashgraph is fast. It is limited only by the bandwidth. If each network node has enough bandwidth to download and upload a given number of transactions per second, the network as a whole can handle close to that many transactions per second. Even a fast home internet connection could enable a hashgraph node to be fast enough to handle transaction volume equal to that of the entire global VISA card network.
Once a network transaction occurs, within seconds all nodes in the network will know where that transaction should be placed in a history of transactions with 100% certainty. More importantly, every node will know that every other node knows this. At that point, the network can just incorporate the effects of the transaction and, unless needed for future audit or compliance, discard the transaction data. So, in a minimal cryptocurrency system, each node would only need to store the current balance of each network account that is not empty. The nodes would not need to remember the full history of the transactions that resulted in those balances all the way back to “genesis.”
All Hedera network communications are encrypted with TLS 1.2, all transactions are digitally signed, and the hashgraph is constructed using cryptographic hashes. All the algorithms and key sizes were chosen to be compliant with the CNSA Suite security standard. This is the standard required for protecting U.S. government Top Secret information. It specifies using AES-256, RSA 3072, SHA-384, and ECDSA and ECDH with p-384, along with ephemeral keys for perfect forward secrecy.
Asynchronous Byzantine fault tolerant
The hashgraph algorithm is asynchronous Byzantine Fault Tolerant (aBFT). This is a technical term meaning that no single node (or small group of nodes) can prevent the network from reaching consensus, nor can they change the consensus once it has been reached. Each Hedera network node will eventually reach a point where it “knows” for sure that the network has reached consensus. Blockchain platforms do not have a guarantee of Byzantine agreement, because a node never reaches certainty that agreement has been achieved. Rather there is just a probability that increases over time. Blockchain is also non-Byzantine because it does not automatically deal with network partitions — i.e., if a group of miners is isolated from the rest of the internet, multiple chains (“forks”) could grow that conflict with each other on the order of transactions.
It is worth noting that the term “Byzantine Fault Tolerant” (BFT) is sometimes used in a weaker sense of resistance to malicious behavior by other consensus algorithms. We use it in its original, stronger sense in that even if we assume (1) some attackers will collude to stop or skew consensus and (2) that some attackers could even control the internet itself (with some limits) and slow or prevent the delivery of messages, the network will eventually reach consensus and every node eventually knows consensus has been reached. Hashgraph is Byzantine, even by this stronger definition. So long as attackers have less than 1/3 of the total stake of hbars, they will be unable to stop consensus or even skew transaction timestamps or consensus order
There are different degrees of BFT, depending on the assumptions made about the network and transmission of messages.
The strongest form of BFT is asynchronous BFT — meaning that the network can achieve consensus even if malicious actors are able to control the network and delete or slow down messages of their choosing. The only assumptions made are that more than 2/3 are following the protocol correctly, and that if messages are repeatedly sent from one node to another over the internet, eventually one will get through, and then eventually another will, and so on. Some systems are partially asynchronous, which are secure only if the attackers do not have too much power and do not manipulate the timing of messages too much. For instance, a partially asynchronous system could prove Byzantine under the assumption that messages get passed over the internet in ten seconds. However, this assumption ignores the reality of botnets, Distributed Denial of Service attacks, and malicious firewalls.
The hashgraph consensus algorithm has been validated as asynchronous Byzantine Fault Tolerant (ABFT) by a math proof checked by computer using the Coq system. This proves the claims stated in the hashgraph tech report that hashgraph is ABFT — mathematically the highest possible level of security for distributed systems.
Coq is a formal proof verification system. Coq provides a formal language to write mathematical definitions and executable algorithms and theorems together with an environment for semi-interactive development of machine-checked proofs. It is often used for certifying the properties of programs, programming languages, and mathematics. Unlike most math proofs that are merely checked by humans, a Coq proof is actually checked by a computer. This avoids some of the mistakes that humans can make when reading a proof.
Hashgraph is fair because there is no leader node or miner given special permissions for determining the consensus timestamp assigned to a transaction. Instead, the consensus timestamps for transactions are calculated via an automated voting process in the algorithm through which the nodes collectively and democratically establish the consensus. We can distinguish between three aspects of fairness.
Hashgraph is fundamentally fair because no individual node can stop a transaction from entering the system, or even delay it very much. If one or a few malicious nodes attempt to prevent a given transaction from being delivered to the rest of the network and so be added into consensus, the random nature of the hashgraph gossip protocol through which nodes communicate messages to each other will ensure that the transaction flows around that blockage.
Hashgraph gives each transaction a consensus timestamp that is based on when the majority of the network nodes received that transaction. This consensus timestamp is fair, because it is not possible for a malicious node to corrupt it and make it differ by very much from that time. Every transaction is assigned a consensus time, which is the median of the times at which each node says it first received it. Received here refers to the time that a given node was first passed the transaction from another node through gossip. This is part of the consensus, and so has all the guarantees of being Byzantine. If more than two-thirds of participating nodes are honest and have reliable clocks on their computer, then the timestamp itself will be honest and reliable, because it is generated by an honest and reliable node or falls between two times that were generated by honest and reliable nodes. Because hashgraph takes the median of all these times, the consensus timestamp is robust. Even if a few of the clocks are a bit off, or even if a few of the nodes maliciously give times that are far off, the consensus timestamp is not significantly impacted.
This consensus time-stamping is useful for things such as a legal obligation to perform some action by a particular time. There will be a consensus on whether an event happened by a deadline, and the timestamp is resistant to manipulation by an attacker. In blockchain, each block contains a timestamp, but it reflects only a single clock: the one on the computer of the miner who mined that block.
Fair transaction order
Transactions are put into order according to their timestamps. Because the timestamps assigned to individual transactions are fair, so is the resulting order. This is critically important for some use cases. For example, imagine a stock market, where Alice and Bob both try to buy the last available share of a stock at the same moment for the same price. In blockchain, a miner might put both of those transactions in a single block and have complete freedom to choose in what order they occur. Or the miner might choose to only include Alice’s transaction, and delay Bob’s to a future block. In hashgraph, there is no way for an individual node to unduly affect the consensus order of those transactions. The best Alice can do is to invest in a better internet connection so that her transaction reaches everyone before Bob’s. That’s the fair way to compete.