In my last post I described a variation of On Tangle Voting in which every message is considered a vote and each vote’s opinion is derived by looking at the opinion of its immediate parents. Because each 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 means that a meta-stable state can never persist indefinitely: as long as nodes publish transactions to the Tangle, the network will necessarily converge.
This approach is relatively lightweight, but it required total agreement on validator weights. What follows is an adjustment to this voting scheme which eliminates the need for total consensus on node weights by considering each vote to have a weight of one. This would seem to require the network to always operate at maximum throughput, so nodes always vote in proportion to their aMana and to guarantee that malicious nodes cannot vote arbitrarily by spamming messages in times of low traffic.
But in this approach, as long as a node always references the most recent part of the Tangle, it will be algorithmically prevented from rolling back any transaction that is more than a couple seconds old. As a result, any node who issues messages at the front of the Tangle, regardless of the rate at which it issues messages, will necessarily vote honestly and contribute to consensus — so a node’s throughput need only be limited by its aMana in times of network congestion. I believe this can be enforced through the rate control, as I will explain below, by limiting a nodes write access to the Tangle in proportion to the amount of time which has passed between its last message and the messages which honest nodes agree to be the most recent part of the Tangle.
The vote algorithm is 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).
A node’s approval weight is measured by the number of times it “observes” the Tangle over a period of time relative to other nodes active in the network. This on-Tangle approval weight counter, which only ever advances, expresses a shared perception of the approval weight in the master branch, and the overall rate at which nodes are “observing” the Tangle.
If a conflict appears in the Tangle you can resolve it with this simple procedure:
- Book conflicting transactions into their respective branches and continue advancing the master branch weight counter for both transactions, and all future messages.
- If a message has parents in only one branch of a conflict set, book the message into that branch.
- If a message has parents in multiple branches, it inherits the opinion of whichever message has the higher master branch weight.
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. The voting logic of the parallel reality ledger is handled on arrival with each message, without having to track multiple branches and the opinion of each node in the network. And even without any strict agreement on the validator weights meta-stable states are ruled out as voting is always “honest.”
With this voting algorithm, 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. So as long as a node always confirms whatever honest nodes agree (more or less) to be the most recent part of the Tangle, a node will be free to issue messages at any rate it wants, limited only by its aMana in times of congestion.
Using the approval weight counter in combination with the rate control, you can ensure that nodes who do not continuously confirm the newest parts of the Tangle will gradually have their write access revoked and be unable to roll back a conflict:
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. If the most recent messages I have seen have 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 Blue node is free to continue confirming old messages, but the longer the Blue node only confirms old messages, the more it’s write access will be decayed as honest nodes perceive more and more approval weight building up in the Tangle.
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, ensuring that a node can never create a branch that will outgrow the master branch and roll back a transaction. But honest nodes will not have to do anything special - only 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%. In addition to this high security this algorithm could never be held in a meta-stable state. Finality times would depend only on the number of messages being issued per second, rather than the cMana distribution. And in times of extremely low throughout a node can always issue empty messages to finalize a conflict faster.
Just as the branch DAG introduces a way to track conflicting perceptions of the Tangle, this master branch weight counter introduces a way to track every node’s perception of the conflicting perceptions in Tangle, so that consensus emerges out of a recursive agreement on every validator’s perception of every other validator’s perception of …. every other validator’s perception of the Tangle. By the addition of this one integer to each message you get Nakamoto consensus on the DAG with two additional special properties: validators can only issue honest statements which always vote for the heavier branch and the number of validators issuing statements eventually approaches 100%
The Tangle is fundamentally a medium of communication. It is both a collection of discrete statements, and single ongoing statement about its own current state. By this I mean that each message communicates an implicit second order message which says: “Everything in my past cone is the current state of the Tangle.” If I see many of these second order statements that convey different perceptions of the state of the Tangle — i.e. how much stuff is in the Tangle currently — I will always prefer whichever of sees the highest total number messages — as that is the most “recent” (in a relativistic sense) and most comprehensive view of the Tangle I could have.
What is really going in this voting mechanism is that the approval weight counter propagates a perception of this second order statement with each and every message. So when I confirm three or four parent messages, I can compare which of these has seen the most of the Tangle, inherit its perception, and add the weight of my own message. By this incredibly simple procedure of always following the most dense perception of the Tangle, the one which includes the most first order statements, the second order statement that the Tangle makes about itself, will always be honest — and this is the definition of consensus. The Tangle is a medium of communication which is always also talking about itself — and it cannot lie.