Триптих Максималиста: Трактат об альткоинах. Proof-of-Stake

Автор Эндрю Поэлстра. Оригинал

Это продолжение частей "Что такое криптосистемы?" и "Что такое криптовалюты?", Криптография Биткоина.

Примечание редактора: в частях от 6.1 Поэльстра рассматривает основные параметры, которые менялись в Протоколе Биткоин для запуска альткоинов. До появления Ethereum основным способом запуска "своего токена" было копирование исходного кода Биткоина и его изменение для несовместимости с оригинальным протоколом.

6.2. Изменения хэш-функции

Популярным и в целом безобидным изменением является замена хэш-функции SHA256d, используемой Биткоином, на что-то другое. Это подробно описано автором в разделе часто задаваемых вопросов по ASIC и децентрализации. По сути, на что следует обратить внимание:

1. Простота проверки: если проверка доказательства работы обходится дорого, неоплачиваемые одноранговые ноды будут остановлены (или, по крайней мере, перестанут проверять блоки), ослабляя сеть и полагаясь на майнеров.
2. Отсутствие постепенности: если в доказательстве работы фигурирует «процент завершенности», даже вероятностный, то майнинг превращается в гонку, в которой непропорционально большое преимущество предоставляется крупным майнинговым компаниям. Это способствует централизации.
3. Невозможность оптимизации: если доказательство работы слишком сложное, отдельные майнеры могут найти секретные оптимизации, что сделает майнинг для них намного дешевле и в конечном итоге вытеснит всех остальных майнеров с рынка. Это приводит к централизации.
4. Простота майнинга: для доказательства работы на основе перебора хэшей неизбежно появление специального оборудования. Чем сложнее алгоритм, тем более централизованной будет его разработка. Преимущество, которое предоставляет его использование, вероятно, также будет больше.

Следует отметить, что алгоритм scrypt, самая популярная альтернатива SHA256d, страдает от первой и последней из этих проблем, а также вынужден балансировать между затратами времени и памяти, что является частным случаем третьего пункта (к 2021 году Scrypt уже не является ASIC-устойчивым, прим. ред.).

6.3. Изменения сложности

Еще одно популярное направление попыток менять дизайн Биткоина связано с регулировкой сложности. В Биткоине сложность регулируется в соответствии с петлей отрицательной обратной связи, которая имеет целью сохранить десятиминутный интервал между блоками. Эта регулировка происходит дискретными шагами каждые 2016 блоков, но ограничена четырёхкратным изменением в любом направлении. Формула для регулировки сложности проста:

Новая сложность = старая сложность * (временная метка последнего блока - временная метка 2016 блоков назад) / (2016 * 10 минут)

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

Мы видим, что изменение сложности полностью определяется временными метками двух блоков. Более того, не проводится никакой проверки этих временных меток - да ее и не может быть, поскольку если бы существовал всемирно признанный авторитет по временным меткам, нам бы не понадобился блокчейн! Другими словами, сложность - это параметр блокчейна Биткоина, который может свободно контролироваться майнерами [15].

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

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

Вот некоторые популярные модификации:

1. Введение нескольких хеш-функций; это означает отдельный расчет сложности для каждой хэш-функции, поскольку все они будут иметь различные требования к производительности. Альткоины, которые вводят подобное, должны не только решать вытекающие из этого проблемы, но также рискуют получить совершенно разные частоты блоков для каждой хэш-функции, создавая «хромающий блокчейн», когда циклы накладываются друг на друга.
2. Ослабление или даже снятие предела изменения сложности; это опасно, поскольку дает майнерам гораздо больший контроль над скоростью добавления блоков. Увеличивая частоту блоков, они могут дать себе значительное преимущество, будучи первыми, кто узнает о каждом новом блоке; Уменьшая эту частоту, они могут вытеснить других майнеров из сети за счет увеличения дисперсии их вознаграждений.
3. Увеличение частоты подстройки сложности; это опасно, поскольку эффективно ослабляет ограничение на величину подстройки (если сложность может изменяться в четыре раза каждые 504 блока, она может меняться в 256 раз каждые 2016 блоков), а также позволяет злоумышленникам действовать «набегами» когда им не нужно очень долго контролировать большие части хэш-мощности для выполнения атак.
   Например, terracoin допустил обе эти ошибки и был уничтожен атакой через манипулирование сложностью [16].
4. Сглаживание изменений сложности, например путем ее пересчета для каждого блока, но каждый раз используя временные отметки последних 2016 блоков; само по себе это практически ни на что не влияет. Однако для поддержания четырехкратного предела для 16 блоков изменение сложности для каждого блока должно быть ограничено коэффициентом 41 = 2016 = 1: 00069. Насколько мне известно, ни один из существующих альткоинов не имеет таких жестких порогов, поэтому эффективное ограничение ослабляется, и цепочка подвергается вышеуказанным атакам.
5. Внедрение какой-нибудь сложной адаптивной схемы, такой как Kimoto Gravity Well (KGW); По сути, это запутанный способ внести некоторые или все вышеперечисленные изменения, и он сопряжен с теми же рисками. Это также усложняет консенсусный код, обеспечивая больше возможностей из-за небольших различий в разных реализациях клиентов создавать форки сети. Обычно эти схемы требуют больше вычислительных ресурсов и, следовательно, значительно удорожают определение самой длинной цепочки только с помощью доказательства выполнения работы, что ложится непропорционально тяжелой нагрузкой на легкие узлы.
   Например, megacoin и vertcoin используют KGW; эти альткойны не подвергались атакам с использованием меток времени, но в результате пострадала их масштабируемость.

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

6.4 Proof of Stake

Стоило нам обзавестись понятием криптовалюты и криптографически не подделываемой передачи стоимости, естественным продолжением этой идеи стало криптографически не подделываемое доказательство владения. Это идея, лежащая в основе proof-of-stake. Для криптовалют в рамках proof-of-stake можно подтверждать не только право собственности на конкретную сумму валюты, но и демонстировать, что эта валюта удовлетворяет определенным условиям (например, она заблокирована и не может быть потрачена, пока не будет выполнен некий контракт).

В частности, подтвержденная доля в редкой и экспериментальной криптовалюте может считаться доказательством заинтересованности в успехе проекта. Доказав долю, заблокированную на определенное время, можно подтвердить этим заинтересованность в продолжительном (и устойчивом) развитии проекта.

Использование proof-of-stake в качестве замены proof-of-work при достижении распределенного консенсуса - популярная идея. Как мы увидим, эта идея в корне ошибочна.

Неудачи. Это не очень-то рекламируется, но в действительности не было ни одного примера, чтобы криптовалюта достигла распределенного консенсуса с помощью proof-of-stake. Прототип валюты proof-of-stake, Peercoin, определяет валидность блока по подписям разработчиков: таким образом консенсус не является распределенным. Та же участь постигла и другие валюты с номинальным PoS, такие как Blackcoin. В своем первоначальном воплощении NXT был подвержен тривиальной атаке через stake-grinding (манипуляцию алгоритмом случайных чисел) и не смог достичь какого-либо консенсуса. После перехода на закрытый код [17] и спама технически безграмотными заявлениями на популярных конференциях, эта валюта должна рассматриваться уже вне рамок данной статьи.

Фактически, Peercoin изначально предполагал отказ от подписей разработчиков после распределения долей. Однажды разработчики попытались это сделать, и тут же нарвались на атаку через stake-grinding. Тогда они незаметно удалили текст, свидетельствующий о намерении отказаться от подписей разработчиков, и добавили небольшой PoW, чтобы сделать stake-grinding менее тривиальным.

Наконец, следует упомянуть, что подписанные разработчиком блоки известны в сообществе PoS как контрольные точки. Это название вводит в заблуждение, потому что оно уже используется для описания меры защиты одноранговой сети Биткоина от отказа в обслуживании; Контрольные точки Биткоина не имеют никакого отношения к консенсусу. Поэтому утверждения сторонников PoS о том, что «Биткойн тоже имеет контрольные точки», просто ложны.

Распределенный консенсус. По сути, идея использования proof-of-stake в качестве механизма консенсуса состоит в том, чтобы переместить альтернативные издержки извне системы внутрь системы. Мотивация для этого заключается в том, что использование «наибольшей доказанной работы» в качестве критерия консенсуса создает экономический стимул доказать как можно больше работы. Для Биткоина, где доказывается термодинамическая работа (то, что было выполнено определенное количество необратимых вычислений), существует физический предел - предел Ландауэра, который определяет, что означает «как можно больше работы» [18]. Этот предел обеспечивает чрезвычайно ресурсоемкий консенсус, производящий энтропию и ведущий нас к тепловой смерти Вселенной буквально с максимальной скоростью, допускаемой законами физики [*]. Перенося альтернативные издержки внутрь искусственно созданной криптовалютной системы, можно будет создать законы, которые налагают гораздо меньшие требования к потреблению ресурсов.

На более низком уровне принцип proof-of-stake состоит в том, что держатели валюты могут заблокировать свои монеты на некоторое время, фиксируя свою «долю», что можно криптографически проверить. Затем, чтобы продолжить консенсусную историю, вместо того, чтобы прикреплять доказательство работы, каждый владелец доли подписывает это продолжение цифровой подписью. По соображениям практичности обычно для каждого продолжения делается небольшая случайная выборка держателей доли, и для того, чтобы это продолжение считалось валидным, достаточно подписей большинства от этой выборки. Выбранные держатели доли получают вознаграждение, и через некоторое время они могут разблокировать свою долю, если пожелают.

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

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

В этом аргументе легко обнаруживается неувязка: «короткий интервал времени» короток лишь в сравнении с консенсусной историей, и соответствует короткому интервалу в реальном времени лишь в том случае, если консенсусная история вообще существует. Так что вопрос все еще остается подвешенным. Фактически, если держатель доли позже безвозвратно продаст свою долю за какой-либо ресурс вне системы (например, на бирже), у него больше нет стимула не форкать историю (или, что еще хуже, не опубликовать свои ключи, позволив другим форкнуть историю) в момент консенсусного времени, когда он имел контроль.

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

Теперь у нас есть консенсусная история и злоумышленник, который может форкнуть ее в какой-то момент. Чтобы фактически заменить всю консенсусную историю, ему нужно создать альтернативную историю, начиная со своего форка, которая длиннее, чем существующая история. Но для каждого блока требуется новый случайный выбор подписывающих лиц, так возможно ли это? Ответ абсолютно положительный: мы использовали слово «случайный», но на самом деле мы требовали консенсуса по набору подписантов (в противном случае возникли бы тривиальные форки), поэтому даже случайный выбор должен выводиться из прошлой консенсусной истории. Следовательно, злоумышленник с достаточным количеством ключей в прошлом может изменить историю, над которой он имеет непосредственный контроль, в результате чего будущий выбор подписантов всегда будет происходить в его пользу. (Скорее всего, ему нужно «перебрать» множество вариантов блоков, прежде чем он найдет тот, который позволяет ему контролировать выбор подписывающей стороны. По сути, он заменил доказательство доли на доказательство работы, но централизованное.)

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

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

Проблема в конечном итоге сводится к тому, что Грег Максвелл называет беззатратной симуляцией, а Эндрю Миллер именует nothing at stake, то есть "ничего не поставлено на карту". Если подписанты не несут затрат на создание валидных блоков, они могут дешево искать в пространстве блоков те, что направляют историю в их пользу. Независимо от того, как сеть спроектирована ради предотвращения захвата власти меньшинством, злоумышленник может направить историю в сторону настоящего, в котором он имеет большинство, с точки зрения консенсуса, даже если в физическом пространстве он представляет лишь небольшую часть держателей.

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

Непринципиальные недостатки. Помимо неспособности proof-of-stake обеспечить распределенный консенсус, которую можно преодолеть, используя для достижения консенсуса «гибридную» систему proof-of-work/proof-of-stake или даже деноминируя долю в какой-либо другой валюте, которая имеет работоспособный консенсус, например, в биткоинах - при использовании доли владения для определения действительности блока также есть проблемы в стимулах.

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

Если блоки недействительны без достаточного количества (во всех существующих системах proof-of-stake «достаточно много» означает одну) подписей, это дает подписывающим сторонам возможность отказываться подписывать до тех пор, пока не будут выполнены некоторые требования, фактически беря блоки в заложники. Это может быть использовано для прямых атак или для того, чтобы помешать майнерам, работающим в режиме proof-of-work (или каким угодно еще, обеспечивающим фактический консенсус), ослабляя этим безопасность валюты.

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

7 Куда я следую дальше

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

Для начала несколько активных и известных криптографов ведут блоги, посвященные изложению криптографических идей в доступной форме. Особый интерес представляют блоги Мэтью Грина и Брюса Шнайера. Также текущие академические исследования обычно публикуются в архиве препринтов на сайте eprint.iacr.org. Полезно периодически просматривать аннотации, чтобы найти интересные работы и чтобы получить представление о текущих тенденциях в криптографических исследованиях.

Исторический очерк с древнейших времен до Второй мировой войны можно найти в книге Дэвида Кана "Взломщики кодов". Это очень длинный текст, но читать его приятно и увлекательно.

Что касается современной криптографии, многие классические работы доступны в Интернете. Неполный и неупорядоченный список необходимой литературы:

• Probabilistic Encryption, Goldwasser and Micali, 1984.
• A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms, ElGamal, 1985.
• The Decision Diffie–Hellman Problem, Boneh, 1998.
• Proofs of Partial Knowledge and Simplified Design of Witness Hiding Protocols, Cramer, Damgård, Schoenmakers, 1994.

• How to Prove Yourself: Practical Solutions to Identification and Signature Problems, Fiat and Shamir, 1986.

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

Дэн Боне также предлагает отличные бесплатные курсы по криптографии онлайн. Доступ к ним можно получить по следующим ссылкам.

• https://www.coursera.org/course/crypto
• https://www.coursera.org/course/crypto2

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

Ссылки

[15] *** здесь авторское примечание, которое перенесено в текст

[16] Обсуждение этого события можно посмотреть в соответствующей ветке форума bitcointalk.

[17] В марте 2015 года со мной связался разработчик NXT и сообщил, что теперь NXT доступен по опенсорсной лицензии MIT.

[18] Вот почему мы считаем доказательство работы «доказательством»: пока наша хэш-функция сильна, законы физики предотвращают мошенничество.

[19] *** здесь авторское примечание, которое перенесено в текст