Untangling IOTA – Tip Selection Part 3 – Combating Lazy Tip

, ,
Combating Tip Selection

Welcome back to our discussion of IOTA and tip selection within the IOTA Tangle!  In the first two parts about Tip Selection, we discussed two methods that are…well, less than optimal for the network to operate effectively at scale.  The first method we looked at was the uniform random tip selection (which can also be referred to as the “random walk”).  Next, we looked at the unweighted random walk, taking another step (pun intended) closer to the optimal solution but not quite making it there.  This post is going to cover the weighted random walk and why it is the best way to perform tip selection within the tangle. 

What is IOTA Tip Selection

Let’s take a second to recap what we’ve learned so far.  If you haven’t read what we discussed on tip selection yet, feel free to pause and check out Part 1 and Part 2 to get up to speed with some of what’s going on.  Remember that a tip is simply an unapproved transaction on the tangle.  While IOTA is technically free to use, there’s still no free lunch here:  before a transaction can be finalized in the network, the node placing the transaction must approve two prior transactions (those which have occurred at some point in the past). 

But which transactions should the node approve? 

This has been the basis of our entire discussion as some methods of choosing tips within the network could lead to delays or instability.  Part 1 showed us that randomly choosing any tip on the network could be highly ineffective in allowing the tangle to converge and remain cohesive.  Part 2 introduced the concept of a walk along the tangle – this is quite necessary in producing an effective tangle.  Nevertheless, without a weighting in the paths taken by the node performing an approval, the tangle could become lop-sided with some transactions having many approvals and others having little to no approvals.  What would happen if we extended this concept to include weighting?

Weighted Random Walk

Excellent question!  We already learned about the concept of a random walk in the last post, but what does it mean to add weighting to a random walk?  Before we look at specifics about IOTA, let’s probe this question in a very generic sense.  Pretend that we have three bags of groceries that we need to carry a few blocks back to our apartment.  As the cashier rang up the items, we placed them in the bags we brought.  As one bag got more and more full, we switched to a different bag.  Near the end, we started finding empty spaces in each of the bags that we could stash the last remaining small items. 

As commonplace as it may seem, this is the same concept as performing a weighted selection of which bag to fill.  One bag fills up, so its weight (both logical and physical) increases.  We choose a different bag eventually until the two bags are similar in weight and then proceed to the third bag.  At the end, we examine the appropriateness of each bag for each item to properly store. 

Weighted Selection

While this demonstration wasn’t random in nature, it was weighted. We didn’t choose bag 1 and put our entire load of groceries in it, carrying the other two empty bags home. Instead, there was a rationale behind which bag we chose based on how much it already had within it. Applying this concept to IOTA, as a walk is performed from the genesis transaction out to the tips of the tangle, there is a weighted approach that can be taken.  As one path gets used more and more (i.e., more groceries in the bag), it will have more of a chance of being chosen (which is the reverse of the bag illustration but stick with us). 

It’s important to remember that a different path still can be chosen – this is, in fact, a random selection – but it’s likelihood of being chosen continues to decrease the fewer times it is traversed relative to other paths. 

Lazy Tip

Let’s step back for a second and take another look at why this is so important.  The concept of a lazy tip is of interest.  A lazy tip is one that, instead of choosing to approve transactions near in time to itself, decides to just choose any old transaction from the network at some point in the past.  It’s referred to as lazy because it doesn’t care about what’s going on right now in the network; it chooses the easy way out by quickly finding two transactions, approving them, and moving about its business.  This doesn’t help the network out as more transactions continually enter the tangle and don’t receive proper verification (the more nodes that approve a transaction lend more credence to the transaction and increase the robustness of the tangle). 

Since we want to discourage this behavior, it’s important to find a method to bias the random walk.  The network designers formulated a method to discourage lazy actors on the network by introducing a cumulative weight to each hop in the walk. 

Cumulative Weight

A transaction that has been approved by more nodes on the network is given a higher weight and will be (probabilistically speaking) more likely to be chosen as nodes traverse the network.  Each time another approval is given to the transaction, the higher its weight becomes and the more likely it will continue to be chosen.  What happens to the lazy tip that decided it didn’t have time to contribute properly?  It may take a while before (or if) it ever gets approved.  Because a major “selling point” of IOTA is the quick transaction speed for IoT devices, this is a real disincentive to actors on the network.

Figure 1:  A lazy tip may take a while to get approved.  Image from the official IOTA blog.

Take a look at Figure 1.  Block 16 decided to lazily select block 7 to approve rather than contributing more intelligently.  As a walker is looking for a transaction to approve, it may eventually reach block 7 and be given the choice:  do I want to proceed to block 9, which has a ton of approvals behind it, or do I want to go approve the lone wolf, block 17?  Again, because this choice is random, there still exists a probability that block 17 will be chosen. 

But because the choice is weighted there will be a much better chance that block 9 is chosen instead.  It pays to be a smart contributor!  This is how the network is able to maintain convergence and stability – no one wants their transaction to receive no approvals or take forever, so nodes wisely choose to be a good team member.

Randomness Generation

If that were the end of the story, it would seem that things have wrapped up neatly and effectively.  But…there’s another facet to look at, one that perplexes even the engineers that have built IOTA.  Just how random is random? 

It may seem strange, but there’s a lot to unpack here.  We won’t go too deep into the weeds (since it can get off-topic pretty quickly), but correctly selecting the value for weighted path choice (which is commonly designated by α or the Greek letter ‘alpha’) is highly important to maintaining an effective tangle.  The most effective method involves a value for α somewhere between 0 (which is the same thing as an unweighted random walk like we discussed in the last post) and 1 (which is the exact opposite where the heaviest path is always chosen). 

What would happen if we chose α = 1?  Take a look at Figure 2 below.

Figure 2:  A super-weighted random walk.  Image from the official IOTA blog.

There are a ton of tips leftover that may or may not ever get approved.  What’s more, they are present during the entire duration of the tangle depicted.  It’s common that some tips will exist at the end of the tangle, but for many to exist throughout the network is troublesome. 

With a value of α = 0, we get the same thing as in Part 2 of this series.  There’s no rhyme or reason as to what may happen in the network without a weighted approach to random walking, again leading to possible instabilities or a lack of convergence of transactions. 

Figure 3 is more of what we’re looking for.

Figure 3:  A weighted random walk.  Image from the official IOTA blog.

Tip Selection

Each time a tip needs to approve another transaction, a weighted random walk occurs.  As time goes on, each tip eventually gets folded into the tangle and the process continues ad infinitum.  And they all lived happily ever after.  The End.

Well hopefully you enjoyed our “walk” down the tangle and have gained a better understanding of tip selection.  While at first it may seem like a simple proposal (“just choose any two transactions” you may have thought), we hope that you’ve learned a lot and better appreciate the work that has gone into developing and maintaining a stable network.  Next week, we’re going to uncover more about transaction confirmation and consensus in the network.  Until then, happy reading!