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

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

2. sipa force-pushed on Feb 12, 2015
3. sipa force-pushed on Feb 12, 2015
4. sipa force-pushed on Mar 2, 2015
5. 
   sipa commented at 10:28 am on March 2, 2015: contributor

   Rebased.
6. sipa force-pushed on Mar 2, 2015
7. 
   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.
8. sipa force-pushed on Mar 28, 2015
9. sipa force-pushed on Mar 29, 2015
10. sipa force-pushed on Apr 11, 2015
11. sipa force-pushed on Apr 12, 2015
12. sipa force-pushed on Apr 23, 2015
13. 
    sipa commented at 9:10 am on April 23, 2015: contributor

    Rebased.
14. peterdettman cross-referenced this on Apr 25, 2015 from issue Effective affine precomputation (by Peter Dettman) by sipa
15. 
    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).

16. sipa force-pushed on Apr 30, 2015
17. in src/group.h: 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.
18. 
    sipa commented at 8:06 pm on May 1, 2015: contributor

    Added the consistency check that @apoelstra suggested.
19. 
    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)
20. sipa force-pushed on Jul 14, 2015
21. sipa force-pushed on Aug 4, 2015
22. sipa force-pushed on Aug 27, 2015
23. gmaxwell added this to the milestone initial release on Aug 31, 2015
24. gmaxwell removed this from the milestone initial release on Aug 31, 2015
25. 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
26. Extra consistency checks for co-z 2317dc435b
27. sipa force-pushed on Sep 22, 2015
28. 
    sipa commented at 7:42 pm on September 22, 2015: contributor

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

    needs rebase
31. sipa closed this on May 8, 2023

    ---

Contributors
sipa peterdettman apoelstra gmaxwell