Add an experimental batch module

[siv2r]

Overview

This PR adds support for batch verifying Schnorr signatures and tweaked x-only public key checks. It is based on the work of @jonasnick in #760.

Batch Verification

This implementation does not strictly follow the BIP340 batch verification spec. The API design is loosely based on this suggestion: https://github.com/bitcoin-core/secp256k1/pull/760#issuecomment-809242311. Prior development discussion of this PR can be found in siv2r/secp256k1#2.

Speed Up

• batch verifying Schnorr signatures is 20% faster - graph here
• batch verifying tweak pubkey checks is 50% faster - graph here

Fixes #1087

[siv2r]

This implementation does not strictly follow the BIP340 batch verification spec.

For example,

• the random numbers (or randomizers) aren’t generated by passing a seed (hash of all inputs) to CSPRNG
• allows mixing of schnorrsig and tweak checks
• uses the tag “BIP0340/batch” for initializing the sha256 obj (not in the BIP340 specs)

Alternative Design Options

• batch module design
  • the current code has: (new batch module)
    • create, destroy, and verify APIs in the batch module
    • batch_add_* APIs in schnorrsig and extrakeys modules (with #ifdef ENABLE_MODULE_BATCH)
  • alternate option 1: (new batch module)
    • place the batch_add_* APIs in the batch module (with schnorrsig and extrakeys header guards)
  • alternate option 2: (no module)
    • place create, destroy, and verify in src/secp256k1.c
    • place batch_add_* APIs in schnorrsig and extrakeys modules
  • relevant discussions:
    • https://github.com/siv2r/secp256k1/pull/2#issuecomment-1134938298
    • https://github.com/siv2r/secp256k1/pull/2#issuecomment-1162522289
• Delayed randomizer generation
  • the current code generates a randomizer just after a user enters input (in _batch_add_*)
  • we could instead generate them (in batch_verify) after the user enters all their input
  • Pros: follows bip340 specs. Cons: consumes more memory.
  • more info: https://github.com/bitcoin-core/secp256k1/issues/1087#issuecomment-1067276801 and here
• Use BLAKE256 instead of SHA256 for generating randomizers (to improve speed).
• In _batch_create, we could:
  • Get memory size instead of max_terms.
  • Provide pre-determined sizes (small, medium, and large) instead of max_terms.
    • Better test coverage?

[siv2r]

Questions

• Streaming batch API (this PR) vs Single call batch API?
• Is transparent verification required?
  • the current code implements transparent verification (inside batch_add_* APIs)
  • without transparent verification, the user needs to check for space in the batch before calling _batch_add APIs:

  if (batch_enough_space_for_schnorrsig) {
    batch_add_schnorrsig()
  }
  

• On an empty batch, Should _batch_verify return 0 or 1?
  • the current code returns 1
    • simple implementation
  • if we want to return 0
    • needs an extra param in batch to avoid ANDing the result with its initial value
    • provides better security?
• xonly_pubkey_tweak_add_check recommends ctx to be initialized for verification, but it can work even if ctx is initialized as none.
  • Since batch_add_tweak_xonlypub_check is based on tweak_add_check, should it also recommend that ctx be initialized for verification?
  • Can it recommend that ctx be initialized for none instead?
• A better name for secp256k1_batch_usable?
  • the current name is confusing
  • here, “usable” means if the batch can be used by the batch_add_* functions

[siv2r]

In extrakeys/bench_impl.h, cast pointers to (void *) before freeing to avoid MSVC warning.

[real-or-random]

I haven't had a closer look yet but I agree with @jonasnick's comments about TV.

[fjahr]

@siv2r Are you still working on this topic? Do you plan to address @jonasnick 's comments?

[siv2r]

@fjahr, this PR needs review from other contributors regarding the (batch API) design decision made here. The https://github.com/bitcoin-core/secp256k1/pull/1134#pullrequestreview-1083948472 comment showed its support for the "Transparent Verification" feature, which was implemented.

IIRC, two documentation changes are required (at the time of writing):

• remove "initialized for verification" from the batch_add_tweak_xonlypub_check doc.
• document that batch_verify_1 is slower than schnorrsig_verify (see #1134 (comment)).

I avoided making these changes immediately to keep the commit history clean for reviewers. I would be happy to work on any required changes after it gets enough review.