Author: Dr. Liew

In the previous article, I have introduced the concept of tips selection using unweighted random walk (URW) algorithm. However, URW has its weakness that could crash the IOTA ecosystem. Fortunately, there is a better tips selection method known as the weighted random walk(WRW). In this article, I shall introduce the concept of WRW with the help of some illustrations.

The Lazy Tips

The main issue of using the URW algorithm is the occurrence of lazy tips. Lazy tips are tips that choose to approve some old transactions rather than actively looking to approve new transactions. We label them lazy tips because they could not be bothered to update the latest state of the IOTA Tangle network. Instead,  they choose to broadcast its transactions based on old data. Let’s examine the following diagram.

With reference to the diagram above, transaction 17 and transaction 18 are lazy tips as they only approved some old transactions, as shown clearly in the diagram. If we employ the unweighted random walk selection method, these two tips have equal chances to get approved as other tips. Their behaviors would not even be penalized by the IOTA system. If there are too many lazy tips exist in the system, the Tangle will become stagnated or simply failed, as illustrated in the diagram below.

In the diagram above,  we notice that the transactions  30 to 38 chose to approve very old transactions, leaving transactions 25 to 29 unapproved, or became orphans. In such situation, the Tangle structure will just stop propagating and eventually crumbles. 

Weighted Random Walk

How should we overcome the ‘Lazy Tips’ phenomenon?  We might impose a rule that requires all incoming transactions to approve the recent transactions. However,  this coercive way is against the principles of decentralization and democracy, the core essence of decentralized ledger technologies. Therefore, IOTA opted for the persuasion method. It implements a built-in incentives system that rewards the participants to approve the recent transactions. The method is called the weighted random walk(WRW).

Weighted random walk uses the bias strategy to select the path towards a particular tip. The bias strategy involves choosing a path that has the highest approved transactions over the path that has very few approved transactions. Here we introduce a term called cumulative weight to denote the number of approvers of the transactions. It means that the higher the number of approvers, the higher the cumulative weight and vice versa. The approvers could both be direct or indirect approvers. Let’s examine the following diagram.

In order to approve tip number 13, the walker needs to walk to transaction number 5. However, transaction 5 only has a cumulative weight of 1, therefore the walker will not continue on this path. Instead, it will look for the path that has the highest cumulative weight. In our example, transaction 3 has a weight of 6, therefore the walker will choose this path and eventually reach transaction 14 and approve it.

The Parameter Alpha   

However, even the weighted random walk method has its own weakness. If we insist that every approval of the transactions must follow the rule strictly, we will do away with randomness completely and many tips will be left unapproved. The Tangle system will end up having many unapproved transactions, or orphans. *I introduced my own word orphan which may not be accurate in accordance with the IOTA white paper. You can read the IOTA white paper here.

To overcome the issues, IOTA introduced a parameter α to control the ‘weight’ of the weighted random walk. If α =0, it becomes unweighted random walk and creates the issue of approving too many lazy tips. On the other hand, if we set the value of α  too high, it will end up as a super weighted random walk which will leave many orphans in the Tangle.

Therefore, it is important to find a good balance between approving too many lazy tips and not leaving too many orphaned tips behind. To sum up, finding an ideal value for α is important to maintain the coherence of the Tangle ecosystem championed by IOTA.

We have learned about the basic concepts of Tangle in the previous article. Now. let’s examine how tips are selected. We shall also discuss transaction rates and the concept of random walk.

In IOTA tangle,  transactions do not occur uniformly but rather randomly. At a certain period,  there may be m transactions while in another period there may be only n transactions, where m>n or m<n. The transaction rate can be determined by a mathematical process known as  Poisson Point Process. The Poisson Point Process model is used to analyze random events, such as the arrival of customers at a store, phone calls at a call center or occurrence of earthquakes, distributed in time

The transaction rate may be calculated based on the simplified Poisson Point Process formula as follows:

N=λt

Where  N is the number of transactions and t is the time unit.  λ is a constant. For example, if we set λ =5, and time unit =10 (the unit could be in milliseconds or seconds etc), the number of transactions occurring in a 10-unit time interval is 5×10=50. 

Setting a suitable value of λ  is crucial to maintaining the coherence of the Tangle structure.   if we set the value of λ to be very small, let’s say 0.1 and the number of transactions remains at 50, the time interval will be 50 ÷ 0.1=500. In this case, it means that transactions will come in so slowly that it will form a chain instead of a Tangle, such that only one single tip could be approved at any given time, instead of approving two previous transactions.  The scenario is illustrated in the diagram below:

On the other hand, what will happen if we set the value of λ  too high? For example,  if λ  =10000 and N=50, the time interval t is 0.0005. It means that transactions will be occurring so fast that the only tip they can view is the genesis node, as illustrated in the diagram below:

In both cases, the Tangle structure will crumble. 

Unweighted Random walk Algorithm

The tips selection algorithm we have discussed so far is a random selection process. This kind of selection process might not be suitable for the real use case. Therefore, we need to choose a more advanced tip selection algorithms. One of the algorithms is known as the unweighted random walk.

What is it? In programming,  a walker is a variable used to move through an array or other data structure, often heading towards a fixed value and stepping through elements in an array. In Tangle, we can program a walker on the genesis transaction, and make it walks towards the tips.

On each step, it walks to one of the transactions which directly approves the one we are currently on. It chooses which transaction to walk to with equal probability, therefore it is called unweighted random walk. You can visualise the process from the animated diagram below:

Please watch the video below to understand more about the Tangle system.