crypto: add `NUMS

josibake commented at 9:47 am on May 6, 2024: member

Broken out from #28122

BIP341 defines a NUMS point H as H = lift_x(0x50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0) which is constructed by taking the hash of the standard uncompressed encoding of the secp256k1 base point G as X coordinate."

Add this as a constant so it can be used in our codebase. My primary motivation is BIP352 specifies a special case for when taproot spends use H as the internal key, but outside of BIP352 it seems generally useful to have H in the codebase, for testing or other use cases.

DrahtBot commented at 9:47 am on May 6, 2024: contributor

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

Code Coverage

For detailed information about the code coverage, see the test coverage report.

Reviews

See the guideline for information on the review process.

Type	Reviewers
ACK	paplorinc, theStack, achow101
Concept ACK	ajtowns
Stale ACK	Sjors, S3RK

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#28201 (Silent Payments: sending by josibake)
#28122 (Silent Payments: Implement BIP352 by josibake)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

DrahtBot added the label Utils/log/libs on May 6, 2024

theStack commented at 12:08 pm on May 6, 2024: contributor

Concept ACK

Found via $ git grep 5092929b74 that we already define this byte-string constant twice for the miniscript fuzz and unit tests (src/test/fuzz/miniscript.cpp and src/test/miniscript_tests.cpp, called NUMS_PK there), that’s a good opportunity to deduplicate.

josibake commented at 1:12 pm on May 6, 2024: member

Found via $ git grep 5092929b74

Nice! Pushed a second commit to update the existing tests.

in src/pubkey.cpp:197 in 8931afc5ca outdated

180@@ -181,6 +181,9 @@ int ecdsa_signature_parse_der_lax(secp256k1_ecdsa_signature* sig, const unsigned
181     return 1;
182 }
183 
184+static const std::vector<unsigned char> NUMS_H_DATA = {0x50, 0x92, 0x9b, 0x74, 0xc1, 0xa0, 0x49, 0x54, 0xb7, 0x8b, 0x4b, 0x60, 0x35, 0xe9, 0x7a, 0x5e, 0x07, 0x8a, 0x5a, 0x0f, 0x28, 0xec, 0x96, 0xd5, 0x47, 0xbf, 0xee, 0x9a, 0xce, 0x80, 0x3a, 0xc0};

ajtowns commented at 11:39 pm on May 6, 2024:

Add a comment indicating where this comes from and why it’s believed no one knows the discrete log?

josibake commented at 7:43 am on May 7, 2024:

Added a comment for where the point comes from. Tried to write a sentence for the “why” but don’t really understand it well enough to articulate succinctly :sweat_smile:.

From what I understand, because H is derived from a known public value G via a hash, we learn nothing about the discrete log of H due to the hash function providing us a uniformly random value. But not sure if that’s entirely correct; if you have a suggestion on how to better (or more correctly!) phrase this, happy to add!

ajtowns commented at 8:23 am on May 7, 2024:

Oh, secp256k1-zkp has a straight forward description: https://github.com/BlockstreamResearch/secp256k1-zkp/blob/11af7015de624b010424273be3d91f117f172c82/src/modules/rangeproof/main_impl.h#L16

josibake commented at 9:08 am on May 7, 2024:

Perfect, will use this!

ajtowns commented at 11:41 pm on May 6, 2024: contributor

Concept ACK

josibake force-pushed on May 7, 2024

in src/pubkey.cpp:197 in a97dae38fa outdated

186+ * NUMS_H is a point with an unknown discrete logarithm, constructed by taking the hash of the
187+ * standard uncompressed encoding of the secp256k1 base point G as X coordinate.
188+ *
189+ * See https://github.com/bitcoin/bips/blob/master/bip-0341.mediawiki#constructing-and-spending-taproot-outputs
190+ */
191+static const std::vector<unsigned char> NUMS_H_DATA = {0x50, 0x92, 0x9b, 0x74, 0xc1, 0xa0, 0x49, 0x54, 0xb7, 0x8b, 0x4b, 0x60, 0x35, 0xe9, 0x7a, 0x5e, 0x07, 0x8a, 0x5a, 0x0f, 0x28, 0xec, 0x96, 0xd5, 0x47, 0xbf, 0xee, 0x9a, 0xce, 0x80, 0x3a, 0xc0};

maflcko commented at 7:51 am on May 7, 2024:

Any reason to drop the ParseHex, which allows to write this as a string literal?

josibake commented at 9:15 am on May 7, 2024:

Seemed unnecessary? Representing this as a byte vector allows us to create an XOnlyPublicKey directly without an extra function call. Is there a reason to prefer having this as a string literal?

maflcko commented at 9:24 am on May 7, 2024:

Just a style-nit, as it makes it easier to grep and compare the string literal. The function call could be moved to compile time, but I haven’t implemented it yet. Calling it once at runtime should be fine also, for now?

Just a nit in any case.

josibake commented at 9:57 am on May 7, 2024:

Ah cool, my slight aversion to ParseHex was the call at runtime for a static const, but if we are going to move that to compile time and the string literal makes it easier to compare (e.g. with the value in BIP341, which is also a string literal), then happy to change it.

josibake force-pushed on May 7, 2024

josibake commented at 10:04 am on May 7, 2024: member

Added a comment per @ajtowns ’s feedback and reverted to using ParseHex on a string literal per @maflcko ’s feedback.

in src/pubkey.cpp:196 in 64c1b06d30 outdated

191+
192+    import hashlib
193+    F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
194+    G_DER = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'
195+    G2 = EllipticCurve ([F (0), F (7)]).lift_x(F(int(hashlib.sha256(G_DER.decode('hex')).hexdigest(),16)))
196+    print('%x %x' % G2.xy())

theStack commented at 6:00 pm on May 7, 2024:

This code snippet doesn’t work for me on Sage 9.5 (see https://github.com/BlockstreamResearch/secp256k1-zkp/pull/292). Also, we only need to output the x-coordinate here:

0    G2 = EllipticCurve ([F (0), F (7)]).lift_x(F(int(hashlib.sha256(bytes.fromhex(G_DER)).hexdigest(),16)))
1    print('%x' % G2.xy()[0])

(That said, I think it’s also completely fine to not include any sage code here and instead just keep the first paragraph.)

josibake commented at 8:45 am on May 8, 2024:

Oops! Should have ran it myself before including it. I have a slight preference for keeping the sage code, since its nice to be able to run that snippet and get the same value as a way of verifying. That being said, “be able to run that snippet” implies keeping the comment up to date, but I doubt that will be much (if any) of a maintenance burden.

Also think its more correct to output the x,y coordinate pair since in the comment we are referring to NUMS_H as a point, whereas the x-only value is a byte encoding of a point. I did check that the y-coordinate printed out is even (i.e. int("31d3c6863973926e049e637cb1b5f40a36dac28af1766968c30c2313f3a38904", 16) % 2 == 0), so the x-only encoding is equivalent to the point printed out by the code.

josibake commented at 8:51 am on May 8, 2024:

Updated to fix the hex decoding. Went ahead and left the (x,y) print out, but can drop the y-value or drop the whole sage snippet if others feel strongly.

theStack commented at 9:30 am on May 8, 2024:

Agree that keeping the sage code and printing out the full point makes sense w.r.t. your point vs byte encoding argument. (By the way, at least in our test-framework implementation of GE, lift_x always produces a point with even y coordinate, but no idea if this is also the case in the GE of sage.)

josibake force-pushed on May 8, 2024

theStack approved

theStack commented at 9:31 am on May 8, 2024: contributor

Code-review ACK a5867a393cacbe4b2e0de51b842362754e98ab42

DrahtBot requested review from ajtowns on May 8, 2024

real-or-random referenced this in commit d661a93cc9 on May 8, 2024

in src/pubkey.h:303 in a5867a393c outdated

299@@ -300,6 +300,8 @@ class XOnlyPubKey
300     SERIALIZE_METHODS(XOnlyPubKey, obj) { READWRITE(obj.m_keydata); }
301 };
302 
303+extern const XOnlyPubKey NUMS_H;

ajtowns commented at 5:52 am on May 9, 2024:

nit: Would it be better to make this a static const member of the XOnlyPubKey class?

josibake commented at 7:02 am on May 9, 2024:

Can you elaborate? Not clear to me what the benefit would be.

ajtowns commented at 2:08 pm on May 9, 2024:

Mostly that NUMS_H is an XOnlyPubkey (rather than a CPubKey or the hex/bytes encoding of the point or something else), so maybe it would make sense to keep it tied to that class. Bit of a knee-jerk “does this really need to be in the global namespace” reaction.

josibake commented at 2:42 pm on May 9, 2024:

Ah, I see. In my head, there is nothing about H that requires it to be an XOnlyPubKey, but you’re right that we are setting it that way (and thats the only way its used in our codebase).

Seems fine to make it a member, altho needing to call something like XOnlyPubKey{XOnlyPubKey::NUMS_H} to use it seems kinda weird to me?

ajtowns commented at 3:13 pm on May 9, 2024:

You’d write builder.Finalize(XOnlyPubKey::NUMS_H); which seems fine?

josibake commented at 5:42 pm on May 9, 2024:

Oh! I see , I misinterpreted what you were suggesting. This does seem better, will update.

DrahtBot requested review from ajtowns on May 9, 2024

josibake force-pushed on May 9, 2024

Sjors commented at 7:50 am on May 10, 2024: member

tACK 57a06646952fed98c1c281f02fe58a0758a8ed5a

I checked that Sage produces the number, and ran the tests.

It seems that BIP341 introduced H as just an example of a NUMS point:

One example of such a point is H

The BIP got it from libsecp256k1 which IIUC only uses it for tests. As does Bitcoin Core so far.

BIP352 gives it special status:

The one exception is script path spends that use NUMS point H as their internal key

DrahtBot requested review from theStack on May 10, 2024

S3RK commented at 7:57 am on May 10, 2024: contributor

Code Review ACK 57a06646952fed98c1c281f02fe58a0758a8ed5a

The constant definition is consistent with BIP-341. PR removes code duplication and provides a single place to refer to NUMS_H either as vector of bytes or x-only pubkey.

theuni approved

theuni commented at 6:41 pm on May 10, 2024: member

Code review 57a06646952fed98c1c281f02fe58a0758a8ed5a. I didn’t verify with sage.

theStack approved

theStack commented at 4:35 am on May 11, 2024: contributor

re-ACK 57a06646952fed98c1c281f02fe58a0758a8ed5a

DrahtBot requested review from theStack on May 11, 2024

in src/pubkey.cpp:196 in 57a0664695 outdated

191+
192+    import hashlib
193+    F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
194+    G_DER = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'
195+    G2 = EllipticCurve ([F (0), F (7)]).lift_x(F(int(hashlib.sha256(bytes.fromhex(G_DER)).hexdigest(),16)))
196+    print('%x %x' % G2.xy())

paplorinc commented at 10:09 am on May 12, 2024:

would it make sense to add a Python test which runs this exact script and checks that the result equals NUMS_H_DATA? Maybe there’s something like this already, found parts of it, could you please check? In that case we wouldn’t need to put code into a comment, we could just point to the test instead.

Sjors commented at 7:40 am on May 13, 2024:

I think that would require adding sage to our test dependencies (which I don’t think we should do).

josibake commented at 8:40 am on May 13, 2024:

I don’t see the value of running a test like this? The code here is not the definition of H, just one way of calculating the value, based on the definition in BIP341. For example, if the test were to fail, that would just mean the comment is out of date, not that our value for H is incorrect.

paplorinc commented at 2:38 pm on May 13, 2024:

What if we just extract it to code like it was done with the rest of the sage files, and reference the file instead of the code (I don’t like dead code in comments), e.g. https://github.com/bitcoin/bitcoin/blob/master/src/secp256k1/src/ecdsa_impl.h#L19 ?

josibake commented at 2:54 pm on May 13, 2024:

Going to leave this as is for now. The sage code in the comment is meant to provide background on where the constant comes from, so I’d prefer to leave it since it is more precise than a written out explanation. However, the code is not essential for checking the “correctness” of the value in that it would be sufficient for someone to simply check that this value matches BIP341. This value will never change, either, so I don’t see any advantage to having a sage file in this repo for generating the constant.

sipa commented at 7:57 pm on May 13, 2024:

If you want, all the EC logic for point decompression is in test/functional/test_framework/crypto/secp256k1.py, no need for Sage:

0from test_framework.crypto.secp256k1 import G
1from hashlib import sha256
2
3print(sha256(G.to_bytes_uncompressed()).digest().hex())

(and to test it’s actually an X coordinate):

0from test_framework.crypto.secp256k1 import FE, G, GE
1from hashlib import sha256
2
3assert GE.lift_x(FE.from_bytes(sha256(G.to_bytes_uncompressed()).digest())) is not None

josibake commented at 7:41 am on May 14, 2024:

Thanks for the code snippets @sipa . Seems like there is appetite for this, so added this script to test/functional/test_framework/crypto/secp256k1.py as a unit test and removed the sage code from the comment.

paplorinc commented at 7:33 pm on May 13, 2024: contributor

ACK 57a06646952fed98c1c281f02fe58a0758a8ed5a

in src/pubkey.cpp:194 in 57a0664695 outdated

189+ *
190+ *  More precisely, H is derived by running the following script with the sage mathematics software:
191+
192+    import hashlib
193+    F = FiniteField (0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F)
194+    G_DER = '0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8'

sipa commented at 7:43 pm on May 13, 2024:

This is not DER encoding; DER is only used for signatures (and once upon a time, for private keys in the wallet). The byte encoding used for secp256k1 public keys is defined in section 2.3.3 of SEC1 v2 (https://www.secg.org/sec1-v2.pdf), though I believe ANSI and/or NIST also standardized it (not for secp256k1 specifically, but for prime-ordered curves in general).

josibake commented at 7:39 am on May 14, 2024:

Fixed!

josibake force-pushed on May 14, 2024

josibake commented at 7:42 am on May 14, 2024: member

Updated the comment to remove the sage code and replaced with a python unit test for calculating H per @paplorinc and @sipa ’s suggestion.

in test/functional/test_framework/crypto/secp256k1.py:354 in e9dfa2840b outdated

345@@ -344,3 +346,9 @@ def mul(self, a):
346 
347 # Precomputed table with multiples of G for fast multiplication
348 FAST_G = FastGEMul(G)
349+
350+class TestFrameworkSecp256k1(unittest.TestCase):
351+    def test_H(self):
352+        H = sha256(G.to_bytes_uncompressed()).digest()
353+        assert GE.lift_x(FE.from_bytes(H)) is not None
354+        self.assertEqual(H.hex(), "50929b74c1a04954b78b4b6035e97a5e078a5a0f28ec96d547bfee9ace803ac0")

paplorinc commented at 7:59 am on May 14, 2024:

is it possible to avoid hard coding? That kinda’ defeats the purpose of the test I think

josibake commented at 8:05 am on May 14, 2024:

I don’t think so? The purpose of adding this code is to give a precise definition of how the constant from BIP341 is calculated. The assert confirms that this code generates a point which matches the expected value from BIP341 and allows anyone else to verify that the code == constant in src/pubkey.cpp == value from BIP341.

paplorinc commented at 8:11 am on May 14, 2024:

But we’re not actually testing the production code this way, i.e. the test would still pass if NUMS_H_DATA were to change (e.g. after an accidental local search/replace or whatever).

josibake commented at 9:42 am on May 14, 2024:

Right, but that’s not the intent of the python code: it’s merely to provide a more precise explanation of the definition of H. A unit test on secp256k1 seemed like the most natural fit.

Seems like what you actually want is a unit test in the C++ code to generate the value of H and then compare it to XOnlyPubKey::NUMS_H. I’ve added that in https://github.com/bitcoin/bitcoin/pull/30048/commits/9408a04e424cee0d226bde79171bd4954f9caeb0

crypto: add NUMS_H const b946f8a4c5

in test/functional/test_framework/crypto/secp256k1.py:350 in 91a804773c outdated

345@@ -344,3 +346,9 @@ def mul(self, a):
346 
347 # Precomputed table with multiples of G for fast multiplication
348 FAST_G = FastGEMul(G)
349+
350+class TestFrameworkSecp256k1(unittest.TestCase):

theStack commented at 8:14 am on May 14, 2024:

Should add secp256k1 to the unit test modules list (so it also gets executed on CI): https://github.com/bitcoin/bitcoin/blob/7fcf4e99791ca5be0b068ac03a81a50ece11dba3/test/functional/feature_framework_unit_tests.py#L15-L17

josibake commented at 8:25 am on May 14, 2024:

Done!

josibake force-pushed on May 14, 2024

tests, fuzz: use new NUMS_H const 9408a04e42

josibake force-pushed on May 14, 2024

DrahtBot added the label CI failed on May 14, 2024

DrahtBot commented at 9:44 am on May 14, 2024: contributor

🚧 At least one of the CI tasks failed. Make sure to run all tests locally, according to the documentation.

Possibly this is due to a silent merge conflict (the changes in this pull request being incompatible with the current code in the target branch). If so, make sure to rebase on the latest commit of the target branch.

Leave a comment here, if you need help tracking down a confusing failure.

Debug: https://github.com/bitcoin/bitcoin/runs/24941511130

paplorinc commented at 11:22 am on May 14, 2024: contributor

re-ACK 9408a04e424cee0d226bde79171bd4954f9caeb0

DrahtBot requested review from Sjors on May 14, 2024

DrahtBot requested review from S3RK on May 14, 2024

DrahtBot requested review from theStack on May 14, 2024

in src/test/key_tests.cpp:373 in 9408a04e42

364@@ -364,4 +365,13 @@ BOOST_AUTO_TEST_CASE(key_ellswift)
365     }
366 }
367 
368+BOOST_AUTO_TEST_CASE(bip341_test_h)
369+{
370+    std::vector<unsigned char> G_uncompressed = ParseHex("0479be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8");
371+    HashWriter hw;
372+    hw.write(MakeByteSpan(G_uncompressed));
373+    XOnlyPubKey H{hw.GetSHA256()};

theStack commented at 11:59 am on May 14, 2024:

nit, as one-liner (feel free to ignore):

0    XOnlyPubKey H{(HashWriter{} << Span(G_uncompressed)).GetSHA256()};

josibake commented at 12:31 pm on May 14, 2024:

Nice, will add if I end up needing to retouch!

theStack approved

theStack commented at 11:59 am on May 14, 2024: contributor

Code-review ACK 9408a04e424cee0d226bde79171bd4954f9caeb0

achow101 commented at 5:59 pm on May 17, 2024: member

ACK 9408a04e424cee0d226bde79171bd4954f9caeb0

achow101 merged this on May 17, 2024

achow101 closed this on May 17, 2024

crypto: add NUMS_H const #30048

Code Coverage

Reviews

Conflicts

crypto: add `NUMS_H` const #30048