A new “consensus”: The Tangle Multiverse [Part 2]

In the first part of this series of blog posts, I have described the fundamental ideas and concepts behind this new approach but all of the descriptions have been pretty philosophical and the descriptions rather vague. I now want to use the additional parts to talk about the actual algorithms and mechanisms that are required to make this approach work.

PS: I have decided to break the remaining content down into several parts as well, because it just get’s too long otherwise.

“Parallel reality” based ledger state

1. Using a UTXO scheme

In such a UTXO scheme, every transaction that moves funds creates an output which can then be referenced as an input in the next transaction. The output contains the balance and is identified by a combination of address and transaction hash. Transactions therefore automatically reference the transactions that were responsible for creating the moved funds.

These additional references (next to branch and trunk) can be used to verify the origin of funds, without having to walk through the tangle and perform an expensive “binary search” for the funds in the past cone of a transaction.

2. Additional references as part of the past cone

  • all of the referenced inputs are solid and
  • branch and trunk are solid.

This way, a solid transaction by definition contains the funds it wants to spend in its past cone no matter where in the tangle a transaction attaches. Accordingly, the additional references allows us to have funding and spending transactions “next to each other” in parallel sub tangles which will make the tip-selection much easier (see picture):

The SPEND does not reference RECEIVE through trunk and branch

Since transactions directly reference funds that they want to spend, it is impossible to have transactions that try to spend funds out of thin air (because they would never become solid).

3. Aggregated Ledger State (for non-conflicting transactions)

All solid transaction will therefore initially be “booked” into an aggregated ledger state, which will simply be a list of transaction outputs — the “master reality”.

4. Detecting double spends

5. Handling conflicts using parallel “realities” (versions of the ledger state)

To be able to correctly reflect this, we create a copy of the ledger state for each of the double spends. Then we walk through the consumers of the double spends and “book” all the balance changes that share this perception into this new version of the ledger. If the balance changes have previously been booked in another reality (i.e. the master-reality while the transaction was not conflicting), then we move the booked balances over to the corresponding reality that we just created.

Note: Instead of making an “actual” copy of the ledger state, we organize these realities in a hierarchical way where every reality has a parent reality from which it recursively inherits all of the balances. This is an optimization that allows us to create realities without having to copy all of the existing transfer outputs. A “reality” becomes extremely lightweight and is just an identifier, which is used to logically “group” the transaction outputs. Since transaction outputs are only stored once and then just get “booked” to this logical group, realities “cost” next to nothing.

Let’s look at the example from the beginning and see how the conflicting transactions “create” new realities:

“Realities” independently track the different “versions” of the ledger state

6. Conflict sets

Note: Nodes can only like exactly one of the realities of a conflict set.

7. Recursive sub-realities

8. Aggregated realities

Whenever we receive a new transaction, we store the reality that a transaction is associated to in the transaction metadata. Newly attached transaction can simply “inherit” the reality of their parents in the following way:

We iterate over the referenced realities and remove all realities that “descend” from one another keeping only the “deepest” realities (that have the longest path to the main-reality).

  • If there is only one reality left, then we associate this reality with the new transaction.
  • If there is more than one reality left, then we combine them into an aggregated reality and assign the aggregated reality to the new transaction.

The identifier of the aggregated reality is calculated by hashing a concatenation of the sorted list of reality ids it “contains”.

9. Conflict resolution and cleaning up

Additional decisions about the pending sub realities will be resolved in the same way by merging them back with their parent reality whenever a decision was made.

Let’s again look at the example from before and assume that the voting resulted in REALITY2 to be accepted:

The winning reality gets promoted and becomes part of the master reality.

Note: We only discard the rejected reality in the ledger state. The transactions that were responsible for creating these realities and everything that attaches to it stay in the tangle and are not affected by this decision process.

Conclusion

The more complicated conflict handling only kicks in if it is really necessary and instead of having to walk the tangle over and over again to determine the balances, we just have to walk through the consumers (which is a very small subset of all the transactions) once when we create the realities.

At the same time, we no longer need to make sure that we correctly reference the funding transaction in the past cone of a spend, which will make the tip selection also independent of walks in the tangle.

This whole mechanism essentially works a little bit like “git”, where you create branches for the conflicting parts of the tangle, which then get merged back with the master branch once a decision has been made.

Anybody who is interested in the code for the ledger state can look it up here: https://github.com/iotaledger/goshimmer/tree/ledger_state/packages/ledgerstate

Note: This whole ledger state is completely independent from the “structure of the tangle” and only relies on the structure of the hidden DAG in the tangle. The worst case (where every single tip is conflicting with all other tips) essentially “degrades” to the way we calculate the ledger state today (with every single transaction having its own reality which can then only be resolved by “walking” through the parent realities of this transaction).

I am a hacker, feminist, futurist and tech enthusiast working for IOTA and trying to make the world a better place (whatever that means) :P