8

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.

12

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 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.

Batch validation speedup

(*) 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.

  • I guess I have to read up the details again but wasn't the idea of the plain public key model and the construction of musig exactly that non interactive aggregation would become possible? Or should I have asked for musig signatures? I thought musig is just the exact scheme that is currently aimed to be used when people talk about schnorr. Do not mark as correct yet as I still have open questions (which are probably my fault) – Rene Pickhardt Mar 10 at 23:18
  • 1
    MuSig allows non-interactive setup - signing is still interactive. – Pieter Wuille Mar 10 at 23:21
  • And MuSig is just one of the things wallet can choose to use when Schnorr validation on chain exist (because the signatures that come out of MuSig signing are compatible with a Schnorr verifier). There are (interactive setup) constructions that let you build k-of-n with a single key for example, or even arbitrary and/or-combinations of participants. – Pieter Wuille Mar 10 at 23:25
  • 1
    "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." -- Couldn't this be iterated for O(log(N)) iterations? – Martin Schwarz Mar 12 at 7:26
  • @Martin Schwarz What do you mean by iterated? The construction (for Schnorr) is that you combine (R1,s1), ..., (Rn,sn) into (R1,...,Rn,s) where s = H(L,1)*s1 + ... + H(L,n)*sn and L = H(R1,...Rn,P1,...,Pn,m1,...,mn), and Pi are the pubkeys and mi are the messages. – Pieter Wuille Mar 12 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.