Bitcoin Core  0.20.99
P2P Digital Currency
tests_exhaustive_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2020 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #ifndef _SECP256K1_MODULE_SCHNORRSIG_TESTS_EXHAUSTIVE_
8 #define _SECP256K1_MODULE_SCHNORRSIG_TESTS_EXHAUSTIVE_
9 
12 
13 static const unsigned char invalid_pubkey_bytes[][32] = {
14  /* 0 */
15  {
16  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
17  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
18  },
19  /* 2 */
20  {
21  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
22  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2
23  },
24  /* order */
25  {
26  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
27  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
28  ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 24) & 0xFF,
29  ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 16) & 0xFF,
30  ((EXHAUSTIVE_TEST_ORDER + 0UL) >> 8) & 0xFF,
31  (EXHAUSTIVE_TEST_ORDER + 0UL) & 0xFF
32  },
33  /* order + 1 */
34  {
35  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
36  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
37  ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 24) & 0xFF,
38  ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 16) & 0xFF,
39  ((EXHAUSTIVE_TEST_ORDER + 1UL) >> 8) & 0xFF,
40  (EXHAUSTIVE_TEST_ORDER + 1UL) & 0xFF
41  },
42  /* field size */
43  {
44  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
45  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x2F
46  },
47  /* field size + 1 (note that 1 is legal) */
48  {
49  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
50  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFC, 0x30
51  },
52  /* 2^256 - 1 */
53  {
54  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
55  0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF
56  }
57 };
58 
59 #define NUM_INVALID_KEYS (sizeof(invalid_pubkey_bytes) / sizeof(invalid_pubkey_bytes[0]))
60 
61 static int secp256k1_hardened_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32,
62  const unsigned char *key32, const unsigned char *xonly_pk32,
63  const unsigned char *algo16, void* data) {
65  int *idata = data;
66  (void)msg32;
67  (void)key32;
68  (void)xonly_pk32;
69  (void)algo16;
70  secp256k1_scalar_set_int(&s, *idata);
71  secp256k1_scalar_get_b32(nonce32, &s);
72  return 1;
73 }
74 
75 static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, const secp256k1_xonly_pubkey* pubkeys, unsigned char (*xonly_pubkey_bytes)[32], const int* parities) {
76  int d;
77  uint64_t iter = 0;
78  /* Iterate over the possible public keys to verify against (through their corresponding DL d). */
79  for (d = 1; d <= EXHAUSTIVE_TEST_ORDER / 2; ++d) {
80  int actual_d;
81  unsigned k;
82  unsigned char pk32[32];
83  memcpy(pk32, xonly_pubkey_bytes[d - 1], 32);
84  actual_d = parities[d - 1] ? EXHAUSTIVE_TEST_ORDER - d : d;
85  /* Iterate over the possible valid first 32 bytes in the signature, through their corresponding DL k.
86  Values above EXHAUSTIVE_TEST_ORDER/2 refer to the entries in invalid_pubkey_bytes. */
87  for (k = 1; k <= EXHAUSTIVE_TEST_ORDER / 2 + NUM_INVALID_KEYS; ++k) {
88  unsigned char sig64[64];
89  int actual_k = -1;
90  int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
91  int e_count_done = 0;
92  if (skip_section(&iter)) continue;
93  if (k <= EXHAUSTIVE_TEST_ORDER / 2) {
94  memcpy(sig64, xonly_pubkey_bytes[k - 1], 32);
95  actual_k = parities[k - 1] ? EXHAUSTIVE_TEST_ORDER - k : k;
96  } else {
97  memcpy(sig64, invalid_pubkey_bytes[k - 1 - EXHAUSTIVE_TEST_ORDER / 2], 32);
98  }
99  /* Randomly generate messages until all challenges have been hit. */
100  while (e_count_done < EXHAUSTIVE_TEST_ORDER) {
102  unsigned char msg32[32];
103  secp256k1_testrand256(msg32);
104  secp256k1_schnorrsig_challenge(&e, sig64, msg32, pk32);
105  /* Only do work if we hit a challenge we haven't tried before. */
106  if (!e_done[e]) {
107  /* Iterate over the possible valid last 32 bytes in the signature.
108  0..order=that s value; order+1=random bytes */
109  int count_valid = 0, s;
110  for (s = 0; s <= EXHAUSTIVE_TEST_ORDER + 1; ++s) {
111  int expect_valid, valid;
112  if (s <= EXHAUSTIVE_TEST_ORDER) {
113  secp256k1_scalar s_s;
114  secp256k1_scalar_set_int(&s_s, s);
115  secp256k1_scalar_get_b32(sig64 + 32, &s_s);
116  expect_valid = actual_k != -1 && s != EXHAUSTIVE_TEST_ORDER &&
117  (s_s == (actual_k + actual_d * e) % EXHAUSTIVE_TEST_ORDER);
118  } else {
119  secp256k1_testrand256(sig64 + 32);
120  expect_valid = 0;
121  }
122  valid = secp256k1_schnorrsig_verify(ctx, sig64, msg32, &pubkeys[d - 1]);
123  CHECK(valid == expect_valid);
124  count_valid += valid;
125  }
126  /* Exactly one s value must verify, unless R is illegal. */
127  CHECK(count_valid == (actual_k != -1));
128  /* Don't retry other messages that result in the same challenge. */
129  e_done[e] = 1;
130  ++e_count_done;
131  }
132  }
133  }
134  }
135 }
136 
137 static void test_exhaustive_schnorrsig_sign(const secp256k1_context *ctx, unsigned char (*xonly_pubkey_bytes)[32], const secp256k1_keypair* keypairs, const int* parities) {
138  int d, k;
139  uint64_t iter = 0;
140  /* Loop over keys. */
141  for (d = 1; d < EXHAUSTIVE_TEST_ORDER; ++d) {
142  int actual_d = d;
143  if (parities[d - 1]) actual_d = EXHAUSTIVE_TEST_ORDER - d;
144  /* Loop over nonces. */
145  for (k = 1; k < EXHAUSTIVE_TEST_ORDER; ++k) {
146  int e_done[EXHAUSTIVE_TEST_ORDER] = {0};
147  int e_count_done = 0;
148  unsigned char msg32[32];
149  unsigned char sig64[64];
150  int actual_k = k;
151  if (skip_section(&iter)) continue;
152  if (parities[k - 1]) actual_k = EXHAUSTIVE_TEST_ORDER - k;
153  /* Generate random messages until all challenges have been tried. */
154  while (e_count_done < EXHAUSTIVE_TEST_ORDER) {
156  secp256k1_testrand256(msg32);
157  secp256k1_schnorrsig_challenge(&e, xonly_pubkey_bytes[k - 1], msg32, xonly_pubkey_bytes[d - 1]);
158  /* Only do work if we hit a challenge we haven't tried before. */
159  if (!e_done[e]) {
160  secp256k1_scalar expected_s = (actual_k + e * actual_d) % EXHAUSTIVE_TEST_ORDER;
161  unsigned char expected_s_bytes[32];
162  secp256k1_scalar_get_b32(expected_s_bytes, &expected_s);
163  /* Invoke the real function to construct a signature. */
164  CHECK(secp256k1_schnorrsig_sign(ctx, sig64, msg32, &keypairs[d - 1], secp256k1_hardened_nonce_function_smallint, &k));
165  /* The first 32 bytes must match the xonly pubkey for the specified k. */
166  CHECK(secp256k1_memcmp_var(sig64, xonly_pubkey_bytes[k - 1], 32) == 0);
167  /* The last 32 bytes must match the expected s value. */
168  CHECK(secp256k1_memcmp_var(sig64 + 32, expected_s_bytes, 32) == 0);
169  /* Don't retry other messages that result in the same challenge. */
170  e_done[e] = 1;
171  ++e_count_done;
172  }
173  }
174  }
175  }
176 }
177 
181  int parity[EXHAUSTIVE_TEST_ORDER - 1];
182  unsigned char xonly_pubkey_bytes[EXHAUSTIVE_TEST_ORDER - 1][32];
183  unsigned i;
184 
185  /* Verify that all invalid_pubkey_bytes are actually invalid. */
186  for (i = 0; i < NUM_INVALID_KEYS; ++i) {
189  }
190 
191  /* Construct keypairs and xonly-pubkeys for the entire group. */
192  for (i = 1; i < EXHAUSTIVE_TEST_ORDER; ++i) {
193  secp256k1_scalar scalar_i;
194  unsigned char buf[32];
195  secp256k1_scalar_set_int(&scalar_i, i);
196  secp256k1_scalar_get_b32(buf, &scalar_i);
197  CHECK(secp256k1_keypair_create(ctx, &keypair[i - 1], buf));
198  CHECK(secp256k1_keypair_xonly_pub(ctx, &xonly_pubkey[i - 1], &parity[i - 1], &keypair[i - 1]));
199  CHECK(secp256k1_xonly_pubkey_serialize(ctx, xonly_pubkey_bytes[i - 1], &xonly_pubkey[i - 1]));
200  }
201 
202  test_exhaustive_schnorrsig_sign(ctx, xonly_pubkey_bytes, keypair, parity);
203  test_exhaustive_schnorrsig_verify(ctx, xonly_pubkey, xonly_pubkey_bytes, parity);
204 }
205 
206 #endif
static void secp256k1_testrand256(unsigned char *b32)
Generate a pseudorandom 32-byte array.
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)
Compute the keypair for a secret key.
Definition: main_impl.h:171
static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, const secp256k1_xonly_pubkey *pubkeys, unsigned char(*xonly_pubkey_bytes)[32], const int *parities)
static SECP256K1_INLINE int skip_section(uint64_t *iter)
static void test_exhaustive_schnorrsig(const secp256k1_context *ctx)
Opaque data structure that holds a parsed and valid "x-only" public key.
static const unsigned char invalid_pubkey_bytes[][32]
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)
Parse a 32-byte sequence into a xonly_pubkey object.
Definition: main_impl.h:21
static secp256k1_context * ctx
Definition: tests.c:36
#define NUM_INVALID_KEYS
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)
Get the x-only public key from a keypair.
Definition: main_impl.h:199
#define CHECK(cond)
Definition: util.h:53
A scalar modulo the group order of the secp256k1 curve.
Definition: scalar_4x64.h:13
Opaque data structure that holds a keypair consisting of a secret and a public key.
static void secp256k1_scalar_get_b32(unsigned char *bin, const secp256k1_scalar *a)
Convert a scalar to a byte array.
#define EXHAUSTIVE_TEST_ORDER
static void secp256k1_scalar_set_int(secp256k1_scalar *r, unsigned int v)
Set a scalar to an unsigned integer.
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)
Create a Schnorr signature.
Definition: main_impl.h:127
void * memcpy(void *a, const void *b, size_t c)
static SECP256K1_INLINE int secp256k1_memcmp_var(const void *s1, const void *s2, size_t n)
Semantics like memcmp.
Definition: util.h:224
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)
Serialize an xonly_pubkey object into a 32-byte sequence.
Definition: main_impl.h:43
static void secp256k1_schnorrsig_challenge(secp256k1_scalar *e, const unsigned char *r32, const unsigned char *msg32, const unsigned char *pubkey32)
Definition: main_impl.h:111
static int secp256k1_hardened_nonce_function_smallint(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *xonly_pk32, const unsigned char *algo16, void *data)
static void test_exhaustive_schnorrsig_sign(const secp256k1_context *ctx, unsigned char(*xonly_pubkey_bytes)[32], const secp256k1_keypair *keypairs, const int *parities)
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)
Verify a Schnorr signature.
Definition: main_impl.h:190