Effective affine precomputation (by Peter Dettman)

sipa commented at 11:20 pm on February 11, 2015: contributor

Significantly refactored version of Peter Dettman’s effective affine precomputation tricks.

See #174 and #41 for old discussion.

sipa cross-referenced this on Feb 11, 2015 from issue Use Co-Z arithmetic for precomputations by peterdettman

sipa cross-referenced this on Feb 11, 2015 from issue Co-Z based precomputation (by Peter Dettman) by sipa

sipa force-pushed on Feb 12, 2015

sipa cross-referenced this on Feb 13, 2015 from issue Effectively affine precomp A for _ecmult without inversion! by peterdettman

sipa force-pushed on Mar 2, 2015

sipa commented at 10:52 am on March 2, 2015: contributor

Rebased.

sipa commented at 1:29 pm on March 3, 2015: contributor

This seems to give a 4.5-6.5% speedup for verification (without and with GLV).

sipa commented at 10:32 am on March 16, 2015: contributor

@gmaxwell @apoelstra: feel like reviewing this?

apoelstra commented at 1:49 pm on March 16, 2015: contributor

Sure. I will need to do the prereading.

sipa force-pushed on Mar 28, 2015

sipa commented at 0:44 am on March 28, 2015: contributor

Rebased.

sipa force-pushed on Mar 29, 2015

gmaxwell commented at 9:13 pm on April 3, 2015: contributor

I believe this needs a citation to https://eprint.iacr.org/2008/051 (you should check to see that the technique agrees).

sipa force-pushed on Apr 11, 2015

sipa commented at 10:42 am on April 11, 2015: contributor

Rebased.

sipa force-pushed on Apr 23, 2015

sipa commented at 9:10 am on April 23, 2015: contributor

Rebased.

sipa commented at 3:28 pm on April 23, 2015: contributor

@apoelstra Feel free to ask any questions.

peterdettman commented at 5:29 am on April 24, 2015: contributor

@apoelstra Happy to answer questions also.

apoelstra commented at 8:52 pm on April 24, 2015: contributor

Hi guys, sorry for the delay. I’ve been caught up in schoolwork as I transition departments and haven’t had enough spare cycles at once. This weekend is hopeful.

Am I correct that there is an explicit description of the new code in https://eprint.iacr.org/2008/051 (which I haven’t read)? Or should I use the algebra and motivations from the Co-Z paper (which I have read in some detail)?

sipa commented at 8:54 pm on April 24, 2015: contributor

That paper is about using Co-Z for speeding up precomputations. It has nothing to do with the effective affine trick (which can, however, be used ad an alternative to co-z for the precomputation).

IIRC the effective affine trick is novel.

peterdettman commented at 7:11 am on April 25, 2015: contributor

@apoelstra Further to @sipa’s comments, “Co-Z” and “Effective affine” are independent techniques. Possibly that was somewhat obscured during the initial development, but with hindsight and a subsequent refactoring of the code (thanks to @sipa) it is now clear.

I would like to clarify my position on claims of novelty. Since here we wish only to deal with “Effective affine”, please also see https://github.com/bitcoin/secp256k1/pull/211 where I will shortly add a similar statement regarding “Co-Z”.

I claim independent discovery of “the effective affine trick”, the essence of which is to perform the main ladder of a scalar multiplication on an isomorphism of the original curve, which avoids the cost of an inversion in the field, whilst still admitting the use of mixed addition with precomputed points. There are some minor corollary techniques reflected in the implementation, to wit: i) applying the trick to the pre-computation itself, and ii) applying the trick in the context of a Strauss-Shamir ladder (with one point fixed).

I think it would be premature to claim novelty at this time, for (at least) the following reasons. Although I read quite widely in the relevant literature and know of no previous description or implementation of the technique, I have made only moderate efforts in a directed search. The technique is only a small step away from other commonly-understood techniques. I have not yet directly solicited the opinion of academic researchers, who are likely to have a more complete (e.g. paywalled) and up-to-date view of the literature. Although I have described the techniques on e.g. the IETF CFRG mailing list and in a few private communications, it has never been in the context of establishing novelty. Finally, I have not conducted or requested a prior art search with any patent office.

sipa commented at 9:07 am on April 25, 2015: contributor

Thanks for the summary!

sipa commented at 9:19 am on April 25, 2015: contributor

The isomorphism involved can be compactly written as:

(in affine coordinates): (a,b) + (c,d) = (e,f) <=> (a_t^2,b_t^3) + (c_t^2,d_t^3) = (e_t^2,f_t^3).
(in Jacobian coordinates): (a,b,c) + (d,e,f) = (g,h,i) <=> (a,b,c_t) + (d,e,f_t) = (g,h,i*t).

This is used in two different ways:

When adding a number of Jacobian points together, which are all known to have the same Z coordinate (called global Z in the source code), one can use the formulae for affine addition (temporarily assuming that global Z coordinate is 1), and then later multiply the result’s Z coordinate with the global Z.
Addition with a Jacobian point of which the inverse of its Z coordinate is known, can be done using a minor modification to the affine formulae.

apoelstra commented at 7:57 pm on April 25, 2015: contributor

Awesome, thanks for the summary @peterdettman and for the algebra @sipa. I’ll check over the code today (as in now) and tomorrow.

sipa commented at 12:08 pm on April 27, 2015: contributor

@apoelstra In particular, feel free to comment about explanations given in comments (not enough, confusing, …).

in src/group.h: in 713db62f02 outdated

92@@ -82,10 +93,10 @@ static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a);
93 static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a);
94 
95 /** Set r equal to the double of a. */
96-static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a);
97+static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, secp256k1_fe_t *rzr);

apoelstra commented at 3:05 pm on April 28, 2015:

I think the doccomment needs to be updated to reflect what happens to rzr. (“Is it r.z/a.z or its recipricol?” is not obvious just from the name. I also don’t think the behaviour for infinity is obvious since then rzr ought be be “0/0”.)

in src/group.h: in 713db62f02 outdated

 92@@ -82,10 +93,10 @@ static void secp256k1_gej_neg(secp256k1_gej_t *r, const secp256k1_gej_t *a);
 93 static int secp256k1_gej_is_infinity(const secp256k1_gej_t *a);
 94 
 95 /** Set r equal to the double of a. */
 96-static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a);
 97+static void secp256k1_gej_double_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, secp256k1_fe_t *rzr);
 98 
 99 /** Set r equal to the sum of a and b. */
100-static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_gej_t *b);
101+static void secp256k1_gej_add_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_gej_t *b, secp256k1_fe_t *rzr);

apoelstra commented at 3:06 pm on April 28, 2015:

Ditto here.

in src/group.h: in 713db62f02 outdated

103@@ -93,11 +104,14 @@ static void secp256k1_gej_add_ge(secp256k1_gej_t *r, const secp256k1_gej_t *a, c
104 /** Set r equal to the sum of a and b (with b given in affine coordinates). This is more efficient
105     than secp256k1_gej_add_var. It is identical to secp256k1_gej_add_ge but without constant-time
106     guarantee, and b is allowed to be infinity. */
107-static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b);
108+static void secp256k1_gej_add_ge_var(secp256k1_gej_t *r, const secp256k1_gej_t *a, const secp256k1_ge_t *b, secp256k1_fe_t *rzr);

apoelstra commented at 3:06 pm on April 28, 2015:

and here.

apoelstra commented at 6:50 pm on April 28, 2015: contributor

Tested ACK. Confirmed that the algebra made sense, comments were sensible, that it was implemented clearly and correctly. Ran unit tests on both commits under valgrind (no leaks or errors) and kcov (“full coverage” as much as that tool can tell), also ran the unit tests for rust-secp256k1 on them.

This is a really elegant and clever improvement. Thanks a ton for your contribution @peterdettman . Sorry all for the delays in my review.

Effective affine addition in EC multiplication

* Make secp256k1_gej_add_var and secp256k1_gej_double return the
  Z ratio to go from a.z to r.z.
* Use these Z ratios to speed up batch point conversion to affine
  coordinates, and to speed up batch conversion of points to a
  common Z coordinate.
* Add a point addition function that takes a point with a known
  Z inverse.
* Due to secp256k1's endomorphism, all additions in the EC
  multiplication code can work on affine coordinate (with an
  implicit common Z coordinate), correcting the Z coordinate of
  the result afterwards.

Refactoring by Pieter Wuille:
* Move more global-z logic into the group code.
* Separate code for computing the odd multiples from the code to bring it
  to either storage or globalz format.
* Rename functions.
* Make all addition operations return Z ratios, and test them.
* Make the zr table format compatible with future batch chaining
  (the first entry in zr becomes the ratio between the input and the
  first output).

Original idea and code by Peter Dettman.

4f9791abba

Apply effective-affine trick to precomp 2d5a186cee

sipa force-pushed on Apr 30, 2015

sipa commented at 4:28 pm on April 30, 2015: contributor

Updated the comments, as requested by @apoelstra.

sipa commented at 5:17 pm on April 30, 2015: contributor

@apoelstra Thanks for the review!

sipa merged this on Apr 30, 2015

sipa closed this on Apr 30, 2015

sipa referenced this in commit 729badff14 on Apr 30, 2015

peterdettman commented at 4:47 am on May 4, 2015: contributor

@apoelstra Thanks for your review, and for your kind words.

Effective affine precomputation (by Peter Dettman) #210