@rocks,

@molecular

"The EC algorithm from a code perspective is pretty straight forward"

The high-level algorithm is pretty straightforward [

see here]. However, once you get into the nuts & bolts, some of the operations are quite tricky and there are lots of ways to skin the cat. I believe there are at least three steps where it is possible to achieve algorithmic coding gain:

1. Calculating the curve point: (x, y) = k * G, where k is a secret number and G is the base point.

2. Doing arithmetic modulo a large prime number (at several points in the calculation)

3. Calculating the inverse of the secret number k.

For example, there are several different algorithms that can be used to carry out the multiplication in #1. The simplest is probably the

"double and add" method. However, the amount of time it takes this algorithm to execute depends on the specific value of k (G is always constant for bitcoin). On the other hand, the

"Montgomery Ladder" approach computes the point multiplication in a fixed amount of time (regardless of the specific value of k). This is beyond my expertise level, but I suspect there are several ways to tune this operation for the particular curve in question (secp256k1) to achieve both "constant time" and "as fast as possible."

Regarding the modulo arithmetic and inverse operations, there are speeds-ups possible here too and AFAIK the curve parameters for secp256k1 were actually chosen to facilitate acceleration of these operations.

I spent many days researching this when I was working on getting my

sigsafe devices to be able to

sign Bitcoin TXs using only the energy available from an NFC field. I forget a lot of it now, but I remember that it appeared to me at the time that lots of improvements should be possible if the math was tuned specifically for Bitcoin's elliptic curve.

That being said, I really wish the Blockstream folks would actually publish there work in a nice paper, so that we could all learn and understand what exactly the optimizations were. I dislike this "it's documented in the code" or "we discussed it on IRC" attitude.