Невозможность идеальной справедливости в порядке транзакций

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

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

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

Парадокс Кондорсе и невозможность идеальной справедливости

Наиболее интуитивное и сильное понятие справедливости - это справедливость по порядку получения (ROF). Неофициально определяемая как "сначала получен, сначала обработан", ROF предписывает, что если достаточное количество транзакций (tx) приходит к большинству узлов раньше, чем другая транзакция (tx′), то система обязана упорядочить tx перед tx′ для выполнения.

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

Парадокс Кондорсе иллюстрирует, как, даже когда каждый узел поддерживает транзитивный внутрений порядок транзакций, коллективное предпочтение в системе может привести к так называемым нетранзитивным циклам. Например, возможно, что большинство узлов получает транзакцию A раньше B, большинство получает B раньше C, и большинство получает C раньше A. Таким образом, три предпочтения большинства образуют цикл (A→B→C→A). Это означает, что ни одно единое, согласованное упорядочение транзакций A, B и C не может удовлетворить все предпочтения большинства одновременно.

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

Hedera Hashgraph и недостаток среднего штамповки времени

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

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

Рассмотрим простой пример с пятью узлами консенсуса (A, B, C, D и E), где узел E действует недобросовестно. Две транзакции, tx₁ и tx₂, передаются в сеть. Все честные узлы получают tx₁ перед tx₂, поэтому ожидаемый итоговый порядок должен быть tx₁ → tx₂.

В этом примере противник присваивает tx₁ более позднюю отметку времени (3) и tx₂ более раннюю (2), чтобы исказить медиану.

Когда протокол вычисляет медианы:

• Для tx₁, отметки времени (1, 1, 4, 4, 3) дают медиану 3.
• Для tx₂, отметки времени (2, 2, 5, 5, 2) дают медиану 2.

Поскольку окончательная отметка времени tx₁ (3) больше, чем tx₂ (2), протокол выводит tx₂ → tx₁, тем самым изменяя истинный порядок, наблюдаемый всеми честными узлами.

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

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

Достижение практических гарантий

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

Протоколы Aequitas ввели критерий справедливости порядка блоков (BOF), или справедливости пакетного порядка. BOF диктует, что если достаточное количество узлов получает транзакцию tx перед другой транзакцией tx′, то tx должна быть доставлена в блоке, передающемся до или одновременно с tx′, что означает, что ни один честный узел не может доставить tx′ в блоке после tx. Это ослабляет правило от "должна быть доставлена перед" (требование ROF) до "должна быть доставлена не позднее чем".

Рассмотрим три узла консенсуса (A, B и C) и три транзакции: tx₁, tx₂ и tx₃. Транзакция считается "полученной ранее", если ее сначала наблюдают хотя бы два из трех узлов (большинство).

Если применить голосование большинства для определения глобального порядка:

• tx₁ → tx₂ (согласовано A и C)
• tx₂ → tx₃ (согласовано A и B)
• tx₃ → tx₁ (согласовано B и C)

Эти предпочтения создают цикл: tx₁ → tx₂ → tx₃ → tx₁. В этой ситуации нет единого порядка, который может удовлетворить все представления одновременно, что означает, что строгий ROF невозможно достичь.

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

Блок B₁ = {tx₁, tx₂, tx₃}

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

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

Несмотря на то, что Aequitas успешно достиг BOF, он столкнулся с серьезными ограничениями, особенно с очень высокой сложностью коммуникации и гарантировавшей лишь слабую живучесть. Слабая живучесть означает, что доставка транзакции гарантирована только после завершения всего цикла Кондорсе, частью которого она является. Это может занять неопределенно долгое время, если циклы "цепляются" друг за друга.

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

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

Предположим, пять узлов (A–E) участвующих в консенсусе получают три транзакции: tx₁, tx₂ и tx₃. Из-за задержек в сети их локальные порядки различаются:

Как и в Aequitas, эти предпочтения создают цикл Кондорсе. Но вместо ожидания разрешения всего цикла, Themis продолжает движение системы, используя метод, называемый раскруткой пакетов. Он идентифицирует все транзакции, которые являются частью цикла, и группирует их в один набор, называемый сильно связанным компонентом (SCC). В этом случае все три транзакции принадлежат к одному SCC, который Themis выводит как пакет в процессе, обозначенный как Пакет B₁ = {tx₁, tx₂, tx₃}.

Делая это, Themis позволяет сети продолжать обработку новых транзакций, даже когда внутренний порядок Пакета B₁ все еще определяется. Это обеспечивает живучесть системы и избегает ее остановки.

Обзор:

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

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

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

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

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

dc.finance не одобряет содержание этой статьи и не поддерживает ни один из упомянутых продуктов. Читатели должны провести собственные исследования, прежде чем предпринимать любые действия, связанные с любым продуктом или компанией, и полностью нести ответственность за свои решения.