Untangling IOTA – Tip Selection Part 2 – Scaling the IOTA Network

, ,

Welcome back to our discussion of IOTA and tip selection within the IOTA Tangle!  So far in this series we have looked at what IOTA is and how its revolutionary tangle is such a paradigm shift from the ordinary blockchain we are used to seeing in so many crypto networks.  In this post, we’re going to try to better understand the unweighted random walk method for tip selection.  It’s a great method, but it merely lays the foundation for a more intelligent algorithm that will provide the best possible way of approving tips and linking branches on the tangle. 

In case you missed the first post on tip selection, let’s take a step back and get on the same page.  We’ll just briefly mention here what we discovered last time (feel free to pause and read Tip Selection Part 1 before venturing on).  Although the nomenclature may seem a bit funny, a tip in the IOTA world simply refers to an unapproved transaction.  Every time a node wants to perform a transaction on the network, the node must first approve two other transactions that have occurred at some point in the past. 

This is how IOTA is “free” to use (as in there is no exchange of currency, or MIOTA, in transactions but rather an exchange of work).  Although approving other transactions in the tangle is a requirement, pay attention to what’s not required here.  Give up?  Choosing which transactions a node approves can play a great role in determining the robustness, scalability, and eventual convergence of the tangle.  It’s not enough to approve transactions at random; there has to be an intelligent method of offering the best two transactions to approve.

Scaling the IOTA Network

This is where we left off last week.  Randomly choosing two transactions to approve was shown to be not so great, at best.  When we begin scaling a network operating for extended durations to many thousands of transactions all occurring quickly, IOTA could potentially become unstable or slow way down. Instead of randomly choosing tips, what if there was a way to more intelligently choose our path to the best tip for the current tangle state?

Unweighted Random Walk

Alright, that was our setup for the unweighted random walk, the next step (pun intended) in achieving tip selection in an intelligent and effective manner.  Before we describe the unweighted random walk, let’s set a clear delineation between it and the last algorithm we studied, the uniform random tip selection.  Our topic of interest in this post is not simply choosing whichever transaction happens to pop up first as we traverse the tangle. 

The last post attempted to clearly spell out the weakness in this pattern.  Instead, what if we started at the genesis block and started walking to the next tip needing approval?  We could incorporate a probabilistic approach that evenly splits up the “playing field” and attempts to balance the tips remaining on the tangle – hence the “random walk”.  (We’ll discuss why it’s unweighted in a minute.)

Rather than sitting here rattling off facts that may have no bearing on your life, let’s try the hands-on approach again this post.  We’ll start with a simple figure that will help illustrate the points we need to grasp; then we can move on to actually playing with a live simulation to further cement our newly acquired knowledge.  Take a look at the figure below.

Probabilistic Approach

GIF of Tip Selection Part 2

GIF of Tip Selection Part 2

Figure 1:  An example of an unweighted random walk.  Image from the IOTA Foundation blog.

            The GIF above shows a very basic tangle that utilizes the unweighted random walk.  Notice the outlines around block 12 above – this is the transaction that has just been added to the network and needs to approve two other transactions.  Starting on the left with block 0 (the genesis block), the transaction path first follows (or “walks”) to block 1.  Notice that the block appears in blue with the text “100%”.  This means that there is a 100% chance that this path will be taken between block 0 and block 1.  This is a rather silly example but clearly shows path traversal and its probabilities. The same thing occurs between block 1 and block 2.

            After block 2, though, things start to get a little more interesting.  Block 2 has three different paths that it can traverse to get one step closer to block 12.  It can either take the path to block 3 or block 4 or block 5.  You’ll notice that those three blocks all turn blue and display “1/3” when it’s time to choose one – this is because there is a 1 in 3 chance that each of them could be chosen.  In this illustration, the path chosen leads to block 4.  Since the only predecessor to block 4 is block 8, there is next a 100% chance that block 12 approves block 8.

Random Walk Weakness

            There it is, the basics of the unweighted random walk.  Let’s take a second now to discuss why this approach has been deemed “unweighted”.  Did you notice that every time a new path could be taken all nodes had the same probability of being chosen?  In other words, when we went from block 2 to the next hop in the random walk, we had an equally likely chance of getting 3 or 4 or 5.  But… what’s wrong with that?  Nothing, technically.

            Here’s where the weakness lies though.  While this is a totally feasible solution to this problem, it’s not the best solution to this problem.  Remember that we had a 1/3 chance of choosing block 4.  What if, for some reason, we happened to randomly choose block 4 90% of the time?  This get less and less feasible the more approvals that take place, but the math can work out without a hitch.  That could mean that, say, block 5 almost never got picked…which means that its downstream branch would rarely ever be touched. 

After a while, all of these random branches could become somewhat “lazy” and lead to a massive, disparate mess rather than a properly functioning tangle.  We’re not going to tackle this problem until next week, but this method gets us one step closer (another walk pun) to understanding how the best method works and why we would end up choosing it over another algorithm.

Tangle and Transactions

            Alright, we promised some hands-on action to better understand this method.  First, let’s go ahead and open the visualization developed by the nice folks over at the IOTA Foundation.  To tame the model and make it a bit easier to digest at first, let’s start with settings at 10 transactions, a transaction rate (or λ, the Greek letter lambda) of 2, and an animation speed of 0.7.  (These don’t have to be exact, just try to get them close.)  Obviously, this process is random, but we’ll try to explain in general terms what’s happening as the visualization progresses.  At first, we see a genesis block created and then block 1 shortly thereafter.  Block 1 obviously has no one else to approve, so it must approve block 0.  However, after we get to blocks 6 and 7, a real hierarchy begins to emerge. 

New Transactions

            New transactions that come online start to approve the second layer of transactions (most likely blocks 1 and 2 or so in your random visualization).  Each time a new transaction comes online, it’s easy to see that the probability of choosing a specific path to walk drops from 100% to 1/2 or 1/3 or so on.  What happens if the transaction rate in the network increases dramatically?  Try setting a rate of about 10-15.  You may or may not get a second tier of approvals; more than likely all of these transactions will approve the genesis block.  This is a by-product of a very active network – a web of transactions is hard to build because there is no settling time to build a tiered network and a flat tangle results.

            Since we’ve looked at simple examples, let’s take a look at a more complicated tangle that highlights the weakness inherent in the unweighted random walk.  Let’s put settings at about 150, 5, and 0.99.  The demonstration moves quickly, but can you see what’s happening to some of the gray blocks as they appear?  It takes a while for some of them to ever get involved in the tangle, and when they do, they might not have much affiliation other than a few approvals.  This isn’t an optimal configuration as we want the tangle to remain diverse yet compact.  We’ll remedy this situation in the next post.

IOTA Tip Selection

            As you can see, tip selection had to be carefully considered by the IOTA researchers in order to build a working and robust tangle that could scale to many thousands (or eventually millions) of transactions during a short period of time.  Interested in reading more?  Check out this blog post by the IOTA Foundation; it’s a great primer with pertinent information to understanding how this process works and why it’s been designed as such.  We know you’ve been waiting in eager anticipation, so next week we’re going to finally uncover the best algorithm for tip selection. 

Although the methods covered this week and last aren’t the final answers to the question, it was important to build a foundation and better appreciate their limitations and the chosen method’s strengths.

Until next time, happy reading!

1 reply

Trackbacks & Pingbacks

  1. […] on the tangle.  If you weren’t there, feel free to take a few minutes and read Part 1, Part 2, and Part […]

Comments are closed.