Пользователь
0,0
рейтинг
18 мая 2015 в 11:14

Разработка → Майним Bitcoin с помощью бумаги и ручки перевод

В один прекрасный момент мне захотелось прикинуть, насколько быстро можно майнить биткойны вручную. Оказалось, что для майнинга используется хеширование SHA-256, а оно достаточно простое и может быть вычислено даже без компьютера. Само собой, процесс очень небыстрый и совершенно непрактичный. Но, пройдя все шаги на бумажке, можно хорошо разобраться в деталях работы алгоритма.


Один криптографический раунд

Майнинг


Ключевая часть всей системы безопасности биткойна — майнинг. Основная идея заключается в том, что майнеры группируют биткойн-транзакции в один блок, который уже подвергают хэшированию неисчислимое число для нахождения очень редкого значения хэша, подпадающего под специальные условия. Когда такое значение находится, блок считается смайненным и попадает в цепочку блоков. Само по себе хэширование не несёт никакой полезной цели кроме увеличения сложности поиска правильного блока. Таким образом, это одна из гарантий того, что никто в одиночку с любым существующим набором ресурсов не сможет взять под контроль всю систему. Подробнее про майнинг можно почитать в моей прошлой статье.

Криптографическая функция хэширования на вход получает блок с данными, а выдаёт небольшой, но непредсказуемый, выход. Она спроектирована так, что не существует быстрого способа получить нужный выход, и вы должны продолжать перебор пока не найдёте подходящее значение. Биткойн использует SHA-256 в качестве такой функции. Причём для усиления стойкости SHA-256 применяется к блоку дважды и называется уже двойным SHA-256.

В биткойне критерием валидности хэша является достаточное число нулей в его начале. [1] Найти такой хэш так же сложно, как, к примеру, найти номер машины или телефона, заканчивающийся на несколько нулей. Но, конечно, для хэша это экспоненциально сложнее. На текущий момент, правильный хэш должен содержать примерно 17 стартовых нулей, чему удовлетворяет только 1 из 1.4x1020. Если провести аналогию, то найти такое значение сложнее, чем обнаружить конкретную частичку среди всего песка на Земле.

На схеме ниже показан типичный блок в цепочке и его хэш. Желтым выделены байты, которые и участвуют в процессе хэширования. В данном примере хэш валиден и имеет достаточное число нулей в своём начале. Однако это нечастый случай, и обычно майнеру приходится перебирать значение поля nonce или других доступных для изменения данных.


Структура биткойн-блока

SHA-256


Алгоритм работает с данными, разбитыми на куски по 512 бит (64 байт), криптографически их смешивает и выдаёт 256-битный (32 байта) хэш. SHA-256 состоит из относительно простого раунда, повторяющегося 64 раза. Снизу, как раз, и показан такой раунд, принимающий на вход 8 4-байтовых слов — от A до H.


Один раунд SHA-256 для восьми входных слов A-H. Схема нарисована kockmeyer, CC BY-SA 3.0.

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

Функция большинства (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 — своя константа для каждого раунда. [2]

На схеме сверху заметно, что только A и E меняются за один криптографический раунд. Остальные слова не меняются, но сдвигаются на выходе — старое A превращается в выходное B, старое B — в новое C, и так далее. Хотя отдельный раунд алгоритма не сильно изменяет данные, но после 64 раундов, входная информация будет полностью зашифрованной. [3]

Майним вручную


На видео я показываю как можно пройти все описанные шаги с помощью ручки и бумаги. Я выполнил первый раунд хэширования для майнинга блока. Заняло это у меня 16 минут, 45 секунд.


Немного поясню что происходит: я записал слова от A до H в шестнадцатеричной форме, и под каждым сделал перевод в двоичный вид. Результат выполнения блока Ma находится под словом C, а значения A после сдвигов и сам выход Σ0 располагаются над строкой с A. Функция выбора появляется под G, и, наконец, соответствующие сдвинутые версии E и значение после блока Σ1 идут над строкой с E. В нижнем правом углу произвёл сложение, результат которого участвует в вычислении и нового A, и нового E (первые три красных блока суммирования). Справа сверху я рассчитал новое значение A, а посерёдке располагается уже расчет нового значения E. Все эти шаги обсуждались выше и легко могут быть отслежены на схеме.

Кроме того раунда, что показан в видео, я провёл еще один — последний 64-ый хэшируюший раунд для конкретного биткойн-блока. На фотографии значение хэша выделено желтым. Количество нулей подтверждает, что это валидный биткойн-хэш. Заметьте, что нули располагаются в конце хэша, а не в начале, как я писал ранее. Причина заключается в том, что биткойн, просто-напросто, переворачивает байты полученные SHA-256. [4]


Последний раунд SHA-256, в результате которого виден успешно смайненный биткойн-блок

Что всё это значит для проектирования «железных» майнеров?


Каждый шаг в SHA-256 очень просто выглядит в цифровой логике — простые битовые операции и 32-битные суммирования (если вы когда-либо изучали схемотехнику, то, скорее всего, уже представили себе как это может выглядеть в железе). Поэтому ASIC-микросхемы реализуют SHA-256 очень эффективно, размещая параллельно сотни блоков исполнения SHA-256 раундов. Фотография ниже показывает микросхему для майнинга, которая может вычислять 2-3 миллиарда хэшей в секунду. На Zeptobars можно поглядеть больше фото.


Снимок кремниевого кристалла ASIC-микросхемы Bitfury, которая может майнить биткойны со скоростью в 2-3 гигахэшей в секунду. Картинка с Zeptobars. (CC BY 3.0)

В противоположность биткойну, Litecoin, Dogecoin и другие похожие альтернативные -coin системы используют алгоритм хэширования scrypt, в котором изначально заложена сложность реализации в железе. Этот алгоритм во время выполнения хранит в памяти 1024 разных значений хэша, а уже на выходе комбинирует их для получения конечного результата. Поэтому требуется куда больше памяти и схематики для вычисления scrypt-хэшей по сравнению с SHA-256-хэшами. Влияние изменения алгоритма хэширования наглядно видно при сравнении соответствующего аппаратного обеспечения для майнинга — версии под scrypt (Litecoin и прочие) в тысячи раз медленнее, чем версии под SHA-256 (биткойн).

Заключение


SHA-256 неожиданно оказался настолько простым, что может быть вычислен даже вручную (алгоритм на эллиптических кривых, который используется для подписи биткойн-транзакции, был бы куда более мучительным, так как содержит кучу перемножений 32-байтных чисел). Расчет одного раунда SHA-256 занял у меня 16 минут, 45 секунд. С такой производительностью хэширование всего биткойн-блока (128 раундов [3]) займёт 1,49 суток, то есть получаем скорость хэширования в 0,67 хэшей в день (на самом деле, конечно же, с практикой процесс бы ускорился). Для сравнения, текущее поколение биткойн-майнеров производит несколько терахэшей в секунду, что примерно в квинтиллион раз быстрее меня. Думаю, очевидно, что ручной майнинг биткойнов не очень практичен. [5]

Читатель с reddit'a спросил о моих затратах энергии. Так как я не прилагаю каких-то серьезных физических усилий, то можно предположить что скорость метаболизма будет 1500 килокалорий в день, тогда получаем, что ручное хэширование требует почти 10 мегаджоулей за хэш. Типичное потребление энергии для железного майнера — 1000 магехэшей за джоуль. Таким образом, я менее энергоэффективен чем специализированная железка в 10^16 раз (10 квадриллионов). Другой вопрос в стоимости энергии. Дешевым источником питания являются пончики по 23 цента за 200 килокалорий. Электроэнергия у меня стоит 15 центов за киловатт-час, что дешевле пончиков в 6.7 раз. В итоге, стоимость энергии в пересчете на хэш для меня, как человека-майнера, в 67 квадриллионов раз выше. Да-а-а, понятно, что я не ухвачу удачу за хвост ручным майнингом биткойнов, и это еще не учитывая стоимость бумаги и ручек!

Примечания и ссылки



1. На самом деле, важно не число лидирующих нулей в хэше, а то, что он должен быть меньше какого-то конкретного значения, которое зависит от текущего уровня сложности системы.

2. Довольно занятно то, откуда пошли эти константы для SHA-256. Так как АНБ разрабатывало этот алгоритм и выбирало константы, то откуда нам знать, что они не подобрали специальные значения, чтобы быстрее ломать хэши? Дабы пресечь подобные спекуляции, начальные инициализирующие значения хэша взяты как квадратные корни из восьми первых простых чисел (первые 32 бита дробной части). А Kt получены из кубических корней первых 64 простых чисел. Как видите, константы сгенерированы с помощью простых формул, поэтому можно доверять тому, что АНБ не придумало ничего хитрого (по крайней мере, в отношении констант).

3. К моему сожалению, SHA-256 работает с блоками из 512 бит, а заголовок биткойн-блока больше. Поэтому необходим второй проход из 64 раундов хэширования. Кроме того, в биткойне используется двойной SHA-256. Таким образом, хэширование одного блока требует 192 раунда. Тем не менее, мы можем сократить это число, потому что процесс майнинга заключается в повторном хэшировании одного и того же блока, с небольшими изменениями поля «nonce» во второй половине блока. И тут возникает оптимизация за счет того, что мы можем использовать результат вычисления первых 512 бит блока повторно. В итоге, нам требуется только 128 раундов хэширования.

4. Само собой, я не настолько невероятно удачлив, что нашёл сразу валидный хэш. Я начал хэширование блока, уже ранее смайнененного. Конкретно того, который уже упоминался в статье — #286819.

5. Еще одна проблема с ручным майнингом заключается в том, что новые блоки майнятся примерно каждые 10 минут, поэтому даже если я успешно намайню блок, то он будет безнадежно устаревшим (сиротой, в терминах биткойна).
Перевод: Ken Shirriff
@mark_ablov
карма
135,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (30)

  • +31
    Теперь можно майнить на кластере китайцев.
    • +14
      Или нанять Анатолия Вассермайнера
      • 0
        И майнить на нем параллельно
  • +24
    Автору этого поста надо познакомиться с автором поста про QR коды habrahabr.ru/post/127197
  • –59
    На гиктаймс.
    • +38
      Криптографию на гиктаймс? Не думаю.
    • +32
      Теперь на хабре есть свои вахтеры. Правильной дорогой идем.
  • 0
    Во время умственной работы мозг также интенсивно потребляет энергию, так что 1500 ккал тут не обойдёшься.

    С другой стороны, медицинский раствор глюкозы, возможно, выйдет дешевле пончиков. Но и другие питательные вещества (белки, жиры, клетчатка) тоже нужны для длительной работы.
  • +21
    Аппаратный ускоритель
    image
    • +5
      А Вы в курсе что эту штуку ещё и можно турбировать? Я пр Счёты… мылом натирали стерженьки, костяшки летели от толчка до конца — сильно ускорялись расчёты.
  • 0
    " я записал слова от A до H в шестнадцатеричной форме" — полагаю, всё-таки имелись в виду буквы, а не слова.

    В оригинале («I've written each block A through H in hex») вообще не использует ни «слова», ни «буквы», так что это вольность перевода.
    • +1
      Ну в переводе много вольностей, да. Но не в этом случае.
      Я, действительно, не стал использовать слово «блок» в четвёртом смысле (биткойн-блок, алгоритмический блок, блок данных).
      Но в русской терминологии эти блоки A..H, которыми оперирует криптографический алгоритм, называют именно словами, блоки это другое, размер блока для SHA-256 — 512бит, но размер слова — 32 бита.
      За примером ходить далеко не надо, откройте вики по SHA-2.
      «дополнения разбивается на блоки, каждый блок — на 16 слов.», «На каждой итерации 2 слова преобразуются, функцию преобразования задают остальные слова».

      Термина «буквы» никогда не встречал в таком контексте.
      • 0
        Ага! Спасибо за разъяснение. Беру свой коммент обратно.
        • 0
          «Беру свой коммент обратно».

          Звучит как попытка забрать перчатку после вызова на дуэль =)
  • 0
    А на Ардуино майнер уже делал кто-нибудь?
    • 0
      Делали конечно, ради шутки, такой же как и ручной майнинг.
      Производительность никакая. Развитие майнинга было примерно такое: cpu -> gpu -> fpga -> asic. Слабенькие 1-2, даже 4-8, ядерные микроконтроллеры сюда никак не вписываются.
    • 0
      Даже на NES делали
      retrominer.com
  • +3
    Скажу только за себя — мне очень интересно. Сколько материалов не прочитал, но тут все классно рассказано,
    Спасибо большое, вот теперь я действительно понял как работает биткоин
  • +1
    А рендерить 3D сцены вручную кто-нибудь уже пробовал?
    • +11
      Ух, много лет уж как. Говорят, Леонардо да Винчи неплохо рендерил… :)
    • +3
      Да, давно уже:
      image
      • +15
        А тут, значит, поделили на ноль:

        • +1
          Не, тут явно текстуры побились.
          • +1
            Судя по характерным дырам, не текстуры, а нормали в геометрии поехали. Видно грани неправильных треугольников в нижних углах.
    • 0
      Художники эпохи Возрождения в этом неплохо преуспели.
  • +2
    … и майнил биткойны в аду
  • 0
    Немного не уловил, а где хешировался список транзакций? Он в этом блоке огромный.
    • 0
      В статье же написано:
      «На схеме ниже показан типичный блок в цепочке и его хэш. Желтым выделены байты, которые и участвуют в процессе хэширования».
      Очевидно, что сами транзакции не участвуют в хэшировании.
      • 0
        А, понял.
        MerkleRoot — 256-bit hash based on all of the transactions in the block — это и есть хеш всех транзакций. А в майнинге уже хешируется по нему.
        • 0
          Не совсем так, Merkle Root куда более сложная сущность, чем просто хэш всех транзакций. Если вкратце, то это корень бинарного дерева double-SHA256 хэшей каждой транзакции, где уровень выше в дереве хэширует конкатенации двух своих ветвей (тоже с хэшами).

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.