Batch Verification

[burdges]

We need not do this by polkadot's launch, but we should aim to eventually support batch signature verification for both ed25519 and sr25519, which likely improves signature verification time by like 40%.

In essence, the execute block flow should go: (1) parse the block, (2) extract all the signatures whose failure forces rejecting the whole block, including fetching anything from storage required for verification, (3) batch verify all those signatures, and (4) finally continue executing the logic for each transaction. Any signatures whose failure does not require rejecting the whole block should be verified in either step (1) or (4).

At first blush, there is a pretty radical transformation required for this workflow, but Rust's unstable generators might greatly simplify this. In other words, all transaction processing functions become #[async] so they can first collect all appropriate signatures ala (2), and then yield returning how much of the block they consumed and a set of signatures they want verified. After all transactions complete or yield, then execute block runs batch verification across all signatures from all transactions. Assuming the batch verifications passes them all, then we resume each yielded transaction.

I'm sure this increases the memory footprint, so issues like cache efficiency impact this too. Also, batch verification efficiency caps out just under 96 signatures, so you need not collect the whole block, just enough transaction so that enough signatures can be batch verified together.

[burdges]

We've no need for generators here because we postpone all writes until the full block passes anyways. We simply accumulate signatures that require verification, but continue the evaluate block logic temporarily assuming the signatures verify, much like we accumulate writes. We then batch verify all signatures after all transactions conclude, or only after we accumulate 96ish signatures. If any signature fails, then we abort the block, but if all succeed then we proceed onto the final write phase.

[rphmeier]

@burdges I think we would want to do verification first, otherwise transactions may do an unbounded amount of work without substantiation. But in principle I could see the Extrinsic and Checkable traits we use to check signatures being rejigged to accommodate batch verification by first extracting signatures and next doing verification.

[burdges]

Yes, there might be transactions that should still do conventional verification, maybe either gossip/mempool or block production should do conventional verification too before including transactions. And scripts or smart contracts could be quite messy.

Yet, I doubt polkadot itself has any tricky transactions, outside validator and council elections, but even those might exploit batch verification internally, not sure.