В один момент мне захотелось узнать, насколько быстро можно добывать биткоины вручную. Оказалось, что для майнинга используют хэширование по алгоритму SHA-256, а оно достаточно простое и может быть вычислено даже без компьютера. Конечно же, процесс очень небыстрый и совершенно непрактичный. Но, пройдя все шаги на бумажке, можно хорошо разобраться в деталях работы алгоритма.
Майнинг
Ключевая часть всей системы безопасности биткоина - майнинг. Основная идея заключается в том, что майнеры группируют биткоин-транзакции в один блок, который уже подвергают хэшированию неисчислимое число для нахождения очень редкого значения хэша, подпадающего под специальные. когда такое значение находится, блок считается смайненным и попадает в блокчейн. Само по себе хэширование не несёт никакой полезной цели кроме увеличения сложности поиска правильного блока. Таким образом, это одна из гарантий того, что никто в одиночку с любым существующим набором ресурсов не сможет взять под контроль всю систему.
Криптографическая функция хэширования на вход получает блок с данными, а выдаёт небольшой, но непредсказуемый, выход. Она спроектирована так, что не существует быстрого способа получить нужный выход, и вы должны продолжать перебор пока не найдёте подходящее значение. Биткоин использует SHA-256 в качестве такой функции. Причём для усиления стойкости SHA-256 применяется к блоку дважды и называется уже двойным SHA-256.
В биткойне критерием валидности хэша является достаточное число нулей в его начале. Найти такой хэш так же сложно, как, к примеру, найти номер машины или телефона, заканчивающийся на несколько нулей. Но, конечно, для хэша это экспоненциально сложнее. На текущий момент, правильный хэш должен содержать примерно 17 стартовых нулей, чему удовлетворяет только 1 из 1.4x1020. Если провести аналогию, то найти такое значение сложнее, чем обнаружить конкретную частичку песка на Земле
На схеме ниже показан типичный блок в цепочке и его хэш. Желтым выделены байты, которые и участвуют в процессе хэширования. В данном примере хэш валиден и имеет достаточное число нулей в своём начале. Однако это нечастый случай, и обычно майнеру приходится перебирать значение поля nonce или других доступных для изменения данных.
SHA-256
Алгоритм работает с данными, разбитыми на куски по 512 бит (64 байт), криптографически их смешивает и выдаёт 256-битный (32 байта) хэш. SHA-256 состоит из относительно простого раунда, повторяющегося 64 раза. Снизу, как раз, и показан такой раунд, принимающий на вход 8 4-байтовых слов — от A до H.
Синие блоки нелинейно перемешивают биты для усложнения криптографического анализа. Причём для еще большей надежности используются разные функции перемешивания (если вы сможете найти математическую лазейку для быстрого генерирования валидных хэшей, то возьмёте под контроль весь процесс майнинга биткойнов).
Функция большинства (Ma блок) побитово работает со словами A, B и C. Для каждой битовой позиции она возвращает 0, если большинство входных битов в этой позиции — нули, иначе вернёт 1.
Блок Σ0 циклически сдвигает A на 2 бита, затем исходное слово A циклически сдвигается на 13 бит, и, аналогично, на 22 бита. Получившиеся три сдвинутые версии A побитово складываются по модулю 2 (обычный xor, (A ror 2) xor (A ror 13) xor (A ror 22)).
Ch реализует функцию выбора. На каждой битовой позиции проверяется бит из E, если он равен единице, то на выход идёт бит из F с этой позиции, иначе бит из G. Таким образом, биты из F и G перемешиваются, исходя из значения E.
Σ1 по структуре аналогичен Σ0, но работает со словом E, а соответствующие сдвиговые константы — 6, 11 и 25.
Красные блоки выполняют 32-битное сложение, формируя новые значения для выходных слов A и E. Значение Wt генерируется на основе входных данных (это происходит в том участке алгоритма, который получает и обрабатывает хэшируемые данные. Он вне нашего рассмотрения). Kt — своя константа для каждого раунда.
На схеме сверху заметно, что только A и E меняются за один криптографический раунд. Остальные слова не меняются, но сдвигаются на выходе — старое A превращается в выходное B, старое B — в новое C, и так далее. Хотя отдельный раунд алгоритма не сильно изменяет данные, но после 64 раундов, входная информация будет полностью зашифрованной.