Прежде чем перейти к статье, хочу вам представить, экономическую онлайн игру Brave Knights, в которой вы можете играть и зарабатывать. Регистируйтесь, играйте и зарабатывайте!
Андрей Карпати — директор по искусственному интеллекту и Autopilot Vision в Tesla.
Я считаю, что блокчейн — классная штука, потому что он расширяет open source разработку софта до open source + state. Это кажется интересным нововведением в компьютерных парадигмах; Мы не просто делиться кодом, мы можем предоставить общий доступ к работающему компьютеру, и любой человек в любом месте может использовать его открыто и без разрешения. Семена этой революции, возможно, начались с биткойна, поэтому мне стало любопытно вникнуть в него более подробно, чтобы получить интуитивное понимание того, как он работает. И в духе «то, что я не могу создать, я не понимаю», что может быть лучше, чем реализовать биткойна с нуля?
Мы собираемся создать, поставить цифровую подпись и транслировать биткойн-транзакцию на чистом Python, с нуля и с нулевыми зависимостями. В процессе мы немного узнаем о том, как биткойн представляет ценность. Давай попробуем.
(кстати, если визуальный формат этого поста вас раздражает, посмотрите версию jupyter notebook, у которой идентичный контент).
Шаг 1: создание крипто сущности
Для начала мы хотим создать совершенно новую криптографическую сущность, которая представляет собой всего лишь пару ключей: публичный и приватный. Биткойн использует криптографию на эллиптических кривых (Elliptic-Сurve Сryptography, ECC) вместо чего-то более распространенного, например RSA, для защиты транзакций. Я не собираюсь здесь углубляться в ECC, потому что другие проделали значительно лучшую работу, например, я считаю серию постов в блоге Андреа Корбеллини очень полезным ресурсом. Здесь мы просто напишем код, но чтобы понять, почему он работает математически, вам нужно прочитать эти посты.
Итак, биткойн использует кривую secp256k1. Как новичок в этой области, я нашел эту часть увлекательной — есть целые библиотеки разных кривых, из которых вы можете выбирать, у каждой свои плюсы, минусы и прочие свойства. NIST публикует рекомендации о том, какие из них использовать, но люди предпочитают использовать другие кривые (например, secp256k1), которые с меньшей вероятностью будут иметь встроенные бэкдоры. Как бы то ни было, эллиптическая кривая — это математический объект довольно низкой размерности, для определения которого требуется всего 3 целых числа: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
)В дополнение к кривой мы определяем точку Generator, которая является просто некоторой фиксированной «начальной точкой» в цикле кривой, которая используется для запуска «случайного блуждания» по кривой. Генератор — это общеизвестная и согласованная константа:
@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Наконец, известен порядок порождающей точки G, который фактически является «размером множества», с которым мы работаем, в терминах целочисленных кортежей (x, y) в цикле вокруг кривой. Мне нравится организовывать эту информацию в еще одну структуру данных, которую я назову 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,
)Обратите внимание, что на самом деле мы пока ничего не сделали, это всего лишь определение некоторых структур данных и их заполнение общеизвестными константами, связанными с эллиптическими кривыми, используемыми в биткойне. Это скоро изменится, так как мы готовы сгенерировать наш закрытый ключ. Закрытый ключ (или «секретный ключ», как я буду называть его в дальнейшем) — это просто случайное целое число, удовлетворяющее условию 1 <= key <n (напомним, что n — это порядок 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Это наш секретный ключ — это довольно скромное целое число, но любой, кто его знает, может контролировать все средства, которыми вы владеете в связанной с ним цепочке биткойнов. В простейшем, наиболее распространенном варианте использования биткойна, — это единственный «пароль», который контролирует вашу учетную запись. Конечно, в чрезвычайно маловероятном случае, когда какой-то другой Андрей вручную сгенерировал свой секретный ключ, как я сделал выше, кошелек, связанный с этим секретным ключом, скорее всего, будет иметь нулевой баланс биткойнов :).
Теперь мы собираемся сгенерировать открытый ключ, и здесь все становится интереснее. Открытый ключ — это точка на кривой, которая получается в результате добавления точки генератора к самой себе secret_key раз. т.е. у нас есть: public_key = G + G + G + (размер секретного ключа) + G = secret_key * G. Обратите внимание, что оба символа '+' (добавить) и '*' (разы, умножить) здесь очень особенные и немного сбивающие с толку. Секретный ключ является целым числом, но точка генератора G представляет собой кортеж (x, y), который является точкой на кривой, в результате чего получается открытый ключ кортежа (x, y), снова точка на кривой. Здесь мы должны фактически определить оператор Сложения на эллиптической кривой. У него очень конкретное определение и геометрическая интерпретация (см. про блог Андреа выше), но фактическая реализация относительно проста:
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Я признаю, что это может показаться немного пугающим, и понимание и повторное получение вышеупомянутого заняло у меня добрую половину дня. Большая часть сложности возникает из-за того, что вся математика выполняется с помощью модульной арифметики. Таким образом, даже простые операции, такие как деление «/», внезапно требуют алгоритмов, таких как обратный элемен по модулю
inv. Но важно отметить, что все это просто набор сложений/умножений по кортежам (x, y) по модулю p, разбросанным повсюду между ними. Давайте попробуем сгенерировать несколько тривиальных (приватных, публичных) пар ключей:# 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Хорошо, у нас есть несколько пар ключей, но мы хотим, чтобы открытый ключ был связан с нашим случайно созданным секретным ключом, указанным выше. Используя только приведенный выше код, нам пришлось бы добавлять G к самому себе очень много раз, потому что секретный ключ — это большое целое число. Таким образом, результат будет правильным, но он будет работать очень медленно. Вместо этого давайте реализуем алгоритм «удвоить и сложить» (double and add), чтобы значительно ускорить повторное сложение. Опять же, посмотрите сообщение выше, чтобы узнать, почему это работает, но вот оно:
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С помощью пары закрытый/открытый ключ мы создали нашу криптоисущность. Теперь пришло время получить связанный адрес биткойн-кошелька. Адрес кошелька — это не просто сам открытый ключ, он может быть детерминирован на его основе и имеет несколько дополнительных преимуществ (например, встроенную контрольную сумму). Прежде чем мы сможем сгенерировать адрес, нам нужно определить некоторые хэш-функции. Биткойн использует вездесущий SHA-256, а также RIPEMD-160. Мы могли бы просто подключать и играть, используя реализации в
hashlib Python, но это должна быть реализация с нулевой зависимостью, так что import hashlib является жульничеством. Итак, сначала вот реализация SHA256, которую я написал на чистом Python в соответствии с (относительно читаемым) документом NIST FIPS PUB 180-4: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Хорошо, причина, по которой я хотел реализовать это с нуля и вставить сюда, заключается в том, что я хочу, чтобы вы заметили, что опять же, внутри нет ничего слишком страшного. SHA256 принимает несколько байтов сообщения, которое должно быть хэшировано, сначала заполняет сообщение, затем разбивает его на части и передает эти фрагменты в то, что лучше всего можно описать как причудливый «битовый миксер», определенный в разделе 3, который содержит несколько битовых сдвигов и бинарных операций, организованных таким образом, который, откровенно говоря, я не в силах понять, но это приводит к прекрасным свойствам, которые предлагает SHA256. В частности, он создает хаоично-выглядящий короткий дайджест фиксированного размера любого исходного сообщения переменного размера при том скремблирование необратимо, а также в принципе невозможно с вычислительной точки зрения создать другое сообщение, которое хешируется таким же дайджестом.
Биткойн повсеместно использует SHA256 для создания хэшей, и, конечно же, это ключевой элемент в Proof of Work биткойна, цель которого состоит в том, чтобы изменить блок транзакций до тех пор, пока все это не хешируется до достаточно низкого числа (когда байты дайджеста интерпретируется как число). Что из-за хороших свойств SHA256 может быть выполнено только с помощью брут форса, полного перебора. Таким образом, все ASIC, предназначенные для эффективного майнинга, представляют собой просто невероятно оптимизированные, close-to-the-metal реализации указанного выше кода.
В любом случае, прежде чем мы сможем сгенерировать наш адрес, нам также понадобится хэш-функция RIPEMD160, которую я нашел в Интернете, сократил и очистил:
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Как и в случае с SHA256 выше, мы снова видим «битовый скремблер» множества двоичных операций. Довольно круто.
Итак, мы наконец-то готовы получить наш биткойн-адрес. Мы собираемся сделать это элегантно, создав подкласс
Point под названием PublicKey, который, опять же, является просто точкой на кривой, но теперь имеет некоторую дополнительную семантику и интерпретацию открытого ключа биткойна, а также некоторые методы кодирования/декодирования ключа в байты для связи в протоколе биткойн.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Мы еще не готовы испытать этот класс, потому что вы заметите, что здесь есть еще одна необходимая зависимость, а именно функция кодирования b58
b58encode. Это просто специфичная для биткойна кодировка байтов, в которой используется база 58 символов алфавита, которые очень однозначны. Например, в нем не используются «O» и «0», потому что их очень легко испортить на бумаге. Итак, нам нужно взять наш биткойн-адрес (который составляет 25 байтов в необработанном виде), преобразовать его в базу 58 и распечатать символы. Необработанные 25 байтов нашего адреса содержат 1 байт для версии («основная сеть» биткойна — это b'\x00', в то время как «тестовая сеть» Биткойна использует b'\x6f'), затем 20 байтов из хэша. дайджест и, наконец, 4 байта для контрольной суммы, чтобы мы могли выдать ошибку с вероятностью 1–1/2** 4 = 93,75% в случае, если пользователь неправильно ввел свой биткойн-адрес в какое-либо текстовое поле. Итак, вот кодировка b58:# 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Теперь напечатаем наш биткойн-адрес:
# 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Круто, теперь мы можем проверить какой-нибудь веб-сайт проводника блоков, чтобы убедиться, что этот адрес никогда ранее не выполнялся: www.blockchain.com/btc-testnet/address/mnNcaVkC35ezZSgvn8fhXEa9QTHSUtPfzQ. К концу этого руководства этого не произойдет, но на момент написания я действительно увидел, что этот адрес «чистый», поэтому никто не сгенерировал и не использовал секретный ключ в тестовой сети, как мы это делали выше. Это имеет смысл, потому что должен был быть какой-то другой «Андрей» с плохим чувством юмора, который также возился с биткойном. Но мы также можем проверить некоторые суперсекретные секретные ключи, которые, как мы ожидаем, использовались людьми в прошлом. Например, мы можем проверить адрес, принадлежащий наименьшему действующему секретному ключу, равному 1, где открытый ключ — это именно точка генератора :). Вот как мы это получаем:
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'В самом деле, как мы видим в обозревателе блокчейнов, на момент написания этот адрес совершал транзакции 1812 раз и имеет баланс 0,00 BTC. Это имеет смысл, потому что, если бы у него был какой-либо баланс (в наивном случае, по модулю некоторых тонкостей с языком сценариев, который мы будем использовать), то любой мог бы просто потратить его, потому что он знает секретный ключ (1) и может его использовать для цифровой подписи транзакций, которые их тратят. Мы скоро увидим, как это работает.
Часть 1: Итоги на данный момент
Мы можем сгенерировать криптосущность, состоящую из секретного ключа (случайного целого числа), известного только нам, и производного открытого ключа, прыгая по эллиптической кривой, используя скалярное умножение точки генерации на эллиптической кривой биткойна. Затем мы также получили связанный биткойн-адрес, которым мы можем поделиться с другими, чтобы запросить деньги, и для этого были введены две хэш-функции (SHA256 и RIPEMD160). Вот три важных количества, обобщенных и снова распечатанных:
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Продолжение следует
- Part 2: Obtaining seed funds + intro to Bitcoin under the hood
- Part 3: Crafting our transaction
