Make fe_cmov take max of magnitudes #1317

1. 
   sipa commented at 1:40 pm on May 15, 2023: contributor

   This addresses part of #1001.

   The magnitude and normalization of the output of secp256k1_fe_cmov should not depend on the runtime value of flag.

2. Make fe_cmov take max of magnitudes 31b4bbee1e
3. sipa cross-referenced this on May 15, 2023 from issue Make fe magnitude implied statically by real-or-random
4. real-or-random approved
5. 
   real-or-random commented at 8:56 pm on May 15, 2023: contributor

   utACK 31b4bbee1e115865a8a3aff6ccf04f6108371c5d
6. 
   real-or-random commented at 8:50 pm on May 17, 2023: contributor

   @stratospher Interested in reviewing this? :)
7. in src/tests.c:3196 in 31b4bbee1e

   3192+        CHECK(!x.normalized);
   3193+        CHECK((x.magnitude == q.magnitude) || (x.magnitude == z.magnitude));
   3194+        CHECK((x.magnitude >= q.magnitude) && (x.magnitude >= z.magnitude));
   3195 #endif
   3196+        x = q;
   3197         secp256k1_fe_cmov(&x, &x, 1);
   

   ---

   ---

   

   stratospher commented at 7:43 am on May 18, 2023:

   31b4bbe: do we need this line? don’t think it does anything. (fe_cmov part)

   ---

   

   sipa commented at 12:47 pm on May 18, 2023:

   I think that’s the point: the test verifies that it does nothing.

   ---

   

   stratospher commented at 6:35 pm on May 18, 2023:

   haha, i see.
8. 
   stratospher commented at 8:15 am on May 18, 2023: contributor

   ACK 31b4bbe.

   haha, yes. surprised to learn that magnitude doesn’t need to be the actual magnitude and is just an overflow protection mechanism.

9. 
   sipa commented at 12:55 pm on May 18, 2023: contributor

   @stratospher Right! They are constraints on the (representation of) the value stored in the field element. They don’t (or at least, shouldn’t) depend on the values themselves. They exist to allow us to reason about what operations are allowed. This is all a consequence of having non-canonical represents in the first place; if we’d always normalize after every operation, they wouldn’t be needed. But we don’t, as a performance optimization, and as a consequence we want to be able to bound how “denormalized” field elements are allowed to be.

   If this were C++ or Rust or some other language with more complex type reasoning, we’d put the magnitude/normalization properties in the type itself, and have their propagation checked by the compiler (e.g. adding a fieldelem of magnitude 3 to a fieldelem of magnitude 4 always yields one of magnitude 7, regardless of the values in it). The explicit runtime tracking of magnitude in VERIFY mode is a best-effort approximation of that which we can do in C.

   But to the extent possible, we want the magnitude/normalization properties to be fixed at compile-time (even if not known), because that guarantees that any possible code path sticks to field elements which satisfy the constraints.

10. 
    stratospher commented at 6:35 pm on May 18, 2023: contributor

    interesting - have a better picture of the rationale behind tracking magnitudes and wanting them to be fixed!
11. real-or-random merged this on May 19, 2023
12. real-or-random closed this on May 19, 2023

    ---

13. vmta referenced this in commit e1120c94a1 on Jun 4, 2023
14. sipa referenced this in commit 901336eee7 on Jun 21, 2023
15. vmta referenced this in commit 8f03457eed on Jul 1, 2023
16. hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023
17. jonasnick cross-referenced this on Jul 26, 2023 from issue Upstream PRs 1314, 1317, 1318, 1316, 1327, 1310, 1328, 1333, 1330, 1334, 1337, 1341, 1339, 1350, 1349, 1338, 1129, 1347, 1336, 1295, 1354, 1355, 1356 by jonasnick

Contributors
sipa real-or-random stratospher