Tangle: Weighted Random walk

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.

Tips Selection in Tangle

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:


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.

Video Adapted from IOTA.ORG

Introducing IOTA

The Machine Economy

From the connected mobile devices, wearable devices to Smart homes, the Internet of Things is beginning to permeate every aspect of our lives.  The adoption of IoT technologies is fostering a new economy nurtured by these technologies. As this kind of economy is powered by the machine to machine (M2M) communication, it is also known as the machine economy.

According to IOTA foundation, the number of connected devices is estimated to reach 75 billion by 2025. Internet of Things (IoT) includes tiny sensors on roads, bridges, railway tracks, mobile phones, smart washing machines , smart drones, wearable electronics like smartwatches and more. The amount of data being produced and consumed by all these devices is becoming astronomical.

Over the next five years, it is predicted that the global IP traffic on the IoT network will increase five-fold by 2021, monthly IP traffic is expected to reach  31 Gigabytes per capita. However, for the same period, broadband speeds are expected only to double and the global data pipelines will experience congestion. By then, it will not be possible for all these devices to stay connected 24/7 to the centralized cloud silos for all the data they will generate.

Recently,  the emergence  ‘Fog’ and ‘Mist’ computing emerged might provide a solution to the aforementioned issue. However, how to distribute resources efficiently across the IoT ecosystem remains a huge challenge in this new Machine Economy. Therefore, IOTA was conceptualized with the mission to tackle the congestion issue. By implementing zero fee transactions, these devices can share the technological resources in real-time locally in a distributed network. In this way, it can avoid the centralized points of failure, eliminating the resource infrastructure bottleneck.

The Vision of IOTA

The vision of IOTA is to enable all connected devices through verification of truth and transactional settlements, which incentivize devices to make available its properties and data in real time. In addition, the IOTA cryptocurrency was developed to enable Machine-2-Machine (M2M) transaction, thus creates the machine economy powered by IoT.

The main objective of IOTA is to serve the machine economy by enabling zero fee M2M payments. IOTA has established itself as the leader in  IoT fintech landscape by providing efficient, secure, lightweight, real-time microtransactions without fees. It is open-source and engineered specifically for the Internet of Things. Its real-time microtransactions using the IOTA cryptocurrency has created an ecosystem that is ready and flexible for scale.

The Tangle

IOTA technology is similar to the blockchain technology but it is not blockchain-based. In fact, it utilizes a kind of distributed ledger technology minus the blocks. IOTA is a permissionless distributed ledger that utilizes a cutting-edge technology, known as Tangle. The Tangle is a new data structure based on a Directed Acyclic Graph(DAG). As opposed to the blockchain, it has no blocks, no chain and also no Miners. This unique new architecture enables IOTA works differently compared to Blockchains and other Distributed Ledger Technologies.

The Core Principles

IOTA uses a DAG instead of a blockchain to store its ledger. The main objective is to solve the scalability issue. As we all know, a blockchain has an inherent transaction rate limit, due to the conflict between block sizes and block issuances rates. If blocks are issued too frequently, or are too large, forks will occur often. When a fork happens, several new blocks are added to the chain simultaneously, and the network needs to decide between them, thus slow down the validation process.

In a DAG, forks can still occur but unlike in a blockchain, a fork is not final. In the DAG system, diverging branches can still be merged back together, as long as they are consistent with each other. The transaction rate is therefore bounded only by the latency between the nodes. A DAG favors availability over consistency.

The Tangle Structure

The Tangle is a Directed Acyclic Graph (DAG). In computer science, a directed graph is a collection of vertices (squares), which are connected to each other by edges (arrows).  In the IOTA Tangle data structure, the vertices represent transactions, and the edges represent approvals. It retains the blockchain features that include distributed ledger,  immutability, and secure transactions, but it does not utilize the blocks.

The Tangle structure is shown in the following figure.

With reference to the figure below,  If there is an edge(arrow)
directed node (vertex) 100  to node 99, it means that node 100 approves the transaction at node 99. When a node issues a new transaction, it must choose 2 previous ones to approve, thereby adding 2 new edges(arrows) to the graph. Notice that each node must be connected to two previous nodes.

The first transaction in the Tangle is referred to as the genesis. All the IOTA tokens were created in the genesis, and no new ones will ever be created. All transactions in the tangle reference the genesis directly or indirectly.

Transactions with no approvers are called tips. In the figure above, node 100 is a tip because no one approves its transaction yet.  All the nodes must choose tips to approve, rather than older transactions, because this helps move the network consensus forwards. The method for choosing which two tips one should approve is one of the key innovations of IOTA.