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
The first big building block is a different form of record keeping for the ledger state that tries to model the ledger state by acknowledging the “hidden tangle inside the tangle” principles rather than trying to make the ledger state being a direct representation of the tangle.
1. Using a UTXO scheme
Instead of using an account based ledger where we only keep track of the addresses and their balances, we accordingly keep track of “sub balances” on an address associated to the transaction hash that was responsible for creating these balances.
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
These additional input references (next to branch and trunk) will be considered to be part of the past cone of a transaction and a transaction is only solid, if
- 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):
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)
Since most of the transactions in a “healthy” tangle are non-conflicting (or just data transaction), they will anyway converge into a globally shared state that nodes will agree on and we don’t even have to think about maintaining “separate” ledger states or perceptions for each of these honest 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
Whenever a transaction consumes an output, we take note of the transaction hash that consumed the output by storing it in a list of consumers together with the output in the database (we mark it as spent). Whenever a transaction consumes an already spent output that was consumed by another transaction, then we have identified a double spend and need to handle it differently.
5. Handling conflicts using parallel “realities” (versions of the ledger state)
Every double spends introduces a unique perception of the ledger that will not automatically converge like the honest transactions discussed before. All transactions, that are directly or indirectly consuming the funds of such a double spend are sharing this unique perception.
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:
6. Conflict sets
If transactions are spending the same input, then their corresponding realities will form a conflict set (identified by the used input). If a transaction is spending multiple inputs, then its reality can be part of multiple conflict sets at the same time.
Note: Nodes can only like exactly one of the realities of a conflict set.
7. Recursive sub-realities
If a reality contains additional double spends, then it will recursively form sub-realities in the same way as realities get formed from the master-reality by creating a new reality that is having his parent reality pointing towards the reality that contained the funds before the second spend arrived.
8. Aggregated realities
It is also possible for transactions to combine multiple realities (if they are not part of the same conflict set) by using outputs from these realities. This will create an “aggregated reality” that has multiple parent realities (namely the ones that got combined). This allows us to associate every transaction with exactly one reality.
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
Once a conflict has been decided (i.e. by finalizing a decision after a virtual voting process), we can remove the conflict set and all of its associated realities (prune the transactions from the ledger state — they will simply be discarded). The winning reality gets promoted, which means that we will copy all of its content into its parent reality and reconnect its sub-realities to now point at the underlying parent reality instead.
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:
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
This way of keeping track of the leder allows us to instantly decide if a transaction is valid without having to walk the tangle. We simply need to retrieve the referenced transaction outputs and check if they have a consumer already.
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).
