The tip selection algorithm selects the attachment points for new messages entering the network.
In the early IOTA network, the biased random walk algorithm was used as it leads not only to a healthy Tangle structure but it also allowed us to identify the heaviest, and therefore preferred, part of the Tangle for attachment. Aside from those qualities, it also showed properties that were less desirable:
- Honest transactions could be left behind if they did not accumulate enough weight.
- Attackers could perform “Confirmation Attacks”, purposely creating malicious structures that would entice the random walk into it, like parasitic chains. Alternatively, an attacker could spam conflicting messages that would take a long time to be abandoned and would drastically drop the confirmation rate.
- Calculating the cumulative weights of transactions is computationally expensive, especially in high throughput scenarios.
Such problems led us to use voting mechanisms in Nectar. We had to make a decision on whether a message would be healthy before further using it to grow the Tangle.
This approach allowed us to have the tip selection play a different role than in pre-Coordicide IOTA: its purpose would only be to allow the Tangle to grow in a stable and secure way, with quick approval and finality times. We separated the tip selection process from the consensus mechanism.
In Nectar’s tip selection, the algorithm selects and approves between two and eight previous messages among a list of tips. This approval mechanism represents “belief” in the Tangle: If message y approves message x, this implies that y believes that x is valid and that its entire history is also valid.
Nectar’s tip selection algorithm is Restricted Uniform Random Tip Selection (RURTS), which selects with uniform probability among the list of eligible tips. The variation on the number of approvals (two to eight) counteracts spam during low-congestion periods: A higher number of approvals prevents a spammer’s messages from widening the Tangle, ensuring it grows in a healthy way. The standard is to use two approvals during uncongested periods.
We further improve the algorithm by introducing approval switches, which separate approvals into two categories: strong and weak. Strong approvals require a healthy past. Weak approvals emulate the good properties of the “White Flag Approach” from IOTA 1.5: it means we approve the content of the message without approving its past necessarily, allowing such message to participate in the Tangle without creating unmergeable branches.
This new system 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.