tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032)

theStack commented at 2:12 pm on June 15, 2023: contributor

This 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 (easy-to-solve) conflicts appeared through cherry-picking. The last commit which actually removes the normalize_weak calls is obviously the critical one and needs the most attention for review.

theStack force-pushed on Jun 27, 2023

theStack commented at 10:18 pm on June 27, 2023: contributor

Rebased 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 and secp256k1_gej_add_ge) in the last commit.

real-or-random added the label assurance on Jun 27, 2023

real-or-random added the label performance on Jun 27, 2023

real-or-random cross-referenced this on Jul 3, 2023 from issue WIP Group verification by peterdettman

real-or-random cross-referenced 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 (no-op unless VERIFY is enabled). */
353 static void secp256k1_fe_verify(const secp256k1_fe *a);
354 
355+#ifdef VERIFY
356+
357+/** Assert a context-specific 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, 0-32 inclusive (since #1066). That also means the implementation of this secp256k1_fe_verify_magnitude can be in field_impl.h rather than in the representation-specific files.

theStack commented at 11:08 pm on July 10, 2023:

Moved secp256k1_fe_verify_magnitude to a (single) implementation in field_impl.h, also removed the VERIFY pre-processor condition from field.h and add a no-op implementation for the case that VERIFY isn’t set instead (even though the no-op case isn’t currently used, it seems to be more consistent to _fe_verify that way).

theStack force-pushed 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]);

real-or-random 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 follow-up material?)

real-or-random 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 follow-up 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 of i for the backwards loop is now done later, due to i 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 for i in the case of len == 0 (even though that’s more theoretical, in practice no-one would call that function with a zero-length 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 (no-op unless VERIFY is enabled). */
353 static void secp256k1_fe_verify(const secp256k1_fe *a);
354 
355+/** Assert a context-specific limit m on the magnitude of a, where
356+ *  m must be in the supported range [0,32] (no-op unless VERIFY is enabled). */
357+static void secp256k1_fe_verify_magnitude(const secp256k1_fe *a, int m);

real-or-random 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 ;))
“context-specific” 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);

real-or-random 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

real-or-random commented at 1:22 pm on July 11, 2023:

The last line here can be removed, it’s covered by the gej_verify:

https://github.com/theStack/secp256k1/blob/6c3e8e3a0b834c989851defbc10fe3c8e4901c8c/src/group_impl.h#L628-L636

(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.

real-or-random commented at 1:23 pm on July 11, 2023: contributor

ACK mod nits

real-or-random commented at 10:35 pm on July 11, 2023: contributor

I think some of the existing VERIFY_CHECKs in field_impl.h can be replaced by calls to secp256k1_fe_verify_magnitude (If that’s desirable but I guess so?)

theStack force-pushed on Jul 14, 2023

theStack commented at 0:06 am on July 14, 2023: contributor

Force-pushed with most suggestions tackled.

I think some of the existing VERIFY_CHECKs in field_impl.h can be replaced by calls to secp256k1_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).

Bezzo100-lab approved

theStack force-pushed on Jul 14, 2023

theStack force-pushed 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 (no-op 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 (no-op unless VERIFY is enabled). */

real-or-random 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) */

real-or-random commented at 11:42 am on July 21, 2023:

8 instead of 5?

theStack commented at 0:27 am on July 22, 2023:

Fixed.

real-or-random 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/bitcoin-core/secp256k1/pull/1344/commits/07c0e8b82e2cea87f85263512945fed7adffea18#diff-28d9b92418cbddbe487fe84847993cc5da0b096363c83631a525cff25189752cR104 This is anyway now implied by the new limits.

Possible follow-up PRs/issues:

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.
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 “side-effect safe”. Another consideration is readability the uppercase VERIFY stands out. With more functions like ge_verify, it’s a bit hard to spot them, so maybe we should actually keep the ifdefs. Or rename the functions to fe_VERIFY.

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 WIP-PR #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

Co-authored-by: Peter Dettman <peter.dettman@gmail.com>
Co-authored-by: Tim Ruffing <crypto@timruffing.de>

690b0fc05a

Add _fe_verify_magnitude (no-op unless VERIFY is enabled)

Co-authored-by: Tim Ruffing <crypto@timruffing.de>

4e9661fc42

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.

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>

173e8d061a

theStack force-pushed on Jul 22, 2023

theStack commented at 1:09 am on July 22, 2023: contributor

Thanks for the review. Force-pushed, 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 follow-up 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 “side-effect safe” mean in this context, is the point here to allow side-effects, and that’s why the expression also needs to be executed in non-verify mode? I fail to see why having side-effects in checks would ever be useful or generally desirable (quickly glancing over git grep VERIFY_CHECK results also didn’t show me any expressions with side-effects, but maybe I’m missing something), so your proposal of redefining VERIFY_CHECK to a no-op in non-verify mode sounds reasonable to me.

real-or-random approved

real-or-random commented at 6:20 am on July 24, 2023: contributor

ACK 31bc9a434811d9d2c0a8058c93957c365b39089b

real-or-random 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 adding secp256k1_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 replace 6 with SECP256K1_GE_X_MAGNITUDE_MAX? Same for the fe_negate in secp256k1_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 method-entry optimizations without adding method-exit 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 trade-off makes sense. The tighter limits don’t add any method-exit costs though. Did you have any specific change in mind that would introduce method-exit 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 case-by-case.

real-or-random 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 case-by-case.

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 the SECP256K1_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 in secp256k1_gej_add_ge (instruction secp256k1_fe_half(&r->y);), not sure if this is still that helpful for the reader in constrast to a concrete magnitude number.

real-or-random commented at 8:20 am on July 29, 2023:

I think the version with constants is slightly better.

real-or-random cross-referenced this on Jul 26, 2023 from issue Add invariant checking for scalars by stratospher

Tighten group magnitude limits

- adjust test methods that randomize magnitudes

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
Co-authored-by: Jonas Nick <jonasd.nick@gmail.com>

c83afa66e0

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).

Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
Co-authored-by: Tim Ruffing <crypto@timruffing.de>
Co-authored-by: Jonas Nick <jonasd.nick@gmail.com>

b7c685e74a

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 range-diff from the current version (which already has one ACK) to the one with tighter limits and magnitude annotations expressed with limit variables (git range-diff 31bc9...b7c68):

  01:  d4527d6 ! 1:  c83afa6 Tighten group magnitude limits
  1    @@ Commit message
  2         - adjust test methods that randomize magnitudes
  3     
  4         Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
  5    +    Co-authored-by: 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         Co-authored-by: Sebastian Falbesoner <sebastian.falbesoner@gmail.com>
 29         Co-authored-by: Tim Ruffing <crypto@timruffing.de>
 30    +    Co-authored-by: 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 force-pushed on Jul 31, 2023

theStack commented at 11:53 pm on July 31, 2023: contributor

Force-pushed 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)).

real-or-random approved

real-or-random commented at 12:33 pm on August 1, 2023: contributor

ACK b7c685e74adbd83937990e90f076600fabf8ccf0

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

ACK b7c685e74adbd83937990e90f076600fabf8ccf0

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

real-or-random commented at 4:47 pm on August 7, 2023: contributor

@sipa Want to re-review this? If no, I think it’s also ready for merge without another ACK.

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

utACK b7c685e74adbd83937990e90f076600fabf8ccf0

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

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

theStack deleted the branch on Aug 16, 2023

tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) #1348