I am currently writing my master thesis about elliptic curve cryptography and Bitcoin. For the section about the performance of secp256k1 and possible improvements I wanted to look at how point addition and multiplication has been implemented in Bitcoin.
I am not the best programmer (I am doing my master in mathematics) and so I wanted to know if there is a theoretical explanation, or where I can find the source code of this part of Bitcoin, to try to figure it out with the help of some IT friends.
I found this paper (
https://eprint.iacr.org/2016/103.pdf) "Speed Optimizations in Bitcoin Key Recovery Attacks"
where it says in section 4.2.3. Secp256k1 point addition formulas: "Bitcoin developers implemented a mixed coordinate formula (Jacobian-Affine)
version based on >>Weierstraß Elliptic Curves and Side-Channel Attacks<< by Eric Brier and Marc Joye :
https://s17.postimg.org/eotd6k6nz/point_multi_BTC.pngIs this still the version up to date?
In (
https://www.microsoft.com/en-us/research/wp-content/uploads/2016/06/complete-2.pdf) "Complete Addition Formulas for Prime Order Elliptic Curves" by Joost Renes, Craig Costello and Lejla Batina it sais that
"compared to the incomplete addition function secp256k1 gej add var used in the Bitcoin
code, our complete addition function in Algorithm 7 saves 4S at the cost of 8a+1mul int5;
compared to Bitcoin's incomplete mixed addition function secp256k1 gej add ge var, our
complete mixed addition saves 3S at the cost of 3M + 2a + 1mul int; and, compared to
Bitcoin's doubling function secp256k1 gej double var, our formulas save 2S + 5mul int at
the cost of 3M+ 3a. In this case it is unclear which set of formulas would perform faster,
but it is likely to be relatively close and to depend on the underlying field arithmetic and/or
target platform. Furthermore, the overall speed is not just dependent on the formulas: the
if statements present in the Bitcoin code also hamper performance. On the contrary, the
complete algorithms in this paper have no if statements."
This paper is from the 28th of April 2016. Which changes of the formulas have been done since then?
I hope someone might take the time to explain the current implementations in Bitcoin, or has another reference of a paper or a forum topic where I can find some answers!
