test: refactor: negate signature-s using libsecp256k1 #32436

theStack commented at 10:44 AM on May 7, 2025: contributor

This small PR gets rid of manual mod-n inversion of the ECDSA signature-s part in unit tests (introduced a long time ago in #5256, triggered by https://github.com/bitcoin-core/secp256k1/pull/69) by using secp256k1 instead. The function wasn't available at that time, but was introduced about three years later, see https://github.com/bitcoin-core/secp256k1/pull/408. Note that as the name suggests, secp256k1_ec_seckey_negate is meant to be used for secret keys, but it obviously works in general for scalars modulo the group order.

DrahtBot commented at 10:44 AM on May 7, 2025: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Code Coverage & Benchmarks

For details see: https://corecheck.dev/bitcoin/bitcoin/pulls/32436.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	laanwj, w0xlt, rkrux, achow101

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

DrahtBot added the label Tests on May 7, 2025

w0xlt commented at 6:05 PM on May 7, 2025: contributor

ACK https://github.com/bitcoin/bitcoin/pull/32436/commits/bfb7b8876035774eddb200d741aa6a86859069b3

in src/test/script_tests.cpp:152 in bfb7b88760 outdated

 161 | -        int n = (int)order[p] - s[p] - carry;
 162 | -        s[p] = (n + 256) & 0xFF;
 163 | -        carry = (n < 0);
 164 | -    }
 165 | -    assert(carry == 0);
 166 | +    // Perform mod-n negation of s by (ab)using libsecp256k1

rkrux commented at 12:48 PM on May 8, 2025:

Note that as the name suggests, secp256k1_ec_seckey_negate is meant to be used for secret keys, but it obviously works in general for scalars modulo the group order.

I can see a call to secp256k1_scalar_negate inside secp256k1_ec_seckey_negate.

https://github.com/bitcoin/bitcoin/blob/64697529523705f5a411ca893060429afcd5cd47/src/secp256k1/src/secp256k1.c#L622-L635

Nit: However, the current comment makes one wonder why it is (ab)using libsecp256k1, which is answered in the commit message - might as well add the reasoning in the comment here itself to get rid of any doubt in the future.

theStack commented at 2:22 PM on May 8, 2025:

Added a comment.

in src/test/script_tests.cpp:155 in bfb7b88760 outdated

 162 | -        s[p] = (n + 256) & 0xFF;
 163 | -        carry = (n < 0);
 164 | -    }
 165 | -    assert(carry == 0);
 166 | +    // Perform mod-n negation of s by (ab)using libsecp256k1
 167 | +    int ret = secp256k1_ec_seckey_negate(secp256k1_context_static, s.data() + 1);

rkrux commented at 12:57 PM on May 8, 2025:

I can see the earlier implementation also ended the iteration at second index (1), which is ok.

However, the + 1 is quite apparent now & I'm not entirely sure why this is the case. It would be helpful to know the reason and document it in code if possible.

laanwj commented at 1:32 PM on May 8, 2025:

The reason is that the first byte cannot have the upper bit set, as this would mean a negative number, which would be illegal here. So the number can be 33 bytes long (with a 0x00 prefixed) even though it fits in 32 bytes.

Always padding to 33 bytes then applying it to data()+1 is just a convenience, i do suggest to assert(s[0] == 0) to make it clearer that this a valid thing to do.

rkrux commented at 2:16 PM on May 8, 2025:

Interesting, thanks. I did read this code comment earlier but the above comment is helpful in connecting the dots. https://github.com/bitcoin/bitcoin/blob/66c968b4b4a98b1d476cb79b0dd2f6b09420c945/src/key.cpp#L201-L204

Always padding to 33 bytes then applying it to data()+1 is just a convenience

Re: Always padding - In the case the first bit is not set already, even then prepending with 00 makes it easier to grasp. Otherwise, s[0] == 0 in some cases, and < 0x80 in the other cases.

theStack commented at 2:37 PM on May 8, 2025:

As another reference and explanation, see also the corresponding serialization implementation in the functional test framework: https://github.com/bitcoin/bitcoin/blob/66c968b4b4a98b1d476cb79b0dd2f6b09420c945/test/functional/test_framework/key.py#L184-L188

laanwj commented at 1:16 PM on May 8, 2025: member

ACK i think this would make it slightly more clear what is going on with regard to ranges and validity:

diff --git a/src/test/script_tests.cpp b/src/test/script_tests.cpp
index 33a4555dd595c9e4886f194cb113b905a55bddb3..6f251b094c5b68373f30d1d578088e65d4595a09 100644
--- a/src/test/script_tests.cpp
+++ b/src/test/script_tests.cpp
@@ -148,11 +148,12 @@ void static NegateSignatureS(std::vector<unsigned char>& vchSig) {
     while (s.size() < 33) {
         s.insert(s.begin(), 0x00);
     }
+    assert(s[0] == 0);
     // Perform mod-n negation of s by (ab)using libsecp256k1
     int ret = secp256k1_ec_seckey_negate(secp256k1_context_static, s.data() + 1);
     assert(ret);

-    if (s.size() > 1 && s[0] == 0 && s[1] < 0x80) {
+    if (s[1] < 0x80) {
         s.erase(s.begin());
     }

(if s[0] doesn't start out as 0, secp256k1_ec_seckey_negate(..., s.data() + 1) isn't correct)

rkrux commented at 1:24 PM on May 8, 2025: contributor

Concept ACK bfb7b8876035774eddb200d741aa6a86859069b3

Conceptually, I'm in agreement with the replacement of custom negation code by using the one from secp256k1. Though I was a little surprised to note that git grep of this function doesn't lead to any actual usages of the function besides the tests & secp256k1_ec_privkey_negate function that too doesn't seem to be used elsewhere.

git grep -n "secp256k1_ec_seckey_negate"

src/secp256k1/include/secp256k1.h:699:SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_ec_seckey_negate(
src/secp256k1/include/secp256k1.h:704:/** Same as secp256k1_ec_seckey_negate, but DEPRECATED. Will be removed in
src/secp256k1/include/secp256k1.h:710:  SECP256K1_DEPRECATED("Use secp256k1_ec_seckey_negate instead");
src/secp256k1/src/ctime_tests.c:142:    ret = secp256k1_ec_seckey_negate(ctx, key);
src/secp256k1/src/secp256k1.c:622:int secp256k1_ec_seckey_negate(const secp256k1_context* ctx, unsigned char *seckey) {
src/secp256k1/src/secp256k1.c:638:    return secp256k1_ec_seckey_negate(ctx, seckey);
src/secp256k1/src/tests.c:6246:    CHECK(secp256k1_ec_seckey_negate(CTX, seckey) == 1);
src/secp256k1/src/tests.c:6248:    CHECK(secp256k1_ec_seckey_negate(CTX, seckey) == 1);
src/secp256k1/src/tests.c:6252:    CHECK(secp256k1_ec_seckey_negate(CTX, seckey) == 1);
src/secp256k1/src/tests.c:6259:    CHECK(secp256k1_ec_seckey_negate(CTX, seckey) == 0);
src/secp256k1/src/tests.c:6269:    CHECK(secp256k1_ec_seckey_negate(CTX, seckey) == 0);

test: refactor: negate signature-s using libsecp256k1

Co-authored-by: laanwj <126646+laanwj@users.noreply.github.com>

1ee698fde2

theStack force-pushed on May 8, 2025

theStack commented at 2:38 PM on May 8, 2025: contributor

Thanks for the reviews! Applied your patch @laanwj and added a comment about the secp256k1 negation function usage.

Conceptually, I'm in agreement with the replacement of custom negation code by using the one from secp256k1. Though I was a little surprised to note that git grep of this function doesn't lead to any actual usages of the function besides the tests & secp256k1_ec_privkey_negate function that too doesn't seem to be used elsewhere.

It would have been used for the BIP 151 (v2 transport protocol) implementation and there was a CKey::Negate wrapper for it once, but with the replacement BIP 324 that was not needed any more and hence it got removed again, see #14047 and #30218. secp256k1_ec_privkey_negate is just the older now deprecated name for the same function, which gets removed with the upcoming secp256k1 release, see https://github.com/bitcoin-core/secp256k1/pull/1593.

laanwj approved

laanwj commented at 3:01 PM on May 8, 2025: member

Code review ACK 1ee698fde2e8652d8eb083749edb8029c003b8db

DrahtBot requested review from w0xlt on May 8, 2025

DrahtBot requested review from rkrux on May 8, 2025

w0xlt commented at 9:40 PM on May 8, 2025: contributor

ACK https://github.com/bitcoin/bitcoin/pull/32436/commits/1ee698fde2e8652d8eb083749edb8029c003b8db

in src/test/script_tests.cpp:158 in 1ee698fde2

 169 | +    // (note that this function is meant to be used for negating secret keys,
 170 | +    //  but it works for any non-zero scalar modulo the group order, i.e. also for s)
 171 | +    int ret = secp256k1_ec_seckey_negate(secp256k1_context_static, s.data() + 1);
 172 | +    assert(ret);
 173 | +
 174 | +    if (s[1] < 0x80) {

rkrux commented at 10:51 AM on May 9, 2025:

Given that s[0] == 0 is asserted above and the signature is negated from s[1] onwards, I was trying to reason why this check is still needed before dropping s[0] & thought of the reason that if s[0] is dropped when s[1] >= 0x80 then s will be treated as a negative number, which is illegal as mentioned in #32436 (review).

laanwj commented at 11:12 AM on May 9, 2025:

Right.

It'd be possible to structure this slightly more intuitive, by first removing the first byte (after asserting it's 0x00), then doing secp256_blabla on the entire 32-byte thing, then conditionally readding it after.

But meh. It's not like this is a easty-to-digest function in the first place 😓

in src/test/script_tests.cpp:156 in 1ee698fde2

 167 | +    assert(s[0] == 0);
 168 | +    // Perform mod-n negation of s by (ab)using libsecp256k1
 169 | +    // (note that this function is meant to be used for negating secret keys,
 170 | +    //  but it works for any non-zero scalar modulo the group order, i.e. also for s)
 171 | +    int ret = secp256k1_ec_seckey_negate(secp256k1_context_static, s.data() + 1);
 172 | +    assert(ret);

rkrux commented at 11:04 AM on May 9, 2025:

I checked that ret here means whether the passed signature/seckey in the second argument is valid according to secp256k1_ec_seckey_verify, which weirdly enough doesn't seem to be called by secp256k1_ec_seckey_negate - maybe the doc is outdated, but I get the general idea of validating the input & returning the response of this check.

https://github.com/bitcoin/bitcoin/blob/5b8752198e979ea4987d8b6238f42f8ed9a38846/src/secp256k1/include/secp256k1.h#L689-L702

https://github.com/bitcoin/bitcoin/blob/5b8752198e979ea4987d8b6238f42f8ed9a38846/src/secp256k1/src/secp256k1.c#L622-L635

rkrux approved

rkrux commented at 11:06 AM on May 9, 2025: contributor

tACK 1ee698fde2e8652d8eb083749edb8029c003b8db

achow101 commented at 8:13 PM on May 9, 2025: member

ACK 1ee698fde2e8652d8eb083749edb8029c003b8db

achow101 merged this on May 9, 2025

achow101 closed this on May 9, 2025

theStack deleted the branch on May 9, 2025

sipa commented at 8:30 PM on May 9, 2025: member

Posthumous Concept ACK