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

На протяжении десятилетий исследования в области распределенных систем, особенно в сфере византийского консенсуса и репликации конечного автомата (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 не может одновременно удовлетворить все предпочтения большинства.Этот парадокс демонстрирует, почему цель идеального достижения справедливости порядка получения невозможна в асинхронных сетях или даже в синхронных сетях, использующих общие часы, если задержки во внешней сети слишком велики. Эта невозможность требует принятия более слабых определений справедливости, таких как справедливость пакетного порядка.Hedera, использующая алгоритм консенсуса Hashgraph, стремится аппроксимировать строгое понятие справедливости порядка получения (ROF). Она делает это, присваивая каждой транзакции окончательную временную метку, вычисленную как медиана локальных временных меток всех узлов для этой транзакции.Однако это по своей сути подвержено манипуляциям. Один злонамеренный узел может намеренно исказить свои локальные временные метки и инвертировать окончательный порядок двух транзакций, даже если все честные участники получили их в правильном порядке.Рассмотрим простой пример с пятью консенсусными узлами (A, B, C, D и E), где узел E действует злонамеренно. Две транзакции, tx₁ и tx₂, транслируются в сеть. Все честные узлы получают tx₁ раньше tx₂, поэтому ожидаемый окончательный порядок должен быть tx₁ → tx₂.Поскольку окончательная временная метка tx₁ (3) больше, чем у tx₂ (2), протокол выводит tx₂ → tx₁, тем самым инвертируя истинный порядок, наблюдаемый всеми честными узлами.Этот простой пример демонстрирует критический недостаток: функция медианы, хотя и кажется нейтральной, парадоксальным образом является фактической причиной несправедливости, поскольку ею может воспользоваться даже один нечестный участник для искажения окончательного порядка транзакций.В результате часто рекламируемая Hashgraph «справедливая временная метка» является на удивление слабым понятием справедливости. Консенсус Hashgraph не гарантирует справедливость порядка получения и вместо этого полагается на разрешенный набор валидаторов, а не на криптографические гарантии.Однако, чтобы обойти теоретическую невозможность, продемонстрированную Кондорсе, практические схемы справедливого упорядочивания должны каким-либо образом ослабить определение справедливости.Протоколы Aequitas ввели критерий справедливости порядка блоков (Block-Order-Fairness, BOF) или справедливости пакетного порядка. BOF предписывает, что если достаточно много узлов получают транзакцию tx раньше другой транзакции tx′, то tx должна быть доставлена в блоке до или одновременно с tx′, что означает, что ни один честный узел не может доставить tx′ в блоке после tx. Это ослабляет правило с «должна быть доставлена раньше» (требование ROF) до «должна быть доставлена не позднее».Рассмотрим три консенсусных узла (A, B и C) и три транзакции: tx₁, tx₂ и tx₃. Транзакция считается «полученной раньше», если по крайней мере два из трех узлов (большинство) наблюдают ее первыми.Эти предпочтения создают цикл: tx₁ → tx₂ → tx₃ → tx₁. В этой ситуации не существует единого порядка, который мог бы удовлетворить все точки зрения одновременно, что означает невозможность достижения строгой ROF.BOF решает эту проблему, группируя все конфликтующие транзакции в один и тот же пакет или блок вместо того, чтобы принуждать одну предшествовать другой. Протокол просто выводит:[tx₁, tx₂, tx₃]Это означает, что с точки зрения протокола все три транзакции рассматриваются так, как если бы они произошли одновременно. Внутри блока детерминированный механизм разрешения конфликтов (например, хеш-значение) определяет точный порядок их выполнения. Таким образом, BOF обеспечивает справедливость для каждой пары транзакций и поддерживает согласованность окончательного журнала транзакций для всех. Каждая из них обрабатывается не позднее той, что ей предшествует.Эта небольшая, но важная корректировка позволяет протоколу обрабатывать ситуации, когда порядки транзакций конфликтуют, группируя эти конфликтующие транзакции в один и тот же блок или пакет. Важно отметить, что это не приводит к частичному упорядочиванию, поскольку каждый узел по-прежнему должен согласовать одну единую, линейную последовательность транзакций. Транзакции внутри каждого блока по-прежнему располагаются в фиксированном порядке для выполнения. В случаях, когда таких конфликтов не возникает, протокол по-прежнему достигает более сильного свойства ROF.Хотя Aequitas успешно достигла BOF, она столкнулась со значительными ограничениями, в частности, с очень высокой коммуникационной сложностью и могла гарантировать только слабую живучесть. Слабая живучесть подразумевает, что доставка транзакции гарантируется только после завершения всего цикла Кондорсе, частью которого она является. Это может занять произвольно долгое время, если циклы «связываются друг с другом».Протокол Themis был представлен для обеспечения того же сильного свойства BOF, но с улучшенной коммуникационной сложностью. Themis достигает этого, используя три метода: развертывание пакетов (Batch Unspooling), отложенное упорядочивание (Deferred Ordering) и более строгие гарантии внутри пакета (Stronger Intra-Batch Guarantees).В своей стандартной форме Themis требует от каждого участника обмениваться сообщениями с большинством других узлов в сети. Объем требуемой связи увеличивается пропорционально квадрату числа участников сети. Однако в своей оптимизированной версии, SNARK-Themis, узлы используют краткие криптографические доказательства для проверки справедливости без необходимости прямого общения с каждым другим участником. Это снижает коммуникационную нагрузку, так что она растет только линейно, что позволяет Themis эффективно масштабироваться даже в больших сетях.Как и в Aequitas, эти предпочтения создают цикл Кондорсе. Но вместо того, чтобы ждать разрешения всего цикла, Themis поддерживает работу системы, используя метод, называемый развертыванием пакетов (batch unspooling). Он идентифицирует все транзакции, являющиеся частью цикла, и группирует их в один набор, называемый сильно связной компонентой (SCC). В данном случае все три транзакции принадлежат одной и той же SCC, которую Themis выводит как находящийся в процессе обработки пакет, обозначенный как Пакет B₁ = {tx₁, tx₂, tx₃}.Таким образом, Themis позволяет сети продолжать обрабатывать новые транзакции, даже пока внутренний порядок Пакета B₁ все еще финализируется. Это гарантирует живучесть системы и предотвращает ее зависание.Концепция идеальной справедливости в упорядочивании транзакций может показаться простой. Чья транзакция первой достигает сети, должна быть обработана первой. Однако, как показывает парадокс Кондорсе, этот идеал не может быть реализован в реальных распределенных системах. Различные узлы видят транзакции в разном порядке, и когда эти точки зрения конфликтуют, ни один протокол не может построить единую, универсально «правильную» последовательность без компромиссов.Hashgraph от Hedera попытался аппроксимировать этот идеал с помощью медианных временных меток, но этот подход больше полагается на доверие, чем на доказательство. Один нечестный участник может исказить медиану и изменить порядок транзакций, показывая, что «справедливое временное клеймение» на самом деле не является справедливым.Протоколы, такие как Aequitas и Themis, продвигают дискуссию вперед, признавая, что может быть достигнуто, а что нет. Вместо того чтобы гнаться за невозможным, они переопределяют справедливость таким образом, чтобы она сохраняла целостность порядка в реальных сетевых условиях. В результате мы видим не отказ от справедливости, а ее эволюцию. Эта эволюция проводит четкую грань между воспринимаемой справедливостью и доказуемой справедливостью. Она показывает, что истинная целостность порядка транзакций в децентрализованных системах не может зависеть от репутации, доверия валидаторов или разрешенного контроля. Она должна исходить от криптографической верификации, встроенной в сам протокол.Эта статья не содержит инвестиционных советов или рекомендаций. Каждое инвестиционное и торговое действие сопряжено с риском, и читатели должны проводить собственное исследование при принятии решения.Эта статья предназначена для общих информационных целей и не является и не должна рассматриваться как юридическая или инвестиционная консультация. Выраженные здесь взгляды, мысли и мнения принадлежат исключительно автору и не обязательно отражают или представляют взгляды и мнения Cointelegraph.Cointelegraph не одобряет содержание этой статьи или любой упомянутый в ней продукт. Читатели должны провести собственное исследование, прежде чем предпринимать какие-либо действия, связанные с любым упомянутым продуктом