[Consensus Attack] Block withholding

[sternhenri]

Still need to think about Expected Reward

[sternhenri]

From an early sim run by @sa8 this attack seems to be a bigger deal than I initially thought. It affects chain quality (fairness).

Here is how you run it (straw man):

• Wait to see both you and honest parties getting blocks
• Start selfish mining, referencing all blocks
• Release after some time.

This will sometimes work due to the "headstart" the adversarial miner gets. Specifically because of block withholding, the attacker gets to count both their and the honest parties' blocks in the first round of the attack, whereas the honest miner can only look at their own. This assumes that the adversarial miner will "drag" and wait as long as possible to release their blocks in case an attack is possible.

For reference, this attack is due to the "headstart" and doesn't apply to a longest chain protocol, but rather to GHOSTy ones. PHANTOM and Fantomette avoid this (numbers to be computed) through their variant of the Tipset rule, i.e. blocks can refer to other blocks across chains, i.e. here, the honest miners can start referring to adversarial chains after the withheld chain is released, thereby mitigating the attack (honest miners' blocks are accepted after all), with anticone rules getting the adversary rejected (thereby reducing adversary earnings -- fuzzy on details here).

@sa8's sim shows that this attack pays off pretty well:

• With 51 honest miners and 49 dishonest (all equal stake -- with collusion, so a block of 49% of power), on a sim run for 25 blocks and the attack starting on the first round in which both parties mine a block (so typically around rd 5/6) --> attacks pays off 53% of the time. (Over that duration with these proportions the honest miner should only have .5 blocks more on expectation, so not enough to make up for the headstart).
• With 70-30 split to honest, run over 13 rounds, the success rate is still 17%.

We can imagine a smarter attack that makes things worse:

• Adaptive release: the attacker releases as soon as they see the honest chain catch up to them, rather than after some set number of blocks.
• Making use of available data: eg with a lookback param, the adversary can time the attack start based on whether they will win future rounds.

There might be an argument that this attack is hard to pull off with a perfect VDF and no lookback but I don't quite see it.

[sternhenri]

Conversation around this yielded a few things:

• Short term attack, effect fades with length. Not a finality issue. Only chain quality

While the headstart issue is particular to EC (due to how tipsets work), a mitigation will have to be a fix for block withholding as a whole given the "headstart" can't be tackled on its own without risking punishing honest miners.

Some mitigation ideas:

• Use PHANTOM-like notions of anticone to punish miners/blocks based on network interconnectedness. (eg through slashing or weighting)
• Move to either more GHOSTyness (eg adding PHANTOM/Fantomette like chain referencing) or pure longest chain (eg adopting Praos method given long range attacks are not an issue for us).
• @ZenGround0 may have other suggestions...

[sternhenri]

• Touch up leader election to lead to fewer than 1 on expectation: hurts liveness, but decreases chance of there being a headstart in the first place.

[ZenGround0]

Spitballing other mitigation strategies:

• address block witholding in a "longest chain" way using some variation of fruitchains
• use some kind of heuristics in our chain selection rule to address headstart behavior. This falls under the same general category as "weighting function" work. See for example bitcoin's "take the first block of a given height that you see", the selfish mining papers "flip a coin and choose a fork at random" modification, and most relevant to this scenario @whyrusleeping's thoughts on ignoring late comers from long ago. In general this kind of direction seems error prone and hard to reason about safely.

[bvohaska]

^ @ZenGround0, @nicola, @sternhenri: sounds like a good candidate to tackle next week ;-) I'd love to help formalize this and build an "attack and mitigations" catalog.