More efficient dispute vote import

[eskimor]

To maximize efficiency when importing dispute votes on chain, we should think about asking the chain about disputes and votes it knows about.

Disputes Query API

Provide a runtime api to ask the chain for disputes it knows about for the given sessions. The returned information should contain a list of disputes.

fn get_session_disputes(Set<SessionIndex>) -> Vec<(CandidateHash, SessionIndex, DisputeStatus)>

Where DisputeStatus the very least should reveal whether a dispute already concluded on chain or not.

With that we can prioritize import of disputes we know about on the node side, but the chain does not yet know about.

Disputes Votes Query API

If we decide to have enough capacity to also provide votes for already known disputes, we would like to be able to ask the chain about votes for disputes it knows about:

fn get_disputes_votes_summary(Set<CandidateHash, SessionIndex>) -> Map<(CandidateHash, SessionIndex), VoteBitfields>

The given HashSet could be all non concluded disputes from the previous get_recent_disputes call for example.
This will return the known votes in a very compact form (via bitfields). Then we can limit what votes (heavy with signatures) to pass to create_inherent to ones the chain does not know about.

The prioritization as described here is a nice additional bonus, but by simply only ever importing stuff to the chain, we know it does not know, we have a guarantee, that we will import meaningful data on each block, no matter how many recent disputes currently exist.

Considerations

Bitfields are pretty compact, so we might also fusion those two runtime calls into one, where get_session_disputes already includes the bitfields instead of an even more compact DisputeStatus. ~2kbit per dispute, for 1000 validators. If every block over 6 sessions would trigger a dispute on Polkadot this would be around ~3,6MB of data, which would probably be fine. I would still lean towards the more flexible two call approach though.

Prioritization

Especially with #4804 in place, it makes sense to prioritize vote import for disputes the chain already knows about as long as they don't have concluded. This ensures that disputes conclude onchain so slashing events can be executed and it would also be good for performance. So prioritization should look something like this:

1. Import votes for disputes the chain knows about but have not concluded already - goal is to conclude disputes. So if we have to prioritize within this first category already, take all votes of dispute A before considering votes for the next dispute B and so on.
2. Then Import any new disputes the chain does not yet know about - as many as fit, but again don't scatter imported votes across disputes. So rather import 10 votes of a single dispute, than 10 disputes 1 vote each (same as for 1).
3. Still space? Import any votes for disputes the chain is aware, but have concluded already - as long as they are fresh.

An additional optimisation at step 2: Prioritise disputes with more votes because there is a better chance for them to be finalised fast.

TODOs:

• Disputes which are unknown for the Runtime are sent with priority by the Provisioner when preparing inherent data #5336
• Implement votes based prioritisation.
• Limit the number of new disputes that can be imported in a single block. Otherwise we might give a single validator too much control, over which votes are going to be imported. This is hard to exploit but better safe than sorry. (courtesy of @eskimor ).

[rphmeier]

We can roll this new runtime API into the 'VStaging' runtime API and then do all the upgrades at once.

[eskimor]

@tdimitrov supporting of multiple runtime versions, can be done like it was done here for example. So we can detect whether the call is not supported by version and do something sensible in that case.

[tdimitrov]

3. Still space? Import any votes for disputes the chain is aware, but have concluded already - as long as they are fresh.

I was thinking about this today. Is it possible to have a 'starvation' for concluded disputes? What I mean is if there are too may active ones and we push only them it (at least in theory) is possible not to import votes for concluded ones.
Can this be a problem?
Should we reserve some capacity for concluded disputes (e.g. 10% of the votes we are about to send to the runtime) and push concluded disputes (oldest first)?

[drahnr]

If a dispute is concluded, the priority should be very low. The worst case of not importing additional votes for concluded ones, is not rewarding validators that are on the "right" side.
A few things that might have side effects that come to mind are, the spam slot logic that lives on-chain, which tracks remote disputes. But that's a lesser concern compared to tracking all active disputes and driving them to conclusion.

Disputes are essentially a state machine:

OpposingStatements --> Active --> Concluded( --> Rewards/Slashing) or (almost never) OpposingStatements --> Active --> Timeout

[eskimor]

As @drahnr writes - concluded disputes are concluded, in broad strokes we would not care about additional votes at all. We do because you get rewards for participation and we would like to avoid block producers being able to steal rewards from others by not including their votes in their produced block for example. That's why we import them at all, but if we can't because of heavy load, it would not matter much, even if we never imported them.