blog.md

The hard way series - Bitcoin: private key, public key, address

This article is all about two ways of generating a Bitcoin address: the hard way using simple math and the easy way using an existing Bitcoin library.

A. The hard way

In this section I am going to use simple math functions like addition and multiplication to generate a valid Bitcoin address starting from a number, the private key and calculating everything all the way up to public key and final Bitcoin address.

TL;DR;

• private key is just a number (like a PIN code) but a very very large one, 10^77 order of magnitude (put this in context of number of atoms in the known, observable universe which is 10^80)
• public key is the result of scalar multiplication of private key and a point on Elliptic curve
• Bitcoin address is derived from public key by doing SHA256 / RIPE160 hashing and adding network prefix and checksum suffix
• we will generate valid Bitcoin address using two hash functions and simple math operations like addition, multiplication
• copy / paste Ruby code snippets below or get the gist

Elliptic Curve domain parameters

First of all let's talk about the 6 domain parameters that are defined in secp256k1: p,a,b,G,n,h. Read this Slashdot thread if you want to dive into a little bit of conspiracy theory.

Prime number - p

The migthy prime number itself.

https://gist.github.com/2c71c6568751ece71985acdce13e1815

Elliptic Curve (EC) - a, b

In general elliptic curves are defined as y^2 = x^3 + ax + b equation but since a = 0 and b = 7 it becomes y^2 = x^3 + 7 which is the elliptic curve used in Bitcoin.

Generator point, order and cofactor - G, n and h

These 3 are all related and together they define a cyclic subgroup of elliptic curve where:

• G is a point on EC, also called the generator or base point, (x,y) coordinates represented in uncompressed format as a concatenation of x and y prefixed with 04 or in compressed format as x coordinate prefix with 02.
• n is the order of subgroup generated by point G; in other words it is the number of points that belong to this subgroup
• h is called cofactor and can be calculated as N/n where N is the order of the entire elliptic curve group. In this case cofactor is 1 so the order of the subgroup is equal to the order of the entire elliptic curve.

https://gist.github.com/7460935bba50ebe0c37f232d91377cb7

0. Private key

We all know that Bitcoin's private key is 256 bits long that has to be an integer between 1 and n, the order of subgroup. Here is my take in binary representation.

https://gist.github.com/4debc05a1b37cb6041f820a8774c6990

1. Public key

Now, public key is just a scalar multiplication of private key (k) and elliptic curve generator point (G) as P = k * G. The result is another point (x, y) on elliptic curve, we take that x coordinate, prefix it with 02 if y is positive or 03 if y is negative and there it is, the public key in compressed format.

A little bit of math and a few algorithms that we need to use for this calculation. For scalar multiplication you can add G to itself k number of times but this will be very inefficient so we are going to use "double and add" algorithm implemented in ec_multiply that in turn uses ec_add and ec_double, addition and doubling operations on elliptic curves. And last, since division is not defined over finite fields we need to multiply by the multiplicative inverse and use extended_euclidean_algorithm to find the greatest common divisor.

https://gist.github.com/6fc21c23ef965911c50abda6a46f2b64

And here it is, point on elliptic curve and scalar multiplication.

https://gist.github.com/c24025753264b07d2338e6c237446d7a

We can easily check if resulting point is still on elliptic curve.

https://gist.github.com/a05228e1457eec44e0e70c5db55ffb12

2. SHA256 hashing

Standard SHA256 hashing here, I am going to use the implementation provided in Ruby.

https://gist.github.com/3c1b26f5e0aef14a25f6aaf1956d1f4d

3. RIPEMD160 hashing

Same here, nothing new, standard RIPEMD160 hashing, no point reinventing the wheel.

https://gist.github.com/c18e93503c4a067d39992bc301146e96

4. Add version byte

Here are a few but see Bitcoin address prefixes for a complete list of all supported prefixes and resulting Base58 encodings:

• 0x00 - Bitcoin address - result prefix is 1
• 0x05 - Pay-to-Script-Hash address - result prefix is 3
• 0x6F - Testnet address - resulting prefix is either m or n

https://gist.github.com/7e0cead84dba11ce56dae16a98dc385f

5.6.7. Calculate checksum

Double SHA256 of previously calculated RIPEMD160 prefixed with version byte:

https://gist.github.com/2d9302e5f6493639d0cfe0794fda93d2

8. Wrap encoding

https://gist.github.com/a62d68f008820216c64d6e4d056c3dc9

9. Bitcoin address

The Base58 algorithm removes confusing characters like "oOiI" and also "+/" signs to make entire address selectable on double click.

https://gist.github.com/8cbdd0ebdfc674051a11a94b9419b31f

Base58 encoding and the final Bitcoin address:

https://gist.github.com/496d2e562eee3d9e6ac8a405d5a1c6d2

B. The easy way

All the steps above can be done 'the easy way', as one-liner, using excellent Libbitcoin Explorer tool:

https://gist.github.com/cf629b07206e13b22b58aa071afdcf0e

C. Conclusions

And here we are, the exact same Bitcoin address used in Bitcoin address generation tutorial is generated the hard way and the easy way. You can check the address.

References

See the most important references below and feel free to contact me if you need more info on the subject.

• Bitcoin address generation
• Elliptic curve point multiplication
• Elliptic Curve Cryptography
• The Science Behind Cryptocurrencies Cryptography
• Math behind Bitcoin