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

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

В публичных блокчейнах порядок выполнения транзакций напрямую влияет на экономические последствия. От него зависит, кто получит прибыль, а кто понесёт убытки, ведь валидаторы, строители блоков или секвенсоры могут использовать своё привилегированное положение в процессе формирования блока для извлечения выгоды. Речь идёт о так называемой максимальной извлекаемой ценности (MEV), которая включает фронтранинг, бэкранинг и «сэндвич»-атаки. На первый взгляд, предотвратить такие практики невозможно, ведь именно блок-пропозеры обладают монопольным правом на выбор порядка транзакций, и ни один протокол не ограничивает их свободу действий в этом вопросе.

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

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

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

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

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

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

Вот пример:

• Большинство узлов видят A до B
• Большинство узлов видят B до C
• Большинство узлов видят C до A

В результате формируется цикл предпочтений (A→B→C→A), и ни одна последовательность не удовлетворит большинство одновременно. Сеть не может построить единый порядок, который бы соответствовал наблюдениям большинства. Поскольку идеальный ROF недостижим в таких условиях, практические системы опираются на ослабленные гарантии справедливости, о которых пойдёт речь далее.

Модель справедливости Hashgraph: граф хешей, медианные временные метки и aBFT-консенсус

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

Когда узел получает транзакцию, он упаковывает её в сообщение под названием «событие» и распространяет его среди peers через механизм gossip. При создании нового события узел фиксирует хеш уже увиденных событий и подписывает его цифровой подписью. Это создаёт криптографическое доказательство того, что узел видел предыдущие события до подписания нового. Таким образом, hashgraph обеспечивает причинный порядок: после публикации события его происхождение (предшествующие события) невозможно подменить.

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

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

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

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

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

BOF-протоколы: справедливость через агрегацию блоков

BOF-протоколы определяют «блок» как набор транзакций, формирующих один цикл Кондорсе, и упорядочивают такие блоки справедливо, игнорируя внутренний порядок транзакций внутри блока. Концепция BOF была впервые представлена Махимной Келкаром и соавторами (2020) в работе «Order-Fairness for Byzantine Consensus», где была формализована семья протоколов Aequitas. В Aequitas γ-BOF требует, чтобы если доля γ узлов наблюдала блок b раньше блока b′, то ни один честный узел не может выдать b после b′. Параметр γ определяет минимальную долю узлов, согласных с порядком блоков, чтобы он считался справедливым и был закреплён в протоколе.

Согласно γ-BOF, если транзакция tx должна предшествовать tx′, то tx не может оказаться в более позднем блоке, чем tx′. Когда отношения справедливости образуют цикл, протокол объединяет весь сильно связанный компонент в один блок, так как BOF рассматривает блок, а не отдельные транзакции, в качестве атомарной единицы справедливости. При γ-BOF запрещён лишь один исход: размещение tx′ в строго более раннем блоке, чем tx, если существует направленное ограничение tx→tx′. Протокол допускает нахождение обеих транзакций в одном блоке и не ограничивает их порядок внутри него.

Например, на Рисунке 2 изображён цикл Кондорсе из 30 транзакций, которые будут объединены в один блок. Сортировка по хешу может поставить транзакцию 30 перед 1 в итоговом порядке. Однако доля γ узлов наблюдала транзакцию 1 раньше 30, и тем не менее размещение 30 перед 1 считается справедливым в рамках γ-BOF. Поскольку 1 и 30 находятся в одном блоке, а эта концепция справедливости учитывает только порядок блоков, но не транзакций внутри них.

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

Протокол реализует три скоординированные стадии для обеспечения согласованного упорядочивания транзакций: стадию распространения, согласования и финализации.

На стадии распространения узлы используют FIFO-вещание для передачи транзакций в порядке их локального получения от отправителя, сохраняя последовательность от каждого peer. После стабилизации распространения начинается стадия согласования, где узлы выполняют Set Byzantine Agreement (Set-BA) для достижения консенсуса по единому набору локальных порядков, который станет основой глобального порядка. На стадии финализации узлы строят граф зависимостей, фиксирующий отношения порядка между транзакциями. Все транзакции, образующие цикл в этом графе, группируются в один сильно связанный компонент и финализируются вместе в рамках блока.

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

Для решения этой проблемы была предложена Themis. Она сохраняет свойство γ-BOF, одновременно устраняя проблемы живучести и коммуникационной нагрузки. Как и Aequitas, Themis строит граф зависимостей и объединяет SCC на стадии FairFinalize. Ключевое отличие в том, что Themis не ждёт завершения цикла. Вместо этого она использует отложенное упорядочивание и пакетное «развёртывание», чтобы выводить SCC инкрементально, позволяя новым транзакциям продолжать поступать. Это сохраняет γ-BOF, но превращает слабую живучесть Aequitas в стандартную, гарантируя доставку в рамках ограниченной задержки.

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

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

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

В эмпирическом анализе, проведённом Махимной Келкаром и соавторами, γ-BOF продемонстрировал более высокую устойчивость к манипуляциям с порядком транзакций по сравнению с timestamp-based-подходами в геораспределённых сетях. Однако это требует значительных вычислительных и протокольных затрат, что можно считать недостатком.

Вывод

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

Hashgraph и BOF представляют два последовательных подхода. Ни один из них не является inherently superior — оба встраивают справедливость непосредственно в механизм консенсуса, не полагаясь на доверие или централизацию. Оба демонстрируют, что справедливость — это не бинарное свойство, а спектр компромиссов, определяемый фундаментальными теоретическими ограничениями. В условиях отсутствия синхронизации и ненадёжных часов выбор между агрегацией медианных временных меток и коллапсом циклов отражает разные, но равноправные ответы на одну и ту же проблему.