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

Протягом десятиліть дослідження у розподілених системах, особливо у Byzantine консенсусі та реплікації стану машини (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, прагне наблизитися до сильної ідеї справедливості порядку отримання (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 вузли використовують короткі криптографічні докази для перевірки справедливості без необхідності безпосереднього спілкування з кожним учасником. Це зменшує навантаження на комунікацію, що дозволяє масштабувати систему навіть у великих мережах.

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

As у Aequitas ці переваги створюють цикл Кондорсе. Але замість чекати, поки весь цикл буде розв’язаний, Themis підтримує рух системи за допомогою методу, званого пакетним розплутуванням. Він визначає всі транзакції, що входять до циклу, і групує їх у один набір, названий сильною зв’язною компонентою (SCC). У цьому випадку всі три транзакції належать до однієї SCC, яку Themis видає як пакет у процесі обробки, позначений як Блок B₁ = {tx₁, tx₂, tx₃}.

Завдяки цьому Themis дозволяє мережі продовжувати обробку нових транзакцій, навіть поки внутрішній порядок пакету B₁ ще не остаточний. Це забезпечує живучість системи і запобігає зупинкам.

Огляд:

Ідеал досконалої справедливості у порядку транзакцій може здаватися простим. Той, чия транзакція першою потрапила до мережі, має бути оброблений першою. Однак, як показує парадокс Кондорсе, цей ідеал неможливий у реальних розподілених системах. Різні вузли бачать транзакції у різному порядку, і коли ці погляди конфліктують, жоден протокол не може побудувати єдину, універсальну «правильну» послідовність без компромісів.

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

Протоколи, такі як Aequitas і Themis, рухають дискусію вперед, визнаючи, що можна і чого не можна досягти. Замість того, щоб переслідувати неможливе, вони переосмислюють справедливість так, щоб вона зберігала цілісність порядку за реальних умов мережі. Виникає не відмова від справедливості, а її еволюція. Ця еволюція чітко розмежовує сприйману справедливість і доведу справедливість. Вона показує, що справжня цілісність порядку транзакцій у децентралізованих системах не може залежати від репутації, довіри валідаторів або дозволеного контролю. Вона має базуватися на криптографічних доказах, закладених у сам протокол.

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

Ця стаття є загальним інформаційним ресурсом і не призначена для надання юридичних або інвестиційних порад. Відгуки, думки та погляди, викладені тут, належать лише автору і не обов’язково відображають позицію Cointelegraph.

Cointelegraph не підтримує зміст цієї статті та жодних продуктів, згаданих у ній. Читачам рекомендується самостійно досліджувати перед будь-якими діями щодо будь-яких продуктів або компаній, згаданих у статті, і нести повну відповідальність за свої рішення.