Hedera Technical Insights: Finality of Consensus — you can take it to the bank (or maybe you are the bank?)
For individuals, being willing to change your mind is generally seen as a good thing — it suggests flexibility and a willingness to accept new data or evidence, even if it contradicts a previously held belief.
Not so for a consensus node in a distributed ledger. Once a consensus node decides on the proposition under consideration — for it to later change its mind complicates the goal of the network as a whole agreeing on that proposition.
In blockchains, the proposition under question is generally “what block should go on the end of the chain?” Blockchains differentiate themselves by the mechanism by which this question is decided. Some blockchains simply have different nodes take turns proposing a block and, as all nodes know whose turn it is, there is no uncertainty over the decision. If the decision process is not so deterministic, it may be possible for there be two valid blocks at a moment in time, and so no immediate answer. In Proof-of-Work (PoW) chains, the miners race to complete the hash puzzle and so win the right to have their block picked as next. As it is possible for two miners to both solve the puzzle around the same time, both proposed blocks are valid candidates to be chosen to be placed at the end of the chain. With both blocks then sent out to the rest of the network by the miners that created them (eager for the associated reward), the network must reconcile the disagreement. Both blocks deserve to be placed at the end of the chain, but only one can be. Which to choose? The chain, until the uncertainty is resolved, has split or forked. PoW chains typically resolve the issue by waiting until another hash puzzle race is completed — the winning block will have necessarily chosen one or the other of the earlier competing blocks. Whichever earlier block was chosen by this new block is retroactively blessed and the other discarded (or orphaned). This is the so-called “longest chain” rule for resolving chain forks — participants agree to build on the longest chain if there is a choice to be made.
The two earlier candidate blocks inevitably contained different sets of transactions — as the miners that created those blocks would have had a different set of transactions waiting in their different mempools. It’s possible that a particular transaction was in one block but not the other. Consequently, it’s possible that a given transaction is in the block that is orphaned but not in the block that is part of the longer chain. If so, then that transaction won’t be processed by the network. For instance, a BTC transfer won’t be made or a smart contract call on Ethereum won’t happen. For whoever sent the transaction, sorry about that. It will still be sitting in the miner’s mempools so it will hopefully be added to a later block. But critically, if there had been any exchange of value based on the assumption that the transaction in question was going to go through because it was in a block that had satisfied the hash puzzle, then someone will be disappointed. Using the archetypical coffee shop example — if the barista served the latte based solely on the payment being added to a confirmed block, then the customer may get the latte for free if the payment transaction is orphaned and never gets into a subsequent block.
A more nefarious scenario has an attacker attempt to manipulate the above temporary uncertainty — if they can send two different transactions spending the same coin into two winning blocks, then it’s possible that they can obtain value for each payment — effectively “double-spending” the coins. As explained above, the network will eventually resolve the discrepancy and only one transaction will be deemed valid, but that will likely be little consolation to whoever gave up something of value in exchange for the transaction that was deemed invalid.
It is for this reason that PoW chains recommend that those parties who rely on a payment being successfully processed wait a certain number of blocks to be added to the chain beyond the block the transaction in question is in. In Bitcoin, the recommended best practice is to wait for a total of six confirmations before assuming that the transaction won’t be in a block that gets orphaned — or the chain to be reorganized. As each block takes ten minutes on average, the best practice is to wait an hour before being fully confident that a BTC transaction is “good”. Ultimately, however, it’s a personal decision. For a latte, the coffee shop might be okay with one additional block. For someone selling a house, they would likely choose to wait the full hour or more before handing over the keys.
As additional blocks are added to the chain, the chances of a transaction in an earlier block being orphaned decrease quickly. After six block confirmations, the chances of a reorganization are very small, but not zero. There is always the theoretical chance that another chain, longer than that which a miner thought was the longest, will be discovered. If so, then the rules require that everyone switch — discarding the erstwhile longest chain (and unfortunately effectively throwing away the electricity spent on its creation).
In PoW chains, miners are required to be willing to change their minds about what chain to build on, and so there is always a chance that transactions previously assumed to be “locked-in” will be retroactively thrown out. Participants must account for this uncertainty.
In the hashgraph algorithm, the proposition under question that nodes must collectively establish agreement on is “is this particular witness famous?” The hashgraph data structure connects together groupings of transactions called “events”. Certain events have a special place in that structure and are called “witnesses”. Some witnesses are even more special — they are deemed “famous”. You can think of famous witnesses as those that are deeply woven into the hashgraph — like human celebrities, everybody “knows” them. All nodes look at the same hashgraph, identify the same set of witnesses for a certain portion of the hashgraph, and use the same algorithm to determine the famous witnesses within that set. Once the famous witnesses are determined, then it’s a straightforward process to calculate timestamps for earlier events within the hashgraph. All nodes identify the famous witnesses and perform the timestamp calculation separately, without any additional confirmations or receipts beyond the gossiped events themselves — but nevertheless come to the same conclusion.
And critically, once a node determines which witnesses are famous in a given section of the hashgraph, they won’t change their mind. If a node determines that a particular witness is not famous, then there is no possibility that it will receive additional information that will cause the node to reevaluate and instead determine that the same witness is famous. Nodes make a choice, and then stick with it. Of course, nodes don’t decide lightly, a node won’t decide on the fame of a witness until it receives sufficient evidence to support the choice — famous or not. The algorithm requires that nodes see agreement from more than 2/3 of the network before making the decision. With such a hard threshold, once a node is able to count enough votes and decide on fame of a particular witness, then hearing from any more of the network, whether that additional information affirms the choice or otherwise, is pointless. In fact it’s more than pointless, it’s wasteful and inefficient. Once nodes reach the threshold, they move on to the next decision — determining the fame of more recent witnesses. Another voting system that has a similar threshold and so similar finality is the US electoral college — once a presidential candidate receives 270 electoral votes, they are the winner. The states keep counting beyond that, but technically they don’t need to.
The above stubborn certainty for hashgraph nodes on the fame of witnesses is called “finality” of consensus. And finality in determination of the fame of witnesses translates into finality of the consensus timestamps and order of all events within the hashgraph (not just witnesses or famous witnesses). Once an event is assigned a timestamp and place in the full order, it won’t change. It can’t change; that would require that a set of famous witnesses changed and, as we saw above, nodes will not entertain that possibility.
Without finality of consensus, you must always to a certain extent “hedge your bets” — anticipating the possibility of a transaction being rolled back. It’s complicated. With finality, things are simpler. A dapp that sends a transaction into the Hedera mainnet and receives a receipt three seconds later with the consensus timestamp for that transaction doesn’t need to ask again three seconds later. Or six seconds. Or nine seconds. The answer will never change. And, with confidence that neither the consensus timestamp nor order of a transaction will ever change, the barista (or exchange, or supply chain partner, or vaccination clinic) can be equally confident that the transaction can be processed immediately with no risk of subsequently needing to be rolled back. Finality becomes particularly important when dealing with sharding or cross-chain interoperability.
There is no equivalent risk of double-spend in hashgraph as described above for PoW. If an attacker simultaneously sends two transactions into the network that together spend more hbars than in the balance of the account — both will receive a consensus timestamp and order. One will be deemed to have occurred earlier than the other. The later transaction will be rejected by all nodes as spending hbars that the account doesn’t have. The timestamps for the two transactions won’t change, and so neither will the determination of which transaction was earlier and valid.
With hashgraph’s finality, a transaction’s timestamp, order, and validity will not change — you can take it to the bank (or maybe you are the bank?)
Originally published at https://hedera.com on February 5, 2021.
