Permission Problem

You don't have permission to do that.

What 'virtual voting' is and how hashgraph uses it to determine consensus order for transactions

What is virtual voting?

Hashgraph relies on a voting mechanism to determine a consensus order for transactions. In this article I will cover how hashgraph uses voting - specifically:

  • What is being voted on?

  • Who casts the votes?

  • How votes are counted?

  • How is the result of the election used?



In a previous article, I described the gossip about gossip mechanism that hashgraph follows.  Gossip about gossip allows all nodes in a hashgraph network to build up a consistent representation of the history (the hashgraph) of how those nodes communicate amongst themselves about transactions.

But that of course is not what we are trying to achieve - the ultimate goal is to allow those same nodes to come to a consensus on the timestamps and order of those transactions. The hashgraph algorithm accomplishes this by having all nodes examine their own local copy of the hashgraph and, indirectly, vote on the consensus timestamps to be assigned to those transactions, and so their order.

Let’s set the scene.

We have n nodes that have gossiped a set of transactions (actually a container for transactions called an ‘event’, analogous to blocks in blockchain) amongst each other. Additionally, they have gossiped about that gossip - allowing all to have a consistent record of what nodes know about those transactions and when they first learned (received the containing event) of them. Clearly, due to the nature of gossip and network latency, different nodes will receive a given event at different times. If Alice creates an event and happens to send it first to Bob, then Bob will receive it earlier than any other node. If Zoe happens to be the last node to hear of that event, she will record a later time than Bob (though likely not significantly so given how fast gossip spreads out).

Once all nodes have received a given event, and have, through the gossip about gossip, built up a hashgraph of the history of when all the other nodes also received that event, we can proceed with assigning that event a timestamp.

Hashgraph is defined such that the consensus timestamp assigned to an event is the median timestamp of when the actively participating nodes first received it, meaning that you simply put all those times in order from earliest to latest and take the middle value. In the above example, the time at which Bob receives Alice’s event will be towards the earlier end of the list (actually Alice’s own time will likely be the first), and Zoe’s the latest. The consensus timestamp given that event will be somewhere between the two. This is a good timestamp. Because the gossip protocol happens exponentially fast, once event X had reached half the active nodes, it would have taken only about one more sync before all the active nodes would have it. And because it's the median of many different timestamps, it would be robust, even if a few of the clocks were a little off, or if a few of the nodes maliciously gave times that were far off.

We would still need to consider a few rare cases like how to break ties.  But usually, they are simply sorted by their consensus timestamp. Then the official consensus order for the transactions is simply the consensus order for the events that contain those transactions.

Note that there was no mention of voting in the above. We simply put a number of timestamps in a list and took the median. Where is the voting?

I wrote ‘median timestamp of when the actively participating nodes first received it’ in the above paragraph. But what does ‘actively participating’ mean? Clearly only if a node is included in that set will it be able to influence the timestamp assigned to an event and so the transactions within. So how to pick these nodes?

Instead of directly voting on the timestamp for a transaction, we will vote on who gets to contribute to the determination of that timestamp.

The voting is virtual, meaning that no ballot messages or receipts flow across the network. Instead, all nodes simply look at their local copy of the hashgraph and examine its structure. Critically, a node is able to look at its own hashgraph and place themselves ‘in the shoes’ of another node and essentially vote as if they were that other node.

The selection of nodes is indirect, ie the voting process does not directly ‘elect’ nodes, but rather we elect events, and it is the nodes that originally created those events that are allowed to contribute to the consensus timestamp for an event. Those events that are elected (using criteria to be explained) are said to be famous. In fact, rather than determining the fame of all events, the vote will be on the fame only of a smaller set of special events called witnesses. A witness is defined to be the first event created by each node in a given round, where a round is a slice of time into which events can be sorted.

Similarly, it is not the nodes (the actual software clients) that vote, but rather witnesses that vote, ie individual witnesses vote on whether earlier witnesses are famous or not. In the first round of voting, a witness votes that an earlier witness is famous if there is a path through the hashgraph from itself to that earlier witness and it knows of no forks by the node that created it. This criteria is called ‘seeing’, ie a witness votes that an earlier witness is famous if it can ‘see’ it, if it is an ancestor. A typical round is long enough for a message to spread from one node to most of the others, and then to spread from each of them to most of the others. So such a path usually exists, and all the witnesses usually start their election with a YES vote.

Intuitively, if there is a witness in a round, and almost everyone saw that witness by the next round, then it should be decided that it is famous. If almost no one saw it in the next round, then it should not be decided as famous.

So far we have had witnesses voting on the fame of earlier witnesses. Now we have to count those votes.

Just like it was witnesses casting votes, it will be witnesses collecting those votes. A witness collects the vote of an witness if  there is a path through the hashgraph from itself to that earlier witness that goes through the hashgraph via a super-majority (eg 2n/3) of the nodes. This more rigorous criteria is called ‘strongly seeing’, ie a witness collects the vote of an earlier witness on the fame of an even earlier witness if it can ‘strongly see’ it.

The witnesses that collect the votes of the earlier witnesses count those votes to see if there is a super-majority of either YES or NO votes. If a witness is able to count that number of votes, then it decides accordingly and  the election is over. For instance, if a witness collects over 2n/3 YES votes (which necessarily means that it can strongly-see those voters) then the election is decided as YES and no other witnesses need to collect votes. If it turns out that no witnesses can collect a super-majority of votes (either YES or NO), then the witnesses collecting the votes will themselves vote instead (based on the votes they collected) and it will be witnesses in the next round that will decide (or vote if unable to decide and we would look to the next round for a decision and so on.)

In normal operation, almost every witness will strongly see every witness from the previous round. So they will typically all be able to reach the required super-majority, and count the votes the same way, and come to the same conclusion on the fame. Consequently, in normal operation, the elections are decided right away, without needing to wait for subsequent rounds of voting. This is a nice property. Byzantine voting algorithms typically are fast on average when they are running any election for a YES/NO question. But they are even faster if the initial votes are almost unanimous. And in the hashgraph, the initial votes are usually a unanimous YES in the first round. So every witness will be famous, and it will be decided very quickly. In the extremely unlikely event that no decision is possible for 10 rounds, we essentially flip a coin between YES or NO to avoid a stalemate.

Once we have determined which are the famous witnesses in a round, we are almost done (in assigning a consensus timestamp to earlier events). We look at those earlier events (not just witnesses now) and determine in what round are those events ‘received’. The round received of an event is the first round in which all the famous witnesses in that round can see it. Once we determine the round received for an event, the calculation of the consensus timestamp for that event is straightforward. For each of the famous witnesses , we determine what was the earliest time that the corresponding nodes had an event that could see the event in question. We place all those times in a list from earliest to latest, and take the median value. If two events end up with the same value for the consensus timestamp, there are ways to break the tie.

So the overall consensus algorithm is simple. Consensus order comes from sorting by the consensus timestamp. The consensus timestamp comes from taking the median time at which active nodes received the event. The active nodes are those that have famous witnesses in that round. The witnesses are famous if they are decided famous in an election performed entirely by virtual voting, by looking at the local copy of the hashgraph. The "voting" is done by the witnesses in the graph, with a witness in one round voting to match the majority of the votes from the previous round. The election starts with every witness voting YES on the fame of witness W if it has W as an ancestor.

Of course, if we want to have strong mathematical guarantees, such as Asynchronous Byzantine Fault Tolerance, then the consensus algorithm needs to have a few details that weren't described above (we hinted at them with the mention of flipping a coin and tie breaking). But they don't really have an effect in normal operation. They are only there to guarantee that everything continues working in the face of unreasonably-powerful attacks.


Comments

Sign In or Register to comment.