tests: improve fe_sqr test (issue #1472)

theStack commented at 1:05 am on February 1, 2024: contributor

As pointed out in issue #1472, currently the run_sqr test doesn’t do anything with the result of the fe_sqr call. Improve that by checking that the equation (x+y)*(x-y) = x^2 - y^2 holds for some random values y, as suggested by real-or-random in #1472 (comment). The existing loop for generating the x values is kept as-is, the sqr call on x is still included in each iteration on the course of calulating the RHS of the equation (secp256k1_fe_sqr(&rhs, &x);).

The suggestion says “for random values y != 0”, but I couldn’t see a good reason to exclude zero. Happy to apply s/random_fe_test/random_fe_non_zero_test/ if needed.

real-or-random commented at 8:48 am on February 1, 2024: contributor

Nice!

The suggestion says “for random values y != 0”, but I couldn’t see a good reason to exclude zero. Happy to apply s/random_fe_test/random_fe_non_zero_test/ if needed.

Ah, this is because fe_mul(_, a, b) cannot handle the case when a is equal to b: https://github.com/bitcoin-core/secp256k1/blob/master/src/field.h#L255-L263

In fact, this is why I suggested the binomial equation. Otherwise, the most natural test would just be x*x = x^2.

I mean, it doesn’t matter for truly random y, but we should still call random_fe_non_zero_test instead. (This reminds me that we could consider biasing the test random function towards zero and other corner cases, but that’s a different project…)

real-or-random added the label assurance on Feb 1, 2024

theStack commented at 10:32 am on February 1, 2024: contributor

The suggestion says “for random values y != 0”, but I couldn’t see a good reason to exclude zero. Happy to apply s/random_fe_test/random_fe_non_zero_test/ if needed.

Ah, this is because fe_mul(_, a, b) cannot handle the case when a is equal to b: https://github.com/bitcoin-core/secp256k1/blob/master/src/field.h#L255-L263

Oh, my interpretation of this was that a and b can’t point to the same object. If a can’t be equal to b for this function to succeed, wouldn’t we need to check for a != b prior each call to ensure that fe_mul doesn’t fail? (For all values, not just for zero?)

real-or-random commented at 1:05 pm on February 1, 2024: contributor

Oh nevermind, you’re right. :D Sorry, this was a brain fart. And indeed, this would be pretty bad.

Now that you have implemented it, I still think that (x+y)*(x-y) = x^2 - y^2 is a nice test. It gets us a good test for two sqr operations for the price of 1 mul. ;)

edit: Perhaps the docs can be improved: Pointers r and a may point to the same object, but neither may point to the object pointed to by b. If you like, add a commit here.

What adds to the confusion is that we denote both the field element and the pointer by a. (We could say *a for the element, but changing this everywhere may be overkill. We talk about the pointers only rarely…)

real-or-random approved

real-or-random commented at 1:11 pm on February 1, 2024: contributor

utACK b702461a8ddd45c6edcf45627200e52e78985947

theStack commented at 2:00 pm on February 1, 2024: contributor

edit: Perhaps the docs can be improved: Pointers r and a may point to the same object, but neither may point to the object pointed to by b. If you like, add a commit here.

Thanks, added that as extra commit. Agree that it’s clearer this way.

real-or-random approved

real-or-random commented at 2:00 pm on February 1, 2024: contributor

utACK 7dcb3a8326507c2cd267cda7d333f8e261568f9b

jonasnick approved

jonasnick commented at 3:25 pm on February 27, 2024: contributor

jonasnick changes_requested

jonasnick commented at 3:28 pm on February 27, 2024: contributor

Needs rebase (due to check_fe_equal not existing anymore in master)

tests: improve fe_sqr test

Currently the `run_sqr` test doesn't do anything with the
result of the `fe_sqr` call. Improve that by checking that
the equation `(x+y)*(x-y) = x^2 - y^2` holds for some random
values y, as suggested in issue #1471 by real-or-random.
The existing loop for generating the x values is kept as-is.

11420a7a28

doc: clarify input requirements for secp256k1_fe_mul

"... neither can be equal to b." could suggest that the values are not
allowed to be identical, but what is meant here is that the mentioned
inputs shouldn't point to the same object.

2028069df2

theStack force-pushed on Feb 27, 2024

theStack commented at 3:43 pm on February 27, 2024: contributor

Needs rebase (due to check_fe_equal not existing anymore in master)

Thanks, done.

 0$ git range-diff 7dcb3a8...2028069       
 1-:  ------- > 1:  00111c9 tests: add missing fe comparison checks for inverse field test cases
 2-:  ------- > 2:  e7bdddd refactor: rename `check_fe_equal` -> `fe_equal`
 3-:  ------- > 3:  e7ea32e msan: Add SECP256K1_CHECKMEM_MSAN_DEFINE which applies to memory sanitizer and not valgrind
 4-:  ------- > 4:  31ba404 msan: notate variable assignments from assembly code
 51:  b702461 ! 5:  11420a7 tests: improve fe_sqr test
 6    @@ src/tests.c: static void run_fe_mul(void) {
 7     +        secp256k1_fe_negate(&tmp, &tmp, 1); /* tmp = -y^2 */
 8     +        secp256k1_fe_add(&rhs, &tmp);       /* rhs = x^2 - y^2 */
 9     +
10    -+        CHECK(check_fe_equal(&lhs, &rhs));
11    ++        CHECK(fe_equal(&lhs, &rhs));
12          }
13      }
14      
152:  7dcb3a8 = 6:  2028069 doc: clarify input requirements for secp256k1_fe_mul

real-or-random approved

real-or-random commented at 3:57 pm on February 27, 2024: contributor

utACK 2028069df2e16a05b332ae24c7ae63791f461063

jonasnick approved

jonasnick commented at 5:14 pm on February 27, 2024: contributor

ACK 2028069df2e16a05b332ae24c7ae63791f461063

jonasnick merged this on Feb 27, 2024

jonasnick closed this on Feb 27, 2024

theStack deleted the branch on Feb 27, 2024

tests: improve fe_sqr test (issue #1472) #1490