Bitcoin Signatures From Scratch (4/4): ECDSA Implementation in Python Using Zero Dependencies

This series of short articles is based on my original giant article: Elliptic curves and ECDSA: everything to know to sign a transaction in Bitcoin from scratch

The series consists of four parts; each part uses the concepts discovered in the previous parts:

1. The Magic of Elliptic Curves
2. The Magic of Elliptic Curves Combined with Finite Fields
3. Using The Magic of Elliptic Curves to Sign and Verify Messages
4. ECDSA Implementation in Python Using Zero Dependencies [you’re here]

All the formulas and concepts used in this implementation are described in two previous parts: part 2, and part 3.

The bottlenecks

• We need to be able to perform basic arithmetical operations on huge numbers. In programming, we can easily operate on large numbers using bignum arithmetic. So our programming language must support it, or we should use some external package to work with it. In the examples of this part, I will use Python, which supports bignum arithmetic out of the box.
  For the Live Demo (next part), I will use JavaScript, and there we will need the BigNumber.js package.
• The other bottleneck we will encounter is finding the multiplicative inverse of a huge number.
  Obviously, brute force is not going to work. The multiplicative inverse can be found by the Extended Euclidean algorithm, which has the complexity of O(log(n)).

Python (3.8+) can find the multiplicative inverse out of the box with its built-in pow function:

If you need the actual implementation of the extended euclidean algorithm, check the code of my Live Demo!

Let’s start writing our code!

We need one simple thing related to the elliptic curve: Point. Let’s define a class Point. In its constructor, we should make check whether the point lies on the curve:

We need to be able to compare two points, add them together, and multiply them by an integer.

Let’s add a method to check if two points are equal:

Now let’s implement add method, which returns a new Point as the result of addition:

All the formulas are listed in Part 2.

Now let’s implement the multiply method.
The most straightforward implementation would be this:

But let’s say we need to multiply our point by a big number: 115792089237316195. Even if we had the speed of 1 billion additions per second, this would take 3.6 years to calculate this point!

And this is not even a big number for us! Here is a big number:
115792089237316195423570985008687907852837564279074904382605163141518161494337

Calculating the point in this way would take billions of billions of billions of billions… of years!

We can define that the efficiency of the algorithm above is O(n), which is of no use for our purposes. If you remember, there is an easy way to achieve O(log2(n)) complexity by continuously doubling our point:

2P = P+P
4P = 2P + 2P
8P = 4P + 4P
16P = 8P + 8P
32P= 16P + 16P
64P = 32P + 32P

And log2(115792089237316195) = 56

log2(115792089237316195423570985008687907852837564279074904382605163141518161494337) = 256

So we don’t need billions of billions of billions… of years. We need 256 operations to get to this large point!

Just one moment: to efficiently multiply by values that are not a degree of 2, it’s reasonable to store all the previous values and then combine the results together.

For example, if we need to get 100P, we can no longer double 64P. Neither can we add points one by one: potentially, this would take billions of billions of years on larger numbers. What’s reasonable to do instead is:
96P = 64P + 32P
100P = 96P + 4P

So for that purpose, we need to store all the previous P’s and afterward efficiently use them.

So here is an efficient implementation:

Thus we’ve got a super efficient implementation! And now, we can perform all the needed operations on an elliptic curve.

Let’s define secp256k1:

I’m using only decimal numbers in our examples because they’re intuitive for people.

So far, we’ve implemented everything that we discussed in Part 2. Now let’s implement the actual digital signature algorithm described in Part 3.

Sign method of ECDSA:

Verify method of ECDSA:

Let’s pick some number as our private key, for example, 123456789012345.
Let our message be 12345.
Do you remember how to get PublicKey from PrivateKey?

Now let’s sign and try to verify:

It works! You can try to corrupt the signature or the original message and make sure that our algorithm works properly.

Here is the complete code:

So the implementation of the entire ECDSA algorithm took just 100 lines of code! And it’s perfectly working. This is absolutely the same algorithm as the one used in Bitcoin!

Live Demo

As I promised at the beginning of this series, here is the live demo using only the concepts and formulas described in the article. Just a couple of notes:

• Initially, we could only sign integer messages. But in the demo, you can choose to apply a hash function (sha256) to your message. Thanks to it, a message can be a string.
• Bitcoin uses slightly different formats of public keys and signatures.
• Never use any piece of it in a production environment! It is not safe. For production, you must only use well-tested solutions.

Here is the demo:

The end of the series

I hope this series of articles was very useful for you. At least, I did my best to make it useful. Feel free to share it with friends or use any piece of it anywhere. Just please leave a link to the original article.

Feel free to contact me:
exemak@gmail.com
https://t.me/exemak
Mikhail Karavaev