Make fe_cmov take max of magnitudes #1317

pull sipa wants to merge 1 commits into bitcoin-core:master from sipa:202305_max_cmov changing 3 files +19 −17

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.
Make fe_cmov take max of magnitudes 31b4bbee1e
real-or-random approved
real-or-random commented at 8:56 PM on May 15, 2023: contributor

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

@stratospher Interested in reviewing this? :)
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.
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.
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.
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!
real-or-random merged this on May 19, 2023
real-or-random closed this on May 19, 2023
vmta referenced this in commit e1120c94a1 on Jun 4, 2023
sipa referenced this in commit 901336eee7 on Jun 21, 2023
vmta referenced this in commit 8f03457eed on Jul 1, 2023
hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023
delta1 referenced this in commit 3f32c20932 on Aug 8, 2023
delta1 referenced this in commit 31ac0c1081 on Aug 31, 2023
janus referenced this in commit c4348d88db on Sep 11, 2023
div72 referenced this in commit af627d47c3 on Apr 12, 2025
str4d referenced this in commit 5a6bf5f178 on Jun 4, 2025
Fabcien referenced this in commit 1570242741 on Apr 24, 2026
Fabcien referenced this in commit 2035258eab on Apr 24, 2026

Contributors

sipa

real-or-random

stratospher

Linked (view graph)

#1001 Make fe magnitude implied statically