MODULE 4TIP SELECTION ALGORITHM

The tip selection algorithm is the method by which transactions are selected for approval. A good algorithm allows the Tangle to grow in a stable and secure way.

To attach a new transaction to the Tangle, the algorithm needs to select and approve two previous transactions — preferably tips. This approval mechanism represents “belief” in the Tangle: If transaction y approves transaction x, this implies that y believes transaction x is valid and that its entire history is also valid.

In the past, we have used a biased random walk as our tip selection algorithm, as this led not only to a healthy Tangle structure but also allowed us to identify the heaviest, and therefore preferred part of the Tangle. While this mechanism was essential for reaching consensus, it also showed properties that were less desirable:

  • Honest transactions could be left behind if they did not accumulate enough weight. This resulted in an increased need for promotions and reattachments (even in the absence of attacks), which in turn significantly lowered the reliability of transactions.
  • Attackers could try to “game” the random walk into entering malicious structures like parasitic chains, or prevent the network from reaching consensus by carrying out splitting attacks.
  • Calculating the cumulative weights of transactions is relatively expensive and poses a problem for the scalability of the protocol, especially in high throughput scenarios.

By adding a voting layer to identify the preferred part of the tangle (as an additional module), we are able to:

  • Resolve conflicts much faster, and therefore lower the chance of a transaction accidentally attaching to the wrong part of the Tangle.
  • Use different tip selection mechanisms that are no longer based on cumulative weight, and have a lower chance of leaving valid transactions behind.

This will increase the reliability of transactions in the IOTA network and significantly reduce the need for reattachments and promotions. It will also make the process of selecting tips much cheaper and faster.

TipA transaction that has not yet been approved.
HistoryThe list of transactions directly or indirectly approved by a given transaction.
PromotionAttaching empty transactions that reference both the original transaction and newer parts of the Tangle in an attempt to get “picked up” by random walks.
ReattachmentResending a transaction by redoing tip selection and referencing newer tips by redoing PoW.