Use Request/Response protocol for availability distribution

[eskimor]

Instead of gossiping via notifications, we should simply directly request our chunk from validators in the backing group of the candidate. No notifications are necessary, once a candidate is awaiting availability on chain, validators will start requesting their chunks. In the future, validators may request their chunks even sooner, if they discover locally via received statements that a candidate was successfully baked.

There are some benefits of this, in comparison to a solution that relies on notifications:

1. It will be even more efficient than notifications could ever be, even with direct connections. As each validator in a backing group would send out notifications to all validators, thus each validator would still receive their chunks multiple times.
2. We require way less connections. With directly sent notifications we would require open connections to all validators of the current session and possible even also for the next session. By means of the request/response approach worst case will only be approximately 2*N/g, where N is the number of validators in a session (2 N because of session boundaries), and g being the group size. So instead of 2000 connections, we only need approx 200 to 300 for a group size of 10. This is because, validators will download their chunks from different backing nodes - this should be achievable by picking a backer at random.
3. It simplifies things: Possibly no need to synchronize views for this protocol or re-request stuff on a missed notification.
4. Request/response is also perfect for availability recovery and PoV distribution. For availability recovery it also has the nice property that the code path for validators doing approval voting and collators that try to recover a PoV can be the same. For validators the TCP connection will stay open as requests keep coming in, for collators the connection would be opened for the request and shortly afterwards closed (because of lacking traffic), thus reducing load on validators.

Considerations

Spam: Spam protection should be relatively easy for availability distribution as each validator is only expected to fetch one piece and there are even multiple nodes it can fetch it from. Therefore we can keep a HashSet of all validator ids and remove those who fetched their piece. We will reject requests from nodes not in that set. Combined with a tight upper message size bound for requests, this should offer some level of protection.

[rphmeier]

This is because, validators will download their chunks from different backing nodes - this should be achievable by picking a backer at random.

In the worst case, only a simple majority of backers have actually backed the parablock. There needs to be a "try another backer" routine in the case that the requested-from backer doesn't have the block data.

Also worth noting that our group sizes in the long term will probably be 1 or 2.

[eskimor]

Yeah, I planed on using a randomized list and try one after the other.

Also worth noting that our group sizes in the long term will probably be 1 or 2.

Oha, I wasn't aware of that! bigeyes.

[rphmeier]

Yeah, most of the security of Polkadot comes from the approval voting, where checks are required before finality and the checkers are not predictable to an adversary. Backing is just about making sure someone gets slashed.

[burdges]

We noticed this protocol requires some back off for retries in the remote disputes case, but presumably everything does and this does in all cases, so nothing new here.

All candidates have an implicit checker list consisting of anyone who signed off on the candidate plus anyone who disputed the candidate, normally only backers and approval checkers but who knows. We could request chunks only the sublist of backers plus disputers because (a) if approval checkers exist then we've passed availability already and the node should eventually learn this, and (b) some nodes not learning this remains okay unless we punish for not voting in disputes. It's possible this sublist grows via late votes or disputes though.

[eskimor]

@burdges I can't really follow. Are disputes and remote disputes already relevant at distribution? With regards to retries, the implementation right now tries to fetch the validator's chunk from each validator in the backing group, one after the other. If it gets through that list without receiving a valid chunk, it gives up.

[burdges]

I'd think disputes would invoke some distribution-like functionality. In particular, we discussed rerunning the availability vote when importing a remote dispute onto the current chain, although we did not settle on whether this allocates some availability core or does a stand along vote that works across all forks.

With regards to retries, the implementation right now tries to fetch the validator's chunk from each validator in the backing group, one after the other. If it gets through that list without receiving a valid chunk, it gives up.

We should think about whether we need some back off and retry here, maybe no for normal distribution but I'll need to page back in the whole remote disputes discussion, well right now it's foggy.

[ordian]

Is it resolved by #2423?

[eskimor]

Mostly, I am working on a few follow ups (more tests, guide update, add back jaeger)

[eskimor]

More tests here