Adds `prefractal`, an experimental module that lets a FROST t-of-n group
occupy ONE participant slot of an ordinary MuSig2 (BIP 327) session. Each
member computes
s_i = k1_i + b_frost*b_musig*k2_i + e*a*lambda_i*g*gacc*d_i
and the group publishes one ordinary MuSig2 public nonce and one ordinary
MuSig2 partial signature, so cosigners need no support for it and cannot tell
a group is involved.
Four public functions, all sessionless (every call takes its session
parameters explicitly, so there are no new opaque types, magics or *_SIZE
constants to keep synchronised):
secp256k1_prefractal_nonce_agg group wire nonce + unscaled aggnonce
secp256k1_prefractal_sign one member's partial signature
secp256k1_prefractal_partial_sig_verify identifiable abort
secp256k1_prefractal_partial_sig_agg sum -> musig partial signature
Three deliberate deviations from BIP 445, all documented in the public header:
1. b_frost does not commit to the message. The target protocols publish the
group's wire nonce before the message exists, so a message-committing
coefficient could not be computed in round one and rebuilt later. The outer
b_musig does commit to the message and multiplies this one, so the product
still binds it. Same trade the iceberg module makes, for the same reason.
The preimage is BIP 445's with the message dropped and the group key
carried in full rather than x-only, since it is used as a full point
downstream.
2. There is NO g_frost factor. Stock FROST normalises its threshold key to
even Y (g_times_gacc_parity = gacc_parity ^ pk_odd, frost/session_impl.h
:664) because it produces a BIP 340 x-only signature. Here the threshold
key is an inner participant of the outer key aggregation and is used as a
full point, so all key-side parity normalisation happens once, at the
aggregate level, off the OUTER keyagg cache. Note this is NOT implied by
the tweak cache being the identity: with an identity cache g_frost is still
-1 for every odd-Y group key, i.e. about half of them. Importing frost's
key-side parity here would yield a signer that works for even-Y groups and
fails for odd-Y ones.
3. The FROST tweak cache must be the identity (tacc == 0, gacc_parity == 0).
Checked in sign and partial_sig_verify, not only in partial_sig_agg, so the
key a member signs under is tied to the cache that was validated; sign and
verify additionally require thresh_pk to equal the cache's own key so the
two arguments cannot disagree.
The verification equation lives in one helper used both by sign's BIP 445
self-check and by partial_sig_verify, so the two cannot drift apart.
Build wiring. Three files order their module blocks differently and the
constraints point in opposite directions:
- src/secp256k1.c: the include goes AFTER frost and musig, because the
module calls their static internals.
- src/CMakeLists.txt: the block goes BEFORE both, because its set() calls
are only observed by blocks that run later.
- configure.ac: the block likewise goes before the musig block, NOT at
iceberg's position further down. configure.ac orders musig and frost ahead
of iceberg, and iceberg's late enable_module_musig=yes is harmless only
because musig defaults to yes. frost defaults to no, so a late
force-enable would leave -DENABLE_MODULE_FROST=1 unemitted while
AM_CONDITIONAL still observed the mutation - a library whose secp256k1.c
never included frost, built alongside frost's own sources.
frost is also the first default-OFF module anything depends on, which breaks
the dependency-guard idiom used everywhere else in both build systems: the
existing "DEFINED X AND NOT X" (CMake) and "x$X = xno" (autotools) tests read
as "the user disabled it explicitly" only for default-ON modules, and are true
by default for a default-OFF one. Since neither build system can distinguish
an explicit disable from the default once both are in the cache, enabling
prefractal simply implies frost; the guard is kept for musig, where it still
means what it says. The CMake block additionally lifts both dependencies into
the parent scope so the top-level configuration summary reports what was
actually built rather than printing "frost OFF" while compiling frost in.
Verified on both build systems:
cmake -B build -DSECP256K1_ENABLE_MODULE_PREFRACTAL=ON -DSECP256K1_BUILD_TESTS=ON
-> musig/frost/prefractal all ON, tests pass, 4 prefractal symbols exported
cmake -B build -DSECP256K1_BUILD_TESTS=ON
-> prefractal OFF, default build unchanged, tests pass
./configure --enable-experimental --enable-module-prefractal && make && make check
-> frost=yes forced on, -DENABLE_MODULE_FROST=1 emitted, 3/3 pass
./configure --enable-module-prefractal
-> correctly refused: "Prefractal module is experimental"
tests_impl.h is a placeholder here so the module links; the real suite lands
next.
Port the experimental Iceberg module from the benchmark-iceberg tree
(github.com/furszy/benchmark-iceberg, sources/secp256k1-kmp/native/
secp256k1) into this repo.
Iceberg is a threshold scheme that lets a group of parties stand in
for a single MuSig2 (BIP 327) participant: the group produces one
ordinary MuSig2 public nonce and one ordinary MuSig2 partial
signature, so cosigners cannot tell a group is involved and need no
changes. Nonces are derived from a caller-chosen per-session label
(sid32) rather than stored, so no signer holds a secret nonce between
rounds; labels are public but must never be reused. A quorum of 2t-1
members (of whom up to t-1 may be corrupt) is needed in each round,
so the threshold is at most half the group rounded up; combined with
the scheme's other constraints the smallest usable group is 2-of-4.
See doc/iceberg.md and the module header for the full usage notes.
Module layout (src/modules/iceberg/, layered bottom-up, each layer
may only use the ones above it -- that ordering is also the
constant-time story):
- scalar_poly.{h,_impl.h}: secret-carrying polynomial arithmetic,
keeping secrets away from inversions (documented in the header).
- rss.{h,_impl.h}: replicated secret sharing evaluation.
- vpss.{h,_impl.h}: verifiable public shares; variable-time by
design, sees only participant indices and published points.
- keygen_impl.h: distributed key generation producing one share per
member.
- session_impl.h: nonce_gen/nonce_agg and partial_sign/
partial_sig_agg producing plain MuSig2 objects.
- tests_impl.h: 28 tests including the shipped vectors.h vector
suite and dealer known-answer tests.
- bench_impl.h: benchmark definitions (wired in a follow-up commit).
Public headers: include/secp256k1_iceberg.h (installed) and
include/secp256k1_iceberg_dealer.h (in-tree only: a trusted dealer is
not part of the shipped API, but tests, benchmarks and the example
need to deal shares).
Content adaptations relative to the source tree (the only changes to
the ported code): three secp256k1_musig_nonce_process call sites in
tests_impl.h gained a NULL adaptor argument, because this repo's
musig is the zkp variant whose public nonce_process takes an optional
adaptor point. All musig internals the module uses (ge_parse_ext,
ge_serialize_ext, keyaggcoef, aggnonce_load, pubnonce_save,
partial_sig_save, nonce_process_internal) are identical in both
trees, as are all core headers the module touches; nothing else
needed adaptation.
Build wiring mirrors the chilldkg module:
- configure.ac: --enable-module-iceberg (default no, experimental
gate), hard dependency on the musig module with a configure error
if musig is explicitly disabled (musig itself pulls in schnorrsig),
AM_CONDITIONAL(ENABLE_MODULE_ICEBERG), summary line.
- Makefile.am: include src/modules/iceberg/Makefile.am.include under
the conditional.
- src/secp256k1.c: guarded include of modules/iceberg/main_impl.h
after the chilldkg block (musig is included earlier, so its
internals are in scope).
- src/tests.c: module test registration via MAKE_TEST_MODULE(iceberg).
- CMakeLists.txt / src/CMakeLists.txt: SECP256K1_ENABLE_MODULE_ICEBERG
option (OFF) with a dependency check on SECP256K1_ENABLE_MODULE_MUSIG
(placed before the musig block so the force-enable takes effect),
ENABLE_MODULE_ICEBERG=1 compile definition, public header export,
summary line.
Verified: ./configure --enable-experimental --enable-module-iceberg
&& make check passes; ./tests --target=iceberg runs the full module
suite (28/28); CMake build + ctest pass; the musig dependency error
fires correctly in both build systems.
Add an empty, experimental `chilldkg` module as the foundation for a
ChillDKG implementation (distributed key generation for FROST) per the
bip-frost-dkg BIP draft (v0.3.0-dev):
https://github.com/BlockstreamResearch/bip-frost-dkg
The module lives in src/modules/chilldkg/ (separate from the frost
module, per the implementation plan in .idea/docs/
chilldkg-implementation-plan.md: FROST signing (BIP 445) and ChillDKG
are separate BIPs with separate reference repos, test vectors and
review cycles; the dependency between them is one-way bytes).
New files:
- include/secp256k1_chilldkg.h: public header skeleton with the same
"EXTREMELY DANGEROUS / work in progress" warning style as
secp256k1_frost.h, plus a note that the BIP is a draft and tagged
hashes/wire formats may change. No API yet (Phase 3+).
- src/modules/chilldkg/main_impl.h: implementation skeleton including
the public header.
- src/modules/chilldkg/tests_impl.h: trivial scaffolding unit test
(chilldkg_scaffolding_test) registered via the tests_chilldkg[]
CASE1 array used by this repo's unit-test framework.
- src/modules/chilldkg/Makefile.am.include: autotools file list,
mirroring the frost module's.
- src/modules/chilldkg/chilldkg.md: module doc stub (purpose, draft
status, dependency on the schnorrsig and ecdh modules).
Build wiring (mirrors the frost module exactly):
- configure.ac: --enable-module-chilldkg (default no, experimental
gate), dependency errors when schnorrsig or ecdh are explicitly
disabled, AM_CONDITIONAL(ENABLE_MODULE_CHILLDKG), summary line.
- Makefile.am: include src/modules/chilldkg/Makefile.am.include under
ENABLE_MODULE_CHILLDKG.
- src/secp256k1.c: guarded include of modules/chilldkg/main_impl.h
after the frost module.
- src/tests.c: guarded include of tests_impl.h and
MAKE_TEST_MODULE(chilldkg) registration.
- CMakeLists.txt: SECP256K1_ENABLE_MODULE_CHILLDKG option (OFF) +
summary line.
- src/CMakeLists.txt: dependency checks on
SECP256K1_ENABLE_MODULE_SCHNORRSIG and SECP256K1_ENABLE_MODULE_ECDH,
ENABLE_MODULE_CHILLDKG=1 compile definition, public header export.
Verified:
- ./autogen.sh && ./configure --enable-experimental
--enable-module-chilldkg --enable-module-schnorrsig
--enable-module-ecdh && make check: PASS 3/3 (tests, noverify_tests,
exhaustive_tests).
- configure fails with a clear error when schnorrsig or ecdh are
disabled, or when experimental is not enabled.
- CMake build with SECP256K1_ENABLE_MODULE_CHILLDKG=ON: ctest 345/345
passed; dependency errors fire correctly when schnorrsig/ecdh OFF.
CI / x86_64: Linux (Debian stable) (clang, map[env_vars:map[CFLAGS:-O1 ECDH:yes ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (clang, map[env_vars:map[ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes WIDEMUL:int128]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (clang-snapshot, map[env_vars:map[BENCH:no BUILD:distcheck CTIMETESTS:no WITH_VALGRIND:no]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (clang-snapshot, map[env_vars:map[CFLAGS:-O1 ECDH:yes ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (clang-snapshot, map[env_vars:map[ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes WIDEMUL:int128]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (gcc, map[env_vars:map[CFLAGS:-O1 ECDH:yes ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (gcc, map[env_vars:map[ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes WIDEMUL:int128]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (gcc-snapshot, map[env_vars:map[BENCH:no BUILD:distcheck CTIMETESTS:no WITH_VALGRIND:no]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (gcc-snapshot, map[env_vars:map[CFLAGS:-O1 ECDH:yes ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes]]) (push) Has been cancelled
CI / x86_64: Linux (Debian stable) (gcc-snapshot, map[env_vars:map[ELLSWIFT:yes EXTRAKEYS:yes MUSIG:yes RECOVERY:yes SCHNORRSIG:yes WIDEMUL:int128]]) (push) Has been cancelled
CI / i686: Linux (Debian stable) (clang --target=i686-pc-linux-gnu -isystem /usr/i686-linux-gnu/include, map[env_vars:map[]]) (push) Has been cancelled
CI / MSan (clang, map[env_vars:map[CFLAGS:-fsanitize=memory -fsanitize-recover=memory -fsanitize-memory-param-retval -g CTIMETESTS:no]]) (push) Has been cancelled
CI / MSan (clang, map[env_vars:map[CFLAGS:-fsanitize=memory -fsanitize-recover=memory -g -O3 CTIMETESTS:yes ECMULTGENKB:2 ECMULTWINDOW:2]]) (push) Has been cancelled
CI / MSan (clang-snapshot, map[env_vars:map[CFLAGS:-fsanitize=memory -fsanitize-recover=memory -fsanitize-memory-param-retval -g CTIMETESTS:no]]) (push) Has been cancelled
CI / MSan (clang-snapshot, map[env_vars:map[CFLAGS:-fsanitize=memory -fsanitize-recover=memory -g -O3 CTIMETESTS:yes ECMULTGENKB:2 ECMULTWINDOW:2]]) (push) Has been cancelled
The 5x52 field multiplication and squaring routines are hot in group arithmetic and scalar multiplication.
Use the new `SECP256K1_FORCE_INLINE` for the thin wrappers and `int128` inner helpers so compilers can schedule the 64x64->128 arithmetic without a call boundary.
Across the measured GCC and MSVC Release builds, this improves ECDSA verification by 0.6% to 9.1%, ECDH by 0.7% to 9.3%, and Schnorr verification by 0.6% to 9.6%.
The direct field benchmarks generally show the intended effect on field squaring and multiplication, while Clang results are mostly flat and less consistently positive.
This is a code-size tradeoff: the tested static library builds grew by about 4.6% to 4.7%, and the tested Windows Release DLL grew by 14.1%.
Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
Co-authored-by: Hennadii Stepanov <32963518+hebasto@users.noreply.github.com>
Co-authored-by: Tim Ruffing <crypto@timruffing.de>
The CMake cache is global in scope. Therefore, setting the standard
cache variable `BUILD_SHARED_LIBS` can inadvertently affect the behavior
of a parent project.
This change:
1. Sets the `BUILD_SHARED_LIBS` cache variable only when libsecp256k1 is
the top-level project.
2. Removes the `SECP256K1_DISABLE_SHARED` cache variable. This enables
parent projects that include libsecp256k1 as a subproject to rely
solely on standard CMake variables for configuring the library type.
Ubuntu 20.04 LTS has reached the end of standard support. There no
longer appear to be compelling reasons to maintain compatibility with
CMake 3.16.
The new suggested minimum, CMake 3.22, is shipped with Ubuntu 22.04 LTS,
which is supported until April 2027.
This change also introduces new CMake policies, from CMP0098 to CMP0128.
c232486d84 Revert "cmake: Set `ENVIRONMENT` property for examples on Windows" (Hennadii Stepanov)
26e4a7c214 cmake: Set top-level target output locations (Hennadii Stepanov)
Pull request description:
While testing https://github.com/bitcoin-core/secp256k1/pull/1551, I noticed that when cross-compiling a shared library with examples for Windows, the `ctest` fails to run examples with Wine. Adjusting the `PATH` variable in 4af241b320/examples/CMakeLists.txt (L16-L18) does not help because `WINEPATH` is expected.
Another issue with the current implementation is that the examples cannot run individually on Windows.
This PR resolves both issues by reverting the implementation from https://github.com/bitcoin-core/secp256k1/pull/1290 in favour of the reworked and improved implementation from https://github.com/bitcoin-core/secp256k1/pull/1233.
ACKs for top commit:
theuni:
Concept ACK and utACK c232486d84.
real-or-random:
utACK c232486d84
Tree-SHA512: 479b71d15d5d5670f6f69da3da599240c345711003383ca805c821b67065c9baaf269f987792cf1029211cdbfe799aecd401e6940a471539e3929b4a90e0781d
168c92011f build: allow enabling the musig module in cmake (Jonas Nick)
f411841a46 Add module "musig" that implements MuSig2 multi-signatures (BIP 327) (Jonas Nick)
0be79660f3 util: add constant-time is_zero_array function (Jonas Nick)
c8fbdb1b97 group: add ge_to_bytes_ext and ge_from_bytes_ext (Jonas Nick)
85e224dd97 group: add ge_to_bytes and ge_from_bytes (Jonas Nick)
Pull request description:
EDIT: based on #1518. Closes#1452. Most of the code is a copy from [libsecp256k1-zkp](https://github.com/BlockstreamResearch/secp256k1-zkp). The API added in this PR is identical with the exception of two modifications:
1. I removed the unused `scratch_space` argument from `secp256k1_musig_pubkey_agg`. This argument was intended to allow using `ecmult_multi` algorithms for key aggregation in the future. But at this point it's unclear whether the `scratch_space` object will remain in its current form (see #1302).
2. Support for adaptor signatures was removed and therefore the `adaptor` argument of `musig_nonce_process` was also removed.
In contrast to the module in libsecp256k1-zkp, the module is non-experimental. I slightly cleaned up parts of the module, adjusted the code to the new definition of the VERIFY_CHECK macro and applied some simplifications that were possible because the module is now in the upstream repo (`ge_from_bytes`, `ge_to_bytes`). You can follow the changes I made to the libsecp256k1-zkp module at https://github.com/jonasnick/secp256k1-zkp/commits/musig2-upstream/.
ACKs for top commit:
sipa:
reACK 168c92011f
real-or-random:
reACK 168c92011f
theStack:
re-ACK 168c92011f
Tree-SHA512: e3a599a8d5a466107b9a86f76582b8fb9dc87ec95416c784c3ef39d1c64686e6c739806ed6ba62c91793eb7fa418a6270cf999027ee7bd3dd85c67bc2c74f677
This change:
1. Collects build artifacts in dedicated locations.
2. Allows to run individual examples with a shared library on Windows.
3. Is compatible with Wine when testing cross-compiled Windows binaries
on Linux.
4. Is compatible with integration the project into a larger project
hierarchy.
7c987ec89e cmake: Call `enable_testing()` unconditionally (Hennadii Stepanov)
6aa576515e cmake: Delete `CTest` module (Hennadii Stepanov)
Pull request description:
1. Delete `CTest` module.
The `CTest` module handles `CDash` integration, which we do not use. It is not required for testing functionality.
2. Clean up cases when to invoke `enable_testing()`
The `enable_testing()` command invocation is required for `add_test()` commands, which are used only for `{noverify_}tests`, `exhaustive_tests` and examples.
ACKs for top commit:
real-or-random:
utACK 7c987ec89e
theStack:
ACK 7c987ec89e
Tree-SHA512: f2628a4c4363b86f7c49d705df192e76368997e3f01cb736fcc272330bbf481af023d29d9faec17878d3bf74e4d265870cd93953406ae4612cd717811f22dd1a
Downstream projects may include libsecp test executables in their test
suites. In such cases, if a `-fsanitize=...` flag is passed via the
`SECP256K1_APPEND_CFLAGS` variable, the same flag must also be passed to
the linker.
4d9645bee0 cmake: Remove "AUTO" value of `SECP256K1_ECMULT_GEN_KB` option (Hennadii Stepanov)
a06805ee74 cmake: Remove "AUTO" value of `SECP256K1_ECMULT_WINDOW_SIZE` option (Hennadii Stepanov)
26b94ee92a autotools: Remove "auto" value of `--with-ecmult-gen-kb` option (Hennadii Stepanov)
122dbaeb37 autotools: Remove "auto" value of `--with-ecmult-window` option (Hennadii Stepanov)
Pull request description:
"auto" implies that a value is being chosen based on build system introspection or host system capabilities. However, for the `--with-ecmult-window` and `--with-ecmult-gen-kb` options, the values "auto" are hardcoded, which might lead to confusion.
This PR replaces "auto" with more appropriate default values.
If Concept ACKed, I'll add equivalent commits for CMake.
ACKs for top commit:
sipa:
utACK 4d9645bee0
real-or-random:
utACK 4d9645bee0 good from my side, but let's see if we can get more (Concept) ACKs
Tree-SHA512: 9e68f73682c5310c68d2337594f13b99a52bfc365564e39df2e412b576635c90cccd2298406a4281f014916c4a1710e19c7390f05a4b0acbd09869bfb56f36ac
158f9e5eae cmake: Do not modify build types when integrating by downstream project (Hennadii Stepanov)
Pull request description:
The `CMAKE_BUILD_TYPE` and `CMAKE_CONFIGURATION_TYPES` must be managed by the downstream project.
Suggesting to review with `git diff -w`.
Fixes `std::out_of_range` exception from CMake in https://github.com/hebasto/bitcoin/pull/192 when running configuration step using "Ninja Multi-Config" generator:
```
$ cmake -B build -G "Ninja Multi-Config"
...
-- Configuring done (17.1s)
terminate called after throwing an instance of 'std::out_of_range'
what(): map::at
Aborted (core dumped)
```
Here are related discussions:
- https://discourse.cmake.org/t/uncaught-exception-when-trying-to-generate-a-project-using-ninja-multi-config/11051
- https://gitlab.kitware.com/cmake/cmake/-/issues/26064
ACKs for top commit:
real-or-random:
ACK 158f9e5eae
Tree-SHA512: b3040f40438d530f14b7e0f7d523e74b5843d88d250ff7955a99cc8c451feb9471a48134d1a89b3651b3f8195f91c17135c7b8a5d3ab092c8d35275b57743b8c
