## Bitcoin

This article will present 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'
ruby> Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
=> 55066263022277343669578718895168534326250603453777594175500187360389116729240
=> 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)}"


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"


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"


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*').to_i 16
output = ''
while value > 0
remainder = value % 58
value /= 58
output += alphabet[remainder]
end
output += alphabet * 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.

The end.