(a.k.a. Tangle Multiverse for dummies)
This text is written expecting that the reader understands how Tangle Multiverse works in general, so if you are not familiar with this subject and want to learn about it, I can recommend to read at least Hans Moog’s blogpost series about Tangle Multiverse.
Tangle Multiverse is like the Holy grail for distributed consensus mechanisms. Its properties are so close to optimal that even if we could find a better consensus someday, the difference couldn’t be radical. The problem is that it’s very hard to make any kind of mathematical proof showing that the model really works. If you can’t prove it, you can’t use it. That is quite a frustrating thing to think about actually and reason for my recent late night hobby: an attempt to simplify Tangle Multiverse for analysis.
Because the hardest part to prove is the actual conflict resolution, I started to think about a solution where conflict resolution is separated into an isolated system. Tangle Multiverse is messy, and there is a lot of different interactions between Tangle DAG and the actual conflict resolution. First realization was that voting indeed can be done in its own DAG inside Tangle DAG. Then everything that happens at Tangle DAG level (variance of available tips and Tangle structure for example) can be left out from the analysis. That is probably self-evident to someone researching DAG structures, but I found that very interesting. You can resolve conflicts efficiently that way, but you lose partition tolerance, because only conflicting transactions accumulate votes over time.
After some faulty iterations came this next version which has partition tolerance, yet it still does conflict resolution quite separately from Tangle DAG. I could not find any critical flaws from this model myself, which doesn’t say too much though. Anyway it’s time for a little reality check and time to ask for some feedback!
General concepts
This model doesn’t have any “branch like switches”. Instead it aims for similar functionality with two different layers of voting i.e. priority 1 and priority 2 layers. Priority 2 layer is close to traditional on Tangle voting, but is mainly used for partition tolerance. It gathers voting information mainly for non-conflicting transactions in case of future conflicts (or network splits). Priority 1 layer pinpoints conflicting transactions from the Tangle DAG and resolves conflicts in its own layer quite separately from priority 2 layer (although even during a conflict resolution some influence from priority 2 layer can leak into priority 1 layer). Even if that separation is not perfect, it might be enough to make analysis easier. All voting information in the network travels via transactions.
We have concepts of “funds origin reality” and “opinion reality” like in Tangle Multiverse, but opinion reality concept differs in that we have two parallel opinion reality systems: priority 1 and priority 2 opinion realities. Priority 1 opinion reality always overrides priority 2 opinion reality if they are in a conflict, so every participant can only vote for one side of a conflict with it’s mana. Funds origin reality of every transaction is always included in its priority 1 and priority 2 opinion realities. Other realities that are included depend on which transactions transaction issuer likes in priority 1 and priority 2 layers. Both layers have their own stack of liked transactions.
Priority 1 layer — Conflict settlement
Each transaction can choose up to n confirmed transactions and and like them with priority 1 like (these can be any conflicting or non-conflicting transactions). Transaction includes priority 1 opinion realities of transactions it likes to it’s own priority 1 opinion reality stack. Every transaction likes also the previous transaction from the issuer itself in priority 1 layer and inherits the same priority 1 opinion realities as the previously issued transaction. (This becomes important once we talk about priority 2 layer)
Transactions can’t like other transactions with priority 1 like if it causes it to vote on both sides of a same conflict simultaneously with that transaction. In these kinds of situations the voters vote can be considered a null. Issuer can however change its previous opinion by giving priority 1 like to a transaction that votes the other side of a conflict the issuer has previously liked. The older opinion reality inherited from the previous transaction is then overwritten.
Honest transactions aim to vote in all conflicts using priority 1 likes if the conflict is supported by less than x percentage of network total mana. Honest nodes will keep on voting until the goal is reached.
Honest actors choose transactions they like at layer 1 using “like selection algorithm”. We don’t specify it here, because there are many possibilities and it probably needs simulations to find the best one. However the general idea is that honest actors choose transactions in a way that maximizes the amount of conflicts they vote at using a minimal amount of votes.
Priority 2 layer — Tangle DAG
Every transaction confirms two transactions and includes priority 2 opinion realities of those transactions to their own priority 2 opinion realities. Nevertheless if a transaction is voting against certain opinion reality using priority 1 opinion reality, it won’t include the conflicting priority 2 opinion reality to it’s opinion reality stack in priority 2 layer. This allows transactions to confirm transactions that have opinion realities they area against.
Transaction issuer can change its opinion on a conflict at priority 2 layer like in Tangle Multiverse, by issuing another transaction that is at the future cone of the transaction with the previous opinion.
Transactions future like cone consists of transactions that directly or indirectly approve the transaction in priority 2 layer, without there being any transaction in between that votes against the transaction using priority 1 layer.
When calculating total mana that votes for a certain transaction, we count together mana of its future like cone, subtract mana that have voted for it in the future like cone but later against it in priority 1 layer and add mana that have voted for it only using priority 1 layer.
How does it look like in action?
Conflict settlement
The Priority 1 layer lives on top of Tangle DAG. Transactions that one transaction likes in Priority 1 layer (directly and indirectly) may for example look like this:
Factors that affect to the structure of Priority 1 layer are:
- structure of conflicts
- the amount of mana each transaction issuer has
- order in which new transactions are issued
- like selection algorithm of priority layer 1
- attackers voting behavior
Important thing is that the general behaviour of honest voters is always the same and it depends mainly on a like selection algorithm.
When there are only a few conflicts (less than n), every honest voter who sees a conflict will vote it in priority 1 layer. This causes conflict resolution to be very independent from Tangle DAG. In case of many conflicts (let’s say n is 5 and there are 100 conflicts) both layers gather voting information during conflict resolution, but priority layer 1 gathers it much faster. If n is larger than 2 there is simply more capacity to vote in priority layer 1 than in priority layer 2. Even more importantly, the like selection algorithm maximizes the amount of information honest players give with their votes.
Example:
In the above example with 100 conflicts, let’s say we have a like selection algorithm that simply only tries to maximize the amount of conflicts each honest voter is participating in.
During the first moment, there might be multiple honest voters that issue transactions quite simultaneously. They all choose 5 conflicts randomly. In the next moment voters can group these transactions together and vote an exponentially larger amount of conflicts. In priority layer 2 transactions are selected by tip selection algorithm. It is designed to confirm the maximal amount of honest transactions in minimal time, and it is thus much slower in gathering voting information.
Preventing Tangle DAG splits and partition tolerance
Because every transaction that is part of the Tangle DAG main branch is either voted for, or against, we can always know how much mana is voting for each honest transaction. This allows honest voters to change their opinion in case of a merge after a network partition. We have basically similar partition tolerance as in Tangle Multiverse.
In contrast Tangle DAG splits are handled a bit differently than in Tangle Multiverse. Here is an example of priority layer 2 (Tangle Dag):
Transactions 1 and 2 are conflicting. For some reason transactions 3,4 and 5 are voting for transaction 2 in priority layer 2, even if the majority of the network’s mana is voting transaction 1 (maybe they didn’t see the transaction 1 for some reason).
Transaction 6 wants to confirm transaction 5, so the issuer likes transaction 1 in Priority layer 1 (if he hasn’t done it yet) and confirms transaction 5 (and likes it in priority layer 2). Transaction 6 also indirectly likes transaction 3 and 4 in Priority layer 2, but not transaction 2 because it has voted on the other side of the conflict already.
If a similar situation would have been solved with a branch like switch, transaction 6 would have only liked transaction 5 funds origin reality, so transaction would not like indirectly any transactions with it’s partial like. Whether or not that is a meaningful difference can be debated.
Because transaction 6 doesn’t vote for transaction 2 on priority layer 2, transactions that confirm transaction 6 won’t either do so.
Comparison to Tangle multiverse
- message size and bandwidth — message size is larger because each message has more references to other messages, still message size probably won’t grow enormously. Optimal n is most likely quite small
- computational complexity — the structure is more complex with two layers and this requires probably more computations. I don’t have knowledge to evaluate this factor any further.
- storage capacity — storage capacity also increases, but like the message size, probably not significantly
- conflict resolution capacity — this model most likely resolves conflicts faster when there is extreme conflict load. On the other hand there are many possible solutions for conflict spamming and it might not be significant difference
- even though this model is less elegant than Tangle Multiverse, it’s still in the same category of blazingly fast and efficient solutions (if it works of course)
I’m quite sure that I have missed something essential and have to go back to square one after feedback. If not, the next iteration will be an attempt to combine this with dynamic sharding and there are a lot more fun ideas I’d like to try to make that happen. But only after I pass this checkpoint. Thanks for reading.
