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

pull sipa wants to merge 29 commits into bitcoin-core:master from sipa:202201_uniform_fe_rules changing 6 files +665 −523
  1. sipa commented at 0:41 am on January 29, 2022: contributor

    Right now, all the logic for propagating/computing the magnitude/normalized fields in secp256k1_fe (when VERIFY is defined) and the code for checking it, is duplicated across the two field implementations. I believe that is undesirable, as these properties should purely be a function of the performed fe_ functions, and not of the choice of field implementation. This becomes even uglier with #967, which would copy all that, and even needs an additional dimension that would then need to be added to the two other fields. It’s also related to #1001, which I think will become easier if it doesn’t need to be done/reasoned about separately for every field.

    This PR moves all logic around these fields (collectively called field verification) to implementations in field_impl.h, which dispatch to renamed functions in field_*_impl.h for the actual implementation.

    Fixes #1060.

  2. in src/field_10x26.h:24 in cda9763adb outdated 
    23-#endif
24+    /*
25+     * Magnitude m implies n[i] <= 2*m*0x3FFFFFF for i=0..8, and
26+     * n[9] <= 2*m*0x3FFFFF (a factor 16 smaller).
27+     *
28+     * Normalized requires magnitude 1, all n[i] <= 0x3FFFFFF, and
    jonasnick commented at 10:48 pm on January 30, 2022:
    “requires magnitude <= 1”?
    sipa commented at 3:24 pm on February 1, 2022:
    This has been changed significantly; the rule that normalized implies magnitude 0 or 1 has now been added to field.h itself (it’s in fact a rule that must hold for all users of field.h, independent of which field implementation was used).
  3. in src/field_10x26.h:22 in cda9763adb outdated 
    21-    int magnitude;
22-    int normalized;
23-#endif
24+    /*
25+     * Magnitude m implies n[i] <= 2*m*0x3FFFFFF for i=0..8, and
26+     * n[9] <= 2*m*0x3FFFFF (a factor 16 smaller).
    jonasnick commented at 10:53 pm on January 30, 2022:
    nit: that wording sounds to me like 0x3FFFFF*16 = 0x3FFFFFF but that’s false.
    robot-dreams commented at 7:38 pm on January 31, 2022:

    Maybe something like this then (similarly for field_5x52.h below)?

    0    /*
1     * Magnitude m implies:
2     *     n[i] <= 2*m*0x3FFFFFF for i=0..8
3     *     n[9] <= 2*m*0x03FFFFF
4     *
5     * Normalized requires:
6     *     magnitude 0 or 1
7     *     all n[i] <= 0x3FFFFFF
8     *     sum(i=0..9, n[i]*2^(i*26)) < p
9     */
    sipa commented at 3:42 pm on February 1, 2022:
    Done something like this (and now also placed it in the right file).
  4. jonasnick commented at 10:56 pm on January 30, 2022: contributor
    PR looks good to me otherwise. Net negative diff :tada:
  5. in src/field_10x26_impl.h:421 in 7716a96507 outdated 
    330@@ -331,15 +331,7 @@ static void secp256k1_fe_impl_get_b32(unsigned char *r, const secp256k1_fe *a) {
331     r[31] = a->n[0] & 0xff;
332 }
333 
334-SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
335-#ifdef VERIFY
336-    VERIFY_CHECK(a->magnitude <= m);
337-    secp256k1_fe_verify(a);
338-    VERIFY_CHECK(0x3FFFC2FUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
    robot-dreams commented at 7:51 pm on January 31, 2022:
    Why remove these (they came from #816 which was recently merged)?
    robot-dreams commented at 3:15 am on February 1, 2022:
    Oh, I guess you no longer need these now that you have secp256k1_fe_verify(a) together with a->magnitude <= m <= 31?
    sipa commented at 3:47 pm on February 1, 2022:
    I’ve reinstituted them; they’re certainly implied, but still clarify why the logic below is legal.
  6. in src/field_10x26_impl.h:1331 in a746648ab8 outdated 
    1093     const uint32_t M30 = UINT32_MAX >> 2;
1094     const uint64_t a0 = a->n[0], a1 = a->n[1], a2 = a->n[2], a3 = a->n[3], a4 = a->n[4],
1095                    a5 = a->n[5], a6 = a->n[6], a7 = a->n[7], a8 = a->n[8], a9 = a->n[9];
1096 
1097-#ifdef VERIFY
1098-    VERIFY_CHECK(a->normalized);
    robot-dreams commented at 8:05 pm on January 31, 2022:
    (No action needed) I agree this can be removed because fe_to_signed30 is static and only ever called after fe_normalize{_var}; similarly with fe_to_signed62 below.
    sipa commented at 3:49 pm on February 1, 2022:
    So just to explain what’s going on here: what this PR does is move the responsibility for checking that inputs/outpts to the field implementation’s code satisfy the normalized/magnitude rules to field.h and field_impl.h. That’s why I removed it here, because whatever rules we want to hold should apply for all fields, not just this specific one. And this to_signed30 and from_signed30 functions are internal implementation details.
  7. in src/field_impl.h:380 in a746648ab8 outdated 
    356+    int input_is_zero = secp256k1_fe_normalizes_to_zero(x);
357+#endif
358+    secp256k1_fe_impl_inv_var(r, x);
359+#ifdef VERIFY
360+    VERIFY_CHECK(secp256k1_fe_normalizes_to_zero(r) == input_is_zero);
361+    r->magnitude = x->magnitude > 0;
    robot-dreams commented at 8:15 pm on January 31, 2022:
    Before this PR, how could r->magnitude have ended up as 0?
    sipa commented at 11:43 pm on January 31, 2022:
    It couldn’t; the new logic is slightly more precise.
    robot-dreams commented at 3:30 am on February 1, 2022:
    Makes sense now, I didn’t realize before that secp256k1_fe_impl_inv{_var} returns zero if the input was zero.
  8. robot-dreams commented at 8:25 pm on January 31, 2022: contributor

    Concept ACK

    The process you used (rename fe_ to fe_impl, move verification into new fe_ functions in field_impl.h) makes sense.

    I don’t see any other relevant #ifdef VERIFY in field_10x26_impl.h or field_5x52_impl.h so it seems like you covered everything.

    I just have a few clarifying questions, and then I want to do one final pass (maybe there’s (1) some easy semi-automated way to check/reproduce the changes or (2) some more macros that can make field_impl.h shorter).

  9. sipa force-pushed on Jan 31, 2022
  10. sipa commented at 11:40 pm on January 31, 2022: contributor
    Made some significant changes here, and addressed some of the comments.
  11. in src/field.h:29 in 8df6f75165 outdated 
    35+ * - magnitude: an integer in [0,32]
36+ * - normalized: 0 or 1; normalized=1 implies magnitude <= 1.
37+ *
38+ * In VERIFY mode, they are materialzed explicitly as fields in the struct,
39+ * allowing run-time verification of these properties. In that case, the
40+ * field implementation also provides a secp256k1_fe_check routine to
    robot-dreams commented at 1:23 am on February 1, 2022: 
    0 * field implementation also provides a secp256k1_fe_verify routine to
    sipa commented at 3:50 pm on February 1, 2022:
    Done.
  12. in src/tests.c:6736 in 8df6f75165 outdated 
    6732@@ -6733,7 +6733,7 @@ void fe_cmov_test(void) {
6733     static const secp256k1_fe one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
6734     static const secp256k1_fe max = SECP256K1_FE_CONST(
6735         0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL,
6736-        0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFFUL
6737+        0xFFFFFFFFUL, 0xFFFFFFFFUL, 0xFFFFFFFEUL, 0xFFFFFC2EUL
    robot-dreams commented at 1:30 am on February 1, 2022:
    Why only change this test (a few more below still use 2^256 - 1)?
    sipa commented at 4:45 pm on February 1, 2022:
    I’ve instead added a commit that actually sets the magnitude/normalized fields correctly for SECP256K1_FE_CONST, instead of assuming “,1,1”.
  13. in src/field_impl.h:165 in 9461ee29dc outdated 
    144+    /* Normalized is 0 or 1. */
145+    r &= (a->normalized == 0) | (a->normalized == 1);
146+    /* If normalized, magnitude must be 0 or 1. */
147+    if (a->normalized) r &= (a->magnitude <= 1);
148+    VERIFY_CHECK(r == 1);
149+    /* Invoke field specific checks. */
    robot-dreams commented at 1:38 am on February 1, 2022: 
    0    /* Invoke implementation-specific checks. */
    sipa commented at 4:46 pm on February 1, 2022:
    Fixed.
  14. in src/field.h:32 in 9461ee29dc outdated 
    33+ * the field representation values depends on the chosen field implementation.
34+ * See the field_*.h files included below for details. They are:
35+ * - magnitude: an integer in [0,32]
36+ * - normalized: 0 or 1; normalized=1 implies magnitude <= 1.
37+ *
38+ * In VERIFY mode, they are materialzed explicitly as fields in the struct,
    robot-dreams commented at 1:40 am on February 1, 2022: 
    0 * In VERIFY mode, they are materialized explicitly as fields in the struct,
    sipa commented at 4:47 pm on February 1, 2022:
    Done.
  15. in src/field.h:31 in 9461ee29dc outdated 
    37+ *
38+ * In VERIFY mode, they are materialzed explicitly as fields in the struct,
39+ * allowing run-time verification of these properties. In that case, the
40+ * field implementation also provides a secp256k1_fe_check routine to
41+ * verify that these fields match the run-time value and internal consistency
42+ * checks. */
    robot-dreams commented at 1:42 am on February 1, 2022: 
    0 * verify that these fields match the run-time value and perform internal
1 * consistency checks. */
    sipa commented at 4:48 pm on February 1, 2022:
    Done (in next push).
  16. in src/field_5x52.h:32 in 9461ee29dc outdated 
    29+     *
30+     * Normalized requires:
31+     *     n[i] <= (2^26 - 1) for i=0..8
32+     *     sum(i=0..9, n[i] << (i*26)) < p
33+     *     (together these imply n[9] <= 2^22 - 1)
34+     */
    robot-dreams commented at 2:01 am on February 1, 2022:
    Did you swap the comments for 5x52 and 10x26?
    sipa commented at 4:48 pm on February 1, 2022:
    I did. Fixed.
  17. in src/field.h:109 in 663a73d8a6 outdated 
    65-/** Normalize a field element. This brings the field element to a canonical representation, reduces
66- *  its magnitude to 1, and reduces it modulo field size `p`.
67+/** Normalize a field element.
68+ *
69+ * On input, r must be a valid field element.
70+ * On output, r represents the same value but has normalized=1 and magnitude=1.
    robot-dreams commented at 2:06 am on February 1, 2022: 
    0 * On output, r represents the same value but has normalized=1 and magnitude=1,
1 * and is reduced modulo the field size `p`.
    sipa commented at 4:51 pm on February 1, 2022:

    So what I’m trying to do in this PR is define a generic interface for field elements, which has well-defined and verified rules at the field layer, independent of the implementation.

    Field elements don’t have an observable notion of “reduced modulo” - they are elements of the field GF(2^256 - 2^32 - 977). Reducing is a concept that only appears if you’re representing those field elements as integers - which is what the field implementations do.

    So what’s happening here is that the interface only says “makes the field element have the normalized property”. What “normalized” entails for the representation is up to the specific field implementation (where you’ll find a comment that the sum of the limbs has to be below p).

    I’ve tried to add a few more comments to explain this, but suggestions welcome if you think it isn’t clear from the text yet.

  18. in src/field.h:124 in 2cbafa18f0 outdated 
    85@@ -84,11 +86,17 @@ static void secp256k1_fe_normalize_weak(secp256k1_fe *r);
86  */
87 static void secp256k1_fe_normalize_var(secp256k1_fe *r);
88 
89-/** Verify whether a field element represents zero i.e. would normalize to a zero value. */
90+/** Determine whether r represents value 0.
    robot-dreams commented at 2:13 am on February 1, 2022: 
    0/** Determine whether r represents field element 0.
    sipa commented at 4:54 pm on February 1, 2022:
    Done (here and further) in the next push.
  19. in src/field.h:154 in a3e03ddce0 outdated 
    115@@ -115,7 +116,14 @@ static void secp256k1_fe_set_int(secp256k1_fe *r, int a);
116  */
117 static void secp256k1_fe_clear(secp256k1_fe *a);
118 
119-/** Verify whether a field element is zero. Requires the input to be normalized. */
120+/** Determine whether a represents value 0.
121+ *
122+ * On input a must be a valid normalized field element.
123+ * Returns whether a  = 0 (mod p).
    robot-dreams commented at 2:18 am on February 1, 2022: 
    0 * Returns whether a = 0 (mod p).
    sipa commented at 4:55 pm on February 1, 2022:
    Done in next push.
  20. in src/field.h:182 in afe66236b6 outdated 
    148@@ -148,7 +149,13 @@ static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b);
149  */
150 static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b);
151 
152-/** Compare two field elements. Requires both inputs to be normalized */
153+/** Compare the values represented by 2 field elements.
    robot-dreams commented at 2:23 am on February 1, 2022: 
    0/** Compare the values represented by 2 field elements, ​without constant-time guarantee.
    sipa commented at 4:57 pm on February 1, 2022:
    Done in next push.
  21. in src/field.h:222 in 6cf718569f outdated 
    193+/** Multiply a field element with a small integer.
194+ *
195+ * On input, r must be a valid field element. a must be an integer in [0,32].
196+ * The magnitude of r times a must not exceed 32.
197+ * Performs {r *= a}.
198+ * On output, r's magnitude is multiplied by a.
    robot-dreams commented at 2:30 am on February 1, 2022: 
    0 * On output, r's magnitude is multiplied by a and normalized is cleared.
    sipa commented at 5:00 pm on February 1, 2022:
    Done in next push.
  22. in src/field_impl.h:297 in 6cf718569f outdated 
    271+    secp256k1_fe_verify(r);
272+    VERIFY_CHECK(a >= 0 && a <= 32);
273+    VERIFY_CHECK(a*r->magnitude <= 32);
274+    secp256k1_fe_impl_mul_int(r, a);
275+    r->magnitude *= a;
276+    r->normalized = 0;
    robot-dreams commented at 2:30 am on February 1, 2022:
    (Not this PR) Should normalized only be cleared if a > 1?
    sipa commented at 5:00 pm on February 1, 2022:
    I’d instead rather add an VERIFY_CHECK(a > 1), because using this function with a=0 or a=1 is dumb.
    real-or-random commented at 8:40 am on May 11, 2023:

    I think it’s fine. Making normalization depend on the value may be a step into the wrong direction (it makes magnitude less static, though the int argument probably doesn’t matter.)

    And I don’t see a good reason to VERIFY_CHECK the input. a may be determined at run time. For example, we currently call this with 0 (determined at run time) in the tests. If you want to add the VERIFY_CHECK, you’d need to adjust random_field_element_magnitude.

  23. in src/field.h:229 in ec4b3d70ea outdated 
    197@@ -197,7 +198,13 @@ static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m);
198  */
199 static void secp256k1_fe_mul_int(secp256k1_fe *r, int a);
200 
201-/** Adds a field element to another. The result has the sum of the inputs' magnitudes as magnitude. */
202+/** Increment a field element by another.
203+ *
204+ * On input, r and a must be valid field elements. The sum of their magnitudes
205+ * may not exceed 32.
    robot-dreams commented at 2:32 am on February 1, 2022: 
    0 * On input, r and a must be valid field elements, not necessarily normalized.
1 * The sum of their magnitudes may not exceed 32.
    sipa commented at 5:02 pm on February 1, 2022:
    Done in next push.
  24. in src/field.h:266 in 8df6f75165 outdated 
    241@@ -240,11 +242,18 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
242  */
243 static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a);
244 
245-/** Sets a field element to be the (modular) inverse of another. Requires the input's magnitude to be
246- *  at most 8. The output magnitude is 1 (but not guaranteed to be normalized). */
247+/** Compute the modular inverse of a field element.
248+ *
249+ * On input, a must be a valid field element; r need not be initialized.
250+ * Performs {r = 1/a}.
    robot-dreams commented at 3:06 am on February 1, 2022: 
    0 * Performs {r = 1/a} if a is nonzero, {r = 0} otherwise.
    sipa commented at 5:07 pm on February 1, 2022:
    Doing something like this in the next push.
  25. robot-dreams commented at 3:34 am on February 1, 2022: contributor
    New approach makes a lot of sense and commits are very well structured. Looks good overall, I just have a few cosmetic comments (feel free not to apply all of them).
  26. real-or-random commented at 12:16 pm on February 1, 2022: contributor

    Concept ACK

    But is there you reason why you prefer to do this before #1001? (@peterdettman and I argued to in #1060 that it may make sense to solve #1001.)

    I haven’t looked at the details here but I think this will non-trivially conflict with #1062. @sipa can you have a look and suggest how we should move forward?

  27. sipa force-pushed on Feb 1, 2022
  28. sipa force-pushed on Feb 1, 2022
  29. sipa force-pushed on Feb 1, 2022
  30. sipa force-pushed on Feb 1, 2022
  31. sipa commented at 5:12 pm on February 1, 2022: contributor

    @real-or-random

    But is there you reason why you prefer to do this before #1001? (@peterdettman and I argued to in #1060 that it may make sense to solve #1001.)

    The impetus for this is really that I want to bring #967 up-to-date and more production-ready, and doing it properly I think would be very unclear without a change like this (having details from the “old” fields leak into the verify checks of the new one etc).

    I’ll comment in #1060, but I think this PR makes it at least obvious in what places norm/mag are not compile-time constants.

    I haven’t looked at the details here but I think this will non-trivially conflict with #1062. @sipa can you have a look and suggest how we should move forward?

    It will. That’s one of the reasons why I kept the changes for each function in separate commits. So I’m happy to rebase this after #1062, or otherwise incorporate the commits here.

  32. sipa cross-referenced this on Feb 1, 2022 from issue Make fe magnitude implied statically by real-or-random
  33. sipa cross-referenced this on Feb 1, 2022 from issue Document field functions assumptions and validate it using magnitude and `fe_verify` checks by siv2r
  34. sipa force-pushed on Jun 8, 2022
  35. sipa commented at 7:05 pm on June 8, 2022: contributor
    Rebased.
  36. sipa force-pushed on Jun 8, 2022
  37. sipa force-pushed on Nov 17, 2022
  38. sipa commented at 4:31 pm on November 17, 2022: contributor
    Rebased, adding an abstraction for secp256k1_fe_half.
  39. sipa force-pushed on Jan 5, 2023
  40. sipa commented at 9:16 pm on January 5, 2023: contributor
    Rebased after merge of #1178.
  41. sipa force-pushed on May 11, 2023
  42. sipa commented at 7:30 am on May 11, 2023: contributor
    Rebased after #1299, #1217, #979.
  43. sipa force-pushed on May 11, 2023
  44. sipa force-pushed on May 11, 2023
  45. in src/field.h:98 in dd5ca02bb4 outdated 
     95+#  define secp256k1_fe_inv_var secp256k1_fe_impl_inv_var
 96+#  define secp256k1_fe_get_bounds secp256k1_fe_impl_get_bounds
 97+#  define secp256k1_fe_half secp256k1_fe_impl_half
 98+#  define secp256k1_fe_add_int secp256k1_fe_impl_add_int
 99+#  define secp256k1_fe_is_square_var secp256k1_fe_impl_is_square_var
100+#endif /* defined(VERIFY) */
    real-or-random commented at 7:54 am on May 11, 2023: 
    0#endif /* !defined(VERIFY) */
    sipa commented at 9:05 am on May 11, 2023:
    Done. That was painful.
  46. in src/field_impl.h:145 in 0cdba2cd1f outdated 
    140+    /* Magnitude between 0 and 32. */
141+    int r = (a->magnitude >= 0) & (a->magnitude <= 32);
142+    /* Normalized is 0 or 1. */
143+    r &= (a->normalized == 0) | (a->normalized == 1);
144+    /* If normalized, magnitude must be 0 or 1. */
145+    if (a->normalized) r &= (a->magnitude <= 1);
    real-or-random commented at 8:08 am on May 11, 2023:

    nit: Maybe make those individual VERIFY_CHECKs. That’s better for debugging because then the error message will show you which line failed.

    same is true for both instances of secp256k1_fe_impl_verify

    sipa commented at 9:05 am on May 11, 2023:
    Done, in a separate commit.
  47. in src/field_impl.h:417 in 0cdba2cd1f outdated 
    145+    if (a->normalized) r &= (a->magnitude <= 1);
146+    VERIFY_CHECK(r == 1);
147+    /* Invoke implementation-specific checks. */
148+    secp256k1_fe_impl_verify(a);
149+}
150+#endif /* defined(VERIFY) */
    real-or-random commented at 8:09 am on May 11, 2023:
    !defined(VERIFY) ?! well in this case i don’t know :D
    sipa commented at 8:44 am on May 11, 2023:
    I think there is a consistent interpretation for this type of comment (if refers to the code block just terminated, not the if condition that started it), for which it is correct. I also don’t think it matters too much, the point is to clarify what kind of condition is being terminated - negating it or not won’t do much for the reader I think.
  48. in src/field.h:59 in c0231d87f8 outdated 
    54+    , (!(((d7) & (d6) & (d5) & (d4) & (d3) & (d2)) == 0xfffffffful && ((d1) == 0xfffffffful || ((d1) == 0xfffffffe && (d0 >= 0xfffffc2f)))))
55+#else
56+#define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
57+#endif
58+
59+/* SECP256K1_FE_CONST_INNER is provided by the field implementation */
    real-or-random commented at 8:19 am on May 11, 2023:
    nit: this is part of the interface, so it should have a /** comment that describes the semantics (incl. mag and normalized).
    sipa commented at 9:05 am on May 11, 2023:
    Done.
  49. Merge magnitude/normalized fields, move/improve comments 
    Also split secp256k1_fe_verify into a generic and an implementation
specific part.
    b29566c51b
  50. in src/field.h:142 in 8c2745ac50 outdated 
    136@@ -136,7 +137,11 @@ static void secp256k1_fe_clear(secp256k1_fe *a);
137  */
138 static int secp256k1_fe_is_zero(const secp256k1_fe *a);
139 
140-/** Check the "oddness" of a field element. Requires the input to be normalized. */
141+/** Determine whether a (mod p) is odd.
142+ *
143+ * On input a must be a valid normalized field element.
    real-or-random commented at 8:26 am on May 11, 2023:
    nit: “On input, a” makes this much easier to parse for my brain. Maybe it’s a good idea add commas after every “On input”/“On output”
    sipa commented at 9:06 am on May 11, 2023:
    Done, inline in the 3 commits in which this happened.
  51. in src/field_5x52.h:45 in dd5ca02bb4 outdated 
    41@@ -29,11 +42,7 @@ typedef struct {
42     ((uint64_t)(d6) >> 16) | (((uint64_t)(d7)) << 16) \
43 }
44 
45-#ifdef VERIFY
46-#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)), 1, 1}
47-#else
48-#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0))}
49-#endif
50+#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) SECP256K1_FE_VERIFY_CONST((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) }
    jonasnick commented at 8:28 am on May 11, 2023:
    This is redundant with FE_CONST definition in field.h
    sipa commented at 9:06 am on May 11, 2023:
    Removed.
  52. in src/field.h:189 in 93bcf65872 outdated 
    163+/** Compare the values represented by 2 field elements, without constant-time guarantee.
164+ *
165+ * On input, a and b must be valid normalized field elements.
166+ * Let va = int(a) mod p, vb = int(v) mod p. Returns 1 if va > vb,
167+ * -1 if va < vb, and 0 if va = vb.
168+ */
    real-or-random commented at 8:31 am on May 11, 2023:
    nit: While “values represented by 2 fields elements” and int(a) etc. is technically correct, it hurts readability a bit. Maybe just identify field elements with their represented values here.
    sipa commented at 9:06 am on May 11, 2023:
    Done. I’ve described it slightly differently. Have a look.
  53. in src/field.h:151 in dd5ca02bb4 outdated 
    150+/** Set a field element to 0.
151+ *
152+ * On input, r does not need to be initialized.
153+ * On output, r represents 0, is normalized and has magnitude 0.
154+ */
155 static void secp256k1_fe_clear(secp256k1_fe *a);
    jonasnick commented at 8:36 am on May 11, 2023:
    The argument is called a.
    sipa commented at 9:06 am on May 11, 2023:
    Fixed.
  54. in src/field_impl.h:238 in dd5ca02bb4 outdated 
    224+static void secp256k1_fe_impl_clear(secp256k1_fe *a);
225+SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
226+    a->magnitude = 0;
227+    a->normalized = 1;
228+    secp256k1_fe_impl_clear(a);
229+}
    jonasnick commented at 8:37 am on May 11, 2023:
    should verify a after clearning?
    sipa commented at 9:06 am on May 11, 2023:
    Done.
  55. in src/field.h:256 in 8a95a15990 outdated 
    230@@ -230,8 +231,13 @@ static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a);
231  */
232 static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe * SECP256K1_RESTRICT b);
233 
234-/** Sets a field element to be the square of another. Requires the input's magnitude to be at most 8.
235- *  The output magnitude is 1 (but not guaranteed to be normalized). */
236+/** Square a field element.
237+ *
238+ * On input, a must be a valid field element; r does not need to be initialized. The magnitude
239+ * of a cannot exceed 8.
    real-or-random commented at 8:43 am on May 11, 2023:
    nit: s/cannot/must not
    sipa commented at 9:06 am on May 11, 2023:
    Done.
  56. in src/field.h:246 in 83ca155c17 outdated 
    219@@ -219,8 +220,14 @@ static void secp256k1_fe_mul_int(secp256k1_fe *r, int a);
220  */
221 static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a);
222 
223-/** Sets a field element to be the product of two others. Requires the inputs' magnitudes to be at most 8.
224- *  The output magnitude is 1 (but not guaranteed to be normalized). */
225+/** Multiply two field elements.
226+ *
227+ * On input, a and b must be valid field elements; r does not need to be initialized.
228+ * r and a may point to the same object, but neither can be equal to b. The magnitudes
    real-or-random commented at 8:43 am on May 11, 2023:
    s/cannot/must not (maybe there are more)
    sipa commented at 9:06 am on May 11, 2023:
    Done. I have not checked for more.
  57. in src/field.h:247 in df113a38c7 outdated 
    247- *  itself. */
248+/** Compute a square root of a field element.
249+ *
250+ * On input, a must be a valid field element with magnitude<=8; r need not be initialized.
251+ * Performs {r = sqrt(a)} or {r = sqrt(-a)}, whichever exists. The resulting value
252+ * represented by r will be a square itself. R and a cannot point to the same object.
    real-or-random commented at 8:45 am on May 11, 2023:

    s/R/r

    add a restrict ? :)

    sipa commented at 9:07 am on May 11, 2023:
    Done.
  58. in src/field_impl.h:377 in e0341e1a51 outdated 
    353+    secp256k1_fe_verify(r);
354+}
355+
356+static void secp256k1_fe_impl_inv_var(secp256k1_fe *r, const secp256k1_fe *x);
357+SECP256K1_INLINE static void secp256k1_fe_inv_var(secp256k1_fe *r, const secp256k1_fe *x) {
358+    int input_is_zero = secp256k1_fe_normalizes_to_zero(x);
    real-or-random commented at 8:51 am on May 11, 2023:

    #ifdef VERIFY here? well ok, I guess dead store elimation can handle it.

    same in constant time variant.

    sipa commented at 9:02 am on May 11, 2023:
    This entire block of functions is inside a #ifdef VERIFY.
  59. sipa force-pushed on May 11, 2023
  60. sipa commented at 9:05 am on May 11, 2023: contributor

    Made the following changes:

      0index 3bf4810c..1a060203 100644
  1--- a/src/field.h
  2+++ b/src/field.h
  3@@ -56,7 +56,13 @@
  4 #define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
  5 #endif
  6 
  7-/* SECP256K1_FE_CONST_INNER is provided by the field implementation */
  8+/** This expands to an initialized for a secp256k1_fe valued sum((i*32) * d_i, i=0..7) mod p.
  9+ *
 10+ * It has magnitude 1, unless d_i are all 0, in which case the magnitude is 0.
 11+ * It is normalized, unless sum(2^(i*32) * d_i, i=0..7) >= p.
 12+ *
 13+ * SECP256K1_FE_CONST_INNER is provided by the implementation.
 14+ */
 15 #define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) SECP256K1_FE_VERIFY_CONST((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) }
 16 
 17 static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
 18@@ -95,7 +101,7 @@ static const secp256k1_fe secp256k1_const_beta = SECP256K1_FE_CONST(
 19 #  define secp256k1_fe_half secp256k1_fe_impl_half
 20 #  define secp256k1_fe_add_int secp256k1_fe_impl_add_int
 21 #  define secp256k1_fe_is_square_var secp256k1_fe_impl_is_square_var
 22-#endif /* defined(VERIFY) */
 23+#endif /* !defined(VERIFY) */
 24 
 25 /** Normalize a field element.
 26  *
 27@@ -119,7 +125,7 @@ static void secp256k1_fe_normalize_var(secp256k1_fe *r);
 28 
 29 /** Determine whether r represents field element 0.
 30  *
 31- * On input r must be a valid field element.
 32+ * On input, r must be a valid field element.
 33  * Returns whether r = 0 (mod p).
 34  */
 35 static int secp256k1_fe_normalizes_to_zero(const secp256k1_fe *r);
 36@@ -139,14 +145,14 @@ static void secp256k1_fe_set_int(secp256k1_fe *r, int a);
 37 
 38 /** Set a field element to 0.
 39  *
 40- * On input, r does not need to be initialized.
 41- * On output, r represents 0, is normalized and has magnitude 0.
 42+ * On input, a does not need to be initialized.
 43+ * On output, a represents 0, is normalized and has magnitude 0.
 44  */
 45 static void secp256k1_fe_clear(secp256k1_fe *a);
 46 
 47 /** Determine whether a represents field element 0.
 48  *
 49- * On input a must be a valid normalized field element.
 50+ * On input, a must be a valid normalized field element.
 51  * Returns whether a = 0 (mod p).
 52  *
 53  * This behaves identical to secp256k1_normalizes_to_zero{,_var}, but requires
 54@@ -156,7 +162,7 @@ static int secp256k1_fe_is_zero(const secp256k1_fe *a);
 55 
 56 /** Determine whether a (mod p) is odd.
 57  *
 58- * On input a must be a valid normalized field element.
 59+ * On input, a must be a valid normalized field element.
 60  * Returns (int(a) mod p) & 1.
 61  */
 62 static int secp256k1_fe_is_odd(const secp256k1_fe *a);
 63@@ -178,8 +184,8 @@ static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b);
 64 /** Compare the values represented by 2 field elements, without constant-time guarantee.
 65  *
 66  * On input, a and b must be valid normalized field elements.
 67- * Let va = int(a) mod p, vb = int(v) mod p. Returns 1 if va > vb,
 68- * -1 if va < vb, and 0 if va = vb.
 69+ * Returns 1 if a > b, -1 if a < b, and 0 if a = b (comparisons are done as integers
 70+ * in range 0..p-1).
 71  */
 72 static int secp256k1_fe_cmp_var(const secp256k1_fe *a, const secp256k1_fe *b);
 73 
 74@@ -238,7 +244,7 @@ static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a);
 75  *
 76  * On input, a and b must be valid field elements; r does not need to be initialized.
 77  * r and a may point to the same object, but neither can be equal to b. The magnitudes
 78- * of a and b cannot exceed 8.
 79+ * of a and b must not exceed 8.
 80  * Performs {r = a * b}
 81  * On output, r will have magnitude 1, but won't be normalized.
 82  */
 83@@ -257,10 +263,10 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
 84  *
 85  * On input, a must be a valid field element with magnitude<=8; r need not be initialized.
 86  * Performs {r = sqrt(a)} or {r = sqrt(-a)}, whichever exists. The resulting value
 87- * represented by r will be a square itself. R and a cannot point to the same object.
 88+ * represented by r will be a square itself. Variables r and a cannot point to the same object.
 89  * On output, r will have magnitude 1 but will not be normalized.
 90  */
 91-static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a);
 92+static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe * SECP256K1_RESTRICT a);
 93 
 94 /** Compute the modular inverse of a field element.
 95  *
 96diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h
 97index 30a541f2..11838a36 100644
 98--- a/src/field_10x26_impl.h
 99+++ b/src/field_10x26_impl.h
100@@ -15,26 +15,25 @@
101 #ifdef VERIFY
102 static void secp256k1_fe_impl_verify(const secp256k1_fe *a) {
103     const uint32_t *d = a->n;
104-    int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
105-    r &= (d[0] <= 0x3FFFFFFUL * m);
106-    r &= (d[1] <= 0x3FFFFFFUL * m);
107-    r &= (d[2] <= 0x3FFFFFFUL * m);
108-    r &= (d[3] <= 0x3FFFFFFUL * m);
109-    r &= (d[4] <= 0x3FFFFFFUL * m);
110-    r &= (d[5] <= 0x3FFFFFFUL * m);
111-    r &= (d[6] <= 0x3FFFFFFUL * m);
112-    r &= (d[7] <= 0x3FFFFFFUL * m);
113-    r &= (d[8] <= 0x3FFFFFFUL * m);
114-    r &= (d[9] <= 0x03FFFFFUL * m);
115+    int m = a->normalized ? 1 : 2 * a->magnitude;
116+    VERIFY_CHECK(d[0] <= 0x3FFFFFFUL * m);
117+    VERIFY_CHECK(d[1] <= 0x3FFFFFFUL * m);
118+    VERIFY_CHECK(d[2] <= 0x3FFFFFFUL * m);
119+    VERIFY_CHECK(d[3] <= 0x3FFFFFFUL * m);
120+    VERIFY_CHECK(d[4] <= 0x3FFFFFFUL * m);
121+    VERIFY_CHECK(d[5] <= 0x3FFFFFFUL * m);
122+    VERIFY_CHECK(d[6] <= 0x3FFFFFFUL * m);
123+    VERIFY_CHECK(d[7] <= 0x3FFFFFFUL * m);
124+    VERIFY_CHECK(d[8] <= 0x3FFFFFFUL * m);
125+    VERIFY_CHECK(d[9] <= 0x03FFFFFUL * m);
126     if (a->normalized) {
127-        if (r && (d[9] == 0x03FFFFFUL)) {
128+        if (d[9] == 0x03FFFFFUL) {
129             uint32_t mid = d[8] & d[7] & d[6] & d[5] & d[4] & d[3] & d[2];
130             if (mid == 0x3FFFFFFUL) {
131-                r &= ((d[1] + 0x40UL + ((d[0] + 0x3D1UL) >> 26)) <= 0x3FFFFFFUL);
132+                VERIFY_CHECK((d[1] + 0x40UL + ((d[0] + 0x3D1UL) >> 26)) <= 0x3FFFFFFUL);
133             }
134         }
135     }
136-    VERIFY_CHECK(r == 1);
137 }
138 #endif
139 
140diff --git a/src/field_5x52.h b/src/field_5x52.h
141index 309f998c..f20c246f 100644
142--- a/src/field_5x52.h
143+++ b/src/field_5x52.h
144@@ -42,8 +42,6 @@ typedef struct {
145     ((uint64_t)(d6) >> 16) | (((uint64_t)(d7)) << 16) \
146 }
147 
148-#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0) {SECP256K1_FE_CONST_INNER((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) SECP256K1_FE_VERIFY_CONST((d7), (d6), (d5), (d4), (d3), (d2), (d1), (d0)) }
149-
150 typedef struct {
151     uint64_t n[4];
152 } secp256k1_fe_storage;
153diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
154index 7839e650..1e9d0c5b 100644
155--- a/src/field_5x52_impl.h
156+++ b/src/field_5x52_impl.h
157@@ -21,19 +21,18 @@
158 #ifdef VERIFY
159 static void secp256k1_fe_impl_verify(const secp256k1_fe *a) {
160     const uint64_t *d = a->n;
161-    int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
162+    int m = a->normalized ? 1 : 2 * a->magnitude;
163    /* secp256k1 'p' value defined in "Standards for Efficient Cryptography" (SEC2) 2.7.1. */
164-    r &= (d[0] <= 0xFFFFFFFFFFFFFULL * m);
165-    r &= (d[1] <= 0xFFFFFFFFFFFFFULL * m);
166-    r &= (d[2] <= 0xFFFFFFFFFFFFFULL * m);
167-    r &= (d[3] <= 0xFFFFFFFFFFFFFULL * m);
168-    r &= (d[4] <= 0x0FFFFFFFFFFFFULL * m);
169+    VERIFY_CHECK(d[0] <= 0xFFFFFFFFFFFFFULL * m);
170+    VERIFY_CHECK(d[1] <= 0xFFFFFFFFFFFFFULL * m);
171+    VERIFY_CHECK(d[2] <= 0xFFFFFFFFFFFFFULL * m);
172+    VERIFY_CHECK(d[3] <= 0xFFFFFFFFFFFFFULL * m);
173+    VERIFY_CHECK(d[4] <= 0x0FFFFFFFFFFFFULL * m);
174     if (a->normalized) {
175-        if (r && (d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
176-            r &= (d[0] < 0xFFFFEFFFFFC2FULL);
177+        if ((d[4] == 0x0FFFFFFFFFFFFULL) && ((d[3] & d[2] & d[1]) == 0xFFFFFFFFFFFFFULL)) {
178+            VERIFY_CHECK(d[0] < 0xFFFFEFFFFFC2FULL);
179         }
180     }
181-    VERIFY_CHECK(r == 1);
182 }
183 #endif
184 
185diff --git a/src/field_impl.h b/src/field_impl.h
186index 37fb1377..630c9dca 100644
187--- a/src/field_impl.h
188+++ b/src/field_impl.h
189@@ -154,12 +154,11 @@ static void secp256k1_fe_verify(const secp256k1_fe *a) { (void)a; }
190 static void secp256k1_fe_impl_verify(const secp256k1_fe *a);
191 static void secp256k1_fe_verify(const secp256k1_fe *a) {
192     /* Magnitude between 0 and 32. */
193-    int r = (a->magnitude >= 0) & (a->magnitude <= 32);
194+    VERIFY_CHECK((a->magnitude >= 0) && (a->magnitude <= 32));
195     /* Normalized is 0 or 1. */
196-    r &= (a->normalized == 0) | (a->normalized == 1);
197+    VERIFY_CHECK((a->normalized == 0) || (a->normalized == 1));
198     /* If normalized, magnitude must be 0 or 1. */
199-    if (a->normalized) r &= (a->magnitude <= 1);
200-    VERIFY_CHECK(r == 1);
201+    if (a->normalized) VERIFY_CHECK(a->magnitude <= 1);
202     /* Invoke implementation-specific checks. */
203     secp256k1_fe_impl_verify(a);
204 }
205@@ -226,6 +225,7 @@ SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe *a) {
206     a->magnitude = 0;
207     a->normalized = 1;
208     secp256k1_fe_impl_clear(a);
209+    secp256k1_fe_verify(a);
210 }
211 
212 static int secp256k1_fe_impl_is_zero(const secp256k1_fe *a);
  61. sipa force-pushed on May 11, 2023
  62. sipa commented at 9:27 am on May 11, 2023: contributor

    Made the following changes:

     0index 1a060203..4ff8d938 100644
 1--- a/src/field.h
 2+++ b/src/field.h
 3@@ -253,7 +253,7 @@ static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp2
 4 /** Square a field element.
 5  *
 6  * On input, a must be a valid field element; r does not need to be initialized. The magnitude
 7- * of a cannot exceed 8.
 8+ * of a must not exceed 8.
 9  * Performs {r = a**2}
10  * On output, r will have magnitude 1, but won't be normalized.
11  */
12@@ -263,10 +263,10 @@ static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a);
13  *
14  * On input, a must be a valid field element with magnitude<=8; r need not be initialized.
15  * Performs {r = sqrt(a)} or {r = sqrt(-a)}, whichever exists. The resulting value
16- * represented by r will be a square itself. Variables r and a cannot point to the same object.
17+ * represented by r will be a square itself. Variables r and a must not point to the same object.
18  * On output, r will have magnitude 1 but will not be normalized.
19  */
20-static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe * SECP256K1_RESTRICT a);
21+static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k1_fe * SECP256K1_RESTRICT a);
22 
23 /** Compute the modular inverse of a field element.
24  *
  63. sipa force-pushed on May 11, 2023
  64. sipa force-pushed on May 11, 2023
  65. sipa commented at 9:36 am on May 11, 2023: contributor

    Made the following changes:

     0diff --git a/src/field_10x26_impl.h b/src/field_10x26_impl.h
 1index 11838a36..0dacd596 100644
 2--- a/src/field_10x26_impl.h
 3+++ b/src/field_10x26_impl.h
 4@@ -342,13 +342,14 @@ static void secp256k1_fe_impl_get_b32(unsigned char *r, const secp256k1_fe *a) {
 5 }
 6 
 7 SECP256K1_INLINE static void secp256k1_fe_impl_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
 8-    /* Verify that for each limb, the value we'll subtract from is larger than
 9-     * the maximum permitted value for that limb. */
10+    /* For all legal values of m (0..31), the following properties hold: */
11     VERIFY_CHECK(0x3FFFC2FUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
12     VERIFY_CHECK(0x3FFFFBFUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
13     VERIFY_CHECK(0x3FFFFFFUL * 2 * (m + 1) >= 0x3FFFFFFUL * 2 * m);
14     VERIFY_CHECK(0x03FFFFFUL * 2 * (m + 1) >= 0x03FFFFFUL * 2 * m);
15 
16+    /* Due to the properties above, the left hand in the subtractions below is never less than
17+     * the right hand. */
18     r->n[0] = 0x3FFFC2FUL * 2 * (m + 1) - a->n[0];
19     r->n[1] = 0x3FFFFBFUL * 2 * (m + 1) - a->n[1];
20     r->n[2] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[2];
21diff --git a/src/field_5x52_impl.h b/src/field_5x52_impl.h
22index 1e9d0c5b..2ac39bdd 100644
23--- a/src/field_5x52_impl.h
24+++ b/src/field_5x52_impl.h
25@@ -311,12 +311,13 @@ static void secp256k1_fe_impl_get_b32(unsigned char *r, const secp256k1_fe *a) {
26 }
27 
28 SECP256K1_INLINE static void secp256k1_fe_impl_negate(secp256k1_fe *r, const secp256k1_fe *a, int m) {
29-    /* Verify that for each limb, the value we'll subtract from is larger than
30-     * the maximum permitted value for that limb. */
31+    /* For all legal values of m (0..31), the following properties hold: */
32     VERIFY_CHECK(0xFFFFEFFFFFC2FULL * 2 * (m + 1) >= 0xFFFFFFFFFFFFFULL * 2 * m);
33     VERIFY_CHECK(0xFFFFFFFFFFFFFULL * 2 * (m + 1) >= 0xFFFFFFFFFFFFFULL * 2 * m);
34     VERIFY_CHECK(0x0FFFFFFFFFFFFULL * 2 * (m + 1) >= 0x0FFFFFFFFFFFFULL * 2 * m);
35 
36+    /* Due to the properties above, the left hand in the subtractions below is never less than
37+     * the right hand. */
38     r->n[0] = 0xFFFFEFFFFFC2FULL * 2 * (m + 1) - a->n[0];
39     r->n[1] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[1];
40     r->n[2] = 0xFFFFFFFFFFFFFULL * 2 * (m + 1) - a->n[2];
  66. sipa force-pushed on May 11, 2023
  67. in src/field.h:230 in 50d916364e outdated 
    249+/** Multiply a field element with a small integer.
250+ *
251+ * On input, r must be a valid field element. a must be an integer in [0,32].
252+ * The magnitude of r times a must not exceed 32.
253+ * Performs {r *= a}.
254+ * On output, r's magnitude is multiplied by a, and normalized is cleared.
    jonasnick commented at 9:54 am on May 11, 2023:
    Probably much clearer to say that r is normalized vs. “normalized is cleared”.
    sipa commented at 10:29 am on May 11, 2023:
    Done (except it’s not normalized).
  68. in src/field.h:237 in 50d916364e outdated 
    257 
258-/** Adds a field element to another. The result has the sum of the inputs' magnitudes as magnitude. */
259+/** Increment a field element by another.
260+ *
261+ * On input, r and a must be valid field elements, not necessarily normalized.
262+ * The sum of their magnitudes may not exceed 32.
    jonasnick commented at 9:55 am on May 11, 2023:
    may not -> must not?
    sipa commented at 10:29 am on May 11, 2023:
    Done.
  69. in src/field.h:59 in 50d916364e outdated 
    54+    , (!(((d7) & (d6) & (d5) & (d4) & (d3) & (d2)) == 0xfffffffful && ((d1) == 0xfffffffful || ((d1) == 0xfffffffe && (d0 >= 0xfffffc2f)))))
55+#else
56+#define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
57+#endif
58+
59+/** This expands to an initialized for a secp256k1_fe valued sum((i*32) * d_i, i=0..7) mod p.
    jonasnick commented at 9:56 am on May 11, 2023:
    expands to an initialized what?
    sipa commented at 10:29 am on May 11, 2023:
    Typo: initializer. Fixed.
  70. in src/field.h:269 in 50d916364e outdated 
    299+ * On input, a must be a valid field element with magnitude<=8; r need not be initialized.
300+ * Performs {r = sqrt(a)} or {r = sqrt(-a)}, whichever exists. The resulting value
301+ * represented by r will be a square itself. Variables r and a must not point to the same object.
302+ * On output, r will have magnitude 1 but will not be normalized.
303+ */
304+static int secp256k1_fe_sqrt(secp256k1_fe * SECP256K1_RESTRICT r, const secp256k1_fe * SECP256K1_RESTRICT a);
    jonasnick commented at 10:00 am on May 11, 2023:
    Did you intentionally skipped adding a postcondition to the sqrt() code (fe_verify of the square root, maybe check the magnitude and normalization).
    sipa commented at 10:28 am on May 11, 2023:

    I’ve added a VERIFY_CHECK that if sqrt returns 0, it’s the sqrt of the negation.

    Other than that, no need for fe_verify, because it’s not touching internals of field elements.

  71. in src/field.h:318 in 50d916364e outdated 
    351 static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag);
352 
353 /** Halves the value of a field element modulo the field prime. Constant-time.
354  *  For an input magnitude 'm', the output magnitude is set to 'floor(m/2) + 1'.
355  *  The output is not guaranteed to be normalized, regardless of the input. */
356 static void secp256k1_fe_half(secp256k1_fe *r);
    jonasnick commented at 10:11 am on May 11, 2023:

    This comment didn’t get updated. How about:

    0/** Halve the value of a field element modulo the field prime in constant-time.
1 *
2 * On input, r must be a valid field element.
3 * On output, r will be normalized and have magnitude floor(m/2) + 1 where m is
4 * the magnitude of r on input.
5 */
    sipa commented at 10:28 am on May 11, 2023:
    Done. Used that literally.
  72. in src/field.h:322 in 50d916364e outdated 
    360+/** Sets r to a field element with magnitude m, normalized if (and only if) m==0.
361+ *  The value is chosen so that it is likely to trigger edge cases related to
362+ *  internal overflows. */
363 static void secp256k1_fe_get_bounds(secp256k1_fe *r, int m);
364 
365 /** Determine whether a is a square (modulo p). */
    jonasnick commented at 10:14 am on May 11, 2023:

    This comment didn’t get updated: Maybe something like:

    0/** Determine whether a is a square (modulo p).
1 *
2 * On input, a must be a valid field element.
3 */

    nit: Should this function declaration be moved to the top to the other _is_ functions?

    sipa commented at 10:27 am on May 11, 2023:
    Done. I didn’t move it to avoid messing with the commits, but we can do that as a follow-up.
  73. Bugfix: correct SECP256K1_FE_CONST mag/norm fields 7fa5195559
  74. Abstract out verify logic for fe_normalize b6b6f9cb97
  75. Abstract out verify logic for fe_normalize_weak e28b51f522
  76. Abstract out verify logic for fe_normalize_var 6c31371120
  77. Abstract out verify logic for fe_normalizes_to_zero{,_var} 864f9db491
  78. Abstract out verify logic for fe_set_int 19a2bfeeea
  79. Abstract out verify logic for fe_clear c701d9a471
  80. Abstract out verify logic for fe_is_zero d3f3fe8616
  81. Abstract out verify logic for fe_is_odd c5e788d672
  82. Improve comments/check for fe_equal{,_var} 7d7d43c6dd
  83. Abstract out verify logic for fe_cmp_var ce4d2093e8
  84. Abstract out verify logic for fe_set_b32 f7a7666aeb
  85. Abstract out verify logic for fe_get_b32 144670893e
  86. Abstract out verify logic for fe_negate 65d82a3445
  87. Abstract out verify logic for fe_mul_int 7e7ad7ff57
  88. Abstract out verify logic for fe_add e179e651cb
  89. Abstract out verify logic for fe_mul 4c25f6efbd
  90. Abstract out verify logic for fe_sqr 6ab35082ef
  91. Improve comments/checks for fe_sqrt be82bd8e03
  92. Abstract out verify logic for fe_cmov 1e6894bdd7
  93. Abstract out verify logic for fe_to_storage 76d31e5047
  94. Abstract out verify logic for fe_from_storage 3167646072
  95. Abstract out verify logic for fe_inv{,_var} d5aa2f0358
  96. Abstract out verify logic for fe_get_bounds 283cd80ab4
  97. Abstract out verify logic for fe_half 89e324c6b9
  98. Abstract out verify logic for fe_add_int 4371f98346
  99. Abstract out verify logic for fe_is_square_var 4e176ad5b9
  100. Simplify secp256k1_fe_{impl_,}verify 7fc642fa25
  101. sipa force-pushed on May 11, 2023
  102. sipa commented at 10:27 am on May 11, 2023: contributor

    Made these changes:

     0diff --git a/src/field.h b/src/field.h
 1index 72e562e1..2c8fbc28 100644
 2--- a/src/field.h
 3+++ b/src/field.h
 4@@ -56,7 +56,7 @@
 5 #define SECP256K1_FE_VERIFY_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
 6 #endif
 7 
 8-/** This expands to an initialized for a secp256k1_fe valued sum((i*32) * d_i, i=0..7) mod p.
 9+/** This expands to an initializer for a secp256k1_fe valued sum((i*32) * d_i, i=0..7) mod p.
10  *
11  * It has magnitude 1, unless d_i are all 0, in which case the magnitude is 0.
12  * It is normalized, unless sum(2^(i*32) * d_i, i=0..7) >= p.
13@@ -227,14 +227,14 @@ static void secp256k1_fe_add_int(secp256k1_fe *r, int a);
14  * On input, r must be a valid field element. a must be an integer in [0,32].
15  * The magnitude of r times a must not exceed 32.
16  * Performs {r *= a}.
17- * On output, r's magnitude is multiplied by a, and normalized is cleared.
18+ * On output, r's magnitude is multiplied by a, and r will not be normalized.
19  */
20 static void secp256k1_fe_mul_int(secp256k1_fe *r, int a);
21 
22 /** Increment a field element by another.
23  *
24  * On input, r and a must be valid field elements, not necessarily normalized.
25- * The sum of their magnitudes may not exceed 32.
26+ * The sum of their magnitudes must not exceed 32.
27  * Performs {r += a}.
28  * On output, r will not be normalized, and will have magnitude incremented by a's.
29  */
30@@ -309,9 +309,12 @@ static void secp256k1_fe_storage_cmov(secp256k1_fe_storage *r, const secp256k1_f
31  */
32 static void secp256k1_fe_cmov(secp256k1_fe *r, const secp256k1_fe *a, int flag);
33 
34-/** Halves the value of a field element modulo the field prime. Constant-time.
35- *  For an input magnitude 'm', the output magnitude is set to 'floor(m/2) + 1'.
36- *  The output is not guaranteed to be normalized, regardless of the input. */
37+/** Halve the value of a field element modulo the field prime in constant-time.
38+ *
39+ * On input, r must be a valid field element.
40+ * On output, r will be normalized and have magnitude floor(m/2) + 1 where m is
41+ * the magnitude of r on input.
42+ */
43 static void secp256k1_fe_half(secp256k1_fe *r);
44 
45 /** Sets r to a field element with magnitude m, normalized if (and only if) m==0.
46@@ -319,7 +322,10 @@ static void secp256k1_fe_half(secp256k1_fe *r);
47  *  internal overflows. */
48 static void secp256k1_fe_get_bounds(secp256k1_fe *r, int m);
49 
50-/** Determine whether a is a square (modulo p). */
51+/** Determine whether a is a square (modulo p).
52+ *
53+ * On input, a must be a valid field element.
54+ */
55 static int secp256k1_fe_is_square_var(const secp256k1_fe *a);
56 
57 /** Check invariants on a field element (no-op unless VERIFY is enabled). */
58diff --git a/src/field_impl.h b/src/field_impl.h
59index 630c9dca..c082d8f5 100644
60--- a/src/field_impl.h
61+++ b/src/field_impl.h
62@@ -55,7 +55,7 @@ static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
63      *  itself always a square (a ** ((p+1)/4) is the square of a ** ((p+1)/8)).
64      */
65     secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
66-    int j;
67+    int j, ret;
68 
69 #ifdef VERIFY
70     VERIFY_CHECK(r != a);
71@@ -145,7 +145,16 @@ static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
72     /* Check that a square root was actually calculated */
73 
74     secp256k1_fe_sqr(&t1, r);
75-    return secp256k1_fe_equal(&t1, a);
76+    ret = secp256k1_fe_equal(&t1, a);
77+
78+#ifdef VERIFY
79+    if (!ret) {
80+        secp256k1_fe_negate(&t1, &t1, 1);
81+        secp256k1_fe_normalize_var(&t1);
82+        VERIFY_CHECK(secp256k1_fe_equal_var(&t1, a));
83+    }
84+#endif
85+    return ret;
86 }
87 
88 #ifndef VERIFY
  103. jonasnick commented at 12:16 pm on May 11, 2023: contributor
    ACK 7fc642fa25ad03ebd95cfe237b625dfb6dfdfa94
  104. real-or-random approved
  105. real-or-random commented at 12:20 pm on May 11, 2023: contributor
    ACK 7fc642fa25ad03ebd95cfe237b625dfb6dfdfa94
  106. sipa merged this on May 11, 2023
  107. sipa closed this on May 11, 2023
  108. sipa cross-referenced this on May 11, 2023 from issue Split fe_set_b32 into reducing and normalizing variants by sipa
  109. sipa referenced this in commit b4eb644b6c on May 12, 2023
  110. hebasto referenced this in commit 49c52ea2b1 on May 13, 2023
  111. sipa cross-referenced this on May 14, 2023 from issue ElligatorSwift + integrated x-only DH by sipa
  112. theStack cross-referenced this on Jun 1, 2023 from issue fix input range comment for `secp256k1_fe_add_int` by theStack
  113. theStack referenced this in commit 605e07e365 on Jun 1, 2023
  114. real-or-random referenced this in commit bf29f8d0a6 on Jun 1, 2023
  115. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
  116. dderjoel referenced this in commit 36bdb19763 on Jun 21, 2023
  117. sipa referenced this in commit 901336eee7 on Jun 21, 2023
  118. vmta referenced this in commit 8f03457eed on Jul 1, 2023
  119. sipa cross-referenced this on Jul 10, 2023 from issue tighten group magnitude limits, save normalize_weak calls in group add methods (revival of #1032) by theStack
  120. jonasnick cross-referenced this on Jul 24, 2023 from issue Upstream PRs 1268, 1276, 1267, 1265, 1230, 1279, 1273, 1263, 1231, 1285, 1283, 1205, 1286, 1275, 1234, 1239, 1240, 1284, 1277, 1289, 1270, 1296, 1301, 1299, 1066, 1300, 1292, 1305, 1303, 1133, 1306, 1207, 1304, 1307, 1311, 1309, 1312 by jonasnick


sipa jonasnick robot-dreams real-or-random

github-metadata-mirror

This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-22 05:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me