After following many discussions on discord and Ioda’s excellent post, I wanted to contribute a few thoughts I’ve had on the meta-stability question that approaches it from a slightly different angle. These are just the thoughts of an enthusiastic amateur, so I apologize if there are any gross misconceptions. I hope there is something useful here that will contribute to the overall conversation.
One question about on-tangle voting is the possibility of a meta-stability attack, where an attacker prevents the network from converging on one of two conflicting sub-branches. In this post I will try to describe a mechanism to prevent this kind of attack by controlling the rate at which an attacker can change its opinion.
The Attack
Say an attacker with p percent of the active mana in the network (where p is under 50%) wants to keep the network in a metastable state, by preventing any branch in a conflict set from getting more than 50 + p percent approval weight. I.e. an attacker with 30% of the active mana, would have to prevent either branch from tipping past 80% approval weight, after which point, the attacker’s mana alone is not sufficient to prevent the network from converging on a single branch.
As the attacker alternates votes between sub branches, it probably wants to keep the maximum weight of either branch as low as possible, and consequently, the minimum weight of either branch as high as possible, to minimize the chance that the heavy reality becomes too heavy, and slips out of its control. In practice this would mean an attacker would try to keep the realities oscillating between approval weight ratios of (50 + p/2)/(50 - p/2) and (50 - p/2)/(50 + p/2) or 65%/35% and 35%/65% in the example above. This strategy maximizes the ‘wiggle room’ the attacker has to work. The more mana an attacker has, the more flexibility it has in the attack.
Thinking through this further, one way an attacker can approach this is to get both realities close to the best initial conditions, and then issue approvals of both realities, one after the other, as quickly as possible. The goal would be for an honest node to have a roughly equal chance of voting for one or the other reality, depending on which confirmation coming from the attacker it sees at the moment when it forms its opinion and issues its next update. Based on the attackers own knowledge of the behavior of other nodes, network delays and the opinion updates it receives from the rest of the network, it would try to modulate the speed with which it changes its opinion to keep the balance of both realities slipping away from this position of optimal control.
More concretely, let’s say our attacker with 30% of the mana sees that both branches are moving away from meta-stability at 65/35 : 35/65 toward 70/30 : 40/60. Once the approval weight ratio between branches swings to a 40/60 balance, the attacker would then slow down its opinion change rate slightly, until it saw the balance return to the ideal 35/65 ratio, and then resume updating its opinion as quickly as possible.
The key point is that the success of this approach depends on the attacker being able to issue opinions very rapidly, and having the time to adjust its opinion change rate as it observes the behavior of other nodes. Even if the attacker had perfect knowledge of the opinion of every other node and the exact timing of every node’s opinion updates, and even if it could update its opinion at precisely the right moment to keep the network in at perfect equilibrium, the attacker would still be constrained by time in order to carry out this attack. She has to have the freedom to issue updates at the right moment, and without waiting too long for consensus to converge.
The Time-Out Rule
A time-out period that limits the rate at which a node can change its opinion could make it very hard, and perhaps impossible, for an attacker to keep the network in a meta-stable state. Assuming fairly consistent network delays among higher mana nodes, the time-out period would force nodes to update in a semi-synchronous fashion and break the meta-stability of the tangle. My first impression is that the optimal duration for the time-out period would have to do with the time it takes for a transaction to propagate through the network.
The simplest implementation of a time-out rule would be to require a node to wait a certain amount of time t before it can issue a transaction that updates its opinion on a given conflict set. If two conflicting realities are present in the tangle, Red and Blue, a node can strongly like a transaction in Red, but must wait time t before it can issue a transaction that strongly likes Blue. Honest nodes would just compare the local time stamp of an opinion update with the timestamp of the previous opinion update to determine if the transaction is valid.
This can be roughly enforced through local time stamps because honest nodes won’t accept new transactions that are farther in the future than their own local time. If a malicious node tries to cheat by issuing an opinion change earlier than allowed with a falsified late timestamp, the update would not be picked up until honest nodes clocks catch up to the time marked in the fake time stamp.
Another element which may make the time-outs more effective would be to have honest nodes express their opinion on a conflict as soon as possible within the constraints of the timeout rule - either through issuing normal transactions, or by issuing a special non-value statement, which expresses an opinion update, as soon as time t expires. This might reduce some of the randomness which makes things difficult for an attacker, but it would ensure that as many votes as possible are registered in the network before the attackers time-out period expires.
There are also variations on the basic rule which might make it more practical. For example, the timeout periods could increase arithmetically with each round, so that nodes would have to wait longer and longer periods to update their opinion. Or the time-out rule could come into effect after a certain number of initial updates. The idea here would be that the time-outs would only really start to slow down consensus if metastability persists for a long enough period of time. This way, the time-out rule works as a kind of feedback mechanism that forces the network into more rigid synchrony the longer a metastable situation persists, but also allows on-tangle-voting to resolve conflicts on its own, if possible.
Attack Scenarios
Here is how I imagine some simplified attack scenarios playing out with the time-out rule.
Let’s say there is an attacker that has 30% of the active mana in the network who issues a conflict into the tangle, creating a Blue and Red reality.
One scenario would be for the attacker to wait for all honest nodes to set their votes, and take advantage of the fact that these honest nodes now have to wait time t to update their opinion.
- All honest nodes vote and enter a time-out period (49% Red, 21% Blue)
- The attacker votes for Blue (49% Red, 51% Blue) and enters a time-out
- The attacker must wait for time t while all the honest nodes’ time-out will expire.
Even in this optimal situation for the attacker, only 30% of the total active mana will have to move from Red to Blue before the attack becomes impossible (19% Red, 81% Blue) , which in this case is about 60% of the honest nodes updating their opinions from red to blue.
Another approach might be for the attacker to vote right away, as soon as the conflict appears, hoping to affect the initial opinions of honest nodes.
- The attacker votes right after issuing the conflict (30% Red, 0% Blue)
- The attacker gets lucky, and honest nodes vote in such a way that the attacker has as much time as possible to change its opinion, at the exact moment the attackers timeout expires (51% Red, 49% Blue)
- The attacker waits for 28 % of the honest nodes to switch from blue to red and enter time-out (79% Red, 21% Blue).
- The attacker changes opinions (49% Red, 51% Blue) and enters time-out
- All of the honest nodes voting for red will exit their time-out period before the attacker.
This alternate strategy concludes in the same way as the first one. If the time-out is long enough for honest nodes to get fully up to date, they should be able to switch opinions while the attacker is still locked in Blue.
Conclusion
Assuming nodes broadcast their opinion updates as soon as possible, with a fairly consistent network delay, and assuming time t is long enough for these updates to reach most nodes, the timeout rule could prevent the kind of rapid, and strategically timed opinion changing which leads to a meta-stable situation.
I don’t have any kind of mathematical framework to model this, or to represent how factors like random network delays and packet loss would figure into a formal representation of this attack. I’m sure these simplified scenarios remove a lot of subtlety about how this would work in reality, and perhaps miss some key attack vectors.
But I think the basic observation that an attacker attempting a metastability attack needs to operate within some bounded time frame does lead to a conclusion that restricting the time within which an attacker acts would lower the success of such an attack.
One last observation - this approach removes some degree of randomness by trying to force nodes to update in a somewhat synchronous manner. My intuition says this could inadvertently make an attack easier, since the behavior of honest nodes becomes more predictable to the attacker. This raises the question if there is an opposite attack mitigation strategy that would involve injecting more randomness into the on-tangle-voting process. For example, if honest nodes notice that they are taking a long time to converge on a single branch, and they are changing their opinions a lot, they could start making their behavior less predictable by issuing ‘wrong’ opinions with some degree of randomness. This could also have the effect of making hard for the attacker to time its attack correctly and break the metastability.
Post Script
After posting this, another consideration regarding a the simplified attack scenarios above came to mind:
Imagine this setup:
- The attacker votes for Blue (49% Red, 51% Blue) and enters a time-out
If the attacker’s time out ends before greater than 29% of the active mana is able switch from Red to Blue, the attacker can wait for the precise right moment (21% Red, 79% Blue)
to switch (51% Red, 49% Blue). As long as under 29% of the active mana switches its opinion before the conlcusion of time period t, the attacker can keep the network in a metastable state.
This suggests that a time-out period, in order to be effective, must be long enough for the mana weight greater than the mana controlled by the attacker to update its opinion and switch sides.
I think this also supports the idea that a slowly increasing time-out period with each update could prevent any metastability attack, as long as the attacker has less than 51% of the active mana.