When Schnorr signatures are part of Bitcoin will it be possible validate each block with only one signature validation?

Question

In a recent talk Pieter Wuille talked about speed up verification when using Schnorr signatures and various algorithms for verifying multiple signatures.

Would it really be possible to verify one single block by aggregating the keys and signatures of all transactions? (In theory even more transactions over several blocks)

I assume this does imply that the old ECDSA scheme would not be used anymore. If we were backwards compatible we could probably only do this for transactions that used Schorr signatures where as the other ones would have to be verified one by one.

(Leaving aside politics of drastic protocol changes) Couldn't we even save more space if we adopt the block header to include one aggregate Schnorre signature for the block and leave out all the schnorr signatures of the single transactions within that block?

Did I miss anything? The talk did not give many details but just mentioned the idea.

Answer 1

Yes, one validation per block, but not one signature per block.

To clear up confusion, there are 3 distinct technologies involved here:

• (1) non-interactive aggregation is the ability for a third party (who does not hold any private keys) to combine multiple signatures, each with their own message and public key, into a single signature that can be verified by someone who knows all messages and public keys.
• (2) interactive aggregation is the same, but when the signers need to be aware of the aggregation, and communicate with each other to jointly produce a single signature.
• (3) batch validation is the ability for a verifier to verify whether multiple (pubkey,message,signature) tuples are all valid or not, faster than verifying the individual signatures. If one or more of the tuples are invalid the verifier will not learn which ones, in this case.

Schnorr signatures (and any other known discrete logarithm based signature schemes) support (2) and (3), but not (1).

The lack of (1) means there cannot be a single signature for an entire block (*), as the miner who constructs the block is a third party who isn't participating in signature creation.

Due to (2), the best we can hope for (as long as we're restricted to DL-based signatures), is one signature per transaction. Even that requires cross-input aggregation, which has complexities beyond just the implementation of on-chain Schnorr signatures (see this post for example).

However, because of (3) it is correct that there can be a single validation per block, however not a single signature per block. The speedup that is possible through batch validation does become nontrivial, in fact. Each of the 4 lines is an optimization technique that is currently implemented in libsecp256k1, which will pick the best one based on the size of the problem and the memory constraints.

(*) There exists a form of non-interactive "half aggregation" for DL based signatures, where N signatures can be non-interactively combined into a single signature of size (1+N)/2 original signatures. This could be used for blocks, though the gains aren't that great, and there are complexities around block-wide aggregation that make it less interesting.