--- Day changed Mon Mar 19 2018
01:38 -!- wump is now known as wumpus     
04:38 -!- jtimon [~quassel@142.29.134.37.dynamic.jazztel.es] has joined #secp256k1     
10:19 -!- phqulsg [~akmwlec@193.106.25.19] has joined #secp256k1     
10:19 -!- phqulsg [~akmwlec@193.106.25.19] has quit [Client Quit]     
12:08 -!- hdevalence [~hdevalenc@52.119.117.17] has joined #secp256k1     
13:58 -!- eklitzke [~evan@fsf/member/eck] has quit [Quit: bye]     
16:50 -!- hdevalence [~hdevalenc@52.119.117.17] has quit [Quit: hdevalence]     
17:00 -!- weez17 [~isaac@unaffiliated/weez17] has quit [Remote host closed the connection]     
17:00 -!- weez17 [~isaac@unaffiliated/weez17] has joined #secp256k1     
19:07 < andytoshi> did we know about https://eprint.iacr.org/2015/1060.pdf ? claims to give a complete addition formula for points on prime order weierstrass curves with cost 12M. page 12 covers the j-invariant 0 case and even mentions bitcoin
19:09 < andytoshi> ah it's in projective coordinates, in jacobian this may be more exensive
19:13 < andytoshi> lol they cite our code elsewhere in the paper. this is super cool
19:15 < sipa> Lejla Batina!
19:15 < sipa> she was a supervisor for a project i did as an undergrad
19:15 < andytoshi> small world :)
19:18 < sipa> i thought it was provably impossible to have a complete addition formula for our curve
19:18 < sipa> but maybe that's only the case for affine or jacobian coordinates?
19:28 < sipa> i must be wrong
19:28 < sipa> , it is highly desirable to go searching for a Jacobian coordinate
19:28 < sipa> analogue of the Bosma–Lenstra (homogeneous coordinates) addition law. Unfortunately, we
19:29 < sipa> now show that such addition formulas in Jacobian coordinates must have a higher bidegree,
19:29 < sipa> intuitively making them slower to compute.
19:33 < sipa> maybe we should review what using homogeneous coordinates would mean
19:43 < sipa> i assume there's no equivalent of the effective affine trick, though
20:21 < andytoshi> i think if you tried to do something like EA in projective coordinates you'd wind up alternating between two isomorphism classes rather than moving through one
20:22 < andytoshi> so maybe there's a way you can split up a ecmult into two ecmults that each always stay in the original one, or something
20:22 < sipa> i think the operation we care about most is secp256k1_gej_add_ge_var
20:22 < sipa> the homogenous equivalent they have looks worse than our current implementation
20:23 < andytoshi> yeah i think any complete formula will be worse than our gej_add_ge_var
20:24 < andytoshi> i was optimistic that we could get a comprehensible gej_add_ge that didn't have a perf hit
20:24 < sipa> right, but it would require changing everything to homogeneous
20:24 < andytoshi> but if we had to switch to projective coords, i'm sure that's a net loss
20:24 < andytoshi> yeah
20:25 < sipa> hmm     
20:25 < sipa> 10M (their homogeneous mixed addition) vs 8M+3S (our secp256k1_gej_add_ge_var)
20:44 < andytoshi> :) i got batch validation of sha2 down from 58.44ms to 39.41ms on my test machine with my scalar-mult elimination work this week
20:47 < andytoshi> i got down to 48.32 ms by rearranging calculations to reduce # of calls to scalar_mul, then the rest of the way by separating out bits in the circuit-generation code and then treating them specially since their constraints have an especially simple form
21:09 < andytoshi> the pedersen hash results are not so dramatic, for 768-bit hash i get from 8.04 to 7.14 ms
21:35 < gmaxwell> andytoshi: for some reason there are a dozen papers for fast addition formula in projective coordinates, I dunno why people keep writing them.
23:07 -!- Cory [~Cory@unaffiliated/cory] has quit [Ping timeout: 255 seconds]     
23:41 -!- Cory [~Cory@unaffiliated/cory] has joined #secp256k1