Co-Z based precomputation (by Peter Dettman) #211

pull sipa wants to merge 3 commits into bitcoin-core:master from sipa:coz changing 13 files +382 −134

sipa commented at 11:21 PM on February 11, 2015: contributor

Refactored version of Co-Z code from #41 and #174.

Builds on top of #210.
sipa force-pushed on Feb 12, 2015
sipa force-pushed on Feb 12, 2015
sipa force-pushed on Mar 2, 2015
sipa commented at 10:28 AM on March 2, 2015: contributor

Rebased.
sipa force-pushed on Mar 2, 2015
sipa commented at 1:36 PM on March 3, 2015: contributor

This gives a 2.0-2.3% speedup for verification on top of #210.
sipa force-pushed on Mar 28, 2015
sipa force-pushed on Mar 29, 2015
sipa force-pushed on Apr 11, 2015
sipa force-pushed on Apr 12, 2015
sipa force-pushed on Apr 23, 2015
sipa commented at 9:10 AM on April 23, 2015: contributor

Rebased.
peterdettman cross-referenced this on Apr 25, 2015 from issue Effective affine precomputation (by Peter Dettman) by sipa
peterdettman commented at 7:43 AM on April 25, 2015: contributor

A brief recap regarding novelty of this idea. Short version: this is not novel (but it's still pretty cool).

Boring version: I learnt about the Co-Z formulae from several papers, of which http://joye.site88.net/papers/GJMRV11regpm.pdf may be taken as representative, and which in turn usually referenced papers of Meloni. At some point I realized it could be applied usefully to the pre-computation of a table of odd multiples, and duly implemented a rough version. Actually it was fairly fast, so I became curious what was the fastest known method for that pre-computation. A literature research turned up https://eprint.iacr.org/2008/051, which upon further investigation, turned out to describe essentially the same approach (explicitly mentioning Meloni's formulae), giving one scheme with the same cost as ours, and a second one that improved on that further. I subsequently implemented the second scheme, although that modification is not yet in any PR (and the effect is small).
sipa force-pushed on Apr 30, 2015

in src/group.h:None in 0569766269 outdated

  36 | + *  An instance of secp256k1_coz_t is always "co-z" with some instance of secp256k1_gej_t, from
  37 | + *  which it inherits its implied z coordinate and infinity flag. */
  38 | +typedef struct {
  39 | +    secp256k1_fe_t x; /* actual X: x/z^2 (z implied) */
  40 | +    secp256k1_fe_t y; /* actual Y: y/z^3 (z implied) */
  41 | +} secp256k1_coz_t;

apoelstra commented at 6:47 PM on May 1, 2015:

Is there any benefit to adding an #ifdef VERIFY z coordinate, then VERIFY_CHECKing in secp256k1_coz_zaddu_var that ra is actually co-Z with b?

sipa commented at 6:53 PM on May 1, 2015:

I think that makes perfect sense.

sipa commented at 8:06 PM on May 1, 2015: contributor

Added the consistency check that @apoelstra suggested.
gmaxwell commented at 7:27 PM on May 2, 2015: contributor

Please also add an explicit citation to the Meloni publicaiton for the co-z formula (the cite is in Longa/Miri 2008)
sipa force-pushed on Jul 14, 2015
sipa force-pushed on Aug 4, 2015
sipa force-pushed on Aug 27, 2015
gmaxwell added this to the milestone initial release on Aug 31, 2015
gmaxwell removed this from the milestone initial release on Aug 31, 2015

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.

28f1568c1a

Extra consistency checks for co-z 2317dc435b
sipa force-pushed on Sep 22, 2015
sipa commented at 7:42 PM on September 22, 2015: contributor

Rebased.
Schnorr overhaul c1fa293f76
gmaxwell commented at 6:39 PM on June 6, 2017: contributor

needs rebase
sipa closed this on May 8, 2023

Contributors

Linked (view graph)

#41 Use Co-Z arithmetic for precomputations #174 Co-Z + effective affine precomputation + tests #210 Effective affine precomputation (by Peter Dettman)