Fragility in DLTs
Nov 08, 2018
by Paul Madsen
Technical Lead for Hedera Hashgraph

Some consensus algorithms are fragile — they cannot adapt to changes, either in the membership of nodes, or in the influence of those nodes towards consensus. The result is that such changes cause consensus to be prevented or corrupted. This can be a problem for some types of distributed ledgers, but it is not a problem for Hedera.

Hedera’s stake-based implementation of the hashgraph consensus algorithm was proven to be asynchronous Byzantine fault tolerant (ABFT) in this paper, and checked by computer with a Coq proof. Additionally, it is resilient in the face of changes to both node membership and the stake those nodes have, and so is not fragile. Nodes will join and drop, the amount of hbars those nodes stake towards consensus will change, the amount of hbars that other accounts proxy to those nodes will rise and fall, but the determination of consensus will adapt to such dynamics, and so will not be fragile. In order to determine a consensus order for transactions, nodes need only know the balances of hbars in accounts - the exact same requirement of a cryptocurrency. Importantly, nodes do not need to know the number of nodes in the network in order to be able to determine consensus.

Fragility

All distributed ledger technologies (DLTs) require that nodes have some level of knowledge about the rest of the network in order to: 

1. Send messages to those nodes
2. Validate messages from those nodes

Some DLTs also require that nodes be able to:

3. Assess the relative influence of other nodes towards consensus

We can say a DLT is fragile if changes to the set of consensus nodes, or their influence towards consensus, can cause consensus to be prevented or corrupted.

If, as an example, upon one node dropping, other nodes were to freeze, then clearly that system would be fragile. Similarly, if, upon a node changing its stake, the existing nodes were unable to appropriately determine the impact of that change towards consensus, then that too would be fragile.

Hedera

Hedera’s consensus model presumes that nodes have knowledge of the influence of other nodes and this influence can and will change over time. Though the network will launch with a permissioned phase, in time it will be possible for arbitrary nodes to participate — joining and leaving in ad hoc fashion. Additionally, a node’s influence will be proportional to their stake, and this will go up and down as they spend and receive hbars, or lose and gain proxy stake from other accounts.

Hedera would be fragile if, as node membership or staking changed, then the calculation of a node’s influence was inconsistent, such as if Alice and Bob were to calculate the influence of Carol differently.

But Hedera, like any proof-of-stake ledger that provides a total order for transactions, allows nodes to consistently adjust their calculations of influence and so account for node membership changes and other dynamics - and so guarantees that it will be resilient to such dynamics.  

The hashgraph virtual voting algorithm has nodes examine their local hashgraph and logically cast votes on behalf of other nodes. For Hedera, these votes are weighted based on the stake of the nodes. All nodes must therefore be able to calculate the influence of all other nodes towards consensus.

Calculation of a node’s relative influence is determined by:

1. The number of hbars the node controls and stakes towards consensus
2. The number of hbars that other participants proxy stake to that node towards consensus
3. The total number of hbars

Concretely, we use stake to weight influence in the following ways:

1. For a given event, we say the timestamp will be the stake-weighted median of the times that active members of the community received it. The different times that the members of that set first learned of that event are put in order from earliest to latest, and the time at the 50th percentile of stake will be the consensus timestamp
2. We determine ‘active’ by having nodes vote on whether a given event is ‘famous’ - these votes are weighted by the stake of each node. The nodes that created such famous events are considered to be active
3. When the counted stake for Y (or alternatively N) on the fame of a given event exceeds 2/3 of the total stake, the election is over and the decision is final

Note that no calculation uses the total number of nodes - that value is not relevant to consensus in Hedera’s implementation of hashgraph. The hashgraph algorithm itself allows other staking models, such as giving each node exactly one unit of stake. That simple staking model would then require knowing the number of nodes. But Hedera doesn’t do that. Hedera uses the full hashgraph algorithm, where different nodes can have different stake. So it needs to keep track of the total stake, not the total number of nodes.

So, at a given moment in time, in order to calculate influence (and so consensus) all nodes need to know

1. The stake of all nodes
2. The total stake

The total stake is fixed for Hedera at 50 billion hbars.

The stake of a given Hedera node will be the sum of:

1. The hbars in the node’s staked account
2. The hbars in the accounts that have been proxy staked to that node

As there is no bonding in Hedera, #1 will change as the node spends hbars from that account, or receives hbars into that account - from both node payments and unrelated transactions.

Similarly, #2 will change as hbars move in and out of the proxy staked accounts, or as new proxy accounts are added, or existing proxying accounts decide to switch to another node.

Ultimately then, the influence of a node will depend on its stake, and its stake is determined by the amount of hbars in a set of cryptocurrency accounts. The burden on Hedera nodes for calculating consensus is therefore, at any moment in time, to know how many hbars are in all staked accounts (unstaked accounts are immaterial).

This is, of course, the exact same burden for a cryptocurrency. The fundamental value proposition of any cryptocurrency (including hbars) is to prevent someone spending coins they don’t own, such as spending 10 hbars when they only have 5 in their account. To make this guarantee, Hedera ensures that all nodes will agree on how many hbars are in every account at any moment in time. Any DLT that cannot make this guarantee is not a viable cryptocurrency.

It is the fact that hashgraph delivers a total order for transactions (i.e. all nodes agree on the sequence of all transactions) that allows nodes to agree on the exact stake of all nodes at a given moment in time - and so be resilient to those staked amounts changing. Consequently, even transactions that change a node’s stake do not prevent the community from agreeing on stake, and so consensus. As an example, if node Alice has 10 hbars in her account but spends 2 of them on a purchase, the network will grant to her 10 hbars worth of influence up to the point when the purchase transaction is recorded, and 8 hbars worth afterwards. As all nodes will agree on the order of her 2 hbar transaction relative to all other transactions, they will agree on her new amount of stake, and when it takes effect, and so her influence towards the consensus calculation of those later transactions. In practice, as an optimization, Hedera nodes will take a snapshot of hbar balances (and so node stake) every 24 hours and use those values for the following 24 hours. But it would be equally resilient for nodes to constantly adjust the stake calculation to reflect real-time account balance flux. 

Conclusion

Hedera’s use of stake-weighted hashgraph is similar to other proof-of-stake ledgers, except without the loss of liquidity through bonding, or risk of loss of stake typical in most other systems. In Hedera’s deployment of hashgraph, all nodes must be able to calculate the influence of all other nodes. To do so they require only the stake any particular node has (both owned and proxied to it) and the total amount of issued hbars. The first is available from the associated cryptocurrency balances and the second a well-known and fixed value. Neither term in the calculation is impacted by other nodes joining or leaving the network, and so the stake calculations (and the consensus algorithm itself) are consequently resilient to any such flux.