Reduce stratch space needed by ecmult_strauss

roconnor-blockstream commented at 8:23 pm on February 26, 2021: contributor

roconnor-blockstream force-pushed on Feb 26, 2021

roconnor-blockstream marked this as ready for review on Feb 26, 2021

roconnor-blockstream renamed this:
~~WIP: Eliminate the prej array from ecmult_strauss_wnaf.~~
Eliminate the prej array from ecmult_strauss_wnaf.
on Feb 26, 2021

roconnor-blockstream force-pushed on Feb 26, 2021

roconnor-blockstream renamed this:
~~Eliminate the prej array from ecmult_strauss_wnaf.~~
Reduce stratch space needed by ecmult_strauss_wnaf.
on Feb 27, 2021

roconnor-blockstream force-pushed on Feb 28, 2021

roconnor-blockstream force-pushed on Mar 1, 2021

roconnor-blockstream cross-referenced this on Mar 1, 2021 from issue Eliminate the use of points and scalars from secp256k1_ecmult_strauss_batch. by roconnor-blockstream

roconnor-blockstream force-pushed on Mar 29, 2021

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

Address @sipa ’s comments from #900.

Please review this PR first.

roconnor-blockstream force-pushed on Mar 30, 2021

roconnor-blockstream commented at 8:22 pm on April 6, 2021: contributor

@real-or-random observes that STRAUSS_SCRATCH_OBJECTS needs to be updated.

roconnor-blockstream force-pushed on May 12, 2021

roconnor-blockstream commented at 3:48 pm on May 12, 2021: contributor

Rebased and updated STRAUSS_SCRATCH_OBJECTS.

roconnor-blockstream force-pushed on Aug 28, 2021

roconnor-blockstream commented at 6:07 pm on August 28, 2021: contributor

rebased.

in src/ecmult_impl.h:66 in ef18beeaed outdated

65+ *  The a value will end up equal to pre_a[(2*n-1)].
66+ *  The output pre_a array will have their z-coordinate omitted.
67+ *  The omitted z-coordinate are implied by the final a value's z-coordinate and the zr array.
68  */
69-static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a) {
70+static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_ge *pre_a, secp256k1_fe *zr, secp256k1_gej *a) {

robot-dreams commented at 6:03 am on December 1, 2021:

Style nit (feel free to ignore): Instead of making a mutable, would it make sense to have an output parameter for the final z value, since that’s the only part of a that gets read later?

roconnor-blockstream commented at 2:19 pm on December 1, 2021:

I have learned that returning structures is frowned upon in C.

robot-dreams commented at 3:17 pm on December 1, 2021:

Oh yeah, I agree with you about that. What I was suggesting is to have an extra parameter to the function that’s a pointer like secp256k1_fe *global_z (or maybe z_final), instead of updating a in place.

roconnor-blockstream commented at 10:47 pm on December 3, 2021:

Done. I’m a little tempted to take z as an input and rescale the a value by its value, but it is probably best to leave it as is.

in src/group.h:70 in ef18beeaed outdated

70- *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored. The x and y
71- *  coordinates of the result are stored in r, the common z coordinate is
72- *  stored in globalz. */
73-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);
74+ *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored.
75+ *  The common z coordinate is the (implicit) z coordinate of a[len-2], and therefore

robot-dreams commented at 6:43 am on December 1, 2021:

Should this say a[len-1] instead of a[len-2]?

roconnor-blockstream commented at 10:45 pm on December 3, 2021:

Fixed.

in src/ecmult_impl.h:305 in fff364f311 outdated

305 
306     for (np = 0; np < no; ++np) {
307         for (i = 0; i < ECMULT_TABLE_SIZE(WINDOW_A); i++) {
308-            secp256k1_ge_mul_lambda(&state->pre_a_lam[np * ECMULT_TABLE_SIZE(WINDOW_A) + i], &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i]);
309+            secp256k1_ge pre_a_lam;
310+            secp256k1_ge_mul_lambda(&pre_a_lam, &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i]);

robot-dreams commented at 7:01 am on December 1, 2021:

Style nit (feel free to ignore): I’m on the fence about this, but do you think it’s worth expressing this as just a field multiplication by beta?

0secp256k1_fe_mul(
1    &state->aux[np * ECMULT_TABLE_SIZE(WINDOW_A) + i],
2    &state->pre_a[np * ECMULT_TABLE_SIZE(WINDOW_A) + i],
3    beta)

roconnor-blockstream commented at 9:47 pm on December 1, 2021:

I think it is a good idea. The major problem is that beta is not available as a global constant, but probably it should be.

roconnor-blockstream commented at 10:46 pm on December 3, 2021:

Done.

in src/ecmult_impl.h:96 in 1cd7ab2c81 outdated

100 
101-    /*
102-     * Each point in 'prej' has a z coordinate too small by a factor of 'd.z'. Only
103-     * the final point's z coordinate is actually used though, so just update that.
104-     */
105-    secp256k1_fe_mul(&prej[n-1].z, &prej[n-1].z, &d.z);

robot-dreams commented at 7:12 am on December 1, 2021:

Is it worth keeping at least some version of this comment? For example:

0    /*
1     * Multiply by d.z to undo the isomorphism that makes 'd' affine.
2     */

roconnor-blockstream commented at 10:48 pm on December 3, 2021:

Done.

in src/group.h:89 in 1cd7ab2c81 outdated

73-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);
74+ *  that mul(a[i].z, zr[i+1]) == a[i+1].z. zr[0] is ignored.
75+ *  The common z coordinate is the (implicit) z coordinate of a[len-2], and therefore
76+ *  the coordinates of a[len-1] are not changed.
77+ */
78+static void secp256k1_ge_globalz_fixup_table(size_t len, secp256k1_ge *a, const secp256k1_fe *zr);

robot-dreams commented at 7:39 am on December 1, 2021:

Is it also worth mentioning that a[len - 1] implicitly has z = 1 (which is why it’s enough for this function to accept a _ge rather than _gej, without even taking in a Z value)?

roconnor-blockstream commented at 9:58 pm on December 3, 2021:

This isn’t correct. The implicit z value is the “global Z” value returned in secp256k1_ecmult_odd_multiples_table.

robot-dreams commented at 10:33 pm on December 3, 2021:

I’m probably using “implicit” incorrectly, I was taking into account this comment:

Each point in 'prej' has a z coordinate too small by a factor of 'd.z'.

https://github.com/bitcoin-core/secp256k1/blob/master/src/ecmult_impl.h#L93

roconnor-blockstream commented at 10:42 pm on December 3, 2021:

The way I think of it is that a is an array of points with unknown z-coordinates, but known ratios of these z-coordinates. But that is good enough to rescale all the points so that they end up all sharing the same z-coordinate of the last entry, whatever it is.

robot-dreams commented at 7:41 am on December 1, 2021: contributor

Concept ACK, secp256k1_ecmult_strauss_wnaf indeed uses scratch space more efficiently with this change.

I ran ./bench_ecmult strauss_wnaf at both 1cd7ab2c81b7a7089709b67638a596b8337d0b41 and 9a5a87e0f1276e0284446af1172056ea4693737f just to make sure there’s no obvious regression in running time.

Unfortunately it looks like this might have some merge conflicts with #638 depending on which gets merged first.

roconnor-blockstream force-pushed on Dec 3, 2021

in src/ecmult_impl.h:83 in 5e44ef6c76 outdated

79@@ -78,22 +80,22 @@ static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, sec
80     d_ge.y = d.y;
81     d_ge.infinity = 0;
82 
83+    ai = *a;

robot-dreams commented at 11:24 pm on December 5, 2021:

 0    /*
 1     * Perform the additions using an isomorphism that divides the z coordinate by the
 2     * constant d.z. The group law is the same in the image, and since 'd' maps to an
 3     * affine point, addition becomes more efficient (using mixed coordinates).
 4     *
 5     *     phi(x, y, z) = (x, y, z/d.z)
 6     *           phi(d) = (d.x, d.y, 1)
 7     *           phi(a) = (a.x, a.y, a.z/d.z) = (a.x*d.z^2, a.y*d.z^3, a.z)
 8     */
 9    secp256k1_ge_set_xy(&d_ge, &d.x, &d.y);
10    secp256k1_ge_set_gej_zinv(&a_ge, a, &d.z);
11    secp256k1_gej_set_ge(&ai, &a_ge);
12    ai.z = a->z;
13
14    zr[0] = d.z;
15    secp256k1_ge_set_xy(&pre_a[0], &ai.x, &ai.y);
16    for (i = 1; i < n; i++) {
17        secp256k1_gej_add_ge_var(&ai, &ai, &d_ge, &zr[i]);
18        secp256k1_ge_set_xy(&pre_a[i], &ai.x, &ai.y);
19    }

in src/ecmult_impl.h:73 in 5e44ef6c76 outdated

66+ *  The output pre_a array will have their z-coordinate omitted.
67+ *  The omitted z-coordinates are implied by the final z coordinate and the zr array.
68  */
69-static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_gej *prej, secp256k1_fe *zr, const secp256k1_gej *a) {
70-    secp256k1_gej d;
71+static void secp256k1_ecmult_odd_multiples_table(int n, secp256k1_ge *pre_a, secp256k1_fe *zr, secp256k1_fe *z, const secp256k1_gej *a) {

robot-dreams commented at 11:57 pm on December 5, 2021:

 0/** Fill a table 'pre_a' with precomputed odd multiples of a.
 1 *  pre_a will contain [1*a,3*a,...,(2*n-1)*a], so it needs space for n group elements.
 2 *  zr needs space for n field elements.
 3 *
 4 *  Although pre_a is an array of _ge rather than _gej, it actually represents elements
 5 *  in Jacobian coordinates with their z coordinates omitted. The omitted z-coordinates
 6 *  can be recovered using z and zr. Using the notation z(b) to represent the omitted
 7 *  z coordinate of b:
 8 *  - 'z' = z(pre_a[n-1])
 9 *  - 'zr[i]' = z(pre_a[i]) / z(pre_a[i-1]) for i > 0
10 *  - 'zr[0]' = z(pre_a[0]) / a.z
11 */

in src/group.h:67 in 5e44ef6c76 outdated

63@@ -64,12 +64,13 @@ static void secp256k1_ge_set_gej_var(secp256k1_ge *r, secp256k1_gej *a);
64 /** Set a batch of group elements equal to the inputs given in jacobian coordinates */
65 static void secp256k1_ge_set_all_gej_var(secp256k1_ge *r, const secp256k1_gej *a, size_t len);
66 
67-/** Bring a batch inputs given in jacobian coordinates (with known z-ratios) to
68+/** Bring a batch inputs given in coordinates (with known z-ratios) to

robot-dreams commented at 3:28 am on December 6, 2021:

 0/** Bring a batch of inputs to the same global z "denominator", based on ratios between
 1 *  (omitted) z coordinates of adjacent elements.
 2 *
 3 *  Although the elements a[i] are _ge rather than _gej, they actually represent elements
 4 *  in Jacobian coordinates with their z coordinates omitted.
 5 *
 6 *  Using the notation z(b) to represent the omitted z coordinate of b, the array zr of
 7 *  z coordinate ratios must satisfy mul(z(a[i]), zr[i+1]) == z(a[i+1]).
 8 *
 9 *  This function modifies 'a' in place so that for all i, z(a[i]) == z(a[len-1]). In other
10 *  words, the initial value of z(a[len-1]) becomes the global z "denominator". Since the
11 *  a[i] don't have z coordinates, we "change the z coordinate" by indirectly, by scaling
12 *  a[i].x and a[i].y based on the known ratios zr.
13 *
14 *  The coordinates of the final element a[len-1] are not changed.
15 */

in src/group_impl.h:170 in 5e44ef6c76 outdated

171-        r[i].y = a[i].y;
172         /* Ensure all y values are in weak normal form for fast negation of points */
173-        secp256k1_fe_normalize_weak(&r[i].y);
174-        *globalz = a[i].z;
175-        r[i].infinity = 0;
176+        secp256k1_fe_normalize_weak(&a[i].y);

robot-dreams commented at 3:31 am on December 6, 2021:

Probably out of scope for this PR, but why is it sufficient to call fe_normalize_weak on a[len-1] only, and none of the remaining elements?

peterdettman commented at 5:05 am on December 6, 2021:

The other elements will each get their y value scaled by multiplication in secp256k1_ge_set_gej_zinv, which will already give a magnitude of 1. Although this is somewhat implicit knowledge, the main consumer is the ECMULT_TABLE_GET_GE macro where the _fe_negate call requires the magnitude to be 1.

Unfortunately that’s only IF a point is ever needed negated, so I think we could do with a static VERIFY check somewhere. #1032 should help lead in that direction.

in src/field_impl.h:140 in 37b572fabb outdated

135@@ -136,5 +136,9 @@ static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
136 }
137 
138 static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
139+static const secp256k1_fe secp256k1_const_beta = SECP256K1_FE_CONST(
140+        0x7ae96a2bul, 0x657c0710ul, 0x6e64479eul, 0xac3434e9ul,

robot-dreams commented at 4:13 am on December 6, 2021:

Nit: deindent?

roconnor-blockstream commented at 10:29 pm on December 8, 2021:

Done.

robot-dreams commented at 4:34 am on December 6, 2021: contributor

OK, I took another look and I think I have a better understanding now. This PR looks pretty solid.

I left a few suggestions for comments / style, mostly because I thought some parts were confusing even before your PR. If you prefer I can also push them to some branch as a follow-up commit.

roconnor-blockstream force-pushed on Dec 8, 2021

roconnor-blockstream commented at 6:36 pm on December 8, 2021: contributor

Thanks @robot-dreams. I’ve taken your suggestions and made some minor adjustments to them.

in src/group.h:13 in 5aea2e854e outdated

 8@@ -9,7 +9,10 @@
 9 
10 #include "field.h"
11 
12-/** A group element of the secp256k1 curve, in affine coordinates. */
13+/** A group element in affine coordinates on the secp256k1 curve,
14+ *  or occasionally on an isomorphic curve of the from y^2 = x^3 + 7*t^6.

robot-dreams commented at 11:24 pm on December 8, 2021:

Nit: from -> form

roconnor-blockstream commented at 3:16 pm on December 9, 2021:

Done.

in src/group.h:14 in 5aea2e854e outdated

 8@@ -9,7 +9,10 @@
 9 
10 #include "field.h"
11 
12-/** A group element of the secp256k1 curve, in affine coordinates. */
13+/** A group element in affine coordinates on the secp256k1 curve,
14+ *  or occasionally on an isomorphic curve of the from y^2 = x^3 + 7*t^6.
15+ *  Note: For exhastive test mode, sepc256k1 is replaced by a small subgroup of a different curve.

robot-dreams commented at 11:31 pm on December 8, 2021:

Nit: exhastive -> exhaustive, sepc256k1 -> secp256k1

roconnor-blockstream commented at 3:16 pm on December 9, 2021:

Done.

robot-dreams commented at 11:46 pm on December 8, 2021: contributor

ACK 5aea2e854e3db0d60416b3118eb5949b315103ef (from inspecting the range diff against ae332324f16f908ddf3b340274816c8edb26738a)

roconnor-blockstream force-pushed on Dec 9, 2021

robot-dreams commented at 2:20 am on December 10, 2021: contributor

ACK b6ed302caf39e95b960ac4383654a710ab2d8737

sipa cross-referenced this on Dec 18, 2021 from issue Add another ecmult_multi test by sipa

in src/group.h:89 in b6ed302caf outdated

90+ *  a[i].x and a[i].y coordinates are explicitly modified; the adjustment of the omitted z coordinate is
91+ *  implicit.
92+ *
93+ *  The coordinates of the final element a[len-1] are not changed.
94+ */
95+static void secp256k1_ge_globalz_fixup_table(size_t len, secp256k1_ge *a, const secp256k1_fe *zr);

jonasnick commented at 1:36 pm on December 23, 2021:

nit: why change the name? fixup would imply to me that there’s something wrong with the input. Perhaps simply ge_table_set_globalz.

roconnor-blockstream commented at 4:35 am on January 19, 2022:

done.

in src/ecmult_impl.h:106 in b6ed302caf outdated

122-    secp256k1_ge_globalz_set_table_gej(ECMULT_TABLE_SIZE(WINDOW_A), pre, globalz, prej, zr);
123+    secp256k1_ecmult_odd_multiples_table(ECMULT_TABLE_SIZE(WINDOW_A), pre, zr, globalz, a);
124+    secp256k1_ge_globalz_fixup_table(ECMULT_TABLE_SIZE(WINDOW_A), pre, zr);
125 }
126 
127 /** The following two macro retrieves a particular odd multiple from a table

jonasnick commented at 1:40 pm on December 23, 2021:

0/** The following macros retrieve a particular odd multiple from a table

While we’re at it, how about moving the VERIFY_CHECKs into

0#define ECMULT_TABLE_VERIFY(n,w) \
1    VERIFY_CHECK(((n) & 1) == 1); \
2    VERIFY_CHECK((n) >= -((1 << ((w)-1)) - 1)); \
3    VERIFY_CHECK((n) <=  ((1 << ((w)-1)) - 1));

?

real-or-random commented at 2:41 pm on December 23, 2021:

Or just turn the macros into functions… I’m not aware of a real reason to use these procedural macros in modern C.*

*Unless you use macros to express things not expressible with a function, e.g., making up identifiers on the fly via string concatenation.

roconnor-blockstream commented at 2:56 pm on January 18, 2022:

I believe we got here as follows. The macro was introduce in https://github.com/bitcoin-core/secp256k1/commit/b1483f874c6111b7d727d6c6cb3df35c16a880bc#diff-1f71a59e139573dfb0695be308c69455971378cd67ad7946a3703cb725b589fdR51 (expand the diff for ecmult.c), where there was a function name argument being passed in. I suppose in that situation a macro makes sense to avoid the use of function pointers?

But this function argument was eliminated in https://github.com/bitcoin-core/secp256k1/commit/41f84554341c3c2f21324da53982b8da045f88e3#diff-dc206b3f5f973b97a0f5c1b12d705d0e58a1cb8c9684e481e7a34fc05e4716aaL63 at which point there is no longer a reason for this to continue to be a macro.

Thus it should be safe for me to convert it into an inline function.

roconnor-blockstream commented at 11:25 pm on January 18, 2022:

Should I move the macros into function and #define ECMULT_TABLE_VERIFY?

jonasnick commented at 11:29 am on January 19, 2022:

That would be ideal I think, but turning the macros to functions isn’t necessary for this PR. I just suggested isolating ECMULT_TABLE_VERIFY because it simplifies review of this PR.

jonasnick commented at 12:28 pm on January 19, 2022:

Looks like you did both, thanks.

in src/ecmult_impl.h:85 in b6ed302caf outdated

89     /*
90-     * Perform the additions on an isomorphism where 'd' is affine: drop the z coordinate
91-     * of 'd', and scale the 1P starting value's x/y coordinates without changing its z.
92+     * Perform the additions using an isomorphism that divides the z coordinate by the
93+     * constant d.z. The group law is the same in the image, and since 'd' maps to an
94+     * affine point, addition becomes more efficient (using mixed coordinates).

jonasnick commented at 1:53 pm on December 23, 2021:

0     * constant d.z. The group law is the same in the image, and since 'd' maps to an
1     * affine point, and since 'd' maps to an affine point, we can use the more
2     * efficient affine addition without a field element inversion to convert 'd' to
3     * an affine point on secp256k1.

roconnor-blockstream commented at 9:09 pm on January 17, 2022:

I’m having trouble following your suggested wording.

We are working on the isomorphic curve y^2 = x^3 + 7*C^6 where C=d.z with our isomorphism sending secp256k1 to this curve is defined by phi(x,y) = (x*C^2, y*C^3). The transformation of some generic point in Jacobian coordinates a := (ax, ay, az) is phi(a) = (ax*C^2,ay*C^3,az) or equivalently phi(a) = (ax,ay,az/C). In particular a set of Jacobian coordinates for phi(d) is (x,y,1) which means the affine coordinates of phi(d) is (x,y). The inverse isomorphism can be applied to a point in Jacobian coordinates by multiplying the z coordinate by C.

We have algorithms for adding two generic points in Jacobian coordinates, and a slightly optimized algorithm for adding a point in Jacobian coordinates with a point in affine coordinates. The optimization amounts to noting that the z value of the point in affine coordinates is 1 and then removing all the places where you would otherwise multiply by 1. Note that we are not adding two affine points, and thus field inversions are not under consideration, nor were they ever under consideration.

That all said, maybe I can try to expand upon this comment to make it more clear. Doing operations on an isomorphic curve is definitely hard to follow.

jonasnick commented at 11:19 am on January 19, 2022:

Sorry for the confusion. Your description of the isomorphism is correct. I am looking for a concise explanation of the optimization which is that we can use the faster gej_add_ge instead of gej_add. Surely we could use the former algorithm without the transformation by doing a field inversion to convert d into a regular ge. Perhaps this point is only confusing and not noteworthy.

jonasnick commented at 12:27 pm on January 19, 2022:

Your new explanation is very good.

in src/ecmult_impl.h:89 in b6ed302caf outdated

93+     * constant d.z. The group law is the same in the image, and since 'd' maps to an
94+     * affine point, addition becomes more efficient (using mixed coordinates).
95+     *
96+     *     phi(x, y, z) = (x, y, z/d.z)
97+     *           phi(d) = (d.x, d.y, 1)
98+     *           phi(a) = (a.x, a.y, a.z/d.z) = (a.x*d.z^2, a.y*d.z^3, a.z)

jonasnick commented at 2:23 pm on December 23, 2021:

0     *     phi(x, y, z) = (x, y, z/d.z)
1     *   d_ge := phi(d) = (d.x, d.y, 1)

roconnor-blockstream commented at 4:35 am on January 19, 2022:

done.

in src/ecmult_impl.h:98 in b6ed302caf outdated

107-    prej[0].z = a->z;
108-    prej[0].infinity = 0;
109+    secp256k1_ge_set_xy(&d_ge, &d.x, &d.y);
110+    secp256k1_ge_set_gej_zinv(&pre_a[0], a, &d.z);
111+    secp256k1_gej_set_ge(&ai, &pre_a[0]);
112+    ai.z = a->z;

jonasnick commented at 2:25 pm on December 23, 2021:

0    secp256k1_ge_set_xy(&d_ge, &d.x, &d.y);
1    /* Set pre_a[0] to the point
2     *     (a.x*d.z^2, a.y*d.z^3, 1) = (a.x, a.y, 1/d.z).
3     * As a result, the omitted z-coordinate z(pre_a[0]) is equal to a.z*d.z. */
4    secp256k1_ge_set_gej_zinv(&pre_a[0], a, &d.z);
5    /* ai := phi(a) = (a.x, a.y, a.z/d.z) = (a.x*d.z^2, a.y*d.z^3, a.z) */
6    secp256k1_gej_set_ge(&ai, &pre_a[0]);
7    ai.z = a->z;

jonasnick commented at 2:26 pm on December 23, 2021:

micronit, but imho slightly more helpful

jonasnick commented at 2:27 pm on December 23, 2021: contributor

Good stuff and despite being an optimization, this PR simplifies a lot of things as well. Also thanks for the new comments. They’re really helpful.

ACK mod nits

robot-dreams cross-referenced this on Dec 23, 2021 from issue ecmult: move `_ecmult_odd_multiples_table_globalz_windowa` by siv2r

roconnor-blockstream force-pushed on Jan 17, 2022

roconnor-blockstream commented at 7:21 pm on January 17, 2022: contributor

Rebased, but I still need to address the outstanding comments.

roconnor-blockstream force-pushed on Jan 19, 2022

roconnor-blockstream commented at 4:35 am on January 19, 2022: contributor

I’ve reworded some comments and made some of the suggested changes.

in src/group_impl.h:10 in 4c144576c7 outdated

 6@@ -7,7 +7,7 @@
 7 #ifndef SECP256K1_GROUP_IMPL_H
 8 #define SECP256K1_GROUP_IMPL_H
 9 
10-#include "field.h"
11+#include "field_impl.h"

roconnor-blockstream commented at 4:39 am on January 19, 2022:

So I had to make this change to get precompute_ecmult_gen.c to build.

I’m not sure what the rules on including *_impl files is. Should secp256k1_const_beta (and secp256k1_fe_one) be moved from field_impl.h to field.h instead?

real-or-random commented at 10:49 am on January 19, 2022:

Well, at the moment there are no written rules. I believe the rules should look like described here: #1039 (comment) but we don’t adhere to them everywhere.

And yes, moving the constants to field.h would take us a step closer to this. So if this works, feel free to do it here but otherwise let’s stick with including the _impl.h file until we have a clean solution to #1039.

roconnor-blockstream commented at 4:55 pm on January 19, 2022:

constants are moved.

in src/ecmult_impl.h:100 in 4c144576c7 outdated

113-    prej[0].infinity = 0;
114+    secp256k1_ge_set_xy(&d_ge, &d.x, &d.y);
115+    /* Set pre_a[0] to the point
116+     *     (a.x*C^2, a.y*C^3, 1) = (a.x, a.y, 1/C).
117+     * As a result, the omitted z-coordinate z(pre_a[0]) is equal to a.z*C.
118+      */

jonasnick commented at 12:15 pm on January 19, 2022:

nit: not aligned

in src/ecmult_impl.h:102 in 4c144576c7 outdated

115+    /* Set pre_a[0] to the point
116+     *     (a.x*C^2, a.y*C^3, 1) = (a.x, a.y, 1/C).
117+     * As a result, the omitted z-coordinate z(pre_a[0]) is equal to a.z*C.
118+      */
119+    secp256k1_ge_set_gej_zinv(&pre_a[0], a, &d.z);
120+    /* ai := phi(a) = (a.x, a.y, a.z/C) = (a.x*C^2, a.y*C^3, a.z) */

jonasnick commented at 12:16 pm on January 19, 2022:

nit: definition of phi(a) already mentioned above. Perhaps just ai := phi(a).

jonasnick commented at 12:27 pm on January 19, 2022: contributor

ACK mod nits

Move secp256k1_fe_one to field.h

This makes secp256k1_fe_one part of field.h's interface, and allows other modules to appropriately access the constant.

c9da1baad1

Eliminate the prej array from ecmult_strauss_wnaf. e5c18892db

Remove the unused prej allocations. ae7ba0f922

Eliminate the pre_a_lam array from ecmult_strauss_wnaf. b3b57ad6ee

Remove the unused pre_a_lam allocations. 7ba3ffcca0

Eliminate na_1 and na_lam state fields from ecmult_strauss_wnaf. 0397d00ba0

Eliminate input_pos state field from ecmult_strauss_wnaf. fe34d9f341

Replace ECMULT_TABLE_GET_GE_STORAGE macro with a function. a731200cc3

Create a SECP256K1_ECMULT_TABLE_VERIFY macro. b797a500ec

roconnor-blockstream force-pushed on Jan 19, 2022

roconnor-blockstream commented at 4:56 pm on January 19, 2022: contributor

I’ve rearranged the code a little bit and rewritten the comments a bit.

jonasnick commented at 8:30 pm on January 19, 2022: contributor

ACK b797a500ec194948eecbea8bd80f6b7d455f7ca2

sipa commented at 7:41 pm on January 25, 2022: contributor

ACK b797a500ec194948eecbea8bd80f6b7d455f7ca2

jonasnick merged this on Jan 26, 2022

jonasnick closed this on Jan 26, 2022

hebasto referenced this in commit 065b6dbf9d on Jan 30, 2022

fanquake referenced this in commit 8f8631d826 on Mar 17, 2022

fanquake referenced this in commit 4bb1d7e62a on Mar 17, 2022

fanquake referenced this in commit 465d05253a on Mar 30, 2022

jonasnick cross-referenced this on Mar 30, 2022 from issue Upstream PRs 1064, 1049, 899, 1068, 1072, 1069, 1074, 1026, 1033, 748, 1079, 1088, 1090, 731, 1089, 995, 1094, 1093 by jonasnick

real-or-random referenced this in commit 6c0aecf72b on Apr 1, 2022

fanquake referenced this in commit afb7a6fe06 on Apr 6, 2022

gwillen referenced this in commit 35d6112a72 on May 25, 2022

patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022

patricklodder referenced this in commit 03002a9013 on Jul 28, 2022

janus referenced this in commit 3a0652a777 on Aug 4, 2022

str4d referenced this in commit 522190d5c3 on Apr 21, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

Reduce stratch space needed by ecmult_strauss_wnaf. #899