Validity in the Tangle: The good, the Bad, and the Ugly

This article discusses how we can assess the validity of a transaction in a distributed ledger, and the particular issues we face in the case of the Tangle.

To begin with, let’s look at blockchain data structures. In a blockchain, before users attach a new block to the end of a chain they will make sure that all of the transactions in the chain are valid. Validity means that in each transaction, the payer has to have the required funds, and no coins can be created outside the protocol specification. This is made simple because the blocks are ordered in time and transactions are ordered within the blocks (by the miners) — this makes a comparison of the timing of two transactions relatively straightforward. For example, if Alice starts with an empty wallet, the transaction “Alice gets 3 coins” must precede the transaction “Alice gives 3 coins,” otherwise the latter is invalid.

How is the Tangle different?

Just like a blockchain, a necessary condition for a transaction to be valid is that the payer has received the coin before making the payment. However, since the Tangle is a Directed Acyclic Graph (DAG), the question of time ordering becomes non-trivial. The DAG structure makes it hard, or sometimes impossible, to resolve whether a payer has received coins before spending them.

Let’s take the case of 2 transactions A and B. In a blockchain transaction, there are only two options regarding their order. A happened before B or A happens after B. However, in a DAG, we also have the option that two transactions are uncomparable (i.e., we do not know which happened first).

To continue our discussion, let us agree on a few preliminaries. First, we treat validity as a state of a transaction, examined in the context of the current state of the Tangle. That is, any function that decides if a transaction is valid or not takes into account both the transaction itself and the Tangle it lives in.

Second, the only thing a transaction is accountable for is its cone of past transactions — that is, all of the transactions that it approves directly or indirectly.

When a user chooses which transactions to approve, they check the validity of the transactions by analyzing their cones (the part of the Tangle which these transactions reference) and can ignore the rest of the Tangle.

Every transaction in a cone implies the movement of coins from one account to another. To assess validity, we apply all of these movements to the Genesis stateto generate an updated state of wallets and their balances. We will call this state acceptable if all of the balances are non-negative (i.e., address balances cannot contain negative values, only zero or positive) and the sum of the balances is equal to the number of coins created in the Genesis.

Now let’s dive deeper into what properties a transaction and its cone should have, for the transaction to be considered valid. There are many options for such properties. Here, we consider three of those:

1. The minimum property

The moment that an honest (even if selfish) user sends a transaction, they should own the funds they are spending. That is, in a healthy system, we expect users to have the money “in their pocket” before trying to give it to someone else.

Having sufficient funds is the most basic condition. For a transaction to be considered valid, we expect that after all of its cone transactions are applied to the Genesis state, we get an acceptable state. This property is minimal in the sense that any other reasonable property we come up with will satisfy this property.

2. The “good random walk” property

This property comes up rather naturally when implementing the Tangle. As we know, to choose two transactions, the user performs two random walks starting from the Genesis until they get to a tip that they consider as “valid.” It would be a pain to go all the way from the Genesis to a tip just to discover that it is no good.

To save time, and broken hearts over bad tips, a user can check that every transaction that the random walk steps on have the “minimum property” stated above. This means for each transaction on the way, after applying the cone of this transaction to the Genesis state, the state we get is acceptable.

3. The maximum property

The most strict property we can demand from a transaction is that every transaction in its cone has the minimum property. In addition to getting an acceptable state for the end transaction or the transactions we saw on the walk, we also check that we get an acceptable state for any transaction that we approve, directly or indirectly.

So if users approve a transaction, they must take some responsibility over the funds in that transaction, even if those funds are not involved in the new transaction they are adding. This property is maximal in the sense that any reasonable property we can think about cannot ask more from the cone than what is stated above.

So which property is good, which is bad and which is ugly? Well, the one thing we can clearly say is that the “good random walk” property is bad, even if appealing from an implementation point of view. The problem with it is the following. If all of the users agree on this property it might be that two users disagree on a validity of a given transaction because the randomness of their walks took them in two different paths. As we would like to have honest users agree with each other as much as possible, this property is definitely bad.

As for the other two — numerous hours and gallons of e-ink went into the discussion of which is the good one (and which is the ugly one). We were not able to find an attack that the minimum property allows or a use case that the maximum property prevents, which leaves a lot of room for discussion without a clear tiebreaker. I have my ideas, but I encourage you to think and share yours and maybe we’ll come up with the one property to rule them all.