Significantly refactored version of Peter Dettman’s effective affine precomputation tricks.
Effective affine precomputation (by Peter Dettman) #210
pull sipa wants to merge 2 commits into bitcoin-core:master from sipa:effective_affine changing 6 files +374 −97-
sipa commented at 11:20 pm on February 11, 2015: contributor
-
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 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 force-pushed on Mar 2, 2015
-
sipa commented at 10:52 am on March 2, 2015: contributorRebased.
-
sipa commented at 1:29 pm on March 3, 2015: contributorThis 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: contributorSure. I will need to do the prereading.
-
sipa force-pushed on Mar 28, 2015
-
sipa commented at 0:44 am on March 28, 2015: contributorRebased.
-
sipa force-pushed on Mar 29, 2015
-
gmaxwell commented at 9:13 pm on April 3, 2015: contributorI 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: contributorRebased.
-
sipa force-pushed on Apr 23, 2015
-
sipa commented at 9:10 am on April 23, 2015: contributorRebased.
-
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: contributorThanks 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: contributorAwesome, 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 torzr
. (“Is itr.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: contributorTested 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.
Apply effective-affine trick to precomp 2d5a186ceesipa force-pushed on Apr 30, 2015sipa commented at 4:28 pm on April 30, 2015: contributorUpdated 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, 2015sipa closed this on Apr 30, 2015
sipa referenced this in commit 729badff14 on Apr 30, 2015peterdettman commented at 4:47 am on May 4, 2015: contributor@apoelstra Thanks for your review, and for your kind words.
github-metadata-mirror
This is a metadata mirror of the GitHub repository bitcoin-core/secp256k1. This site is not affiliated with GitHub. Content is generated from a GitHub metadata backup.
generated: 2024-12-23 12:15 UTC
This site is hosted by @0xB10C
More mirrored repositories can be found on mirror.b10c.me