Andrey Karpati is Director of Artificial Intelligence and Autopilot Vision at Tesla.
I think blockchain is cool because it extends open source software development to open source + state. This seems like an interesting innovation in computer paradigms; We don't just share code, we can share a running computer and anyone anywhere can use it openly and without permission. The seeds of this revolution may have started with Bitcoin, so I was curious to delve into it in more detail to gain an intuitive understanding of how it works. And in the spirit of "what I can't create, I don't understand," what better way to implement Bitcoin from scratch?
We are going to create, digitally sign and broadcast a Bitcoin transaction in pure Python, from scratch and with zero dependencies. In the process, we will learn a little about how bitcoin is valuable. Let's try.
(by the way, if the visual format of this post annoys you, check out the jupyter notebook version that has identical content).
Step 1: creating a crypto entity
First, we want to create a completely new cryptographic entity, which is just a pair of keys: public and private. Bitcoin uses Elliptic Curve Cryptography (ECC) instead of something more common like RSA to secure transactions. I'm not going to delve into ECC here because others have done significantly better work, for example, I find the series of blog posts by Andrea Corbellini to be a very useful resource . We're just going to write the code here, but to understand why it works mathematically, you need to read these posts.
So bitcoin is using the secp256k1 curve
. As a newbie in the field, I found this part fascinating - there are whole libraries of different curves you can choose from, each with its own pros, cons, and other properties. NIST publishes guidelines on which to use, but people prefer to use other curves (like secp256k1) that are less likely to have backdoors built in. Be that as it may, an elliptical curve is a fairly low-dimensional mathematical object that requires only 3 integers to define:
from __future__ import annotations # PEP 563: Postponed Evaluation of Annotations
from dataclasses import dataclass # https://docs.python.org/3/library/dataclasses.html I like these a lot
@dataclass
class Curve:
"""
Elliptic Curve over the field of integers modulo a prime.
Points on the curve satisfy y^2 = x^3 + a*x + b (mod p).
"""
p: int # the prime modulus of the finite field
a: int
b: int
# secp256k1 uses a = 0, b = 7, so we're dealing with the curve y^2 = x^3 + 7 (mod p)
bitcoin_curve = Curve(
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F,
a = 0x0000000000000000000000000000000000000000000000000000000000000000, # a = 0
b = 0x0000000000000000000000000000000000000000000000000000000000000007, # b = 7
)
In addition to the curve, we define a Generator point, which is simply some fixed “starting point” in the loop of the curve that is used to start a “random walk” along the curve. A generator is a well-known and agreed constant:
@dataclass
class Point:
""" An integer point (x,y) on a Curve """
curve: Curve
x: int
y: int
G = Point(
bitcoin_curve,
x = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798,
y = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8,
)
# we can verify that the generator point is indeed on the curve, i.e. y^2 = x^3 + 7 (mod p)
print("Generator IS on the curve: ", (G.y**2 - G.x**3 - 7) % bitcoin_curve.p == 0)
# some other totally random point will of course not be on the curve, _MOST_ likely
import random
random.seed(1337)
x = random.randrange(0, bitcoin_curve.p)
y = random.randrange(0, bitcoin_curve.p)
print("Totally random point is not: ", (y**2 - x**3 - 7) % bitcoin_curve.p == 0)
Generator IS on the curve: True
Totally random point is not: False
Finally, the order of the generating point G is known, which is actually the "set size" we are working with, in terms of the integer tuples (x, y) in a loop around the curve. I like to organize this information into another data structure, which I'll call Generator:
@dataclass
class Generator:
"""
A generator over a curve: an initial point and the (pre-computed) order
"""
G: Point # a generator point on the curve
n: int # the order of the generating point, so 0*G = n*G = INF
bitcoin_gen = Generator(
G = G,
# the order of G is known and can be mathematically derived
n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141,
)
Note that we haven't actually done anything yet, this is just defining some data structures and filling them with well-known constants associated with elliptic curves used in bitcoin. This will change soon as we are ready to generate our private key. A private key (or "secret key" as I will call it later) is just a random integer that satisfies the condition 1 <= key <n (recall that n is the order of G):
# secret_key = random.randrange(1, bitcoin_gen.n) # this is how you _would_ do it
secret_key = int.from_bytes(b'Andrej is cool :P', 'big') # this is how I will do it for reproducibility
assert 1 <= secret_key < bitcoin_gen.n
print(secret_key)
22265090479312778178772228083027296664144
This is our secret key - it's a rather modest integer, but anyone who knows it can control all the funds you own in the associated bitcoin chain. In its simplest, most common use of Bitcoin, it is the only "password" that controls your account. Of course, in the extremely unlikely case that some other Andrew has manually generated his secret key, as I did above, the wallet associated with that secret key will most likely have zero bitcoin balance :).
Now we're going to generate a public key, and this is where things get interesting. A public key is a point on a curve that results from adding the generator point to itself secret_key times. those. we have: public_key = G + G + G + (secret key size) + G = secret_key * G. Note that both characters '+' (add) and '*' (times, multiply) here are very special and a little confusing. The secret key is an integer, but the point of the generator G is a tuple (x, y), which is a point on the curve, resulting in the public key of the tuple (x, y), again a point on the curve. Here we have to actually define the Add operator on the elliptic curve. He has a very specific definition and geometric interpretation (see Andrea's blog above),but the actual implementation is relatively simple:
INF = Point(None, None, None) # special point at "infinity", kind of like a zero
def extended_euclidean_algorithm(a, b):
"""
Returns (gcd, x, y) s.t. a * x + b * y == gcd
This function implements the extended Euclidean
algorithm and runs in O(log b) in the worst case,
taken from Wikipedia.
"""
old_r, r = a, b
old_s, s = 1, 0
old_t, t = 0, 1
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
return old_r, old_s, old_t
def inv(n, p):
""" returns modular multiplicate inverse m s.t. (n * m) % p == 1 """
gcd, x, y = extended_euclidean_algorithm(n, p) # pylint: disable=unused-variable
return x % p
def elliptic_curve_addition(self, other: Point) -> Point:
# handle special case of P + 0 = 0 + P = 0
if self == INF:
return other
if other == INF:
return self
# handle special case of P + (-P) = 0
if self.x == other.x and self.y != other.y:
return INF
# compute the "slope"
if self.x == other.x: # (self.y = other.y is guaranteed too per above check)
m = (3 * self.x**2 + self.curve.a) * inv(2 * self.y, self.curve.p)
else:
m = (self.y - other.y) * inv(self.x - other.x, self.curve.p)
# compute the new point
rx = (m**2 - self.x - other.x) % self.curve.p
ry = (-(m*(rx - self.x) + self.y)) % self.curve.p
return Point(self.curve, rx, ry)
Point.__add__ = elliptic_curve_addition # monkey patch addition into the Point class
I admit it can seem a little intimidating, and it took me a good half day to understand and re-get the above. Much of the complexity comes from the fact that all the math is done using modular arithmetic. Thus, even simple operations such as “/” division suddenly require algorithms such as inverse modulo
inv
. But it's important to note that this is all just a bunch of additions / multiplications over tuples (x, y) mod p, scattered everywhere in between. Let's try to generate some trivial (private, public) key pairs:
# if our secret key was the integer 1, then our public key would just be G:
sk = 1
pk = G
print(f" secret key: {sk}\n public key: {(pk.x, pk.y)}")
print("Verify the public key is on the curve: ", (pk.y**2 - pk.x**3 - 7) % bitcoin_curve.p == 0)
# if it was 2, the public key is G + G:
sk = 2
pk = G + G
print(f" secret key: {sk}\n public key: {(pk.x, pk.y)}")
print("Verify the public key is on the curve: ", (pk.y**2 - pk.x**3 - 7) % bitcoin_curve.p == 0)
# etc.:
sk = 3
pk = G + G + G
print(f" secret key: {sk}\n public key: {(pk.x, pk.y)}")
print("Verify the public key is on the curve: ", (pk.y**2 - pk.x**3 - 7) % bitcoin_curve.p == 0)
secret key: 1
public key: (55066263022277343669578718895168534326250603453777594175500187360389116729240, 32670510020758816978083085130507043184471273380659243275938904335757337482424)
Verify the public key is on the curve: True
secret key: 2
public key: (89565891926547004231252920425935692360644145829622209833684329913297188986597, 12158399299693830322967808612713398636155367887041628176798871954788371653930)
Verify the public key is on the curve: True
secret key: 3
public key: (112711660439710606056748659173929673102114977341539408544630613555209775888121, 25583027980570883691656905877401976406448868254816295069919888960541586679410)
Verify the public key is on the curve: True
Okay, we have a couple of key pairs, but we want the public key to be associated with our randomly generated private key above. Using just the above code, we would have to add G to ourselves so many times, because the secret key is a large integer. Thus, the result will be correct, but it will be very slow. Instead, let's implement a double and add algorithm to dramatically speed up re-addition. Again, see the post above to see why this works, but here it is:
def double_and_add(self, k: int) -> Point:
assert isinstance(k, int) and k >= 0
result = INF
append = self
while k:
if k & 1:
result += append
append += append
k >>= 1
return result
# monkey patch double and add into the Point class for convenience
Point.__rmul__ = double_and_add
# "verify" correctness
print(G == 1*G)
print(G + G == 2*G)
print(G + G + G == 3*G)
True
True
True
# efficiently calculate our actual public key!
public_key = secret_key * G
print(f"x: {public_key.x}\ny: {public_key.y}")
print("Verify the public key is on the curve: ", (public_key.y**2 - public_key.x**3 - 7) % bitcoin_curve.p == 0)
x: 83998262154709529558614902604110599582969848537757180553516367057821848015989
y: 37676469766173670826348691885774454391218658108212372128812329274086400588247
Verify the public key is on the curve: True
With the help of a private / public key pair, we created our crypto entity. Now it's time to get the associated Bitcoin wallet address. The wallet address is not just the public key itself, it can be deterministic based on it and has several additional advantages (for example, a built-in checksum). Before we can generate an address, we need to define some hash functions. Bitcoin uses the ubiquitous SHA-256 as well as RIPEMD-160. We could just plug and play using
hashlib
Python implementations , but it has to be a zero dependency implementation, so that's
import hashlib
a scam. So first, here is the SHA256 implementation I wrote in pure Python according to the (relatively readable) NIST FIPS PUB 180-4 document:
def gen_sha256_with_variable_scope_protector_to_not_pollute_global_namespace():
"""
SHA256 implementation.
Follows the FIPS PUB 180-4 description for calculating SHA-256 hash function
https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
Noone in their right mind should use this for any serious reason. This was written
purely for educational purposes.
"""
import math
from itertools import count, islice
# -----------------------------------------------------------------------------
# SHA-256 Functions, defined in Section 4
def rotr(x, n, size=32):
return (x >> n) | (x << size - n) & (2**size - 1)
def shr(x, n):
return x >> n
def sig0(x):
return rotr(x, 7) ^ rotr(x, 18) ^ shr(x, 3)
def sig1(x):
return rotr(x, 17) ^ rotr(x, 19) ^ shr(x, 10)
def capsig0(x):
return rotr(x, 2) ^ rotr(x, 13) ^ rotr(x, 22)
def capsig1(x):
return rotr(x, 6) ^ rotr(x, 11) ^ rotr(x, 25)
def ch(x, y, z):
return (x & y)^ (~x & z)
def maj(x, y, z):
return (x & y) ^ (x & z) ^ (y & z)
def b2i(b):
return int.from_bytes(b, 'big')
def i2b(i):
return i.to_bytes(4, 'big')
# -----------------------------------------------------------------------------
# SHA-256 Constants
def is_prime(n):
return not any(f for f in range(2,int(math.sqrt(n))+1) if n%f == 0)
def first_n_primes(n):
return islice(filter(is_prime, count(start=2)), n)
def frac_bin(f, n=32):
""" return the first n bits of fractional part of float f """
f -= math.floor(f) # get only the fractional part
f *= 2**n # shift left
f = int(f) # truncate the rest of the fractional content
return f
def genK():
"""
Follows Section 4.2.2 to generate K
The first 32 bits of the fractional parts of the cube roots of the first
64 prime numbers:
428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2
"""
return [frac_bin(p ** (1/3.0)) for p in first_n_primes(64)]
def genH():
"""
Follows Section 5.3.3 to generate the initial hash value H^0
The first 32 bits of the fractional parts of the square roots of
the first 8 prime numbers.
6a09e667 bb67ae85 3c6ef372 a54ff53a 9b05688c 510e527f 1f83d9ab 5be0cd19
"""
return [frac_bin(p ** (1/2.0)) for p in first_n_primes(8)]
# -----------------------------------------------------------------------------
def pad(b):
""" Follows Section 5.1: Padding the message """
b = bytearray(b) # convert to a mutable equivalent
l = len(b) * 8 # note: len returns number of bytes not bits
# append but "1" to the end of the message
b.append(0b10000000) # appending 10000000 in binary (=128 in decimal)
# follow by k zero bits, where k is the smallest non-negative solution to
# l + 1 + k = 448 mod 512
# i.e. pad with zeros until we reach 448 (mod 512)
while (len(b)*8) % 512 != 448:
b.append(0x00)
# the last 64-bit block is the length l of the original message
# expressed in binary (big endian)
b.extend(l.to_bytes(8, 'big'))
return b
def sha256(b: bytes) -> bytes:
# Section 4.2
K = genK()
# Section 5: Preprocessing
# Section 5.1: Pad the message
b = pad(b)
# Section 5.2: Separate the message into blocks of 512 bits (64 bytes)
blocks = [b[i:i+64] for i in range(0, len(b), 64)]
# for each message block M^1 ... M^N
H = genH() # Section 5.3
# Section 6
for M in blocks: # each block is a 64-entry array of 8-bit bytes
# 1. Prepare the message schedule, a 64-entry array of 32-bit words
W = []
for t in range(64):
if t <= 15:
# the first 16 words are just a copy of the block
W.append(bytes(M[t*4:t*4+4]))
else:
term1 = sig1(b2i(W[t-2]))
term2 = b2i(W[t-7])
term3 = sig0(b2i(W[t-15]))
term4 = b2i(W[t-16])
total = (term1 + term2 + term3 + term4) % 2**32
W.append(i2b(total))
# 2. Initialize the 8 working variables a,b,c,d,e,f,g,h with prev hash value
a, b, c, d, e, f, g, h = H
# 3.
for t in range(64):
T1 = (h + capsig1(e) + ch(e, f, g) + K[t] + b2i(W[t])) % 2**32
T2 = (capsig0(a) + maj(a, b, c)) % 2**32
h = g
g = f
f = e
e = (d + T1) % 2**32
d = c
c = b
b = a
a = (T1 + T2) % 2**32
# 4. Compute the i-th intermediate hash value H^i
delta = [a, b, c, d, e, f, g, h]
H = [(i1 + i2) % 2**32 for i1, i2 in zip(H, delta)]
return b''.join(i2b(i) for i in H)
return sha256
sha256 = gen_sha256_with_variable_scope_protector_to_not_pollute_global_namespace()
print("verify empty hash:", sha256(b'').hex()) # should be e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
print(sha256(b'here is a random bytes message, cool right?').hex())
print("number of bytes in a sha256 digest: ", len(sha256(b'')))
verify empty hash: e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855
69b9779edaa573a509999cbae415d3408c30544bad09727a1d64eff353c95b89
number of bytes in a sha256 digest: 32
Ok, the reason I wanted to implement this from scratch and stick it in here is because I want you to notice that again, there is nothing too scary inside. SHA256 takes a few bytes of a message to be hashed, first populates the message, then breaks it apart, and passes those chunks into what can best be described as the fancy "bit mixer" defined in section 3 that contains multiple bit shifts and binary operations, organized in a way that I honestly cannot understand, but it leads to the wonderful properties that SHA256 offers. In particular, it creates a chaotic-looking, short, fixed-size digest of any variable-size original message, while scrambling is irreversible.and also, in principle, it is impossible from a computational point of view to create another message that is hashed with the same digest.
Bitcoin uses SHA256 all over the place to create hashes, and of course it is a key element in Bitcoin's Proof of Work, the purpose of which is to change the block of transactions until the whole thing is hashed to a low enough number (when the digest bytes are interpreted as a number). That, due to the good properties of SHA256, it can only be done with brute force, brute force. Thus, all ASICs designed for efficient mining are just incredibly optimized, close-to-the-metal implementations of the above code.
Anyway, before we can generate our address, we'll also need the RIPEMD160 hash function, which I found on the internet, shortened and cleaned up:
def gen_ripemd160_with_variable_scope_protector_to_not_pollute_global_namespace():
import sys
import struct
# -----------------------------------------------------------------------------
# public interface
def ripemd160(b: bytes) -> bytes:
""" simple wrapper for a simpler API to this hash function, just bytes to bytes """
ctx = RMDContext()
RMD160Update(ctx, b, len(b))
digest = RMD160Final(ctx)
return digest
# -----------------------------------------------------------------------------
class RMDContext:
def __init__(self):
self.state = [0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0] # uint32
self.count = 0 # uint64
self.buffer = [0]*64 # uchar
def RMD160Update(ctx, inp, inplen):
have = int((ctx.count // 8) % 64)
inplen = int(inplen)
need = 64 - have
ctx.count += 8 * inplen
off = 0
if inplen >= need:
if have:
for i in range(need):
ctx.buffer[have+i] = inp[i]
RMD160Transform(ctx.state, ctx.buffer)
off = need
have = 0
while off + 64 <= inplen:
RMD160Transform(ctx.state, inp[off:])
off += 64
if off < inplen:
for i in range(inplen - off):
ctx.buffer[have+i] = inp[off+i]
def RMD160Final(ctx):
size = struct.pack("<Q", ctx.count)
padlen = 64 - ((ctx.count // 8) % 64)
if padlen < 1 + 8:
padlen += 64
RMD160Update(ctx, PADDING, padlen-8)
RMD160Update(ctx, size, 8)
return struct.pack("<5L", *ctx.state)
# -----------------------------------------------------------------------------
K0 = 0x00000000
K1 = 0x5A827999
K2 = 0x6ED9EBA1
K3 = 0x8F1BBCDC
K4 = 0xA953FD4E
KK0 = 0x50A28BE6
KK1 = 0x5C4DD124
KK2 = 0x6D703EF3
KK3 = 0x7A6D76E9
KK4 = 0x00000000
PADDING = [0x80] + [0]*63
def ROL(n, x):
return ((x << n) & 0xffffffff) | (x >> (32 - n))
def F0(x, y, z):
return x ^ y ^ z
def F1(x, y, z):
return (x & y) | (((~x) % 0x100000000) & z)
def F2(x, y, z):
return (x | ((~y) % 0x100000000)) ^ z
def F3(x, y, z):
return (x & z) | (((~z) % 0x100000000) & y)
def F4(x, y, z):
return x ^ (y | ((~z) % 0x100000000))
def R(a, b, c, d, e, Fj, Kj, sj, rj, X):
a = ROL(sj, (a + Fj(b, c, d) + X[rj] + Kj) % 0x100000000) + e
c = ROL(10, c)
return a % 0x100000000, c
def RMD160Transform(state, block): #uint32 state[5], uchar block[64]
x = [0]*16
assert sys.byteorder == 'little', "Only little endian is supported atm for RIPEMD160"
x = struct.unpack('<16L', bytes(block[0:64]))
a = state[0]
b = state[1]
c = state[2]
d = state[3]
e = state[4]
#/* Round 1 */
a, c = R(a, b, c, d, e, F0, K0, 11, 0, x)
e, b = R(e, a, b, c, d, F0, K0, 14, 1, x)
d, a = R(d, e, a, b, c, F0, K0, 15, 2, x)
c, e = R(c, d, e, a, b, F0, K0, 12, 3, x)
b, d = R(b, c, d, e, a, F0, K0, 5, 4, x)
a, c = R(a, b, c, d, e, F0, K0, 8, 5, x)
e, b = R(e, a, b, c, d, F0, K0, 7, 6, x)
d, a = R(d, e, a, b, c, F0, K0, 9, 7, x)
c, e = R(c, d, e, a, b, F0, K0, 11, 8, x)
b, d = R(b, c, d, e, a, F0, K0, 13, 9, x)
a, c = R(a, b, c, d, e, F0, K0, 14, 10, x)
e, b = R(e, a, b, c, d, F0, K0, 15, 11, x)
d, a = R(d, e, a, b, c, F0, K0, 6, 12, x)
c, e = R(c, d, e, a, b, F0, K0, 7, 13, x)
b, d = R(b, c, d, e, a, F0, K0, 9, 14, x)
a, c = R(a, b, c, d, e, F0, K0, 8, 15, x) #/* #15 */
#/* Round 2 */
e, b = R(e, a, b, c, d, F1, K1, 7, 7, x)
d, a = R(d, e, a, b, c, F1, K1, 6, 4, x)
c, e = R(c, d, e, a, b, F1, K1, 8, 13, x)
b, d = R(b, c, d, e, a, F1, K1, 13, 1, x)
a, c = R(a, b, c, d, e, F1, K1, 11, 10, x)
e, b = R(e, a, b, c, d, F1, K1, 9, 6, x)
d, a = R(d, e, a, b, c, F1, K1, 7, 15, x)
c, e = R(c, d, e, a, b, F1, K1, 15, 3, x)
b, d = R(b, c, d, e, a, F1, K1, 7, 12, x)
a, c = R(a, b, c, d, e, F1, K1, 12, 0, x)
e, b = R(e, a, b, c, d, F1, K1, 15, 9, x)
d, a = R(d, e, a, b, c, F1, K1, 9, 5, x)
c, e = R(c, d, e, a, b, F1, K1, 11, 2, x)
b, d = R(b, c, d, e, a, F1, K1, 7, 14, x)
a, c = R(a, b, c, d, e, F1, K1, 13, 11, x)
e, b = R(e, a, b, c, d, F1, K1, 12, 8, x) #/* #31 */
#/* Round 3 */
d, a = R(d, e, a, b, c, F2, K2, 11, 3, x)
c, e = R(c, d, e, a, b, F2, K2, 13, 10, x)
b, d = R(b, c, d, e, a, F2, K2, 6, 14, x)
a, c = R(a, b, c, d, e, F2, K2, 7, 4, x)
e, b = R(e, a, b, c, d, F2, K2, 14, 9, x)
d, a = R(d, e, a, b, c, F2, K2, 9, 15, x)
c, e = R(c, d, e, a, b, F2, K2, 13, 8, x)
b, d = R(b, c, d, e, a, F2, K2, 15, 1, x)
a, c = R(a, b, c, d, e, F2, K2, 14, 2, x)
e, b = R(e, a, b, c, d, F2, K2, 8, 7, x)
d, a = R(d, e, a, b, c, F2, K2, 13, 0, x)
c, e = R(c, d, e, a, b, F2, K2, 6, 6, x)
b, d = R(b, c, d, e, a, F2, K2, 5, 13, x)
a, c = R(a, b, c, d, e, F2, K2, 12, 11, x)
e, b = R(e, a, b, c, d, F2, K2, 7, 5, x)
d, a = R(d, e, a, b, c, F2, K2, 5, 12, x) #/* #47 */
#/* Round 4 */
c, e = R(c, d, e, a, b, F3, K3, 11, 1, x)
b, d = R(b, c, d, e, a, F3, K3, 12, 9, x)
a, c = R(a, b, c, d, e, F3, K3, 14, 11, x)
e, b = R(e, a, b, c, d, F3, K3, 15, 10, x)
d, a = R(d, e, a, b, c, F3, K3, 14, 0, x)
c, e = R(c, d, e, a, b, F3, K3, 15, 8, x)
b, d = R(b, c, d, e, a, F3, K3, 9, 12, x)
a, c = R(a, b, c, d, e, F3, K3, 8, 4, x)
e, b = R(e, a, b, c, d, F3, K3, 9, 13, x)
d, a = R(d, e, a, b, c, F3, K3, 14, 3, x)
c, e = R(c, d, e, a, b, F3, K3, 5, 7, x)
b, d = R(b, c, d, e, a, F3, K3, 6, 15, x)
a, c = R(a, b, c, d, e, F3, K3, 8, 14, x)
e, b = R(e, a, b, c, d, F3, K3, 6, 5, x)
d, a = R(d, e, a, b, c, F3, K3, 5, 6, x)
c, e = R(c, d, e, a, b, F3, K3, 12, 2, x) #/* #63 */
#/* Round 5 */
b, d = R(b, c, d, e, a, F4, K4, 9, 4, x)
a, c = R(a, b, c, d, e, F4, K4, 15, 0, x)
e, b = R(e, a, b, c, d, F4, K4, 5, 5, x)
d, a = R(d, e, a, b, c, F4, K4, 11, 9, x)
c, e = R(c, d, e, a, b, F4, K4, 6, 7, x)
b, d = R(b, c, d, e, a, F4, K4, 8, 12, x)
a, c = R(a, b, c, d, e, F4, K4, 13, 2, x)
e, b = R(e, a, b, c, d, F4, K4, 12, 10, x)
d, a = R(d, e, a, b, c, F4, K4, 5, 14, x)
c, e = R(c, d, e, a, b, F4, K4, 12, 1, x)
b, d = R(b, c, d, e, a, F4, K4, 13, 3, x)
a, c = R(a, b, c, d, e, F4, K4, 14, 8, x)
e, b = R(e, a, b, c, d, F4, K4, 11, 11, x)
d, a = R(d, e, a, b, c, F4, K4, 8, 6, x)
c, e = R(c, d, e, a, b, F4, K4, 5, 15, x)
b, d = R(b, c, d, e, a, F4, K4, 6, 13, x) #/* #79 */
aa = a
bb = b
cc = c
dd = d
ee = e
a = state[0]
b = state[1]
c = state[2]
d = state[3]
e = state[4]
#/* Parallel round 1 */
a, c = R(a, b, c, d, e, F4, KK0, 8, 5, x)
e, b = R(e, a, b, c, d, F4, KK0, 9, 14, x)
d, a = R(d, e, a, b, c, F4, KK0, 9, 7, x)
c, e = R(c, d, e, a, b, F4, KK0, 11, 0, x)
b, d = R(b, c, d, e, a, F4, KK0, 13, 9, x)
a, c = R(a, b, c, d, e, F4, KK0, 15, 2, x)
e, b = R(e, a, b, c, d, F4, KK0, 15, 11, x)
d, a = R(d, e, a, b, c, F4, KK0, 5, 4, x)
c, e = R(c, d, e, a, b, F4, KK0, 7, 13, x)
b, d = R(b, c, d, e, a, F4, KK0, 7, 6, x)
a, c = R(a, b, c, d, e, F4, KK0, 8, 15, x)
e, b = R(e, a, b, c, d, F4, KK0, 11, 8, x)
d, a = R(d, e, a, b, c, F4, KK0, 14, 1, x)
c, e = R(c, d, e, a, b, F4, KK0, 14, 10, x)
b, d = R(b, c, d, e, a, F4, KK0, 12, 3, x)
a, c = R(a, b, c, d, e, F4, KK0, 6, 12, x) #/* #15 */
#/* Parallel round 2 */
e, b = R(e, a, b, c, d, F3, KK1, 9, 6, x)
d, a = R(d, e, a, b, c, F3, KK1, 13, 11, x)
c, e = R(c, d, e, a, b, F3, KK1, 15, 3, x)
b, d = R(b, c, d, e, a, F3, KK1, 7, 7, x)
a, c = R(a, b, c, d, e, F3, KK1, 12, 0, x)
e, b = R(e, a, b, c, d, F3, KK1, 8, 13, x)
d, a = R(d, e, a, b, c, F3, KK1, 9, 5, x)
c, e = R(c, d, e, a, b, F3, KK1, 11, 10, x)
b, d = R(b, c, d, e, a, F3, KK1, 7, 14, x)
a, c = R(a, b, c, d, e, F3, KK1, 7, 15, x)
e, b = R(e, a, b, c, d, F3, KK1, 12, 8, x)
d, a = R(d, e, a, b, c, F3, KK1, 7, 12, x)
c, e = R(c, d, e, a, b, F3, KK1, 6, 4, x)
b, d = R(b, c, d, e, a, F3, KK1, 15, 9, x)
a, c = R(a, b, c, d, e, F3, KK1, 13, 1, x)
e, b = R(e, a, b, c, d, F3, KK1, 11, 2, x) #/* #31 */
#/* Parallel round 3 */
d, a = R(d, e, a, b, c, F2, KK2, 9, 15, x)
c, e = R(c, d, e, a, b, F2, KK2, 7, 5, x)
b, d = R(b, c, d, e, a, F2, KK2, 15, 1, x)
a, c = R(a, b, c, d, e, F2, KK2, 11, 3, x)
e, b = R(e, a, b, c, d, F2, KK2, 8, 7, x)
d, a = R(d, e, a, b, c, F2, KK2, 6, 14, x)
c, e = R(c, d, e, a, b, F2, KK2, 6, 6, x)
b, d = R(b, c, d, e, a, F2, KK2, 14, 9, x)
a, c = R(a, b, c, d, e, F2, KK2, 12, 11, x)
e, b = R(e, a, b, c, d, F2, KK2, 13, 8, x)
d, a = R(d, e, a, b, c, F2, KK2, 5, 12, x)
c, e = R(c, d, e, a, b, F2, KK2, 14, 2, x)
b, d = R(b, c, d, e, a, F2, KK2, 13, 10, x)
a, c = R(a, b, c, d, e, F2, KK2, 13, 0, x)
e, b = R(e, a, b, c, d, F2, KK2, 7, 4, x)
d, a = R(d, e, a, b, c, F2, KK2, 5, 13, x) #/* #47 */
#/* Parallel round 4 */
c, e = R(c, d, e, a, b, F1, KK3, 15, 8, x)
b, d = R(b, c, d, e, a, F1, KK3, 5, 6, x)
a, c = R(a, b, c, d, e, F1, KK3, 8, 4, x)
e, b = R(e, a, b, c, d, F1, KK3, 11, 1, x)
d, a = R(d, e, a, b, c, F1, KK3, 14, 3, x)
c, e = R(c, d, e, a, b, F1, KK3, 14, 11, x)
b, d = R(b, c, d, e, a, F1, KK3, 6, 15, x)
a, c = R(a, b, c, d, e, F1, KK3, 14, 0, x)
e, b = R(e, a, b, c, d, F1, KK3, 6, 5, x)
d, a = R(d, e, a, b, c, F1, KK3, 9, 12, x)
c, e = R(c, d, e, a, b, F1, KK3, 12, 2, x)
b, d = R(b, c, d, e, a, F1, KK3, 9, 13, x)
a, c = R(a, b, c, d, e, F1, KK3, 12, 9, x)
e, b = R(e, a, b, c, d, F1, KK3, 5, 7, x)
d, a = R(d, e, a, b, c, F1, KK3, 15, 10, x)
c, e = R(c, d, e, a, b, F1, KK3, 8, 14, x) #/* #63 */
#/* Parallel round 5 */
b, d = R(b, c, d, e, a, F0, KK4, 8, 12, x)
a, c = R(a, b, c, d, e, F0, KK4, 5, 15, x)
e, b = R(e, a, b, c, d, F0, KK4, 12, 10, x)
d, a = R(d, e, a, b, c, F0, KK4, 9, 4, x)
c, e = R(c, d, e, a, b, F0, KK4, 12, 1, x)
b, d = R(b, c, d, e, a, F0, KK4, 5, 5, x)
a, c = R(a, b, c, d, e, F0, KK4, 14, 8, x)
e, b = R(e, a, b, c, d, F0, KK4, 6, 7, x)
d, a = R(d, e, a, b, c, F0, KK4, 8, 6, x)
c, e = R(c, d, e, a, b, F0, KK4, 13, 2, x)
b, d = R(b, c, d, e, a, F0, KK4, 6, 13, x)
a, c = R(a, b, c, d, e, F0, KK4, 5, 14, x)
e, b = R(e, a, b, c, d, F0, KK4, 15, 0, x)
d, a = R(d, e, a, b, c, F0, KK4, 13, 3, x)
c, e = R(c, d, e, a, b, F0, KK4, 11, 9, x)
b, d = R(b, c, d, e, a, F0, KK4, 11, 11, x) #/* #79 */
t = (state[1] + cc + d) % 0x100000000
state[1] = (state[2] + dd + e) % 0x100000000
state[2] = (state[3] + ee + a) % 0x100000000
state[3] = (state[4] + aa + b) % 0x100000000
state[4] = (state[0] + bb + c) % 0x100000000
state[0] = t % 0x100000000
return ripemd160
ripemd160 = gen_ripemd160_with_variable_scope_protector_to_not_pollute_global_namespace()
print(ripemd160(b'hello this is a test').hex())
print("number of bytes in a RIPEMD-160 digest: ", len(ripemd160(b'')))
f51960af7dd4813a587ab26388ddab3b28d1f7b4
number of bytes in a RIPEMD-160 digest: 20
As with SHA256 above, we again see a "bit scrambler" of many binary operations. Pretty cool.
So, we are finally ready to receive our bitcoin address. We're going to do this elegantly by creating a subclass
Point
called
PublicKey
, which, again, is just a point on a curve, but now has some additional semantics and interpretation of the bitcoin public key, as well as some techniques to encode / decode the key into bytes for communication in the bitcoin protocol.
class PublicKey(Point):
"""
The public key is just a Point on a Curve, but has some additional specific
encoding / decoding functionality that this class implements.
"""
@classmethod
def from_point(cls, pt: Point):
""" promote a Point to be a PublicKey """
return cls(pt.curve, pt.x, pt.y)
def encode(self, compressed, hash160=False):
""" return the SEC bytes encoding of the public key Point """
# calculate the bytes
if compressed:
# (x,y) is very redundant. Because y^2 = x^3 + 7,
# we can just encode x, and then y = +/- sqrt(x^3 + 7),
# so we need one more bit to encode whether it was the + or the -
# but because this is modular arithmetic there is no +/-, instead
# it can be shown that one y will always be even and the other odd.
prefix = b'\x02' if self.y % 2 == 0 else b'\x03'
pkb = prefix + self.x.to_bytes(32, 'big')
else:
pkb = b'\x04' + self.x.to_bytes(32, 'big') + self.y.to_bytes(32, 'big')
# hash if desired
return ripemd160(sha256(pkb)) if hash160 else pkb
def address(self, net: str, compressed: bool) -> str:
""" return the associated bitcoin address for this public key as string """
# encode the public key into bytes and hash to get the payload
pkb_hash = self.encode(compressed=compressed, hash160=True)
# add version byte (0x00 for Main Network, or 0x6f for Test Network)
version = {'main': b'\x00', 'test': b'\x6f'}
ver_pkb_hash = version[net] + pkb_hash
# calculate the checksum
checksum = sha256(sha256(ver_pkb_hash))[:4]
# append to form the full 25-byte binary Bitcoin Address
byte_address = ver_pkb_hash + checksum
# finally b58 encode the result
b58check_address = b58encode(byte_address)
return b58check_address
We are not ready to try this class out yet, because you will notice that there is another required dependency here, namely the b58 encoding function
b58encode
. It's just a bitcoin-specific byte encoding that uses a base 58 characters of the alphabet which are very unambiguous. For example, it doesn't use "O" and "0" because it's very easy to mess up on paper. So, we need to take our bitcoin address (which is 25 bytes raw), convert it to base 58, and print the characters. The raw 25 bytes of our address contains 1 byte for the version (Bitcoin's "mainnet" is
b'\x00'
, while Bitcoin's "testnet" uses
b'\x6f'
), then 20 bytes from the hash. digest and, finally, 4 bytes for the checksum, so that we can give an error with a probability
1–1/2** 4 = 93,75%
in case the user entered his bitcoin address incorrectly in any text field. So here is the b58 encoding:
# base58 encoding / decoding utilities
# reference: https://en.bitcoin.it/wiki/Base58Check_encoding
alphabet = '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
def b58encode(b: bytes) -> str:
assert len(b) == 25 # version is 1 byte, pkb_hash 20 bytes, checksum 4 bytes
n = int.from_bytes(b, 'big')
chars = []
while n:
n, i = divmod(n, 58)
chars.append(alphabet[i])
# special case handle the leading 0 bytes... ¯\_(ツ)_/¯
num_leading_zeros = len(b) - len(b.lstrip(b'\x00'))
res = num_leading_zeros * alphabet[0] + ''.join(reversed(chars))
return res
Now let's print our bitcoin address:
# we are going to use the develop's Bitcoin parallel universe "test net" for this demo, so net='test'
address = PublicKey.from_point(public_key).address(net='test', compressed=True)
print(address)
mnNcaVkC35ezZSgvn8fhXEa9QTHSUtPfzQ
Cool, we can now check some block explorer website to make sure this address has never been executed before: www.blockchain.com/btc-testnet/address/mnNcaVkC35ezZSgvn8fhXEa9QTHSUtPfzQ... By the end of this tutorial, this will not happen, but at the time of writing, I did see that this address was "clean", so no one generated or used the secret key on the testnet as we did above. It makes sense because there must have been some other "Andrey" with a bad sense of humor who was also messing with bitcoin. But we can also verify some of the super secret secret keys that we expect people to have used in the past. For example, we can check the address belonging to the smallest valid secret key equal to 1, where the public key is exactly the generator point :). This is how we get it:
lol_secret_key = 1
lol_public_key = lol_secret_key * G
lol_address = PublicKey.from_point(lol_public_key).address(net='test', compressed=True)
lol_address
'mrCDrCybB6J1vRfbwM5hemdJz73FwDBC8r'
In fact, as we can see in the blockchain explorer, at the time of writing, this address has transacted 1,812 times and has a balance of 0.00 BTC. This makes sense, because if it had some kind of balance (in the naive case, modulo some subtleties with the scripting language we'll be using), then anyone could just spend it, because they know the secret key ( 1) and can use it to digitally sign transactions that spend them. We'll see how this works shortly.
Part 1: Summary to date
We can generate a crypto entity consisting of a secret key (a random integer) known only to us and a derivative of the public key by jumping on an elliptic curve using scalar multiplication of the generation point on bitcoin's elliptic curve. We then also got an associated bitcoin address that we can share with others to request money, and two hash functions were introduced for this (SHA256 and RIPEMD160). Here are three important quantities, summarized and printed again:
print("Our first Bitcoin identity:")
print("1. secret key: ", secret_key)
print("2. public key: ", (public_key.x, public_key.y))
print("3. Bitcoin address: ", address)
Our first Bitcoin identity:
1. secret key: 22265090479312778178772228083027296664144
2. public key: (83998262154709529558614902604110599582969848537757180553516367057821848015989, 37676469766173670826348691885774454391218658108212372128812329274086400588247)
3. Bitcoin address: mnNcaVkC35ezZSgvn8fhXEa9QTHSUtPfzQ
To be continued
- Part 2: Obtaining seed funds + intro to Bitcoin under the hood
- Part 3: Crafting our transaction