Co-Z + effective affine precomputation + tests

sipa commented at 2:28 am on December 29, 2014: contributor

This 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: contributor

Much 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 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: contributor

I 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: contributor

Sorry, 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: contributor

Rebased, 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

gmaxwell commented at 1:12 pm on January 26, 2015: contributor

@sipa thanks for rebasing

sipa force-pushed on Feb 7, 2015

sipa commented at 0:21 am on February 7, 2015: contributor

Rebased again.

gmaxwell commented at 2:37 am on February 7, 2015: contributor

Needs operation counts.

sipa force-pushed on Feb 7, 2015

sipa commented at 2:49 am on February 7, 2015: contributor

Done.

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, 2015

sipa commented at 0:58 am on February 9, 2015: contributor

Refactored 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.

69ac1fddaa

Apply effective-affine trick to precomp 959aee39e7

Optionally 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.

ce97d974b2

sipa force-pushed on Feb 11, 2015

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

Closing 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 sipa

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

Co-Z + effective affine precomputation + tests #174