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