approval-voting: approvals gossip and lazy signature checks optimizations

[sandreim]

Problem

The overhead from gossip and signature check is significant as we scale the number of validators and parachains. An analysis of the overhead of current gossip topology and performance characteristics of approval vote signature checks can be found in #732 . The gist of it:

• 15K messages coming in from peers
• 938 assignments checked in 379ms
• 1373 approvals checked in 338 ms
• the rest(~250ms) book-keeping and forwarding message to the network bridge.

Potential solution

We introduce a fast path which relies on the fact that we can be optimistic when sending and lazy when processing approval vote messages:

• no gossip, validators send approvals to all connected peers on the Validation peerset.
• no need to check signatures of the approvals if the sending peer is also the originator of the message

This fast path also works if the system is loaded with disputes since we check the vote signatures before pushing them on-chain for slashing the offenders so we still don't need to check them at receive time unless they arrive via gossip. The only drawback is that we won't be able to apply reputation changes for any bad approval signatures detected late.

Slow path

We will revert to using gossip when approval checking is lagging by using the already existing implementation of approval-distribution aggression such that all validators send all messages to all peers in the X and Y dimensions of the topology. In such scenarios we perform signature checks only for approvals received from non originators.

Concerns

• it might be possible that we send an approval to a peer before it learns the assignment via gossip (slow path will help, or otherwise we could buffer orphan approvals + DoS protection)

[rphmeier]

From a security perspective, I don't believe this works.

Our security model with approvals is about making sure that checkers aren't squashed quickly. An attacker may have enough time before anyone notices finality is lagging to get enough checkers to finalize a bad parablock. Getting assignments to as many validators as possible, quickly, is really important for the security of approval-checking. In the worst case, the expected value of the number of validators we could get our assignment to before being noticed by an attacker is quite low. If the validators we sent to beforehand are redistributing, then it gets out to more. Otherwise, those ones just get DoSed as well.

[sandreim]

@rphmeier I totally agree on why we need to gossip assignments, but this ticket refers strictly to approval votes messages, not assignments.

If validators get DoSed before they send out the vote they would no show, so additional checker tranches will trigger.

[rphmeier]

Sorry - I misread. Yeah, fast-path for approvals would work well.

[alexggh]

Draft implementation: paritytech/polkadot#7482, feel free to have a look.

[alexggh]

Putting this on hold in favor of: #701

[alexggh]

Will not implement because we are taking other optimization avenues.

[burdges]

938 assignments checked in 379ms
1373 approvals checked in 338 ms

Is this simply the time spent on signature checks?

How can there be (so many) more approvals than assignments?

How can checking the approvals signatures be so much slower per signatures? VRFs should cost like 2x what the approvals do.

If the first is no, and approvals counds block execution too, then maybe the third comes from the parablocks being nearly empty.

[alexggh]

Is this simply the time spent on signature checks?

It was all the time spent in check_and_import_assignment and check_and_import_approval, it isn't just the signature checks it is other bookkeeping as well.

How can there be (so many) more approvals than assignments?

It was just some snapshot at specific moment in time.

I would consider this measurements kind of obsolete now since a lot of optimisations already went in, this is the alternative path we want to work on now #1617.