IOTA: Confirmation rates in the Tangle

  • Monday, 16 April 2018 17:23
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. You can see his full report here.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.Illustration of how confirmed transactions are measured. The large red circle is the tip chosen by the large α walk, and the red circles are considered confirmed.You can see some of the results in the following plot:The probability of a transaction getting left behind, for various values of α and λ. λ is the rate of transactions, measured in units of transactions per h. You can see this article for more details, but essentially h is the average time it takes to perform proof of work. Assuming it takes one minute to perform PoW (which is more or less the case), than λ is in transactions per minute.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.Confirmation rates in the Tangle was originally published in IOTA on Medium, where people are continuing the conversation by highlighting and responding to this story.

Additional Info

Leave a comment

Make sure you enter all the required information, indicated by an asterisk (*). HTML code is not allowed.

Disclaimer: As a news and information platform, also aggregate headlines from other sites, and republish small text snippets and images. We always link to original content on other sites, and thus follow a 'Fair Use' policy. For further content, we take great care to only publish original material, but since part of the content is user generated, we cannot guarantee this 100%. If you believe we violate this policy in any particular case, please contact us and we'll take appropriate action immediately.

Our main goal is to make crypto grow by making news and information more accessible for the masses.