group: save normalize_weak calls in `secp256k1_ge_is_valid_var`/`secp256k1_gej_eq_x

theStack commented at 10:39 pm on June 12, 2023: contributor

This PR removes unneeded normalize_weak calls in two group element functions:

secp256k1_ge_is_valid_var: After calculating the right-hand side of the elliptic curve equation (x^3 + 7), the field element x3 has a magnitude of 2 (1 as result of secp256k1_fe_mul, then increased by 1 due to secp256k1_fe_add_int). This is fine for secp256k1_fe_equal_var, as the second parameter only requires the magnitude to not exceed 31, and the normalize_weak call is hence not needed and can be dropped. Note that the interface description for secp256k1_fe_equal (which also applies to secp256k1_fe_equal_var) once stated that both parameters need to have magnitude 1, but that was corrected in commit 7d7d43c6dd2741853de4631881d77ae38a14cd23.
secp256k1_gej_eq_x_var: By requiring that the input group element’s X coordinate (a->x) has a magnitude of <= 31, the normalize_weak call and also the field element variable r2 are not needed anymore and hence can be dropped.

group: remove unneeded normalize_weak in `secp256k1_ge_is_valid_var`

After calculating the right-hand side of the elliptic curve equation
(x^3 + 7), the field element `x3` has a magnitude of 2 (1 as result of
`secp256k1_fe_mul`, then increased by 1 due to `secp256k1_fe_add_int`).
This is fine for `secp256k1_fe_equal_var`, as the second parameter only
requires the magnitude to not exceed 31, and the normalize_weak call can
hence be dropped.

efa76c4bf7

real-or-random added the label performance on Jun 14, 2023

real-or-random commented at 10:30 am on June 14, 2023: contributor

Concept ACK

I think secp256k1_gej_eq_x_var can be simplified as well. Do you want to have a look?

theStack commented at 2:01 pm on June 14, 2023: contributor

I think secp256k1_gej_eq_x_var can be simplified as well. Do you want to have a look?

Sure! It seems that the normalize_weak call (and r2) could be dropped only if we knew that a->x has a magnitude of <= 31:

https://github.com/bitcoin-core/secp256k1/blob/67214f5f7d8e0bdf193ceb1f47ba8277d1a0871a/src/group_impl.h#L316-L324

Is there a general guarantee about the magnitudes of gej members (in this case, ‘x’ specifically)? If not, would it make sense to add this as a precondition? E.g. something like:

 0diff --git a/src/group_impl.h b/src/group_impl.h
 1index 44d9843..25e84b1 100644
 2--- a/src/group_impl.h
 3+++ b/src/group_impl.h
 4@@ -314,13 +314,15 @@ static int secp256k1_gej_eq_var(const secp256k1_gej *a, const secp256k1_gej *b)
 5 }
 6
 7 static int secp256k1_gej_eq_x_var(const secp256k1_fe *x, const secp256k1_gej *a) {
 8-    secp256k1_fe r, r2;
 9+    secp256k1_fe r;
10     secp256k1_fe_verify(x);
11     secp256k1_gej_verify(a);
12     VERIFY_CHECK(!a->infinity);
13     secp256k1_fe_sqr(&r, &a->z); secp256k1_fe_mul(&r, &r, x);
14-    r2 = a->x; secp256k1_fe_normalize_weak(&r2);
15-    return secp256k1_fe_equal_var(&r, &r2);
16+#ifdef VERIFY
17+    VERIFY_CHECK(a->x.magnitude <= 31);
18+#endif
19+    return secp256k1_fe_equal_var(&r, &a->x);
20 }
21
22 static void secp256k1_gej_neg(secp256k1_gej *r, const secp256k1_gej *a) {

Tests still seem to pass.

real-or-random commented at 2:25 pm on June 14, 2023: contributor

Is there a general guarantee about the magnitudes of gej members (in this case, ‘x’ specifically)? If not, would it make sense to add this as a precondition?

There’s no specific guarantee for gej members, we only have the general guarantee that magnitudes are <=32 (see field.h). When I wrote that comment above, I was off by one and assumed we only need <=32. But yes, I think it makes sense to require that requirement to the function. That makes the function a bit less generic, but it’s used in ECDSA verification, so performance is interesting here.

Your suggestion is almost perfect except the nits that we usually have the precondition checks at the beginning of the function (see e.g. https://github.com/bitcoin-core/secp256k1/blob/master/src/field_impl.h#L60-L64) and that the precondition should be documented, of course.

sipa commented at 3:30 pm on June 14, 2023: contributor

@theStack You may be interested in #1032.

theStack force-pushed on Jun 14, 2023

theStack renamed this:
~~group: remove unneeded normalize_weak in `secp256k1_ge_is_valid_var`~~
group: speedup pubkey parsing / ECDSA verification by removing unneeded normalize_weak calls
on Jun 14, 2023

theStack commented at 4:45 pm on June 14, 2023: contributor

Is there a general guarantee about the magnitudes of gej members (in this case, ‘x’ specifically)? If not, would it make sense to add this as a precondition?

There’s no specific guarantee for gej members, we only have the general guarantee that magnitudes are <=32 (see field.h). When I wrote that comment above, I was off by one and assumed we only need <=32. But yes, I think it makes sense to require that requirement to the function. That makes the function a bit less generic, but it’s used in ECDSA verification, so performance is interesting here.

Your suggestion is almost perfect except the nits that we usually have the precondition checks at the beginning of the function (see e.g. https://github.com/bitcoin-core/secp256k1/blob/master/src/field_impl.h#L60-L64) and that the precondition should be documented, of course.

Thanks, added a second commit for the proposed change in secp256k1_gej_eq_x_var and addressed the nits. Also adapted the PR title / description accordingly, to express better what these changes actually achieve.

@theStack You may be interested in #1032.

Looks interesting indeed. Seems like this is in “waiting for author” status for quite a while, but maybe it’s worthwhile to pick it up.

real-or-random commented at 5:42 pm on June 14, 2023: contributor

The second change makes ECDSA verification a little faster. On my machine:

Oh, that’s more than 5%. I haven’t run benchmarks on my machine, but didn’t except that it will be that significant.

edit:

maybe it’s worthwhile to pick it up.

That would be nice if you’re interested.

theStack commented at 6:13 pm on June 14, 2023: contributor

The second change makes ECDSA verification a little faster. On my machine:

Oh, that’s more than 5%. I haven’t run benchmarks on my machine, but didn’t except that it will be that significant.

Have to say that I ran these benchmarks on a VPS instance (i.e. I no physical access, no control what the actual CPUs are doing) so there could be some fluctuation and the results probably have to be taken with a grain of salt. Will re-benchmark on my physical machine at home with CPU frequency scaling disabled to get clearer results.

real-or-random approved

real-or-random commented at 1:28 pm on June 15, 2023: contributor

ACK https://github.com/bitcoin-core/secp256k1/pull/1344/commits/205e2c8f1b3f2f696851a42d449db2a04867ef2e

I only did a quick’n’dirty benchmark, but I can’t measure an improvement in ecdsa_verify.

theStack commented at 2:26 pm on June 15, 2023: contributor

I only did a quick’n’dirty benchmark, but I can’t measure an improvement in ecdsa_verify.

Right, did now several runs on two different machines with CPU frequency scaling disabled and also can’t confirm any speed-up anymore :/ Seems presenting the first benchmark result was too rushed, caused by my excitement – sorry for creating wrong expectations there. Will change the PR title once again, as “speedup” doesn’t apply.

theStack renamed this:
~~group: speedup pubkey parsing / ECDSA verification by removing unneeded normalize_weak calls~~
group: save normalize_weak calls in `secp256k1_ge_is_valid_var`/`secp256k1_gej_eq_x_var`
on Jun 15, 2023

real-or-random commented at 2:35 pm on June 15, 2023: contributor

sorry for creating wrong expectations there. Will change the PR title once again, as “speedup” doesn’t apply.

No worries, it was me who suggested that it could make a difference. And saving a few ops is certainly a speedup, just apparently not a large one.

jonasnick commented at 2:03 pm on July 3, 2023: contributor

ACK efa76c4bf7cab1c22aa476cd2730e891450ad4a0 (the first commit)

As for the second commit, I don’t see a speedup either:

0This PR @ 205e2c8f1b3f2f696851a42d449db2a04867ef2e
1ecdsa_verify                  ,    71.6       ,    71.6       ,    71.6
2
3master
4ecdsa_verify                  ,    71.5       ,    71.5       ,    71.5

Given that @theStack and @real-or-random don’t see a speedup either, it would be best to remove the claim from the commit message.

I’m wondering if putting magnitude restrictions on group functions is justified if there’s no speedup. It seems like a layer violation.

It seems like it would be cleaner to do this change when #1032 is merged. Then we wouldn’t even need to document the magnitude requirements, since #1032 makes sure that the coordinates of group elements are always below some value <= 31.

real-or-random commented at 2:35 pm on July 3, 2023: contributor

Then we wouldn’t even need to document the magnitude requirements, since #1032 makes sure that the coordinates of group elements are always below some value <= 31.

See #1348 for a revival of PR #1032. But it enforces <= 32 (and not 31).

I’m wondering if putting magnitude restrictions on group functions is justified if there’s no speedup. It seems like a layer violation.

I think many group functions already have some magnitude requirements. (For example, secp256k1_gej_add_var starts with a fe_sqr on the Z coord.) Those requirements are just never explicitly documented in the header. That’s why I don’t think the second commit here changes anything fundamentally. Of course, we can still have doubt whether it improves anything.

sipa commented at 2:41 pm on July 3, 2023: contributor

I also think we see secp256k1_ge as an “open” data structure, in the sense that its users know, rely on, and access its fields (.x, .y, .z, .infinity), and the group.h file functions are just helpers to do useful things with them, rather than a full abstraction. In that sense there is no layer violation, as there is no real layer.

This is different from the secp256k1_fe type which is fully abstracted, and its users are not supposed to access the internals at all.

group: remove unneeded normalize_weak in `secp256k1_gej_eq_x_var`

By requiring that the input group element's X coordinate (`a->x`) has a
magnitude of <= 31, the normalize_weak call and also the field element
variable `r2` are not needed anymore and hence can be dropped.

07c0e8b82e

theStack force-pushed on Jul 3, 2023

jonasnick commented at 2:55 pm on July 3, 2023: contributor

But it enforces <= 32 (and not 31).

It seems to enforce that the x-coordinate’s magnitude does not exceed 6. @sipa If it’s considered an “open datastructure” it’s even more important to keep the group interface simple.

However, in light of #1348, the special restriction on secp256k1_gej_eq_x_var would only be temporary. So I’d be fine with ACK’ing this (once the commit message is fixed).

theStack commented at 2:57 pm on July 3, 2023: contributor

Given that @theStack and @real-or-random don’t see a speedup either, it would be best to remove the claim from the commit message.

Thanks for noticing, dropped the misleading results from the second commit message now.

jonasnick approved

jonasnick commented at 3:00 pm on July 3, 2023: contributor

ACK 205e2c8f1b3f2f696851a42d449db2a04867ef2e

sipa commented at 5:43 pm on July 3, 2023: contributor

utACK 07c0e8b82e2cea87f85263512945fed7adffea18

real-or-random commented at 5:56 pm on July 3, 2023: contributor

ACK 205e2c8

old commit? @jonasnick

jonasnick commented at 6:02 pm on July 3, 2023: contributor

ACK 07c0e8b82e2cea87f85263512945fed7adffea18

real-or-random merged this on Jul 4, 2023

real-or-random closed this on Jul 4, 2023

theStack deleted the branch on Jul 4, 2023

fanquake referenced this in commit 56c05c5ec4 on Jul 17, 2023

fanquake referenced this in commit ff061fde18 on Jul 18, 2023

hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023

jonasnick cross-referenced this on Jul 27, 2023 from issue Upstream PRs 1357, 1345, 1358, 1368, 1369, 1323, 1364, 1370, 1367, 1344, 1371, 1363, 1340, 1366, 1313, 1378, 1298, 1382, 1383, 1384, 1386 by jonasnick

group: save normalize_weak calls in secp256k1_ge_is_valid_var/secp256k1_gej_eq_x_var #1344

group: save normalize_weak calls in `secp256k1_ge_is_valid_var`/`secp256k1_gej_eq_x_var` #1344