Майним Bitcoin с помощью бумаги и ручки
В один прекрасный момент мне захотелось прикинуть, насколько быстро можно майнить биткойны вручную. Оказалось, что для майнинга используется хеширование SHA-256, а оно достаточно простое и может быть вычислено даже без компьютера. Само собой, процесс очень небыстрый и совершенно непрактичный. Но, пройдя все шаги на бумажке, можно хорошо разобраться в деталях работы алгоритма.
Один криптографический раунд
Майнинг
Ключевая часть всей системы безопасности биткойна — майнинг. Основная идея заключается в том, что майнеры группируют биткойн-транзакции в один блок, который уже подвергают хэшированию неисчислимое число для нахождения очень редкого значения хэша, подпадающего под специальные условия. Когда такое значение находится, блок считается смайненным и попадает в цепочку блоков. Само по себе хэширование не несёт никакой полезной цели кроме увеличения сложности поиска правильного блока. Таким образом, это одна из гарантий того, что никто в одиночку с любым существующим набором ресурсов не сможет взять под контроль всю систему. Подробнее про майнинг можно почитать в моей прошлой статье.
Криптографическая функция хэширования на вход получает блок с данными, а выдаёт небольшой, но непредсказуемый, выход. Она спроектирована так, что не существует быстрого способа получить нужный выход, и вы должны продолжать перебор пока не найдёте подходящее значение. Биткойн использует SHA-256 в качестве такой функции. Причём для усиления стойкости SHA-256 применяется к блоку дважды и называется уже двойным SHA-256.
В биткойне критерием валидности хэша является достаточное число нулей в его начале. [1] Найти такой хэш так же сложно, как, к примеру, найти номер машины или телефона, заканчивающийся на несколько нулей. Но, конечно, для хэша это экспоненциально сложнее. На текущий момент, правильный хэш должен содержать примерно 17 стартовых нулей, чему удовлетворяет только 1 из 1.4×10 20 . Если провести аналогию, то найти такое значение сложнее, чем обнаружить конкретную частичку среди всего песка на Земле.
На схеме ниже показан типичный блок в цепочке и его хэш. Желтым выделены байты, которые и участвуют в процессе хэширования. В данном примере хэш валиден и имеет достаточное число нулей в своём начале. Однако это нечастый случай, и обычно майнеру приходится перебирать значение поля 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 квадриллионов раз выше. Да-а-а, понятно, что я не ухвачу удачу за хвост ручным майнингом биткойнов, и это еще не учитывая стоимость бумаги и ручек!
Источник
Как я blakecoin майнер делал
Не знаю кому как, а меня прошедший 2017 год шокировал стремительным взлетом биткоина. Сейчас, конечно, ажиотаж уже ушел, а в 17-м году про криптовалюты говорили и писали все кому не лень.
Я видел, что люди пытаются зарабатывать на криптовалютах. Кто как умеет. Кто-то на все сбережения скупал видеокарты и начинал самостоятельно майнить в гараже. Кто-то вкладывался в облачный майнинг. Кто-то пытается организовать свой пул. Кто-то запустил в производство шоколадные биткоины, а кто-то выпускает минеральную воду:
Я тоже стал изучать, что же такое эти самые биткоины. Когда-то я даже начал свое собственное иследование алгоритма SHA256 и написал статью здесь на хабре «Можно ли вычислять биткоины быстрее, проще или легче?». Мои исследования алгоритмов хеширования до сих пор продолжаются и еще и близко не завершены… Может быть когда нибудь напишу про это отдельную статью. А сейчас пока вот это..
Я попробовал запустить bitcoin майнер в FPGA. Я понимал, что время уже ушло, но хотелось все же прикоснуться к технологии. Уже в конце прошлого года я вдруг почему-то вспомнил, что у меня совершенно без дела лежит плата Terasic DE10-Standard с ПЛИС Intel Cyclone V 5CSXFC6D6F31C6 — это тот чип, который со встроенным процессором ARM. Я подумал, что было бы интересно запустить какой нибудь альткоин майнер в этой плате. А что? Инвестировать в оборудование мне уже не надо, оно и так есть. Главное, чтобы плата зарабатывала больше, чем потребляет энергии.
Поиск подходящего альткоина был весьма прост. Я искал готовые проекты для FPGA, которые я смогу адаптировать под свою плату. Таковых оказалось не очень много. На самом деле как я понимаю во всем мире есть всего несколько человек, которые делали FPGA проекты и главное публиковали их в открытом доступе, например, на github.
Таким образом, я взял проект github.com/kramble/FPGA-Blakecoin-Miner и адаптировал его под имеющуюся у меня плату Марсоход3, а так же адаптировал этот проект для DE10-Standard.
Собственно о том, как я адаптировал проект для платы Марсоход3 написано здесь. Для Cyclone V в принципе все то же самое — только ревизия проекта квартуса blake_cv, мои исходники вот.
К моему сожалению в имеющийся у меня Cyclone V помещается только три хэш функции blake.
Чуть-чуть не хватает емкости ПЛИС до четырех хэшеров. Я запускаю проект на частоте 120МГц и за один такт рабочей частоты вычисляется один хэш blake. Значит производительность моего проекта 120*3=360MH/sec. Не очень много честно говоря, однако, как я уже сказал, плата у меня уже была, и возвращаеть ее стоимость мне не нужно… Тут еще Quartus говорит, что Fmax=150MHz. Можно попытаться поднять частоту, но боюсь придется ставить кулер, будет гудеть — ну не на столько мне нужны эти крипты, чтоб еще гул в комнате слушать.
Общая задумка проекта такая: плата имеет микросхему у которой есть и ПЛИС и Dual-ARM:
Когда плата стартует, то из U-BOOT первым делом загружается ПЛИС, затем стартует Linux и в нем программа майнинга cgminer. Я сперва думал, что я смогу устроить виртуальный канал связи между ARM и FPGA, и это на самом деле возможно, но так не получилось. Дело в том, что программа майнера cgminer работает с аппаратными майнерами через USB и использует библиотеку libusb. То есть мне проще подключить ПЛИС к Linux системе через преобразователь USB-COM на FTDI, чем городить городушку соединяя ПЛИС на шину ARMа. Я таким уже как-то занимался и это было не очень просто.
Сейчас мой «майнер» выглядит вот так (на Cyclone V поставил радиатор на термопасте, а то сильно греется):
Сказать по правде основные проблемы у меня как раз возникли не с FPGA проектом, а с cgminer.
1) Какой cgminer брать за основу своей разработки? И связанный с этим вопрос «Куда подключаться, чтобы начать майнить?». А какая связь между этими вопросами? Казалось бы, где тут проблема — бери самый свежий cgminer, какой найдешь. Но позвольте: на github есть 98 форков программы cgminer. Все они чем-то отличаются, какой есть хороший, а какой плохой, какой есть вообще хотя бы рабочий? Вот вам и опенсоурс. Каждый автор чего-то там себе добавлял и исправлял, или ломал… или делал свою монету. Разобраться не просто. Нашел для себя сайт, где на одной странице есть ссылка и на github проект и на github проект для FPGA. То есть эти два проекта видимо как-то могут и должны пересекаться.
2) Поскольку я взял за основу FPGA проект от автора kramble, то на самом деле, конечно, логично было бы взять его патчи, которые он приложил к своему проекту. Но и тут не без проблем. У него есть патчи к программе cgminer-3.1.1 и cgminer-3.4.3. Я решил, что лучше брать ту, что новее 3.4.3, но только потерял с ней время. Похоже автор начал адаптировать для этой версии, но что-то там не довел до конца и эта версия совсем сырая. Пришлось брать 3.1.1 а это кажется вообще старючая версия.
3) Авторы изменяющие программу cgminer в своих форках для своих альткоинов не следят за правильностью комментариев и именованием функций в коде. Зачастую в коде тут и там встречается слово bitcoin, а сам этот форк cgminer-а уже кажется не может считать для биткоина, а может только в альткоин.
4) Тесты. ГДЕ ТЕСТЫ? Я чего-то не понимаю, как можно делать сложный продукт без тестов? Я их не нашел.
Сказать по правде даже начинать что-то делать было не просто. Представьте себе, что нужно запустить некоторый проект в FPGA, но не очень понятно, что он должен делать, как получать данные, какие данные и в каком виде нужно выдавать результат. К этому FPGA проекту должна прилагаться некоторая программа, которую не известно точно где взять, но она должна обнаружить плату майнера, что-то туда посылать (неизвестно что) и что-то из нее получать. В каком формате, какими блоками, как часто — ничего не известно.
На самом деле, изучая патчи cgminer от kramble я примерно представляю себе как оно должно работать.
В файле usbutils.c прописаны устройства, которые могут рассматриваться как аппаратные внешние майнеры на шине USB:
Я в эту структуру добавил описатель своего USB-to-COM преобразователя FTDI-2232H. Теперь, если cgminer обнаружит устройство с VendorId/DeviceId = 0x0403:0x6010, то он попробует работать с этим устройством, как с платой Icarus, хоть она таковой и не является.
Дальше смотрим файл driver-icarus.c и тут есть функция icarus_detect_one:
Смысл такой. Программа передает плате заведомо известное задание на поиск хэша, причем в задании сказано с какого нонсе начинать вычисление и это нонсе немного меньше настоящего GOLDEN nonce. Таким образом, плата начнет считать с указанного места и буквально сразу в считанные доли секунды наткнется на GOLDEN nonce и вернет его. Программа тут же получит этот результат, сравнит его с правильным ответом и сразу становится понятно — это действительно тот HW майнер с которым можно работать или нет.
И вот тут была ужасная проблема — в проекте есть патчи на языке C, есть тестовая программа на питоне и тестбенч для FPGA.
В патчах на C тестовые данные выглядят вот так:
1) патч для cgminer-3.1.1
1) патч для cgminer-3.4.3
И что тут правильно, а что нет? Исходные данные одинаковые, а golden nonce объявлен разным. Парадокс… (заранее скажу, что в патче для cgminer-3.4.3 ошибка — нонсе 0x000187a2 не верный, а сколько времени я на это потратил..)
В проекте есть тестовая программа на питоне, которая читает текстовый файл, извлекает из него данные и передает в плату через последовательный порт… Там тестовые данные вот такие:
0000007057711b0d70d8682bd9eace78d4d1b42f82da7d934fac0db4001124d600000000cfb48fb35e8c6798b32e0f08f1dc3b6819faf768e1b23cc4226b944113334cc45255cc1f1c085340967d6c0e000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
0000007057711b0d70d8682bd9eace78d4d1b42f82da7d934fac0db4001124d6000000008fa40da64f312f0fa4ad43e2075558faf4e6d910020709bb1f79d0fe94e0416f5255cc521c085340df6b6e01000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
0000007095696e4529ae6568e4b2a0057a18e82ccf8d370bf87e358900f8ab5000000000253c6078c7245036a36c8e25fb2c1f99c938aeb8fac0be157c3b2fe34da2fa0952587a471c00fa391d2e5b02000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
000000704445e0446fcf2a84c47ce7305722c76507ba74796eaf39fe0007d44d00000000cac961f63513134a82713b172f45c9b5e5eea25d63e27851fac443081f453de1525886fe1c01741184a5c70e000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
00000070a3ac7627ca52f2b9d9a5607ac8212674e50eb8c6fb1219c80061ccd500000000ed5222b4f77e0d1b434e1e1c70608bc5d8cd9d363a59cbeb890f6cd433a6bd8d5258a0141c00b4e770777200000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
000000706c90b789e84044d5be8b2fac01fafe3933ca3735269671e90043f8d900000000d74578c643ab8e267ab58bf117d61bb71a04960a10af9a649c0060cdb0caaca35258b3f81c00b4e7b1b94201000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
00000070171d2644781cccf873ce3b6e54967afda244c47fc963bb240141b4ad00000000d56c4fbdc326e8f672834c8dbca53a087147fe0996d0c3a908a860e3db0589665258da3d1c016a2a14603a0a000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
00000070d03c78cb0bb0b41a5a2c6ce75402e5be8a705a823928a5640011110400000000028fb80785a6310685f66a4e81e8f38800ea389df7f16cf2ffad16bb98e0c4855258dda01c016a2ae026d404000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
0000007091a7eef446c4cb686aff8908ab5539d03a9ab2e975b9fe5700ed4ca9000000000f83bb385440decc66c10c0657fcd05f94c0bc844ebc744bba25b5bc2a7a557b5258e27c1c016a2a6ce1900a000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
00000070856bd0a3fda5dac9ede45137e0c5648d82e64fbe72477f5300e96aec0000000026ca273dbbd919bdd13ba1fcac2106e1f63b70f1f5f5f068dd1da94491ed0aa45258e51b1c017a7644697709000000800000000000000000000000000000000000000000000000000000000000000000000000000000000080020000
Ну то есть совершенно другие! Потом я уже понял, что это не те даннае, что посылаются в плату, из этих только извлекаются данные, специальным образом конвертируются в задание и отсылаются в плату.
Но все равно, среди этих тестовых данных для программы на питоне НЕТ задания похожего на то, которое описано в программе на C.
Ну хорошо, тогда смотрю тестовую программу-тестбенч на verilog:
Здесь есть предполагаемый пакет данных, который плата должна принять. Но опять этот предполагаемый пакет данных никак не похож на пакет данных в программе на C или на данные для тестовой программы на питоне.
Вот это отсутствие общих тестовых данных для программы на питоне, C и Verilog очень сильно портит картину. Получается, что между компонентами как бы нет общих точек соприкосновения, общих тестов и это печально.
Вообще, в верилог проекте blakecoin майнера было скрыто еще одно форменное издевательство над моим организмом.
Если проводить симуляцию проекта с verilog тестбенчем, то в симуляторе с вот этими тестовыми данными 416’h000007ffffbd9207ffff001e11f35052d5544… замечательно находится и возвращается результат GOLDEN nonce.
Потом проект компилирую для реальной FPGA платы, эти же самые данные подаю из программы на питоне и… плата не находит GOLDEN nonce…
Оказывается, что тестовые данные в verilog тестбенче «немного плохие». Они для низкой сложности, когда в результирующем хэше всего 24 ведущих нуля, а не 32, как требуется.
В файле experimental/LX150-FourPiped/BLAKE_CORE_FOURPIPED.v есть вот такой код
В Verilog симуляторе проверяется не так, как будет будет работать в железе! То есть для реальной FPGA платы будем проверять на 32 бита ведущих нулей, а в симуляции будем проверять только 24 бита. Это просто прелестно. Хочется побить автора.
Я конечно, все это победил. По крайней мере, тестовая программа на питоне выдает бодрые сообщения:
Ладно, что в результате? Сколько намайнил? К сожалению нисколько.
Как только я был уже готов начать майнить, буквально в конце января сложность блейка сильно возросла:
Теперь я мог оставить на сутки плату и она хоть и находила решения, но их не принимал пул — все еще мало ведущих нулей.
Я пробовал переключиться на другую валюту — VCASH. С этой валютой пул хотя бы иногда выдавал мне бодрящие сообщения вроде вот этого:
Но все равно и VCASH пул ничего не начисляет. Печаль-беда.
Пользуясь случаем хотел бы спросить у знающих людей. Вот у меня есть видеокарта Nvidia 1060. Она выдает 1,25GHash/sec на блейкоине и за час два-три раза выдает nonce, который принимает пул (и начисляет копеечку). Я думал, что если моя FPGA плата считает 360MHash/sec, ну то есть примерно в 3 раза хуже, чем видеокарта, то я за два часа получу хотя бы один нонсе принятый пулом. Однако, этого не происходит. Даже за сутки нет ни одной копеечки… Где тут подвох для меня так и осталось загадка…
Сейчас я на досуге пытаюсь понять можно ли как-то оптимизировать имеющийся FPGA проект, скажем задействовать встроенную память или еще что-то. Может быть, если повезет, что-то и придумаю.
Источник
