I went down the rabbit hole, 120 ms to sign and as many to verify was too much.
I knew libsecp256k1 was efficient (and, more important, secure) but I wanted to learn how it was as many as a _thousand_ times faster
I knew libsecp256k1 was efficient (and, more important, secure) but I wanted to learn how it was as many as a _thousand_ times faster
https://twitter.com/RCasatta/status/1016032457924235264
The journey in the hole brought me to learn and implement:
* Jacobian coordinates
* Pre-caching G multiples
* Specific code for doubling points and mixed add
* Borrowing instead of copying
* Multiplying instead of powering for 2 or 3
* Avoiding any inverse in verify
* Jacobian coordinates
* Pre-caching G multiples
* Specific code for doubling points and mixed add
* Borrowing instead of copying
* Multiplying instead of powering for 2 or 3
* Avoiding any inverse in verify
* NAF non adjacent form to multiply
* Shamir's trick
* Bos-Coster
* Arbitrary precision integer libs
* Benchmarking everything for evidence
* Shamir's trick
* Bos-Coster
* Arbitrary precision integer libs
* Benchmarking everything for evidence
Those improvement brought signing time to 270 us and verifying to 1.1 ms which are still slower than libsecp256k1 (about 3 times slower to sign and 11 times slower to verify). However a _lot_ closer!
About the Non Adjacent Form, the choice of w wasn't discounted, so I benchmarked it and went to use w=5, I wonder if libsecp256k1 use the same 
About the batch verification, it looks Bos-Coster achieve logarithmic efficiency.
Any suggestions to improve results are welcome!
• • •
Missing some Tweet in this thread? You can try to
force a refresh
