Removes `_fe_equal_var`, and unwanted `_fe_normalize

siv2r commented at 11:05 pm on January 4, 2022: contributor

Changes:

removes unwanted fe_normalize_weak calls to the second argument of fe_equal
removes fe_equal_var

siv2r renamed this:
~~update preconditions of `fe_equal_var` and remove unwanted `_fe_normalize_weak` calls~~
update preconditions of `fe_equal_var` in doc and remove unwanted `_fe_normalize_weak` calls
on Jan 4, 2022

in src/field.h:68 in 77f5323d8c outdated

63@@ -64,10 +64,13 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
64 /** Check the "oddness" of a field element. Requires the input to be normalized. */
65 static int secp256k1_fe_is_odd(const secp256k1_fe *a);
66 
67-/** Compare two field elements. Requires magnitude-1 inputs. */
68+/** Compare two field elements. Requires both the inputs to have magnitude = 1.
69+ *  i.e. a->magnitude = 1 and b->magnitude = 1 */

real-or-random commented at 3:35 pm on January 5, 2022:

Just a nit but why not just

0/** Compare two field elements. Requires both the inputs to have magnitude 1. */

(Hm, in fact it’s <= 1 even but that should go away when #1001 is solved).

I don’t think it’s necessary to phrase it twice (and x->magnitude is only there #ifdef VERIFY – but ok people would understands what is meant. ;))

Same below.

siv2r commented at 4:12 pm on January 5, 2022:

Sure, I will remove this additional comment. I wanted to be more explicit, but I forgot that x->magnitude is used only in the VERIFY build.

real-or-random commented at 3:35 pm on January 5, 2022: contributor

Concept ACK

I think then we should add (#ifdef VERIFY) magnitude checks to secp256k1_fe_equal_var and secp256k1_fe_equal.

If you’re up to it, I think the other field function could need an audit for similar checks.

siv2r commented at 11:26 am on January 13, 2022: contributor

In fe_sqrt: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/field_impl.h#L132-L135 Here, the secp256k1_fe_sqr function ensures that t1->magnitude = 1 but there is no guarantee for the magnitude of a to be one since it is passed into the function. Hence, some fe_sqrt tests are failing after adding magnitude checks inside fe_equal.

We could do secp256k1_fe_normalize_weak(a) but this changes the value of a and we don’t want that right? Alternatively, we could call fe_equal_var instead of fe_equal. Is it necessary for secp256k1_fe_sqrt to be of constant time?

peterdettman commented at 12:01 pm on January 13, 2022: contributor

@siv2r Regarding _fe_sqrt, there is an implicit magnitude restriction on a, since it is used as the input to _fe_mul and _fe_sqr at the top of the method. That magnitude restriction is <= 8. 8 is also a kind of global implicit limit for inputs where not otherwise stated (but we should definitely be working towards fully documenting and validating all such assumptions).

I think it might be better to just say that both inputs to the equals methods can be magnitude <= 8 too (indeed tied to the mul/sqr limit whatever it is or changes to). There’s no real obstacle to the implementation(s) (just change the third argument to _fe_negate to 8) and no performance hit AFAICT.

peterdettman commented at 12:05 pm on January 13, 2022: contributor

Is it necessary for secp256k1_fe_sqrt to be of constant time?

It’s only used in a single var-time caller, so technically it could be changed to sqrt_var, but preferably not.

real-or-random commented at 12:58 pm on January 13, 2022: contributor

Apparently secp256k1_fe_equal and secp256k1_fe_equal_var are identical up to the final call to normalizes_to_zero or normalizes_to_zero_var and so they both only require that a has magnitude 1. So we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

Edited because I first thought secp256k1_fe_equal and secp256k1_fe_equal_var are exactly identical.

siv2r commented at 6:09 pm on January 13, 2022: contributor

It’s only used in a single var-time caller

Oh, Okay. Then, creating a new function for secp256k1_fe_sqrt_var (while renaming the old one to _fe_sqrt_const) might be overkill.

we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

Yes, I think this might be a better approach since it keeps the functionality of both fe_equal_var and fe_equal similar.

After this, I felt we needed to remove the _fe_normalize_weak calls before _fe_equal, but surprisingly _fe_equal is used rarely in the code. The only other place where it is used is: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77 Even here, the magnitude of y is two, so modifying the _fe_sqrt function (which I suggested) is a bad idea.

real-or-random commented at 6:21 pm on January 13, 2022: contributor

https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77

Hehe ok, and here it’s basically an oversight. This is just test code, so fe_equal_var could be used instead. I mean, not that it matters.

peterdettman commented at 6:58 pm on January 13, 2022: contributor

fe_equal_var is really a bit dubious. It only has a fast path when the inputs are not equal, and the only callers are for public key parsing and (ECDSA) verification, where that would mean an error condition and is probably uncommon. If the fast path is not hit, it actually costs a couple of cycles more. (Not to mention that the performance difference is tiny relative to those operations anyway).

peterdettman commented at 7:05 pm on January 13, 2022: contributor

While I’m on the subject, the other callers to _fe_normalizes_to_zero_var expect a false result and so will almost always hit the fast path. Depending on the level of inlining, _fe_equal_var could be “spoiling” the branch prediction for that fast path check for the other callers.

siv2r force-pushed on Jan 14, 2022

siv2r commented at 4:15 am on January 14, 2022: contributor

addressed #1062 (review) and #1062#pullrequestreview-844742940 (detailed explanation in 08186e8).

siv2r commented at 4:25 am on January 14, 2022: contributor

I also benchmarked the tests.c file (using time ./tests) since a lot of secp256k1_fe_verify calls were added in this PR. These are the results (on 64-bit, i7-8750H) for three iterations:

branch	iter1	iter2	iter3
master	2min 26.21sec	2min 26.44sec	2min 26.68sec
this PR	2min 26.99sec	2min 26.91sec	2min 26.83sec

siv2r renamed this:
~~update preconditions of `fe_equal_var` in doc and remove unwanted `_fe_normalize_weak` calls~~
document field functions assumptions and validate it using magnitude and `fe_verify` checks
on Jan 14, 2022

siv2r renamed this:
~~document field functions assumptions and validate it using magnitude and `fe_verify` checks~~
Document field functions assumptions and validate it using magnitude and `fe_verify` checks
on Jan 14, 2022

real-or-random commented at 5:58 pm on January 18, 2022: contributor

@peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

real-or-random cross-referenced this on Jan 18, 2022 from issue call `fe_verfiy` for not normalized field element in `fe_set_b32` by siv2r

peterdettman commented at 5:44 pm on January 19, 2022: contributor

@peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

Yeah, pretty much. Until there’s a performance-sensitive caller for whom a != b is the expected result, I don’t see any value in _fe_equal_var. If such a caller does turn up, then there should be a fast path for inequality that doesn’t even need the subtraction, so we’d rewrite it anyway.

siv2r force-pushed on Jan 26, 2022

siv2r commented at 7:14 pm on January 26, 2022: contributor

addressed #1061

real-or-random commented at 10:01 am on January 27, 2022: contributor

@siv2r Do you plan to also remove the fe_equal_var in a further commit? Or should we do this in a separate PR?

(If you want to add it here, I think it’s really ok to add it on top of the existing commits, no need to rewrite the existing commits).

siv2r commented at 10:45 am on January 27, 2022: contributor

Okay, I will remove fe_equal_var in a new commit (this PR).

siv2r commented at 11:22 pm on January 30, 2022: contributor

Removed fe_equal_var and documented the reason in fe_equal
Replaced the fe_equal_var calls with fe_equal

real-or-random cross-referenced this on Feb 1, 2022 from issue Abstract out and merge all the magnitude/normalized logic by sipa

in src/field.h:69 in ea1225bff5 outdated

63@@ -64,12 +64,12 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
64 /** Check the "oddness" of a field element. Requires the input to be normalized. */
65 static int secp256k1_fe_is_odd(const secp256k1_fe *a);
66 
67-/** Compare two field elements. Requires magnitude-1 inputs. */
68+/** Compare two field elements. Requires the first input to have magnitude equal to 1. 
69+ *  The variable time counterpart of this function `secp256k1_fe_equal_var` was removed 
70+ *  since it hits fast path only when the inputs are unequal. This unequal inputs

sipa commented at 5:43 pm on February 1, 2022:

I think this is something you can document in the commit comment; it’s weird to have it in the codebase. As in: there are many other things that aren’t implemented because they’re not worth it; they aren’t exhaustively listed in the source code.

in src/group_impl.h:244 in c6c44f4f58 outdated

240@@ -241,7 +241,7 @@ static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a)
241     secp256k1_fe r, r2;
242     VERIFY_CHECK(!a->infinity);
243     secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
244-    r2 = a->x; secp256k1_fe_normalize_weak(&r2);
245+    r2 = a->x;

sipa commented at 5:45 pm on February 1, 2022:

The r2 variable isn’t needed anymore; you can just call return secp256k1_fe_equal_var(&r, &a->x); directly.

siv2r commented at 7:25 pm on February 1, 2022:

Nice catch, Thanks!

sipa commented at 5:50 pm on February 1, 2022: contributor

I missed the “field: add magnitude check and _fe_verify check for internal field APIs” commit being added here before writing #1066 (which duplicates some of its efforts, but also goes a lot further in a number of ways). Feel free to keep it in (and I’ll rebase), but if you think #1066 covers everything you’re doing here, perhaps it’s easier to leave that for that PR.

siv2r commented at 7:39 pm on February 1, 2022: contributor

No worries, I will rebase this PR.

real-or-random commented at 5:31 pm on May 11, 2023: contributor

No worries, I will rebase this PR.

Ok, merging #1066 took a while…. This PR here needs rebase now. :)

real-or-random added the label assurance on May 11, 2023

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

siv2r force-pushed on Aug 15, 2023

siv2r commented at 12:14 pm on August 15, 2023: contributor

Rebased.

#1066 took care of all the magnitude and fe_verify checks so, this PR currently does:

removes unwanted fe_normalize_weak calls to the second argument of fe_equal
removes fe_equal_var

in src/tests.c:2994 in 79abdf0a50 outdated

2966@@ -2967,7 +2967,6 @@ static int check_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
2967     secp256k1_fe an = *a;
2968     secp256k1_fe bn = *b;
2969     secp256k1_fe_normalize_weak(&an);
2970-    secp256k1_fe_normalize_var(&bn);

siv2r commented at 12:23 pm on August 15, 2023:

Not sure why normalize_var was used on bn. I assumed it intended to set bn’s magnitude to 1 for the fe_equal call. So, I removed it. Please let me know if that’s not the case, and I’ll revert this.

All test cases passed with this change.

real-or-random commented at 3:01 pm on August 15, 2023: contributor

Nice. :)

#1066 took care of all the magnitude and fe_verify checks so, this PR currently does:

Can you update the PR title and the initial comment, so that they reflect the current status?

real-or-random removed the label documentation on Aug 15, 2023

real-or-random removed the label assurance on Aug 15, 2023

real-or-random added the label refactor/smell on Aug 15, 2023

siv2r renamed this:
~~Document field functions assumptions and validate it using magnitude and `fe_verify` checks~~
Removes `_fe_equal_var`, and unwanted `_fe_normalize_weak` calls (in tests)
on Aug 15, 2023

real-or-random commented at 11:54 am on August 16, 2023: contributor

Needs rebase again, sorry, but should be trivial. :)

Thanks for updating the PR title. Can you also update the initial post/PR description (e.g., replace the contents with #1062 (comment) )? It’s just cosmetic, but the text of will be added to the merge commit, so it makes sense to keep this updated.

tests: remove unwanted `secp256k1_fe_normalize_weak` call

It is not neccessary for the second argument in `secp256k1_fe_equal_var`
(or `secp256k1_fe_equal`) to have magnitude = 1.
Hence, removed the `secp256k1_fe_normalize_weak` call for those argument.

bb4efd6404

field: remove `secp256k1_fe_equal_var`

`fe_equal_var` hits a fast path only when the inputs are unequal, which is
uncommon among its callers (public key parsing, ECDSA verify).

54058d16fe

siv2r force-pushed on Aug 16, 2023

siv2r commented at 12:11 pm on August 16, 2023: contributor

Rebased and updated the description. I forgot about the merge commit including the description too. Thanks!

real-or-random approved

real-or-random commented at 12:13 pm on August 16, 2023: contributor

utACK 54058d16feaa431520029335e2d56252859d3260

jonasnick commented at 3:05 pm on August 17, 2023: contributor

Until there’s a performance-sensitive caller for whom a != b is the expected result, I don’t see any value in _fe_equal_var.

I don’t think we know what the expected result of the caller is. The difference seems to be negligible though.

ACK 54058d16feaa431520029335e2d56252859d3260

real-or-random merged this on Aug 17, 2023

real-or-random closed this on Aug 17, 2023

fanquake referenced this in commit a2cadecc45 on Aug 21, 2023

fanquake cross-referenced this on Aug 21, 2023 from issue libsecp256k1: remove secp256k1_fe_equal_var by fanquake

sipa referenced this in commit c0da4f60e2 on Sep 4, 2023

jonasnick cross-referenced this on Sep 19, 2023 from issue Upstream PRs 1391, 1290, 1389, 1397, 1399, 1400, 1348, 1402, 1274, 1394, 1404, 1062, 1401, 1373, 1403, 1398, 1405, 1396, 1406, 1410, 1409, 1411, 1412, 1414, 1413, 1415, 1417, 1390, 1416, 1422, 1424, 1395 by jonasnick

Retropex referenced this in commit 5f62ed90f6 on Oct 4, 2023

real-or-random referenced this in commit d575ef9aca on Oct 12, 2023

siv2r deleted the branch on Mar 5, 2024

Removes _fe_equal_var, and unwanted _fe_normalize_weak calls (in tests) #1062

Removes `_fe_equal_var`, and unwanted `_fe_normalize_weak` calls (in tests) #1062