In my previous post I described an approach to On Tangle Voting where every message is considered a vote. The opinion expressed by each vote is derived by counting the opinions it has “seen” in its past cone and assigning a message to whichever branch has more approval weight according to this calculation. Because a node’s opinion is found implicitly by reading whichever part of the Tangle it confirms, a node can only ever vote for the heavier branch. This enforcement of honest behavior should mean that a meta-stable state can never persist indefinitely, as every time a node publishes a message to the Tangle it necessarily contributes to consensus.
However, the only way I could imagine implementing such an approach is with lengthy past cone walks, or by storing each message with an opinion vector that records the opinion of every other node. What follows is a variation on this idea with a much more lightweight and hopefully practical implementation that nevertheless seems to remove the need for a meta-stability breaker.
Just as before, nodes are not required to select tips in any particular way, nor are they required to publish their opinion explicitly with a “like” reference. Nodes just publish messages to the Tangle, and read consensus from the Tangle as it emerges. The additional computational overhead is a single 32-bit UInt stored locally with each message.
To understand how this would work, imagine a new message arrives with three parents, and you know the messages in the past cone of each parent contain a certain amount of approval weight voting for either branch in a conflict. Without walking the past cones of each parent message, you can never know how much these past cones overlap and therefore exactly how much approval weight the new message has “seen” in either branch.
However, you can always assume that the new message has seen at a minimum the heaviest branch weights seen by any of its parents. For example, message 4 has seen at least 110 approval weight voting for branch A and at least 80 for branch B (even if the real distribution might be much different).
For example: the node issuing message 4 has seen at least 110 approval weight in branch A and at least 80 in branch B.
Using this concept of a perceived “minimal branch weight” you can build a voting mechanism that follows these basic rules:
1. Every message in the future cone of a conflict set is considered a vote on the conflict set.
2. If a vote has no other votes in its past cone, it is booked into the branch of whichever conflict transaction it references directly (or the one with the lower hash if it references both). The vote is also booked with a “minimum branch weight” value, equal to the approval weight of the issuing node. (This value only needs to be recorded for the winning branch.)
For example, Node Z has voted for Branch B, with a minimal branch weight of 10, equal to the node’s own approval weight.
3. If a vote references previously cast votes, you compare the “minimum branch weight” of all its immediate parents and the previous vote of the issuing node (if it exists). The new message follows the opinion of the parent messages with the highest “minimum branch weight.”
4. A message inherits the “minimum branch weight” value from the parent message it follows (which can also be a node’s own previous vote). If the issuing node has never voted for that branch before, its own approval weight is added to the “minimum branch weight” value. (i.e. a node’s own weight is added to the “minimum branch weight” when it first casts a vote and if/when it first switches opinions to the other branch).
For example, Node Q sees that Branch B has a minimal branch weight (40) greater than Branch A (20). It’s message is booked into Branch B, and inherits the minimal branch weight from the blue message (40), plus its own weight (120).
In this approach, any nodes who see the same messages will come to the same perception of the “minimal branch weight” assigned to a given message, and therefore of the opinions of all other nodes. Opinion formation happens “on Tangle” so whenever a node issues a message, it has no choice but to vote for the heaviest branch and advance consensus. And the minimal branch weight value is bounded by the total approval weight voting in the conflict, so eventually one branch will be the winner, or in the case of a tie, nodes will prefer the branch with the lower hash.
When one branch is winning, the only nodes who can vote for the losing branch and effectively increase its minimal branch weight are those nodes who have both a) never voted for the losing branch before and b) whose most recent vote contains a perception of the winning branch weight that is less than the heaviest published perception of the losing branch. As this list shrinks, there is a moment where the total approval weight available to vote for the losing branch is small enough that the branch weight of the losing branch can never surpass the winning branch and voting is terminated.
One odd thing about this approach is that nodes are not actually voting on “which branch is heavier” but “which branch is heavier going by whatever you can measure without doing a past cone walk.” However, the result is the same — all nodes eventually agree to follow the same branch, so the branch with the highest “minimal branch weight” ends up being the one with the most absolute approval weight when voting is complete. In effect, this voting system uses the minimum branch weight as a representation of each node’s unique perception the state of Tangle — an incomplete image that stands in for the real thing. Nodes vote on this representation, but in so doing the Tangle and its representation end up identical to one another.
Addendum
After some discussions with Luka, it became clear that there is at least one scenario (although extremely unlikely) in which an attacker could theoretically stall consensus, even with a very small amount of approval weight. Because the termination of the voting process depends on both a) the difference between the minimal branch weights of both branches, and b) the total approval weight available to vote for the losing branch, there could be a situation in which, through some kind of network layer manipulation or through sheer chance, that both branches end up relatively close to each other. If, for example, by the time all honest nodes have voted, Branch A has a minimal branch weight of 100, and B has one of 80, and attacker with 30 (around 23% of the total weight) can simply stop voting. Or create a situation where both branches are equal to each other, the cast votes very slowly for either side with very small voting weights. In either case, the attacker has full control on when and if the voting terminates.
However, in the situation where a node switches its vote from branch A to to branch B, if you had a way to subtract that node’s vote from branch A, you could prevent this situation from arising in the first place, and guarantee consensus, regardless of an attacker’s cMana.
For example, in the diagram below, Node X has first voted for branch A, but then approves a message which changes its opinion to branch B. You can store with this message one more integer, which reflects the approval weight that Node X withdraws from Branch A. Now Node X, and any node who confirms this message, will only be able to vote for Branch A if it can find a message that has a perception of the weight of Branch A which is greater than its current perception of Branch B plus 20.
The voting rules follow the same procedure as above, with the difference now that a node’s voting weight is applied to a branch every time it switches sides, and simultaneously subtracted from the branch it rejects. This can be handled with a similar voting logic which only requires consideration of the parent messages of each vote:
When a message arrives, you look at all the parents of the new message. From the branch weight perceptions of each parent, you find the highest branch weight for branch A and branch B. You also find the largest negative branch weight (in terms of absolute value) for branch A and branch B. You combine these values — subtracting from A the negative branch weight for A, and the same for branch B.
Following this calculation, the message is booked into the heavier branch, inheriting both the largest “minimal branch weight” of the winning branch, and the lowest “negative branch weight” of the losing branch. If a node has changed its opinion from its previous vote, its own weight is added to the “minimal branch weight” value.
For example, in the picture below, Node Q votes for several message with different opinions positive and negative branch weights. To find the Node Q’s opinion you sum the highest and lowest values of A and B seen by any of its parents and discover that A has a branch weight of 30, and B of 0. Node Q follows branch A, and inherits the highest branch weight for A(45), and the lowest branch weight for B (-40). Because Node Q has never voted before, its own weight is added to the branch weight for A.
With these rules, I can think of no situation in which the network does not converge because if an attacker tries to stall consensus by switching sides, they will forced to always vote for heavier and heavier parts of either branch, until they are unable to do so.