I initially posted this as a follow up to my last post, but I felt the ideas presented here are different enough, that they should be presented and discussed separately.
On tangle voting is based on the idea that when presented with conflicting versions of the tangle, a node should ‘vote’ for the version of the tangle it perceives to be heavier (based on the weight of the mana which approves it), by attaching transactions to that version of the tangle. It’s a simple voting mechanism that is communicated directly in the data structure of the tangle.
A corollary of this principle is that a node should not vote for the reality it does not prefer - the reality with lower mana approval weight. It seems obvious, but this kind of dishonest voting is precisely what allows a meta-stability attack to take place, when an attacker uses its mana weight to switch from a heavy reality to a lighter reality and then back again.
If we can enforce honest voting decisions, that is, a rule that nodes can only vote for the reality it perceives to be heavier, we could prevent any metastability attack from arising, regardless of the attacker’s mana.
Below I’ve tried to sketch out a method to require all nodes to provide proof that they are voting honestly, based on their local perception of the tangle, whenever they update their opinion within the OTV / Multiverse framework. Much like OTV itself, these ‘virtual proofs’ require no extra message overhead, but are expressed in the structure of the tangle.
When a node updates its opinion on a conflict set by attaching a transaction to a given reality, that transaction also attests to a certain partial perception of the weight of that reality, at the time the transaction was issued. This “perceived reality weight” can be calculated by walking the past cone of the opinion update transaction back to the conflict transaction at the beginning of the reality sub-branch. If a node strongly likes a given reality, we can be sure that that node perceives the reality to have at minimum, the approval weight contained in the past cone of the node’s transaction.
We could implement a simple rule, that when a node issues an opinion update transaction on a conflict set it must ‘prove’ that is has voted for what it perceives to be a heavier reality. So, when changing opinions, a node would be required to strongly like the new reality in such a way that the ‘perceived weight’ of the newly preferred reality, measured by the past cone of the vote issuing transaction, is heavier than the ‘perceived weight’ of the previously preferred reality.
Stated slightly differently, when a node updates its opinion it must reference, through weak or strong references, the other transactions which prove its perception of the weights of both realities at the time of the update. This proof should be easy for honest nodes to perform, as well as to verify, by simply walking the past cone of the update transaction back to the conflict origin. (In reality, this may require no new walk, since multiverse already keeps track of reality weights). However, this proof would be difficult, or impossible, for an attacker who is trying to change its opinion from a heavy reality to a light reality during a meta-stability attack.
An attacker attempting to keep the tangle in a meta-stable state could try to attach to old parts of a given reality during an update transaction, attempting to provide a false perception of the weight of the conflicting realities as proof that its vote is honest. To prevent this, we could add another rule, that when a node updates its opinion, it must also reference all the previous transactions it issued on the conflict set in the past cone of the update transaction. Because nodes advance a counter each time they update their opinion on a conflict, this criterion can also easily be checked by walking the past cone of the opinion update transaction.
This would mean an attacker would be forced, at minimum, to directly reference all its older updates. In a situation where an attacker is attempted to vote for a reality with a lower weight (Red), it would need to reference transactions that both reference all its previous transactions, and offer a perception that the heavier reality (Blue) is in fact lighter. The only transactions which could possibly do this would be an honest transactions by another node that arrived at a different local perception of the tangle than the attacker, and changed its opinion from Blue to Red. If the attacker followed this opinion, she would be voting honestly, and no longer carrying out an attack.
Post-script
On further reflection, it may be that you only need the first rule, requiring a node to prove it is attaching its opinion update to a heavier reality, if you consider all of a node’s previous votes as part of its proof.
Here is a simple attack scenario to demonstrate the point:
An attacker has 30% of the active mana and votes on the first Blue transaction. This vote also proves that it perceives the Blue reality to now have at least 30% of the active weight (its own mana).
If the attacker wants to change its opinion to Red, regardless of timing, it has to attach to Red somewhere that proves that it has a perception that Red already has at least 31% of the mana weight at the time of the vote. And once it changes its opinion, it also confirms its perception that Red has 61% of the weight (the old weight, plus the weight of its transaction).
In order to change opinion again it would need to prove that it has a perception that Blue has 62% of the weight, and then would immediately push the Blue reality to 92% of the weight with its vote. It should also be noted that for this switch to Blue to be successful, at this point, the attacker would have to prove that honest nodes, whose mana it does not control, updated their opinion to prefer Blue oustide the perception of all of its past votes (otherwise those votes would have already been represented in its proofs. And it is impossible for the attacker to prove that its own mana has switched sides, before actually doing so!). If this were the case, and the attacker is able to switch to Blue would no longer represent an attack, but the behavior of an honest node, following the activity of other nodes, who have their own asynchronous perception of the ledger state.
To put it all in more concise terms: let’s define the “perceived reality weight” of a transaction as the sum of the mana weight contained in the past cone of a transaction, up to the origin of the reality in which the transaction is issued.
If a node issues transaction X, attaching it to reality A, and then updates its opinion by attaching transaction Y to reality B, it must attach to reality B at such a point that the perceived reality weight of transaction Y is greater than the perceived reality weight of X plus the weight of the transaction X itself.
The advantage of this approach, if it does work, is that it is incredibly simple, and like OTV itself, the proofs of honest voting are objectively expressed in the tangle with no additional message overhead.
Thanks for the detailed response, I’m actually very excited about this idea, now when I get it right. Can’t wait to hear what others think about it.