Design Disputes Module

[rphmeier]

This module has three roles:

• Handling disputes of included parablocks during their acceptance period
• Signaling rollback of the relay-chain to a given ancestor (by number) when a parablock is bad
• Handling "roll-ups" proving that a parablock was found invalid on another fork of the relay-chain. These are used to ensure that misbehaving validators are slashed on all viable forks.

[rphmeier]

From Riot:

@burdges

Imagine bad block BB becomes available and executes in relay chain block R, which makes R bad too but innocently so, so the dispute starts in some dependent of R. We cannot handle the dispute in a descendent or R because R contains the bad block executing, so our dispute must push the relay chain bad to some ancestor R' < R of R. Yet, we do not have availability for BB in R'.

We cannot even put the availability votes for BB into a new successor of R' because two disputes could push us back to before BB was even backed.

@AlistairStewart

It should be the case that if we had an availability vote on the new chain, and enough validators were on that new chain, then the availability vote should pass.

So what you could do is have a complaint which includes the conflicting attestations made by a validator who has the PoV block. Then we assign that complaint to an availability core. If the vote fails, we would have to slash the complainant to stop spam.

The downside is that they would get slashed for something that depends on liveness, which increases the chance that even if there are 1/3 honest validators who already have their pieces the vote fails, so it shouldn;t be too much

But fortunately, we already have a mechanism to assign cores, price assigning them and which even allows retries.

So maybe we should schedule this complaint as though it were a parathread block? It needs a whole lot of special casing, but having the scheduling and even pricing of a parathread block might be useful in cutting down the amount of extra coding needed.

@rphmeier

1. Parablock B becomes available in some relay-chain block R. 2. Dispute is resolved against B in a descendent of R. 3. R is rolled back to its ancestor R' where B has not been executed. 4. A rollup is posted to a fresh descendent of R' which proves availability and invalidity of B.
   Backers of B are slashed

But to avoid reverting finality, we should only be finalizing a relay-chain block R when all candidates backed in R are at least partway through the acceptance period and undisputed. We don't want to finalize R when all candidates backed in R have just begun the acceptance period (i.e. at the exact point of availability)
It's worth noting that an absentee validator group can delay finality by rotation_frequency + availability_timeout by refusing to distribute availability pieces.

We are going to have to be able to revert finality regardless, which will be a pain.

The above only works if we never have to roll back more than 1 session. Moving from session S to S-1 is fine, but from S to S-2 loses us consensus on the validators, but this seems to be a requirement of BABE anyway

[rphmeier]

Since our availability scheme depends on an (f + 1, n) erasure-coding, and the dispute resolution process (presumably) resolves against a parablock if n - 2f votes appear against the parablock, that should mean that a roll-up of n - 2f against-votes also implies availability of the parablock, so no further work needs to be done to prove availability.

We'd only be able to process such rollups on forks that are aware of the validator-set at the time of the dispute, so finality needs to come faster than one session, as mentioned above.

[rphmeier]

Another role of the Validity module is handling double-vote reports and other obvious low-hanging fruit misbehavior.