Local Predictability's effect on attacks

[sternhenri]

This conversation came up in discussion with @whyrusleeping, discussing tradeoffs related to lookback parameters in the current EC construction and specifically the loss of local unpredictability (i.e. with a k block lookback for ElectionProofs, a miner knows they will win k blocks in advance).

The fears are of the following attacks, related to transaction censorship by colluding parties who know they will win ahead of time and can coordinate for runs of n rounds in which they win:

• Slashing censorship (to earn more by waiting before reporting faults, or prevent others from earning))
• PoST delays (and power table shenanigans)
• Ignoring other people’s blocks and mining off of lighter TipSets

Discussing this with @ZenGround0, we make a few claims:

• The attacks discussed above are not tied to collusion, in fact, it is both simpler and secure to think about powerful adversarial miners (with 30% of power, eg rather than 30% colluders) in our security model.
• We claim this is actually simply a form of selfish mining (though where not sharing the chain matters less): in order to successfully censor the chain, the miner cares about series of n blocks in which she has more than 50% of the network power (i.e. majority of blocks mined in a round).
• Even with local predictability, it's important to note that the malicious miner does not have perfect information: they cannot know when others will win a block (global predictability). In that sense, the lookback gets them better info (since they know when they will win) but not perfect info.

We believe the rational strategy for this attack in EC is as follows:

• When you know you will have >=50% of power over n blocks, run attack (i.e. ignore others’ blocks in your chain)
• when you have <= 50% don’t (i.e. allow others to mine heaviest chain and include their blocks so as to not lose power/reward).
• The Cost of messing up and running the attack with < 50% of power is you end up mining a lighter chain and lose out on block reward or, conversely (not running the attack when you should) you unnecessarily include others’ blocks when mining heaviest chain.

So the point here is that lookback param gets you better info, and a better estimate for your likelihood of being an effective 51% attacker over n rounds.

But point is that this attack gets you better info (when you will win), either way you don’t know when others will win (so no perfect info). But so less likely to mess up when you should run attack, i.e. better outcome. Thus the issue here is not actually a new class of attacks enabled by local predictability, but rather more cost efficient attack through better timing.

Can we quantify this gain? Yes, chernoff bounds help here (cc @bvohaska) and some of this work has already happened in the code/attacks section of this repo. @ZenGround0 will spend a bit of time trying to estimate what an attacker gains (ie the cost of having a lookback), while I finish the sim to motivate the lookback. @sa8 is also thinking about whether the lookback is worth the complexity it introduces into EC.

We can then make a rational decision about the construction.

[sternhenri]

Do you consider this launch critical @ZenGround0 ?

If so, could you help with it? or @bvohaska ?