Ordering the Tangle with Virtual Voting
In the following post, I want to outline a way we can use virtual voting to come to consensus on the order of the tangle. The ideas and methods that make up on-tangle-voting or “multiverse consensus” were elaborated to deal with UTXO conflicts, but they can be extended to resolve conflicts on the perception of the order of the ledger state in a relatively straightforward way.
This expanded version of virtual voting would give an unambiguous order to events in the tangle past a certain depth, which would become increasingly immune to reorganization over time, all with zero message overhead. Extending the (potential) role of virtual voting within the protocol is possible because finding consensus on conflicting perceptions of causality (UTXO collisions), and on conflicting perceptions of the order of events in the tangle, are in fact the same thing.
The Proposal
If we consider a transaction’s “age” to be the approval weight contained in its future cone, we can then require tips to reference transactions younger than a certain “age limit,” i.e. with less than a certain approval weight, in order to be considered valid. Based on this rule alone, when a new transaction A references an old transaction B, different nodes may come to different local perceptions of the validity of A. Different parts of the network will begin to issue transactions in two conflicting versions of the tangle, one which includes and one which rejects transaction A. As nodes become aware of each other’s conflicting perceptions of the ledger state, they can use “virtual voting” to select the version of the tangle they perceive to have more approval, simply by issuing new transactions that reference it. As with on-tangle-voting in general, weak references can be used to prevent the need for re-attachments.
What follows is a more detailed elaboration this basic idea.
Approval Weight and Transaction “Age”
If we take a given transaction in the tangle, and look at all the events it references, directly or indirectly, we can be certain that these happened at an earlier moment in time. Likewise, if we look at all the events that reference our transaction, directly or indirectly, we can be sure they came later than our transaction.
Viewed this way, there is an intuitive correlation between the approval weight of a transaction and its age. If we see a bunch of nodes who have seen other nodes who have seen other nodes who have seen other nodes … see an event, we can infer from the “depth” of these recursive observations how far something has happened in the past. We can also infer from the number of observers and their reliability (the mana held by a node), a degree of certainty that our perception is true. Approval weight expresses something like the mana-weighted perception of time.
For now let’s say, without other qualifications, that a transaction with a relatively heavy future-cone (FC), and light past cone (PC) is “older” and that a transaction with a light FC and heavy PC is “newer.” The oldest transaction, the genesis transaction, has a past cone with zero approval weight. The newest transactions (i.e. tips) have a FC of zero.
Reorganizations
However, there is one major problem. If we relied only on the FC of a transaction to determine its age, and therefore the order of the tangle, a node could issue a new transaction which references a transaction deep in the past, and change our perception of its age relative to other transactions. For instance, in this diagram, the newly arrived transaction A references B and creates the impression that B is older, by adding approval weight to the FC of B. Simultaneously, the age of the transactions outside of the past cone of B remain unchanged. This situation could arise because the node issuing transaction A is out of sync with the rest of the network, or acting maliciously, trying to affect someone’s understanding of the global order of events in the tangle.
Locally Verified Age Limits
A first step to mitigating reorganizations is to set some kind of locally verified “age limit,” a rule that considers any transactions that reference older parts of the tangle to be invalid. Using the approval weight contained in the future cone of a transaction as a measure of its age, we can establish a rule that a valid tip should only reference other transactions with a maximum age no greater than some constant k.
The diagram above shows the perspective of the Green node who sees this particular view of the tangle. The approval weight expressed in the future cone of B (blue) is larger than a certain constant k, so it considers A to have an invalid perception of time.
The Green transaction can now weakly reference A, stating in effect that it approves of the contents of A, but that A has a false perception of the age of transaction B. The approval weight of A is not applied to any transactions in its past cone, and the objective perception of the age of B, relative to all other transactions recorded in the tangle remains unchanged.
We can also calculate the age of A by looking at its future cone, as we would with any other transaction, beginning with the weak reference from Green, and any future transactions which reference it directly with weak references, or indirectly by approving the Green transaction.
Conflicting Versions of the Ledger
If all nodes had the same perception of the tangle at the same time this would work wonderfully. However, in the diagram above, a Purple node has a completely different view of the same tangle, and believes the approval weight confirming B is much lower than as perceived by the Green node. Therefore, it strongly likes A, believing it to be a valid tip, and even references a transaction in B’s past cone.
Now any node seeing this same setup from their own perspective, will all come to one of two conclusions:
- transaction A references a part of the tangle which is too old, and expresses an invalid perception of time. A, and any transactions which strongly reference A, should only be referenced with a weak reference.
- transaction A references a recent part of the tangle and expresses a valid perception of time. A should be referenced with strong references.
When nodes are presented with two competing perceptions of the ledger state, they can use virtual voting, in exactly the same terms already elaborated in “multiverse consensus.” Some of the more subtle mechanics for coming to consensus on the perception of time are slightly different than voting on conflicting ledger updates, but they closely resemble one another.
Voting on the Order of the Tangle
The Green node which believes transaction A has an invalid perception of time, will reference A with a weak reference, if no one else has done so already. It immediately creates two new realities, one identified by transaction A, and one identified by transaction B. Transaction A along with any other transactions which strongly reference A will be booked into Reality A.
Reality B corresponds to the opinion that transaction A has an invalid perception of time, and should be weakly referenced. The weight of Reality B is measured by the approval weight of the transactions which strongly reference B but do not strongly reference A.
Once the Purple node, which believes A has a valid perception of time, catches up a little bit, and sees that Green has liked A with a weak reference, it too will also create two realities, one for A and one for B. Now consensus can proceed in the same manner it would with regard to conflicts about the ledger state. As a node sees that more approval weight has accumulated in one reality or the other, it switches sides, by attaching new transactions to the reality which strongly references either transaction A or B. A node’s most recent transaction expresses its current opinion.
In the example, nodes in Reality B will weakly reference transactions in Reality A, in order to incorporate them into their own perception of time. However, if Reality A gets heavy enough that nodes switch from B to A, as nodes switch they can weakly reference old transactions which collide with their own perception of the age of transaction B, and incorporate them into the new reality.
One detail which is worth noting: In my example, transaction A only references one transaction in the ‘main tangle.’ In reality, A could reference several transactions, in which case the realities would always be formed with respect to the oldest transaction referenced by A, measured by its future approval weight. And in the case where none of A’s children is ‘older’ we would just sort them by hash.
Conclusion
There is a strong intuitive appeal to the idea that if we can use virtual voting to resolve conflicting perceptions of causality (UTXO collisions), then virtual voting should also apply to conflicting perceptions of the order of events. Causality and order are deeply connected, and on some level represent the same thing. When voting at two competing UTXO’s we are essentially trying to determine which one came first - which is equivalent to measuring its age, by the mana weight which approves it. A transaction with zero approval weight, in a sense, has never happened at all.
The only major difference between virtual voting on UTXO conflicts versus voting on the order of the tangle is that at the resolution of a UTXO conflict, a single transaction is orphaned. When coming to consensus on the order of the ledger, this is not the case. However, this is only a cursory overview of how one could approach consensus on the order of the Tangle with virtual voting. There are likely many details which I’ve glossed over or failed to consider, both with regard to theoretical details and practical implementation.
For instance, how would this approach handle nested conflicts? I think the Git-like branches and sub-branches already specified for multiverse consensus would easily translate into this context. And for meta-stability attacks, whichever approach works for “vanilla” multiverse consensus will likely work here (I favor using “proof of honest voting,” as I outlined in my last post). There are also existing tools, like markers, which might make tracking approval weights more efficient. Virtual voting on the order of transactions can also be applied to non-value transactions, and may provide a good way to test the reliability of on-tangle-voting “in the wild” before applying it to value transactions.
One last thing to consider is the value of the constant k, which I only mentioned in passing above. My suspicion is that setting k very low, and requiring nodes to attach to more recent parts of the tangle, will force more virtual voting, and cause the order of the tangle to conform to the perception of a smaller number of high mana nodes. Setting k higher will lead to fewer rounds of voting, and incorporate the opinion of lower mana nodes, with the trade-off that it will take longer for the order of the tangle to solidify. I suspect that determining the value of k, which could be dynamic, will be not only a question of efficiency and safety, but also an “ethical” question about the role of small mana holders in consensus.
If this approach is successful it would have many applications and advantages, apart from its simplicity and messaging efficiency, like guaranteeing with high probability a total order of events past a certain depth, enforcing reliable timestamps, and the mitigation of parasite chains. In fact, in this approach, in order to reference the genesis transaction, node would need to reproduce the approval weight contained in the entire tangle (and provide ‘virtual proof’ that it has never used that mana ever before in the entire tangle!).
The equivalence of consensus on causality and consensus on time suggested above is rooted in the basic fact that every statement in the Tangle is also a statement about the validity of other statements. This in turn allows every node, albeit asynchronously, to arrive a perception of all other nodes’ perceptions of all other nodes’ perceptions of all other nodes’ perceptions … and so on … of the ledger state. Consensus is nothing more than aligning one’s local perception of truth with the majority perception of truth most recently visible in the network. The function of a node is, after all, only to verify statements - including its own - which it does by always preferring the perception of truth more strongly verified by others. The basic requirement for honest nodes to “tell the truth” leads to the fascinating property that consensus on the state of the Tangle is an emergent behavior of the Tangle itself.
