Document field functions assumptions and validate it using magnitude and `fe_verify` checks

[siv2r]

Fixes #946 and #1061

Changes:

• update docs to _fe_equal_var requires only the first input magnitude to be 1
• removed the secp256k1_fe_normalize_weak call for the second argument of _fe_equal_var

make check results

make  check-am
make[1]: Entering directory '/home/siv2r/Projects/secp256k1'
make  check-TESTS
make[2]: Entering directory '/home/siv2r/Projects/secp256k1'
make[3]: Entering directory '/home/siv2r/Projects/secp256k1'
PASS: tests
PASS: exhaustive_tests
============================================================================
Testsuite summary for libsecp256k1 0.1.0-pre
============================================================================
# TOTAL: 2
# PASS:  2
# SKIP:  0
# XFAIL: 0
# FAIL:  0
# XPASS: 0
# ERROR: 0
============================================================================
make[3]: Leaving directory '/home/siv2r/Projects/secp256k1'
make[2]: Leaving directory '/home/siv2r/Projects/secp256k1'
make[1]: Leaving directory '/home/siv2r/Projects/secp256k1'

[siv2r]

In fe_sqrt: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/field_impl.h#L132-L135 Here, the secp256k1_fe_sqr function ensures that t1->magnitude = 1 but there is no guarantee for the magnitude of a to be one since it is passed into the function. Hence, some fe_sqrt tests are failing after adding magnitude checks inside fe_equal.

We could do secp256k1_fe_normalize_weak(a) but this changes the value of a and we don't want that right? Alternatively, we could call fe_equal_var instead of fe_equal. Is it necessary for secp256k1_fe_sqrt to be of constant time?

[peterdettman]

@siv2r Regarding _fe_sqrt, there is an implicit magnitude restriction on a, since it is used as the input to _fe_mul and _fe_sqr at the top of the method. That magnitude restriction is <= 8. 8 is also a kind of global implicit limit for inputs where not otherwise stated (but we should definitely be working towards fully documenting and validating all such assumptions).

I think it might be better to just say that both inputs to the equals methods can be magnitude <= 8 too (indeed tied to the mul/sqr limit whatever it is or changes to). There's no real obstacle to the implementation(s) (just change the third argument to _fe_negate to 8) and no performance hit AFAICT.

[peterdettman]

Is it necessary for secp256k1_fe_sqrt to be of constant time?

It's only used in a single var-time caller, so technically it could be changed to sqrt_var, but preferably not.

[real-or-random]

Apparently secp256k1_fe_equal and secp256k1_fe_equal_var are identical up to the final call to normalizes_to_zero or normalizes_to_zero_var and so they both only require that a has magnitude 1. So we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

Edited because I first thought secp256k1_fe_equal and secp256k1_fe_equal_var are exactly identical.

[siv2r]

It's only used in a single var-time caller

Oh, Okay. Then, creating a new function for secp256k1_fe_sqrt_var (while renaming the old one to _fe_sqrt_const) might be overkill.

we should just document that secp256k1_fe_equal only requires the magnitude of a to be 1.

Yes, I think this might be a better approach since it keeps the functionality of both fe_equal_var and fe_equal similar.

After this, I felt we needed to remove the _fe_normalize_weak calls before _fe_equal, but surprisingly _fe_equal is used rarely in the code. The only other place where it is used is: https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77 Even here, the magnitude of y is two, so modifying the _fe_sqrt function (which I suggested) is a bad idea.

[real-or-random]

https://github.com/bitcoin-core/secp256k1/blob/a1102b12196ea27f44d6201de4d25926a2ae9640/src/modules/extrakeys/tests_impl.h#L75-L77

Hehe ok, and here it's basically an oversight. This is just test code, so fe_equal_var could be used instead. I mean, not that it matters.

[peterdettman]

fe_equal_var is really a bit dubious. It only has a fast path when the inputs are not equal, and the only callers are for public key parsing and (ECDSA) verification, where that would mean an error condition and is probably uncommon. If the fast path is not hit, it actually costs a couple of cycles more. (Not to mention that the performance difference is tiny relative to those operations anyway).

[peterdettman]

While I'm on the subject, the other callers to _fe_normalizes_to_zero_var expect a false result and so will almost always hit the fast path. Depending on the level of inlining, _fe_equal_var could be "spoiling" the branch prediction for that fast path check for the other callers.

[siv2r]

addressed https://github.com/bitcoin-core/secp256k1/pull/1062#discussion_r778917127 and https://github.com/bitcoin-core/secp256k1/pull/1062#pullrequestreview-844742940 (detailed explanation in 08186e8).

[siv2r]

I also benchmarked the tests.c file (using time ./tests) since a lot of secp256k1_fe_verify calls were added in this PR. These are the results (on 64-bit, i7-8750H) for three iterations:

branch	iter1	iter2	iter3
master	2min 26.21sec	2min 26.44sec	2min 26.68sec
this PR	2min 26.99sec	2min 26.91sec	2min 26.83sec

[real-or-random]

@peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

[peterdettman]

@peterdettman Good points. Do you think we should remove fe_equal_var entirely and maybe document in fe_equal that this is intentional?

Yeah, pretty much. Until there's a performance-sensitive caller for whom a != b is the expected result, I don't see any value in _fe_equal_var. If such a caller does turn up, then there should be a fast path for inequality that doesn't even need the subtraction, so we'd rewrite it anyway.

[siv2r]

addressed #1061

[real-or-random]

@siv2r Do you plan to also remove the fe_equal_var in a further commit? Or should we do this in a separate PR?

(If you want to add it here, I think it's really ok to add it on top of the existing commits, no need to rewrite the existing commits).

[siv2r]

Okay, I will remove fe_equal_var in a new commit (this PR).

[siv2r]

• Removed fe_equal_var and documented the reason in fe_equal
• Replaced the fe_equal_var calls with fe_equal

[sipa]

I missed the "field: add magnitude check and _fe_verify check for internal field APIs" commit being added here before writing #1066 (which duplicates some of its efforts, but also goes a lot further in a number of ways). Feel free to keep it in (and I'll rebase), but if you think #1066 covers everything you're doing here, perhaps it's easier to leave that for that PR.

[siv2r]

No worries, I will rebase this PR.