BIP458: Schnorr (Incremental) Half Aggregation #1566

This implements BIP458: https://github.com/bitcoin/bips/pull/2205

The original version of this code ported over the work from b-wagn in https://github.com/BlockstreamResearch/secp256k1-zkp/pull/261

Rebased on the musig changes and added the compile options for cmake

Rebased to take into account the latest changes to cmake, CI and test framework. Also squashed the commit since maintaining them was annoying and there wasn't really a good reason for them. It was more of a crutch for me while I was taking my first steps here.

I think there's a typo

Rebased and added the test vectors from the BIP draft: https://github.com/bitcoin/bips/pull/2205

Addressed the feedback from @theStack and rebased, happy to remove the experimental status if reviewers think it doesn't apply here.

Changed the tag to include the BIP number

The vector generator breaks on the BIP's new size vectors, and inc_aggregate differs from the BIP when n_before is 0.

I ran the vectors of bitcoin/bips#2205 at 2f436b0 through the module, and 300 random cases against an implementation I maintain, on btclib-ecc. 36 of the 37 vectors the C API can express pass, and the random cases agree byte for byte, including corrupted inputs and s ≥ n. Results are the same on a local merge with master.

Rerunning tools/test_vectors_halfagg_generate.py on that BIP head writes the eight new size vectors into fixed-size arrays. The too-long ones fail the build under -Werror. The too-short ones are zero-padded without a warning, so aggregate vector 9, a 31-byte key, succeeds and the test aborts. The generator could skip them, as it skips incaggregate 4 to 6. The vector left, incaggregate 6, is skipped because inc_aggregate ignores the input s when n_before is 0, while the BIP adds it and fails when it is ≥ n. With s = 1, the C result verifies and the BIP's does not. aggregate relies on this, passing its output buffer as the input. Zeroing those 32 bytes in aggregate, as the BIP's Aggregate does, would let inc_aggregate read s. Otherwise the header could say s is ignored there. I measured through ctypes and can share the script.

3361972502628adaa7938f8473067f190296fc37 needs rebase

Rebased

The vector generator breaks on the BIP's new size vectors

The latest update of the BIP just wasn't pulled in yet. I updated the vectors to the latest version of the BIP. The generator now skips the size vectors.

inc_aggregate differs from the BIP when n_before is 0

I addressed this. inc_aggregate now always reads s, and aggregate starts from s = 0 through a shared internal helper instead of zeroing the buffer. Vector 6 is also no longer skipped.

Concept ACK

One issue should be fixed before merge: doc/halfagg.md says that aggregating an invalid signature gives an invalid aggregate. That holds for one invalid input, but two can cancel out, as BIP 458 warns under both Aggregate and IncAggregate.

At ac35c4a83d7effb33180a30679dfa3fb1aefffcf, two signatures that each fail secp256k1_schnorrsig_verify aggregate into a signature that secp256k1_schnorrsig_aggverify accepts, in 100 of 100 random cases. I add d to one s and subtract d/z1 from the other, leaving the weighted sum unchanged. Readers may take a valid aggregate as proof that every input was valid, since the doc asks for individual checks only to find which signature failed. The sentence could follow the BIP: a valid aggregate does not prove valid inputs, so inputs that must be valid are verified individually first.

Both points of my earlier comment are fixed. inc_aggregate now reads the input s when n_before is 0, and the generator rebuilds vectors.h byte for byte from bitcoin/bips#2205's vectors at fe78361, incaggregate vector 6 included. Through ctypes, I compared the module with btclib-ecc, an independent implementation: in 300 random cases the two give the same bytes for aggregation and for incremental aggregation from an input s and reject the same input s ≥ n, and in the 267 non-empty ones they accept or reject the same valid and corrupted aggregates. At the previous head the same script fails all 300 cases with an input s. tests, the example and the benchmark pass on macOS arm64. Scripts and output: https://gist.github.com/fametrano/aba13d49caf4e9d0bdbdb3354b7fb100/2aadc3e1529cb27af32c0432323a9d8f09cdbb5a

doc/halfagg.md says that aggregating an invalid signature gives an invalid aggregate. That holds for one invalid input, but two can cancel out

Updated the doc to say that a valid aggregate does not imply valid input signatures.

ACK c371cec84c6cfacfe6aace890644b9b6724ae932

I read main_impl.h, tests_impl.h, the header, the example and the benchmark against BIP 458 and its halfagg.py at fe78361, and found no defect in the code. The hash order, the fixed first randomizer, the range checks and the verification equation match the BIP. Lengths and counts are checked before any read or write. I did not read the generator or the data in vectors.h, which regenerates byte for byte.

Only the doc sentence changed since my last review, and it is now correct: invalid inputs crafted to cancel verify in 100 of 100 cases through aggregate and through inc_aggregate, and without the cancelling input they are rejected in 200 of 200. The 300 random cases against btclib-ecc, an independent implementation, still agree. All 256 ctest tests pass on macOS arm64. Under ASan and UBSan, all but the exhaustive test pass, and so do 754 checks of a harness using exact-size heap buffers, including failed calls leaving the output untouched. Of 26 mutations of main_impl.h, the module's tests catch 24. One survivor accepts r ≥ p; I see no feasible signature that would tell it apart. Scripts and output: https://gist.github.com/fametrano/75c48df66cf2b0fa2d666bf0bbf80a02/fb73252aaa096f790fb6a60446aaced7da8cec1c

Not blocking: the other survivor removes aggverify's s range check. test_schnorrsig_aggregate_overflow sets s to all 0xFF, which fails either way, and no vector catches it. aggverify(CTX, NULL, NULL, 0, order, 32) == 0 with s equal to the group order does: I ran it, and it passes now and fails without the check. In test_schnorrsig_aggregate_unforge, the first case passes sizeof(aggsig) as the length, so 1002 of 1024 runs were rejected on length alone; 32*(n+1) would fix that.

In test_schnorrsig_aggregate_unforge, the first case passes sizeof(aggsig) as the length

Addressed by passing 32*(n + 1) as the length now.

the other survivor removes aggverify's s range check

I don't think this is really needed, but I may add an empty-aggregate vector with s = n to the BIP if I have to touch it again.

reACK c7ed5e0a0dbc69f5f75bc00e516ccd5ee1033e25

The only change since c371cec84c6cfacfe6aace890644b9b6724ae932 is the suggested 32*(n + 1) length in test_schnorrsig_aggregate_unforge. make check passes with the module enabled.