Untangling IOTA – Tip Selection Series – Part 1

,
Tangle Series Tip Selection

Hello there, and welcome back to our IOTA tangle series! Throughout the course of this series, we plan to look at the fundamental concepts behind IOTA, a revolutionary cryptocurrency that ditches the blockchain in favor of a…tangle?  If you’re thinking to yourself, “What’s a tangle?”, then you’re in the right place. 

IOTA Tangle Series Recap

Starting in the last post, we began our dive into a better understanding of the IOTA tangle, how it works, and why it even matters in the first place. 

Let’s recap:  a tangle is a directed acyclic graph or DAG.  Unless you’re already a math wizard, though, this concept might be a bit vague, so let’s break it down some.  A graph groups together objects; a directed graph means that the order between various relationships in the group matters; a directed acyclic graph has no succession of hops (between points) that forms a cycle (such that you could start at the beginning and repeat steps in a cyclic fashion indefinitely). 

What Does a Tangle Look Like

This was a bit abstract, so this week we plan to put some more details into the mix to better understand the tangle from an application perspective.  Again, if you want to learn more about the tangle itself from a fundamental, logical viewpoint, check out the last post in the series.

What does a tangle look like in practice?  A simple (i.e., verrrryyy simple) tangle is shown below:

Figure 1:  An example tangle.  Image from IOTA’s official blog.

Let’s start at the very left with block 0.  Like other cryptocurrencies, IOTA also has a so-called genesis block that kicked off the entire chain (or web in this case) of transactions.  When the genesis block was first instantiated, the entirety of MIOTA (IOTA’s token) was put into circulation.  How many tokens did this include?  Quite a few:  2,779,530,283,277,761 to exact (or around 2.78 x 1015 for those who prefer scientific notation).  Note that this number is actually the number of IOTA in place as a MIOTA refers to 1,000,000 IOTA (nice and confusing, eh?).  So while MIOTA is the actual name of the token, the number of IOTA listed above should be divided by 1,000,000 to get the number of MIOTA in circulation. 

Transactions And Approvals

What happened after the genesis block was created?  This is when the network actually kicked things off and started allowing for transactions and approvals.  Remember that the squares in the diagram above represent transactions in the network while the edges that connect the squares represent approvals of transactions.  Every time a new transaction (square) is placed on the network, it needs to choose two prior transactions to approve (where the older transactions are on the left of Figure 1 and newer transactions move to the right).  For example, take transaction #5.  Someone decided to make a transaction on the network, and now they need to approve 2 tips (where tips refer to unapproved transactions).  We’ll get into the selection process for tips in a little bit, but for now notice that #5 approves both #2 and #3.  In a logical fashion, both #2 and #3 have already approved #1 which approved #0…you get the picture. 

As each new transaction comes onto the network and approves 2 more tips, the previous transaction approvals get stronger and stronger (similar to the period of time in Bitcoin it takes to get a high probability of a block being approved; it takes quite a few blocks to really trust a transaction is legitimate – not just one approval).  Are there any more tips still on the diagram above?  Yep – #6 is a tip because it has yet to be approved by any other transactions.

IOTA Tip Selection

Now we understand the basics of the tangle – there are transactions and approvals, and before a transaction can be placed on the tangle it has to approve two other transactions.  No problem.  So that means a node can just choose any two transactions it wants, approve them, and be on its merry way, right?  Not only is this selection process an interesting facet of IOTA as a whole, but it is also extremely important to maintaining the convergence of the tangle and the network’s stability. In this post and the next, we’re going to try to better understand what it means to make a tip selection

Random Walk and Unweighted Random Walk

We could choose any number of methodologies to direct the approval of other transactions, but we’re going to stick with two of the more frequently cited alternatives in this process:  the random walk (or more precisely termed the “uniform random tip selection”) and the unweighted random walk.  I’m going to go ahead and spoil the surprise:  neither of these tip selection methods is used in IOTA; however, without understanding their underlying principles and the why behind their ineffectiveness, we can’t fully appreciate the weighted random walk used by the network.  Let’s start with the random walk (again, the more precise term is “uniform random tip selection”, but we’re just going to refer to it as “random walk” in this post for brevity).

The IOTA Foundation has put together quite an amazing visualization that you can use to better understand the random walk.  Feel free to give it a try before proceeding to experience a more intricate example of a tangle and why choosing the correct algorithm for tip selection is such a vital part of IOTA.

Figure 2:  Animation of a Random Walk

            So let’s examine Figure 2 a bit more.  Both #5 and #6 are animated as having 1) approved previous transactions and 2) been approved by later transactions.  This method is simple…just choose another transaction to approve and you’re good to go.  But what happens when the tangle gets really large or when a lot of people are trying to use the network at one time or both?

Tip Selection Visualization

Here’s where you get to be the kid in the science museum – we’re going to walk through the visual together to understand why choosing random transactions to approve is not a good approach on a sizeable network.  Just in case you didn’t click above, the visualization can be found here.  You’ll see two sliding controls on the web page.  The first is just the number of transactions currently displayed on the screen – simple enough.  The next slider represents the transaction rate on the network (the funny squiggle beside it is the Greek letter lambda).  The transaction rate can be thought of as the time between transactions of various nodes.  This means that at higher transaction rates, more nodes are trying to use the network at one time, but at lower rates few nodes are attempting to perform transactions simultaneously.

Alright, you’ve finally gotten to the fun part.  If you’re following along, go ahead and place the number of transactions at 10 (or close to 10) and place the transaction rate as low as it will go (0.1).  What happens?  This forms a chain of transactions (or it will with high probability; you may occasionally get something other than a pure chain).  In this case, the network is so under-utilized that only one tip ever exists at a time, leading to the next transaction approving the former and so forth.  What about with a transaction rate set equal to 50?  This is the other end of the spectrum – the network is so heavily utilized that the transactions come in too quickly for any mutual approvals to occur.  All of the transactions end up approving only the genesis block; needless to say, this is relatively useless for ensuring validity of transactions moving across the x-axis (time units). 

Transaction Rate

Now that we’ve varied the transaction rate, let’s keep it fixed and begin to vary the number of transactions on the chart.  Go ahead and set the transaction rate at close to 5 and the number of transactions around 30.  You can hover over the transaction sets and notice the paths in red that were previous in time to the current transaction and those in blue that were in the future.  Why are all of the gray blocks present?  These gray blocks represent tips, and there are quite a few, even at a small number of transactions.  What happens if we set the number of transactions to 300?  There are a smaller percentage of tips since the network rate has stayed the same.  Increasing the rate (to around 20 or so) causes the number of tips to get drastically higher. 

Feel free to play with the visualization some more, but let’s summarize what we’ve seen in this exercise:

·        A very low transaction rate will lead to a bland and less trustworthy network since there are no varied paths that lead to mutual ends.

·        A high transaction rate (relative to the number of transactions in the network) will leave quite a few orphaned nodes (or tips).  The paths they take may or may not be of use to the network, and when things scale to real-life size (say many thousands of transactions), the network could become unstable or fail to converge.

IOTA Tip Selection Series

If you’ve found this interesting, here are a couple of links to follow to learn more:

  • ·        Here’s a great summary of the topic we covered this week.
  • ·        Check out the section on transaction tips to get another perspective on this facet of the tangle.

Thanks again for reading!  Next week, we’re going to take a look at the unweighted random walk and why it technically helps but doesn’t fully solve our current problem.  Happy reading!

3 replies

Trackbacks & Pingbacks

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

  2. […] 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 […]

  3. […] 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 […]

Comments are closed.