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

pull jonasnick wants to merge 1 commits into bitcoin:master from jonasnick:128b-randomizers changing 2 files +17 −1

jonasnick commented at 8:49 PM on August 22, 2022: contributor
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.
bip-340: reduce size of randomizers to 128 bit and provide argument
This (currently) speeds up batch verification in libsecp256k1 by up to 9%.
fc7722a35b
jonasnick commented at 6:19 AM on August 23, 2022: contributor

Closing... this was intended to be opened against a different repo.
jonasnick closed this on Aug 23, 2022

Contributors