This PR implements signing, verification and batch verification as described in BIP-340 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-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.
784+ x8 += LE32(seed32[4]);
785+ x9 += LE32(seed32[5]);
786+ x10 += LE32(seed32[6]);
787+ x11 += LE32(seed32[7]);
788+ x12 += idx;
789+ x13 += idx >> 32;
Travis with 32-bit size_t is failing because:
0./src/scalar_8x32_impl.h:760:19: warning: shift count >= width of type [-Wshift-count-overflow]
1 x13 = idx >> 32;
2 ^ ~~
3./src/scalar_8x32_impl.h:789:20: warning: shift count >= width of type [-Wshift-count-overflow]
4 x13 += idx >> 32;
I’d replace the size_t above with uint32_t or uint64_t.
Good catch. See also the version of this commit in secp-zkp (where Tim suggests making all the size_ts be uint64_ts.)
idx has been changed to uint64_t.
70+ const secp256k1_context* ctx,
71+ secp256k1_schnorrsig *sig,
72+ const unsigned char *msg32,
73+ const unsigned char *seckey,
74+ secp256k1_nonce_function noncefp,
75+ const void *ndata
292+
293+ VERIFY_CHECK(ctx != NULL);
294+ ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx));
295+ ARG_CHECK(scratch != NULL);
296+
297+ secp256k1_sha256_initialize(&sha);
sha object into secp256k1_schnorrsig_verify_batch_init_randomizer?
An argument against that is that it makes combining multiple init_randomizers less succinct. With a shared sha object it’d look like
0 secp256k1_sha256_initialize(&sha);
1 secp256k1_schnorr_verify_init_randomizer(ctx, &ecmult_data.schnorr, &sha, sig, msg32, pk, n_sigs);
2 secp256k1_taproot_verify_init_randomizer(ctx, &sha, ...);
3 secp256k1_sha256_finalize(&sha, ecmult_data.schnorr.chacha_seed);
sha object, bikeshedding about the module name, and also I did not check that the static test vectors match those in the BIP.
80+ data.msgs = (const unsigned char **)malloc(MAX_SIGS * 32);
81+ data.sigs = (const secp256k1_schnorrsig **)malloc(MAX_SIGS * sizeof(*data.sigs));
82+
83+ for (i = 0; i < MAX_SIGS; i++) {
84+ unsigned char sk[32];
85+ unsigned char *msg = malloc(32);
74+ size_t i;
75+ bench_schnorrsig_data data;
76+
77+ data.ctx = secp256k1_context_create(SECP256K1_CONTEXT_VERIFY | SECP256K1_CONTEXT_SIGN);
78+ data.scratch = secp256k1_scratch_space_create(data.ctx, 1024 * 1024 * 1024);
79+ data.pk = (const unsigned char **)malloc(MAX_SIGS * 33);
MAX_SIGS * sizeof(unsigned char*)? (Same below)
81+ data.sigs = (const secp256k1_schnorrsig **)malloc(MAX_SIGS * sizeof(*data.sigs));
82+
83+ for (i = 0; i < MAX_SIGS; i++) {
84+ unsigned char sk[32];
85+ unsigned char *msg = malloc(32);
86+ secp256k1_schnorrsig *sig = (secp256k1_schnorrsig *)malloc(sizeof(*sig));
bench_* function is not measured by the tool and it would increase code complexity.
24+} bench_schnorrsig_data;
25+
26+void bench_schnorrsig_sign(void* arg) {
27+ bench_schnorrsig_data *data = (bench_schnorrsig_data *)arg;
28+ size_t i;
29+ unsigned char sk[32] = "benchmarkexample secrettemplate";
data->sk[i] (which could easily be added to the data struct) and data->msgs[i]?
malloc is a PITA to use :P
bench_schnorrsig_verify and bench_schnorrsig_verify_n use the malloc’ed data while this doesn’t. Feel free to ignore though.
68+ */
69+SECP256K1_API int secp256k1_schnorrsig_sign(
70+ const secp256k1_context* ctx,
71+ secp256k1_schnorrsig *sig,
72+ const unsigned char *msg32,
73+ const unsigned char *seckey,
secp256k1_scalar *, like in the ecdsa_sig_sign interface?
secp256k1_scalar is not a public type.
59+ }
60+
61+ secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pkj, &x);
62+ secp256k1_ge_set_gej(&pk, &pkj);
63+
64+ if(!noncefp(buf, msg32, seckey, NULL, (void*)ndata, 0)) {
if is inconsistent in this file.
298+ if(!secp256k1_schnorrsig_verify_batch_init_randomizer(ctx, &ecmult_context, &sha, sig, msg32, pk, n_sigs)) {
299+ return 0;
300+ }
301+ secp256k1_sha256_finalize(&sha, ecmult_context.chacha_seed);
302+
303+ secp256k1_scalar_clear(&s);
schnorrsig_verify_batch_sum_s
I’d prefer to have it outside of batch_sum_s to allow combining similar helper functions in a more general batch verification function like
0 secp256k1_scalar_clear(&s);
1 secp256k1_schnorrsig_verify_batch_sum_s(&s, ecmult_context.chacha_seed, sig, n_sigs)
2 secp256k1_taproot_verify_init(&s, ...);
I added better documentation to this helper function instead.
198+ }
199+
200+ /* -R */
201+ if (idx % 2 == 0) {
202+ secp256k1_fe rx;
203+ secp256k1_scalar_negate(sc, &ecmult_context->randomizer_cache[(idx / 2) % 2]);
sum_s term in verify_batch rather than each one here.
Nice! Such hype.
I skipped the tests, hoping to get back around to them.
@gmaxwell By anti-covert channel do you mean essentially sign-to-contracting random data? I would like this. One thing blocking it is that our nonce function does not take a secp context currently, which makes sign-to-contract unergonmic – see in sighacker how the sign-to-contract context needs to contain a pointer to the secp context.
I think we should fix that but it should probably be in another PR.
286+
287+ for (i = 0; i < n_sigs; i++) {
288+ int overflow;
289+ secp256k1_scalar term;
290+ if (i % 2 == 0) {
291+ secp256k1_schnorrsig_batch_randomizer(randomizer_cache, chacha_seed, i / 2);
Currently, we discard one random value in secp256k1_schnorrsig_batch_randomizer(). We could instead
randomizer_cache[0] with 1i % 2 == 1secp256k1_schnorrsig_batch_randomizer())&r[0] and &r[1] in secp256k1_schnorrsig_batch_randomizer()` to make sure we don’t use the scalars in a weird order – but who cares?)And similarly for the other side of the verification equation / ecmult. I think that’ll be i % 4 == 2
0@@ -1,6 +1,7 @@
1 bench_inv
2 bench_ecdh
3 bench_ecmult
4+bench_schnorrsig
5 bench_sign
6 bench_verify
7 bench_schnorr_verify
17+ */
18+typedef struct {
19+ unsigned char data[64];
20+} secp256k1_schnorrsig;
21+
22+/** Serialize a Schnorr signature
. at end of line
89+ const secp256k1_schnorrsig *sig,
90+ const unsigned char *msg32,
91+ const secp256k1_pubkey *pubkey
92+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
93+
94+/** Verifies a set of Schnorr signatures
271+}
272+
273+/** Helper function for batch verification. Sums the s part of all signatures multiplied by their
274+ * randomizer.
275+ *
276+ * Returns 1 if s is successfully summed.
325+ if (!secp256k1_schnorrsig_verify_batch_sum_s(&s, ecmult_context.chacha_seed, sig, n_sigs)) {
326+ return 0;
327+ }
328+ secp256k1_scalar_negate(&s, &s);
329+
330+ return secp256k1_ecmult_multi_var(&ctx->ecmult_ctx, scratch, &rj, &s, secp256k1_schnorrsig_verify_batch_ecmult_callback, (void *) &ecmult_context, 2 * n_sigs)
Possible integer overflow in 2 * n_sigs.
Okay, I need to give you at least 2^31 signatures (each one with s = 0) to exploit that, but then all my signatures suddenly verify. :P
305@@ -314,12 +306,19 @@ int secp256k1_schnorrsig_verify_batch(const secp256k1_context *ctx, secp256k1_sc
306 VERIFY_CHECK(ctx != NULL);
307 ARG_CHECK(secp256k1_ecmult_context_is_built(&ctx->ecmult_ctx));
308 ARG_CHECK(scratch != NULL);
309+ /* Check that n_sigs is less than half of the maximum size_t value. This is necessary because
310+ * the number of points given to ecmult_multi is 2*n_sigs. */
311+ ARG_CHECK(n_sigs < (size_t)1 << (sizeof(size_t)*8-1));
1 << sizeof(size_t)*8-1 is not necessarily half of the maximum value that can be represented by size_t. For example, there could be unused “padding bits” in the integer. This is only a problem on exotic platforms that we don’t support anyway but yeah… Anyway, a simpler expression is MAX_SIZE >> 1 (only in C99) or equivalently (size_t)(-1) >> 1 because we want C89.
BUT I don’t know if we need to go this far, I guess there are a lot of places where the code anyway assumes that size_t is at least 32 bits. So we probably can just use the check below? @sipa
(size_t)(-1) >> 1 because it’s easier to read. Or even use / 2 instead of >> 1, this will be evaluated at compile-time anyway.
1013+ secp256k1_scalar_chacha20(&r1, &r2, seed1, 100);
1014+ secp256k1_scalar_set_b32(&exp_r1, &expected3[0], NULL);
1015+ secp256k1_scalar_set_b32(&exp_r2, &expected3[32], NULL);
1016+ CHECK(secp256k1_scalar_eq(&exp_r1, &r1));
1017+ CHECK(secp256k1_scalar_eq(&exp_r2, &r2));
1018+}
It’s perhaps useful to add one test case with some arbitrary input and position, to make sure an implementation isn’t swapping some of the first 31 bytes of the input seed for example.
Here is a suggestion:
0+ unsigned char input4[32] = {
1+ 0x32, 0x56, 0x56, 0xf4, 0x29, 0x02, 0xc2, 0xf8,
2+ 0xa3, 0x4b, 0x96, 0xf5, 0xa7, 0xf7, 0xe3, 0x6c,
3+ 0x92, 0xad, 0xa5, 0x18, 0x1c, 0xe3, 0x41, 0xae,
4+ 0xc3, 0xf3, 0x18, 0xd0, 0xfa, 0x5b, 0x72, 0x53
5+ };
6+ unsigned char expected4[64] = {
7+ 0x28, 0xd3, 0x56, 0xe7, 0x5c, 0x19, 0xc6, 0xe9,
8+ 0x21, 0x8e, 0x17, 0x6f, 0x11, 0x72, 0x1e, 0x8c,
9+ 0x0d, 0x17, 0xbd, 0xe7, 0xe9, 0xad, 0x14, 0xac,
10+ 0x92, 0xb6, 0x9f, 0x3d, 0xfb, 0x20, 0x09, 0xd6,
11+ 0x6d, 0x3b, 0x8e, 0x43, 0xc7, 0xdc, 0x33, 0xe3,
12+ 0xbb, 0x6f, 0x07, 0x6c, 0xb5, 0xc8, 0xb4, 0x1f,
13+ 0x12, 0xe5, 0x6c, 0xe3, 0x0c, 0x64, 0xd7, 0xd9,
14+ 0xab, 0x0d, 0xa7, 0xf5, 0x81, 0xf1, 0x03, 0x79
15+ };
16+
17+ secp256k1_scalar_chacha20(&r1, &r2, input4, 0x6ff8602a7a78e2f2ULL);
18+ secp256k1_scalar_set_b32(&exp_r1, &expected4[0], NULL);
19+ secp256k1_scalar_set_b32(&exp_r2, &expected4[32], NULL);
20+ CHECK(secp256k1_scalar_eq(&exp_r1, &r1));
21+ CHECK(secp256k1_scalar_eq(&exp_r2, &r2));
788+ x12 += idx;
789+ x13 += idx >> 32;
790+ x14 += 0;
791+ x15 += over_count;
792+
793+ r1->d[7] = BE32(x0);
But we don’t care about the concrete PRG instantiation and other implementations can use whatever they like, right? Or do we want to standardize it (in the BIP)?
I’m just asking to be sure, I don’t think it’s necessary to standardize it. Advantages are 1) implementations can be (consensus-)consistent with each other, but that’s only relevant in cases that should happen with at most negligible probability, and 2) maybe people won’t get the idea to use their home-made PRG. The obvious disadvantage is less flexibility.
LE.
I think this entire discussion is the wrong one. Here we read uint32_ts into uint32_ts (8x32) or into uint64_ts (4x64) (and then of course most natural way is to do this is to copy the integers and not reverse the bytes). Endianness is not relevant here, so the LE32() macro is wrong here. I think this is the cause of the failure on s390x, which is 64-bit BE, so the LE32() call reverses the bytes there.
(Maybe I’m on the wrong track. I hate to think about byte order, and probably get it more often wrong than right. :D)
0@@ -0,0 +1,118 @@
1+#ifndef SECP256K1_SCHNORRSIG_H
2+#define SECP256K1_SCHNORRSIG_H
3+
4+/** This module implements a variant of Schnorr signatures compliant with
5+ * BIP-schnorr
6+ * (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki).
7+ */
8+
9+/** Opaque data structure that holds a parsed Schnorr signature.
As the Schnorr signature BIP defines the actual byte representation of signatures, there is no distinction between “invalid because incorrect values” and “invalid because incorrect serialization” (as is the case with ECDSA and DER encoding).
Because of that, there seems to not be any strict need for separately exposed parse/serialize functions. That is unless we expect operations besides sign/verify that operate on signatures, which one is expected to use without intervening serialization step. In that case we may opt to later change the representation inside to be a secp256k1_fe_storage and a secp256k1_scalar.
We cannot use secp256k1_fe_storage or secp256k1_scalar because the size of these objects is not exported, so it would prevent users building them on the stack.
Eliminating parse/serialize operations will prevent any future changes we might want to do that could use a more efficient format. On the other hand, I can’t imagine what future changes those might be.
Look at how secp256k1_pubkey_load works :)
And yes, I can’t imagine what those operations would be either. I’d like to make sure we’re not committing to an unnecessarily complex API without reason.
That is unless we expect operations besides sign/verify that operate on signatures, which one is expected to use without intervening serialization step.
There are definitely operations besides sign/verify that operate on signatures, for example verifying a sign-to-contract commitment as implemented here https://github.com/bitcoin-core/secp256k1/pull/572/files#diff-b19c5ee427283d4d82bc5beb4e2f4777R202
548+ 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFE,
549+ 0xBA, 0xAE, 0xDC, 0xE6, 0xAF, 0x48, 0xA0, 0x3B,
550+ 0xBF, 0xD2, 0x5E, 0x8C, 0xD0, 0x36, 0x41, 0x41
551+ };
552+ test_schnorrsig_bip_vectors_check_verify(scratch, pk13, msg13, sig13, 0);
553+ }
It would be beneficial to know what theses test vector are actually testing for, especially the negative ones.
I gather that: Test 6 check what happen when R.y is not a quadratic residue. Test 7 is test 3 with an invalid value for s ? Is that value somehow specific ? Test 8 is test 1 with negated s ? Test 9 is test 9 with a negated pubkey. Test 10 is test 2 with s such as s * G = e * P so R goes to infinity. Test 11 is test 2 with an invalid value for r. Test 12 is test 2 with r >= n. Test 13 is test 2 with s >= p.
While I can gather why most of them are doing, some of them still are unclear, and, in any case, I do not think it is beneficial that detective work is required to figure this out.
test_schnorrsig_bip_vectors). The BIP has an explanation for the test vectors at https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki#test-vectors-and-reference-code. It may be better to add a link to the BIP test vectors but I didn’t want to do that while it’s not merged into the BIP repo.
secp256k1_schnorrsig.h file doesn’t have “#ifdef __cplusplus extern { #endif” protections that make the header C++ compatible.
67+ * Returns 1 on success, 0 on failure.
68+ * Args: ctx: pointer to a context object, initialized for signing (cannot be NULL)
69+ * Out: sig: pointer to the returned signature (cannot be NULL)
70+ * nonce_is_negated: a pointer to an integer indicates if signing algorithm negated the
71+ * nonce (can be NULL)
72+ * In: msg32: the 32-byte message hash being signed (cannot be NULL)
This PR failed to build on s390x on Fedora Linux.
The patch was applied to commit a34bcaadf14442b86a5de120d4afd131f910d73d-
Log: https://kojipkgs.fedoraproject.org//work/tasks/7518/35017518/build.log Build task overview: https://koji.fedoraproject.org/koji/taskinfo?taskID=35017512
To save others from looking through it, the interesting lines are
0+ ./tests
1BUILDSTDERR: src/tests.c:1044: test condition failed: secp256k1_scalar_eq(&exp_r1, &r1)
2BUILDSTDERR: /var/tmp/rpm-tmp.SSskCl: line 31: 56834 Aborted (core dumped) ./tests
1039+ unsigned char seed0[32] = { 0 };
1040+
1041+ secp256k1_scalar_chacha20(&r1, &r2, seed0, 0);
1042+ secp256k1_scalar_set_b32(&exp_r1, &expected1[0], NULL);
1043+ secp256k1_scalar_set_b32(&exp_r2, &expected1[32], NULL);
1044+ CHECK(secp256k1_scalar_eq(&exp_r1, &r1));
@hegjon Do you happen to have the stdout too (instead of only the stderr)? It contains a random seed for the entire test run. Is the failure reproducible?
(Sorry for 3 comments in 5 min…)
@hegjon Do you happen to have the stdout too (instead of only the stderr)? It contains a random seed for the entire test run. Is the failure reproducible?
I can check and see if I am able to find them, I could also try to redirect stdout to stderr while debugging.
(Sorry for 3 comments in 5 min…)
No worries, thanks for replying
Is the failure reproducible?
Seems like it fails every time for s390x, will try to get the stdout
948@@ -946,4 +949,94 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
949 secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 6] >> ((shift - 1) & 0x3f)) & 1);
950 }
951
952+#define ROTL32(x,n) ((x) << (n) | (x) >> (32-(n)))
the result of this will be invalid if the integer type of x has a storage size larger than 32 bits.
for instance ROTL32((1UL << 31), 1) will not equal 1. It doesn’t look like it’s relevant for the current PR as it stands, but this is a common gotcha when using 64 bit literals.
suggest: ((uint32_t)(v) << (n)) | ((uint32_t)(v) >> (32 - (n)))
719@@ -718,4 +720,102 @@ SECP256K1_INLINE static void secp256k1_scalar_mul_shift_var(secp256k1_scalar *r,
720 secp256k1_scalar_cadd_bit(r, 0, (l[(shift - 1) >> 5] >> ((shift - 1) & 0x1f)) & 1);
721 }
722
723+#define ROTL32(x,n) ((x) << (n) | (x) >> (32-(n)))
LE32 macro from the integer assignments makes the tests on my big endian machine pass. I’ll add a commit to fix that later.
LE32 macro when doing the final chacha20 assignments. This didn’t appear in the little endian tests because LE32 is a noop there. I only ran the tests with 32 bit scalars on the big endian machine, because using 64 bit scalars is prohibited by __int128 support not being available.
It builds+all tests passes on all arches for Fedora with the latest changes.
I also added these configure flags:
0--enable-experimental --enable-module-schnorrsig
are they required?
78+ const secp256k1_context* ctx,
79+ secp256k1_schnorrsig *sig,
80+ int *nonce_is_negated,
81+ const unsigned char *msg32,
82+ const unsigned char *seckey,
83+ secp256k1_nonce_function noncefp,
Using @sipa logic from above
As the Schnorr signature BIP defines the actual byte representation of signatures, there is no distinction between “invalid because incorrect values” and “invalid because incorrect serialization”
Shouldn’t the deterministic derivation that’s described in BIP Schnorr be part of the function itself? (I guess if you see someone using this directly for Musig or something like that he will want to provide a different source of randomness)
ecdsa_sign. In almost all the cases users will provide NULL. I don’t know a specific case where you would want to provide your own nonce function (outside of testing).
65+/** Create a Schnorr signature.
66+ *
67+ * Returns 1 on success, 0 on failure.
68+ * Args: ctx: pointer to a context object, initialized for signing (cannot be NULL)
69+ * Out: sig: pointer to the returned signature (cannot be NULL)
70+ * nonce_is_negated: a pointer to an integer indicates if signing algorithm negated the
nonce_is_negated as part of the full opening which is better.
731+#define LE32(p) ((((p) & 0xFF) << 24) | (((p) & 0xFF00) << 8) | (((p) & 0xFF0000) >> 8) | (((p) & 0xFF000000) >> 24))
732+#else
733+#define LE32(p) (p)
734+#endif
735+
736+static void secp256k1_scalar_chacha20(secp256k1_scalar *r1, secp256k1_scalar *r2, const unsigned char *seed, uint64_t idx) {
A thought about multiple implementations of the same cryptography. is this library becoming a general cryptography library? should there be a different general crypto library with sha2/chacha20 etc.?
Because right now both libsecp and bitcoin implements SHA256 and HMAC, and after this they’ll also both implement Chacha20 (https://github.com/bitcoin/bitcoin/blob/master/src/crypto/chacha20.cpp)
Any ideas on the matter? (I myself don’t like duplicate implementations especially of sensitive cryptography(and there’s also a performance difference too))
libsecp256k1 is absolutely not a generic low-level cryptographc primitives library; it’s a library implementing high-level cryptographic algorithms efficiently with a safe-to-use interface.
As far as duplicate implementations goes, these are included for necessity of exposing fully-functional versions of the high-level functions it implements. I personally don’t think code duplication for such low-level primitives is an issue, as this code doesn’t “rot” (it won’t go out of date ever, at worst very rarely needs to be extended, and possibly doesn’t need to be touched ever, at all), so it isn’t subject to the same priorities most software engineering places.
That said, there are some practical reasons why having a built-in implementation may be undesirable:
Because of that reason, I think we should see the internal primitives as default, naive, private implementations, and if there is ever a reason to use another one, we should add functionality to make libsecp256k1 use external versions (rather than exposing/improving the internal ones).
Yeah, I didn’t consider the first option a real one, just a possibility about how will the library look with more primitives being added.
I guess your answer is fair, optimized sha256 might already be a nice speedup in a rapid verification scenario(which is already considered in the whole batch verification).
Maybe making a general low level library that is shared between libsecp and bitcoin is an option? Otherwise your suggestion that if someone really wanted then it’s possible to add a feature to support these functions as extern.
73+ secp256k1_ge_set_gej(&r, &rj);
74+
75+ if (nonce_is_negated != NULL) {
76+ *nonce_is_negated = 0;
77+ }
78+ if (!secp256k1_fe_is_quad_var(&r.y)) {
Is this constant time? As far as I could tell this uses https://github.com/bitcoin-core/secp256k1/blob/master/src/num_gmp_impl.h#L147
Which uses GMP. Am I missing something?
It isn’t (all functions ending with _var are variable time).
This isn’t a problem, as R (including its original Y coordinate) is not secret.
Constant time, constant memory access signing and pubkey generation.
Thanks!
The whole “constant time” naming is confusing really, as we can’t actually guarantee actual constant time (e.g. the div x86 instruction is variable time!).
Really what we’re aiming for is sidechannel resistance, and one of the criteria is that no execution branches are memory access locations are dependent on secret data.
Removed nonce_is_negated out argument from schnorrsig_sign because it was only required for a follow-up sign-to-contract PR that I closed in favor of a different sign-to-contract PR which does not use a nonce_is_negated argument but instead adds s2c_opening and s2c_data arguments (PR #589).
Also squashed in order to allow to cleanly build the sign-to-contract PR on top.
59+ }
60+
61+ secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &pkj, &x);
62+ secp256k1_ge_set_gej(&pk, &pkj);
63+
64+ if (!noncefp(buf, msg32, seckey, NULL, (void*)ndata, 0)) {
secp256k1_nonce_function the algo16 parameter should be written to and non null for schemes besides ECDSA - should the NULL be replaced with an algorithm identifier?
@jonasnick reason for the request - https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L90 According to here, NULL is passed for ecdsa, others need a 16byte identifier for the signing algorithm. I maintain language bindings to libsecp256k1, and have an implementation of a secp256k1_nonce_function to allow callers to use their own noncefp. The algo16 is currently the same for ecdsa and schnorr (null) so I can’t run this branch in tests: https://github.com/Bit-Wasp/secp256k1-php/blob/ea94d1daba2dcf07a575d294ce2159e73a15d2cc/secp256k1/secp256k1.c#L55
If there are any hard coded signature fixtures in tests, they’ll likely need tweaking as the bipschnorr noncefp also commits to the algo16: https://github.com/bitcoin-core/secp256k1/pull/558/files#diff-0d77700fa6e05639431c962ffaa5365aR429
Thanks @afk11 , good catch! The simplest fix ist to change nonce_function_bipschnorr to write nothing additional into the hash if algo16 is “bip-schnorr sign “, 0 if NULL, and 16 bytes of algo16 otherwise. @sipa We could easily remove the noncefp parameter from normal schnorrsig signing but then we need to provide another a more specific schnorrsig_sign function that allows providing your nonce function.There are already experimental applications of this where the nonce function returns a static nonce. For example, this is part of the discreet log contracts idea where only one outcome is supposed to be signed and otherwise the secret key leaks.
Perhaps ideally we should use a tagged hash anyway in bip-schnorr nonce derivation. So in the libsecp bip-schnorr nonce function the tag is either according to bip-schnorr if algo16 is “bip-schnorr sign " otherwise it’s empty and algo16 is written somewhere into the hash.
EDIT: opened PR for tagged hash in bip-schnorr (https://github.com/sipa/bips/pull/61)
I pushed new commits that do the following:
secp256k1_schnorrsig_pubkey which is same as the normal pubkey except its y coordinate is always a quadratic residue. Also added creation function, as well as serialization and parsing according to bip-schnorr.algo16 argument that @afk11 discoveredbipschnorr_nonce_function as it’s exposed via secp.h but different values would not result in different nonces (no one compiles with -DVERIFY) which could result in nonce reuse.Now I’ll add functions to commit to, verify and sign for a taproot commitments.
* Introduce new `secp256k1_schnorrsig_pubkey` which is same as the normal pubkey except its y coordinate is always a quadratic residue.
I wonder if secp256k1_32byte_pubkey or similar is better name for the future. Not sure.
I changed the schnorrsig_pubkey commits to rename the pubkey struct to positive_pubkey (alternative names runners-up: “xonly”, “short”). Also, positive_pubkey related code was moved from the schnorrsig module into the main code. In principle it could be its own module, but if we expect more modules to use positive_pubkeys then I think not doing that is the easiest way.
I added a new commit that introduces positive_privkey_tweak_add, positive_pubkey_tweak_add, positive_pubkey_tweak_verify, positive_pubkey_from_signed and positive_pubkey_to_signed in order to support bip-taproot operations. See https://github.com/bitcoin-core/secp256k1/pull/558/commits/59d10284ec18c74755d486cce6af55e46e25fbae#diff-4ad2dd2b8b6840915f8f0e99d18e1dc8R721 for an example of how to use these functions.
It’s not particularly elegant to have all this conversion between positive and “signed” pubkeys but I didn’t really find a way around it. One possible optimization of the API would be to have privkey_tweak_add take the corresponding pubkey as an argument which would avoid having to compute it.
quad_pubkey or something like that?
Why positive?
So far it’s the best option I’ve heard (h/t to @sipa). quad_pubkey is possible, but sounds overly technical and is not particularly precise (what’s a quadratic pubkey?). Defining positive points as points where the Y coordinate has a quadratic residue makes it easy to talk about them. Look at how often we say “point with a Y coordinate that is a quadratic residue” in BIP-schnorr/taproot, which is irritating. The definition makes it easy to partition points into positive and negative and in that context we can use “signed” for the existing pubkey type where we don’t care. Additionally, it’s similar to the real numbers where positive numbers have a square root and negative numbers don’t.
I guess “positive” may be confusing, and the opposite “signed” is probably even more confusing.
I’m also ok with “x-only”. Arguably, “positive” (if anything) is a property of the point, while having a Y coordinate at all is a property of the type of public key.
is_y_quad bit which is simply called sign in this PR. is_y_quad also comes up in bip-taproot and would be much nicer if it could also be called sign.
So what about this:
What do you think?
positive to xonly, removed signed_pks and kept the sign bit. Also rebased on master to remove travis.yml conflict.
So what about this:
* We introduce the term "positive" and "negative" as properties of EC points. Positive means Y is a quadratic residue; negative means Y is a quadratic nonresidue. * Then we defined x-only public keys as 32 bytes (in addition to compressed public keys of 33 bytes and uncompressed public keys of 65 bytes), which implicitly correspond to the positive point with the given X coordinateWhat do you think?
This sounds great.
844+
845+ *output_pubkey = *(secp256k1_pubkey *)internal_pubkey;
846+ return secp256k1_ec_pubkey_tweak_add(ctx, output_pubkey, tweak32);
847+}
848+
849+int secp256k1_xonly_pubkey_tweak_verify(const secp256k1_context* ctx, const secp256k1_pubkey *output_pubkey, const secp256k1_xonly_pubkey *internal_pubkey, const unsigned char *tweak32) {
Before the caller can do exactly the same thing they apparently would need to figure out how to compare pubkeys. On the other hand the taproot branch doesn’t use it because it doesn’t have to parse the serialized output pubkey in the first place and therefore compare the serialized versions.
Comparing via memcmp should be fine as the field elements are normalized when converting from group elements and parsing and it’s used in tests all over the codebase. But this is not documented or immediately obvious and therefore not ideal. Perhaps it’s time to finally add a group element comparison function.
FYI it’s documented that you should serialize secp256k1_pubkey before comparing https://github.com/bitcoin-core/secp256k1/blob/master/include/secp256k1.h#L64
EDIT: Not really related to what you’re doing, just a comment on Comparing via memcmp should be fine. internally it’s obviously fine
722+ * comparison, use secp256k1_xonly_pubkey_serialize and
723+ * secp256k1_xonly_pubkey_parse.
724+ */
725+typedef struct {
726+ unsigned char data[64];
727+} secp256k1_xonly_pubkey;
typedef up closer to the top of the file with all the other structures that are typedefed?
126+ secp256k1_ge pkp;
127+ secp256k1_gej pkj;
128+
129+ secp256k1_scalar_negate(&nege, e);
130+
131+ if (!secp256k1_pubkey_load(ctx, &pkp, (secp256k1_pubkey *) pk)) {
(const secp256k1_pubkey *) pk to avoid discarding the const qualifier.
(const secp256k1_pubkey *) pk to avoid discarding the const qualifier.
783+ size_t outputlen = sizeof(buf);
784+ VERIFY_CHECK(ctx != NULL);
785+ ARG_CHECK(pubkey != NULL);
786+ ARG_CHECK(output32 != NULL);
787+
788+ if (!secp256k1_ec_pubkey_serialize(ctx, buf, &outputlen, (secp256k1_pubkey *) pubkey, SECP256K1_EC_COMPRESSED)) {
(const secp256k1_pubkey *) pubkey to avoid casting away the const qualifier.
522@@ -523,6 +523,13 @@ SECP256K1_API int secp256k1_ecdsa_signature_normalize(
523 */
524 SECP256K1_API extern const secp256k1_nonce_function secp256k1_nonce_function_rfc6979;
525
526+/** An implementation of the nonce generation function as defined in BIP-schnorr.
It may be worth pointing out here that it’s safe to use this function for ECDSA as well (and perhaps document what tag is used in that case).
Alternatively, the function could just only support schnorr, and fail in any other context.
ecdsa_sign not providing an algo16 parameter. But what do you mean by tag?
The algo16 parameter isn’t observable to users of this function, so it doesn’t need to be mentioned.
For the current implementation however, I think you need to document:
And written like that, I think that’s a weird choice for the tag, as the fact that ecdsa_sign happens to pass an empty algo16 is an implementation detail that perhaps shouldn’t leak into the protocol used - but this is bikeshedding.
707@@ -701,6 +708,188 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ec_pubkey_combine(
708 size_t n
709 ) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
710
711+/** Opaque data structure that holds a parsed and valid "x-only" public key.
712+ * An x-only pubkey encodes a positive point. That is a point whose Y
713+ * coordinate is a quadratic residue. It is serialized using only its X
707@@ -701,6 +708,188 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ec_pubkey_combine(
708 size_t n
709 ) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
710
711+/** Opaque data structure that holds a parsed and valid "x-only" public key.
712+ * An x-only pubkey encodes a positive point. That is a point whose Y
713+ * coordinate is a quadratic residue. It is serialized using only its X
714+ * coordinate (32 bytes). A secp256k1_xonly_pubkey is also a secp256k1_pubkey
This could be misinterpreted as meaning you can cast a pointer from one to another (which is currently true, but not behavior we should commit to).
Is it really needed to have support for converting xonly_pubkeys to pubkeys? With a few changes (see below), I think it would be easier to describe the behavior simply as “pubkeys can be converted to xonly_pubkeys, using function xonly_pubkey_from_pubkey and will remain consistent with their private keys when doing so.” I may be overlooking something, though.
This could be misinterpreted as meaning you can cast a pointer from one to another (which is currently true, but not behavior we should commit to).
Yeah, we do that internally, but shouldn’t encourage users to do the same.
Is it really needed to have support for converting xonly_pubkeys to pubkeys? With a few changes (see below) […]
I think with the few changes it may still make sense to have the conversion. A user may only have an xonly pubkey but wants to use an existing function. But I have no specific use case in mind. We could add this later if necessary.
759+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
760+
761+/** Compute the xonly public key for a secret key. Just as ec_pubkey_create this
762+ * function computes the point P by multiplying the seckey (interpreted as a scalar)
763+ * with the generator. The public key corresponds to P if the Y coordinate of P is a
764+ * quadratic residue or -P otherwise.
786+ * 0 otherwise
787+ *
788+ * Args: ctx: pointer to a context object
789+ * Out: xonly_pubkey: pointer to an x-only public key object for placing the
790+ * converted public key (cannot be NULL)
791+ * sign: sign bit of the pubkey. Can be used to reconstruct a
“sign” is probably confusing when talking about signatures.
Also, is this needed? Ideally the conversion from pubkey to xonly_pubkey was one-way.
is_positive.
860+ * Out: output_pubkey: pointer to a public key object (cannot be NULL)
861+ * In: internal_pubkey: pointer to an x-only public key object to apply the
862+ * tweak to (cannot be NULL)
863+ * tweak32: pointer to a 32-byte tweak (cannot be NULL)
864+ */
865+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_add(
I think this function should input an xonly_pubkey, and output an xonly_pubkey plus a negation/sign/square/negative/… bit, which is sufficient for verifying it efficiently.
@real-or-random suggests seeing it as a commitment scheme and having a function that takes as input xonly_pubkey + message (+ tag?), and outputs an xonly_pubkey (the commitment) and a boolean (the opening). And then a verify function that takes the commitment, point, message, opening and returns true or false. The downside would be that the hashing needs to happen inside libsecp256k1, where it’s harder to take advantage of efficient hashing functions.
I think the best approach right now is having tweak_add/tweak_add_verify functions working on xonly_pubkeys/bools, and then seeing if we can e.g. make the caller pass in a SHA256 implementation etc. At that point we could start thinking about having more high-level operations like taproot_commitment/verify and bip32_derive etc instead of the rather low-level “tweak” style functions.
I’m in favor of high level operations which is why my other open pull requests have similar commitment APIs to what real-or-random suggests. For this PR I had a different mindset, because when I brought up high level functions you mentioned “ec_pubkey_tweak is perfect” which was a misunderstanding apparently.
Having tweak_add/tweak_add_verify functions working on xonly_pubkeys/bools is what I started out with, but then decided against that because 1) the output of tweak_add is a secp_pubkey, so returning a pubkey is a better separation of layers, 2) the user otherwise has to deal with two pieces of data of data 3) musig_pubkey_combine takes a tweak as well, and would either have to get an additional out argument with the sign or would work differently than tweak_add and return a pubkey.
However, if we want to add a high level API anyway, I’m happy with changing this again to the more hacky version if it’s more straightforward to use in your taproot implementation.
881+ * In: output_pubkey: pointer to a public key object (cannot be NULL)
882+ * internal_pubkey: pointer to an x-only public key object to apply the
883+ * tweak to (cannot be NULL)
884+ * tweak32: pointer to a 32-byte tweak (cannot be NULL)
885+ */
886+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_verify(
pubkey. What about instead having it take an input and output xonly_pubkey and a boolean?
82+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4);
83+
84+/** Verify a Schnorr signature.
85+ *
86+ * Returns: 1: correct signature
87+ * 0: incorrect or unparseable signature
101+ *
102+ * Returns 1 if all succeeded, 0 otherwise. In particular, returns 1 if n_sigs is 0.
103+ *
104+ * Args: ctx: a secp256k1 context object, initialized for verification.
105+ * scratch: scratch space used for the multiexponentiation
106+ * In: sig: array of signatures, or NULL if there are no signatures
105+ * scratch: scratch space used for the multiexponentiation
106+ * In: sig: array of signatures, or NULL if there are no signatures
107+ * msg32: array of messages, or NULL if there are no signatures
108+ * pk: array of x-only public keys, or NULL if there are no signatures
109+ * n_sigs: number of signatures in above arrays. Must be smaller than
110+ * 2^31 and smaller than half the maximum size_t value. Must be 0
162@@ -163,6 +163,20 @@ static void secp256k1_sha256_finalize(secp256k1_sha256 *hash, unsigned char *out
163 memcpy(out32, (const unsigned char*)out, 32);
164 }
165
166+/* Initializes a sha256 struct and writes the 64 byte string
167+ * SHA256(tag)||SHA256(tag) into it. The taglen should be less than or equal to
81+ if (!secp256k1_fe_is_quad_var(&pk.y)) {
82+ secp256k1_scalar_negate(&x, &x);
83+ }
84+
85+ if (!noncefp(buf, msg32, seckey, (unsigned char *) "BIPSchnorrDerive", (void*)ndata, 0)) {
86+ return 0;
85+ if (!noncefp(buf, msg32, seckey, (unsigned char *) "BIPSchnorrDerive", (void*)ndata, 0)) {
86+ return 0;
87+ }
88+ secp256k1_scalar_set_b32(&k, buf, NULL);
89+ if (secp256k1_scalar_is_zero(&k)) {
90+ return 0;
No wiping of sig here?
(“this can’t happen” is a good answer)
205+ * consecutive tuples before we need to call the RNG for new randomizers:
206+ * (-randomizer_cache[0], R1)
207+ * (-randomizer_cache[0]*e1, P1)
208+ * (-randomizer_cache[1], R2)
209+ * (-randomizer_cache[1]*e2, P2) */
210+ secp256k1_scalar_chacha20(&ecmult_context->randomizer_cache[0], &ecmult_context->randomizer_cache[1], ecmult_context->chacha_seed, idx / 4);
secp256k1_schnorrsig_verify_batch is spent in chacha during the schnorrsig batch benchmarks.
769+ ARG_CHECK(input32 != NULL);
770+
771+ buf[0] = SECP256K1_TAG_PUBKEY_EVEN;
772+ memcpy(&buf[1], input32, 32);
773+ if (!secp256k1_ec_pubkey_parse(ctx, (secp256k1_pubkey *) pubkey, buf, sizeof(buf))) {
774+ return 0;
As it stands, if secp256k1_xonly_pubkey_parse fails, it will leave the pubkey value in a invalid state. If the user of the this API were to ignore the return value of secp256k1_xonly_pubkey_parse and proceeded to call secp256k1_schnorrsig_verify, the verification could, perhaps, succeed.
However if we were to add a line such as memset(pubkey, 0, sizeof(secp256k1_xonly_pubkey); here, then pubkey would be initialized to a value that denotes a point with a zero x-coordinate. The current implementation of secp256k1_schnorrsig_verify calls secp256k1_pubkey_load which explicitly fails when passed a pubkey point with a zero x-coordinate, which in turn would cause secp256k1_schnorrsig_verify to unconditionally fail, even if the result of secp256k1_xonly_pubkey_parse were ignored. (Not only does secp256k1_pubkey_load unconditionally fail, but it also calls ctx->illegal_callback).
secp256k1_ec_pubkey_parse does that already:
https://github.com/bitcoin-core/secp256k1/blob/e541a90ef6461007d9c6a74b9f9a7fb8aa34aaa8/src/secp256k1.c#L256
Just a note:
The existing pubkey functions all have an ec_ pubkey prefix but the xonly_ do not.
We could add the ec_ there too, just for consistency. However, I think it would be better to remove the ec_ entirely but it’s too late for this now…. So I think just xonly_ is fine exactly because it does not have this annoying prefix.
The existing pubkey functions all have an ec_ pubkey prefix but the xonly_ do not.
Yes, this is on purpose and I agree that this is fine.
I added a few commits addressing the feedback to
pubkey to xonly_pubkey and is_positive bit (which reduces taproot test loc quite a bit).Also, there was a mismatch with the spec where we had fed the non-negated seckey into the nonce function (to be clear, not a security problem). I also updated test vectors.
I left the pubkey to xonly pubkey conversion. That’s right now the only efficient way to tweak a seckey and get a corresponding xonly pubkey (with is_positive to allow verification):
0secp256k1_xonly_privkey_tweak_add(ctx, sk, tweak);
1secp256k1_ec_pubkey_create(ctx, &xy_pk, sk);
2secp256k1_xonly_pubkey_from_pubkey(ctx, &output_pk, &is_positive, &xy_pk);
Alternatively we could offer an secp256k1_xonly_pubkey_create_tweaked that in addition to the secret key takes a tweak and returns tweaked seckey and pubkey.
HOST=i686-linux-gnu ENDOMORPHISM=yes). I’ve done a ./tests 100 iterations locally and wasn’t able to reproduce this so I’m guessing it’s just an accident. I opened #685 to improve reproducibility in the future.
Squashed the fixup commits and made a few more logical commits.
0Add xonly_pubkeys which are serialized as 32 byte and whose Y coordinate is a quadratic residue
1Add tweak functions for xonly_pubkeys that allow to add a tweak to a
2Add chacha20 function
3Add initialize_tagged to sha256 which initializes and writes the 64 byte string SHA256(tag)||SHA256(tag) into it.
4Add schnorrsig module which implements BIP-schnorr [0] compatible signing, verification and batch verification
5Add taproot test case to schnorrsig module
Also rebased on master to fix conflicts and get travis to work again. There were no code changes except two typo fixes.
865+ * has_square_y: 1 if output_pubkey has a square Y coordinate and 0 otherwise.
866+ * internal_pubkey: pointer to an x-only public key object to apply the
867+ * tweak to (cannot be NULL)
868+ * tweak32: pointer to a 32-byte tweak (cannot be NULL)
869+ */
870+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_verify(
I don’t know about this name, people might think it’s actually verifying some commitment which it is not.
the commitment is a valid one iff it is P + H(P||C)G. otherwise it’s a regular tweak add which there’s nothing to “verify” about.
right now that it’s only doing memcmp maybe it’s kinda useless and should be done in core? (I’d agree that if you use gej<->gej comparison than maybe the speed benefit is worth it but that’s not what happening here)
Though I see that I might be overthinking this.
right now that it’s only doing memcmp maybe it’s kinda useless and should be done in core?
Also comparing has_square_y. I think we should keep that function, but you’re right about the naming. I renamed it from verify to test and added a note in the doc.
I think we should definitely make use of avoiding the conversion to affine but not in this PR because there doesn’t seem to be a very concise way to do this.
40+ sha->s[4] = 0x814b9e66ul;
41+ sha->s[5] = 0x0469e801ul;
42+ sha->s[6] = 0x83909280ul;
43+ sha->s[7] = 0xb329e454ul;
44+ sha->bytes = 64;
45+}
Tested locally with the following logic:
0let mut hash = Sha256::new();
1hash.input(b"BIPSchnorr");
2let schnorr = hash.finalize();
3let mut hash = Sha256::new();
4hash.input(&schnorr);
5hash.input(&schnorr);
6hash.process_current_block();
7for i in &hash.hash {
8 println!("0x{:08x}", i);
9}
ACK on the resulting midstate
00x048d9a59
10xfe39fb05
20x28479648
30xe4a660f9
40x814b9e66
50x0469e801
60x83909280
70xb329e454
88+ memset(sig, 0, sizeof(*sig));
89+ memset(seckey_tmp, 0, sizeof(seckey_tmp));
90+ secp256k1_scalar_clear(&x);
91+ return 0;
92+ }
93+ memset(seckey_tmp, 0, sizeof(seckey_tmp));
if (secp256k1_scalar_is_zero(&k)) {
760+ ARG_CHECK(pubkey != NULL);
761+ ARG_CHECK(input32 != NULL);
762+
763+ buf[0] = SECP256K1_TAG_PUBKEY_EVEN;
764+ memcpy(&buf[1], input32, 32);
765+ if (!secp256k1_ec_pubkey_parse(ctx, (secp256k1_pubkey *) pubkey, buf, sizeof(buf))) {
Isn’t it better to use secp256k1_ge_set_xquad directly?
that way there’s no need to use secp256k1_ec_pubkey_absolute because it is already a square root. (right now there’s a bunch of redundant negations and conversations if the quad residue isn’t even)
and you could use the 32 byte buffer directly as your TODO says :)
773- secp256k1_ec_pubkey_absolute(ctx, (secp256k1_pubkey *) pubkey, NULL);
774+ if (!secp256k1_ge_set_xquad(&Q, &x)) {
775+ return 0;
776+ }
777+ secp256k1_pubkey_save((secp256k1_pubkey *) pubkey, &Q);
778+ secp256k1_ge_clear(&Q);
795+ if (!secp256k1_pubkey_load(ctx, &Q, (secp256k1_pubkey *) pubkey)) {
796 return 0;
797 }
798- memcpy(output32, &buf[1], 32);
799+ secp256k1_fe_normalize_var(&Q.x);
800+ secp256k1_fe_get_b32(output32, &Q.x);
835@@ -836,7 +836,7 @@ int secp256k1_xonly_pubkey_tweak_add(const secp256k1_context* ctx, secp256k1_xon
836 return secp256k1_xonly_pubkey_from_pubkey(ctx, output_pubkey, has_square_y, &pubkey_tmp);
837 }
838
839-int secp256k1_xonly_pubkey_tweak_verify(const secp256k1_context* ctx, const secp256k1_xonly_pubkey *output_pubkey, int has_square_y, const secp256k1_xonly_pubkey *internal_pubkey, const unsigned char *tweak32) {
840+int secp256k1_xonly_pubkey_tweak_test(const secp256k1_context* ctx, const secp256k1_xonly_pubkey *output_pubkey, int has_square_y, const secp256k1_xonly_pubkey *internal_pubkey, const unsigned char *tweak32) {
748+ secp256k1_xonly_pubkey* pubkey,
749+ const unsigned char *input32
750+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
751+
752+/** Serialize an xonly_pubkey object into a 32-byte sequence. Use the
753+ * SECP256K1_LEN_XONLY_PUBKEY macro if your want to avoid the magic number 32.
52@@ -53,6 +53,11 @@ static int secp256k1_ge_set_xquad(secp256k1_ge *r, const secp256k1_fe *x);
53 * for Y. Return value indicates whether the result is valid. */
54 static int secp256k1_ge_set_xo_var(secp256k1_ge *r, const secp256k1_fe *x, int odd);
55
56+/* Converts group element into its "absolute" value. That means it is kept as
57+ * is if it has a square Y and otherwise negated. has_square_y is set to 1 in
58+ * the former case and to 0 in the latter case. */
59+static void secp256k1_ge_absolute(secp256k1_ge *r, int *has_square_y);
had_square_y?
is_negated
4374+ CHECK(secp256k1_xonly_pubkey_parse(none, &pk, ones32) == 0);
4375+ CHECK(ecount == 2);
4376+ /* There's no point with x-coordinate 0 on secp256k1 */
4377+ CHECK(secp256k1_xonly_pubkey_parse(none, &pk, zeros32) == 0);
4378+ CHECK(ecount == 2);
4379+ CHECK(secp256k1_xonly_pubkey_parse(none, &pk, buf32) == 1);
ecount can only be changed through illegal or error callbacks which should always entail return value of 0.
4372+ memset(&pk_tmp, 0, sizeof(pk_tmp));
4373+ CHECK(secp256k1_xonly_pubkey_serialize(none, buf32, &pk_tmp) == 0);
4374+ }
4375+ /* pubkey_load called illegal callback */
4376+ CHECK(ecount == 3);
4377+ CHECK(secp256k1_xonly_pubkey_serialize(none, buf32, &pk) == 1);
851@@ -852,8 +852,11 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_add(
852 const unsigned char *tweak32
853 ) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
854
855-/** Verifies that output_pubkey and has_square_y is the result of calling
856- * secp256k1_xonly_pubkey_tweak_add with internal_pubkey and tweak32.
857+/** Tests that output_pubkey and has_square_y is the result of calling
858+ * secp256k1_xonly_pubkey_tweak_add with internal_pubkey and tweak32. Note
859+ * that this alone does _not_ verify anything cryptographically. If the tweak
I don’t know that “anything cryptographically” is. This sentence is hard to understand.
“Note that this does not verify that tweak32 is constructed in a specific way, e.g., as the hash of internal_pubkey and some message.” “Note that this does not verify that output_pubkey is a commitment to some message.”
222@@ -223,6 +223,10 @@ static int secp256k1_schnorrsig_verify_batch_ecmult_callback(secp256k1_scalar *s
223 secp256k1_sha256 sha;
224
225 if (!secp256k1_xonly_pubkey_load(ecmult_context->ctx, pt, ecmult_context->pk[idx / 2])) {
226+ /* Logically unreachable because verify_batch_init_randomizer calls
227+ * secp256k1_ec_pubkey_serialize which only works if loading the
228+ * pubkey into a group element succeeds.*/
229+ VERIFY_CHECK(0);
822@@ -822,9 +823,10 @@ int secp256k1_xonly_privkey_tweak_add(const secp256k1_context* ctx, unsigned cha
823 }
824 secp256k1_pubkey_load(ctx, &ge, &pubkey);
825 if (!secp256k1_fe_is_quad_var(&ge.y)) {
826- if (!secp256k1_ec_privkey_negate(ctx, seckey32)) {
827- return 0;
828- }
829+ secp256k1_scalar_set_b32(&sec, seckey32, NULL);
858@@ -859,9 +859,9 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_xonly_pubkey_tweak_add(
859
860 /** Tests that output_pubkey and is_negated is the result of calling
s/is the result/are the results well, maybe better say
“Tests whether a pair (output_pubkey, is_negated) is the result of calling” or similar. I think that’s more readable even though there are no actual pairs in C.
159+ }
160+
161 secp256k1_schnorrsig_sha256_tagged(&sha);
162 secp256k1_sha256_write(&sha, &sig->data[0], 32);
163- secp256k1_xonly_pubkey_serialize(ctx, buf, pk);
164+ secp256k1_fe_normalize_var(&pk.x);
226+ return 0;
227+ }
228 secp256k1_schnorrsig_sha256_tagged(&sha);
229 secp256k1_sha256_write(&sha, &ecmult_context->sig[idx / 2]->data[0], 32);
230- secp256k1_xonly_pubkey_serialize(ecmult_context->ctx, buf, ecmult_context->pk[idx / 2]);
231+ secp256k1_fe_normalize_var(&pt->x);
848+ const secp256k1_context* ctx,
849+ secp256k1_xonly_pubkey *output_pubkey,
850+ int *is_negated,
851+ const secp256k1_xonly_pubkey *internal_pubkey,
852+ const unsigned char *tweak32
853+) SECP256K1_ARG_NONNULL(1) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3) SECP256K1_ARG_NONNULL(4) SECP256K1_ARG_NONNULL(5);
How do people feel about promising that it’s fine for output_pubkey and internal_pubkey to point to the same object?
Right now it will work. but a lot of our APIs start by zeroing out the output object. and then this isn’t fine anymore.
On one hand it’s nice to not return uninitialized objects. on the other a lot of times you want to tweak the key in place.
Right now it will work. but a lot of our APIs start by zeroing out the output object. and then this isn’t fine anymore.
I don’t see why. secp256k1_ec_pubkey_tweak_add zeroes the key and is in place. Actually we should also zeroize the output key in this function.
Also, that xonly_pubkey_tweak_add does not work in place (and therefore differs from ec_pubkey_tweak_add) is just for historical reasons (initially output_pubkey was a different type than internal_pubkey, namely secp256k1_pubkey). How do people feel about changing the function to tweak the pubkey in-place? I think I prefer that because otherwise it’s inconsistent with pubkey_tweak_add.
tweak_add changes the pubkey in-place now. And added a test that the pubkey is zeroed on failure.
The reason for zeroizing the outputs is mostly so that if the caller doesn’t know errors need to be handled, that the output is invalid so that hopefully later error handling will do something useful. This is especially a concern because errors should never be seen without crafted inputs, and it’s plausible a caller simply won’t know they’re possible at all. This isn’t incompatible with in-place operation. (though not-in-place operation is arguably riskier to not zero because it might expose the content of random secrets if the caller ignores the error).
Zeroizing also makes programming errors more likely to get detected faster, e.g. if the function is called with an invalid output pointer but also an invalid input, if it zeroizes it’s more likely to cause a valgrind error and/or program crash rather than silently being broken.
531+ * When this function is used in ecdsa_sign, it generates a nonce using an
532+ * analogue of the bip-schnorr nonce generation algorithm, but with tag
533+ * "BIPSchnorrNULL" instead of "BIPSchnorrDerive".
534+ * The attempt argument must be 0 or the function will fail and return 0.
535+ */
536+SECP256K1_API extern const secp256k1_nonce_function secp256k1_nonce_function_bipschnorr;
0SECP256K1_API extern const secp256k1_nonce_function secp256k1_nonce_function_bip340;
67+ * Returns 1 on success, 0 on failure.
68+ * Args: ctx: pointer to a context object, initialized for signing (cannot be NULL)
69+ * Out: sig: pointer to the returned signature (cannot be NULL)
70+ * In: msg32: the 32-byte message being signed (cannot be NULL)
71+ * seckey: pointer to a 32-byte secret key (cannot be NULL)
72+ * noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bipschnorr is used
0 * noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_bip340 is used
62+ ARG_CHECK(sig != NULL);
63+ ARG_CHECK(msg32 != NULL);
64+ ARG_CHECK(seckey != NULL);
65+
66+ if (noncefp == NULL) {
67+ noncefp = secp256k1_nonce_function_bipschnorr;
0 noncefp = secp256k1_nonce_function_bip340;
412@@ -413,6 +413,54 @@ static SECP256K1_INLINE void buffer_append(unsigned char *buf, unsigned int *off
413 *offset += len;
414 }
415
416+/* Initializes SHA256 with fixed midstate. This midstate was computed by applying
417+ * SHA256 to SHA256("BIPSchnorrDerive")||SHA256("BIPSchnorrDerive"). */
418+static void secp256k1_nonce_function_bipschnorr_sha256_tagged(secp256k1_sha256 *sha) {
0static void secp256k1_nonce_function_bip340_sha256_tagged(secp256k1_sha256 *sha) {
428+ sha->bytes = 64;
429+}
430+
431+/* This nonce function is described in BIP-schnorr
432+ * (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki) */
433+static int nonce_function_bipschnorr(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
0static int nonce_function_bip340(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {
439+ /* Tag the hash with algo16 which is important to avoid nonce reuse across
440+ * algorithms. If the this nonce function is used in BIP-schnorr signing as
441+ * defined in the spec, an optimized tagging implementation is used. */
442+ if (algo16 != NULL) {
443+ if (memcmp(algo16, "BIPSchnorrDerive", 16) == 0) {
444+ secp256k1_nonce_function_bipschnorr_sha256_tagged(&sha);
0 secp256k1_nonce_function_bip340_sha256_tagged(&sha);
490@@ -443,6 +491,7 @@ static int nonce_function_rfc6979(unsigned char *nonce32, const unsigned char *m
491 return 1;
492 }
493
494+const secp256k1_nonce_function secp256k1_nonce_function_bipschnorr = nonce_function_bipschnorr;
0const secp256k1_nonce_function secp256k1_nonce_function_bip340 = nonce_function_bip340;
712@@ -701,6 +713,170 @@ SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ec_pubkey_combine(
713 size_t n
714 ) SECP256K1_ARG_NONNULL(2) SECP256K1_ARG_NONNULL(3);
715
716+/** Opaque data structure that holds a parsed and valid "x-only" public key.
717+ * An x-only pubkey encodes a point whose Y coordinate is square. It is
718+ * serialized using only its X coordinate (32 bytes). See bip-schnorr for more
0 * serialized using only its X coordinate (32 bytes). See BIP-340 for more
6+#ifdef __cplusplus
7+extern "C" {
8+#endif
9+
10+/** This module implements a variant of Schnorr signatures compliant with
11+ * BIP-schnorr
0 * BIP-340
7+extern "C" {
8+#endif
9+
10+/** This module implements a variant of Schnorr signatures compliant with
11+ * BIP-schnorr
12+ * (https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki).
0 * (https://github.com/bitcoin/bips/blob/master/bip-0340.mediawiki).
This link is broken until the PR is merged.
28+ memcpy(sig->data, in64, 64);
29+ return 1;
30+}
31+
32+/* Initializes SHA256 with fixed midstate. This midstate was computed by applying
33+ * SHA256 to SHA256("BIPSchnorr")||SHA256("BIPSchnorr"). */
BIP340, so I will not suggest the edit, but please confirm that BIPSchnorr is the proper way.