bip-340: reduce size of randomizers to 128 bit and provide argument

[jonasnick]

This (currently) speeds up batch verification in libsecp256k1 by up to 9%.

Reopen of https://github.com/sipa/bips/pull/220 which was automatically closed. Closes https://github.com/sipa/bips/pull/219.

• [ ] Consider replacing Schwartz-Zippel with proof by induction.

Applying Schwartz-Zippel may be detrimental if we want to allow a more general approach where randomizer a_i only depend on pk_1..pk_i, m_1..m_i and sig_1..sig_i and not all pubkeys messages and sigs (this is actually currently implemented in https://github.com/bitcoin-core/secp256k1/issues/1087. Hence, one can choose pk_{i+1} and therefore bias a_{i+1} after computing a_i. SZ on the other hand requires the randomizers to be drawn random independently and uniformly.

The proof sketch in the issue does not use SZ but instead a proof by induction that appears to be better suited for dependent a_i.

[real-or-random]

I'm not sure if the distinction between invoking SZ and the inductive proof makes a difference with respect to the incremental derivation of randomizers. Already with the SZ proof and the non-incremental variant, the fact that randomizers are actually deterministic is outside the scope of the proof. So the attacker can bias all a_i by choosing pk_1

But I need to think more about it...

[jonasnick]

So the attacker can bias all a_i by choosing pk_1

Yes, but those a_i are all independent of each other. With incremental derivation, the attacker can choose a_{i+1} dependent on a_i.