Add an experimental batch module

siv2r commented at 8:55 am on August 21, 2022: contributor

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: #760 (comment). 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

batch: Initialize an experimental batch module

This commit adds the foundational configuration, build scripts,
and an initial structure for experimental batch module.

db210f461d

batch: Add `create` and `destroy` APIs

This commit adds the _batch_create and _batch_destroy APIs.

Relevant Links:
1. _batch_scratch_size allocation formula is taken from bench ecmult:
https://github.com/bitcoin-core/secp256k1/blob/694ce8fb2d1fd8a3d641d7c33705691d41a2a860/src/bench_ecmult.c#L312.
2. aux_rand16 param in _batch_create enables synthetic randomness for
randomizer generation: sipa/bips#204.

e0dbd665fb

batch, ecmult: Add `batch_verify` API and refactor `strauss_batch`

This commit refactors _ecmult_strauss_batch and adds _batch_verify API.

The current _ecmult_strauss_batch only works on empty scratch space. To
make _batch_verify work, we need _ecmult_strauss_batch to support a scratch
space pre-filled with scalars and points. So, it was refactored to do
exactly that.

The _batch_verify API always uses the Strauss algorithm. It doesn't switch
to Pippenger (unlike _ecmult_multi_var). _ecmult_pippenger_batch represents
points as secp256k1_ge whereas _ecmult_strauss_batch represents points as
secp256k1_gej. This makes supporting both Pippenger and Strauss difficult
(at least with the current batch object design). Hence, _batch_verify only
supports Strauss for simplicity.

b7c7b581db

batch: Add `batch_add_*` APIs

This commit adds the batch APIs:

1. _batch_add_schnorrsig
    Adds a Schnorr signature to the batch.

2. _batch_add_xonlypub_tweak_check
	Adds a tweaked x-only pubkey check to the batch.

3. _batch_usable
	Checks if a batch can be used by _batch_add_* APIs.

**Side Note:**
Exposing batch_add_schnorrsig in the `secp256k1_schnorrsig.h` header
file (with batch module header guards) will force the user to define
ENABLE_MODULE_BATCH during their code compilation. Hence, it is in a
standalone `secp256k1_schnorrsig_batch` header file. A similar argument
could be made for batch_add_xonlypub_tweak_check.

9c120ef35a

batch: Add API usage example

This commit adds an example C program using the batch API.

GNU Autotools will compile this example only if both batch and
schnorrsig modules are enabled.

b3d370f397

batch,ecmult: Add tests for core batch APIs and `strauss_batch` refactor

This commit adds the following tests:
	1. Cirrus scripts
	2. Batch API tests (ordered)
	3. Tagged SHA256 test
	4. BIP340 test vectors: https://github.com/bitcoin/bips/blob/master/bip-0340/test-vectors.csv
	5. Large random test for `strauss_batch` refactor

d0446a86f7

batch: Add tests for `batch_add_*` APIs

This commit adds the following tests:
	1. Random bitflip test for randomizer generating function
	2. Random bitflip in Schnorr Signature (_batch_add_schnorrsig test)
	3. NULL arg tests (for both _batch_add APIs)

8a77b2c770

siv2r commented at 9:02 am on August 21, 2022: contributor

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: #1087 (comment) 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 commented at 9:03 am on August 21, 2022: contributor

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:
```
0if (batch_enough_space_for_schnorrsig) {
1  batch_add_schnorrsig()
2}
```
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

batch, extrakeys: Add benchmark for batch verify and `tweak_add_check`

This commit adds benchmarks for Schnorr signature batch verification,Tweaked
pubkey check batch verification, and Tweaked pubkey check (single verification).

For batch verify benchmark, the number of sigs (or checks) in the batch
varies from 1 to SECP256K1_BENCH_ITERS with a 20% increment.

d3fbae5580

batch: Generate graphs for batch verification speed up

This commit generates two semi-log graphs that visualize the batch
verification speed up over single verification (y-axis) wrt the number
of signatures (or tweak checks) in the batch (x-axis). The input data
points are taken from the batch verify benchmark.

GNU plot was used to generate these graphs (plot.gp file). The instructions
to reproduce these graphs (on your local machine) are given in
doc/speedup-batch.md file.

The value of `STRAUSS_MAX_TERMS_PER_BATCH` was calculated (approx) from
the generated graphs.
Relevant discussion: https://github.com/siv2r/secp256k1/pull/2#issuecomment-1211585236

eb49e93b50

siv2r force-pushed on Aug 21, 2022

siv2r commented at 10:35 am on August 21, 2022: contributor

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

in doc/speedup-batch/bench_output.txt:5 in eb49e93b50

0@@ -0,0 +1,137 @@
1+Benchmark                          ,    Min(us)    ,    Avg(us)    ,    Max(us)    
2+
3+schnorrsig_sign                    ,    50.4       ,    50.5       ,    50.7    
4+schnorrsig_verify                  ,    89.1       ,    89.2       ,    89.3    
5+schnorrsig_batch_verify_1          ,   104.0       ,   104.0       ,   104.0

sipa commented at 5:11 pm on August 23, 2022:

batch_verify_1 shouldn’t be slower than non-batch verify. Is it possible to revert to using non-batch validation logic for this case?

siv2r commented at 10:29 pm on August 23, 2022:

Not possible with the current design.

The non-batch validation (secp256k1_schnorrsig_verify) logic looks something like this:

calc rj using secp256k1_ecmult: Rj = sG - eP
convert rj (gej) to r (ge)
check if the r.x = sig[0:32] and r.y = even

one schnorrsig occupies two points in the batch, and one tweak check occupies one point in the batch. If a batch contains two points, there is no guarantee that they are from a schnorrsig (R, P). It could be from two tweak checks. So, we can’t use the r.y = even check.

Hence, I tried implementing a slightly modified schnorrsig_verify logic (not implement in this PR):

calc neg_rj using secp256k1_ecmult: neg_Rj = -s*G + batch.scalars[1]*batch.points[1]
check if neg_rj + batch.points[0] == inf using _gej_add_var
- batch.scalars[0] = 1 always. So, we don’t need to use ecmult again

This gives somewhat better benchmarks than before:

0Benchmark                          ,    Min(us)    ,    Avg(us)    ,    Max(us)    
1
2schnorrsig_sign                    ,    49.1       ,    50.1       ,    53.4    
3schnorrsig_verify                  ,    86.6       ,    87.2       ,    88.4    
4schnorrsig_batch_verify_1          ,    94.7       ,    95.0       ,    95.2

But schnorrsig_batch_verify_1 is still slower than schnorrsig_verify.

jonasnick commented at 2:43 pm on August 24, 2022: contributor

This implementation does not strictly follow the BIP340 batch verification spec. […] the random numbers (or randomizers) aren’t generated by passing a seed (hash of all inputs) to CSPRNG

The security argument for batch verification should relatively easily translate to the approach in this PR.

Is transparent verification required?

I initially wasn’t a fan of transparent verification because developers generally want to know how long a certain function call takes and don’t want to be surprised by some batch_add calls taking much longer than others. But I changed my mind on this.

The batch verification API right now is used as follows:

0for (i = 0; i < N_SIGS; i++) {
1    if(!batch_usable(batch) || !batch_add_schnorrsig(batch, sig[i], msg[i], sizeof(msg[i]), &pk)) {
2        return 0;
3    }
4}
5if(!batch_verify(ctx, batch)) {
6    return 0;
7}

Without TV, then one option is to have the user create a batch that is large enough. Of course that’s not alway possible because the batch can get larger than the available memory. Moreover, this would require adding an API that, given a number of schnorrsigs and tweaks (and more in the future) returns the size of the required batch. That seems way more complicated than TV.

If there’s no TV and the batch is not guaranteed to be large enough, then users need to essentially reimplement something like transparent verification:

 0for (i = 0; i < N_SIGS; i++) {
 1    if(!schnorrsig_batch_has_space(batch)) {
 2        if(!batch_verify(batch)) {
 3            return 0;
 4        }
 5    }
 6    if (!batch_add_schnorrsig(batch, sig[i], msg[i], sizeof(msg[i]), &pk)) {
 7        return 0;
 8    }
 9}
10if(!batch_verify(ctx, batch)) {
11    return 0;
12}

This is more code compared to having TV built into batch_add.
*_batch_has_space is specific to whatever you’re trying to add to the batch, i.e., we would also have to add tweak_has_space, for example.
The batch_usable function in the current implementation (with TV) only allows for earlier aborts and is not essential (unless you want to determine if a batch_add failed because its input is obviously malformed or because the previous batch_add triggered a batch_verify that failed).
If users don’t want to use TV (for whatever reason), then they don’t have to - even in the current implementation. This requires counting the terms that have been added to the batch and verifying before it’s full (perhaps we can make this simpler).

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?

I don’t think so. #1126 removes “initialized for verification” from the API docs of xonly_pubkey_tweak_add_check. For consistency it would be better if you’d remove “(can be initialized for none)” from the API doc.

real-or-random commented at 6:54 pm on August 24, 2022: contributor

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

fjahr commented at 7:54 pm on December 25, 2022: none

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

siv2r commented at 6:34 am on December 26, 2022: contributor

@fjahr, this PR needs review from other contributors regarding the (batch API) design decision made here. The #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.

real-or-random cross-referenced this on May 10, 2023 from issue Rework or get rid of scratch space by real-or-random

fjahr cross-referenced this on Feb 27, 2024 from issue [DO NOT MERGE] Schnorr batch verification for blocks by fjahr

in src/modules/batch/main_impl.h:197 in eb49e93b50

192+        int strauss_ret = secp256k1_ecmult_strauss_batch_internal(&ctx->error_callback, batch->data, &resj, batch->scalars, batch->points, &batch->sc_g, batch->len);
193+        int mid_res = secp256k1_gej_is_infinity(&resj);
194+
195+        /* `_strauss_batch_internal` should not fail due to insufficient memory.
196+         * `batch_create` will allocate memeory needed by `_strauss_batch_internal`. */
197+        VERIFY_CHECK(strauss_ret != 0);

fjahr commented at 11:57 pm on February 27, 2024:

Getting an unused variable warning about strauss_ret here when building this as part of bitcoin core, probably because the check is removed with optimizations?

real-or-random commented at 2:28 pm on February 28, 2024:

The macro VERIFY_CHECK(code) is defined to be the empty string in production builds, that’s why you need to suppress the warning using (void)strauss_ret;.

in include/secp256k1_batch.h:27 in eb49e93b50

22+ *
23+ *  The purpose of this structure is to store elliptic curve points, their scalar
24+ *  coefficients, and scalar coefficient of generator point participating in Multi-Scalar
25+ *  Point Multiplication computation, which is done by `secp256k1_ecmult_strauss_batch_internal`
26+ */
27+typedef struct secp256k1_batch_struct secp256k1_batch;

fjahr commented at 11:59 pm on February 27, 2024:

secp256k1_batch isn’t part of the API yet it seems.

0SECP256K1_API const secp256k1_batch *secp256k1_batch_struct;

siv2r commented at 1:01 pm on February 28, 2024:

Why do we need this? Currently, users can only create pointers to the secp256k1_batch object, which is the intended functionality of opaque objects, right?

fjahr commented at 3:20 pm on February 28, 2024:

Hm, never mind, it seems it’s not needed anymore with the latest version of my bitcoin core code.

fjahr commented at 0:02 am on February 28, 2024: none

I have opened a draft PR for using this in bitcoin core: https://github.com/bitcoin/bitcoin/pull/29491

Here is a rebased branch of the code that I am using: https://github.com/fjahr/secp256k1/tree/pr1134-rebase-2024

I hope this can create some new interest and motivate people to review here as well.

real-or-random added the label feature on Feb 28, 2024

real-or-random added the label performance on Feb 28, 2024

Add an experimental batch module #1134

Overview

Batch Verification

Speed Up

Alternative Design Options

Questions