Squashed 'src/secp256k1/' changes from 2ed54da18a..8ab24e8dad

8ab24e8dad Merge #558: Add schnorrsig module which implements BIP-340 compliant signatures
f3733c5433 Merge #797: Fix Jacobi benchmarks and other benchmark improvements
cb5524adc5 Add benchmark for secp256k1_ge_set_gej_var
5c6af60ec5 Make jacobi benchmarks vary inputs
d0fdd5f009 Randomize the Z coordinates in bench_internal
c7a3424c5f Rename bench_internal variables
875d68b95f Merge #699: Initialize field elements when resulting in infinity
54caf2e74f Merge #799: Add fallback LE/BE for architectures with known endianness + SHA256 selftest
f431b3f28a valgrind_ctime_test: Add schnorrsig_sign
16ffa9d97c schnorrsig: Add taproot test case
8dfd53ee3f schnorrsig: Add benchmark for sign and verify
4e43520026 schnorrsig: Add BIP-340 compatible signing and verification
7332d2db6b schnorrsig: Add BIP-340 nonce function
7a703fd97d schnorrsig: Init empty experimental module
eabd9bc46a Allow initializing tagged sha256
6fcb5b845d extrakeys: Add keypair_xonly_tweak_add
58254463f9 extrakeys: Add keypair struct with create, pub and pub_xonly
f0010349b8 Separate helper functions for pubkey_create and seckey_tweak_add
910d9c284c extrakeys: Add xonly_pubkey_tweak_add & xonly_pubkey_tweak_add_test
176bfb1110 Separate helper function for ec_pubkey_tweak_add
4cd2ee474d extrakeys: Add xonly_pubkey with serialize, parse and from_pubkey
f49c9896b0 Merge #806: Trivial: Add test logs to gitignore
aabf00c155 Merge #648: Prevent ints from wrapping around in scratch space functions
f5adab16a9 Merge #805: Remove the extremely outdated TODO file.
bceefd6547 Add test logs to gitignore
1c325199d5 Remove the extremely outdated TODO file.
47e6618e11 extrakeys: Init empty experimental module
3e08b02e2a Make the secp256k1_declassify argument constant
8bc6aeffa9 Add SHA256 selftest
670cdd3f8b Merge #798: Check assumptions on integer implementation at compile time
5e5fb28b4a Use additional system macros to figure out endianness
7c068998ba Compile-time check assumptions on integer types
02b6c87b52 Add support for (signed) __int128
979961c506 Merge #787: Use preprocessor macros instead of autoconf to detect endianness
887bd1f8b6 Merge #793: Make scalar/field choice depend on C-detected __int128 availability
0dccf98a21 Use preprocessor macros instead of autoconf to detect endianness
b2c8c42cf1 Merge #795: Avoid linking libcrypto in the valgrind ct test.
57d3a3c64c Avoid linking libcrypto in the valgrind ct test.
79f1f7a4f1 Autodetect __int128 availability on the C side
0d7727f95e Add SECP256K1_FE_STORAGE_CONST_GET to 5x52 field
805082de11 Merge #696: Run a Travis test on s390x (big endian)
39295362cf Test travis s390x (big endian)
6034a04fb1 Merge #778: secp256k1_gej_double_nonzero supports infinity
f60915906d Merge #779: travis: Fix argument quoting for ./configure
9e49a9b255 travis: Fix argument quoting for ./configure
18d36327fd secp256k1_gej_double_nonzero supports infinity
214cb3c321 Merge #772: Improve constant-timeness on PowerPC
40412b1930 Merge #774: tests: Abort if malloc() fails during context cloning tests
2e1b9e0458 tests: Abort if malloc() fails during context cloning tests
67a429f31f Suppress a harmless variable-time optimization by clang in _int_cmov
5b196338f0 Remove redundant "? 1 : 0" after comparisons in scalar code
3e5cfc5c73 Merge #741: Remove unnecessary sign variable from wnaf_const
66bb9320c0 Merge #773: Fix some compile problems on weird/old compilers.
1309c03c45 Fix some compile problems on weird/old compilers.
2309c7dd4a Merge #769: Undef HAVE___INT128 in basic-config.h to fix gen_context compilation
22e578bb11 Undef HAVE___INT128 in basic-config.h to fix gen_context compilation
3f4a5a10e4 Merge #765: remove dead store in ecdsa_signature_parse_der_lax
f00d6575ca remove dead store in ecdsa_signature_parse_der_lax
dbd41db16a Merge #759: Fix uninitialized variables in ecmult_multi test
2e7fc5b537 Fix uninitialized variables in ecmult_multi test
37dba329c6 Remove unnecessary sign variable from wnaf_const
6bb0b77e15 Fix test_constant_wnaf for -1 and add a test for it.
47a7b8382f Clear field elements when writing infinity
61d1ecb028 Added test with additions resulting in infinity
60f7f2de5d Don't assume that ALIGNMENT > 1 in tests
ada6361dec Use ROUND_TO_ALIGN in scratch_create
8ecc6ce50e Add check preventing rounding to alignment from wrapping around in scratch_alloc
4edaf06fb0 Add check preventing integer multiplication wrapping around in scratch_max_allocation

git-subtree-dir: src/secp256k1
git-subtree-split: 8ab24e8dad9d43fc6661842149899e3cc9213b24

3 files changed, 348 insertions, 1 deletions

diff --git a/include/secp256k1.h b/include/secp256k1.h
index 2ba2dca388..2178c8e2d6 100644
--- a/include/secp256k1.h
+++ b/include/secp256k1.h
@@ -134,7 +134,7 @@ typedef int (*secp256k1_nonce_function)(
 #  else
 #   define SECP256K1_API
 #  endif
-# elif defined(__GNUC__) && defined(SECP256K1_BUILD)
+# elif defined(__GNUC__) && (__GNUC__ >= 4) && defined(SECP256K1_BUILD)
 #  define SECP256K1_API __attribute__ ((visibility ("default")))
 # else
 #  define SECP256K1_API
diff --git a/include/secp256k1_extrakeys.h b/include/secp256k1_extrakeys.h
new file mode 100644
index 0000000000..0c5dff2c94
--- /dev/null
+++ b/include/secp256k1_extrakeys.h
@@ -0,0 +1,236 @@
+#ifndef SECP256K1_EXTRAKEYS_H
+#define SECP256K1_EXTRAKEYS_H
+
+#include "secp256k1.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** Opaque data structure that holds a parsed and valid "x-only" public key.
+ *  An x-only pubkey encodes a point whose Y coordinate is even. It is
+ *  serialized using only its X coordinate (32 bytes). See BIP-340 for more
+ *  information about x-only pubkeys.
+ *
+ *  The exact representation of data inside is implementation defined and not
+ *  guaranteed to be portable between different platforms or versions. It is
+ *  however guaranteed to be 64 bytes in size, and can be safely copied/moved.
+ *  If you need to convert to a format suitable for storage, transmission, or
+ *  comparison, use secp256k1_xonly_pubkey_serialize and
+ *  secp256k1_xonly_pubkey_parse.
+ */
+typedef struct {
+    unsigned char data[64];
+} secp256k1_xonly_pubkey;
+
+/** Opaque data structure that holds a keypair consisting of a secret and a
+ *  public key.
+ *
+ *  The exact representation of data inside is implementation defined and not
+ *  guaranteed to be portable between different platforms or versions. It is
+ *  however guaranteed to be 96 bytes in size, and can be safely copied/moved.
+ */
+typedef struct {
+    unsigned char data[96];
+} secp256k1_keypair;
+
+/** Parse a 32-byte sequence into a xonly_pubkey object.
+ *
+ *  Returns: 1 if the public key was fully valid.
+ *           0 if the public key could not be parsed or is invalid.
+ *
+ *  Args:   ctx: a secp256k1 context object (cannot be NULL).
+ *  Out: pubkey: pointer to a pubkey object. If 1 is returned, it is set to a
+ *               parsed version of input. If not, it's set to an invalid value.
+ *               (cannot be NULL).
+ *  In: input32: pointer to a serialized xonly_pubkey (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_parse(
+    const secp256k1_context* ctx,
+    secp256k1_xonly_pubkey* pubkey,
+    const unsigned char *input32
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+/** Serialize an xonly_pubkey object into a 32-byte sequence.
+ *
+ *  Returns: 1 always.
+ *
+ *  Args:     ctx: a secp256k1 context object (cannot be NULL).
+ *  Out: output32: a pointer to a 32-byte array to place the serialized key in
+ *                 (cannot be NULL).
+ *  In:    pubkey: a pointer to a secp256k1_xonly_pubkey containing an
+ *                 initialized public key (cannot be NULL).
+ */
+SECP256K1_API int secp256k1_xonly_pubkey_serialize(
+    const secp256k1_context* ctx,
+    unsigned char *output32,
+    const secp256k1_xonly_pubkey* pubkey
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+/** Converts a secp256k1_pubkey into a secp256k1_xonly_pubkey.
+ *
+ *  Returns: 1 if the public key was successfully converted
+ *           0 otherwise
+ *
+ *  Args:         ctx: pointer to a context object (cannot be NULL)
+ *  Out: xonly_pubkey: pointer to an x-only public key object for placing the
+ *                     converted public key (cannot be NULL)
+ *          pk_parity: pointer to an integer that will be set to 1 if the point
+ *                     encoded by xonly_pubkey is the negation of the pubkey and
+ *                     set to 0 otherwise. (can be NULL)
+ *  In:        pubkey: pointer to a public key that is converted (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_from_pubkey(
+    const secp256k1_context* ctx,
+    secp256k1_xonly_pubkey *xonly_pubkey,
+    int *pk_parity,
+    const secp256k1_pubkey *pubkey
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4);
+
+/** Tweak an x-only public key by adding the generator multiplied with tweak32
+ *  to it.
+ *
+ *  Note that the resulting point can not in general be represented by an x-only
+ *  pubkey because it may have an odd Y coordinate. Instead, the output_pubkey
+ *  is a normal secp256k1_pubkey.
+ *
+ *  Returns: 0 if the arguments are invalid or the resulting public key would be
+ *           invalid (only when the tweak is the negation of the corresponding
+ *           secret key). 1 otherwise.
+ *
+ *  Args:           ctx: pointer to a context object initialized for verification
+ *                       (cannot be NULL)
+ *  Out:  output_pubkey: pointer to a public key to store the result. Will be set
+ *                       to an invalid value if this function returns 0 (cannot
+ *                       be NULL)
+ *  In: internal_pubkey: pointer to an x-only pubkey to apply the tweak to.
+ *                       (cannot be NULL).
+ *              tweak32: pointer to a 32-byte tweak. If the tweak is invalid
+ *                       according to secp256k1_ec_seckey_verify, this function
+ *                       returns 0. For uniformly random 32-byte arrays the
+ *                       chance of being invalid is negligible (around 1 in
+ *                       2^128) (cannot be NULL).
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_add(
+    const secp256k1_context* ctx,
+    secp256k1_pubkey *output_pubkey,
+    const secp256k1_xonly_pubkey *internal_pubkey,
+    const unsigned char *tweak32
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
+
+/** Checks that a tweaked pubkey is the result of calling
+ *  secp256k1_xonly_pubkey_tweak_add with internal_pubkey and tweak32.
+ *
+ *  The tweaked pubkey is represented by its 32-byte x-only serialization and
+ *  its pk_parity, which can both be obtained by converting the result of
+ *  tweak_add to a secp256k1_xonly_pubkey.
+ *
+ *  Note that this alone does _not_ verify that the tweaked pubkey is a
+ *  commitment. If the tweak is not chosen in a specific way, the tweaked pubkey
+ *  can easily be the result of a different internal_pubkey and tweak.
+ *
+ *  Returns: 0 if the arguments are invalid or the tweaked pubkey is not the
+ *           result of tweaking the internal_pubkey with tweak32. 1 otherwise.
+ *  Args:            ctx: pointer to a context object initialized for verification
+ *                       (cannot be NULL)
+ *  In: tweaked_pubkey32: pointer to a serialized xonly_pubkey (cannot be NULL)
+ *     tweaked_pk_parity: the parity of the tweaked pubkey (whose serialization
+ *                        is passed in as tweaked_pubkey32). This must match the
+ *                        pk_parity value that is returned when calling
+ *                        secp256k1_xonly_pubkey with the tweaked pubkey, or
+ *                        this function will fail.
+ *       internal_pubkey: pointer to an x-only public key object to apply the
+ *                        tweak to (cannot be NULL)
+ *               tweak32: pointer to a 32-byte tweak (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_add_check(
+    const secp256k1_context* ctx,
+    const unsigned char *tweaked_pubkey32,
+    int tweaked_pk_parity,
+    const secp256k1_xonly_pubkey *internal_pubkey,
+    const unsigned char *tweak32
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
+
+/** Compute the keypair for a secret key.
+ *
+ *  Returns: 1: secret was valid, keypair is ready to use
+ *           0: secret was invalid, try again with a different secret
+ *  Args:    ctx: pointer to a context object, initialized for signing (cannot be NULL)
+ *  Out: keypair: pointer to the created keypair (cannot be NULL)
+ *  In:   seckey: pointer to a 32-byte secret key (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_create(
+    const secp256k1_context* ctx,
+    secp256k1_keypair *keypair,
+    const unsigned char *seckey
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+/** Get the public key from a keypair.
+ *
+ *  Returns: 0 if the arguments are invalid. 1 otherwise.
+ *  Args:    ctx: pointer to a context object (cannot be NULL)
+ *  Out: pubkey: pointer to a pubkey object. If 1 is returned, it is set to
+ *               the keypair public key. If not, it's set to an invalid value.
+ *               (cannot be NULL)
+ *  In: keypair: pointer to a keypair (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_pub(
+    const secp256k1_context* ctx,
+    secp256k1_pubkey *pubkey,
+    const secp256k1_keypair *keypair
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+/** Get the x-only public key from a keypair.
+ *
+ *  This is the same as calling secp256k1_keypair_pub and then
+ *  secp256k1_xonly_pubkey_from_pubkey.
+ *
+ *  Returns: 0 if the arguments are invalid. 1 otherwise.
+ *  Args:   ctx: pointer to a context object (cannot be NULL)
+ *  Out: pubkey: pointer to an xonly_pubkey object. If 1 is returned, it is set
+ *               to the keypair public key after converting it to an
+ *               xonly_pubkey. If not, it's set to an invalid value (cannot be
+ *               NULL).
+ *    pk_parity: pointer to an integer that will be set to the pk_parity
+ *               argument of secp256k1_xonly_pubkey_from_pubkey (can be NULL).
+ *  In: keypair: pointer to a keypair (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_xonly_pub(
+    const secp256k1_context* ctx,
+    secp256k1_xonly_pubkey *pubkey,
+    int *pk_parity,
+    const secp256k1_keypair *keypair
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(4);
+
+/** Tweak a keypair by adding tweak32 to the secret key and updating the public
+ *  key accordingly.
+ *
+ *  Calling this function and then secp256k1_keypair_pub results in the same
+ *  public key as calling secp256k1_keypair_xonly_pub and then
+ *  secp256k1_xonly_pubkey_tweak_add.
+ *
+ *  Returns: 0 if the arguments are invalid or the resulting keypair would be
+ *           invalid (only when the tweak is the negation of the keypair's
+ *           secret key). 1 otherwise.
+ *
+ *  Args:       ctx: pointer to a context object initialized for verification
+ *                   (cannot be NULL)
+ *  In/Out: keypair: pointer to a keypair to apply the tweak to. Will be set to
+ *                   an invalid value if this function returns 0 (cannot be
+ *                   NULL).
+ *  In:     tweak32: pointer to a 32-byte tweak. If the tweak is invalid according
+ *                   to secp256k1_ec_seckey_verify, this function returns 0. For
+ *                   uniformly random 32-byte arrays the chance of being invalid
+ *                   is negligible (around 1 in 2^128) (cannot be NULL).
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_keypair_xonly_tweak_add(
+    const secp256k1_context* ctx,
+    secp256k1_keypair *keypair,
+    const unsigned char *tweak32
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* SECP256K1_EXTRAKEYS_H */
diff --git a/include/secp256k1_schnorrsig.h b/include/secp256k1_schnorrsig.h
new file mode 100644
index 0000000000..0150cd3395
--- /dev/null
+++ b/include/secp256k1_schnorrsig.h
@@ -0,0 +1,111 @@
+#ifndef SECP256K1_SCHNORRSIG_H
+#define SECP256K1_SCHNORRSIG_H
+
+#include "secp256k1.h"
+#include "secp256k1_extrakeys.h"
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+/** This module implements a variant of Schnorr signatures compliant with
+ *  Bitcoin Improvement Proposal 340 "Schnorr Signatures for secp256k1"
+ *  (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).
+ */
+
+/** A pointer to a function to deterministically generate a nonce.
+ *
+ *  Same as secp256k1_nonce function with the exception of accepting an
+ *  additional pubkey argument and not requiring an attempt argument. The pubkey
+ *  argument can protect signature schemes with key-prefixed challenge hash
+ *  inputs against reusing the nonce when signing with the wrong precomputed
+ *  pubkey.
+ *
+ *  Returns: 1 if a nonce was successfully generated. 0 will cause signing to
+ *           return an error.
+ *  Out:     nonce32:   pointer to a 32-byte array to be filled by the function.
+ *  In:      msg32:     the 32-byte message hash being verified (will not be NULL)
+ *           key32:     pointer to a 32-byte secret key (will not be NULL)
+ *      xonly_pk32:     the 32-byte serialized xonly pubkey corresponding to key32
+ *                      (will not be NULL)
+ *           algo16:    pointer to a 16-byte array describing the signature
+ *                      algorithm (will not be NULL).
+ *           data:      Arbitrary data pointer that is passed through.
+ *
+ *  Except for test cases, this function should compute some cryptographic hash of
+ *  the message, the key, the pubkey, the algorithm description, and data.
+ */
+typedef int (*secp256k1_nonce_function_hardened)(
+    unsigned char *nonce32,
+    const unsigned char *msg32,
+    const unsigned char *key32,
+    const unsigned char *xonly_pk32,
+    const unsigned char *algo16,
+    void *data
+);
+
+/** An implementation of the nonce generation function as defined in Bitcoin
+ *  Improvement Proposal 340 "Schnorr Signatures for secp256k1"
+ *  (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).
+ *
+ *  If a data pointer is passed, it is assumed to be a pointer to 32 bytes of
+ *  auxiliary random data as defined in BIP-340. If the data pointer is NULL,
+ *  schnorrsig_sign does not produce BIP-340 compliant signatures. The algo16
+ *  argument must be non-NULL, otherwise the function will fail and return 0.
+ *  The hash will be tagged with algo16 after removing all terminating null
+ *  bytes. Therefore, to create BIP-340 compliant signatures, algo16 must be set
+ *  to "BIP0340/nonce\0\0\0"
+ */
+SECP256K1_API extern const secp256k1_nonce_function_hardened secp256k1_nonce_function_bip340;
+
+/** Create a Schnorr signature.
+ *
+ *  Does _not_ strictly follow BIP-340 because it does not verify the resulting
+ *  signature. Instead, you can manually use secp256k1_schnorrsig_verify and
+ *  abort if it fails.
+ *
+ *  Otherwise BIP-340 compliant if the noncefp argument is NULL or
+ *  secp256k1_nonce_function_bip340 and the ndata argument is 32-byte auxiliary
+ *  randomness.
+ *
+ *  Returns 1 on success, 0 on failure.
+ *  Args:    ctx: pointer to a context object, initialized for signing (cannot be NULL)
+ *  Out:   sig64: pointer to a 64-byte array to store the serialized signature (cannot be NULL)
+ *  In:    msg32: the 32-byte message being signed (cannot be NULL)
+ *       keypair: pointer to an initialized keypair (cannot be NULL)
+ *       noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bip340 is used
+ *         ndata: pointer to arbitrary data used by the nonce generation
+ *                function (can be NULL). If it is non-NULL and
+ *                secp256k1_nonce_function_bip340 is used, then ndata must be a
+ *                pointer to 32-byte auxiliary randomness as per BIP-340.
+ */
+SECP256K1_API int secp256k1_schnorrsig_sign(
+    const secp256k1_context* ctx,
+    unsigned char *sig64,
+    const unsigned char *msg32,
+    const secp256k1_keypair *keypair,
+    secp256k1_nonce_function_hardened noncefp,
+    void *ndata
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
+
+/** Verify a Schnorr signature.
+ *
+ *  Returns: 1: correct signature
+ *           0: incorrect signature
+ *  Args:    ctx: a secp256k1 context object, initialized for verification.
+ *  In:    sig64: pointer to the 64-byte signature to verify (cannot be NULL)
+ *         msg32: the 32-byte message being verified (cannot be NULL)
+ *        pubkey: pointer to an x-only public key to verify with (cannot be NULL)
+ */
+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_schnorrsig_verify(
+    const secp256k1_context* ctx,
+    const unsigned char *sig64,
+    const unsigned char *msg32,
+    const secp256k1_xonly_pubkey *pubkey
+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif /* SECP256K1_SCHNORRSIG_H */