The Tangle: an Illustrated Introduction

Part 5

Last week we mentioned the double-spend problem, which arises when Alice tries to spend her money more than once. In this post, which will be the last in the series, we show how this problem is resolved in the Tangle, and how we decide which history is the valid one.

To illustrate the problem, we will examine the following double spend scenario:

As you can see, Alice has 5i, which she gives to both Charlie and Bob. This is clearly a problem: we cannot treat both of these transactions as valid. Using Tangle terminology, we cannot have a future transaction approving both of them, since it will end up with a negative balance in Alice’s account.

We have learned that using the weighted random walk algorithm, eventually one of the branches will become much larger. Thus a consensus is formed around which transaction is valid. From the perspective of Bob or Charlie, however, there is a problem: how do they know if they really got the money from Alice?

Imagine Bob and Charlie are dinosaur dealers, and Alice purchased a pet T-Rex from each of them. If they both send her the T-Rex immediately after seeing her transaction in the Tangle, eventually one of them will discover he has not been paid. How can they know when it is safe to ship the lizard?

This is a serious problem, and in fact, Bitcoin was the first technology to successfully deal with it, back in 2009. To show how the Tangle solves it, we introduce a concept called confirmation confidence. This confidence is a measure of a transaction’s level of acceptance by the rest of the Tangle.

The confirmation confidence of a transaction is computed as follows:

Run the tip selection algorithm 100 times.
Count how many of those 100 tips approve our transaction, and call it A.
The confirmation confidence of our transaction is “A percent”.

In other words, the confidence of a transaction is the percentage of tips that approve it. Not all tips are considered equally; more likely tips are given more importance. To illustrate this point, we added confirmation confidence to the simulation. Transactions with a confidence of over 95% are shown with a thick border around them.

In the Tangle above, transaction 9 is approved by two out of the four tips. If we were using uniform random tip selection, it would have a confidence of exactly 50%. However, the tips that approve it are apparently more likely than the tips that do not, which raises the confidence a bit.

Now it is clear how Bob and Charlie can tell when it is safe to send their T-Rex to Alice. Once Alice’s transaction reaches some very high confidence threshold, say 95%, it is very unlikely that it will be pushed out of the consensus. We should be careful and say very unlikely, rather than impossible; if Alice wants to cheat, and has enough computational power, she can try to double-spend.

To do that, she will issue a transaction paying Charlie, instead of Bob. She will have to approve two old transactions with it, which do not reference her payment to Charlie. She will then start issuing as many transactions as she can, trying to raise the cumulative weight of her new branch. If she has enough computational power, she can cause the entire IOTA network to believe her and follow her new branch, thus re-writing history and successfully double-spending. If we look at the confidence level of her transaction with Bob, we will see it declining from 95% to eventually zero.

This attack is illustrated in the Tangle below, with time going downwards:

This scenario is only a risk if Alice can send more transactions than everyone else combined, or close to it. While not a major risk in a mature and active network, it is a real problem for today’s IOTA. There are not enough transactions going through the system for it to be safe from a concentrated double-spend attack.

Since IOTA was built for scaling we employ a voluntary and temporary different consensus mechanism for security reasons: the coordinator. Every two minutes, a milestone transaction is issued by the IOTA Foundation, and all transactions approved by it are considered to have a confirmation confidence of 100%, immediately. Using the coordinator, Alice’s second transaction will never have been approved in the first place. This acts as a protective mechanism while the IOTA network keeps growing toward the necessary activity from adoption needed to keep the network secure in a 100% decentralized manner, where the full Tangle distributed consensus algorithm kicks in. At that point, the IOTA Foundation will shut down the Coordinator and let the Tangle evolve entirely on its own. This will happen in iterative phases. When the network is mature enough to get rid of the Coordinator the network will also instantly become orders of magnitude more efficient.

I want to thank everyone who followed this series. I had a lot of fun writing it and answering your comments and questions and I'll be happy to take requests for follow-up posts on more advanced topics. Some candidates are attack vectors on the Tangle, an explanation of how alpha is defined, practical optimizations to the tip selection algorithm, and anything else you want to know more about.

You are welcome to write me in the comments section below, or on Discord: @alongal#3938.

Part 1: Introduction to the Tangle
Part 2: Transaction rates, latency, and random walks
Part 3: Cumulative weights and weighted random walks
Part 4: Approvers, balances, and double-spends