validation – Preventing Schnorr Signature Batch Verification of Invalid Signatures


In BIP-0340, in the Batch Verification section, (u - 1) randomly selected coefficients a2, ..., au are used in the batch verification equation, as opposed to just setting all of these to value of 1. The reason is given in the following two sources :

https://is.muni.cz/th/oaxta/thesis.pdf :

Page 7

A malicious party could produce an invalid signature, which would
complement or cancel out another (possibly invalid) signature, thus
making the batch verification succeed even for invalid signatures.

LearnMeABitcoin.com :

However, this equation isn’t completely secure, as it’s possible to
construct a signature that will balance out the equation for an
invalid signature. So to prevent this from happening, we multiply each
individual verification equation by its own random number (which we
call a).

However how could such a balancing out be achieved? Consider the case of u = 2 and set a2 = 1 in BIP-0340 and suppose that (pk1, m1, sig1) is an INVALID signature (so that s1*G != R1 + e1*P1) and we seek some signature (pk2, m2, sig2) (valid or invalid) that we can supply so that the following batch equation balances :

(s1 + s2)*G = R1 + R2 + e1*P1 + e2*P2

My immediate thought was to choose any signature (pk2, m2, sig2) which has R2 equal to the following :

R2 = (s1 + s2)*G - R1  - e1*P1 - e2*P2

which would then make the above equation balance.

But this would not work because e2 has a hash dependency on R2, because e2 equals a hash of data which includes the x-coordinate r2 of R2.

So how can a suitable signature (pk2, m2, sig2) be found, and how would setting a2 != 1 prevent that from working?

Leave a Reply

Your email address will not be published. Required fields are marked *