Breaking metastability in the Tangle Multiverse with proof of honest voting

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.

1 Like

Here is a diagram, which hopefully makes this concept more clear.

I also want to add a small observation that is suggested by these kind of virtual proofs:

The tangle is not only a medium for communicating what a node’s perception is (that a certain reality is heavier), but it also communicates recursively what a node knows about the perception of other nodes (and their knowledge, and so on…). This is because the choice of where a node attaches its transaction is inherently a statement to the rest of the network of the nodes local knowledge of the opinions of others in the network. It is because the Tangle has this property that nodes are able to look at the Tangle itself to confirm the honesty of other’s statements. This ability for every participant in the network to come to an understanding of what everyone else knows is how consensus is achieved.

1 Like

Hi b0rg!

Very interesting approach there! I think this proposal would indeed make it harder for an attacker to balance a conflict. Yet, I also think an attacker might have a method to avoid restrictions caused by this approach.

I try to describe it first with a simplified scenario and then expand from there:

Let’s say we have two conflicting transactions A and B. They are both broadcasted to the network at the same time, and the initial situation with given votes is 50:50. To simplify the example, lets assume that honest voters stop their voting for a moment. Also, the attacker has not yet voted in the conflict.

If the rules you described would be flawless, the attacker could vote for A or B, but he shouldn’t be able to vote first A, then B, and back to A. Especially, he should not be able to continue this forever.

In the example below an attacker uses three nodes to constantly flip his voting opinion from one side to another. We count here the attackers “total voting opinion”, i.e. combined voting weight of all of its nodes.

reply

We read this graph from bottom to up.

  1. First transaction x votes for side A and uses honest transactions as a proof of his view of the situation. (He could reference just part of honest voters’ transaction from side B, to prove that he is voting for a heavier side).
  2. The transaction y votes for side B, and ignores transaction x claiming that it has not “seen” it. It also uses honest transaction to create his proof of the view of the situation.
  3. Transaction z votes for A and claims that it has seen transaction x, but not transaction y.
  4. Transaction x changes its side to B and claims that he has seen transaction y, but not transaction z.
  5. This can go on forever, as can be seen. The numbers demonstrate how attackers overall voting influence flips from side to side.

Now what would happen if honest voters would vote actively during this example? The attacker would get more stepping stones to balance the situation and could do it more efficiently. Also, the attacker could control 100 of nodes and there could be 100 conflicting transactions not just A and B.

Generally speaking, I think that a clever attacker can be indistinguishable from an honest voter in on Tangle voting, so it is very hard to create rules that would always distinguish attackers.

On the other hand, the proposal makes attackers job harder and doesn’t add any additional message overhead.

One thing I’m also thinking is, how this affects to tip confirmation rate?

What do you think about these thoughts?

1 Like

Ioda - thanks for this thoughtful reply. This is not an attack I had considered and its quite interesting. However, after going through it in more detail, as far as I understand what you have presented, I think the attack will not succeed.

Just for the sake of clarity, I want to restate a few things about the general principles here, and make one important point:

Let’s say a node X updates its opinion from Red to Blue. The first opinion is contained in transaction one at t=1, and the update is expressed in transaction two at t=2.

When X switches to Blue at t=2, it has to prove its perceived reality weight for both realities, Red and Blue, as perceived at the moment before t=2.

The proof for the ‘new’ Blue reality is contained in the past cone of transaction two, minus any ‘negative weight’ contained in the past cone of transaction one. By “negative weight” I mean transactions which show an opinion change away from Blue to Red, which are visible in the past cone of transaction 1 in the ‘old reality’

However, the proof for the Red reality, consists of the past cone of transaction one plus the mana weight of X itself, and minus the ‘negative weight’ contained in the past cone of transactions made by X in the Blue reality earlier than time = 1 (if they exist).

The key thing is that at the moment the proof is issued, the proof of the weight of the old reality also contains the weight of the node itself, since that weight must have been included in the old reality, before the moment of the update. I think this may have been missed in your calculation.

With that clarification, I tried to walk through your scenario step by step to make sure I got all the points. I hope I’ve understood it correctly. - I’ve set all of our attackers nodes to have no initial vote on any reality, to give the attacker the most flexibility for switching sides

X has mana 2
Y has mana 3
Z has mana 3

Time =1

None of the nodes have voted yet

X currently perceives reality B to have a weight of 0 or
X(t=1, B) = 0

Y perceives reality A to have a weight of 0 or
Y(t=1, A) = 0

Z perceives reality B to have a weight of 0 or
Z(t=1, B) = 0

Time = 2

  • X casts a new vote for reality A

  • X now perceives reality A to be 0, plus its own mana weight, or 2

  • X(t=2, A) = 2

Time = 3

  • Y casts a new vote in reality B.

  • Y now perceives reality B to be 0, plus its own mana weight, i.e. 3.

  • Y(t=3, B) = 3

Time = 4

  • Z casts a vote for reality A and with a past cone that includes transaction X(t=2, A) = 2

  • By including X(t=2), Z sees X’s mana weight (2), which will be subtracted from any of X’s weight in reality B visible, in a future proof of Z. Let’s call this “available negative weight” and write it like this: ANW(B) = mana(X) = 2

  • In order to include X(t=2), Z must inherit X’s perceived reality weight of 2.

  • Z now perceives reality A to be 2, plus its own mana weight, i.e. 5.

  • Z(t=4, A) = 5

  • Z has ANW(B) = mana(X) = 2

Time = 5

  • X casts a vote for reality B, with a past cone that must be greater than 2, which includes Y(t=3, B) = 3 in its past cone.

  • X(t=5, B) = 5

  • X has ANW(A) = mana(Y) = 3

Time = 6

  • Y casts a new vote in reality A, with a past cone greater than 3, which includes Z(t=4, A) = 5

  • Y(t=6, A) = 8

  • Y has ANW(A) = mana(Z) = 3

Time = 7

  • Z casts a vote in reality A with past cone that must be greater than 5, and includes X(t=5, B) = 5 and Y(t=3) in its past cone.

  • Z(t=7, B) = 8

  • However, Z can deduct the mana from Y that’s in its past cone, so

  • Z(t=7, B) = 6

Note here that the deduction available to Z, only made the proof a little more difficult (although still successful), because reality A is now proven to be weighted 6 in relation to Z’s last perception of reality B at 5. Without the deduction, reality A is heavier and reality B is lighter, thus making the proof ‘easier’

Conclusion

Assuming I haven’t made any errors in my calculations, and my understanding of your proposed attack, going through this step by step shows, that even if the attacker starts in the most favorable initial conditions, the attacker nodes will be forced, through the requirement of proof of honest voting, to slowly vote on heavier and heavier parts of both realities, until they all eventually have to prove that they see greater than 50% of the mana to perform their next switch.

I carried the calculations a few steps further to show how even with the ‘negative mana weight’ a node gets by referencing earlier transactions, the nodes perceived reality weight still increases with each cycle of voting.

Of course, you could expand this attack over thousands of nodes, with an attacker constantly taking nodes offline and bringing new ones online, or sending mana around. But because the attackers mana is ultimately tied to the tokens it holds, it always votes with a bounded and unique set of mana weights, so over time, even a lot of mana spread over thousands of nodes, the attacker would be forced toward consensus. That doesn’t mean she couldn’t stall consensus for a long time though - as difficult as this attack might be, it does leave room to consider additional protective mechanisms, the aleph reference transaction you describe, or time delays and so on. These would be in place to help break metastability faster, in rare cases where it was necessary (assuming theses proofs work as I think they do).

There is one question which your scenario raises which is how to deal with a perfect 50:50 split. In this case, we could have one more rule, that if nodes perceived two conflicting realities, with a mana weight greater than zero, and the weights of both realities are equal, it should choose the reality whose origin transaction has a higher hashed value. This rule would also be checked in a proof, if a node moves from one 50% reality to another 50% reality. I think this small addition would break the 50/50 setup.

Regarding tip selection - for honest nodes it would be quite simple. Once an honest node receives a tip, which gives it the perception that another reality is heavier, it changes its opinion by referencing that tip. The proof would be guaranteed with this behavior. I did think there might be a benefit of having honest nodes reference all the tips it sees in a given reality during an opinion update, if there are more than one. This would ensure that proofs contain maximum information about a node’s current perception, which may help the network achieve consensus more quickly. I can’t say on a protocol side if making a node select tips in this way would have other tradeoffs.

1 Like

Hi,

I’m rarely this happy of being wrong. :wink: 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.

Another thing I’m considering though is how mana is measured in this system? If voters have even slightly different perceptions of mana, it might cause some nodes to consider a transaction correct, while other nodes could consider it incorrect right? Deciding whether a transaction meets your criteria is binary decision. Could this escalate small differences into major ones, if for example half of the network views some large mana holders transaction invalid?

1 Like

Sorry for taking so long to reply to this, but I’ve had some more time to think about this question.

I think you are right that you can’t rely on everyone having the same exact perception of the mana-state at the same time. Perhaps, rather than reject a message which does not pass the requirement of “proof of honest voting” a node should just not count the message as a “vote” toward consensus (i.e. consider the issuing node’s weight as being applied to the “old” reality and pick up the “dishonest” message with a weak reference). This way, different nodes can have slightly different perceptions of the “honesty” of a message but they will eventually agree (because they eventually see the same ledger).

So, if node A votes for what node B perceive to be a lower weighted reality, whether due to malicious behavior, or because both nodes have a slightly different perception of the mana-state, node B will just not apply A’s weight to the “new” reality it has voted for. Then, either node A gets some new information about the mana-state which it had not seen, and will adjust its opinion accordingly (switching back to the previous reality), or node B gets new information, and would then consider node A’s message valid, and apply node A’s weight to the reality it has voted for.

Basically, I think if you just calculated reality weights, and the “honesty” of a consensus vote based on your local perception of the ledger, but updated those calculations based on new information as it arrives, you should eventually align with all the other participants in the network.