Серхио Лернер, разработчик в RSK Labs и один из соавторов технологии оптимизации майнинга ASICboost, ставшей причиной недавнего скандала в сообществе Биткоина, написал статью о том, какие явные и скрытые связи могут существовать между внедрением Segregated Witness и использованием ASICboost в майнинге.
Segwit и AsicBoost достаточно сильно связаны между собой - как если говорить о связях, которые лежат на поверхности, так и о скрытых взаимодействиях. Помимо этого, нельзя упускать из внимания недавно предложенный метод, позволяющий устранить проблемы во взаимодействии скрытого AsicBoost и некоторыми улучшениями в протоколе, содержащимися в SegWit. Такое предложение делает технологию скрытого AsicBoost более дорогостоящей, но вполне реальной.
AsicBoost - это по сути две составляющие:
Технология, используемая в работе чипов ASIC в алгоритме PoW, которая теоретически позволяет майнить быстрее, чем стандартная технология, путем фиксации последних 64 байтjd первого приложения SHA256 (окончания заголовка блока данных) и изменения среднего состояния (начала заголовка блока данных), а не наоборот. Это требует постоянного и повторного использования окончания заголовка.
Набор методов для изменения первых 64 байтов в начале заголовка блока, оставляя при этом конец заголовка неизменным.
Если говорить о методах в пункте 2, то есть два способа изменить начало (первые 64 байта) заголовка блока:
Изменить поле nVersion заголовка блока.
Изменить 28 байтов Merkle root в заголовке блока.
Первый вариант метода называется «открытым» AsicBoost, потому что все пользователи могут проверять поле nVersion в блоке. В свернутом поле nVersion будет активировано несколько случайных битов. Поскольку семантика битов поля nVersion изменяется в соответствии с BIP9, в настоящее время случайные изменения в этом поле интерпретируются узлами Bitcoin Core как поддержка несуществующих предложений софтфорка.
Второй метод получил название «скрытого» AsicBoost, так как очень сложно выявить блок, в котором древо Merkle было «свернуто». Даже если обнаружение единичного скрытого AsicBoost может быть затруднительно, то понять, что какой-то майнер работает этому методу практически невозможно, опираясь на статистические данные.
Скрытый AsicBoost требует от майнера найти «коллизии» последних 4 байтов корневого поля Merkle, так как они хранятся в конце заголовка блока, а не в начале. Это стадия предварительной обработки, которая должна быть пройдена каждый раз, когда создается новый блок. Есть несколько алгоритмических методов для поиска коллизий, какой из них использовать - зависит от количества запрашиваемых коллизий и размеров коллизионных групп. Требования к группам зависят от того, как было создано ядро с SHA256.
Чтобы найти коллизии, где есть несколько способов создания новых корневых вариантов Merkle, нужно:
Изменить состав транзакции T.
Изменить порядок транзакций.
Изменение порядка транзакций требует повторного вычисления ID транзакции (двойная операция SHA256) и обновления древа Merkle от раздела T до корня. На каждом уровне должен выполняться двойной SHA256 из 128-байтного блока данных. Если предположить, что все сжатие SHA256 и расширение сообщения занимает одно и тоже время Q, то в общей сложности на каждом уровне выполнение операций будет занимать 6Q. Если в блоке 2048 транзакций, то тогда речь идет об 11 уровнях и 66Q, выполняющихся при каждом изменении транзакции. Если окончание транзакции T изменено (вместо заголовка), то для пересчета идентификатора транзакций может потребоваться только 4Q. В общей сложности необходимо потратить около 70Q.
Если блок содержит только coinbase транзакцию (обычно такие блоки называют «пустыми»), то можно вычислить корень древа Merkle лишь за 4Q, потому что в этом случае ID транзакции coinbase и есть корень Merkle. Таким образом, использование технологии скрытого AsicBoost путем изменения coinbase стимулирует создание блоков с меньшим количеством транзакций. Найти коллизию для пустого блока можно в 17 раз быстрее, чем для блока с 2048 транзакциями, используя первый описанный метод.
Изменение порядка транзакций, описанное во втором методе, может быть произведено несколькими способами. Это позволяют сделать два подметода:
Самый простой способ – создать набор левых субдеревьев и набор правых субдеревьев в памяти, а затем соединять их всеми возможными способами. Это можно сделать только в том случае, если правый и левый набор независимы друг от друга. Если для каждого субдерева имеется n вариантов, то можно построить n^2 корней. Количество транзакций в каждом субдереве практически не имеет значения, потому что каждое из них может быть создано путем изменения содержимого одной транзакции. Такой метод требует 6Q для создания каждого корневого варианта, поэтому он лучше, чем изменение coinbase, даже если блок «пустой». Этот метод лучше всего подходит для CPU и GPU.
Другой способ заключается в вычислении вариантов левого и правого субдеревьев моментально, путем замены узлов на разных уровнях. Этот метод требует гораздо меньшего количества внутренней памяти и больше подходит для FPGA или ASIC.
Количество операций SHA256, необходимых для поиска коллизий, устанавливает фиксированную задержку для запуска майнинга AsicBoost. Во время периода обнаружения коллизий, системе необходимо майнить блоки, используя традиционный метод перебора nonce-rolling, до тех пор, пока коллизии не будут готовы. При этом неважно, пусты ли блоки в это время.
Если майнинговое оборудование поддерживает только AsicBoost, а не стандартный майнинг, тогда майнер не может генерировать какой-либо блок в течение этого периода. Поэтому существует достаточно высокая необходимость в снижении затрат на обнаружение коллизий в том случае, если чип поддерживает только AsicBoost (а не два режима). Если чип является двухрежимным, может быть допущена задержка до 1 минуты.
Стоит отметить, что даже изменение порядка транзакций самым быстрым скрытым методом все равно медленнее, чем осуществление этой же задачи открытым методом, так как он вообще не требует поиска коллизий.
Когда Segwit (BIP141) позволяет блокчейну принимать блоки, которые содержат по крайней мере одну транзакцию Segwit, он принимает блок только в том случае, если у него есть древо wtxid с корнем Merkle, которое хранится в транзакции coinbase. Это древо содержит транзакции wtxids. Wtxid в свою очередь содержит и данные транзакции, а также witness данные. Поэтому, если порядок транзакций изменяется (но не обязательства wtxid), то это несоответствие делает блок недействительным.
Вот почему Segwit усложняет процесс изменения порядка транзакций, хотя этот метод и является наиболее эффективным для скрытой AsicBoost и наиболее подходящим для FPGA. Это вынуждает майнеров, использующих технологию скрытого AsicBoost, разрабатывать только те блоки, которые не содержат Segwit транзакций.
Источник
19.04.2017, 16:00
