"Zero-Message" OTV with approximate consensus on validator weights

[b0rg]

Below is a modified version of a “zero-message” on-tangle voting algorithm I discussed on discord, adjusted so that it does not require total agreement on the validator weights and should still prevent a meta-stable state from appearing in the Tangle.

In this approach, every message is considered a vote. Nodes do not communicate their opinions explicitly with a “like” reference. Instead, every message is booked on arrival with a “master branch weight” integer, which represents a partial, but globally agreed upon perception of the approval weight in each message’s past cone. The opinion expressed by a vote is always derived deterministically by following the opinion of whichever parent message has “seen” the most approval weight in its sub-branch, so the voting cannot be held in a meta-stable state.

The proposal makes at least one major assumption, however: An honest node must always issue messages as close as possible to the maximum rate allowed by its aMana - and nodes who do not vote, or who vote too slowly will have their aMana decayed until it matches their lower voting rate.

.

The voting algorithm runs as follows:

Every time a message is published it’s booked with a “master branch weight” integer, equal to one plus the highest branch weight booked with any of its parents (including the issuing nodes last message).

If a conflict appears in the Tangle you can resolve it with this simple procedure:

1. Book conflicting transactions into their respective branches. Advance the branch weight counter as usual for each of the transactions, and all future message.s

2. If a message has parents in only one branch of the conflict set, book the message into that branch.

3. If a message has parents in both branches, it inherits the opinion of whichever parent message has the higher master branch weight value. (I explain below why this value always correlates to the sub-branch with the most overall approval weight)

In the case of a tie a message will be booked into the sub-branch with the lower hash.

The voting process is quite simple as can be seen in this example:

This voting process will scale to an unlimited number of conflicts because this single branch weight value can be used to vote on an unbounded set of conflicts. Voting is Sybil protected because is governed by the rate control, so nodes can only vote in proportion to the amount of mana they hold. And even without any strict agreement on the validator weights meta-stable states are ruled out as voting is always “honest.”

---

Here is some of my reasoning for why this algorithm will guarantee eventual agreement:

In this approach nodes are assumed to issue messages at the maximum allowed rate. Therefore, a node’s approval weight is understood as the amount of times a node “observes” the Tangle over a period of time relative to other nodes active in the network - a rate proportional to the node’s aMana.

Assuming a node issues each message with a reference to its previous message, you can walk through a message’s past cone, and count the number of messages it has “seen” from every other node and arrive at a perception of the global Mana distribution by comparing the relative rates at which each node has issued its messages. The total number of votes in a messages past cone gives a perception of the total combined approval weight of all the nodes. Over time, the more messages a node confirms, the more accurately will its past cone represent the current mana distribution in the network and the total approval weight in the Tangle.

For example, in the image below, the Green node’s most recent message records a perception that the green node has three times the aMana of the Red node.

During a conflict, when node follows the opinion of whichever parent message has seen the most overall approval weight in the master branch, nodes are implicitly following the opinions of the validators with the highest combined aMana - those who issue transactions at the highest combined rate.

As a result a node necessarily follows the branch with the most approval weight in terms of its own published perception of the Tangle. A node cannot switch from the winning branch to the losing branch, unless it can confirm a message from another node that has both a) confirmed more messages overall and b) voted for the losing branch. The only attack vector open to a node is to accumulate a lot of mana and then to not vote and prevent consensus.

But in this approach voting rights and access rights are equivalent, so an “active” validator is just one who is currently voting at the rate allowed by its aMana allocation. If a validator starts writing to the Tangle at a slower rate, its aMana is decayed until it matches the rate at which the validator is voting, and other honest nodes will increase their relative portion of network throughput. This means that eventually the percentage of active validators issuing statements will approach 100%, and all validators will necessarily issue honest statements.

[b0rg]

A short follow up: I think it may be possible to make this voting algorithm secure without forcing the network to always run a full capacity.

As long as a node always confirms whatever honest nodes agree (more or less) to be the most recent part of the Tangle, it will not matter at what rate that node issues messages. A node that confirms the most recent messages of the Tangle will necessarily inherit the perception of all messages that have come before and will be algorithmically prohibited from rolling back anything that has already been confirmed. You can use the approval weight counter in combination with the rate control to ensure that nodes who do not continuously confirm the newest parts of the Tangle will gradually have their write access revoked. Nodes would then be able to issue messages at any rate, only limited by their aMana in times of congestion.

The approval weight counter gives you a perception of a) how fast the tangle is growing and b) the amount of time passed between one message and another. For example, if the most recent message I have seen has an approval weight of 200, and the last message I have seen from the Blue node has an approval weight of 100, and I know the Tangle is currently growing at roughly 100 units of approval weight per second, I can limit the maximum write access of the Blue node to 1 MPS. The longer the Blue node only confirms old messages, the more it’s write access will be throttled until the moment it confirms a recent message.

This logic, which says that a node can only ever write messages to the Tangle at a speed proportional to the distance between its last message and what the network more or less agrees to be the most recent messages, will ensure that a node can never create a branch that will outgrow the master branch and roll back a transaction. But honest nodes will only ever have to confirm the most recent messages they have seen and they will be able to write to the Tangle at any rate they want, limited only by their aMana in times of congestion.

This principle, if it could be implemented in the rate control, is a essentially a way of forcing a node to prove it is in sync as it writes to the Tangle, that it shares a roughly similar perception of what is the “present.” A malicious or faulty node who only writes to older parts of the Tangle will gradually be removed from the network as the Tangle grows and its rate limit simultaneously approaches a level so low that all messages it sends will be considered spam and it will be blacklisted.

Here an active validator is one who is provably in sync with the rest of the network. Voting in this way would be 99.99% Byzantine fault tolerant, as all nodes would necessarily vote honestly, and the percentage of active validators issuing statements always approaches 100%.