BIP459: Add FullAgg (DahLIAS) module #1754

This PR adds a FullAgg module implementing full aggregation of BIP 340 signatures using the interactive aggregate signature scheme (DahLIAS).

The implementation follows the BIP459.

Concept ACK

The last commit here now is implementing the code sharing between the musig and the fullagg model. That is one of the first questions I have when reviewers will take a closer look here: Do we want to do it this way? And do we event want to do this at all? I think it's pretty good but also the amount of LOC saving has been a bit underwhelming at the end.

A second thing that I changed and that I would be interested in high-level feedback on: I realized that the fullagg module really doesn't need any of the Schnorr module code, it just depends on extrakeys. I fixed this in the config where I still had the schnorr module as dependency of the fullagg module. However, in practical terms they will likely always be active together and it's also a bit awkward that I still have the module named schnorrsig_fullagg which I took over from the Halfagg PR where it's schnorrsig_halfagg. The most correct way would be to remove the schnorrsig part here but I am also unsatisfied with the asymmetry this would create 🙈 If anyone has opinions on this I am happy to hear them.

The latest push is a rebase but also does a bunch of renaming and rewording in response to the naming discussion in the BIP, e.g. dropping the "FullAgg of Schnorr signatures" framing.

Split out the first commit which is a pure refactor: https://github.com/bitcoin-core/secp256k1/pull/1915

Rebased after #1915 was merged

Pulled in additional test vectors added based on feedback on the BIP

Haven't had a deep look on the code yet (still catching up on BIP reading), but giving my two cents on the high-level questions:

The last commit here now is implementing the code sharing between the musig and the fullagg model. That is one of the first questions I have when reviewers will take a closer look here: Do we want to do it this way? And do we event want to do this at all? I think it's pretty good but also the amount of LOC saving has been a bit underwhelming at the end.

Good question, I think there could be made convincing arguments for both sharing and not sharing. One one hand deduplicating code is always nice (even if the overall LOC saving is not that large, the modules ideally become more readable overall), on the other hand this opens up a few questions regarding code organization, naming and scope (e.g. I wouldn't expect to find functions dealing with partial signatures in a module called "nonce_common"). Unless others strongly push back, I think a separate PR which creates the shared module (only moving from musig) could be already opened now for further discussion, in order to keep this PR focused on the new functionality.

A second thing that I changed and that I would be interested in high-level feedback on: I realized that the fullagg module really doesn't need any of the Schnorr module code, it just depends on extrakeys. I fixed this in the config where I still had the schnorr module as dependency of the fullagg module. However, in practical terms they will likely always be active together and it's also a bit awkward that I still have the module named schnorrsig_fullagg which I took over from the Halfagg PR where it's schnorrsig_halfagg. The most correct way would be to remove the schnorrsig part here but I am also unsatisfied with the asymmetry this would create 🙈 If anyone has opinions on this I am happy to hear them.

I'd slightly lean on keeping the schnorrsig_ prefix, to indicate the type of signature which is aggregated (even if the aggregation modules indeed don't depend on the regular schnorrsig module).

65e57481c4c5199c6beb1a0a6272ae739a22bf5a needs rebase

Unless others strongly push back, I think a separate PR which creates the shared module (only moving from musig) could be already opened now for further discussion, in order to keep this PR focused on the new functionality.

Sounds good to me, I have dropped the commit here and instead opened #1938. That would be a good place for people to push back strongly if they feel like it :)

I'd slightly lean on keeping the schnorrsig_ prefix, to indicate the type of signature which is aggregated (even if the aggregation modules indeed don't depend on the regular schnorrsig module).

Thanks, I actually already removed the prefix in some push earlier but my comment didn't make that clear enough since I hadn't really made up my mind when I wrote it. I will wait for 1-2 more opinions before I put them back. My feeling is that @real-or-random might lean the other way :)

needs rebase

Done

I built this at 1af6f99 and found no discrepancy with an independent BIP459 implementation, but vectors.h is behind the BIP.

I compared the module with that implementation, which I wrote from the BIP on btclib-ecc, and ran its tests. On 300 random sessions of 1 to 6 signers the nonces, partial signatures and aggregates are identical, and so are the verify results on 1,200 altered aggregates. make check, ctime_tests under Valgrind (0 errors), and tests 300 with -DVERIFY under ASan and UBSan pass. I can share the code.

vectors.h is exactly what the generator produces from bips 9dd6d42 (2026-09-16). The BIP at 8678edb has five more sign-error rows (zero secnonce, zero key, three bad aggnonces) and one more tweak row. tools/test_vectors_fullagg_generate.py fails on the new sign-error CSV, because it gained an aggnonce column. The module already refuses the three aggnonces and the zero key. Could the generator and vectors.h be updated, with the bips commit named in the commit message?

1af6f99027a9e9d040cafe24232aa08559650be0 needs rebase

Following up on my earlier comment: every new BIP459 vector in fjahr/bips#8 that the C API can take agrees with this module, and verify 14, already in the BIP, needs a decision.

I ran every row of fjahr/bips#8, proposed for bitcoin/bips#2210, against this module at 1af6f99 through ctypes, next to an implementation I maintain. Besides verify 11 to 13, which vectors.h already omits, the API cannot take five new rows: nonce_gen 2 (38-byte extra_in), sign_error 10 and 11 (a secnonce value of n, which only a struct written by hand can hold), and verify 15 and 16 (31- and 33-byte messages). The generator's verify filter would keep 15 and 16. I can share the scripts in a gist.

Verify 14 expects FALSE for an empty signer list. The generator calls that input inexpressible, but n_signers = 0 can be passed, and secp256k1_fullagg_verify then hits ARG_CHECK(n_signers > 0), which aborts under the default illegal-argument callback. Should it return 0, as the BIP expects, or is the abort intended?

Rebased

vectors.h is behind the BIP.

Updated to the latest version of the BIP. The generator reads the new aggnonce column, and the new NonceGen and NonceAgg vectors are tested as well.

The generator's verify filter would keep 15 and 16.

It now skips verify vectors whose messages are not 32 bytes. The other rows you listed (nonce_gen 2, sign_error 10 and 11) did not go into the BIP.

Should it return 0, as the BIP expects, or is the abort intended?

It returns 0 now. The header already said verify returns 0 for anything but a valid signature and, unlike the signing functions, never required n_signers > 0. Following #1983, pubkeys and messages can also be NULL if n_signers is 0. Verify 14 is included in vectors.h now.

In src/ctime_tests.c, secp256k1_fullagg_nonce_gen_counter overwrites secnonce immediately after secp256k1_fullagg_nonce_gen:

ret = secp256k1_fullagg_nonce_gen(ctx, &secnonce, &pubnonce, session_secrand, key, &pk, extra_input);
...
ret = secp256k1_fullagg_nonce_gen_counter(ctx, &secnonce, &pubnonce, nonrepeating_cnt, &keypair, extra_input);

Because secnonce is overwritten before secp256k1_fullagg_partial_sign, the secret nonce derived from session_secrand and key is never exercised under signing in the ctime harness. Also, keypair at that point was initialized from defined memory and has not been marked undefined with SECP256K1_CHECKMEM_UNDEFINE(&keypair, sizeof(keypair)).

Separating both into distinct sign passes:

        ret = secp256k1_fullagg_nonce_gen(ctx, &secnonce, &pubnonce, session_secrand, key, &pk, extra_input);
        SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret));
        CHECK(ret == 1);
        CHECK(secp256k1_fullagg_nonce_agg(ctx, &aggnonce, pubnonce_ptr, 1));
        SECP256K1_CHECKMEM_DEFINE(msg, sizeof(msg));
        CHECK(secp256k1_fullagg_session_init(ctx, &session, &aggnonce, pk_ptr, msg_ptr, pubnonce_ptr, 1) == 1);
        ret = secp256k1_keypair_create(ctx, &keypair, key);
        SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret));
        CHECK(ret == 1);
        ret = secp256k1_fullagg_partial_sign(ctx, &partial_sig, &secnonce, &keypair, msg, &session, pk_ptr, msg_ptr, pubnonce_ptr, 1, 0);
        SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret));
        CHECK(ret == 1);

        SECP256K1_CHECKMEM_UNDEFINE(&keypair, sizeof(keypair));
        ret = secp256k1_fullagg_nonce_gen_counter(ctx, &secnonce, &pubnonce, nonrepeating_cnt, &keypair, extra_input);
        SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret));
        CHECK(ret == 1);
        CHECK(secp256k1_fullagg_nonce_agg(ctx, &aggnonce, pubnonce_ptr, 1));
        CHECK(secp256k1_fullagg_session_init(ctx, &session, &aggnonce, pk_ptr, msg_ptr, pubnonce_ptr, 1) == 1);
        ret = secp256k1_fullagg_partial_sign(ctx, &partial_sig, &secnonce, &keypair, msg, &session, pk_ptr, msg_ptr, pubnonce_ptr, 1, 0);
        SECP256K1_CHECKMEM_DEFINE(&ret, sizeof(ret));
        CHECK(ret == 1);

Tested locally with Valgrind 3.27, runs clean with 0 errors.

In src/modules/fullagg/main_impl.h:817, found_index can also stay size_t without casting:

size_t found_count = 0;
size_t found_index = 0;
...
if (found_count != 1 || found_index != signer_index)

At 5f0e692, what Yudis-bit's ctime patch adds is that keypair is undefined when nonce_gen_counter runs; the extra signing pass with the nonce_gen secnonce adds no coverage.

To check this, I added a branch on a secret value to the module and ran ctime_tests under Valgrind 3.24 on Linux aarch64 with three harnesses: as it is, with Yudis-bit's patch, and with only its keypair line added. A branch on the secret key in nonce_gen_counter goes unreported as the harness is, and is reported with either change. A branch on the secret nonce in partial_sign is already reported as the harness is, because the counter secnonce is undefined through extra_input and partial_sign does not depend on which function made the nonce. With no branch added, all three report 0 errors. The patches, the command and the output are in https://gist.github.com/fametrano/520c7d7fb7ae32a6df298b09c2d39c12/17ca42fe588140de1fc16751a1a6f75fe3a0e306.

So SECP256K1_CHECKMEM_UNDEFINE(&keypair, sizeof(keypair)) before nonce_gen_counter is enough. The musig harness on master has the same gap, and #1979 adds the same line there. musig also needs a declassify, because it copies the pubkey with keypair_pub; fullagg takes it with keypair_xonly_pub, whose keypair_load already declassifies it.

vectors.h is now exactly what the generator produces from BIP459 as merged in bitcoin/bips (a0c977f), and verify 14 is among the cases tests runs. make check, and tests 300 under ASan and UBSan, pass on macOS arm64.