Confirmation rates in the Tangle
The full article was originally published by Alon Gal on Medium. Read the full article here.
The IOTA consensus mechanism is based on a weighted random walk. Using this tip selection mechanism, large branches of the Tangle become larger and smaller ones become smaller, until they get abandoned. The intuition is quite similar to blockchains: while a blockchain builds upon the longest chain, the Tangle builds upon the heaviest branch.
Except it doesn’t, not quite. Instead of always going towards the heaviest branch, some randomness is allowed in the walk, to make sure that lighter branches are occasionally approved. The motivation for this is maintaining a high transaction rate: if only the heaviest branch are approved, the result will be a thin chain of approved transactions, with most others getting left behind. For an illustration of this, try running the visual simulation with a large value of α, and see that most transactions are not confirmed. Remember that a small α value means a lot of randomness, while a large value implies a deterministic walk towards the heaviest branch.
It should be emphasized that a transaction getting left behind does not mean that any money is lost. It only means that the transaction has not been confirmed, and must be re-attached or promoted. The net effect is mostly a slowdown in confirmation times.
So how high should α be? That is exactly the question that Bartosz Kusmierz, an IOTA Foundation researcher, is working on answering. The goal is a quantitative estimate of how many transactions get left behind, for a given α. Given that, it is possible to set an upper bound on α, beyond which an unacceptable percent of transactions in the network are lost.
To find the probability of getting left behind, Bartosz ran simulations of the Tangle, and measured what fraction of transactions were confirmed at various time points. Notice that confirmation rate and the probability of getting left behind are closely related: the two quantities always sum to 100%. This is because every transaction is eventually either confirmed or left behind.
To define whether a transaction is confirmed, the following heuristic is used: run the tip selection algorithm once, with a very large α. This is equivalent to always walking towards the heaviest branch. Once you reach a tip, any transaction it approves is considered confirmed, and all others are left behind. While this definition is not strictly identical to the concept of confirmation confidence, they do converge when simulating long time periods, and it is simpler to analyze since it gives a yes/no answer.
You can see some of the results in the following plot:
It is not surprising to see that large α values imply a high chance of being left behind, which corresponds to a low confirmation rate. However, it is interesting to see how the rate of transactions affects this dynamic; as the transaction rate goes higher, α must be steadily decreased in order to keep a constant confirmation rate.
These results are extremely useful to have, since they provide a good measure of what α values are reasonable, and which are too high, for a given transaction rate. For example, if for achieving a confirmation rate of at least 80%, the value of α should be set according to the purple curve, or below it.
Given that an upper bound has been established, the natural next question is what the lower bound should be. Generally, the lower α is, the more vulnerable the network is to double spends and lazy behavior. To understand what the lower bound should be, more studies of attacks and misbehaviors must be performed. These will be shared with the community as soon as concrete results are available.
As always, your comments and questions are very welcome, either here or in our Discord (I’m @alongal#3938, and Bartosz is @bartkusmierz#7311).
You can find Bartosz’s full report here.