bitcoin-2
Момент, о котором забыл в прошлый раз. Помните, там были такие транзакции, с входами и выходами, да? И я ещё говорил, что вот, нету денег как таковых, как суммы, которую можно потратить, есть только история транзакций? Вот, всё так и есть, только не сказал, что делать, если нужно перевести кому-то часть суммы. Ну, т.е. собрал блок, заработал 50 коинов, а теперь хочешь перевести кому-то 10 из этих 50-и. Ответ такой: напрямую это сделать невозможно, вход всегда используется полностью, можно перевести только все 50. Другой вопрос, что можно 10 перевести кому-то, а остальные 40 опять себе. На тот же адрес или на другой.
Движемся дальше: срывание покровов с криптографической магии и заложенных идей. По замыслу этот раздел промежуточный между размахиванием руками в первом и безудержным программированием где-то в будущем.
Чтобы читать дальше нужно знать, что такое хеш-функции и криптография с открытым ключом. Алгоритмы и детали не нужны, но нужно понимание, что это и зачем это; названия алгоритмов ниже приводятся только для конкретности.
Как оно работает? [приблизительно]
В качестве хешей используется две функции:
hash256(x) = SHA-256(SHA-256(x)) -- дважды применённое SHA-256. На выходе 32 байта.
hash160(x) = RIPEMD-160(SHA-256(x)) -- сначала SHA-256, а потом RIPEMD-160. На выходе 20 байтов.
Криптография с открытым ключом -- только подпись, применяется ECDSA. Очень мало чего про него знаю, да это и не важно в данном случае. Ну, традиционно: некий открытый ключ, некий закрытый ключ, генерация подписи закрытым, проверка открытым.
Транзакции
Транзакции имеют каноническое бинарное представление, в таком виде они передаются по сети и хранятся на диске, подробности сейчас не важны. Вычисленный от этого представления hash256 это transaction-id -- trId для краткости.
Именно trId и есть "номер транзакции", упомянутый в предыдущем посте. Итак, уточняя сказанное ранее:
- транзакции имеют уникальный номер, но он не задан явно, а вычисляется как hash256 от бинарного представления
- входы транзакций содержат trId транзакции-источника денег, индекс её выхода и первую половину скрипта
- выходы -- переводимую сумму и адрес вторую половину скрипта
Скрипты
Биткоиновский скрипт это очень простой стековый язык, на котором пишут маленькие программки. Идея следующая:
- сначала выполняется первая половина скрипта, из входа. При этом разрешены только команды вида "положить в стек".
- после этого выполняется вторая половина скрипта, из того выхода той транзакции, на которую ссылается вход
- если в итоге получилось 1, значит правомерность использования доказали, если нет, то нет.
Вариант №1: а знаешь ли ты приватный ключ?
Первая половина скрипта (предъявляемая, при попытке использовать выход) должна выглядеть так:
PUSH <подпись>
А вторая (опубликованная в транзакции, как часть выхода):
PUSH <публичный ключ>
OP_CHECKSIG
Операция OP_CHECKSIG проверяет, что второй аргумент в стеке (положенный первой половиной скрипта) это действительно подпись (подпись чего -- чуть позже), сделанная с помощью приватного ключа, соответствующего первому аргументу в стеке.
Очень просто.
Вариант №2: а знаешь ли ты публичный и приватный ключи?
Первая половина скрипта должна выглядеть так:
PUSH <подпись>
PUSH <публичный ключ>
Вторая:
OP_DUP
OP_HASH160
PUSH <хеш>
OP_EQUALVERIFY
OP_CHECKSIG
Как это работает ("стек после", очевидно, будет "стеком до" для следующей команды):
операциястек после (растёт вправо)описание
PUSH <подпись> <подпись>
PUSH <публичный ключ> <подпись>, <публичный ключ> к этому моменту выполнена первая половина скрипта
OP_DUP <подпись>, <публичный ключ>, <публичный ключ> DUP дублирует верхний элемент стека
OP_HASH160 <подпись>, <публичный ключ>, hash160(<публичный ключ>) вынимает из стека верхний элемент, вычисляет от него hash160, кладёт результат в стек
PUSH <хеш> <подпись>, <публичный ключ>, hash160(<публичный ключ>), <хеш> кладёт в стек ожидаемый хеш
OP_EQUALVERIFY <подпись>, <публичный ключ> вынимает из стека два верхних элемента и проверяет, что они равны друг другу. Если не так -- конец программы, fail.
OP_CHECKSIG 1 а эта команда уже описана выше
То есть:
- создателю транзакции не известен публичный ключ получателя. Он знает только хеш от него
- получатель предъявляет свой публичный ключ, а так же подпись, подтверждающую, что он владеет обоими ключами
- при проверке хеш предъявленного ключа сверяется с известным и проверяется корректность подписи
Язык позволяет больше, вот например такой красивый вариант, или можно отдать деньги первому попросившему, без всяких проверок (очевидно, PUSH 1). Но, повторюсь, во всех опубликованных на данный момент транзакциях (в основной сети) используются только эти два.
Итого осталось два вопроса: что всё-таки подписываем и откуда тогда берётся адрес?
С адресом всё просто, это определённым образом преобразованный в читаемый вид hash160(публичный ключ). Во втором виде скриптов присутствует сам хеш, а в первом -- ключ, так что получить адрес для этих двух случаев несложно (в общем случае это, конечно, невозможно). Как именно он преобразуется в строчку -- не важные программистские детали. С подписью чуть сложнее.
Подпись
К подписи предъявляются два требования:
- убедить всех, что подписывающий владеет приватным ключом, т.е. что выход был направлен именно ему -- для этой цели можно подписывать что угодно, хоть фиксированную строчку "1234567890".
- убедить всех, что подписывающий имел ввиду именно эту транзакцию, что враги не поменяли в ней суммы и адресатов, или вообще не переклеили эту подпись откуда-то из другой транзакции
В итоге, если убрать совсем кровавые детали, алгоритм выглядит так:
- перед началом у нас есть:
- текущая транзакция, которую мы проверяем
- конкретный вход этой транзакции, который мы сейчас проверяем на обоснованность
- транзакция, на которую он ссылается, её конкретный выход, а главное -- скрипт S из этого выхода. По идее именно этот скрипт выполняется в процессе проверки
- взять текущую транзакцию
- выкинуть из всех её входов все скрипты
- на место скрипта в текущий вход вставить скрипт S
- всё это сериализовать в стандартный вид
- последний байт предъявляемой подписи это "тип хеша". Во-первых, этот байт нужно от подписи отделить, во-вторых, нужно растянуть его на 4 и добавить в конец к получившимся данным
- теперь это пропускается через hash256
- и наконец можно проверять подпись
Есть ещё два типа хешей, и один флаг к ним всем, в итоге можно подписывать все меньше и меньше данных; это нужно для контрактов, о которых будет следующий пост. Всё это безумие описано здесь.
Блоки
Я говорил о сложной задаче, которую нужно решить при формировании блока. И, конечно, немножко заработать на этом. Подробности.
Блок состоит из заголовка и транзакций. В заголовке:
- версия
- хеш предыдущего блока
- хитрым образом вычисляемый хеш от всех своих транзакций
- текущее время с точностью до секунды
- текущая сложность
- волшебное число, названное nonce
while (hash256(заголовок) >= текущая_сложность) nounce++;
или, немножко грубее, нужно подобрать такой nonce, чтобы хеш от заголовка начинался с нужного количества нулей. Текущее значение, которое не должен превышать хеш можно посмотреть здесь, сейчас это число:
000000000000094A860000000000000000000000000000000000000000000000
В бинарном виде это 13*4 = 52 нуля в начале, соответственно каждая попытка угадает с вероятностью 1/252. Сколько нужно попыток, чтобы набрать вероятность 1/2? Вместо того, чтобы тупо складывать вероятности и получать 251 (чего делать, конечно, нельзя), прикинем по науке:
Вероятность не угадать после n попыток должна быть равна 1/2:
логарифм от обеих сторон:
логарифм числа, настолько близкого к 1, хорошо оценивается:
итого:
Примерно 0.7 * 252 попыток. При реализации "в лоб", мой не очень крутой компьютер считает 10 миллионов хешей за 13 секунд на одном ядре. Пусть будет миллион в секунду, два, если на двух ядрах. Пусть крутой компьютер считает в 50 раз быстрее, итого 100 миллионов в секунду. 0.7 * 252 это примерно 2.8 * 1015, делим на 100 миллионов, получаем 2.8 * 107 секунд. Это 324 дня непрерывной работы. Давайте трезво оценивать наши шансы. Поскольку nonce это последний элемент структуры, кажется, вычисление первого SHA можно сильно ускорить, вычислив его от неполной структуры, и потом завершая с разными nonce-ами. Но даже если мы сведём время его вычисления к 0, это сократит работу всего в два раза, там же ещё второй SHA поверх.
Пусть возможна гораздо более оптимальная реализация. Но и тут предел виден: частоты процессоров выше 4ГГц пока не поднимаются, вычислить хеш меньше чем за 400 ассемблерных инструкций, кажется, слегка оптимистично, SHA не настолько просто устроен, так что не больше 10 миллионов в секунду на ядро. Пусть 10 ядер, вот и есть те же 100 миллионов на компьютер.
Вот табличка со статистикой по разному железу, сравнивающая скорость майнинга. Если коротко, то рулят графические карты, обычные процессоры и близко не валяются. Правда, самое крутое, что там было -- конфигурация с тремя AMD Radeon HD 6990 -- даёт 2094 миллиона хешей в секунду. Всего в 20 раз быстрее, чем рассмотренный выше условный компьютер. Для процессоров лучший результат -- 115 миллионов на 4-процессорной машине с 48-ю ядрами.
В общем, на одном компьютере с теми самыми видеокартами, 16 дней, не меньше. Непрерывной работы. Для вероятности 1/2.
Ещё есть новый и старый калькуляторы, позволяющие оценить ожидаемую прибыльность. Сложность там измеряется в неких условных единицах, стандартных для биткоинов, это производная от описанной выше сложности, текущую можно узнать здесь. Ну и аккуратнее с числами, новый просит количество миллионов хешей в секунду, старый -- тысяч в секунду. Новый оптимистично считает, что каждая попытка приносит 1/вероятность от биткоина и выдаёт "заработанную" сумму в день-неделю-месяц, старый считает, сколько дней нужно работать на 50% и на 95%. Оценки очень похожи на мои.
А тут показывают динамику изменения сложности и скорости работы сети. Картинка хороша, впечатляет. Самое удивительное здесь, на мой взгляд, то, что при таких вероятностях кто-то этим ещё сознательно занимается! Неужели у них хотя бы окупается электричество? Или они так рассчитывают на дефляцию? Или это ботнеты и чужого электричества не жалко? В общем, не совсем понимаю. Правда, видна тенденция на снижения, видимо, оценив шансы, народ начал отваливаться.
Upd: в комментах объяснили, что теория вероятностей сосёт всё не так грустно и на самом деле есть способы.