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

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

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

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

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

Самое интуитивное и сильное понятие справедливости — Receive-Order-Fairness (ROF). Неофициально определяемое как «первым получен — первым выполнен», ROF предписывает, что если достаточное количество транзакций (tx) поступают в большинство узлов раньше другой транзакции (tx′), то система должна упорядочить tx перед tx′ для выполнения.

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

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

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

Hedera Hashgraph и недостатки медианного таймстампа

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

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

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

In в этом примере злоумышленник присваивает 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 не гарантирует Receive-Order-Fairness и вместо этого зависит от набора разрешённых валидаторов, а не от криптографических гарантий.

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

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

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

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

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

• 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₃. Из-за задержек сети их локальные порядки отличаются:

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

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

Обзор:

Идея идеальной справедливости в порядке транзакций кажется простой: кто первым достиг сети, тот и должен обрабатываться первым. Однако, как показывает парадокс Кондорсе, эта идея невозможна в реальных распределённых системах. Разные узлы видят транзакции в разном порядке, и при конфликте этих взглядов невозможно построить единый, универсальный «правильный» порядок без компромиссов.

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

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

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

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

Cointelegraph не поддерживает содержание этой статьи и любые упомянутые в ней продукты. Читатели должны самостоятельно исследовать информацию и нести полную ответственность за свои решения.

• #DeFi
• #Hedera
• #Validator
• #CointelegraphResearchArticles