Spartan v3: Безопасный консенсус Proof-of-Capacity (PoC) на Substrate

August 3, 2021
Jeremiah Wagstaff

Оригинал статьи: https://medium.com/subspace-network/spartan-v3-secure-proof-of-capacity-poc-consensus-on-substrate-a4c2f2c5ce84

Мой Дискорд: useless_dorozhkina#1394

Мы рады сообщить, что Subspace Labs преодолели третью и последнюю веху нашего Web 3 Foundation Open Grant, внесение консенсуса Spartan Proof-of-Capacity (PoC) в Substrate! Для получения дополнительной информации о цели этого гранта и консенсусе PoC, пожалуйста, обратитесь к первой статье этой серии.

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

Далее следует краткое изложение наших результатов. Для более подробного анализа, пожалуйста, посмотрите Milestone 3 Security Analysis Document. Мы очень благодарны Srivatsan Sridhar, нашему летнему стажеру-исследователю из Стэнфордского университета, за тяжелую работу и глубокие размышления, которые он вкладывал в этот анализ последние несколько месяцев.

Ленивый Фарминг (Сопротивление Атаке Сивиллы)

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

К счастью, мы можем воспрепятствовать ленивому фарму, лишь немного изменив аудит консенсуса. В настоящее время мы применяем общую задачу, то есть все фермеры в сети запрашивают свой плот, или, точнее, свое двоичное дерево поиска (BST), используя одну и ту же случайную задачу. Если вместо этого мы “посолим” вызов идентификатором фармера, так что для каждого идентификатора сивиллы потребуется своя задача; ленивые фармеры теперь будут обязаны поддерживать другой BST и проводить другой поиск для каждого идентификатора, который они используют. Это означает, что фармер-сивилла увидит повышенные вычислительные затраты на участие в консенсусе, линейные степени используемых им идентичностей сивиллы, без каких-либо преимуществ, кроме некоторой начальной пропускной способности.

Симуляция (Nothing-at-Stake)

Блокчейны, в которых используется головоломка консенсуса Proof-of-Work (PoW), такие как Bitcoin, обладают свойством, известным как сохранение работы, которое заставляет любую ноду консенсуса выделять свои ресурсы для решения одной задачи головоломки. Конкретно в случае честного форка сети, майнер не может выделить всю свою хеш-мощность обеим ветвям. Он должен либо выбрать одну ветвь, либо каким-то образом разделить мощность между ними обоими.

Эффективные головоломки консенсуса, такие как Proof-of-Stake (PoS) и Proof-of-Capacity (PoC), не сохраняют это свойство. Вместо этого, в случае форка, фармер может тривиально решить обе ветви и получить из этого преимущество. В настоящее время хорошо известно, что это преимущество ограничено фактором e, а это означает, что злоумышленник, использующий данную стратегию, может дважды расходовать 1/(1+e) или ~27% от общего объема сетевого хранилища (вместо 51%). Если мы сделаем симуляцию стратегией по умолчанию, как предлагают некоторые цепочки PoS и PoC, мы откроем сеть для разрушительной атаки 51%, которая требует еще меньшего объема памяти.

Чтобы справиться с этой проблемой, мы используем не менее известное решение, называемое переработкой вызовов или c-correlation, которое было проиллюстрировано Ouroborous Praos и реализовано в BABE (и служит основой для нашей реализации). Вместо того, чтобы использовать задачу для одного блока (или временного интервала в нашем случае), мы получаем задачу для многих временных интервалов (в одной эпохе), используя одну и ту же (общую) случайность эпохи. Чтобы получить случайность для следующей эпохи, мы объединяем и хешируем результаты нескольких Proofs-of-Replication (PoR) для предыдущей эпохи, создавая randomness beacon.

Этот метод эффективно сглаживает любое преимущество, которое можно было бы получить от симуляции. Чем больше количество ожидаемых блоков в эпоху, тем меньше преимуществ может получить злоумышленник от симуляции. Это происходит за счет повышенной предсказуемости или способности фармеров знать, будут ли они избраны на какой-либо временной интервал в будущем, что может быть использовано в качестве основы для атаки bribery. Мы выбрали параметр в 256 ожидаемых блоков, что обеспечивает предсказуемость около 26 минут при обеспечении безопасности до ~47% хранилища.

Двусмысленность (Спам Блоков)

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

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

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

Компромисс Времени и Памяти (PoRs в Майнинге)

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

Чтобы конкурировать на равных с честным фармером с плотом в один ТБ, состоящим примерно из 250 000 000 кодировок, майнер должен создавать по запросу такое же количество кодировок каждые шесть секунд (интервал блока). Если честная нода может засеять один ТБ примерно за 24 часа, используя стандартный четырехъядерный процессор, злоумышленнику потребуется примерно в 14 000 раз больше непрерывной вычислительной мощности. Если вместо этого мы предположим, что честная сеть имеет один ЭБ хранилища, злоумышленнику потребуется в 14 000 000 000 больше, чем вычислительные ресурсы одного честного фармера.

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

Compression attack (Атака Сжатием)

Оказывается, существует более эффективная форма атаки компромисса между временем/памятью/данными на Spartan (и Subspace), которая использует уязвимость в эффективном аудите на основе таблиц поиска или BST. Напомним, что во время аудита фармер не запрашивает свой плот кодировок, а только BST фиксаций этих кодировок. Это означает, что фармер может удалить свой плот, по-прежнему участвовать в аудите консенсуса и быстро повторно получить кодировку из некоторой информации (например, нонса или индекса части), хранящегося вместе с фиксацией в BST. В Spartan повторное получение кодировки тривиально, поскольку существует только одна часть генезиса. Тем не менее, даже в Subspace злоумышленнику требуется только одна копия незакодированной истории блокчейна, накладные расходы, которые могут амортизироваться среди многих плотов или распределяться между многими нодами.

Фармер, который использует эту лазейку, может эффективно сжать свой плот в 256 раз и, по-видимому, иметь гораздо больше места для хранения, чем честный фармер. Хотя это по-прежнему требует в 256 раз больше вычислений для создания плотов, это нарушает честность принципа один-диск-один-голос, поскольку злоумышленнику, проводящему атаку сжатием, требуется всего 0,2% общего (честного) пространства, выделенного сети, для двойного расходования. Хуже того, в случае с Subspace, мы теряем любые гарантии реплицированного хранения истории блокчейна, поскольку для многих сжимающих фармеров было бы гораздо эффективнее делиться единственной копией незакодированной истории.

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

В частности, мы меняем схему фиксации с схемы, основанной на простом хешировании кодировки, на схему, основанную на коде проверки подлинности сообщений кодировок, использующем односторонние хеш-функции (HMAC), и случайном нонсе. Затем мы требуем, чтобы фармеры периодически повторно фиксировали свои плоты с новым случайным нонсом, полученным из самого блокчейна. Например, каждую неделю фармеру потребуется считывать свои кодировки с жесткого диска и вычислять новый BST на основе нового нонса. Это повлекло бы за собой незначительные накладные расходы для честного фармера и могло бы также амортизироваться в течение интервала. Сжимающий злоумышленник (который намеренно отказался от своих плотов) не может провести повторную фиксацию без повторного плоттинга и теперь должен постоянно засеивать (или майнить), чтобы сохранить свое преимущество.

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

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

Переписывание Истории (Атаки Дальнего Действия)

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

Если бы Subspace был независимым блокчейном, эту проблему нужно было бы решить внутри самого протокола. Однако, поскольку Subspace стремится запуститься как парачейн в сети Polkadot, эта проблема решается за счет общей безопасности, обеспечиваемой Polkadot Relay Chain. Поскольку каждый парачейн передает свой заголовок блока в ретранслирующую цепь, который записывается в каждом соответствующем блоке цепочки ретрансляции, успешная атака дальнего действия должна быть выполнена одновременно как на Subspace Parachain, так и на Polkadot Relay Chain. Поскольку стоимость восстановления ретрансляционной цепи в настоящее время составляет несколько миллиардов долларов, это считается маловероятным.

Гарантия Безопасности и Жизнеспособности

Учитывая следующие предположения:

Spartan (и Subspace) можно рассматривать как безопасное расширение протокола консенсуса в стиле Накамото или протокола консенсуса с самой длинной цепочкой, берущего свое начало с Bitcoin в рамках PoW, расширенного до Ouroboros Praos в рамках PoS, как (в значительной степени) реализованное в BABE и переработанное для Spartan PoC;
Оценка плота (или, точнее, BST) может быть смоделирована как случайный оракул, подобно оценке хеш-функции в PoW или оценке проверяемой случайной функции (VRF) в PoS;
Описанные выше меры противодействия обеспечивают защиту от атак сивиллы, симуляции, двусмысленности, компромисса между временем и памятью, сжатия и дальнего действия;

следует, что ни один экономически рациональный противник с менее чем 47% от общего объема сетевого хранилища не может нанести удар безопасности (т. е. двойное расходование) или жизнеспособности (т. е. цензурировать транзакции) протокола.

Следующие Шаги Subspace

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

Модернизация базового уровня консенсуса с proof-of-useless-space (Spartan) на proof-of-useful-storage (Subspace).
Расширение фармера до работы в качестве ноды в Сети с Распределенным Хранением (DSN) с гарантией, что история блокчейна действительно доступна.
Реализация разделения консенсуса и выполнения внутри клиента, чтобы облегчить фармерам бремя поддержания состояния и вычисления переходов состояний для каждого нового блока.

Мы также запустили закрытый тест для Spartan, который мы скоро откроем для более широкой аудитории вместе с доступом к нашему внутреннему серверу Discord.

Большое спасибо за все отличные отзывы и поддержку, которые мы получили за последние три месяца от команд Parity и Web3 Foundation для разработки и реализации Spartan и многих тонкостей Substrate!