normalize_weak
calls is obviously the critical one and needs the most attention for review.
tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) #1348
pull theStack wants to merge 6 commits into bitcoincore:master from theStack:revival_of_1032 changing 5 files +182 −73
theStack commented at 2:12 pm on June 15, 2023: contributorThis PR picks up #1032 by peterdettman. It’s essentially a rebase on master; the original first commit (09dbba561fdb9d57a2cc9842ce041d9ba29a6189) which introduced group verification methods has mostly been replaced by PR #1299 (commit f20266722ac93ca66d1beb0d2f2d2469b95aafea) and what remains now is only adding a few missing checks at some places. The remaining commits are unchanged, though some (easytosolve) conflicts appeared through cherrypicking. The last commit which actually removes the

theStack forcepushed on Jun 27, 2023

theStack commented at 10:18 pm on June 27, 2023: contributorRebased on master (there was a conflict in tests.c due to #1358) and also updated the operations count comments on each of the optimized functions (i.e.
secp256k1_gej_add_ge_var
,secp256k1_gej_add_zinv_var
andsecp256k1_gej_add_ge
) in the last commit. 
realorrandom added the label assurance on Jun 27, 2023

realorrandom added the label performance on Jun 27, 2023

realorrandom crossreferenced this on Jul 3, 2023 from issue WIP Group verification by peterdettman

realorrandom crossreferenced this on Jul 3, 2023 from issue group: save normalize_weak calls in `secp256k1_ge_is_valid_var`/`secp256k1_gej_eq_x_var` by theStack

in src/field.h:357 in 7ba858ed17 outdated
351@@ 352,4 +352,12 @@ static int secp256k1_fe_is_square_var(const secp256k1_fe *a); 352 /** Check invariants on a field element (noop unless VERIFY is enabled). */ 353 static void secp256k1_fe_verify(const secp256k1_fe *a); 354 355+#ifdef VERIFY 356+ 357+/** Assert a contextspecific limit m on the magnitude of a. m cannot be outside
sipa commented at 1:58 pm on July 10, 2023:This comment is outdated; all implementations now support the same range of magnitudes, 032 inclusive (since #1066). That also means the implementation of thissecp256k1_fe_verify_magnitude
can be in field_impl.h rather than in the representationspecific files.
theStack commented at 11:08 pm on July 10, 2023:Movedsecp256k1_fe_verify_magnitude
to a (single) implementation in field_impl.h, also removed the VERIFY preprocessor condition from field.h and add a noop implementation for the case that VERIFY isn’t set instead (even though the noop case isn’t currently used, it seems to be more consistent to _fe_verify that way). 
theStack forcepushed on Jul 10, 2023

in src/group_impl.h:243 in 672b1016ff outdated
234@@ 231,6 +235,7 @@ static void secp256k1_ge_table_set_globalz(size_t len, secp256k1_ge *a, const se 235 secp256k1_fe_verify(&zr[i]); 236 /* Ensure all y values are in weak normal form for fast negation of points */ 237 secp256k1_fe_normalize_weak(&a[i].y); 238+ secp256k1_ge_verify(&a[i]);
realorrandom commented at 1:08 pm on July 11, 2023:nit: I think the functions would be easier to read, if they all follow the same pattern (in particular the functions with loops:)
 on entry, verify all input ge, gej
 (possibly an empty line if you’re willing to add this)
 actual function body
 (possibly an empty line if you’re willing to add this)
 on exit, verify all output gej, possibly separated by a newline
theStack commented at 0:05 am on July 14, 2023:Started working on that but got doubt, as I think that would need additional verification loops at the start and end of a function if the input is an array of ge(j) instances (like in secp256k1_ge_table_set_globalz). Is that what you meant? (If yes, maybe good followup material?)
realorrandom commented at 7:56 am on July 14, 2023:Is that what you meant?
Yes, this would decouple the verification from the actual code. (And loops could be in
#ifdef VERIFY
, though any sane compiler would remove the empty loop.)(If yes, maybe good followup material?)
Okay, fair. I’m happy with any way in the end.
My thinking was that the advantage of doing it in this PR is that it will be easier to check for reviewers that verification is present everywhere. (The diff of that commit will be large, but noone will need to read the diff; they can just check if the result catches everything.) But I’m convinced of this already because I did the work to go through the
group_impl.h
.If you think a separate PR for this refactor is better, then yet another way to do this would be to have a separate PR before this PR. But this may require more rebasing work.
I believe you can decide best now that you looked into this.
theStack commented at 10:48 am on July 14, 2023:My thinking was that the advantage of doing it in this PR is that it will be easier to check for reviewers that verification is present everywhere. (The diff of that commit will be large, but noone will need to read the diff; they can just check if the result catches everything.)
That makes sense! Thanks for elaborating, the motivation is now clear to me. Added the suggestion in the first commit. Should be quite trivial to review, only the changes in
secp256k1_ge_table_set_globalz
are a bit more invasive, as the initialization ofi
for the backwards loop is now done later, due toi
also being used for the verification loop of inputs before. But I think that’s actually even a slight improvement because we avoid a potential integer underflow fori
in the case oflen == 0
(even though that’s more theoretical, in practice noone would call that function with a zerolength I guess).I decided to put the input/output verification loops in
#ifdef VERIFY
, mostly for visual reasons (I’d also assume that even without those, most compilers would optimize the loops away anyway), but also happy to remove them if wished. 
in src/field.h:356 in d0d4d09df2 outdated
351@@ 352,4 +352,8 @@ static int secp256k1_fe_is_square_var(const secp256k1_fe *a); 352 /** Check invariants on a field element (noop unless VERIFY is enabled). */ 353 static void secp256k1_fe_verify(const secp256k1_fe *a); 354 355+/** Assert a contextspecific limit m on the magnitude of a, where 356+ * m must be in the supported range [0,32] (noop unless VERIFY is enabled). */ 357+static void secp256k1_fe_verify_magnitude(const secp256k1_fe *a, int m);
realorrandom commented at 1:13 pm on July 11, 2023:nits in the comment:
 s/Assert/Check (Assert is actually the better term, but we write check everywhere else for this. Or change it in the entire code base ;))
 “contextspecific” can be a bit unclear. And I don’t think it adds much.
 Maybe just: “Check that the magnitude of a is at most m. (…) “?
theStack commented at 0:03 am on July 14, 2023:Thanks, went with your suggestion. 
in src/group_impl.h:94 in 4da686881c outdated
88@@ 89,9 +89,9 @@ static void secp256k1_gej_verify(const secp256k1_gej *a) { 89 secp256k1_fe_verify(&a>x); 90 secp256k1_fe_verify(&a>y); 91 secp256k1_fe_verify(&a>z); 92 secp256k1_fe_verify_magnitude(&a>x, 8); 93 secp256k1_fe_verify_magnitude(&a>y, 8); 94 secp256k1_fe_verify_magnitude(&a>z, 8); 95+ secp256k1_fe_verify_magnitude(&a>x, 6); 96+ secp256k1_fe_verify_magnitude(&a>y, 4); 97+ secp256k1_fe_verify_magnitude(&a>z, 2);
realorrandom commented at 1:17 pm on July 11, 2023:I wonder if it’s better to have constants for this. If we change these values here, one needs to change the tests, too, and this is rather easy to miss.
Alternatively (and slightly worse if you ask me), you could add comments here and in the tests that just state that the values need to match these in the other file.
theStack commented at 0:03 am on July 14, 2023:Agree! I’ve introduced #defines SECP256K1_{GE,GEJ}_{X,Y,Z}_MAGNITUDE_MAX in group.h and used that in the following commit, indeed much nicer now. Happy to receive improvement suggestions for the new constants naming and the place where they are defined. 
in src/group_impl.h:1 in 6c3e8e3a0b
realorrandom commented at 1:22 pm on July 11, 2023:The last line here can be removed, it’s covered by the
gej_verify
:(Strictly speaking not this PR, but it’s at least related.)
theStack commented at 0:03 am on July 14, 2023:Done, included the removal of this line in the last commit with a mention in the commit message. 
realorrandom commented at 1:23 pm on July 11, 2023: contributorACK mod nits

realorrandom commented at 10:35 pm on July 11, 2023: contributorI think some of the existing
VERIFY_CHECK
s infield_impl.h
can be replaced by calls tosecp256k1_fe_verify_magnitude
(If that’s desirable but I guess so?) 
theStack forcepushed on Jul 14, 2023

theStack commented at 0:06 am on July 14, 2023: contributor
Forcepushed with most suggestions tackled.
I think some of the existing
VERIFY_CHECK
s infield_impl.h
can be replaced by calls tosecp256k1_fe_verify_magnitude
(If that’s desirable but I guess so?)Added another commit for doing that after the “secp256k1_ge_table_set_globalz” one (203e41b86280d5ea5ed9ab599ddbc21970529601).

Bezzo100lab approved

Bezzo100lab approved

theStack forcepushed on Jul 14, 2023

theStack forcepushed on Jul 15, 2023

in src/field.h:355 in 063e2dba10 outdated
351@@ 352,4 +352,7 @@ static int secp256k1_fe_is_square_var(const secp256k1_fe *a); 352 /** Check invariants on a field element (noop unless VERIFY is enabled). */ 353 static void secp256k1_fe_verify(const secp256k1_fe *a); 354 355+/** Check that magnitude of a ist at most m (noop unless VERIFY is enabled). */
realorrandom commented at 11:35 am on July 21, 2023:s/ist/is ;)
theStack commented at 0:27 am on July 22, 2023:Oops, probably my mind was switching over to german for a moment when I typed this :sweat_smile: Fixed. 
in src/group_impl.h:756 in 78cdcb0c50 outdated
755+ secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2  X2*Z1^2 (8) */ 756 757 secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); 758 secp256k1_fe_cmov(&m_alt, &m, !degenerate); 759+ secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (8) */ 760+ secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (5) */
realorrandom commented at 11:42 am on July 21, 2023:8 instead of 5?
theStack commented at 0:27 am on July 22, 2023:Fixed. 
realorrandom commented at 12:08 pm on July 21, 2023: contributor
Although that could be done in a separate PR, I think this ideally should also remove the restriction to magnitude 31 introduced here: https://github.com/bitcoincore/secp256k1/pull/1344/commits/07c0e8b82e2cea87f85263512945fed7adffea18#diff28d9b92418cbddbe487fe84847993cc5da0b096363c83631a525cff25189752cR104 This is anyway now implied by the new limits.
Possible followup PRs/issues:
 Some (but not all) of the group functions verify their input
fe
s. That doesn’t hurt, but it’s also not necessary because all field functions do that anyway. Anyway, we should either always do it or never.  We should really think about
#ifdef VERIFY
now. It seems that the current convention is to put all new VERIFY_CHECKs in ifdefs. If we do this anyway, then we may as well redefine VERIFY_CHECK to be a noop (and give up on the idea that this macro is “sideeffect safe”. Another consideration is readability the uppercase VERIFY stands out. With more functions likege_verify
, it’s a bit hard to spot them, so maybe we should actually keep the ifdefs. Or rename the functions to fe_VERIFY.
 Some (but not all) of the group functions verify their input

add missing group element invariant checks
The group element checks `secp256k1_{ge,gej}_verify` have first been implemented and added in commit f20266722ac93ca66d1beb0d2f2d2469b95aafea (PR #1299). This commit adds additional verification calls in group functions, to match the ones that were originally proposed in commit 09dbba561fdb9d57a2cc9842ce041d9ba29a6189 of WIPPR #1032 (which is obviously not rebased on #1299 yet). Also, for easier review, all functions handling group elements are structured in the following wasy for easier review (idea suggested by Tim Ruffing):  on entry, verify all input ge, gej (and fe)  empty line  actual function body  empty line  on exit, verify all output ge, gej Coauthoredby: Peter Dettman <peter.dettman@gmail.com> Coauthoredby: Tim Ruffing <crypto@timruffing.de>

Add _fe_verify_magnitude (noop unless VERIFY is enabled)
Coauthoredby: Tim Ruffing <crypto@timruffing.de>

Take use of _fe_verify_magnitude in field_impl.h 49afd2f5d8

Implement current magnitude assumptions
Remove also the explicit magnitude restriction `a>x.magnitude <= 31` in `secp256k1_gej_eq_x_var` (introduced in commit 07c0e8b82e2cea87f85263512945fed7adffea18), as this is implied by the new limits. Coauthoredby: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>

theStack forcepushed on Jul 22, 2023

theStack commented at 1:09 am on July 22, 2023: contributor
Thanks for the review. Forcepushed, removed the <= 31 magnitude check in
secp256k1_gej_eq_x_var
(included in the commit which introduces the tighter group magnitude limits) and also tackled the two other smaller review comments above.Some comments to the followup ideas:
Some (but not all) of the group functions verify their input fes. That doesn’t hurt, but it’s also not necessary because all field functions do that anyway. Anyway, we should either always do it or never.
Any preference between “always” and “never”? Since the checks are not necessary, I would personally prefer “never”, leading to less code, even though the diff would be a bit larger (there are more functions taking fe inputs in group_impl.h that already verify the fe than those that miss the check), but that shouldn’t matter.
As for the
#ifdef VERIFY
subject, what exactly does “sideeffect safe” mean in this context, is the point here to allow sideeffects, and that’s why the expression also needs to be executed in nonverify mode? I fail to see why having sideeffects in checks would ever be useful or generally desirable (quickly glancing overgit grep VERIFY_CHECK
results also didn’t show me any expressions with sideeffects, but maybe I’m missing something), so your proposal of redefining VERIFY_CHECK to a noop in nonverify mode sounds reasonable to me. 
realorrandom approved

realorrandom commented at 6:20 am on July 24, 2023: contributorACK 31bc9a434811d9d2c0a8058c93957c365b39089b

realorrandom commented at 9:14 am on July 24, 2023: contributor
Some (but not all) of the group functions verify their input fes. That doesn’t hurt, but it’s also not necessary because all field functions do that anyway. Anyway, we should either always do it or never.
Any preference between “always” and “never”? Since the checks are not necessary, I would personally prefer “never”, leading to less code, even though the diff would be a bit larger (there are more functions taking fe inputs in group_impl.h that already verify the fe than those that miss the check), but that shouldn’t matter.
I tend to agree. This will also separate concerns more clearly: The field code verifies the field element, the group code verifies the group elements. And if the group code accesses
fe
internals directly (e.g.magnitude
), that should be considered a layer violation (and this PR here will fix this by addingsecp256k1_fe_verify_magnitude
).As for the
#ifdef VERIFY
subject, […]See #1381.

in src/group_impl.h:560 in 31bc9a4348 outdated
558 secp256k1_fe_mul(&u2, &b>x, &z12); 559 s1 = a>y; secp256k1_fe_normalize_weak(&s1); 560+ s1 = a>y; 561 secp256k1_fe_mul(&s2, &b>y, &z12); secp256k1_fe_mul(&s2, &s2, &a>z); 562 secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); 563+ secp256k1_fe_negate(&h, &u1, 6); secp256k1_fe_add(&h, &u2);
jonasnick commented at 12:48 pm on July 24, 2023:Better to replace6
withSECP256K1_GE_X_MAGNITUDE_MAX
? Same for thefe_negate
insecp256k1_gej_add_zinv_var
. 
in src/group.h:53 in 31bc9a4348 outdated
48+ * in affine (x, y) and jacobian (x, y, z) representation. */ 49+#define SECP256K1_GE_X_MAGNITUDE_MAX 6 50+#define SECP256K1_GE_Y_MAGNITUDE_MAX 4 51+#define SECP256K1_GEJ_X_MAGNITUDE_MAX 6 52+#define SECP256K1_GEJ_Y_MAGNITUDE_MAX 4 53+#define SECP256K1_GEJ_Z_MAGNITUDE_MAX 2
jonasnick commented at 12:49 pm on July 24, 2023:How did you arrive at these values? The tightest limits that let the tests pass are
0#define SECP256K1_GE_X_MAGNITUDE_MAX 4 1#define SECP256K1_GE_Y_MAGNITUDE_MAX 3 2#define SECP256K1_GEJ_X_MAGNITUDE_MAX 4 3#define SECP256K1_GEJ_Y_MAGNITUDE_MAX 4 4#define SECP256K1_GEJ_Z_MAGNITUDE_MAX 1
theStack commented at 11:49 pm on July 28, 2023:Good question. I took these limits over from the original PR by @peterdettman (#1032) without further evaluation. Even on that PR, I verified that with the limits (4,3) and (4,4,1) the tests still pass, so no idea where the (6,4)/(6,4,2) limits were originally coming from. (My best guess would be that in the earliest version of the PR, those were the tightest limits where test would pass?!).
peterdettman commented at 2:56 am on July 29, 2023:Good question. I took these limits over from the original PR by @peterdettman (#1032) without further evaluation. Even on that PR, I verified that with the limits (4,3) and (4,4,1) the tests still pass, so no idea where the (6,4)/(6,4,2) limits were originally coming from. (My best guess would be that in the earliest version of the PR, those were the tightest limits where test would pass?!).
There is an inherent tension between tight limits, which might enable optimizations at method entry, and more generous limits, which might enable optimizations at method exit.
The true initial choice of limit was 8, to reflect the tacit assumption throughout the existing group code that it was safe to immediately (i.e. without normalization) mul/sqr any coordinate(s). Abstractly the intention was then to conservatively tighten the limits as necessary to enable specific methodentry optimizations without adding methodexit costs.
The only actual optimization applied was the one in the original PR removing the need to _normalize_weak as part of u1, u2 calculations in group addition. This leads to the choice of 6 for x, y.
My memory fails me as to the choice of 4 for z, but it might make sense that I was contemplating a possible implementation that calculates the output z using the form (a+b)^2  a^2  b^2 (instead of 2.a.b).
peterdettman commented at 10:11 am on July 29, 2023:Oops, not sure why I thought the original PR had z magnitude limit of 4. Anyway the choice was just based on the various extant group formulae at the time.
jonasnick commented at 12:36 pm on July 31, 2023:Thanks @peterdettman. The argument that it’s a tradeoff makes sense. The tighter limits don’t add any methodexit costs though. Did you have any specific change in mind that would introduce methodexit costs when using the tighter limits?
peterdettman commented at 3:07 am on August 1, 2023:I think the introduction of _fe_half is what allowed the z max magnitude to be lowered to 1. We have flirted in the past with formulae that utilize an output z calculation of the form (a+b)^2  a^2  b^2 (where a^2 and b^2 are already used in the formula, so that overall 1M is saved at 1S cost  plus linear ops), which suggests it might like z max mag >= 4, but there’s no strong reason to expect we will move to such formulae.
My main focus was really just getting the limits 8,8(,8) in place and verified. I don’t see any harm in setting the tightest limits that work; future changes contemplating changes to those limits can then be argued casebycase.
realorrandom commented at 12:33 pm on August 1, 2023:I don’t see any harm in setting the tightest limits that work; future changes contemplating changes to those limits can then be argued casebycase.
Agreed. The important thing is that valid limits exist. Which among all valid limits we verify doesn’t matter for correctness, so why not verify the tightest?

in src/group_impl.h:730 in 31bc9a4348 outdated
726@@ 672,17 +727,17 @@ static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp256k1_gej *a, const 727 */ 728 729 secp256k1_fe_sqr(&zz, &a>z); /* z = Z1^2 */ 730 u1 = a>x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */ 731+ u1 = a>x; /* u1 = U1 = X1*Z2^2 (6) */
jonasnick commented at 12:58 pm on July 24, 2023:Do you think it makes sense to express the magnitudes in the in terms of theSECP256K1_GE{,J}_{X,Y,Z}_MAGNITUDE_MAX
constants (both in code and comments)? For the comments it would then make sense to abbreviate these values as, for example,GE{,J}_{X,Y,Z}_M
, etc.
theStack commented at 11:49 pm on July 28, 2023:This sounds like a good idea, as it would avoid the tedious work of adapting the comments if the magnitude limits ever change in the future. On the other hand, the expressions get quite long at the end, e.g.((GEJ_Y_M+3)/2 + 1)
for the last annotation insecp256k1_gej_add_ge
(instructionsecp256k1_fe_half(&r>y);
), not sure if this is still that helpful for the reader in constrast to a concrete magnitude number.
realorrandom commented at 8:20 am on July 29, 2023:I think the version with constants is slightly better. 
realorrandom crossreferenced this on Jul 26, 2023 from issue Add invariant checking for scalars by stratospher

Tighten group magnitude limits
 adjust test methods that randomize magnitudes Coauthoredby: Sebastian Falbesoner <sebastian.falbesoner@gmail.com> Coauthoredby: Jonas Nick <jonasd.nick@gmail.com>

Save _normalize_weak calls in group add methods
Also update the operations count comments in each of the affected functions accordingly and remove a redundant VERIFY_CHECK in secp256k1_gej_add_ge (the infinity value range check [0,1] is already covered by secp256k1_gej_verify above). Coauthoredby: Sebastian Falbesoner <sebastian.falbesoner@gmail.com> Coauthoredby: Tim Ruffing <crypto@timruffing.de> Coauthoredby: Jonas Nick <jonasd.nick@gmail.com>

theStack commented at 11:52 pm on July 28, 2023: contributor
@jonasnick: Thanks for the review! I’ve tried to tackle your suggestions in a separate branch for review of how the proposed changes would look like (https://github.com/theStack/secp256k1/tree/revival_of_1032_magnitude_comments, in particular the last commit https://github.com/theStack/secp256k1/commit/b7c685e74adbd83937990e90f076600fabf8ccf0). This is the rangediff from the current version (which already has one ACK) to the one with tighter limits and magnitude annotations expressed with limit variables (
git rangediff 31bc9...b7c68
):01: d4527d6 ! 1: c83afa6 Tighten group magnitude limits 1 @@ Commit message 2  adjust test methods that randomize magnitudes 3 4 Coauthoredby: Sebastian Falbesoner <sebastian.falbesoner@gmail.com> 5 + Coauthoredby: Jonas Nick <jonasd.nick@gmail.com> 6 7 ## src/group.h ## 8 @@ src/group.h: typedef struct { 9 @@ src/group.h: typedef struct { 10 #define SECP256K1_GEJ_X_MAGNITUDE_MAX 8 11 #define SECP256K1_GEJ_Y_MAGNITUDE_MAX 8 12 #define SECP256K1_GEJ_Z_MAGNITUDE_MAX 8 13 +#define SECP256K1_GE_X_MAGNITUDE_MAX 6 14 +#define SECP256K1_GE_Y_MAGNITUDE_MAX 4 15 +#define SECP256K1_GEJ_X_MAGNITUDE_MAX 6 16 ++#define SECP256K1_GE_X_MAGNITUDE_MAX 4 17 ++#define SECP256K1_GE_Y_MAGNITUDE_MAX 3 18 ++#define SECP256K1_GEJ_X_MAGNITUDE_MAX 4 19 +#define SECP256K1_GEJ_Y_MAGNITUDE_MAX 4 20 +#define SECP256K1_GEJ_Z_MAGNITUDE_MAX 2 21 ++#define SECP256K1_GEJ_Z_MAGNITUDE_MAX 1 22 23 /** Set a group element equal to the point with given X and Y coordinates */ 24 static void secp256k1_ge_set_xy(secp256k1_ge *r, const secp256k1_fe *x, const secp256k1_fe *y); 252: 31bc9a4 ! 2: b7c685e Save _normalize_weak calls in group add methods 26 @@ Commit message 27 28 Coauthoredby: Sebastian Falbesoner <sebastian.falbesoner@gmail.com> 29 Coauthoredby: Tim Ruffing <crypto@timruffing.de> 30 + Coauthoredby: Jonas Nick <jonasd.nick@gmail.com> 31 32 ## src/group_impl.h ## 33 @@ src/group_impl.h: static void secp256k1_gej_add_var(secp256k1_gej *r, const secp256k1_gej *a, cons 34 @@ src/group_impl.h: static void secp256k1_gej_add_ge_var(secp256k1_gej *r, const s 35 + s1 = a>y; 36 secp256k1_fe_mul(&s2, &b>y, &z12); secp256k1_fe_mul(&s2, &s2, &a>z); 37  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); 38 + secp256k1_fe_negate(&h, &u1, 6); secp256k1_fe_add(&h, &u2); 39 ++ secp256k1_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); secp256k1_fe_add(&h, &u2); 40 secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1); 41 if (secp256k1_fe_normalizes_to_zero_var(&h)) { 42 if (secp256k1_fe_normalizes_to_zero_var(&i)) { 43 @@ src/group_impl.h: static void secp256k1_gej_add_zinv_var(secp256k1_gej *r, const 44 + s1 = a>y; 45 secp256k1_fe_mul(&s2, &b>y, &z12); secp256k1_fe_mul(&s2, &s2, &az); 46  secp256k1_fe_negate(&h, &u1, 1); secp256k1_fe_add(&h, &u2); 47 + secp256k1_fe_negate(&h, &u1, 6); secp256k1_fe_add(&h, &u2); 48 ++ secp256k1_fe_negate(&h, &u1, SECP256K1_GEJ_X_MAGNITUDE_MAX); secp256k1_fe_add(&h, &u2); 49 secp256k1_fe_negate(&i, &s2, 1); secp256k1_fe_add(&i, &s1); 50 if (secp256k1_fe_normalizes_to_zero_var(&h)) { 51 if (secp256k1_fe_normalizes_to_zero_var(&i)) { 52 @@ src/group_impl.h: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp2 53 54 secp256k1_fe_sqr(&zz, &a>z); /* z = Z1^2 */ 55  u1 = a>x; secp256k1_fe_normalize_weak(&u1); /* u1 = U1 = X1*Z2^2 (1) */ 56 + u1 = a>x; /* u1 = U1 = X1*Z2^2 (6) */ 57 ++ u1 = a>x; /* u1 = U1 = X1*Z2^2 (GEJ_X_M) */ 58 secp256k1_fe_mul(&u2, &b>x, &zz); /* u2 = U2 = X2*Z1^2 (1) */ 59  s1 = a>y; secp256k1_fe_normalize_weak(&s1); /* s1 = S1 = Y1*Z2^3 (1) */ 60 + s1 = a>y; /* s1 = S1 = Y1*Z2^3 (4) */ 61 ++ s1 = a>y; /* s1 = S1 = Y1*Z2^3 (GEJ_Y_M) */ 62 secp256k1_fe_mul(&s2, &b>y, &zz); /* s2 = Y2*Z1^2 (1) */ 63 secp256k1_fe_mul(&s2, &s2, &a>z); /* s2 = S2 = Y2*Z1^3 (1) */ 64  t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (2) */ 65  m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (2) */ 66 + t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (7) */ 67 + m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (5) */ 68 ++ t = u1; secp256k1_fe_add(&t, &u2); /* t = T = U1+U2 (GEJ_X_M+1) */ 69 ++ m = s1; secp256k1_fe_add(&m, &s2); /* m = M = S1+S2 (GEJ_Y_M+1) */ 70 secp256k1_fe_sqr(&rr, &t); /* rr = T^2 (1) */ 71  secp256k1_fe_negate(&m_alt, &u2, 1); /* Malt = X2*Z1^2 */ 72  secp256k1_fe_mul(&tt, &u1, &m_alt); /* tt = U1*U2 (2) */ 73 @@ src/group_impl.h: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp2 74 rr_alt = s1; 75  secp256k1_fe_mul_int(&rr_alt, 2); /* rr = Y1*Z2^3  Y2*Z1^3 (2) */ 76  secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2  X2*Z1^2 */ 77 + secp256k1_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3  Y2*Z1^3 (8) */ 78 + secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2  X2*Z1^2 (8) */ 79 ++ secp256k1_fe_mul_int(&rr_alt, 2); /* rr_alt = Y1*Z2^3  Y2*Z1^3 (GEJ_Y_M*2) */ 80 ++ secp256k1_fe_add(&m_alt, &u1); /* Malt = X1*Z2^2  X2*Z1^2 (GEJ_X_M+2) */ 81 82  secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); 83  secp256k1_fe_cmov(&m_alt, &m, !degenerate); 84 + secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (8) */ 85 + secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (8) */ 86 ++ secp256k1_fe_cmov(&rr_alt, &rr, !degenerate); /* rr_alt (GEJ_Y_M*2) */ 87 ++ secp256k1_fe_cmov(&m_alt, &m, !degenerate); /* m_alt (GEJ_X_M+2) */ 88 /* Now Ralt / Malt = lambda and is guaranteed not to be Ralt / 0. 89 * From here on out Ralt and Malt represent the numerator 90 * and denominator of lambda; R and M represent the explicit 91 * expressions x1^2 + x2^2 + x1x2 and y1 + y2. */ 92 secp256k1_fe_sqr(&n, &m_alt); /* n = Malt^2 (1) */ 93  secp256k1_fe_negate(&q, &t, 2); /* q = T (3) */ 94 + secp256k1_fe_negate(&q, &t, 7); /* q = T (8) */ 95 ++ secp256k1_fe_negate(&q, &t, 96 ++ SECP256K1_GEJ_X_MAGNITUDE_MAX + 1); /* q = T (GEJ_X_M+2) */ 97 secp256k1_fe_mul(&q, &q, &n); /* q = Q = T*Malt^2 (1) */ 98 /* These two lines use the observation that either M == Malt or M == 0, 99 * so M^3 * Malt is either Malt^4 (which is computed by squaring), or 100 @@ src/group_impl.h: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp2 101  secp256k1_fe_sqr(&n, &n); 102  secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (2) */ 103 + secp256k1_fe_sqr(&n, &n); /* n = Malt^4 (1) */ 104 + secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (5) */ 105 ++ secp256k1_fe_cmov(&n, &m, degenerate); /* n = M^3 * Malt (GEJ_Y_M+1) */ 106 secp256k1_fe_sqr(&t, &rr_alt); /* t = Ralt^2 (1) */ 107 secp256k1_fe_mul(&r>z, &a>z, &m_alt); /* r>z = Z3 = Malt*Z (1) */ 108 secp256k1_fe_add(&t, &q); /* t = Ralt^2 + Q (2) */ 109 @@ src/group_impl.h: static void secp256k1_gej_add_ge(secp256k1_gej *r, const secp2 110  secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (3) */ 111  secp256k1_fe_negate(&r>y, &t, 3); /* r>y = (Ralt*(2*X3 + Q) + M^3*Malt) (4) */ 112  secp256k1_fe_half(&r>y); /* r>y = Y3 = (Ralt*(2*X3 + Q) + M^3*Malt)/2 (3) */ 113 + secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (6) */ 114 + secp256k1_fe_negate(&r>y, &t, 6); /* r>y = (Ralt*(2*X3 + Q) + M^3*Malt) (7) */ 115 + secp256k1_fe_half(&r>y); /* r>y = Y3 = (Ralt*(2*X3 + Q) + M^3*Malt)/2 (4) */ 116 ++ secp256k1_fe_add(&t, &n); /* t = Ralt*(2*X3 + Q) + M^3*Malt (GEJ_Y_M+2) */ 117 ++ secp256k1_fe_negate(&r>y, &t, 118 ++ SECP256K1_GEJ_Y_MAGNITUDE_MAX + 2); /* r>y = (Ralt*(2*X3 + Q) + M^3*Malt) (GEJ_Y_M+3) */ 119 ++ secp256k1_fe_half(&r>y); /* r>y = Y3 = (Ralt*(2*X3 + Q) + M^3*Malt)/2 ((GEJ_Y_M+3)/2 + 1) */ 120 121 /* In case a>infinity == 1, replace r with (b>x, b>y, 1). */ 122 secp256k1_fe_cmov(&r>x, &b>x, a>infinity);
Any opinions on what of those changes should be adapted? On one hand I think it’s nice to express the magnitudes in a generic way in the comments, on the other hand it probably causes more confusion and is not that helpful (especially for longer expressions). Also, is there any drawback in tightening the limits too much, e.g. increased risk that they have to be lifted again soon, causing extra work? Happy to receive input and change the PR either way.

jonasnick commented at 12:36 pm on July 31, 2023: contributor@theStack I slightly prefer this variant and I don’t think the resulting expressions are particularly confusing. For the code it makes more sense to use the
SECP256K1_GE{,J}_{X,Y,Z}_MAGNITUDE_MAX
constants instead of magic numbers. And then it’s easier to follow the comments if they use the same constants. 
theStack forcepushed on Jul 31, 2023

theStack commented at 11:53 pm on July 31, 2023: contributorForcepushed the prepared variant which uses the magnitude limit constants both in the code and in the comments. Right now the tightest limits that still pass the tests are set ((4,3) for ge, (4,4,1) for gej), but this can be changed easily if there are concerns raised and more relaxed limits would be preferred (following the open discussion at #1348 (review)).

realorrandom approved

realorrandom commented at 12:33 pm on August 1, 2023: contributorACK b7c685e74adbd83937990e90f076600fabf8ccf0

jonasnick commented at 9:33 am on August 3, 2023: contributorACK b7c685e74adbd83937990e90f076600fabf8ccf0

theStack crossreferenced this on Aug 4, 2023 from issue Implement new policy for VERIFY_CHECK and #ifdef VERIFY (issue #1381) by theStack

realorrandom commented at 4:47 pm on August 7, 2023: contributor@sipa Want to rereview this? If no, I think it’s also ready for merge without another ACK.

sipa commented at 7:03 pm on August 15, 2023: contributorutACK b7c685e74adbd83937990e90f076600fabf8ccf0

realorrandom merged this on Aug 16, 2023

realorrandom closed this on Aug 16, 2023

theStack deleted the branch on Aug 16, 2023