Make endorsement check `O(1)` instead of linear
Context
Currently, checking if an endorsement is valid is linear in the number of endorsers for the block.
In the worst case, it can be O(32) with the current Mainnet setup.
When checking if a block is valid, each endorsement is checked separately, giving a quadratic algorithm.
This won't be acceptable anymore if we decide to raise the number of endorsers.
Fixing the complexity of the operation requires passing an additional parameter to the endorsement checker (the endorsement slot). Naively extending the endorsement format to include the slot would mean breaking changes impacting various places of the signing infrastructure of bakers.
This MR implements a tricky way to provide the endorsement slot to the protocol, without changing the format that bakers sign.
Endorsements in their current format still exist in the operation format, to be signed by bakers. But the protocol only accepts a new kind of operation called endorsement_with_slot. These are unsigned operation, that contain an endorsement and the slot to which it corresponds. Their branch must match the endorsement they wrap. The tezos-endorser will produce the endorsement, have the signer stack provide the signature, then wrap it with its slot before injecting it in the node.
The change also propagates to the double_endorsement_evidence operation, that is extended to bear a slot.
This will introduce a breaking (but light) API change, mostly impacting block explorers and monitoring tools.
Note : I also experimented with another solution that consists in requiring that the endorsements are sorted in blocks, and use the wrappers only for the mempool. This is available in klakplok@linear_endorsement_check_trick_sorting but is more convoluted and has flaws, not worth the risks in my opinion for the only advantage of not changing the RPC API.
Update after discussion: the endorsement slot should be the smallest possible, and this applies to the double endorsement evidence as well.
Testing
The current test cases for endorsements should cover most of the failure cases.
A few minor tests have been added to check that the protocol does not accept unwrapped endorsement anymore and that the wrapped slot makes sense, but all suggestions of extra tests are welcome.
Still missing a check for double endorsement denunciation across protocol activation, but there isn't one currently.
Performance testing (@bidinger)
Added tests_python/tests_alpha/test_perf_endorsement.py to check that a block can be baked with 256 endorsements in less than 1s (conservative), it took about 10s without the current patch.
For this test, I had to add commit Proto: change endorsing constants to allow for 256 endorsements in a block. But it maybe redundant with @eugenz's MR !2386 (merged).
I couldn't try the test on the CI for this branch as it still fails in the build stage (opam dep failure).
Fix #1028 (closed)