How Monte Carlo Markov Chain is used in IOTA to Select tip

Hey everyone, welcome back to Lets See tech. Today I am going to write an article about IOTA, basic of IOTA and How Monte Carlo Markov Chain (MCMC) is used in IOTA to select a tip. This is a very vast question but I will try to elaborate in a simple way so that you can easily understand. So let’s start from the beginning i.e  UNDERSTANDING ABOUT IOTA and Tip selection techniques.

UNDERSTANDING ABOUT IOTA 

The main data structure behind the IOTA is Tangle, it is one type of directed graph that holds transactions. In this directed graph each vertex is represented as the transaction. In a tangle, when a new transaction enters, it needs to approve two previous transactions and as a result, the edges represent the connections of those two transactions. Here the unapproved transactions are called a tip. Now the main question arises which two tips to approve?

If we assume that transaction rate is very less, in that case, directed graphs form a chain because the new transaction approves only one transaction rather than two transactions.

How Monte Carlo Markov Chain is used in IOTA to select tip

Again if we assume that the transaction rate is very high, in that case, all the new transactions will approve the genesis transactions because a transaction is so fast. 

How Monte Carlo Markov Chain is used in IOTA to select tip

These are problems based on transaction rate. To overcome these problems, a tip selection algorithm is required.

The tip selection method should ideally provide the following two features:

  • Once a transaction accumulates a large number of approvers, it is very unlikely to get abandoned.
  • Honest transactions should get approved quickly.

Unweighted Random Walk:

In this algorithm, we start from the genesis block and start walking from that block to the tips. The walker, in each step, jumps to the transaction which directly approves that transaction. In this algorithm, walker jumps to the transaction which has the equal probabilities that’s why this algorithm is called unweighted.

Drawback: large number of lazy tips. Lazy tips are those transactions which approve old transactions rather than the latest transactions.

How Monte Carlo Markov Chain is used in IOTA to select tip

As you can see above figure 14 number transection is a lazy tip because it approves the old transaction 3 and 1 rather than the new transaction.

Weighted Random Walk:

In this algorithm, a new term is introduced that is the cumulative weight. Cumulative weight is the sum of total approvers a transaction has (including direct and indirect) and add one.

The main strategy of this algorithm is that the walker jumps to the transactions which have a higher cumulative weight than a light one. Using this algorithm we can overcome the lazy tip’s problems.

Drawback: In this algorithm, it only approves the single central chain. Most of the transactions are left behind.

How Monte Carlo Markov Chain is used in IOTA to select tip

As you can see from the above fig, grey boxes basically represent the zero approvers. So this the main drawback in this algorithm.

So to overcome these problems one more term is introduced which is alpha (α). Based on this alpha the walker jumps to the next transaction because alpha determines the importance of the transaction’s cumulative weight.

When we set the value alpha α very less in that case the walker follows the unweighted random walk. On the other hand, when the value alpha α is very high in that case the walker follows the weighted random walk algorithm. This method is known as Monte Carlo Markov chain(MCMC) Random walk process.

Monte Carlo Markov chain  Random walk process as follows-

  • First, we consider all the sites on the interval [W, 2W], where W is chosen large.
  • After that, we place N walkers independently on any site in the interval.
  • After that walkers start walking from that block to the tips by traversing multiple sites on the tangle. The walker, in each step, jumps to the transaction which directly approves that transaction.
  • During traversing, the two tips identified at first will be approved. However, those random walkers that reach the tips too fast are discarded because it may be a lazy tip, so which are not approved for a long time.
  • The transition probability of walkers as given below-

How Monte Carlo Markov Chain is used in IOTA to select tip Where   Pxy = Probability to walk from x to y.

             Hx = Cumulative weight of x;

             Hy = Cumulative weight of y;

             Hz = Cumulative weight of z;

             z~>x = z directly approves x.

 

Example:

How Monte Carlo Markov Chain is used in IOTA to select tip

From the figure, here the walkers reach to T0  which has three approvers namely T1, T2 and T3

See Also: How Technology has affected Humans

Here the T1 has only 1 approver, T2 has 3 approvers and T3 has 0 approver, so the cumulative weight of these approvers are

HT1 =2;

 HT2 = 3;

 HT3 = 1;

When alpha, α = 1;

How Monte Carlo Markov Chain is used in IOTA to select tip

As you can see T3 has the smaller probability as compared to T1 and T2

                               Now if we set the value alpha α = 0.1 in that case,

How Monte Carlo Markov Chain is used in IOTA to select tip

From this example, we got the main strategy of this algorithm is that 

  • When the value of alpha α is very high in that case  the walker follows the weighted random walk algorithm. From this example T2 has the highest probability as T2 has the highest cumulative weights .
  • When the value of alpha α is very less in that case  the walker follows the unweighted random walk algorithm with a probability of ⅓  (from this example). Here the walk is completely random

 

(Sources)

2 thoughts on “How Monte Carlo Markov Chain is used in IOTA to Select tip”

  1. Hello there, You have done an excellent job. I’ll certainly digg it and personally recommend to my friends.
    I’m sure they’ll be benefited from this website.

Leave a Reply

Your email address will not be published. Required fields are marked *