On Voting on the Tangle (on the Tangle)

What follows is a sketch for a variation on On Tangle Voting (originally outlined here). For those of you who’ve been following the development of OTV, the motivation for this proposal is the simplification of tip selection and resilience against a metastability attack, possibly allowing for the removal of the dRNG from the protocol. The proposal also comes with some drawbacks, primarily that it requires a lot of past cone walks. But there may be a way to overcome these inefficiencies with the tools already provided by the parallel reality ledger state. These ideas are based on my own amateur reasoning about OTV without any formal mathematical proofs and I’d love to hear feedback and criticism from the community.

In the original description of OTV nodes use a strong reference to communicate which branch in a conflict set it prefers and a weak reference to approve valid messages that accidentally voted for the branch it dislikes. In the following approach, however there are no weak or strong references or special references of any kind — the tip selection and the voting process are entirely separated. A node simply selects whatever tips its wants and its opinion is derived from the past cone of the message it sends. This opinion is found in such a way that everyone eventually agrees on the perception of all nodes and all nodes necessarily follow the heaviest branch and achieve consensus.

To begin it first helps to think of the Tangle as a communication medium which also communicates recursively about itself. When a node issues a message it is also making a second order statement “I have seen all the messages in the past cone of my message.” Because those messages have the same property, this node is also making a third order statement “I have seen that all the nodes who issued messages in my past cone have seen all the messages in the past of their messages” and so on. Due to its unique structure the Tangle always broadcasts with each message implicit information about what each node knows about what other nodes knows about what other nodes knows about … the Tangle.

This self-reflexive property of the Tangle means that every message which references a conflict set, directly or indirectly, is also making a statement about a nodes perception of everyone else’s perception of everyone else’s perception … of the conflict. This version of OTV reaches consensus using only this information which is already available in the Tangle.

More concretely the rules of this voting process are as follows:

Every message in the future cone of a conflict set can be considered a vote which expresses the issuing nodes opinion on the conflict set (which branch it prefers). At a given moment the Tangle can contain many different messages from the same node that express conflicting opinions. It is only important that all nodes agree on the opinion expressed by an individual vote.

If a node broadcasts a vote that has no other votes in its past cone it, the vote is booked into the branch corresponding to the conflicting transaction it references directly or the branch with the lower lexicographic hash, if it references both transactions.

Otherwise the opinion expressed by a vote N is found by walking through its past cone, counting all the opinions of each node whose votes appear in its past cone. Vote N is then booked into whichever branch appears to have more approval weight, according to the votes it “sees” in its past. For this reason every vote automatically follows the heavier branch, at least according the perception of the Tangle expressed in the past cone of that vote.

If the past cone of vote N contains multiple votes from the same node A, vote N’s perception of node A’s opinion is found by walking through the combined past cones of all node A’s votes, deriving node A’s perception of the heavier branch in the same manner. For this reason nodes are free to broadcast multiple conflicting opinions because they will eventually be resolved in the same way by all nodes as the conflicting perceptions receive more confirmations.

With these simple rules, every message is booked into whichever branch it perceives to be heavier, which can be discovered in the same manner by every node: by simply counting up the votes already booked in the past cone of a nodes message. Because every node automatically follows the heaviest branch, every node eventually agrees on the perception of every other node, and all nodes eventually follow the same branch. Regardless of the way nodes select tips we are only using the implicit statements nodes are already making about their own perception of the tangle: “I have seen that these nodes have seen this conflict and perceived this to be the heaviest branch because they have seen that these nodes have seen …” and so on..

This approach has some interesting side effects. First of all it completely decouples tip selection from voting, because the “opinion” expressed in a node’s vote is derived from its own perception of the Tangle which it has published to the Tangle. There can be no dishonest voting because a node cannot “lie” about seeing a part of the Tangle, nor can it “unsee” a part of the Tangle of has already publicly claimed to see. So every nodes vote is automatically a vote for the heaviest branch no matter which tips it selects, and eventually all nodes agree on which branch is heavier.

OTV works because it recognizes that the Tangle can contain conflicting versions of the ledger state which are eventually resolved. This approach makes a subtle addition to that principle by recognizing that the Tangle can contain conflicting perceptions of nodes opinions on the conflict which will also eventually be resolved.

I believe a knock on consequence of this approach is that a metastability attack is impossible. I cannot prove this mathematically, but it seems that in a system where every node automatically follows the heavier branch consensus would be inevitable, as this is the definition of honest behavior. Furthermore an attacker can only switch branches if it can approve previously unseen messages which justify its opinion change — so an attacker trying to hold the tangle in a metastable state would be unable to switch between branches arbitrarily.

The Perceptual Branch DAG

The main drawback of this approach as I’ve described it is of course that it requires many recursive walks through many past cones, which could become very difficult. However, in the same way that the “parallel reality ledger state” is able to handle conflicting versions of the ledger state, I believe its basic tools can also be used to track different perceptions about the state of such a conflict.

On top of the regular branch DAG you could have something like a “perceptual branch DAG” which tracks nodes perceptions of the branch DAG. This sounds a bit outlandish but I think it is less cumbersome than it sounds.

Let’s say the red node casts a vote for Branch A. You would then create a new sub-branch of A called A.Red.1. This sub-branch tells you the red node voted for Branch A with message 1. Every message which approves that vote is booked into the same sub-branch, basically saying it has seen the red node voted for Branch A with message 1. New votes from other nodes will also create their own nested sub-branches of A or B, so that by looking at all the sub-branches a message is booked into, you can tell immediate which nodes it has seen voting for which branch and derive its opinion based on those votes in its past cone.

Now if the red node broadcasts a second vote that directly or indirectly approves its previous vote, you would book it into all the sub-branches of its parents, but instead of booking it into the A.Red.1 branch you would book it into a new sub-branch called A.Red.2. This way the number of sub-branches a message can belong to is bounded by the number of nodes voting on the conflict, to prevent the number of sub-branches you need to track from ballooning to infinity.

Now say a message has one parent that was booked into A.Blue.1 and another parent that was booked into B.Blue.2, inheriting two conflicting perceptions of the opinion of the blue node. To resolve this conflict you would look at blue nodes first message and the blue nodes second message and derive a new opinion for the blue node based on all the sub-branches which contain either of the blue nodes votes. The new message can now be booked into a sub-branch called A.blue.(1,2) with an updated opinion for the blue node.

Described another way, each message is just recorded with a list of the previous votes used to derive it’s opinion and that list is never longer than the number of total nodes in the network. A message can inherit this list from its parents so there are no past cone walks. And you can also quickly merge multiple votes from the same node into a new single opinion. Tracking the various perceptions of the state of the conflict in this way you would always see which branch every message belongs to, along with all the messages upon which it’s opinion is based.

Although this approach to consensus uses a slightly different way of thinking it is actually quite simple and draws on all the same core concepts of OTV. I think the simplicity of this approach also comes with increased security — as anyone who writes to the Tangle will necessarily vote for the heavier branch, and therefore contribute to consensus. Using nothing more than the Tangle, random tip selection and the parallel reality ledger state you can find consensus that already exists in the Tangle, as if consensus were not a matter of controlling the Tangle but simply listening to what it has to say.