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

siv2r · 2022-01-04T23:05:50Z

Fixes #946 and #1061

Changes:

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

real-or-random

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.

src/field.h

siv2r · 2022-01-13T11:26:03Z

In fe_sqrt:

secp256k1/src/field_impl.h

Lines 132 to 135 in a1102b1

    
           /* Check that a square root was actually calculated */ 
        
           secp256k1_fe_sqr(&t1, r); 
        
           return secp256k1_fe_equal(&t1, a);

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 · 2022-01-13T12:01:07Z

@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 · 2022-01-13T12:05:45Z

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 · 2022-01-13T12:58:50Z

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 · 2022-01-13T18:09:43Z

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:

secp256k1/src/modules/extrakeys/tests_impl.h

Lines 75 to 77 in a1102b1

    
           CHECK(secp256k1_fe_equal(&pk1.x, &pk2.x) == 1); 
        
           secp256k1_fe_negate(&y, &pk2.y, 1); 
        
           CHECK(secp256k1_fe_equal(&pk1.y, &y) == 1);

Even here, the magnitude of y is two, so modifying the _fe_sqrt function (which I suggested) is a bad idea.

real-or-random · 2022-01-13T18:21:14Z

secp256k1/src/modules/extrakeys/tests_impl.h

Lines 75 to 77 in a1102b1

CHECK(secp256k1_fe_equal(&pk1.x, &pk2.x) == 1);

secp256k1_fe_negate(&y, &pk2.y, 1);

CHECK(secp256k1_fe_equal(&pk1.y, &y) == 1);

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 · 2022-01-13T18:58:18Z

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 · 2022-01-13T19:05:59Z

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 · 2022-01-14T04:15:11Z

addressed #1062 (comment) and #1062 (review) (detailed explanation in 08186e8).

siv2r · 2022-01-14T04:25:21Z

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

real-or-random · 2022-01-18T17:58:25Z

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

peterdettman · 2022-01-19T17:44:08Z

@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 · 2022-01-26T19:14:58Z

addressed #1061

real-or-random · 2022-01-27T10:01:16Z

@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 · 2022-01-27T10:45:04Z

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

siv2r · 2022-01-30T23:22:31Z

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

src/field.h

src/group_impl.h

sipa · 2022-02-01T17:50:13Z

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 · 2022-02-01T19:39:04Z

No worries, I will rebase this PR.

real-or-random · 2023-05-11T17:31:33Z

No worries, I will rebase this PR.

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

siv2r · 2023-08-15T12:14:28Z

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

siv2r · 2023-08-15T12:23:29Z

src/tests.c

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


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 · 2023-08-15T15:01:06Z

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 · 2023-08-16T11:54:17Z

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.

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.

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

siv2r · 2023-08-16T12:11:46Z

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

real-or-random

utACK 54058d1

jonasnick

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 54058d1

siv2r changed the title ~~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 Jan 4, 2022

real-or-random reviewed Jan 5, 2022

View reviewed changes

src/field.h Outdated Show resolved Hide resolved

siv2r force-pushed the doc-fe-equal-var branch from 77f5323 to 08186e8 Compare January 14, 2022 04:12

siv2r changed the title ~~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 Jan 14, 2022

siv2r changed the title ~~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 Jan 14, 2022

real-or-random mentioned this pull request Jan 18, 2022

call fe_verfiy for not normalized field element in fe_set_b32 #1061

Closed

siv2r force-pushed the doc-fe-equal-var branch from 08186e8 to d40ea5f Compare January 26, 2022 19:13

real-or-random mentioned this pull request Feb 1, 2022

Abstract out and merge all the magnitude/normalized logic #1066

Merged

sipa reviewed Feb 1, 2022

View reviewed changes

src/field.h Outdated Show resolved Hide resolved

src/group_impl.h Outdated Show resolved Hide resolved

real-or-random added assurance user-documentation user-facing documentation labels May 11, 2023

siv2r force-pushed the doc-fe-equal-var branch from ea1225b to 315275f Compare August 15, 2023 12:11

siv2r commented Aug 15, 2023

View reviewed changes

real-or-random added tweak/refactor and removed user-documentation user-facing documentation assurance labels Aug 15, 2023

siv2r changed the title ~~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) Aug 15, 2023

siv2r added 2 commits August 16, 2023 17:38

tests: remove unwanted secp256k1_fe_normalize_weak call

bb4efd6

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.

field: remove secp256k1_fe_equal_var

54058d1

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

siv2r force-pushed the doc-fe-equal-var branch from 315275f to 54058d1 Compare August 16, 2023 12:09

real-or-random approved these changes Aug 16, 2023

View reviewed changes

jonasnick reviewed Aug 17, 2023

View reviewed changes

real-or-random merged commit de657c2 into bitcoin-core:master Aug 17, 2023

siv2r deleted the doc-fe-equal-var branch March 5, 2024 09:22

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

Uh oh!

Conversation

siv2r commented Jan 4, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

real-or-random left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

siv2r commented Jan 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

peterdettman commented Jan 13, 2022

Uh oh!

peterdettman commented Jan 13, 2022

Uh oh!

real-or-random commented Jan 13, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

siv2r commented Jan 13, 2022

Uh oh!

real-or-random commented Jan 13, 2022

Uh oh!

peterdettman commented Jan 13, 2022

Uh oh!

peterdettman commented Jan 13, 2022

Uh oh!

siv2r commented Jan 14, 2022

Uh oh!

siv2r commented Jan 14, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

real-or-random commented Jan 18, 2022

Uh oh!

peterdettman commented Jan 19, 2022

Uh oh!

siv2r commented Jan 26, 2022

Uh oh!

real-or-random commented Jan 27, 2022

Uh oh!

siv2r commented Jan 27, 2022

Uh oh!

siv2r commented Jan 30, 2022

Uh oh!

Uh oh!

Uh oh!

sipa commented Feb 1, 2022

Uh oh!

siv2r commented Feb 1, 2022

Uh oh!

real-or-random commented May 11, 2023

Uh oh!

siv2r commented Aug 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

siv2r Aug 15, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

real-or-random commented Aug 15, 2023

Uh oh!

real-or-random commented Aug 16, 2023

Uh oh!

siv2r commented Aug 16, 2023

Uh oh!

real-or-random left a comment

Choose a reason for hiding this comment

Uh oh!

jonasnick left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

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

siv2r commented Jan 4, 2022 •

edited

Loading

siv2r commented Jan 13, 2022 •

edited

Loading

real-or-random commented Jan 13, 2022 •

edited

Loading

siv2r commented Jan 14, 2022 •

edited

Loading

siv2r commented Aug 15, 2023 •

edited

Loading

siv2r Aug 15, 2023 •

edited

Loading