IOTA New tip selection algorithm

IRI 1.5.0 — New tip selection algorithm and other improvements
We are constantly working on improving the IOTA reference implementation (IRI) and moving it closer to the IOTA white paper. This requires a lot of planning, research, development, and testing of any changes we make. The IRI team at IOTA has been hard at work to improve the current tip selection algorithm. We are happy to introduce a complete rewrite of the tip selection algorithm that is part of IRI version 1.5.0.

Want to learn more about the Tangle? See The Tangle: an Illustrated Introduction.

The new tip selection algorithm introduced in IRI 1.5.0 is changing quite a few things. This post will briefly introduce the changes, but if you want to look over the new implementation in detail, see our detailed post.

Cumulative weights
In the previous versions of IRI, we used a simplified weight calculation algorithm for each of the transactions. Depending on the Tangle topology, the previous approach could lead to results not very representative of the actual weight of the transactions in the Tangle. This has now changed to what is proposed in the Tangle white paper. Actual values representing the weight of each transaction based on the amount of transactions that directly and indirectly reference it are used instead. While the new approach is computationally more expensive, we’ve developed an algorithm that allows us to do the computation in a memory efficient way.

Fixed subgraph
Weight calculation is an expensive process, to address this, we are now using a fixed portion of the graph, called subgraph, on which we perform the calculation. The subgraph is formed from a portion of the graph between an older milestone and the current tips. How many milestones back the subgraph goes is defined by a user-defined ‘depth’ value up to a pre-defined ‘maxDepth’ value. The previous approach also had other drawbacks, like the theoretical chance that new transactions would be added to the calculation faster than the walker is able to move. This will not happen with a fixed subgraph.

Ignoring invalid transactions
The previous implementation of IRI stopped the walker when it encountered an invalid transaction and returned the last valid transaction up to that point. The walker also stopped at this point. This allowed for the formation of the infamous blowballs. We’ve now changed this behavior so that the walker simply ignores the invalid transaction, removes it from the list of approvers, and continues the walk on a different path. This makes the Tangle safer. With the previous approach, adversaries could have taken advantage of the creation of blowballs to affect the overall confirmation rate.

Blowballs occur when a large number of transactions reference a single specific transaction, which typically turns out to be a milestone. This prevents the Tangle from growing organically, by “trapping” incoming transactions inside of the blowball. [Image from IOTA StackExchange]

New transition function
We have changed the transition function in IRI to an exponential function. We’ve done research and simulations on the exponential version of the function and we are confident it represents the behavior that we want in the transition function. The function also implements an ‘alpha’ parameter, which gives us control over the randomness of the walk. We can use the parameter to tweak the function as necessary to achieve the best results in different parts of the walk.

Other improvements
A very important part of the effort to change the tip selection algorithm was also documenting how the algorithm works. As mentioned earlier, please see our detailed post.

Last but not least, we’ve also worked hard on improving the readability and testability of the code. This will make maintaining the code and making improvements to IRI simpler for us. We also hope it will make it easier for you, our community members, to contribute directly to the IRI project.

Free coins?
If you are making use of our Devnet (previously testnet), you will be glad to hear that we’ve now made getting free test coins super simple. We’ve created a faucet website where you can request coins. Just provide your IOTA address and off you go!

Please provide any feedback on the faucet website on the #testnet Discord channel.

Deprecating testnet URLs
Please note that testnet URLs are now deprecated. We will be removing all testnet.iota.org URLs in the future. Instead, use devnet.iota.org.

Release Notes
A full set of release notes will be available on the release page when the new version is made available.

This version includes the following:

Rework of the Tip Selection algorithm (#778)
Validate the alpha value (#817)
TipSelection: update API reference (#773)
Inserted check for number of available processors. (#758)
Improved Docker support (#744)
Faster PearlDiver (PoW) (#733)
Kerl hashing speed improvement (#628)
Logging routing rework (#727)
Minor changes and fixes

Fixed attachmentTimestampUpperBound value (#777)
Fixed getBalances tips parameter parsing (#776)
Added hash to tx_trytes ZMQ topic (#739)
Thanks to Alon Elmaliah and Alon Gal.

Thanks to Alon Elmaliah.