libsecp256k1

docs: update README

silentpayments: skip slow benchmarks for low iters count (<= 2)

The worst-case scanning benchmarks and the common-case scanning
benchmarks with N>10 are relatively slow, leading to signifcantly
long run times of CI jobs. Avoid this by skipping these if the
iters count is <= 2 (CI jobs run with SECP256K1_BENCH_ITERS=2).
This is the same approach used in the ecmult benchmarks (bench_ecmult).

ci: enable silentpayments module

tests: add constant time tests

Co-authored-by: Jonas Nick <2582071+jonasnick@users.noreply.github.com>
Co-authored-by: Sebastian Falbesoner <91535+thestack@users.noreply.github.com>

tests: add sha256 tag test

Test midstate tags used in silent payments.

tests: add BIP-352 test vectors

Add the BIP-352 test vectors. The vectors are generated with a Python script
that converts the .json file from the BIP to C code:

$ ./tools/tests_silentpayments_generate.py test_vectors.json > ./src/modules/silentpayments/vectors.h

Co-authored-by: Ron <4712150+macgyver13@users.noreply.github.com>
Co-authored-by: Sebastian Falbesoner <91535+thestack@users.noreply.github.com>
Co-authored-by: Tim Ruffing <1071625+real-or-random@users.noreply.github.com>

silentpayments: optimize scanning by using batch inversion

This improves the worst-case scanning scenario performance by ~2.5x
and also helps notably in the common case ("no match") scenario,
especially if the number of outputs is high.

Benchmark results on parent commit (without optimization):

Benchmark , Min(us) , Avg(us) , Max(us)

silentpayments_scan_nomatch_N=2 , 40.1 , 40.1 , 40.2
silentpayments_scan_nomatch_N=5 , 43.7 , 43.8 , 43.8
silentpayments_scan_nomatch_N=10 , 50.1 , 50.1 , 50.1
silentpayments_scan_nomatch_N=100 , 166.0 , 168.0 , 173.0
silentpayments_scan_nomatch_N=1000 , 1363.0 , 1368.0 , 1376.0
silentpayments_scan_nomatch_N=2323 , 3107.0 , 3113.0 , 3122.0
silentpayments_scan_nomatch_N=23250 , 30719.0 , 30764.0 , 30813.0
silentpayments_scan_worstcase_K=10 , 336371.0 , 336429.0 , 336492.0
silentpayments_scan_worstcase_K=100 , 3081573.0 , 3082413.0 , 3082899.0
silentpayments_scan_worstcase_K=1000 , 29909353.0 , 29931334.0 , 29951917.0
silentpayments_scan_worstcase_K=2323 , 67392236.0 , 67410087.0 , 67440159.0

Benchmark results on this commit (with optimization):

Benchmark , Min(us) , Avg(us) , Max(us)

silentpayments_scan_nomatch_N=2 , 39.3 , 39.3 , 39.4
silentpayments_scan_nomatch_N=5 , 40.5 , 40.5 , 40.6
silentpayments_scan_nomatch_N=10 , 43.5 , 43.5 , 43.5
silentpayments_scan_nomatch_N=100 , 90.0 , 92.7 , 100.0
silentpayments_scan_nomatch_N=1000 , 578.0 , 579.0 , 584.0
silentpayments_scan_nomatch_N=2323 , 1296.0 , 1300.0 , 1310.0
silentpayments_scan_nomatch_N=23250 , 12629.0 , 12649.0 , 12664.0
silentpayments_scan_worstcase_K=10 , 137746.0 , 137781.0 , 137813.0
silentpayments_scan_worstcase_K=100 , 1261417.0 , 1261614.0 , 1261774.0
silentpayments_scan_worstcase_K=1000 , 12245097.0 , 12249587.0 , 12258039.0
silentpayments_scan_worstcase_K=2323 , 27591765.0 , 27594324.0 , 27597324.0

(Benchmark machine: arm64 notebook, Snapdragon X Elite X1E-78-100)

silentpayments: sending

Add a routine for the entire sending flow which takes a set of private keys,
the smallest outpoint, and list of recipients and returns a list of
x-only public keys by performing the following steps:

1. Sum up the private keys
2. Calculate the input_hash
3. For each recipient group:
3a. Calculate a shared secret
3b. Create the requested number of outputs

This function assumes a single sender context in that it requires the
sender to have access to all of the private keys. In the future, this
API may be expanded to allow for a multiple senders or for a single
sender who does not have access to all private keys at any given time,
but for now these modes are considered out of scope / unsafe.

Internal to the library, add:

1. A function for creating shared secrets (i.e., a*B or b*A)
2. A function for generating the "SharedSecret" tagged hash
3. A function for creating a single output public key

Co-authored-by: w0xlt <94266259+w0xlt@users.noreply.github.com>

silentpayments: add examples/silentpayments.c

Demonstrate sending and scanning on full nodes.

silentpayments: respect per-group recipients protocol limit (K_max=2323)

This affects both the sending and scanning API functions:
* Sending fails if any group is exceeding the limit.
* Scanning doesn't look beyond the limit.

Also add a recommendation to the API docs to shuffle the
`tx_outputs` input array, which improves the worst-case by ~2x.

Co-authored-by: nymius <155548262+nymius@users.noreply.github.com>

silentpayments: receiving

Add routine for scanning a transaction and returning the necessary
spending data for any found outputs. This function works with labels via
a lookup callback and requires access to the transaction outputs.
Requiring access to the transaction outputs is not suitable for light
clients, but light client support is enabled in a future release.

Add an opaque data type for passing around the prevout public key sum
and the input hash tweak (input_hash). This data is passed to the scanner
before the ECDH step as two separate elements so that the scanner can
multiply the scan_key * input_hash before doing ECDH.

Finally, add test coverage for the receiving API.

Co-authored-by: w0xlt <94266259+w0xlt@users.noreply.github.com>

silentpayments: recipient label support

Add function for creating a label tweak. This requires a tagged hash
function for labels. This function is used by the receiver for creating
labels to be used for a) creating labeled addresses and b) to populate
a labels cache when scanning.

Add function for creating a labeled spend pubkey. This involves taking
a label tweak, turning it into a public key and adding it to the spend
public key. This function is used by the receiver to create a labeled
silent payment address.

Add tests for the label API.

Co-authored-by: w0xlt <94266259+w0xlt@users.noreply.github.com>

build: add skeleton for new silentpayments (BIP352) module

silentpayments: add benchmarks for scanning

Add a benchmark for a full transaction scan, both for the common
case and worst-case (full-block sized tx) scenarios.
Only benchmarks for scanning are added as this is the most
performance critical portion of the protocol.

Co-authored-by: Sebastian Falbesoner <91535+thestack@users.noreply.github.com>

field: serialize elements by word

The byte assignments replaced nested nibble loops before the endian write helpers existed.
Pack the 5x52 limbs into four 64-bit words and the 10x26 limbs into eight 32-bit words, then use those helpers.
This matches the scalar serializers and keeps the output unchanged.
Benchmarks indicate no measurable performance regression.

SECURITY.md: Align the table

SECURITY.md: Add theStack's key

SECURITY.md: remove Jonas Nick from trusted keys

scalar: correct `_scalar_get_bits_{limb32,var}` input condition docs

field: correct fe_equal's b magnitude bound

`secp256k1_fe_equal` negates `a` before adding `b`.
That gives the temporary value magnitude 2, and the following field addition requires the input magnitudes to sum to at most 32.
So the largest `b` magnitude the implementation can accept is 30, not 31.

Lower the documented and checked bound for `b` to 30.
Adjust the focused test to use random field elements with randomized magnitudes within the accepted `a <= 1` and `b <= 30` bounds.

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
Co-authored-by: Tim Ruffing <me@real-or-random.org>

tests: Fix GCC 17 snapshot warning

Passing a non-malloc pointer to free() would be UB. In this case, the
free() line is never actually reached (and GCC 17 fails to prove this)
in a correct implementation of secp256k1_scratch_space_destroy(), but
the test shouldn't rely on the correctness of the tested function.

ci: add 'brew trust' invocation to macOS CI

Should fix issues like:

> Error: Refusing to load formula louisbrunner/valgrind/valgrind from untrusted tap louisbrunner/valgrind.
> Run `brew trust --formula louisbrunner/valgrind/valgrind` or `brew trust louisbrunner/valgrind` to trust it.
> Error: Process completed with exit code 1.

Use __GNUC__ instead of SECP256K1_GNUC_PREREQ

Replace all SECP256K1_GNUC_PREREQ version checks with plain
defined(__GNUC__) checks, since the macro was only used for ancient GCC
versions that are no longer worth supporting individually. Moreover, the
macro was misleading because Clang claims to be GCC 4.2 by default.

All GCC versions that we reasonably support have the features previously
gated behind these checks (__inline__, __builtin_expect, __restrict__,
__warn_unused_result__, __nonnull__, and the __builtin_ctz* family).

Co-authored-by: Tim Ruffing <me@real-or-random.org>

hash: Include secp256k1.h directly

Move the #include "../include/secp256k1.h" from src/util.h to
src/hash.h, which is the file that actually depends on the
secp256k1_sha256_compression_function type defined there.

Co-authored-by: Tim Ruffing <me@real-or-random.org>

include: Remove SECP256K1_GNUC_PREREQ macro

The macro is no longer used anywhere in the codebase. This is
technically a breaking change, but it's not expected any user code
actually uses this macro.

Co-authored-by: Tim Ruffing <me@real-or-random.org>