IOTA Deepdive #1: Consensus on the Tangle
IOTA is one of the first cryptocurrencies to work without a Blockchain. The IOTA Foundation, the creators of IOTA, has improved upon the concept of Blockchain and created “The Tangle”, which is a Directed Acyclic Graph (DAG) application that holds many of the same properties as Blockchain, but without some of the issues.
IOTA improves upon blockchain technology by being able to scale, have no fee’s and be quantum resistant. In this series of blogs, I am going to explain how IOTA has managed to make such massive improvements to the Blockchain protocol and how they work. I will often compare current Blockchain technology with the IOTA equivalents. In the first blog, I will explain how consensus is reached in the Tangle.
In the “classical” implementation of the Blockchain, we find two separated groups of people that interact with the network: miners and users. A user is someone who sends and receives data, while a miner is only busy with securing the network. The two groups interact through the nodes, which make up the Blockchain network. A node can be run by anyone, including users and miners. It stores the Blockchain and continuously monitors everything to make sure that all the transactions conform to the consensus rules of the network.
IOTA has merged these groups together, where the users directly contribute to the security of the network. This is where the big difference starts between the Tangle and a Blockchain. For every transaction that is attached to the Tangle, two older transactions need to be confirmed and some Proof-of-Work (PoW) calculations must be performed. The PoW that a user does, adds security to the network and removes the need for miners. The miners normally secure the network at the cost of paying them a transaction fee, but in IOTA the user is his own miner, making the transaction free. However, the PoW does add an electricity cost to the transaction, preventing someone from spamming the network without any costs.
Besides the PoW, every transaction also must confirm two other transactions. The PoW adds a weight to the transaction due to the amount of work that has been done. This weight is the start value for the cumulative weight counter for the transaction. Any transaction that has been referenced directly or indirectly through our confirmation, has its cumulative weight increased by the transactions PoW weight (Figure 1). A higher cumulative weight has increased likelihood that the transaction is confirmed in the entire network. In Figure 1, we see transaction F with a cumulative weight of 9. The weight comes from its own PoW (3), the direct references of B (3) and E (1) and the indirect references of C (1) via E and A (1) via B. The total sum is 3 + 3 + 1 + 1 + 1 = 9.
Figure 1: The cumulative weight of IOTA transactions. The blocks are transactions, with the arrows indicating the other transactions they confirm. Inside the box, bottom right is the weight of the PoW of the transaction and the top left is the cumulative weight. Source: IOTA whitepaper.
When a user wants to send a transaction, a request is sent to the node that connects them to the network. The node runs the tip selection algorithm, which finds two transactions that are near the end of the Tangle. The node then checks if these transactions were valid, to make sure no invalid transactions receive confirmations. After the transaction has been completed by the node, it will notify all other nodes in the network about the transaction. All other nodes will also check the validity of the transaction. Confirming invalid transaction risks your own transaction to remain unconfirmed and may even result in the node being kicked from the network.
The tip selection algorithm is a weighted random walk through the Tangle towards the tips. It chooses directions based on the cumulative weights of the transactions. In Figure 2, the tip selection algorithm is shown during a decision. It can choose to go through 3 transactions, the top transaction with a cumulative weight of 6 has 65% to be chosen, the middle 6% and the bottom 29%. This shows how the Tangle prefers to grow in the direction which is already the longest. The algorithm ends when it finds a tip and cannot go further. That tip will be the first of the two transactions that will be confirmed by the new incoming transaction. The algorithm will be run twice, in order to select two transactions.
Due to the preference towards a higher cumulative weight, the tip selection algorithm will automatically prefer to choose transaction tips that are at the end of the longest branch of the Tangle. So, when our transaction is already deep within the Tangle, it will be very unlikely that the Tangle would drop our transaction. The tip selection algorithm is important because it determines in what direction the Tangle grows and what transactions get confirmed with it. To confirm our transaction, we want the Tangle to grow in a direction where our transaction is included. Every application/user can verify if a transaction is confirmed by running the tip selection algorithm very often, say 100 times, and check how many of the chosen tips (in)directly confirm our transaction.
Figure 2: An example of the tip selection algorithm at work. The red lines show the decision that the algorithm has made so far in finding a tip. The blue lines are the current options of which transaction to pick. The number indicates the cumulative weight of the transactions, calculated by the amount of (in)direct confirmation it has from newer transactions. Grey boxes are potential tips where the algorithm could end. Source: IOTA blog: “The Tangle, an illustrated introduction”.
Promoting and Reattaching
When a transaction is getting older, without gaining many confirmations, the probability that it will be selected by the tip selection algorithm diminishes. This can randomly happen and doesn’t mean that our transaction was deemed invalid. However, in order to get confirmed, we can promote our transaction. This is done by creating a transaction that doesn’t send any IOTA’s (a zero-value transaction), which confirms our older transaction. This new transaction is seen as a new tip and has a higher probability to be selected for confirmation. Every confirmation that our promoter transaction receives counts as an indirect confirmation of our previous transaction, increasing the cumulative weight.
A transaction has a low probability to be confirmed if it has not been confirmed after 30 minutes, even if you keep promoting the transaction. In this case, a reattachment might be necessary. This is basically a copy-paste of your old transaction, and just attaching it to the Tangle again. It will be fresh on the tip of the Tangle, with a high probability to be confirmed. The Tangle will never allow two transactions to spend the same money, so therefore it will not confirm both transactions. Due to the relative newness of our reattached transaction, it will most likely be chosen over our initial transaction.
This all sounds like one big complicated mess that you don’t want to deal with, right? Well, luckily you won’t have to. Modern wallets like Trinity will handle all these problems under the hood. You will only have to post the transaction and wait for it to be confirmed.
As new transactions are required to confirm older transactions, an increase in transaction count will decrease the confirmation time. Therefore, IOTA can claim to scale and support thousands of transactions per second. However, this only looks at the speed of the algorithm, which is literally unlimited with IOTA, while blockchain solutions like Bitcoin and Ethereum are already limited by this due to a set block size and block time. When you look at limitations at the node level, scaling is still a potential issue. A node can only receive a set amount of transactions to process. This can be limited by network speed, disk space and even compute power. IOTA will eventually need to improve on these aspects as well. Some improvements are already scheduled, but most of them will get a higher priority when they start to be problematic. For now, IOTA is far ahead of the curve but will need to keep working on scaling solutions.
While scaling doesn’t seem to be a problem, IOTA has what I call an inverse scaling problem. The Tangle is not good at handling a low amount of transactions, which makes the system vulnerable and slow. With a low amount of transactions, the Tangle could possibly be invalidated in great amounts. This means that a secondary branch of transactions could be made, which will be attached on the main tangle before a legitimate transaction that it tries to invalidate (Figure 3). If the secondary branch becomes longer then the initial Tangle, it will be favored by the tip selection process and will continue to be used. The other transactions from the initial branch will be considered unconfirmed tips.
Figure 3: A malicious double spend through a branch transaction. The double-spend transaction tries to invalidate the legitimate transaction. The double-spend transaction is bigger in size, due to an increased PoW, which adds more weight to that transaction. Source: IOTA whitepaper.
Therefore, the IOTA Foundation is running a special node called “The Coordinator”. The Coordinator will only be used during the first phase of the IOTA development, where the network doesn’t have enough transactions per second to stay secure. Like any other user, the Coordinator issues transactions that validate two other transactions. However, all transactions that are verified directly or indirectly by a transaction from the Coordinator node are considered confirmed. These special transactions from the Coordinator are called milestones. The milestones make sure that the Tangle grows in a single direction, while also increasing the speed that the transactions are confirmed. Currently, milestones are created every 30 seconds. The Coordinator and all connected nodes all check if the referenced transactions are indeed valid, otherwise, the milestone will not be accepted by the network. The IOTA network still works on a decentralized consensus mechanism and therefore, the Coordinator cannot cheat.
When the adoption of IOTA starts taking off, the number of transactions per second will increase steadily. The more transactions per second, the harder and more unlikely it becomes that the Tangle will split into multiple branches. At that point, the Coordinator is no longer needed and would slow down the network. The Coordinator will most likely be removed in stages until the Tangle can grow and confirm on its own. When this will happen depends on the speed of adoption, but every project and every new user helps to reach the goal of running the Tangle without a Coordinator.
IOTA runs a very different and difficult consensus mechanism. The Tangle doesn’t work like a linear blockchain and therefore allows for great scaling and free transactions at the cost of PoW. While all the mechanisms of the IOTA Tangle might be very complicated, the wallet that users will be using to interact with the Tangle will hide most of these complications. The Tangle is unable to perform safely until the network has high activity, therefore the IOTA Foundation runs the Coordinator to support the network until it is completely self-sustaining.