This blog post was jointly written by Dr. Leemon Baird (Co-founder & Chief Scientist), Atul Luykx (Head of Cryptography), and Paul Madsen (Technical Lead).
Many applications require knowing either the time at which a business transaction happened (for instance, submitting federal taxes before the deadline) or its order relative to other transactions (for instance, competing bids in markets or auctions) or both. Time, or order, will generally be used to assess validity of a transaction or priority relative to other transactions.
Consider an online auction where someone is selling 30 shares of a stock. Alice, Bob, and Carol each submit a bid to buy 20, all at the same price. A fair outcome would be to give the sale to the first bidder. They buy 20, leaving 10, which are then sold to the second bidder. The third bidder would be too late, and would not receive any. As the order has financial consequences, it is important to be fair in determining the order of the bids.
If the bids are all submitted to a single trusted computer, then fair ordering is easy to do. The computer records the time that it receives each bid and orders them by when they were received. As the computer is trusted, it will not manipulate the order. This is fair.
But maybe there is no single computer that we trust. Or we don’t want to be dependent on the honesty of a single party. In that case, we can use multiple computers, and should consider how to determine a fair order for the bids when multiple computers are involved.
What would a fair timestamp and order for bids (or more generally arbitrary transactions) be when multiple computers are involved and some of them might be dishonest?
For a single computer, we said that the fair timestamp and order was determined by when that single computer received the bids. We could say the same for multiple computers – the true timestamp for each bid will be the time the network as a whole receives them, and the true order determined by sorting by those timestamps.
But some of the computers may be dishonest and lie. Or the local clocks of the computers may not be perfectly accurate. So we cannot guarantee a “true” result. Instead, the result should be “fair” in the sense that all the computers have an equal influence in determining the outcome, and a small number of dishonest or faulty computers cannot pull the result too far from the true result.
But what is the definition of “reaching the network”? And what is “not too far”?
We could say that a transaction “reaches the network” when it reaches any computer. But that has problems. That computer might crash before passing it on to anyone else. Or it might be disconnected from the network and unable to pass it on. It seems unreasonable to assign a transaction as coming first because it reached a single computer, if almost none of the other computers ever received it.
Or we could say that a transaction “reaches the network” when it reaches all computers. But if even a single computer were to crash, then no transaction would ever “reach the network”, and we would never be able to establish timestamps or order for them.
It would be more reasonable to say a transaction “reaches the network” when it has reached most of the computers. A few crashed computers won’t prevent this.
This timestamp for a transaction could be determined by taking the time at which the transaction reached each computer, sorting the list of times, and taking the one in the middle, that is, the median. If some of the computers have crashed, the calculation can still proceed.
But maybe some computers are malicious and lie about when they received the transaction. Maybe they lie by a huge amount, claiming to have received the transaction a million years in the past, or a million years in the future. Would they have a large effect on this timestamp? No.
If the transaction reached the computers by a gossip protocol, then it would reach each of them at times following something similar to a bell-shaped curve. Most of the computers would have received it at about the same time, with a few being earlier, and a few being later. The median time will be somewhere in that dense mass of roughly equal times. This is the timestamp with half of them before it and half after it. The median time is also the time at which the message first reached most of the computers. So the median time is a reasonable definition of when the message “reached the network”.
This is represented in the following diagrams. The graphs depict a distribution of timestamps that 1000 computers have assigned to a transaction. The x-axis is time, and the y-axis is number of computers. The blue tick marks along the horizontal axis are individual timestamps. The message reached most computers at around the same time, with those timestamps clustered in the middle, and a few spread out before and after it. The black dashed line shows the median of all the timestamps.
If honest computers report the time they received it, then the distribution would be the above graph. But what if one of the computers lies? The graph below represents the case of a single dishonest computer that is maliciously claiming a time far in the future – the red tick on the far right. The calculated median is shifted only slightly to the future, from one of the honest times in the cluster to another one adjacent to it. A single malicious time would usually have very little effect. The median is great at excluding outliers. So a malicious computer has only a small effect on the calculated median timestamp. The timestamp is fair.
That was for a single bad actor out of the 1000 computers. If 10% of the computers collude and all claim that same late time received, the effect on the median is still very slight. The resulting consensus timestamp is the red dashed line. It is very slightly to the right of the black dashed line, which would have been the consensus, if they had been honest. In this picture, the red and black are almost on top of each other.
The diagram below gives the results when almost one third of the computers give false times that are far in the future. They should have an effect, because every vote should count. But the effect is limited. The consensus timestamp is still within the dense cluster of honest times in the middle. The honest computers have timestamps all clustered around the black dashed line, and the red dashed line is still within that cluster. So even if all the malicious computers report unreasonable times that are millions of years in the past or future, the final timestamp will still be reasonable – as represented by the influenced red dashed line still being within the central peak of the distribution. The timestamp is still fair.
Of course, if the attackers control 51% of the vote, then they should be allowed to move the consensus timestamp extremely far. After all, if a country holds a fair election, then the majority should decide. But what if the attackers have only 49% of the vote? They should have about half the influence, so they should be able to move the consensus a large distance. But they are in the minority, so there should be a limit on how far they should be able to move it. In this case, the results look like this:
The 49% dishonest voters can drag the timestamp to the right. But they are limited. The consensus timestamp can’t be forced to be a million years in the future. It is guaranteed to be a time that came from an honest voter, or was between the times from two honest voters. So the 49% dishonest voters are still constrained by the boundaries of the 51% that are honest.
If the order is then calculated by sorting by the timestamps, then fair timestamps yield an order that is intuitively fair. The order can only change when two true timestamps are close enough that the malicious votes can swap them using only their fair amount of weight. The order will not be unreasonably affected by the malicious computers because they cannot have an unreasonable influence on the timestamps and so the order will be one that reflects those reasonable timestamps. The order is fair.
Of course, in any election that is almost a tie, a single person changing their vote can decide the outcome. That isn’t unfair. That is the way elections should work. So if two transactions have median timestamps that are almost exactly equal, then a single voter should be able to affect their order, by affecting their timestamps. But it would be unfair if one voter had more influence than others. So if two transactions have median timestamps far enough apart that a single voter can’t change the order of the timestamps, then the single voter shouldn’t be able to change their order. That is what the median achieves.
The above was for 1000 computers for better illustration. But would the results be similar for a smaller number, such as 27 computers? Yes, they are very similar:
So the ordering can be considered fair if it is derived from consensus timestamps that are fair. And consensus timestamps can be fair if they represent the median of the voted times.
The hashgraph consensus algorithm determines consensus timestamps and order for transactions in this manner.
There are other ways to calculate an order of transactions. However, they tend to have issues with fairness.
The simplest is to pick a leader who will be temporarily empowered with the authority to pick a set of transactions and how they should be ordered. As the leader at any moment in time could manipulate the order they assign, this is clearly not fair.
Another alternative is to skip the calculation of the timestamps and just calculate the order directly. Some applications may not require that each transaction receive a timestamp and so just determining the order might be acceptable. Is there a way to find the order by itself, and still be “fair” by some reasonable definition?
One possible mechanism for ordering transactions is to consider transactions in pairs, and allow each computer to vote on which transaction within that pair was received first. For each pair of transactions, the votes would be collected and the transaction that received the most ‘first’ votes would be deemed to have come before the other transaction in the pair.
This sounds intuitively appealing, because it discards a great deal of information, and keeps only the results of pairwise comparisons. But it has some fundamental problems. It is possible for the pairwise votes to give incompatible results, that aren’t consistent with any possible order at all. It is also possible for honest votes to be completely consistent with a single order, but then just a single malicious voter can use a dishonest vote to make them inconsistent. The following walks through the difficulties with this approach and why an order based on fair timestamps might be considered more “fair”.
Returning to the initial example of Alice, Bob, and Carol sending bids - each computer would record the order in which it received the three bids. And then they could all vote on three pairwise questions: who came first, Alice’s transaction or Bob’s? Bob’s or Carol’s? Alice’s or Carol’s?
It might seem that we could take the majority from each of those votes, and that would give us a rational order. But it turns out that sometimes that is impossible.
Suppose 3 computers, 1, 2, and 3, each received bids from Alice, Bob, and Carol in the following order:
1: Alice, Bob, Carol
2: Bob, Carol, Alice
3: Carol, Alice, Bob
If we then asked them to vote on who came first out of each pair, they would vote like this:
The winner of each vote is clear. The community agrees by majority vote that the consensus order should have Alice before Bob, and Bob before Carol, and Carol before Alice. But that’s impossible! There is no way to make an order that will agree with all the individual pairwise votes. Any possible order will violate a clear majority vote of the community on one of the pairwise orders.
This is known as Condorcet’s Paradox. If we look at pairwise preferences, then we can get almost everyone to agree on a series of preferences that are impossible to achieve. The preferences aren’t “transitive”. And those majority votes can each be a very strong majority. For example, if computers 1 to 5 are voting for bids received from Alice through Ed, the results could be:
1: Alice, Bob, Carol, Dave, Ed
2: Bob, Carol, Dave, Ed, Alice
3: Carol, Dave, Ed, Alice, Bob
4: Dave, Ed, Alice, Bob, Carol
5: Ed, Alice, Bob, Carol, Dave
In this case, every gray election is almost unanimous: only a single vote disagrees with the majority. And the majority says that Alice’s bid arrived before Bob, who was before Carol, who was before Dave, who was before Ed, who was before Alice. As in the previous example, those are contradictory. That cycle is impossible.
Of course, we won’t always have paradoxes like that. Sometimes, we will see a nice, clear consensus on an order. For example, this might be the order in which each computer receives each bid:
3: Alice, Bob, Carol, Dave, Ed
5: Alice, Bob, Carol, Dave, Ed
This is very nice. The pairwise vote majorities actually agree on this order:
Alice, Bob, Carol, Dave, Ed
For every pair of names, there is a majority of votes for the names being in that order. So we might be tempted to say that, at least in this special case, we could get away with just using pairwise votes, and demanding that our order satisfy them.
But there’s still a problem. That was just the order that the computers actually received the bids. What happens if computer number 5 lies about the order it received them, and claims that Alice was last rather than first? So just a single computer lies about a single bid. Then the votes would be:
5: Bob, Carol, Dave, Ed, Alice
Now we’re back to the original problem! The vote for Alice vs Ed now shows the majority voting for Ed and, so again, the majority vote of the community is an impossible requirement to satisfy.
And so this pairwise voting model is fragile. A single dishonest computer can trigger the paradox, even in this easy case where an honest vote would have caused all the pairwise votes majorities to be consistent with a single order. The paradox doesn’t just lead to a different consensus, it prevents establishment of any order for all transactions that is consistent with all the majority votes.
This is different from the median-timestamp model discussed above. In it, the order is determined based on the consensus timestamps of individual transactions and these consensus timestamps are calculated as the medians of the times that the computers received those transactions. A dishonest computer has a limited ability to influence the timestamp for a given transaction. This limits the influence a malicious computer has to affect the relative order of two transactions. The dishonest computer could lie and say it received Alice’s transaction much later, but the nature of the median calculation for both transactions makes it more difficult to swap their order than in the pairwise voting model. It has only a reasonable amount of influence on the timestamps and it is able to change the order only when that influence is enough to make one timestamp move to come before the other one. And in that case, it should have the ability to change the order. For the same reason that democracy requires that any single voter can decide the election when the rest of the voters are tied. A fair election isn’t one where no one can influence the outcome. A fair election is one where everyone has an equal weight in influencing the outcome.
It is important to use a median rather than an average. If the consensus timestamp were an average of all the received times, then a single computer could lie and claim to have received a given transaction a million years in the future or the past. And the influence on the average would be enormous. But with a median, the lying computer will have only a reasonable effect on the fair timestamps, in the sense that a small number of outliers have little effect, and even if almost half of the timestamps are dishonest, then it is still guaranteed that the consensus timestamp will be the time received from an honest computer, or between the times from two honest computers. And the fair ordering will reflect these fair timestamps.
Even in a world populated by almost a third liars, this is a robust and fair way to assess timestamps and order of transactions.
The above graphs were generated by a simulation. At the start of the simulation, only a single computer has the message. Then every computer chooses another at random and starts a sync with it. Each sync lasts for a random amount of time. When it is finished, if either computer had the message at the start of the sync, then both have it at the end. If this is the first time one of them received it, then the time is recorded. The computer then initiates another sync with a random computer. So at any given time, a computer is involved in two syncs, with the computer it chose, and with the one that chose it.
The random duration of each sync is chosen as 1 unit plus a random number chosen from an exponential distribution with a mean of 1 unit. So syncs always last for at least 1 unit of time, are on average 2 units of time, and only rarely go far longer than that. The recorded times are the short blue lines in the figure. And that distribution (a sum of delta functions) is then smoothed by convolution with a gaussian to give the blue curve.