Co-Z + effective affine precomputation + tests #174
pull sipa wants to merge 3 commits into bitcoin-core:master from sipa:ecmult-coz changing 8 files +527 −93-
sipa commented at 2:28 am on December 29, 2014: contributorThis builds on top of #171 but reworks the group element tests, making them much more extensive (and faster).
-
peterdettman commented at 5:35 am on December 29, 2014: contributorMuch appreciated, sipa. Nice catch of the missing normalisation of a->y in dblu.
-
sipa cross-referenced this on Dec 29, 2014 from issue Rework group tests by sipa
-
sipa force-pushed on Dec 29, 2014
-
sipa force-pushed on Dec 29, 2014
-
sipa commented at 3:54 pm on December 29, 2014: contributor
Updated. Rebased on top of #176, splitted up the commits, and made some changes to comments and function names.
Instead of secp256k1_gej_add_ge_var allowing an “a Z ratio” to be passed in, I’ve turned it into a separate function secp256k1_gej_add_zinv, which adds a point B whose Z coordinate is given by passing in its inverse (which is effectively equivalent to the old method with an azr passed in, but easier to explain IMHO).
-
sipa commented at 4:08 pm on December 29, 2014: contributor
Benchmark before and after this entire PR (including both of @peterdettman’s commits):
- With endomorphism: 198k -> 183k cycles
- Without endomorphism: 266k -> 249k cycles.
-
peterdettman commented at 1:10 am on December 30, 2014: contributorI don’t mind the switch to an equivalent zInv formulation; it corresponds to the first “alternative scheme” given in https://github.com/bitcoin/secp256k1/pull/41#issuecomment-66867000. It avoids the awkwardness of using a->z*azr, then updating from just a->z. @sipa Did you have any thoughts on https://github.com/bitcoin/secp256k1/issues/159? All these coz and mixed additions are doing input normalisation that could be avoided…
-
sipa commented at 1:13 am on December 30, 2014: contributor@peterdettman Not sure what optimization there you’re referring to, the comment is a bit vague. If you have further improvements, feel free to PR them!
-
sipa commented at 1:16 am on December 30, 2014: contributor@peterdettman I’m not sure I’m following you. 28f317f97e31a4c8392b96d4665feff082201cce makes 0 semantic changes - it only separates the azr==NULL and azr!=NULL case into separate functions, and renames the second one and its explanation/argument name.
-
peterdettman commented at 1:51 am on December 30, 2014: contributorSorry, the second link was wrong, I was asking about https://github.com/bitcoin/secp256k1/issues/159. As for the first part, I agree there’s no semantic change, I was just noting that I’d previously used the _gej_add_zinv “syntax” in a similar context, so it’s arguably a more natural presentation.
-
sipa force-pushed on Jan 4, 2015
-
sipa force-pushed on Jan 8, 2015
-
sipa commented at 1:29 am on January 8, 2015: contributorRebased, and restructured the commits significantly (moving the Co-Z part to a separate commit). @peterdettman since the code and ideas were yours, I left you as author, but feel free to complain if you think that’s not appropriate.
-
sipa force-pushed on Jan 8, 2015
-
peterdettman commented at 2:42 pm on January 9, 2015: contributor@sipa I don’t have any problems with that, thanks for asking though.
-
sipa force-pushed on Jan 26, 2015
-
sipa force-pushed on Feb 7, 2015
-
sipa commented at 0:21 am on February 7, 2015: contributorRebased again.
-
gmaxwell commented at 2:37 am on February 7, 2015: contributorNeeds operation counts.
-
sipa force-pushed on Feb 7, 2015
-
sipa commented at 2:49 am on February 7, 2015: contributorDone.
-
in configure.ac: in c5d6cf7a16 outdated
309@@ -305,11 +310,16 @@ if test x"$use_endomorphism" = x"yes"; then 310 AC_DEFINE(USE_ENDOMORPHISM, 1, [Define this symbol to use endomorphism optimization]) 311 fi 312 313+if test x"$use_coz" = x"yes"; then 314+ AC_DEFINE(USE_COZ, 1, [Define this symbol to use endomorphism optimization])
peterdettman commented at 7:58 am on February 7, 2015:Copy/paste error for help text here?
sipa commented at 8:00 am on February 7, 2015:Copy/paste error for help text here?
Fixed.
sipa force-pushed on Feb 7, 2015sipa commented at 0:58 am on February 9, 2015: contributorRefactored the code further (to facilitate later batch chaining, in order to support batch signature validation).peterdettman commented at 9:42 am on February 9, 2015: contributor@sipa I put together a commit demonstrating how to get half of the speed gain of Co-Z precomp without the Co-Z formulae: https://github.com/peterdettman/secp256k1/commit/f188650d2a54434907ec1f655aa60ca33ac287e8 . It basically applies the effective-affine trick so that the precomp additions are mixed.sipa commented at 10:47 pm on February 11, 2015: contributor@peterdettman Awesome, makes perfect sense.
Benchmarks (without GLV, with GMP): Effective affine: 256k cycles Effective affine + effective affine odd multiples: 254k cycles Effective affine + Co-Z odd multiples: 248k cycles
Benchmarks (with GLV, with GMP): Effective affine: 188k cycles Effictive affine + effective affine odd multiples: 185k cycles Effective affine + Co-Z odd multiples: 182k cycles
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 959aee39e7Optionally use Co-Z arithmetic for precomputations
- Selected Co-Z formulas from "Scalar Multiplication on Weierstraß Elliptic Curves from Co-Z Arithmetic" (Goundar, Joye, et. al.) added as group methods with new type sep256k1_coz_t. - Co-Z methods used for A and G point precomputations. - DBLU cost: 3M+4S, ZADDU cost: 5M+2S. Original idea and code by Peter Dettman. Refactored by Pieter Wuille.
sipa force-pushed on Feb 11, 2015sipa commented at 11:18 pm on February 11, 2015: contributorClosing this, way too many refactors to follow the discussion; I’ll open new pull requests.sipa closed this on Feb 11, 2015
sipa cross-referenced this on Feb 11, 2015 from issue Effective affine precomputation (by Peter Dettman) by sipasipa cross-referenced this on Feb 11, 2015 from issue Co-Z based precomputation (by Peter Dettman) by sipa
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-10-30 07:15 UTC
More mirrored repositories can be found on mirror.b10c.me