Это вторая часть статьи про биткоин, в которой разбираются детали реализации. Общие принципы работы описаны в первой части.

Ключи

Биткоин использует криптографию на эллиптических кривых, а именно кривую secp256k1:

Параметры кривой
Уравнение: $y^2 = x^3 + 7 \bmod \ p$
$p$ - простое
$G$ - точка генерации
$n$ - порядок точки $G$

Закрытый ключ $k$ - случайное целое число меньше порядка точки генерации на кривой (чуть меньше $2^{256}$)
Открытый ключ - точка на эллиптической кривой. Вычисляется из закрытого ключа $P = k * G$, где $G$ - точка генерации кривой
В основе безопасности лежит сложная задача дискретного логарифмирования на эллиптической кривой: по известным точкам $P$ и $G$ найти число $k$ такое, что $P= k * G$

Сокращённая запись публичных ключей

Публичный ключ является точкой на эллиптической кривой - $(x, y)$
Поскольку координату $y$ можно вычислить по $x$ из уравнения кривой (решив квадратное уравнение), то часто для экономии места публичные ключи представляют в сжатом виде - только координатой $x$. Чтобы отличать различные представления ключей в начало добавляется префикс:

Адреса

Вместо длинных публичных ключей при переводах используются более компактные и удобные для человека адреса, которые выглядят как строка из цифр и символов латинского алфавита в кодировке Base58.

Base58

Base58 - алгоритм кодирования бинарных данных в виде буквенно-цифрового текста на основе латинского алфавита. Используются прописные и заглавные буквы и цифры, но без некоторых символов, которые часто путаются: 0 (ноль) и O (заглавная буква О), l (маленькая L), I (большая i)
Алфавит Base58 в биткоин: 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz

Base58Check

Base58Check - это улучшенный вариант Base58, который используется для генерации биткоин-адресов. К Base58 добавлена контрольная сумма для обнаружения ошибок и версия для поддержки различных типов адресов.

Расчёт контрольной сумма данных (payload) Base58Check :

1. В начало данных добавляется версия: $version + payload$
2. Вычисляется хеш данных - двойной SHA-256:
   $hash = SHA–256(SHA–256(version + payload))$
3. Из хеша берётся 4 первых байта ($checksum$) и добавляется в конец данных
4. Результат: $version + payload + checksum$

Биткоин адреса бывают различных версий в зависимости от того, из чего они генерируются.

Примеры версий:

Алгоритм генерации адреса из публичного ключа

1. Вычисляется двойной хеш от публичного ключа: $SHA–256(REPIMD–160(pubkey))$
2. Добавляется версия
3. Полученное значение кодируется в Base58Check

Пример:

Публичный ключ:
04
0CF0764C3518C46A300280948F094DE80114E115775EF607AAAF9AE09CC68E70 7B75431FB1E8004BF42A5F904534E16394DA3BB72780B8EFB9D8529A337C88B2

Применили SHA-256:
86A1158D5AC5DCA27DF13A099D25B921BF2045DF291396AD4C67ED50CD4096B9

Применили RIPEMD-160:
D1A3DA516E60B7EE8D8F8748447283ADA8BB7D67

Добавили версию (00 в начало):
00D1A3DA516E60B7EE8D8F8748447283ADA8BB7D67

Применили два раза SHA-256:
031857852824BC52708122B0817F2BE87839C8062B16DF95935DAA91EDB42B08

Взяли первые 4 байта:
03185785

Добавили эти 4 байта ((контрольная сумма) в конец хеша с версией:
00D1A3DA516E60B7EE8D8F8748447283ADA8BB7D6703185785

Закодировали Base58:
1L7UWnXsXsZf6ymj7x6ZK7W5gNaYFEFSgk

∎

Кошельки

Кошельки – это программы для хранения ключей. Делятся на два вида:

1. Простые – набор случайно сгенерированных независимых ключей
2. Иерархические, или кошельки “с зерном” - в них приватные ключи выстроены в виде дерева и происходят от общего предка - случайного числа

Иерархические кошельки

В иерархических кошельках все ключи генерируются из одного начального случайного числа. Первым делом из числа генерируется мастер-ключ. Затем из мастер-ключа несколько новых ключей, из них, в свою очередь, ещё новые ключи и так далее. В результате получается дерево ключей.

Интересной особенностью является возможность генерировать ветки публичных ключей без соответствующих закрытых ключей. Это позволяет использовать адреса в слабо защищённых средах, не опасаясь потери биткоинов.

Пример:

∎

Определение:

Введём несколько обозначений:
$hash$ - 512 битное хеш-значение
$hash_{left}$ - левые 256 бит
$hash_{right}$ - правые 256 бит
$k$ - закрытые ключи
$p$ - открытые ключи

Генерация мастер-ключа

Мастер-ключ генерируется из случайного числа $seed$

1. $hash = HMAC–SHA–512(seed)$
2. $k = hash_{left}$ - приватный ключ
3. $code = hash_{right}$ - код цепочки. Код цепочки используется в дальнейшем для генерации дочерних ключей, чтобы они зависели не только от закрытого ключа

Генерация дочерних ключей

Генерация дочернего приватного и публичного ключа из родительского приватного ключа
$$PrivGen(k_{par}, code_{par}, i) = (k_{child}, p_{child}, code_{child})$$

1. $hash = HMAC–SHA–512(k_{par} * G, code_{par}, i)$
2. $k_{child} = (hash_{left} + k_{par}) \pmod{n}$
3. $p_{child} = k_{child} * G$
4. $code_{child} = hash_{right}$

Генерация дочернего публичного ключа из родительского публичного ключа $$PubGen(p_{par}, code_{par}, i) = (p_{child}, code_{child})$$

1. $hash = HMAC–SHA–512(p_{par}, code_{par}, i)$
2. $p_{child} = hash_{left} * G + p_{par}$
3. $code_{child} = hash_{right}$

Теорема:

∎

Доказательство:

∎

Именно это свойство позволяет генерировать цепочки дочерних публичных ключей без дочерних приватных ключей, используя только родительский публичный ключ.

Транзакции

Структура транзакции:

• Входы транзакции являются ссылками на выходы предыдущих транзакций. Сценарий траты выхода транзакции (кто и при каких условиях может потратить выход) описывается на специальном языке скриптов
• В транзакции нет отдельного поля для комиссий. Комиссия считается как разница между суммой входов и суммой выходов
• Время блокировки (locktime) обычно не используется и устанавливается 0. Это означает, что транзакцию можно включать в блок сразу без задержки

Входы

Структура входа транзакции:

Coinbase-транзакция - это особая транзакция, в которой майнер получает награду за найденный блок. Включается в блок первой. Входы coinbase-транзакции не имеют ссылки на выход предыдущей транзакции и открывающего скрипта

Структура входа coinbase-транзакции:

Выходы

Структура выхода транзакции:

Скрипты

Вход транзакции содержит закрывающий скрипт, в вход - открывающий. Если эти скрипты, выполненные вместе, выдают значение “Истина”, то проверка пройдена и трата биткоинов разрешается.

Язык скриптов

Биткоин использует стековый скриптовый Forth-подобный язык. Язык не тьюринг-полный, например, в нём нет циклов. Это сделано в целях безопасности и противодействия спам-атакам на сеть. Например, нельзя создать скрипт, который выполняет бесконечный цикл, чтобы тратить ресурсы узлов.

Скрипт выполняется по одному элементу слева направо. Данные помещаются на стек. Операторы помещают или извлекают параметры из стека, производят действия над ними, и помещают результат выполнения обратно на стек. Для выполнения скрипта не требуется никаких внешних данных – вся информация, необходимая для выполнения скрипта, содержится в самом скрипте.

Пример:

Закрывающий скрипт:

2 OP_ADD 42 OP_EQUAL

Открывающий скрипт:

40

Соединим открывающий и закрывающий скрипт:

40 2 OP_ADD 42 OP_EQUAL

Выполнение скрипта:

1. Поместить 40 на стек
2. Поместить 2 на стек
3. OP_ADD - взять два числа из стека, сложить, результат поместить на стек: 40 + 2 = 42
4. Поместить 42 на стек
5. OP_EQUAL - взять два значения из стека проверить, что они равны: 42 = 42, результат “Истина”

Результат выполнения скрипта “Истина” следовательно выход может быть потрачен.

∎

Виды транзакций

Самый распространённый вид транзакции- это “Алиса переводит Бобу” и соответствующий закрывающий скрипт “Потратить выход может тот, кто предоставит подпись на секретном ключе Боба”. Но на этом возможности биткоин не исчерпываются, система скриптов позволяет реализовать различные сценарии проведения операций.

Распространённые виды транзакций:

Pay-to-Public-Key
Самый простой вариант: перевод по публичному ключу. Доказательством траты является подпись, сгенерированная на соответствующем закрытом ключе.
Скрипты:
pkscript: <public_key> OP_CHECKSIG
sigscript: <signature>

Pay-to-Public-Key-Hash (P2PKH)
Аналогичен Pay-to-Public-Key, только вместо публичного ключа используется его хеш для уменьшения размеров транзакций. Наиболее частый вариант на данный момент.

Скрипты:
pkscript: OP_DUP OP_HASH160 <public_key_hash> OP_EQUAL OP_CHECKSIG
sigscript: <signature> <public_key>

Ещё одно достоинство P2PKH в том, что публичный ключ публикуется в блокчейне в sigscript, то есть только когда выход потрачен. До тех пор в блокчейне хранится только хеш ключа - это дополнительная защита публичных ключей от взлома.

Pay To Multisig
Требование наличия нескольких подписей для траты выхода. Из N публичных ключей, перечисленных в скрипте, по меньшей мере М должны предоставить подписи (M-N сценарий). Может быть использован, если для траты необходимо согласие нескольких участников. Пример: чтобы потратить биткоины требуется согласие одновременно главного бухгалтера и исполнительного директора: каждый из них может потратить биткоины только при наличии подписи второго.

Скрипты (2-3 сценарий):
pkscript: 2 <public_key_A> <public_key_B> <public_key_C> 3 OP_CHECKMULTISIG
sigscript: OP_0 <public_key_A> <public_key_C>

В качестве sigscript подойдёт любой скрипт, в котором будут указаны любые два ключа из A,B,C. Например, OP_0 <public_key_B> <public_key_C> также подходит.

Вывод данных (OP_RETURN)
Используется для хранения данных в блокчейне. Этот вариант означает, что средства с выхода гарантировано нельзя потратить. Как правило, выход имеет нулевую сумму, иначе биткоины будут потеряны навсегда. Примеры использования: подтверждение авторства, цифровой нотариат. В сообществе неоднозначное отношения к OP_RETURN: с одной стороны он демонстрирует, что возможности блокчейна выходят за рамки проведения платежей. С другой стороны, данные увеличивают общий размер блокчейна, хотя не участвуют в переводах биткоинов. Был достигнут компромисс: данные хранить можно, но не более 80 байт.

Скрипты:
pkscript: OP_RETURN <data>
sigscript: Выход невозможно потратить

Pay-to-Script-Hash (P2SH)
Оплаты по произвольным правилам (скрипту). Вместо текста скрипта для экономии места используется хеш скрипта. Позволяет реализовывать произвольные сценарии оплаты.

Скрипты:
pkscript: OP_HASH160 <20-байтный хеш закрывающего скрипта> OP_EQUAL
sigscript: <data> <закрывающий скрипт>

Есть возможность представлять хеш сценария в виде биткоин-адреса (P2SH-адреса) - это определено в BIP13. P2SH-адрес - это 20-ти байтовый хеш сценария в кодировке Base58Check, аналогично тому, как биткоин-адрес - это 20-байтовый хеш открытого ключа в кодировке Base58Check. P2SH-адреса начинаются с “3”. Кошельки распознают этот формат адреса, что скрывает все сложности для плательщика, для него оплата выглядит как перевод на обычный адрес.

Блок

Структура блока:

Структура заголовка блока:

Расчёт хеша блока

Каждый блок содержит хеш предыдущего блока. Цепочка блоков образует блокчейн. Хеш блока рассчитывается как двойной SHA–256 заголовка блока.

Пример:

Расчёт хеша блока с номером 123456 на python:

import hashlib
from binascii import unhexlify, hexlify
headerHex = (
 "01000000" +  # version
 "9500c43a25c624520b5100adf82cb9f9da72fd2447a496bc600b000000000000" + # previousblockhash
 "6cd862370395dedf1da2841ccda0fc489e3039de5f1ccddef0e834991a65600e" + # merkleroot
 "a6c8cb4d" + # time
 "b3936a1a" + # bits
 "e3143991") # nonce
headerBinary = unhexlify(headerHex)
hash = hashlib.sha256(hashlib.sha256(headerBinary).digest()).digest()
print(hexlify(hash[::-1]).decode("utf-8")) 
# 0000000000002917ed80650c6174aac8dfc46f5fe36480aaef682ff6cd83c3ca

∎

Дерево Меркла

Дерево меркла (бинарное дерево хешей) – бинарное дерево, в узлах которого хранятся хеши. Используется для эффективной проверки целостности больших наборов данных. Листьями являются хеши от данных, а каждая вершина – это хеш от “суммы” (обычно используется конкатенация) потомков.

Пример:

Блоки данных: $A, B, C, D$
Хеш-функция: hash
Листья:
$H_A = hash(A)$
$H_B = hash(B)$
$H_C = hash(C)$
$H_D = hash(D)$
Вершины:
$H_{AB} = hash(H_A + H_B)$
$H_{CD} = hash(H_C + H_D)$

Корень:
$H_{ABCD} = hash(H_{AB} +H_{CD} )$

∎

В биткоин в качестве хеш функции используется двойная SHA-256. В заголовке блока хранится корень дерева Меркла merkleroot, построенного из всех транзакций, входящих в блок. Это позволяет вычислять хеш блока единым способом, вне зависимости от количества транзакций в блоке.

Аутентификационный путь

С помощью дерева Меркла можно эффективно проверить вхождение транзакции в блок. Последовательность вершин, соединяющая корень дерева с проверяемой транзакцией, называется аутентификационный путь. Для доказательства принадлежности транзакции достаточно привести её аутентификационный путь. Это свойство широко используется кошельками, которые являются лёгкими узлами (SPV-узлами), и не скачивают весь блокчейн на устройство пользователя. SPV-узлы (в отличии от полных узлов) не хранят транзакции и полные блоки, только заголовки блоков. Для того, чтобы убедиться, что транзакция включена в блок, SPV-узлы используют аутентификационный путь транзакции, который они запрашивают у полного узла.

Пример:

В дереве из предыдущего примера необходимо проверит вхождение блока С
Для этого нужно проверить, что $root == hash(H_{AB} + hash(hash(C) + H_D))$
Можно убедиться, что $H_C$ принадлежит дереву, имея хеши $H_D$ и $H_{AB}$ (аутентификационный путь), вычислив дополнительно $H_{CD}$ и $H_{ABCD}$. При этом не нужно пересчитывать хеши всех блоков данных

∎

В общем случае для подтверждения принадлежности транзакции блоку нужно выполнить $O(log(N))$ операций хеширования.

Целевая сложность

В поле bits содержится значение сложности в формате “коэффициент и показатель степени”. Первый байт означают показатель степени, а следующие три байта – коэффициент.

Целевая сложность рассчитывается по формуле:
$$target = coefficient * 2^{(8 * (exp – 3))}$$

Пример:

∎

Nonce

Цель майнера – найти такое значение nonce, при котором хеш заголовка блока меньше целевой сложности. Майнеры перебирают значения nonce, пока кто-нибудь не найдёт подходящее значение.

Extra nonce

Поле nonce имеет размер всего 4 байта. По мере увеличения целевой сложности, майнеры всё чаще перебирали все 4 миллиарда возможных значений nonce и не находили нужное значение. Одни майнеры в этом случае увеличивают время создания блока и повторяют перебор. Другие используют в качестве “дополнительного nonce” поле данных coinbase-транзакции. Так как coinbase-транзакция используется для расчёта корная дерева Меркла, а корень входит в заголовок блока, её изменение также изменяет хеш заголовка блока.

Развитие и улучшения биткоин

В биткоин есть механизм внесения улучшений и обсуждения BIP (Bitcoin Improvement Proposal). Цель BIP – стандартизировать процедуру внесения изменений в систему биткоин. Предложения хранятся в виде текстовых файлов в публичном репозитории, их содержание и история доступны каждому пользователю.

Типы BIP:
Информационные. Разъяснения и уточнения по различным аспектам работы биткоин

Изменения протокола. Изменения протокола, влияющие на механизм консенсуса. Добавляют новые возможности в протокол или исправляют ошибки. При этом блоки, созданные до изменения, по-прежнему остаются корректными. Такие изменения называются софтфорками. Например, так был добавлен вид транзакции P2SH

Общие изменения. Изменения, не затрагивающий протокол биткоина. Например, улучшения в работе кошельков

BIP ни для кого не является обязательным, поэтому он работает только если действительно представляет консенсус сообщества. В биткоин каждый узел работает независимо, а значит, BIP будет использоваться, только если по нему есть консенсус участников.
Если у участников разные взгляды на изменения, это может привести к разделению протокола на два, так что блоки в каждой ветке не считаются корректными в другой ветке – такое разделение называется хардфорком.

Пример:

Хардфорк биткоина - Bitcoin cash

Изначально размер блока был 1 мегабайт. При маленьком количестве транзакций это не имело значения, но при увеличении количества транзакций, они не все помещались в новый блок, что увеличивало время прохождения переводов.

Обсуждалось два пути решения:

1. Вообще снять ограничение на размер блока
2. Немного увеличить размер блока и изменить способ хранение данных

В итоге сообщество пришло к решению изменить способ хранения данных и увеличить размер блока до 2 мегабайт.

Часть сообщества не согласилась и решила увеличить размер до 8 мегабайт без изменения структуры хранения данных. Произошёл хардфорк биткоина, который назвали Bitcoin cash. У обеих криптовалют общая начальная история, блок 478558 стал последним общим блоком. Следующий блок с номером 478559 был сформирован дважды в разных форматах.

∎