MB feasibility check and unsigned submissions

# MB feasibility check and unsigned submissions **Feasibility checks** - Partial feasibility checks - voter exists in the snapshot - target exists in the snapshot - voter and target indices match the snapshot - maximum number of backers per winner in supports is `<=` `T::MaxBackersPerWinner` - number of supports is `<=` `desired_targets` - Full-solution feasibility checks - *total* backers per winner `<=` `T::MaxBackersPerWinner` - `claimed_score == full_solution_score` (note: submitters "claim" a full score before the feasibility checks are done to sort the submissions per score and ensure that the solution has a best score than the currently queued) ## Signed submission The feasibility check is done per solution page/block. It is performed once per page for each signed submission. However there are a few checks that require the full solution to be available, namely checking the i) full solution score and ii) check the max backers per winner. In the context of the signed submission, both partial solution and full solution feasibility checks are easily performed. The submitter is incentivizes to provide a good solution and not falsify the claimed full score (used to sort all submissions) due to a slashable deposit per submission. The partial feasibility checks are performed one page per block. The full solution checks are performed at the last block of the partial checks, if all paged solution checks are OK. In a nutshell, for the signed submissions we can ensure that both partial and full submission checks are OK and embed the economic mechanisms to incentivize the submitter to submit an honest solution. ## Unsigned submission For the unsigned submission, the solution is *collaboratively* submitted by `N == nr_pages_solution` block builders. Note that the unsigned solution is also paged, one solution being submitted per block -- so potentially each paged solution is submitted by `N` different block builders. The paged solutions are calculated by the offchain worker and submitted through an inherent. The inherent callable can check the partial feasibility checks on every single page. However, it can only perform the full feasibility check when all solution pages are submitted. Note that if a partial solution is not correct as per the inherent callable check and partial feasibility checks, the block will be discarded. But the full feasibility check submission can only be checked when all the pages are submitted. This opens an attack vector: - **grieving attack**: any block builder may craft a solution which passes the individual checks but will make the full solution fail. In this case, if the block builder is not submitting last solution page, the block corresponding solution page is accepted. The final solution will not be accepted and the unsigned phase needs to be restarted (or skipped). ### Potential solutions **1. Slash block builder stake** - if the full solution check fails, we can slash *all* the block builder stashes since we keep track of the block builder IDs that proposed the blocks with partial solutions during the unsigned submission. - this approach may be too harsh as honest block builders will also be slashed and it is *may* not be possible to check which of the validator(s) were dishonest. - (see point 3. as well) **2. Single page for unsigned submission** - accept a single page solution for unsigned submissions, in which case the partial and full solution checks can be performed in the inherent callable. - the final election score will be lower than multi-page solutions. - in this case, we need to ensure that the pages are large enough to accommodate enough backers and stake to result in a score that is sensible (i.e. `MinUntrustedScore`) - the unsigned submissions are very unlikely to compete with the singed submissions and will be used only for emergency cases. **3. Do not perform full-solution checks** - we can assume it is very hard to setup an attack so that: - *all* staking miners do not submit a signed solution - attacker acquires 1 or more block producers during the unsigned phase (in an election round where no signed submissions were performed) - if we assume that the attack is hard enough to perform, we can drop the full-page checks. - we still need to ensure that the final score is higher than `MinUntrustedScore` though. **4. Rely on on-chain fallback election instead** - with the multi-block election, we may be able to calculate a on-chain election that is sensible (i.e. `MinUntrustedScore`). - we can extend the number of election blocks if the on-chain election is running until the solution reaches the `MinUntrustedScore`. **5. Enforce upper bound on the number of backers per winners per page and skip the full score check** - if we ensure that the number of backers per winners *per page* is lower than `MaxBackersPerWinner / Pages`, we ensure that the maximum backers per winner in the full solution is always bounded by the `MaxBackersPerWinner`. - this new upper bound per page may affect the final solution score (to worse). - skip the full score check per page and only check if it is an improvement and higher than `MinUntrustedScore` when the full solution is available. - in this case, we don't slash the block builders in case the solution is not good enough. - instead of entering in `EmergencyPhase`, keep the current set of validators and try again next era. **6. Use Bulletproofs or other computation verification scheme to prove/verify paged solutions** (research) - off-chain worker computes the paged solution and computes a proof of correctness - inherent callable verifies the proof and accepts/reject the solution - Bulletproofs may be a good scheme for on-chain verification given the linear verification and `O(log(n))` communication overhead. - overhead too high? **7. Replace/complement the unsigned solution with an on-chain fallback** - leverage the multi-block election and blockspace of the staking parachain to compute an on-chain solution throughout the era. **8. Mixed approach** - use single age for unsigned phase and fallback on on-chain solution if the unsigned election score is not good enough after the unsigned phase is over. - (there are other mix-and-match approaches) --- IMO, I think that a mix of these approaches could be used in the short term, namely: - enforce the upper bound on the number of backers per winners per page. - if the full solution checks fail, do not enter in emergency phase and either: - perform MB-onchain election (needs checking) - rotate era with the same validator set and try again next era - no slashes to the block builders (unless we can prove on-chain or through an extrinsic which validator(s) was(were) dishonest(s), which I think it's pretty hard).