MoneroKon D2 - Выступление Говарда Чу

23/06/2019

ASIC-устойчивое доказательство работы: миф или реальность?

Разработчик программного обеспечения, гений оптимизации, в послужной список которого входит рекорд по созданию самого быстрого мультипроцессорного стека TCP, самого быстрого в мире стека Appletalk, самого быстрого в мире LDAP сервера, работающих быстрее распознавания речи в режиме реального времени, быстрее демультиплексора/декодера радиолокационных данных реального времени и так далее.

Аннотация

Оригинальная «белая книга» CryptoNote заложила основу эгалитарного майнинга и определила алгоритм доказательства работы (PoW) CryptoNight для достижения этой цели. Шло время, технология развивалась, и производители специализированного аппаратного обеспечения в конечном счёте преодолели все технические препятствия CryptoNight. Споры относительно практической возможности и даже самой необходимости противодействия ASIC-майнингу не стихают, но Проект Monero по сей день твёрдо придерживается принципа эгалитарного майнинга. В этом выступлении поднимается вопрос неизбежности применения ASIC и того, какие подходы рассматриваются для нейтрализации преимуществ ASIC-майнеров с фиксированной функцией. Кроме того, в выступлении говорится о RandomX, новом PoW алгоритме, предложенном нами для Monero и разработанном с учётом уже полученных уроков.

Стенограмма:

Меня зовут Говард Чу, я являюсь основателем Symas Corporation. На прошлой неделе мы отметили своё двадцатилетие, а написанием программного обеспечения я занимаюсь уже что-то около сорока лет. Я работал с открытым (open source) программным обеспечением с момента его появления. Я работал над всеми утилитами, компиляторами, отладчиками, компоновщиками, текстовыми и другими программами GNU. В моём послужном списке есть не только то программное обеспечение, которое установлено буквально на каждом компьютере во всём мире, но даже то, которое работает на орбите, и оно никогда ещё не падало. Вот те несколько вещей, которые стоит упомянуть за это время. Я обожаю быстрое программное обеспечение. Безопасность — я также много занимался криптографией, вопросами безопасной аутентификации и различными системами безопасности.

Ok, так, перейдём к сути дела. Когда мы говорим о противодействии ASIC, что мы вообще имеем в виду, почему это важно, и как нам достичь успеха в решении этого вопроса?

Сейчас, чтобы создать некий фон, надо обозначить, с чего начался весь разговор — Monero, монета на базе протокола CryptoNote, разработанная где-то в 2013, 2014 году. Вы знаете, если вы читали «белую книгу», то знаете, что это была сильная реакция на недостатки в решении Bitcoin. Вы понимаете, что понятие псевдоанонимности, связанное с Bitcoin, не является адекватным с точки зрения защиты пользователей. Тот факт, что программное обеспечение Bitcoin имеет в себе жёстко закодированные константы, что очень серьёзно влияет на масштабируемость, уже был очевидным. И, несмотря на то, что само решение Bitcoin задумывалось как децентрализованное, реальность обернулась высоким уровнем централизации экосистемы Bitcoin уже в те 2013, 2014 годы.

Итак, я откопал вот эти графики. Это просто пример распределения хешрейта среди майнеров в 2013. Можно отметить, что здесь вероятность проведения атаки 51% довольно высока. Достаточно было одного или сговора двух пулов, чтобы поджарить всю сеть.

А затем произошло развитие технологии майнинга. В самом начале, в самый первый год существования, использовались только PC, CPU. А затем люди неожиданно обнаружили, что GPU прекрасно работают с SHA-2, и началась эра GPU, и всё завертелось. А потом в игру вступили разработчики-любители ASIC, и наконец дело дошло до профессиональных, масштабных коммерческих разработчиков ASIC.

Самая первая схема ASIC по сегодняшним стандартам была довольно скромным усовершенствованием, но даже её эффективность уже была в пятьдесят раз выше. Сегодня едва ли кому-то в голову придёт заниматься майнингом Bitcoin посредством PC, поскольку ASIC будет работать в миллион раз лучше. В миллион раз лучше, чем CPU. Наблюдая за Bitcoin, мы получаем опыт и можем отметить, что как только появляется зависимость от специализированного оборудования, автоматически повышается уровень централизации, то есть происходит то, с чем мы постоянно боремся, поскольку централизация мощности подразумевает проблемы с доверием. По сути, Кристи уже упомянула, производители ASIC, скорее, пользуются собственными чипами для майнинга в своих интересах, а не создают их для продажи другим. И если они и продают их, то уже после того, как чипы устаревают.

Так почему же эти самые ASIC так эффективны? И в этом контексте я продолжу говорить о SHA-2 схемах ASIC для майнинга Bitcoin. Причины довольно просты. Прежде всего, само аппаратное обеспечение очень просто — оно разрабатывается для решения всего одной задачи, то есть является оборудованием с фиксированной функцией. Оно делает лишь одну вещь, и вещь эта довольно тривиальна. Алгоритм SHA-2 по сути был разработан с расчётом на лёгкость вычислений. Таким образом, объём необходимой работы невелик. И сам алгоритм безумно прост, он решается по прямой, в нём нет точек решения, вы начинаете с одной стороны и заканчиваете на противоположной, и всё.

Так что если вы посмотрите на оборудование для SHA-2, то увидите всего с дюжину компонентов — никаких сложностей. Думаю, не стоит разбираться со схемой коммутации справа, но поверьте мне, там всего пара аддитивных операторов, пара регистров, что тривиально для интегрированных схем.

Хорошо. Итак, мы отметили отсутствие точек принятия решений, никакого разветвления, а также мы отметили, что 100% схемы отвечает за решение вашей задачи, никакой траты памяти или времени, или чего бы то ни было ещё. А когда схема настолько проста, можно без труда разместить тысячи экземпляров на одном чипе. Таким образом, вот такую среду мы имеем на сегодняшний день в случае с Bitcoin.

Хорошо. Итак, повторю, протокол CryptoNote был разработан как реакция на это, но он не стал единственной попыткой решить проблему. Если вы посмотрите на Ethereum, то увидите, что Ethash также был разработан с учётом возможности противодействия ASIC. И оба протокола взяли за основу схожий философский подход, подход, привязанный к памяти. И оказалось, что ребята, разработавшие CryptoNote, были несколько консервативны в своих оценках. CryptoNote превосходно работал в течение трёх или четырёх лет, и я бы сказал, что время и технология догнали его, и устойчивость, которую он обеспечивал, потерпела крах. Ethereum со своим алгоритмом Ethash пока неплохо держится, но, должен сказать, и его дни сочтены.

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

Так что сейчас мы приходим к динамическим алгоритмам без статической последовательности выполнения. Рассматривались и другие, помимо RandomX, и я немного расскажу об этом. Достаточно забавно то, что первый алгоритм, с которым я столкнулся, обсуждался в контексте Ethereum, это была идея, которую они пытались воплотить до того, как перешли на Ethash, и у него были некоторые из характеристик, которые есть у нас в RandomX. Но если вы посмотрите на ту разработку, то вы отметите, что она была довольно, я бы сказал, незавершённой. Они разработали алгоритм в качестве прототипа, но, по сути, так и не реализовали идею до конца.

А затем в конце, простите, в начале прошлого года, примерно в марте, у меня родилась идея RandomJS, и мы работали с ней около полугода, шесть или восемь месяцев, пока не обнаружили в алгоритме такие недостатки, которые мы не могли исправить, слабые места в подходе как таковом. Другим алгоритмом, о котором вы, возможно, слышали, был ProgPow, который, по сути, был разработан командой Кристи. Он был ориентирован на GPU и в этом отношении работал довольно хорошо, обеспечивая массовый параллелизм, который мы имеем в случае с GPU. Я бы сказал, что случайный код, который генерируется… Я по-прежнему считаю, что он довольно прост.

Алгоритм Cryptonight-R, который в настоящее время работает в сети Monero. Причина существования Cryptonight-R заключается в том, что мы пока не закончили разработку RandomX, и некоторые из идей, которые мы воплотили в RandomX, в некотором смысле были взяты и вставлены в Cryptonight, то есть мы сделали что-то вроде заплатки.

Итак, некоторые люди ставили под вопрос или критиковали наше решение сфокусироваться на CPU, они говорили, что мы бросаем GPU на произвол судьбы, но следует рассматривать среду в глобальном смысле. GPU не занимают большой части общей картины. В мире используется гораздо больше CPU, с каждым годом покупается всё больше CPU, и ещё, если говорить о смартфонах, представляющих самый быстрорастущий сегмент на рынке потребительской вычислительной техники, в мире уже насчитывается 2,2 миллиарда пользователей смартфонов, а каждый год покупается 1,5 миллиона новых устройств. Их становится больше, и они совершенствуются. Если вы посмотрите на цикл обновления PC, то увидите, что люди покупают новые компьютеры не чаще, чем раз в два или три года, в то время как большинство пользователей смартфонов предпочитает использовать самую последнюю и самую продвинутую технологию. Эти факторы реально влияют на технологию, разрабатываемую нами, которая предполагает наличие высоких требований к CPU, поэтому появление более мощных новых смартфонов нам только на пользу.

Итак, теперь о самом RandomX. Мы говорим о случайно генерируемых программах на машинном языке для специализированной виртуальной машины, которая была разработана нами. Идея состоит в том, что любая случайная восьмибитная последовательность всегда будет действительной командой. Это было одной из проблем, с которыми мы столкнулись в случае с RandomJS, то есть приходилось генерировать случайную программу, которая соответствовала синтаксису языка Javascript. Таким образом, когда к ней применялись эти правила синтаксиса, становилось сложнее генерировать случайную программу, которая бы работала. Теперь мы говорим о машинном языке, в котором отсутствуют правила синтаксиса, любое сгенерированное вами случайное число будет действительной командой. Я называю это умеренной сложностью, так как если вы сравните их и взглянете на виртуальную машину RandomX, а затем на реальный процессор Intel или AMD CPU, наш набор команд будет довольно маленьким. Но он делает практически всё, что нам нужно, а сочетание команд, используемое нами в генерируемых программах, моделируется в соответствии с типами операций, которые вы можете увидеть в реальных пользовательских программах.

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

И вот идея и причина, по которой мы выбрали этот подход — мы пытаемся по максимуму использовать то, в чём хороши CPU, а CPU хороши тем, что могут выполнять самый разнообразный код. А если вы попытаетесь построить под это ASIC, то закончится всё тем, что вы создадите CPU. И, опять же, мы сфокусировались на CPU просто потому, что они более доступны, а также потому, что наборы команд для CPU, как правило, выглядят практически одинаково. У всех у них один и тот же набор целочисленных математических операций, у всех у них есть команды ветвления, какими бы они ни были, поэтому нам легко определить поднабор, который будет хорошо работать абсолютно на любом CPU. Мы можем использовать алгоритм с ARM, мы можем запускать его с Intel и AMD, мы можем применить его к PowerPC и к чему вам будет угодно. Для сравнения, GPU, как правило, имеют довольно проприетарный набор команд, и их функции не пересекаются полностью, как в случае с AMD, где набор команд не включает ни одного множества, используемого нами, поэтому, Ok, работать с GPU было бы гораздо сложнее, общий поднабор был бы более ограниченным. И, опять же, у нас есть чёткое понимание того, что работа должна быть динамичной. Если бы у нас был просто фиксированный набор операций, то его было бы легко закрепить за чипом, а это именно то, чего нам хотелось бы избежать.

Теперь вы задумались над тем, что же такое алгоритм доказательства работы, а в конечном счёте это просто цикл временной задержки. Его цель состоит в потреблении времени и в потреблении энергии, и он должен быть настолько неэффективен, насколько это возможно. И это, знаете, это настолько потрясло меня в ментальном плане, ведь я сделал карьеру на том, что создавал эффективное программное обеспечение, подстраивал компиляторы, и всё это делалось для того, чтобы система совершала большую часть работы с меньшим расходом энергии. Но тут интересно следующее: после того как вы проведёте всё своё время, размышляя над этим, вы обязательно придёте к непосредственному пониманию того, какие операции являются затратными, а какие нет. Это позволяет нам иметь особый взгляд на то, как можно написать самый неэффективный алгоритм из возможных. И ещё, есть ещё одна общая тема, с которой я столкнулся: анонимность и децентрализация диаметрально противоположны эффективности. Когда вы имеете дело с эффективными системами, они, как правило, централизованы, и централизация, по сути, повышает эффективность большинства таких систем. И это работает не только в случае с доказательством работы. Если обратиться к сетевой коммуникации, то как обеспечивается безопасность передачи данных в сети? И знаете, мы много говорили об анонимности в течение этого уикенда, и как мне кажется, термины «анонимность» и «секретность» использовались взаимозаменяемо, но в данном случае есть серьёзное отличие: анонимность — это только составляющая секретности. Если у вас есть зашифрованный канал передачи данных между двумя конечными точками, как сессия TLS, например, то в данном случае вы обеспечиваете анонимность содержимого такого канала связи, но сам факт того, что у вас есть такой канал связи, не является анонимным. Людям известно, что вы передавали данные. Таким образом, вы можете вести анонимный разговор, но он не будет секретным. Обеспечение анонимности не является затратным делом. Зашифрованный канал AES не требует значительных затрат, поскольку AES имеет аппаратное ускорение. Но если вы хотите сделать что-то секретное, чтобы никто не знал, что вы сделали это, то соотношение затрат/неэффективности немного возрастёт. Способ обеспечения секретности канала передачи данных, как правило, заключается в том, что вы создаёте массу отвлекающих «помех», позволяющих скрыть передаваемые вами данные, а это также означает, что создаётся большой объём трафика, в котором скрывается фактическое сообщение, отправляемое вами. И снова, как только вы достигаете эффективности, она как бы противопоставляется анонимности и секретности, поэтому мы пытаемся сделать так, чтобы доказательство работы стало неэффективным, децентрализованным, и это по-прежнему разрывает мне мозг, но мы работаем в этом направлении.

Ok, итак, что касается RandomX, мы хотим, чтобы алгоритм стал настолько неэффективным, чтобы он потреблял максимальное количество мощности, использовал максимальный ресурс, обеспечиваемый CPU. И тут у нас есть… эта блок-схема ядра AMD Zen. Сверху можно увидеть клиентскую сторону пользовательского интерфейса, где у нас находится кэш команд, декодер, модуль прогнозирования ветвлений, кэш операций, вот такой внешний интерфейс, на промежуточном уровне у нас модули целочисленных операций, модули операций с плавающей запятой, а на нижнем уровне — интерфейсы памяти и кэши данных.

Если посмотреть на то, что нами было реализовано в RandomX, то можно увидеть, что он фактически использует 100% компонентов ядра, но не использует всей остальной части чипа. У чипа CPU другие интерфейсы. У него интерфейсы PCI Express со всеми остальными вещами, у него есть шина администрирования для передачи данных между чипами системного управления, это такие вещи, которые мы не можем использовать эффективно, просто потому что они сильно привязаны к определённому устройству. Мы не можем учитывать их в зависимости от того, какой чип используется. Но мы можем полностью использовать ядро и весь интерфейс памяти.

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

И как я уже упоминал ранее, генерирование случайной программы является сложной частью, если вы используете высокоуровневый язык. Вам приходится строить её в соответствии с очень строгими правилами, в противном случае код не будет работать. Стандартный способ заключается в построении абстрактного синтаксического дерева, в котором каждый узел будет оператором вашей программы. И тут забавно то, что вы переходите от этого абстрактного синтаксического дерева к исходному коду программы, а затем вы передаёте исходный код в компилятор, и компилятор проводит синтаксический разбор исходного кода и возвращает его в абстрактное синтаксическое дерево, которое уже было у вас. Таким образом, происходит большой объём избыточной работы, и это работало против нас, так как получался эффективный алгоритм доказательства работы, а если вы создадите ASIC для работы с этим алгоритмом, то микросхема обойдёт всю избыточную работу, что будет равноценно получению преимущества с точки зрения эффективности. Именно это и убило идею RandomJS. Таким образом, наилучшим подходом, который мы могли бы использовать, стало генерирование случайных байтов. В этом случае нет никакого синтаксиса и нет никаких правил построения.

Затем, чтобы перевести всё в «родной» машинный код, который работает на реальном CPU, нам не хотелось ограничиваться исключительно x86, поскольку в современном мире архитектуры ARM и других CPU являются ведущими, и нам не хотелось упустить какую-либо из них. Мы используем виртуальную машину, которую, по сути, можем перевести в любую из других реальных архитектур CPU, и чтобы сделать это максимально быстро, нам необходимо использовать простые команды уровня машины, которые можно будет легко перенести в команды реальной машины, и просто нет времени на разработку оптимизирующего транслятора, просто проанализировать код и переписать его под определённые цели, поскольку любое время, которое затрачивается на это, могло быть использовано для генерирования хешей.

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

Окончательный результат, используемый нами, вычисляется при помощи Blake 2B, криптографического алгоритма хеширования, разработанного специально для CPU. А затем для более масштабных вычислений мы используем AES, и это работает довольно хорошо, так как большинство современных CPU имеют AES с аппаратным ускорением. Если бы не это, то такой вариант бы даже не рассматривался.

Я бегло пройдусь по всему остальному.

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

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

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

Нами предусмотрен лёгкий режим, не требующий двух гигабайт ОЗУ, а всего 256 мегабайт. Он работает в восемь раз медленнее, чем полный режим, и если мы ещё больше сократим объём используемой памяти, то следующим этапом станут 128 мегабайт, и работа замедлится уже в 3700 раз. Таким образом, существует некий компромисс, связанный с оперативной памятью, и нами была выбрана золотая середина.

Ok, что касается текущего состояния кода. Он уже готов к запуску в monerod для версии x86. Нам всё ещё нужно реализовать версию для ARM. Продолжается работа над версией для GPU, мы уже поддерживаем Nvidia, CUDA, и есть версия OpenGL для AMD GPU, это не стандартная OpenGL, в ней используется значительная часть программы на ассемблере для AMD. Нами проводится четыре аудита безопасности, один уже завершён, два проводятся прямо сейчас, и один начнётся завтра.

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

А вот мы все.

Перевод: Mr. Pickles
Редактирование: Agent LvM
Коррекция: Kukima