clean up in-comment Sage code (refer to secp256k1

theStack commented at 2:52 pm on June 11, 2023: contributor

Some of the C source files contain contain in-comment Sage code calculating secp256k1 parameters that are already defined in the file secp256k1_params.sage. Replace that by a corresponding load instruction and access the necessary variables. In ecdsa_impl.h, update the comment to use a one-line shell command calling sage to get the values.

The remaining code (test test_add_neg_y_diff_x in tests.c) is updated to work with a current version based on Python3 (Sage 9.0+, see https://wiki.sagemath.org/Python3-Switch).

The latter can be seen as a small follow-up to PR #849 (commit 13c88efed0005eb6745a222963ee74564054eafb).

real-or-random commented at 4:54 pm on June 11, 2023: contributor

Thanks for caring about this!

I think the sage code for secp256k1_ecdsa_const_order_as_fe and also secp256k1_ecdsa_const_p_minus_order could be dropped entirely. They’re easy to write given https://github.com/bitcoin-core/secp256k1/blob/master/sage/secp256k1_params.sage#L17. Or even better, those values can just be defined in the secp256k1_params.sage file, which is run on CI to avoid code rot.

Not sure what do to with the code in the test. I haven’t checked. Are these the only instances in the entire code base?

real-or-random added the label documentation on Jun 11, 2023

theStack commented at 1:37 pm on June 14, 2023: contributor

I think the sage code for secp256k1_ecdsa_const_order_as_fe and also secp256k1_ecdsa_const_p_minus_order could be dropped entirely. They’re easy to write given https://github.com/bitcoin-core/secp256k1/blob/master/sage/secp256k1_params.sage#L17. Or even better, those values can just be defined in the secp256k1_params.sage file, which is run on CI to avoid code rot.

Sounds like a good idea. By the way, I found this approach for calculating p interesting (i.e. “find the first number equal or lower than 2^256 - 2^32 - 1023 which is prime”): https://github.com/bitcoin-core/secp256k1/blob/67214f5f7d8e0bdf193ceb1f47ba8277d1a0871a/src/ecdsa_impl.h#L18-L23

But I guess there’s no good reason to keep that code and having the fixed p number (as it is now in secp256k1_params.sage) is just fine? The referenced SEC2 document also doesn’t mention anything about the above approach. 🤷‍♂️

Not sure what do to with the code in the test. I haven’t checked. Are these the only instances in the entire code base?

I think that’s the only instances. My approach was manually looking through all the results of $ git grep -i sage (which included many false-positives due to the word “message”) – of course, it could still be possible that I either missed something, or there is sage code around without the word “sage” in a description close.

real-or-random commented at 1:35 pm on June 15, 2023: contributor

But I guess there’s no good reason to keep that code and having the fixed p number (as it is now in secp256k1_params.sage) is just fine?

Yeah. If anything, the definition in SEC2 is canonical, and it just gives the number as you point out.

For the code in the tests, perhaps that can at least be shortened to assume that the constants from https://github.com/bitcoin-core/secp256k1/blob/master/sage/secp256k1_params.sage are already defined.

sipa commented at 12:57 pm on June 19, 2023: contributor

The code in ecdsa_impl can be dropped entirely, I think, as it’s just computing the group order. If we care about the (assumed) mechanism through which the constants were generated, that belongs more in secp256k1_params.sage itself.

theStack force-pushed on Jul 7, 2023

theStack renamed this:
~~fix in-comment Sage code to work with Sage9.0+ (based on Python3)~~
clean up in-comment Sage code (refer to secp256k1_params.sage, update to Python3)
on Jul 7, 2023

theStack commented at 5:11 pm on July 7, 2023: contributor

I’ve removed all in-comment sage code for calculating secp256k1 parameters and referred to secp256k1_params.sage instead. For ecdsa_impl.h, the comment is now a shell command which calls sage to emit the necessary values. There’s still a small chance for code rot, though I’d argue it’s negligible – the chance that the filename secp256k1_params.sage ever changes or that the basic parameters P and N are renamed is rather small I’d say. Still open for alternative approaches.

in src/tests.c:4015 in 017358e685 outdated

4015-     * G = C.lift_x(0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798)
4016-     * N = FiniteField(G.order())
4017+     *
4018+     * load("secp256k1_params.sage")
4019      *
4020      * # endomorphism values (lambda is 1^{1/3} in N, beta is 1^{1/3} in F)

real-or-random commented at 5:36 pm on July 7, 2023:

comment needs to be updated, I think

theStack commented at 5:47 pm on July 7, 2023:

Done (assumed that you only meant the rename from N to Z).

real-or-random commented at 5:36 pm on July 7, 2023: contributor

There’s still a small chance for code rot, though I’d argue it’s negligible – the chance that the filename secp256k1_params.sage ever changes or that the basic parameters P and N are renamed is rather small I’d say. Still open for alternative approaches.

certainly good enough :)

theStack force-pushed on Jul 7, 2023

clean up in-comment Sage code (refer to secp256k1_params.sage, update to Python3)

Some of the C source files contain contain in-comment Sage code
calculating secp256k1 parameters that are already defined in the file
secp256k1_params.sage.  Replace that by a corresponding load instruction
and access the necessary variables. In ecdsa_impl.h, update the comment
to use a one-line shell command calling sage to get the values.

The remaining code (test `test_add_neg_y_diff_x` in tests.c) is updated
to work with a current version based on Python3 (Sage 9.0+, see
https://wiki.sagemath.org/Python3-Switch).

The latter can be seen as a small follow-up to PR #849 (commit
13c88efed0005eb6745a222963ee74564054eafb).

600c5adcd5

theStack force-pushed on Jul 10, 2023

theStack commented at 0:37 am on July 10, 2023: contributor

I only realized now that the code for calculating the lambda value in test_add_neg_y_diff_x can also be removed, as it’s equivalent with LAMBDA from secp256k1_params.sage (i.e. given order N and field Z for secp256k1, the sage expressions Z(3)^((N-1)/3) and (1 - (polygen(Z))^3).roots()[1][0] lead to the same value):

0sage: load("secp256k1_params.sage")
1sage: Z(3)^((N-1)/3)
237718080363155996902926221483475020450927657555482586988616620542887997980018
3sage: (1 - (polygen(Z))^3).roots()[1][0]
437718080363155996902926221483475020450927657555482586988616620542887997980018
5sage: LAMBDA
637718080363155996902926221483475020450927657555482586988616620542887997980018

Force-pushed accordingly. (For a rough explanation why these two expressions are equivalent, I’d be more than thankful :))

sipa commented at 1:36 pm on July 10, 2023: contributor

Let $F = GF(n)$, where $n$ is prime and $n-1$ is a multiple of 3.

We know from Fermat’s Little Theorem that for any non-zero $x$ it holds that $x^n = x$, and thus $x^{n-1} = 1$.

Pick a non-zero element $q$ in the field, and let $r = q^{(n-1)/3}$. Then it follows that $r^3 - 1 = (q^{(n-1)/3})^3 - 1 = q^{n-1} - 1 = 1 - 1 = 0$. Thus, $r$ is a cube root of 1, but possible a trivial one ($r=1$). It turns out that if $q$ was itself a cube, then $r = q^{(n-1)/3} = 1$, but otherwise you get a nontrivial root of 1.

sipa commented at 1:53 pm on July 10, 2023: contributor

ACK 600c5adcd59240305e22918943f45dceeabb7e93

real-or-random approved

real-or-random commented at 4:33 pm on July 10, 2023: contributor

ACK 600c5adcd59240305e22918943f45dceeabb7e93

real-or-random merged this on Jul 10, 2023

real-or-random closed this on Jul 10, 2023

theStack deleted the branch on Jul 10, 2023

fanquake referenced this in commit 56c05c5ec4 on Jul 17, 2023

fanquake referenced this in commit ff061fde18 on Jul 18, 2023

hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023

jonasnick cross-referenced this on Jul 27, 2023 from issue Upstream PRs 1357, 1345, 1358, 1368, 1369, 1323, 1364, 1370, 1367, 1344, 1371, 1363, 1340, 1366, 1313, 1378, 1298, 1382, 1383, 1384, 1386 by jonasnick

clean up in-comment Sage code (refer to secp256k1_params.sage, update to Python3) #1340