Перевод Актуальное состояние Proof-of-Work алгоритма: RandomX

Тема в разделе "Статьи", создана пользователем TheFuzzStone, 6 июл 2019.

  1. TheFuzzStone

    Команда форума Администратор Модератор

    Регистрация:
    18 авг 2017
    Сообщения:
    181
    Симпатии:
    42
    1.png

    RandomX - это новый ASIC и GPU-устойчивый PoW-алгоритм, изначально разработанный для Monero, но потенциально может быть применим в любом блокчейне, который использует PoW и стремится к переходу на CPU-майнинг. Компания Arweave заключила контракт на проверку этого нового алгоритма в течение двухнедельных занятий и предоставила руководство по выбору альтернативных параметров. Но что делает его необычным и почему вас это должно волновать?

    Стандартный Proof-of-Work


    В классических PoW алгоритмах (таких как hashcash, используемых в Bitcoin) ядро обычно представляет собой криптографическую хеш-функцию, единственной переменной которой являются входные в функцию данные. Для достижения заданной "твердости" требуется определенное количество нулевых битов в качестве префикса вывода хеша. Каждый добавленный нулевой бит удваивает сложность добычи. Однако данный тип алгоритма очень легко поддается ускорению с помощью ASIC и GPU, так как на всех входах с ограниченными требованиями к памяти выполняется фиксированный набор операций. Это нежелательно.

    Почему нас волнует устойчивость к ASIC?

    Майнинг в идеале является сильно децентрализованной задачей без единого субъекта, который бы контролировал значительную часть хеширующих мощностей. Блокчейн подвержен атакам 51%, при которых большинство злоумышленников может перехитрить глобальное состояние сети, например, допуская двойные траты. Если ASIC может быть построен таким образом, чтобы значительно повысить эффективность майнинга, по сравнению с CPU общего назначения, то экономические факторы будут препятствовать майнингу на базе CPU. Результат этого можно увидеть в сети Bitcoin, где производители ASIC построили крупные майнинговые фермы, и горстка предприятий контролирует высокий процент хешрейта.

    За последние несколько лет производители ASIC продемонстрировали огромные возможности для быстрого проектирования и изготовления ASIC. Таким образом, проект, который хочет быть устойчивым к ASIC (без перехода на Proof-of-Stake модель, которая имеет свой собственный набор компромиссов), должен попытаться воспользоваться преимуществами, присущими для CPU общего назначения над гипотетическими ASIC.

    Это желание привело к значительному количеству исследований в области противодействия ASIC. RandomX представляет собой конкретную реализацию самых современных ASIC-устойчивых идей по отношению к криптовалютам.

    Как работает RandomX

    В основе RandomX лежит концепция рандомизированного выполнения. Проще говоря, мы хотим выполнить серию случайных команд, чтобы воспользоваться универсальной гибкостью CPU и динамическим выполнением кода. Разработчики RandomX подробно задокументировали свои расчеты и представили спецификацию с более подробным объяснением, однако при небольшом упрощении алгоритм делает следующее:
    • Шаг 1
    Структура данных под названием Cache создается с помощью argon2d, с помощью входного ключа K. Argon2d изначально была разработана как функция хеширования паролей, требующая памяти. Компьютеры, как правило, имеют большие пулы быстрой памяти, но память стоит дорого для ASIC. Требование большого объема памяти является одной из наиболее распространенных мер защиты от специализированного оборудования. Argon2 использует различные методы для обеспечения большого (конфигурируемого) объема памяти и неэффективности любых компромиссных атак по времени/памяти. Подробнее о них можно прочитать в спецификации argon2.
    • Шаг 2
    Набор данных (структура памяти, доступная только для чтения) расширяется из Cache. Базы данных представляют собой большой сегмент памяти, содержащий данные, которые виртуальная машина будет читать. Существуют два значения, которые контролируют размер набора данных (RANDOMX_DATASET_BASE_SIZE и RANDOMX_DATASET_EXTRA_SIZE). Вместе они устанавливают верхнюю границу общей памяти, необходимой алгоритму. Дополнительный размер используется для того, чтобы немного подтолкнуть память за пределы двух границ, что затрудняет жизнь производителям ASIC. Реальная генерация наборов данных выполняется путем загрузки данных из Cache, создания набора экземпляров SuperscalarHash, а затем вызова этих экземпляров для получения окончательного результата. SuperscalarHash предназначен для энергопотребления в ожидании данных от DRAM. Это мешает ASIC, который пытается вычислить наборы данных динамически из Cache.
    • Шаг 3
    Инициализируется Scratchpad-память (чтение/запись) путем хеширования входных данных с помощью blake2 и использования полученных результатов для выдачи AesGenerator. Этот генератор использует инструкции AES-NI для заполнения Scratchpad-памяти. Генерация исходной Scratchpad использует преобразования AES. Этот алгоритм уже аппаратно ускорен на современных процессорах, поэтому ASIC не получит никаких преимуществ от его реализации. Сама Scratchpad представляет собой (относительно) большую структуру данных чтения/записи, разработанную специально для размещения в кэшах, доступных в CPU.
    • Шаг 4
    Теперь перейдем к ядру алгоритма: рандомизированным программам, работающим на виртуальной машине. Виртуальная машина выполняется путем построения программы, использующей случайные байты, созданные с помощью другого генератора. Архитектура виртуальной машины RandomX тщательно разработана для того, чтобы любая последовательность 8-байтовых слов была правильной командой. Эта инструкция предназначена для:
    • Выполнения операций с плавающей точкой двойной точности
    • Использования 128-битной векторной математики
    • Использования всех четырех режимов округления с плавающей запятой IEEE 754
    • Чтения и записи в Scratchpad-память, которая, как уже говорилось выше, полностью помещается в кэш процессора и поэтому работает очень быстро
    • Получения выгоды от прогнозирования ветвей с помощью низковероятных инструкций ветвей
    • Выполнения инструкций с использованием суперскалярных и неупорядоченных возможностей CPU
    Каждое из этих свойств является особым преимуществом CPU общего назначения и требует дополнительного пространства кристаллов для реализации в ASIC, снижая его преимущества.

    Полученное в результате этого состояние виртуальной машины после выполнения программы хешируется и используется для генерации новой программы. Количество циклов, выполняемых таким образом, настраивается, но по умолчанию установлено восемь. Такое поведение было выбрано во избежание ситуаций, когда ASIC-майнер может выполнять только часть возможных операций и запускать только "простые" программы на виртуальной машине. Поскольку последующая программа не может быть определена до тех пор, пока не будет полностью выполнена текущая, майнер не может предсказать, будет ли "легкой" вся цепочка, поэтому реализовать частичный набор команд становится невыгодным.
    • Шаг 5
    Наконец, файлы Scratchpad и Register File (регистры виртуальной машины) хешируются с помощью AesHash, за которыми следует последний blake2 хеш. Этот шаг не предлагает никакого значительного сопротивления ASIC, кроме использования команд AES, но он включен, чтобы показать окончательное хеширование до 64-байтового значения.

    Что мы нашли

    В ходе двухнедельного исследования мы обнаружили три проблемы (две проблемы низкой степени, одна информационная).


    Одиночные AES круги, используемые в AesGenerator


    Шифрование AES, описанное в спецификации RandomX, относится к одному кругу AES, что недостаточно для полного смешивания входных данных. Безопасность RandomX не зависит от шифрования AES. Вместо этого AES используется как основанное на CPU быстрое преобразование, обеспечивающее диффузию на выходе. Однако диффузия битов через выходные данные зависит от количества циклов AES.

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

    После раскрытия этого факта команда разработчиков RandomX разработала новую функцию AesGenerator4R, которая выполняет четыре цикла. Эта функциональность была добавлена в RandomX с момента пул реквеста 46. Четыре раунда как часть процесса создания программы решают проблемы, описанные в этой реализации.

    В коде RandomX отсутствует возможность тестовой валидации семантики виртуальной машины. Trail of Bits выделила половину времени (одну неделю) на оценку общих защитных свойств реализации алгоритма. Несмотря на то, что эти усилия выявили несколько ошибок в качестве кода, их было недостаточно для проверки отсутствия серьезных семантических ошибок в реализации виртуальной машины.

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

    Рассмотрим случай, когда сторонняя реализация спецификации RandomX становится популярной в блокчейне с использованием RandomX для PoW-алгоритма. Блокчейн разделится, если между вариантами реализации майнеров есть даже небольшая семантическая разница.

    Настраиваемые параметры являются чувствительными

    RandomX содержит 47 настраиваемых параметров, включая флаги для распараллеливания, расхода памяти и итераций исходного KDF, объёма памяти, набора данных, размера трех уровней кэша для виртуального CPU, размера итераций программ на виртуальной машине, доступа/латентности к кэшу. Параметры по умолчанию были выбраны для максимизации преимуществ CPU для данного алгоритма. Однако угроза атак 51% заставляет альтернативные блокчейны, заинтересованные в использовании RandomX, делать различный выбор для этих параметров. Эти решения должны приниматься без четкого понимания того, какие из них могут поставить под угрозу преимущества алгоритма. Такая чувствительность может препятствовать принятию решения третьей стороной.


    Глубина оценки


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

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

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

    Этот принцип реализации безопасности программного обеспечения хорошо отражен в старом докладе Дэйва Эйтеля: Стратегия хакера. А именно, качество уязвимостей, которые могут быть обнаружены исследователем, тесно связано с затраченным временем. Один час улавливает крайне поверхностные проблемы, одна неделя - значительно больше, а через месяц вы можете обнаружить уязвимости, которые никто другой не сможет обнаружить.

    Более подробно об этом говорится в публикации "Нулевые дни, тысячи ночей" - авторитетном справочнике по исследованиям уязвимостей, основанном на десятках интервью с экспертами в данной области:
    Например, ручная проверка корректности RandomX VM (что является самой серьезной обнаруженной нами проблемой) займет несколько недель в одиночку. Весьма вероятно, что по окончании всех четырех проверок не будет никакой гарантии того, что реализация виртуальной машины не будет содержать семантических ошибок.

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

    Текущее состояние проекта

    Наша двухнедельная аудиторская проверка была первой из многочисленных запланированных командой RandomX. В течение следующих нескольких недель проект подвергнется еще трем небольшим аудиторским проверкам, результаты которых должны быть опубликованы позднее в этом месяце. Как только эти аудиты будут опубликованы, и авторы RandomX разрешат любые дополнительные проблемы, Arweave и Monero намерены использовать этот алгоритм в своих соответствующих продуктах в рамках запланированного обновления протокола.

    Источник: State of the Art Proof-of-Work: RandomX

    Перевод:
    TheFuzzStone (@TheFuzzStone)
    Редактирование:
    Agent LvM (@LvMi4)
    Коррекция:
    Kukima (@Kukima)
     
  • О нас

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