Rename msg32 to msghash32 in ecdsa_sign/verify and add explanation

Merge #851: make test count iteration configurable by environment variable

f4fa8d226a95e42b252c07edb425c446370e01c0 forbid a test iteration of 0 or less (Andrew Poelstra)
0ce45548813709d828cb3abcc7db4c9ce6e26907 make test count iteration configurable by environment variable (Andrew Poelstra)

Pull request description:

ACKs for top commit:
  jonasnick:
    ACK f4fa8d226a95e42b252c07edb425c446370e01c0
  real-or-random:
    ACK f4fa8d226a95e42b252c07edb425c446370e01c0

Tree-SHA512: 087771402c8e9536c07446baa7d02da5104d2b691f40c1dd04737329534422d895d3b692f485990d5791af8ccc124305b4f8b19be75e27b6b04cfb2337b28beb

forbid a test iteration of 0 or less

Merge #849: Convert Sage code to Python 3 (as used by Sage >= 9)

13c88efed0005eb6745a222963ee74564054eafb Convert Sage code to Python 3 (as used by Sage >= 9) (Frédéric Chapoton)

Pull request description:

ACKs for top commit:
  jonasnick:
    ACK 13c88efed0005eb6745a222963ee74564054eafb

Tree-SHA512: 6b8a32c35554b7e881841c17fe21323035014d25003f14e399f03ec017ea1bae1c68eee18a4d0315fc0f3b40d8252b5c8790f6c355d7d074a8ebc5e1ca832795

Convert Sage code to Python 3 (as used by Sage >= 9)

Co-authored-by: Tim Ruffing <[email protected]>

make test count iteration configurable by environment variable

Merge #835: Don't use reserved identifiers memczero and benchmark_verify_t

1f4dd0383807bfb7fef884601357b4c629dfb566 Typedef (u)int128_t only when they're not provided by the compiler (Tim Ruffing)
e89278f211a526062745c391d48a7baf782b4b2b Don't use reserved identifiers memczero and benchmark_verify_t (Tim Ruffing)

Pull request description:

  As identified in #829 and #833. Fixes #829.

  Since we touch this anyway, this commit additionally makes the
  identifiers in the benchmark files a little bit more consistent.

  This is necessary before we can merge #833. I preferred a separate PR because it makes it easier to see the results of Travis in #833.

ACKs for top commit:
  sipa:
    utACK 1f4dd0383807bfb7fef884601357b4c629dfb566
  jonasnick:
    ACK 1f4dd0383807bfb7fef884601357b4c629dfb566

Tree-SHA512: c0ec92798f3c94f3ef6ac69b3f0f39a39257a32be9d9a068832cece1ebe64c89848b70e44652fc397004b8b240883ac4bc0c8f95abbe4ba4b028de120e6734bf

Merge #839: Prevent arithmetic on NULL pointer if the scratch space is too small

29a299e373d5f0e326be74c514c7c70ddf50cce1 Run the undefined behaviour sanitizer on Travis (Fabien)
7506e064d791e529d2e57bb52c156deb33b897ef Prevent arithmetic on NULL pointer if the scratch space is too small (Fabien)

Pull request description:

ACKs for top commit:
  sipa:
    ACK 29a299e373d5f0e326be74c514c7c70ddf50cce1. Reviewed the code changes and verified that building with these sanitizer flags catches the existing error, as well as a signed integer overflow if introduced.
  real-or-random:
    ACK 29a299e373d5f0e326be74c514c7c70ddf50cce1 code inspection
  jonasnick:
    utACK 29a299e373d5f0e326be74c514c7c70ddf50cce1

Tree-SHA512: 4d788f12f3d7b48018e884910adb9b530a05d88f504de83dadeab8a22d75da83c05a1518f7317de5f536c4dd243ea7b347b1eaddb2ca1d804c663e41b85db69d

Merge #840: Return NULL early in context_preallocated_create if flags invalid

ebfa2058e9cc2999dada47d2f1e1e5c0f4bcf619 Return NULL early in context_preallocated_create if flags invalid (Tim Ruffing)

Pull request description:

ACKs for top commit:
  sipa:
    ACK ebfa2058e9cc2999dada47d2f1e1e5c0f4bcf619
  jonasnick:
    ACK ebfa2058e9cc2999dada47d2f1e1e5c0f4bcf619

Tree-SHA512: 61310539046e015e5c9e6b5702ac7b542fda854a23915ef5dd549361c8ec6e70aa6d509e02b30fd859b24dfaf2250721bb55270767323d6e94854067b7d7e9a6

Typedef (u)int128_t only when they're not provided by the compiler

Merge #838: Make autotools check for all the used openssl functions

3734b68200ee37f5eea80f47d611e9b5a65548fe Configure echo if openssl tests are enabled (Elichai Turkel)
e6692778d3f6507eb1325785cdd424073a945ff7 Modify bitcoin_secp.m4's openssl check to call all the functions that we use in the tests/benchmarks. That way linking will fail if those symbols are missing (Elichai Turkel)

Pull request description:

  I added all the openssl functions that we call in `tests.c` and in `bench_verify.c` to the m4 check, that way if any of them are missing it won't enable openssl.
  I also modified it a little to prevent a segmentation fault when running that program (not that it really matters for autotools)

  This should fix #836

ACKs for top commit:
  sipa:
    ACK 3734b68200ee37f5eea80f47d611e9b5a65548fe
  real-or-random:
    ACK 3734b68200ee37f5eea80f47d611e9b5a65548fe

Tree-SHA512: c82aa96a4176061284dfa5fdb87ca874a25aa2e11f75c4ec6d1edebcc8a19e2bc940990f8a5cfa64776fd295b6fd3a140fa2afede29326564504bc8d1a3a6b69

Configure echo if openssl tests are enabled

Return NULL early in context_preallocated_create if flags invalid

If the user passes invalid flags to _context_create, and the default
illegal callback does not abort the program (which is possible), then we
work with the result of malloc(0), which may be undefined behavior. This
violates the promise that a library function won't crash after the
illegal callback has been called.

This commit fixes this issue by returning NULL early in _context_create
in that case.

Merge #841: Avoids a potentially shortening size_t to int cast in strauss_wnaf_

8893f42438ac75838a9dc7df7e98b29e9a1a085f Avoids a potentially shortening size_t to int cast in strauss_wnaf_ (Tim Ruffing)

Pull request description:

ACKs for top commit:
  sipa:
    ACK 8893f42438ac75838a9dc7df7e98b29e9a1a085f. `np` and `no` shouldn't ever take on negative values.
  jonasnick:
    ACK 8893f42438ac75838a9dc7df7e98b29e9a1a085f
  elichai:
    ACK 8893f42438ac75838a9dc7df7e98b29e9a1a085f

Tree-SHA512: 431a6b88c8db8c8883b35c9bc03c90e37ecd0b06c7ee01c5d83cca4a7f6fc1f3cfbbaa871a4a23374ce4cc5bcfb9502c7f2e2540f9f9db9535e47e48827b6af6

Run the undefined behaviour sanitizer on Travis

Run UBSAN with both GCC and Clang, on Linux and macOS.
The `halt_on_error=1` option is required to make the build fail if the
sanitizer finds an issue.

Prevent arithmetic on NULL pointer if the scratch space is too small

If the scratch space is too small when calling
`secp256k1_ecmult_strauss_batch()`, the `state.pre_a` allocation will
fail and the pointer will be `NULL`. This causes `state.pre_a_lam` to be
computed from the `NULL` pointer.

It is also possible that the first allocation to fail is for `state.ps`,
which will cause the failure to occur when in
`secp256k1_ecmult_strauss_wnaf()`.

The issue has been detected by UBSAN using Clang 10:
```
CC=clang \
CFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
LDFLAGS="-fsanitize=undefined -fno-omit-frame-pointer" \
../configure

UBSAN_OPTIONS=print_stacktrace=1:halt_on_error=1 make check
```

Avoids a potentially shortening size_t to int cast in strauss_wnaf_

Fixes #834.

Modify bitcoin_secp.m4's openssl check to call all the functions that we
use in the tests/benchmarks.
That way linking will fail if those symbols are missing

Merge #809: Stop treating ECDH as experimental

e6e3d5da2f92f327019a62dc5f62f9335b2d0975 travis: add schnorrsig to valgrind and big endian platform test (Jonas Nick)
353dff156f1ed43a93c14a3686dc0649713d2997 Stop treating ECDH as experimental (Jonas Nick)

Pull request description:

  Fixes #665

ACKs for top commit:
  real-or-random:
    ACK e6e3d5da2f92f327019a62dc5f62f9335b2d0975
  elichai:
    ACK e6e3d5d

Tree-SHA512: 07379429ee159aad011c7cefcea35423602e9d119d994e11c78a89fcc74c2c65835b3d55f6f781fe28b4e3622db9ee470e48a223037a20baf94c0263b1c60105

travis: add schnorrsig to valgrind and big endian platform test

Stop treating ECDH as experimental

Don't use reserved identifiers memczero and benchmark_verify_t

As identified in #829 and #833. Fixes #829.

Since we touch this anyway, this commit additionally makes the
identifiers in the benchmark files a little bit more consistent.

Merge #830: Rip out non-endomorphism code + dependencies

c582abade1c50ef50dc7ee9f7b7af8e06e22065d Consistency improvements to the comments (Pieter Wuille)
63c6b71616816b19bec9cb3ab6b45ae5afd955f0 Reorder comments/function around scalar_split_lambda (Pieter Wuille)
2edc514c90293af8f602e4376e832773779c9426 WNAF of lambda_split output has max size 129 (Pieter Wuille)
4232e5b7da0a68adc14fa4b481f7e106403c200d Rip out non-endomorphism code (Pieter Wuille)
ebad8414b0e68041568d0b5ebe0bd395dbfbed9e Check correctness of lambda split without -DVERIFY (Gregory Maxwell)
fe7fc1fda8675aa9d79dae54a1b8b3cd06abcf81 Make lambda constant accessible (Pieter Wuille)
9d2f2b44d895509e8c4e7831fa917f13fa69f054 Add tests to exercise lambda split near bounds (Pieter Wuille)
9aca2f7f07b0563f8c65fcc22a0a91325cf6273b Add secp256k1_split_lambda_verify (Russell O'Connor)
acab934d24ff26289ab9930587c3fc51c30c6a2f Detailed comments for secp256k1_scalar_split_lambda (Russell O'Connor)
76ed922a5f09d63e0622825ca83d9301c1ef3efe Increase precision of g1 and g2 (Russell O'Connor)
6173839c90553385171d560be8a17cbe167e3bef Switch to our own memcmp function (Tim Ruffing)

Pull request description:

  This is a rebased/combined version of the following pull requests/commits with minor changes:
  * #825 Switch to our own memcmp function
    * Modification: `secp256k1_memcmp_var` is marked static inline
    * Modification: also replace `memcmp` with `secp256k1_memcmp_var` in exhaustive tests
    * Modification: add reference to GCC bug 95189
  * #822 Increase precision of g1 and g2
    * Modification: use the new `secp256k1_memcmp_var` function instead of `memcmp` (see https://github.com/bitcoin-core/secp256k1/pull/822#issuecomment-706610361)
    * Modification: drop the " Allow secp256k1_split_lambda_verify to pass even in the presence of GCC bug https://gcc.gnu.org/bugzilla/show_bug.cgi?id=95189." commit, as it's dealt with using `secp256k1_memcmp_var`.
    * Modification: rename secp256k1_gej_mul_lambda -> secp256k1_ge_mul_lambda
  * A new commit that moves the `lambda` constant out of `secp256k1_scalar_split_lambda` and (`_verify`).
  * The test commit suggested here: https://github.com/bitcoin-core/secp256k1/pull/822#issuecomment-706610276
    * Modification: use the new accessible `secp256k1_const_lambda` instead of duplicating it.
  * #826 Rip out non-endomorphism code
  * A new commit that reduces the size of the WNAF output to 129, as we now have proof that the split output is always 128 bits or less.
  * A new commit to more consistently use input:`k`, integer outputs:`k1`,`k2`, modulo n outputs:`r1`,`r2`

ACKs for top commit:
  real-or-random:
    ACK c582abade1c50ef50dc7ee9f7b7af8e06e22065d code inspection, some tests, verified the new g1/g2 constants
  jonasnick:
    ACK c582abade1c50ef50dc7ee9f7b7af8e06e22065d didn't verify the proof

Tree-SHA512: 323a3ee3884b7ac4fa85c8e7b785111b5c0638d718bc1c805a38963c87411e81a746c98e9a42a3e2197ab34a874544de5cc51326955d1c4d0ea45afd418e819f

Consistency improvements to the comments

Reorder comments/function around scalar_split_lambda

WNAF of lambda_split output has max size 129

Rip out non-endomorphism code

Check correctness of lambda split without -DVERIFY

The VERIFY macro turns on various paranoid consistency checks, but
 the complete functionality should still be tested without it.

This also adds a couple of static test points for extremely small
 split inputs/outputs.  The existing bounds vectors already check
 extremely large outputs.

Make lambda constant accessible

Add tests to exercise lambda split near bounds

Add secp256k1_split_lambda_verify

Detailed comments for secp256k1_scalar_split_lambda

Increase precision of g1 and g2

This allows us to shift by 256+128 = 384 bits, which is a multiple of the limb size of
the scalar representation. This also happens to be the most precision possible for g2
that still fits into a 256-bit value.

Switch to our own memcmp function

Fixes #823.

Merge #827: Rename testrand functions to have test in name

a45c1fa63cb3020225d72049ef9c1cf300014795 Rename testrand functions to have test in name (Pieter Wuille)

Pull request description:

  Suggested here: https://github.com/bitcoin-core/secp256k1/pull/808#discussion_r488871913

ACKs for top commit:
  real-or-random:
    ACK a45c1fa63cb3020225d72049ef9c1cf300014795 diff looks good
  elichai:
    utACK a45c1fa63cb3020225d72049ef9c1cf300014795

Tree-SHA512: a15c29b88877e0f1a099acab90cbfa1e70420527e07348a69c8a5b539319a3131b771b86852e772a669a1eb3475d508d0f7e10f37eec363dc6640d4eaf967536

Merge #821: travis: Explicitly set --with-valgrind

4eecb4d6ef6d4f18be8870a5929feb1dae376d15 travis: VALGRIND->RUN_VALGRIND to avoid confusion with WITH_VALGRIND (Jonas Nick)
66a765c7752b76d99be02d0f84dc05105bf4e70d travis: Explicitly set --with-valgrind (Jonas Nick)

Pull request description:

  Also remove CPPFLAGS=-DVALGRIND because that's redundant with when
  configured with --enable-valgrind.

ACKs for top commit:
  real-or-random:
    ACK 4eecb4d6ef6d4f18be8870a5929feb1dae376d15 diff and travis output look good
  sipa:
    utACK 4eecb4d6ef6d4f18be8870a5929feb1dae376d15
  elichai:
    ACK 4eecb4d6ef6d4f18be8870a5929feb1dae376d15

Tree-SHA512: c22d79fccaa926a074272b63a61f052f4bec3b1e5a871e3f08a4f6c19046da575779126a7008eb8a7513e70997b32d1dc6565dfb7aa41c57c0b6ef15ebbc8303

Merge #818: Add static assertion that uint32_t is unsigned int or wider

c0041b5cfca5efb160aa9a5616350069c89a8c29 Add static assertion that uint32_t is unsigned int or wider (Tim Ruffing)

Pull request description:

  Solves one item in #792 .

ACKs for top commit:
  sipa:
    utACK c0041b5cfca5efb160aa9a5616350069c89a8c29
  elichai:
    ACK c0041b5cfca5efb160aa9a5616350069c89a8c29

Tree-SHA512: 9f700e89be39e15983260da94642593d16b9c437171e10377837ac73731ca7ba5dd7e328b3d93d0a24d143fb9e73abd11c578f6b58e2f94c82b783e977173b0c

Rename testrand functions to have test in name

Merge #808: Exhaustive test improvements + exhaustive schnorrsig tests

8b7dcdd955a4f57174f478e36bdae5b84784fb9c Add exhaustive test for extrakeys and schnorrsig (Pieter Wuille)
08d7d89299a6492bf9388b4662b709d268c8ea29 Make pubkey parsing test whether points are in the correct subgroup (Pieter Wuille)
87af00b511f2938b6b4799f94d446a005730515e Abstract out challenge computation in schnorrsig (Pieter Wuille)
63e1b2aa7d396209aa5e26aa540d9593ede312a6 Disable output buffering in tests_exhaustive.c (Pieter Wuille)
39f67dd072fc44c7c0d27b95610ba8912de56db5 Support splitting exhaustive tests across cores (Pieter Wuille)
e99b26fcd54cb4096515ba80cf0f79d147b2683c Give exhaustive_tests count and seed cmdline inputs (Pieter Wuille)
49e6630bca5f6628bd1fd92d70d465273d4d873f refactor: move RNG seeding to testrand (Pieter Wuille)
b110c106fa9704e30f6b0c2ffa6a2697031e89a8 Change exhaustive test groups so they have a point with X=1 (Pieter Wuille)
cec7b18a34e68adb04f31a71a2eb4c5fc97674ce Select exhaustive lambda in function of order (Pieter Wuille)
78f6cdfaae9866694dcb0eee966332688753a8c3 Make the curve B constant a secp256k1_fe (Pieter Wuille)
d7f39ae4b67ea1ac6f085e6262a5f53afc0c5a25 Delete gej_is_valid_var: unused outside tests (Pieter Wuille)
8bcd78cd791fd9209d72d6bce455c8d3cf2c0249 Make secp256k1_scalar_b32 detect overflow in scalar_low (Pieter Wuille)
c498366e5b2d9c60e2e677949cf7373dbe877515 Move exhaustive tests for recovery to module (Pieter Wuille)
be317915436909573733afe3972a9abdee9357f7 Make group order purely compile-time in exhaustive tests (Pieter Wuille)

Pull request description:

  A few miscellaneous improvements:
  * Just use EXHAUSTIVE_TEST_ORDER as order everywhere, rather than a variable
  * Move exhaustive tests for recovery module to the recovery module directory
  * Make `secp256k1_scalar_set_b32` detect overflow correctly for scalar_low (a comment in the recovery exhaustive test indicated why this was the case, but this looks incorrect).
  * Change the small test groups so that they include a point with X coordinate 1.
  * Initialize the RNG seed, allowing configurating from the cmdline, and report it.
  * Permit changing the number of iterations (re-randomizing for each).
  * Support splitting the work across cores from the cmdline.

  And a big one:
  * Add exhaustive tests for schnorrsig module (and limited ones for extrakeys).

ACKs for top commit:
  real-or-random:
    ACK 8b7dcdd955a4f57174f478e36bdae5b84784fb9c
  jonasnick:
    ACK 8b7dcdd955a4f57174f478e36bdae5b84784fb9c

Tree-SHA512: 18d7f362402085238faaced164c0ca34079717a477001fc0b13448b3529ea2ad705793a13b7a36f34bf12e9231fee11070f88cc51bfc2a83ca82aa13f7aaae71

travis: VALGRIND->RUN_VALGRIND to avoid confusion with WITH_VALGRIND

Also remove CPPFLAGS=-DVALGRIND because that's redundant when
configured with --with-valgrind.

travis: Explicitly set --with-valgrind

Also set --with-valgrind=no once

Merge #813: Enable configuring Valgrind support

412bf874d09517b559eba4f7addb4c181cc2780b configure: Allow specifying --with[out]-valgrind explicitly (Luke Dashjr)

Pull request description:

ACKs for top commit:
  sipa:
    ACK 412bf874d09517b559eba4f7addb4c181cc2780b. Tested by running configure on a system with and without valgrind, and with no argument, with `--with-valgrind`, and with `--without-valgrind`.
  real-or-random:
    ACK 412bf874d09517b559eba4f7addb4c181cc2780b
  jonasnick:
    ACK 412bf874d09517b559eba4f7addb4c181cc2780b

Tree-SHA512: 92417609751e5af813faff1661055cd37f3d00dbcf109a8f14f8ba59d9f3d620c9c6b67d2b1629b6ab75e2afcd47d2b3898a0427931567fb505bc92fa5ee3532

Merge #819: Enable -Wundef warning

e73ff309221dcf677e861a49010b93dc6bb0ac48 Enable -Wundef warning (Tim Ruffing)

Pull request description:

ACKs for top commit:
  practicalswift:
    ACK e73ff309221dcf677e861a49010b93dc6bb0ac48 -- patch looks correct
  sipa:
    ACK e73ff309221dcf677e861a49010b93dc6bb0ac48
  jonasnick:
    ACK e73ff309221dcf677e861a49010b93dc6bb0ac48

Tree-SHA512: 1f0d477e41f33276eceb5324162731ba8aacd8d6571d7020344206b31c7f48c31f6bccbed2ce3ffe2e8c13abf98db24d177521b6b36a3087b81b55a253559fe6

Add exhaustive test for extrakeys and schnorrsig

Make pubkey parsing test whether points are in the correct subgroup

Abstract out challenge computation in schnorrsig

Disable output buffering in tests_exhaustive.c

Support splitting exhaustive tests across cores

Give exhaustive_tests count and seed cmdline inputs

refactor: move RNG seeding to testrand

Change exhaustive test groups so they have a point with X=1

This enables testing overflow is correctly encoded in the recid, and
likely triggers more edge cases.

Also introduce a Sage script to generate the parameters.

Select exhaustive lambda in function of order

Make the curve B constant a secp256k1_fe

Delete gej_is_valid_var: unused outside tests

Make secp256k1_scalar_b32 detect overflow in scalar_low

Move exhaustive tests for recovery to module

Make group order purely compile-time in exhaustive tests

Enable -Wundef warning

Add static assertion that uint32_t is unsigned int or wider

Merge #782: Check if variable=yes instead of if var is set in travis.sh

34debf7a6d36bbd9a52e68e079ddfc446faf5bef Modify .travis.yml to explictly pass no in env vars instead of setting to nothing (Elichai Turkel)
ef37761feed0172baa03dd94c842f1547bdf3016 Change travis.sh to check if variables are equal to yes instead of not-empty. Before this, setting `VALGRIND=wat` was considered as true, and to make it evaluate as false you had to unset the variable `VALGRIND=` but not it checks if `VALGRIND=yes` and if it's not `yes` then it's evaluated to false (Elichai Turkel)

Pull request description:

ACKs for top commit:
  real-or-random:
    ACK 34debf7a6d36bbd9a52e68e079ddfc446faf5bef
  jonasnick:
    ACK 34debf7a6d36bbd9a52e68e079ddfc446faf5bef

Tree-SHA512: 91becfbc9cb7587ee55b2bceb604ea0aed8860990d63a5f414b11db92180c090ea8bcc048c2fb67a094e892138e3be46f00562bf78b7c3369232457289cde447

configure: Allow specifying --with[out]-valgrind explicitly

Modify .travis.yml to explictly pass no in env vars instead of setting to nothing

Merge #814: tests: Initialize random group elements fully

5738e8622d8ba02caa984425c23c072a3f14352c tests: Initialize random group elements fully (Tim Ruffing)

Pull request description:

  Also fix add a missing comment.

ACKs for top commit:
  sipa:
    utACK 5738e8622d8ba02caa984425c23c072a3f14352c

Tree-SHA512: c7723e225434e7044379f307b2977a3a5251080793bd87b377a2bbf1d18b39ca05f6fb3b427acec32c3b34f4de678fe7087a2dcca4b5f03ec1fc680a88d82b9a

tests: Initialize random group elements fully

Also fix add a missing comment.

Merge #812: travis: run bench_schnorrsig

a51f2af62bde6e169499308e01ef768c09dd8127 travis: run bench_schnorrsig (Jonas Nick)

Pull request description:

ACKs for top commit:
  sipa:
    ACK a51f2af62bde6e169499308e01ef768c09dd8127
  elichai:
    ACK a51f2af62bde6e169499308e01ef768c09dd8127

Tree-SHA512: dfe68090fc60cba3cf2ff2f459f8ee47c4de65d28aee64310a7f7d54667daea5e82b907742445fa76b95cc2e67d57605dd260080919d8b805704784618745e29

travis: run bench_schnorrsig

Merge #558: Add schnorrsig module which implements BIP-340 compliant signatures

f431b3f28ac95a3645ad5a6dc96b878fa30a1de3 valgrind_ctime_test: Add schnorrsig_sign (Jonas Nick)
16ffa9d97cef93f49544b016339c107882f9a1c3 schnorrsig: Add taproot test case (Jonas Nick)
8dfd53ee3fa059562483d1867815f78b9e00d947 schnorrsig: Add benchmark for sign and verify (Jonas Nick)
4e43520026f5bcd182d21f0759bac159ef47bb62 schnorrsig: Add BIP-340 compatible signing and verification (Jonas Nick)
7332d2db6b62fda851f9ed8adbfda187a875b84e schnorrsig: Add BIP-340 nonce function (Jonas Nick)
7a703fd97db0161bae07ef84513ddde6e0d27353 schnorrsig: Init empty experimental module (Jonas Nick)
eabd9bc46a31c0da6db6d88840eadbe9006447b1 Allow initializing tagged sha256 (Jonas Nick)
6fcb5b845d2832ce019d60507033f74426290768 extrakeys: Add keypair_xonly_tweak_add (Jonas Nick)
58254463f9a2e96d893157a341c9953c440fdf60 extrakeys: Add keypair struct with create, pub and pub_xonly (Jonas Nick)
f0010349b876bc6b3f0a6ec6c8bad0b12ca17b51 Separate helper functions for pubkey_create and seckey_tweak_add (Jonas Nick)
910d9c284c33b77774a9316d4524f313357d441c extrakeys: Add xonly_pubkey_tweak_add & xonly_pubkey_tweak_add_test (Jonas Nick)
176bfb1110147b5dca1834ea071acc846fb1cab3 Separate helper function for ec_pubkey_tweak_add (Jonas Nick)
4cd2ee474d178bd1b5602486104db346a7562c67 extrakeys: Add xonly_pubkey with serialize, parse and from_pubkey (Jonas Nick)
47e6618e11813cfabe91f0909ca031f960cb7dd4 extrakeys: Init empty experimental module (Jonas Nick)
3e08b02e2a78f2a1fc457efab665db8ab8085373 Make the secp256k1_declassify argument constant (Jonas Nick)

Pull request description:

  This PR implements signing, verification and batch verification as described in [BIP-340](https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki) in an experimental module named `schnorrsig`. It includes the test vectors and a benchmarking tool.
  This PR also adds a module `extrakeys` that allows [BIP-341](https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki)-style key tweaking.

  (Adding ChaCha20 as a CSPRNG and batch verification was moved to PR #760).

  In order to enable the module run `./configure` with `--enable-experimental --enable-module-schnorrsig`.

  Based on apoelstra's work.

ACKs for top commit:
  gmaxwell:
    ACK f431b3f28ac95a3645ad5a6dc96b878fa30a1de3  (exactly matches the previous post-fixup version which I have already reviewed and tested)
  sipa:
    ACK f431b3f28ac95a3645ad5a6dc96b878fa30a1de3
  real-or-random:
    ACK f431b3f28ac95a3645ad5a6dc96b878fa30a1de3 careful code review

Tree-SHA512: e15e849c7bb65cdc5d7b1d6874678e275a71e4514de9d5432ec1700de3ba92aa9f381915813f4729057af152d90eea26aabb976ed297019c5767e59cf0bbc693

Merge #797: Fix Jacobi benchmarks and other benchmark improvements

cb5524adc589d3ae5066a1aa2f818bbfb91d0b1d Add benchmark for secp256k1_ge_set_gej_var (Pieter Wuille)
5c6af60ec5f1f4bc7883737ba34dd1789f1e9bd8 Make jacobi benchmarks vary inputs (Pieter Wuille)
d0fdd5f00969861ebe3e48d39be6d5f706b9b17c Randomize the Z coordinates in bench_internal (Pieter Wuille)
c7a3424c5f45a538ef141402a653b038e050a1ac Rename bench_internal variables (Pieter Wuille)

Pull request description:

ACKs for top commit:
  real-or-random:
    ACK cb5524adc589d3ae5066a1aa2f818bbfb91d0b1d
  jonasnick:
    ACK cb5524adc589d3ae5066a1aa2f818bbfb91d0b1d

Tree-SHA512: 0cbcfffebebf563cf9a1bd951394a0419503ffd43a2d0df4c99e4a839c89c8454925314f7e7eee0c01bce94b6dfeab935f36cc27f9bfc878f702313d455db7e1

Add benchmark for secp256k1_ge_set_gej_var

Make jacobi benchmarks vary inputs

Also make the num_jacobi benchmark use the scalar order as modulus,
instead of a random number.

Randomize the Z coordinates in bench_internal

Also increase the number of fe inputs.

Rename bench_internal variables

The _x and _y suffices are confusing; they don't actually correspond
to X and Y coordinates. Instead replace them with arrays.

Merge #699: Initialize field elements when resulting in infinity

47a7b8382fd6f1458d859b315cf3bcd3b9790b68 Clear field elements when writing infinity (Elichai Turkel)
61d1ecb02847be9d65ffe9df2d2408d85f3a0711 Added test with additions resulting in infinity (Elichai Turkel)

Pull request description:

  Currently if `secp256k1_gej_add_var` / `secp256k1_gej_add_ge_var` /` secp256k1_gej_add_zinv_var` receive `P + (-P)` it will set `gej->infinity = 1` but doesn't call initialize the field elements.
  Notice that this is the only branch in the function that results in an uninitialized output.

  By using `secp256k1_gej_set_infinity()` it will set the field elements to zero while also setting the infinity flag.

  I also added a test that fails with valgrind on current master but passes with the fix.

  EDIT: This isn't a bug or something necessary, I just personally found this helpful.

ACKs for top commit:
  real-or-random:
    ACK 47a7b8382fd6f1458d859b315cf3bcd3b9790b68

Tree-SHA512: cdc2efc242a1b04b4f081183c07d4b2602cdba705e6b30b548df4e115e54fb97691f4b1a28f142f02d5e523c020721337a297b17d732acde147b910f5c53bd0a

Merge #799: Add fallback LE/BE for architectures with known endianness + SHA256 selftest

8bc6aeffa9a191e677cb9e3a22fff130f16990f3 Add SHA256 selftest (Pieter Wuille)
5e5fb28b4a45d7e35e55b5f5feead2be07bccc28 Use additional system macros to figure out endianness (Pieter Wuille)

Pull request description:

  These are all the architecture macros I could find with known endianness. Use those as a fallback when __BYTE_ORDER__ isn't available.

  See https://github.com/bitcoin-core/secp256k1/pull/787#issuecomment-673764652

  It also adds a SHA256 selftest, so that improperly overriding the endianness detection will be detected at runtime.

ACKs for top commit:
  real-or-random:
    ACK 8bc6aeffa9a191e677cb9e3a22fff130f16990f3 I read the diff, and tested that the self-test passes/fails with/without the correct endianness setting
  gmaxwell:
    ACK 8bc6aeffa9a191e677cb9e3a22fff130f16990f3  looks good and I also ran the tests on MIPS-BE and verified that forcing it to LE makes the runtime test  fail.

Tree-SHA512: aca4cebcd0715dcf5b58f5763cb4283af238987f43bd83a650e38e127f348131692b2eed7ae5b2ae96046d9b971fc77c6ab44467689399fe470a605c3458ecc5

valgrind_ctime_test: Add schnorrsig_sign

schnorrsig: Add taproot test case

schnorrsig: Add benchmark for sign and verify

schnorrsig: Add BIP-340 compatible signing and verification

schnorrsig: Add BIP-340 nonce function

schnorrsig: Init empty experimental module

Allow initializing tagged sha256

This will be used by the schnorrsig module

extrakeys: Add keypair_xonly_tweak_add

extrakeys: Add keypair struct with create, pub and pub_xonly

Separate helper functions for pubkey_create and seckey_tweak_add

This is in preparation for allowing code reuse by keypair functions

extrakeys: Add xonly_pubkey_tweak_add & xonly_pubkey_tweak_add_test

Separate helper function for ec_pubkey_tweak_add

This is in preparation for allowing code reuse by xonly tweak add functions

extrakeys: Add xonly_pubkey with serialize, parse and from_pubkey

Merge #806: Trivial: Add test logs to gitignore

bceefd6547635132ba17f022a52db18f17e00df6 Add test logs to gitignore (Jake Rawsthorne)

Pull request description:

  Was just running the tests for https://github.com/bitcoin-core/secp256k1/pull/558 and noticed these logs weren't ignored

ACKs for top commit:
  real-or-random:
    ACK https://github.com/bitcoin-core/secp256k1/pull/806/commits/bceefd6547635132ba17f022a52db18f17e00df6
  sipa:
    ACK bceefd6547635132ba17f022a52db18f17e00df6

Tree-SHA512: 690906bc80abc547e1ef78d8654900c2f4054fd8cb8c2e0a6f6b95a5875930b8e1e3a69a5dca86b198e4a2601788f584c8b2ff6f5a85da230b12954e07aeff37

Merge #648: Prevent ints from wrapping around in scratch space functions

60f7f2de5de917c2bee32a4cd79cc3818b6a94a0 Don't assume that ALIGNMENT > 1 in tests (Tim Ruffing)
ada6361dece4265823478e0019a8c196e9285a26 Use ROUND_TO_ALIGN in scratch_create (Jonas Nick)
8ecc6ce50ead28a0b8bab2f1fb18a58ee5204a13 Add check preventing rounding to alignment from wrapping around in scratch_alloc (Jonas Nick)
4edaf06fb02a9ac9cd115e0c967bb0ef35cae01d Add check preventing integer multiplication wrapping around in scratch_max_allocation (Jonas Nick)

Pull request description:

  This PR increases the general robustness of scratch spaces. It does not fix an existing vulnerability because scratch spaces aren't used anywhere in master. Additionally,  it must be prevented anyway that an attacker has (indirect) control over the arguments touched in this PR.

ACKs for top commit:
  sipa:
    ACK 60f7f2de5de917c2bee32a4cd79cc3818b6a94a0

Tree-SHA512: ecdd794b55a01d1d6d24098f3abff34cb8bb6f33737ec4ec93714aa631c9d397b213cc3603a916ad79f4b09d6b2f8973bf87fc07b81b25a530cc72c4dbafaba9

Merge #805: Remove the extremely outdated TODO file.

1c325199d590e018cdfb5ea2ab541774009bf7f7 Remove the extremely outdated TODO file. (Gregory Maxwell)

Pull request description:

  This had two things in it-- tests for the scalar/field code and
   constant time signing and keygen.

  The signing and keygen have been thoroughly constant time for years
   and there are now powerful tests to verify it...  no further work
   on constant-time is needed at least on ordinary platforms (other
   sidechannels-- sure).

  The scalar and field code have extensive tests.  They could use
   better static test vectors but they're well tested.

  TODOs for the project are currently better documented on github
   right now.  This file could return in the future with current
   info, if needed.

ACKs for top commit:
  real-or-random:
    ACK https://github.com/bitcoin-core/secp256k1/pull/805/commits/1c325199d590e018cdfb5ea2ab541774009bf7f7

Tree-SHA512: 65c730ad2816b28991cdb74df6da4671abe76a74a0d0b306f13612b4bbe9b54f9a623b18fc288e0ec13572d9fdbab6f376ce7aafc9fe601644239629b84fb15c

Add test logs to gitignore

Remove the extremely outdated TODO file.

This had two things in it-- tests for the scalar/field code and
 constant time signing and keygen.

The signing and keygen have been thoroughly constant time for years
 and there are now powerful tests to verify it...  no further work
 on constant-time is needed at least on ordinary platforms (other
 sidechannels-- sure).

The scalar and field code have extensive tests.  They could use
 better static test vectors but they're well tested.

TODOs for the project are currently better documented on github
 right now.  This file could return in the future with current
 info, if needed.

extrakeys: Init empty experimental module

This is to prepare for xonly_pubkeys and keypairs.

Make the secp256k1_declassify argument constant

This is required to declassify pointers to constant memory. Declassify should
never modify its argument.

Add SHA256 selftest

Merge #798: Check assumptions on integer implementation at compile time

7c068998bac3e4a254d8542458b2068e38fca435 Compile-time check assumptions on integer types (Pieter Wuille)
02b6c87b52dbac1557b689ab2ebc8b91d67fd0f3 Add support for (signed) __int128 (Pieter Wuille)

Pull request description:

  A compile-time check is implemented in a new `src/assumptions.h` which verifies several aspects that are implementation-defined in C:
  * size of bytes
  * conversion between unsigned and (negative) signed types
  * right-shifts of negative signed types.

ACKs for top commit:
  gmaxwell:
    ACK 7c068998bac3e4a254d8542458b2068e38fca435
  real-or-random:
    ACK 7c068998bac3e4a254d8542458b2068e38fca435 code review and tested

Tree-SHA512: 3903251973681c88d64d4af0f6cb40fde11eb436804c5b6202c3715b78b1a48bcb287f601b394fd0b503437e3832ba011885e992fe65098b33edc430d9b1f67d

Use additional system macros to figure out endianness

Also permit it being overridden by explicitly passing SECP256K1_{BIG,LITTLE}_ENDIAN

Compile-time check assumptions on integer types

Add support for (signed) __int128

Merge #787: Use preprocessor macros instead of autoconf to detect endianness

0dccf98a21beb245f6cd9ed76fb7368529df09c7 Use preprocessor macros instead of autoconf to detect endianness (Tim Ruffing)

Pull request description:

  This does not fix any particular issue but it's preferable to not
  rely on autoconf. This avoids endianness mess for users on BE hosts
  if they use their build without autoconf.

  The macros are carefully written to err on the side of the caution,
  e.g., we #error if the user manually configures a different endianness
  than what we detect.

  Supersedes #770 .

ACKs for top commit:
  sipa:
    ACK 0dccf98a21beb245f6cd9ed76fb7368529df09c7
  gmaxwell:
    ACK 0dccf98a21beb245f6cd9ed76fb7368529df09c7

Tree-SHA512: 6779458de5cb6eaef2ac37f9d4b8fa6c9b299f58f6e5b72f2b0d7e36c12ea06074e483acfb85085a147e0f4b51cd67d897f61a67250ec1cea284a0f7680eb2e8