Design RelayEquivocationStory

[rphmeier]

This is described in the implementer's guide section on protocol_approval, but it isn't yet part of the Approval Voting Subsystem.

[burdges]

I'll explain this design for everyone else besides Rob and myself:

We use use secret randomness to assign approval checkers after inclusion, so that adversaries who make an invalid candidate cannot predict the assigned approval checkers. An adversary can respond dynamically after they learn approval checker assignments however. We address dynamic attacks with additional VRF criteria that add more checkers, so that even powerful adversaries should exhaust their stake before they ever finalize an invalid block.

We have no-show replacements to address DoS-like attacks that prevent assignee from performing their checks. We figured out a trick for no-show replacements that avoids adding more VRF input types aka "stories".

We selected the relay chain's BABE VRF for our default story because doing so reduces an adversary's available entropy which decreases how often the default story favors them. We need another "story" for equivocations in relay chain block production though because approval checkers have exactly the same assignments in both equivocations, which by definition have the same BABE VRF.

If B is a block on parachain B then we say B is a candidate equivocation if there exist relay chain equivocations R1 and R2 such that R1 includes B but R2 does not includes B. If B is a candidate equivocation then approval requires additional assignees using a VRF criteria with story H(B).

If relay chain equivocations R1 and R2 both include B then B is not a candidate equivocation. We make this rule so that innocent relay chain equivocations produce fewer additional approval assignments. Also, candidates are not equivocations if they only get non-inclusion activity like backing in relay chain equivocations.

At this point, we've two questions:

Could approval be simpler if we made H(B) be our only story? Yes but.. We want more assigned approval checkers when using H(B) so all the complexity from also doing the BABE VRF story reduces our workload by perhaps half, meaning twice as many parachains when not under attack.

Would using the old BABE VRF from when B got backed help? Not really. We do not care about optimizing for the case of a relay chain equivocation since the slash can cover this cost. Also, we'd need to finalize the backing blocks or else still provide another fallback to H(B).

[burdges]

If not obvious, we've no analog of RelayVRFModulo here, only the delay checks. We therefore concentrate some lower delay tranches at tranche zero with a saturating_sub, which Rob already coded into the RelayVRFDelay stuff, even if not important there.

We only require candidate block hashes here, not VRFs, but identifying candidate equivocations requires reading both relay chain blocks. This creates some plumbing work:

Are there or should there be flags in expressing core inclusion and backing in relay chain headers? If so, this simplifies the plumbing, but obviously bloats the header by 256 bytes if we've 1024 parachains. If not, then actually nodes require both blocks to identify candidate equivocations, which sounds much harder but we'll discuss that if necessary.