Ordering the Tangle with Virtual Voting

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.


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:

  1. 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.
  2. 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.


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.

As a short(ish) follow up, I want clarify a few of the ideas I outlined in the above post, correct some conceptual errors, and put things in slightly more concrete terms. Hopefully make it easier to see if this approach is viable and practical.

The whole approach can be summarized as follows: If one of two distinct sub-branches of the Tangle contains approval weight above a certain ‘age limit’ k, nodes will consider those branches to be conflicting, and it will eventually become impossible to merge branches with a valid transaction. Nodes will then choose to follow the sub-branch with the most approval weight, updating their opinions to follow the majority of other nodes, and using the weak reference to approve valid messages which approved an invalid sub-branch.

For example, when nodes see a new tip or tips referencing the main tangle below a certain approval weight “age limit” will consider tangle to be split into two conflicting sub-realities, consisting of the newly arrived transaction(s) and the most recent part of the main-branch which does contain the new tips in its past or future cone. These two conflicting sub-branches, or sub-realities, represent conflicting possible futures for the Tangle, which nodes can ‘vote’ on by appending messages to the heavier sub-reality.

To go through it a little more carefully, I’ll quickly outline a few basic ideas. We can think of the ‘main branch’ of the tangle, as the set of all messages in the future cone of the genesis message. There can be no messages in the tangle which are not part of the main branch.


Sub-branches of the Tangle can be thought of as portions of the Tangle, which have non-overlapping future cones. New tips will always create small sub-branches which are merged when future transactions reference them. We can also identify sub-branches by the transaction ID of the oldest messages which are part of the sub-branch, and contain the entire sub-branch in their future cone. In the diagram below, a red sub-branch A and yellow sub-branch BC, which itself contains two further sub-branches, D and E.


To prevent the formation of large sub-branches - parasite chains - which attach to old parts of the Tangle, we’d first define an age limit, k - such that any part of the main Tangle which is referenced by over k approval weight is considered ‘old.’

When a node sees a message arrive that references a message below this age limit, the node should consider the main branch as being split into two conflicting sub-branches. In the diagram below, when the yellow messages begin to reference an old part of the main branch, an honest node would now consider main branch to have two conflicting sub-branches A and XY (identified by the oldest messages of each sub-branch which contain the entire sub branch in their future cone).


These two sub-branches, or sub-realities, of the main tangle, represent two possible, but conflicting futures of the Tangle. Honest nodes would always approve the sub-branch they perceive to be heavier, and pick up messages in the lighter branch with weak references.


If we look closer at the yellow sub-branch in the above diagram, we can see that an honest message C (which perhaps doesn’t see all the green messages) could reference the yellow branch and part of the green branch. But because of the green branch contains greater than k approval weight, it is only ever possible to ‘merge’ conflicting sub-branches up to a certain limit.

In the diagram below, message D contains enough approval weight, that any message which approves D, would necessarily consider message B to have approval weight greater than k. A transaction which approves message D would be agreeing with the perception of the green branch, that transaction A references a part of the main branch which is too old. Therefore it cannot also consider the yellow sub-branch valid. Any honest node would consider such a transaction to be an invalid approval of two conflicting sub-branches (similar to a message which confirms two conflicting UTXO ‘realities’). After a solidity check, any node would have all the information it needs to reject it.


In other words, the age limit k not only lets an honest node know when a sub-branch is attaching to an ‘old’ part of the main branch. It also means there is a limit to how ‘wide’ a sub-branch can get, before any message that tries to reference two conflicting sub-branches will be considered invalid. Any side-chain will be forced to grow outward and never be allowed to merge.

Now, honest nodes who see two conflicting sub-branches can simply choose to follow the heavier sub-branch by attaching transactions to it, and reference the rejected sub-branch with weak-references. The only effective way to create a parasite chain at a certain depth, would be to split the main branch into two conflicting sub branches, and fill the smaller sub-branch with enough approval weight to outpace the bigger branch. Older parts of the tangle will become increasingly immune to side chains, as it will always require more and more mana to force nodes to switch their perception of the heavier sub-branch. In addition, the perceived order of the Tangle would become more and more difficult to change with time. This approach essential replaces the ‘longest chain wins’ rule of Nakomoto Consensus with a “heaviest tangle wins” rule.

Incidentally, we can now see very clearly how resolving UTXO conflicts comes down to a specific application of this general logic. In the diagram below, if we have a UTXO conflict between A and B, any transaction which confirms both sub branches will be considered invalid. So these conflicting branches are allowed to grow but never merge, and honest nodes will simply prefer the heavier branch, thus deciding on one, agreed future for the Tangle. The remaining message with zero approval weight is effectively orphaned.


There is certainly more to say on this topic, but I think these are the basic contours of how this solution would work. The way nodes track branches and sub-branches would of course need more careful specification, but I imagine it would follow the same logic of tracking ‘realities’ in UTXO conflicts. I think there are questions too about how this approach interacts with UTXO conflict resolution and time stamps. As I mentioned above, if this approach works, it could be a way to apply virtual voting to order non-value messages, while still using FPC to resolve value conflicts.