Eliminate the use of points and scalars from secp256k1_ecmult_strauss

roconnor-blockstream commented at 1:29 pm on March 1, 2021: contributor

We have secp256k1_ecmult_strauss_wnaf invoke the callback itself.

This builds upon PR #899.

roconnor-blockstream force-pushed on Mar 1, 2021

in src/ecmult_impl.h:82 in c531ff8fb9 outdated

81@@ -82,7 +82,7 @@
82  *  contain prej[0].z / a.z. The other zr[i] values = prej[i].z / prej[i-1].z.

sipa commented at 7:09 pm on March 7, 2021:

In commit c531ff8fb96cdaa871e637631a346bb1352cca3d:

The documentation above secp256k1_ecmult_odd_multiples_table is now outdated (it is only fixed in the next commit, I believe).

roconnor-blockstream commented at 11:14 pm on March 7, 2021:

It’s probably because I don’t know how to GitHub, but I intended for these comments to end up on #899 instead.

roconnor-blockstream commented at 7:25 pm on March 29, 2021:

Done.

in src/group.h:69 in c531ff8fb9 outdated

76  *  the same global z "denominator". zr must contain the known z-ratios such
77- *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored. The x and y
78- *  coordinates of the result are stored in r, the common z coordinate is
79- *  stored in globalz. */
80-static void secp256k1_ge_globalz_set_table_gej(size_t len, secp256k1_ge *r, secp256k1_fe *globalz, const secp256k1_gej *a, const secp256k1_fe *zr);
81+ *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored.

sipa commented at 7:12 pm on March 7, 2021:

In c531ff8fb96cdaa871e637631a346bb1352cca3d:

perhaps document which global z everything is set to?

roconnor-blockstream commented at 7:25 pm on March 29, 2021:

Done.

roconnor-blockstream force-pushed on Mar 29, 2021

roconnor-blockstream cross-referenced this on Mar 29, 2021 from issue Reduce stratch space needed by ecmult_strauss_wnaf. by roconnor-blockstream

roconnor-blockstream force-pushed on Mar 30, 2021

roconnor-blockstream force-pushed on May 12, 2021

roconnor-blockstream force-pushed on Aug 28, 2021

in src/ecmult_impl.h:430 in 3652cec456 outdated

438-    state.pre_a_lam = (secp256k1_ge*)secp256k1_scratch_alloc(error_callback, scratch, n_points * ECMULT_TABLE_SIZE(WINDOW_A) * sizeof(secp256k1_ge));
439     state.ps = (struct secp256k1_strauss_point_state*)secp256k1_scratch_alloc(error_callback, scratch, n_points * sizeof(struct secp256k1_strauss_point_state));
440 
441-    if (points == NULL || scalars == NULL || state.prej == NULL || state.zr == NULL || state.pre_a == NULL || state.pre_a_lam == NULL || state.ps == NULL) {
442+    if (state.aux == NULL || state.pre_a == NULL || state.ps == NULL ||
443+            !secp256k1_ecmult_strauss_wnaf(&state, r, n_points, &secp256k1_ecmult_adaptor_cb, &adaptor_data, cb_offset, inp_g_sc)) {

robot-dreams commented at 4:29 pm on December 1, 2021:

If you’re checking the return value of secp256k1_ecmult_strauss_wnaf when you call it here, would you also need to check it when you call it at the end of secp256k1_ecmult?

My concern is that if the callback (and thus the call to secp256k1_ecmult_strauss_wnaf) “fails”, this could either (1) introduce a way for secp256k1_ecmult to fail unexpectedly, or (2) force secp256k1_ecmult to return int instead of void, and either way this would break the “public” API.

robot-dreams commented at 10:24 pm on December 1, 2021: contributor

I only reviewed the last 2 commits, since the rest are from #899 .

I think the callback/adaptor is a nice idea for optimizing space usage, but my main concern is about possibly breaking the “public” API (see inline comment).

A quick check of ./bench_ecmult strauss_wnaf at three different versions shows that there are no immediately obvious performance regressions:

Plot

roconnor-blockstream force-pushed on Dec 3, 2021

Eliminate the prej array from ecmult_strauss_wnaf. 350ceba091

Remove the unused prej allocations. ee03b344e7

Eliminate the pre_a_lam array from ecmult_strauss_wnaf. c48a9f0056

Remove the unused pre_a_lam allocations. 508f659a62

Eliminate na_1 and na_lam state fields from ecmult_strauss_wnaf. 80e91931f4

Eliminate input_pos state field from ecmult_strauss_wnaf. 5aea2e854e

Eliminate the use of points and scalars from secp256k1_ecmult_strauss_batch.

We have secp256k1_ecmult_strauss_wnaf invoke the callback itself.

8242379f22

Remove the unused points and scalars allocation from secp256k1_ecmult_strauss_batch. 29a1b7e60b

roconnor-blockstream force-pushed on Dec 8, 2021

roconnor-blockstream commented at 2:54 pm on January 28, 2022: contributor

I’m going to close this PR. I don’t feel like pursing it; I’m not really convinced it is worthwhile. If, for whatever reason, someone disagree and does think it is worthwhile, feel free to take it over.

roconnor-blockstream closed this on Jan 28, 2022

Eliminate the use of points and scalars from secp256k1_ecmult_strauss_batch. #900