# 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.

```
ruby> p = 2**256 - 2**32 - 2**9 - 2**8 - 2**7 - 2**6 - 2**4 - 1
=> 115792089237316195423570985008687907853269984665640564039457584007908834671663
```

#### 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.

```
ruby> G = '0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8'
=> "0479BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8"
ruby> Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
=> 55066263022277343669578718895168534326250603453777594175500187360389116729240
ruby> Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
=> 32670510020758816978083085130507043184471273380659243275938904335757337482424
ruby> n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
ruby> h = 1
```

### 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.

```
ruby> k = 0b1100011100001010010100111101101101010001100000111111101000010011010101001010011111000000100010100011100000001111001111100100011100111011101001110011111111001101001000111111000101100001000000011010111011011001010011010001000000110001100100001011100100101
=> 11253563012059685825953619222107823549092147699031672238385790369351542642469
ruby> k.to_s 16
=> "18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725"
```

### 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 even or `03`

if `y`

is odd 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.

```
def ec_multiply(m, px, py, pn)
nx, ny = px, py
qx, qy = 0, 0
while m > 0
qx, qy = ec_add qx, qy, nx, ny, pn if m&1 == 1
nx, ny = ec_double nx, ny, pn
m >>= 1
end
[qx, qy]
end
def ec_add(ax, ay, bx, by, pn)
return [ax, ay] if bx == 0 && by == 0
return [bx, by] if ax == 0 && ay == 0
return ec_double(ax, ay, pn) if ax == bx && ay == by
i_bax = inverse(ax - bx, pn)
slope = ((ay - by) * i_bax) % pn
x = (slope**2 - ax - bx) % pn
y = (slope*(ax - x) - ay) % pn
[x, y]
end
def ec_double(px, py, pn)
i_2y = inverse(2 * py, pn)
slope = (3 * px**2 * i_2y) % pn
x = (slope**2 - 2 * px) % pn
y = (slope*(px - x) - py) % pn
[x, y]
end
def inverse(n, p)
gcd, x, y = extended_euclidean_algorithm(n, p)
(n * x + p * y) % p == gcd || raise('invalid gcd')
gcd == 1 || raise('no multiplicative inverse')
x % p
end
def extended_euclidean_algorithm(a, b)
s, old_s = 0, 1
t, old_t = 1, 0
r, old_r = b, a
while r != 0
quotient = old_r / r
old_r, r = r, old_r - quotient * r
old_s, s = s, old_s - quotient * s
old_t, t = t, old_t - quotient * t
end
[old_r, old_s, old_t]
end
```

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

```
ruby> Px, Py = ec_multiply(k, Gx, Gy, p)
=> [36422191471907241029883925342251831624200921388586025344128047678873736520530, 20277110887056303803699431755396003735040374760118964734768299847012543114150]
ruby> P = "#{Py.even? ? '02' : '03'}#{Px.to_s(16)}"
=> "0250863ad64a87ae8a2fe83c1af1a8403cb53f53e486d8511dad8a04887e5b2352"
```

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

```
((Px**3 + 7 - Py**2) % p == 0) || raise('public key point is not on the curve')
```

### 2. SHA256 hashing

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

```
ruby> require 'digest'
ruby> sha256 = Digest::SHA256.hexdigest([P].pack('H*'))
=> "0b7c28c9b7290c98d7438e70b3d3f7c848fbd7d1dc194ff83f4f7cc9b1378e98"
```

### 3. RIPEMD160 hashing

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

```
ruby> ripemd160 = Digest::RMD160.hexdigest([sha256].pack('H*'))
=> "f54a5851e9372b87810a8e60cdd2e7cfd80b6e31"
```

### 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

```
ruby> with_version = "00#{ripemd160}"
=> "00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31"
```

### 5.6.7. Calculate checksum

Double SHA256 of previously calculated RIPEMD160 prefixed with version byte:

```
ruby> checksum = Digest::SHA256.hexdigest(Digest::SHA256.digest([with_version].pack('H*')))[0, 8]
=> "c7f18fe8"
```

### 8. Wrap encoding

```
ruby> wrap_encode = "#{with_version}#{checksum}"
=> "00f54a5851e9372b87810a8e60cdd2e7cfd80b6e31c7f18fe8"
```

### 9. Bitcoin address

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

```
def base58(binary_hash)
alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
value = binary_hash.unpack('H*')[0].to_i 16
output = ''
while value > 0
remainder = value % 58
value /= 58
output += alphabet[remainder]
end
output += alphabet[0] * binary_hash.bytes.find_index{|b| b != 0}
output.reverse
end
```

Base58 encoding and the final Bitcoin address:

```
ruby> base58([wrap_encode].pack('H*'))
=> "1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs"
```

## B. The easy way

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

```
shell> echo 18e14a7b6a307f426a94f8114701e7c8e774e7f9a47e2c2035db29a206321725 | bx ec-to-public | bx sha256 | bx ripemd160 | bx wrap-encode | bx base58-encode
1PMycacnJaSqwwJqjawXBErnLsZ7RkXUAs
```

## 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.

## D. 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

The end.