Aptos labs вирішила дві важливі відкриті проблеми в DAG BFT, значно зменшивши затримку та вперше усунувши потребу в паузах у детермінованих практичних протоколах. Загалом це покращує затримку Bullshark на 40% у випадку відсутності збоїв і на 80% у випадку збою.
Shoal — це структура, яка покращує будь-який консенсусний протокол на основі Narwhal (наприклад, DAG-Rider, Tusk, Bullshark) за допомогою конвеєрної обробки та репутації лідера. Конвеєрна підготовка зменшує затримку впорядкування DAG, вводячи прив’язку на раунд, а репутація лідера додатково покращує затримку, гарантуючи, що прив’язки пов’язані з найшвидшими валідаторами. Крім того, репутація лідера дозволяє Shoal використовувати асинхронну конструкцію DAG для усунення тайм-аутів у всіх сценаріях. Це дозволяє Shoal надати властивість, яку ми назвали Universal Response, яка містить оптимістичну відповідь, яка зазвичай потрібна.
Наша техніка дуже проста, вона передбачає послідовне виконання кількох екземплярів основного протоколу один за одним. Таким чином, якщо створити екземпляр за допомогою Bullshark, ми отримаємо групу «акул», які беруть участь в естафеті.
Мотивація
У гонитві за високою продуктивністю в блокчейн-мережах постійна увага приділяється зменшенню складності зв’язку. Однак такий підхід не призвів до істотного збільшення пропускної здатності. Наприклад, реалізація Hotstuff у ранній версії Diem досягла лише 3500 TPS, що набагато нижче нашої мети досягти 100k+ TPS.
Однак нещодавні прориви пов’язані з усвідомленням того, що розповсюдження даних є головним вузьким місцем протоколів на основі лідерів і що воно може виграти від розпаралелювання. Система Narwhal відокремлює розповсюдження даних від основної консенсусної логіки та пропонує архітектуру, де всі валідатори поширюють дані одночасно, тоді як консенсусні компоненти впорядковують лише меншу кількість метаданих. Газета Narwhal повідомляє про продуктивність 160 000 TPS.
У попередній статті ми представили Quorum Store. Наша реалізація Narwhal відокремлює розповсюдження даних від консенсусу, і як ми використовуємо це для розширення нашого поточного протоколу консенсусу Jolteon. Jolteon — це провідний протокол, який поєднує швидкий лінійний шлях Tendermint зі змінами перегляду в стилі PBFT, щоб зменшити затримку Hotstuff на 33%. Однак очевидно, що консенсусний протокол на основі лідера не може повністю використати пропускну здатність Narwhal. Незважаючи на відокремлення розповсюдження даних від консенсусу, лідери Hotstuff/Jolteon все ще обмежені, оскільки пропускна здатність зростає.
Тому ми вирішили розгорнути Bullshark, консенсусний протокол із нульовими витратами на зв’язок, поверх Narwhal DAG. На жаль, структура DAG, яка підтримує високу пропускну здатність Bullshark, має 50% штраф за затримку порівняно з Jolteon.
У цій публікації ми описуємо, як Shoal досяг значного скорочення затримки Bullshark.
Фон DAG-BFT
Давайте почнемо з розуміння відповідної передісторії цієї статті. Щоб отримати детальний опис Narwhal і Bullshark, зверніться до публікації DAG зустрічає BFT.
Кожна вершина в DAG Narwhal пов’язана з круглим числом. Щоб увійти в раунд r, верифікатор повинен спочатку отримати nf вершин, що належать раунду r-1. Кожен верифікатор може транслювати одну вершину за раунд, і кожна вершина посилається принаймні на nf вершин у попередньому раунді. Через асинхронність мережі різні валідатори можуть спостерігати різні локальні перегляди DAG у будь-який момент часу. Ось ілюстрація можливого часткового перегляду:
Рисунок 1: Причинно-наслідкова історія вершин, визначених у раунді 2 перевірки, вузол 2 виділено зеленим кольором
Ключовою властивістю DAG є відсутність двозначності: два валідатори мають однакову причинно-наслідкову історію v, якщо вони мають однакову вершину v у своєму локальному представленні DAG.
Загальне замовлення
Можна узгодити загальний порядок усіх вершин у DAG без додаткових витрат на зв’язок. З цією метою валідатори в DAG-Rider, Tusk і Bullshark інтерпретують структуру DAG як консенсусний протокол, де вершини представляють пропозиції, а ребра представляють голоси.
Хоча логіка групового перетину відрізняється від структури DAG, усі існуючі консенсусні протоколи на основі Narwhal мають таку структуру:
Заздалегідь визначені якорі, буде заздалегідь визначений лідер кожні кілька раундів (наприклад, два раунди в Bullshark), а вершини лідера називаються якорями;
Упорядковуючи прив’язки, верифікатор незалежно, але детерміновано вирішує, які прив’язки замовляти, а які пропустити;
Порядок причинно-наслідкових історій, де валідатори обробляють свій упорядкований список прив’язок один за одним, і для кожного прив’язки сортують усі попередньо невпорядковані вершини в його причинно-наслідковій історії за якимось детермінованим правилом.
Рисунок 2: Ілюстрація можливого часткового вигляду DAG у протоколі Bullshark. У цьому прикладі червоні та жовті прив’язки сортуються, тоді як зелені (не в DAG) пропускаються. Тому, щоб упорядкувати DAG, валідатори спочатку детерміновано впорядковують історії причин червоних прив’язок, а потім жовтих прив’язок.
Ключ до забезпечення безпеки полягає в тому, щоб на кроці (2) вище всі чесні валідатори створили впорядкований список прив’язок, щоб усі списки мали однаковий префікс. У Shoal ми робимо такі зауваження щодо всіх наведених вище протоколів:
** Усі валідатори погоджуються щодо першого замовленого прив’язки. **
Затримка Bullshark
Затримка Bullshark залежить від кількості раундів між упорядкованими якорями в DAG. Хоча найбільш корисна частково синхронна версія Bullshark має кращу затримку, ніж асинхронна версія, вона далека від оптимальної.
Проблема 1: Середня затримка блоку. У Bullshark кожен парний раунд має якір, а вершини кожного непарного раунду інтерпретуються як голоси. Як правило, потрібно два раунди DAG, щоб упорядкувати прив’язки, однак вершини в причинно-наслідковій історії прив’язки потребують набагато більше раундів, щоб очікувати впорядкування прив’язки. У звичайному випадку вершини в непарних раундах вимагають трьох раундів, тоді як вершини без прив’язки в парних раундах вимагають чотирьох раундів (див. Малюнок 3).
Рисунок 3: У звичайному випадку прив’язки в раунді i+1 потрібно відсортувати для двох раундів. Вершини в раунді i сортуються одночасно, тому їх затримка становить три раунди. Однак вершини в раунді i+1 повинні чекати на сортування наступного прив’язки (той, що в раунді i+3), тому їхня затримка сортування становить чотири раунди.
Проблема 2: Затримка у випадку невдачі, наведений вище аналіз затримки застосовується до випадку без невдачі, з іншого боку, якщо лідер раунду не в змозі транслювати прив’язки досить швидко, прив’язки не можуть бути впорядковані (і, отже, пропускаються), тому всі невідсортовані вершини в попередніх раундах повинні чекати на сортування наступного прив’язки. Це може значно знизити продуктивність геореплікованої мережі, особливо тому, що Bullshark використовує тайм-аути в очікуванні лідера.
Рамка мілини
Shoal вирішує обидві ці проблеми із затримкою, покращуючи Bullshark (або будь-який інший протокол BFT на основі Narwhal) за допомогою конвеєрної обробки, дозволяючи прив’язку в кожному раунді та зменшуючи затримку всіх неприв’язаних вершин у DAG до трьох раундів. Shoal також впроваджує механізм репутації лідера без накладних витрат у DAG, який зміщує вибір на користь швидких лідерів.
виклик
У контексті протоколів DAG конвеєрне забезпечення та репутація лідера вважаються складними проблемами з таких причин:
Попередні конвеєрні спроби змінити основну логіку Bullshark, але це здається неможливим за своєю суттю
Репутація лідера, введена в DiemBFT і формалізована в Carousel, — це ідея динамічного вибору майбутніх лідерів (якорів у Bullshark) на основі минулої продуктивності валідаторів. Хоча розбіжності щодо ідентичності лідера не порушують безпеку в цих протоколах, у Bullshark це може призвести до зовсім іншого порядку, що потрапляє в суть питання, яке полягає в тому, що динамічний і детермінований вибір колісних якорів є рішенням для досягнення консенсусу, тоді як валідаторам потрібно узгодити впорядковану історію, щоб вибрати майбутні прив’язки.
Як доказ складності проблеми ми зауважимо, що реалізація Bullshark, включаючи поточну реалізацію у виробництві, не підтримує ці функції.
Угода
Незважаючи на вищезазначені проблеми, виявляється, що рішення, як то кажуть, ховаються за простотою.
У Shoal ми покладаємося на здатність виконувати локальні обчислення на DAG і реалізуємо здатність зберігати та переосмислювати інформацію з попередніх раундів. Маючи основне розуміння того, що всі валідатори погоджуються щодо першого впорядкованого прив’язки, Shoal конвеєрує їх, створюючи кілька екземплярів Bullshark так, щоб (1) перший упорядкований прив’язка була точкою перемикання для примірників, і (2) причинно-наслідкова історія якір використовується для розрахунку репутації лідера.
Конвеєрна розробка
Подібно до Bullshark, валідатори апріорі узгоджують потенційні прив’язки, тобто існує відоме відображення F: R -> V відображення раундів до лідерів. Shoal запускає екземпляри Bullshark один за одним таким чином, що для кожного екземпляра прив’язка заздалегідь визначена картою F. Кожен екземпляр замовляє якір, який запускає перехід до наступного екземпляра.
Спочатку Shoal запускає перший екземпляр Bullshark у першому раунді DAG і запускає його, доки не буде ідентифіковано перший впорядкований якір, скажімо, у раунді r. Усі валідатори згодні з цим прив’язкою. Таким чином, усі валідатори можуть детерміновано домовитися про те, щоб повторно інтерпретувати DAG, починаючи з раунду r+1. Шол щойно починає новий екземпляр Bullshark у раунді r+1.
У найкращому випадку це дозволяє Шоалу замовляти якір кожного раунду. Якір для першого раунду сортується за першим зразком. Потім Шол запускає новий екземпляр у другому раунді, який сам має якір, замовлений екземпляром, потім інший новий екземпляр замовляє якір у третьому раунді, і процес продовжується. Будь ласка, перегляньте ілюстрацію нижче:
Рисунок 4: Вершини, що відповідають лідерам, визначеним F, позначені короною.Перший екземпляр Bullshark спочатку інтерпретує DAG з якорями в раундах 1, 3 і 5. Bullshark визначає якорі в раунді 1 (зелена галочка mark) є першим, який сортується в першому випадку. (Зауважте, що в загальному випадку цей якір можна пропустити, тоді як деякі інші якорі будуть відсортовані першими.) Потім решта першого екземпляра ігнорується, а новий екземпляр Bullshark починається з раунду 2, точки прив’язки позначаються. у 2 і 4 раундах.
Репутація лідера
Збільшена затримка під час пропуску прив’язок під час сортування Bullshark. У цьому випадку техніка конвеєрної обробки безсила, оскільки новий екземпляр не може бути запущений, доки попередній екземпляр не замовить прив’язку. Shoal гарантує, що відповідний лідер з меншою ймовірністю буде обраний у майбутньому, щоб мати справу з втраченим якорем, використовуючи механізм репутації, щоб призначити кожному валідатору бал на основі його історії останніх дій. Валідатор, який відповідає та бере участь у протоколі, отримає високу оцінку, інакше валідатору буде присвоєно низький бал, оскільки він може вийти з ладу, бути повільним або шкідливим.
Ідея полягає в тому, щоб детерміновано повторно обчислювати попередньо визначене відображення F від раундів до лідерів при кожному оновленні балів, віддаючи перевагу лідерам з вищими балами. Для того, щоб валідатори погодилися щодо нового відображення, вони повинні узгодити оцінку і, отже, історію, використану для отримання оцінки.
У Shoal конвеєрну репутацію та репутацію лідера можна природно поєднати, оскільки обидва вони використовують ту саму основну техніку переосмислення DAG після узгодження першого впорядкованого якоря.
Фактично, єдина відмінність полягає в тому, що після сортування прив’язок у раунді r валідатору потрібно лише обчислити нове відображення F' із раунду r+1 на основі історії причин упорядкованих прив’язок у раунді r. Потім валідатор виконує новий екземпляр Bullshark, починаючи з раунду r+1, використовуючи оновлену функцію вибору прив’язки F'. Дивіться зображення нижче:
Рисунок 5. Вершини, що відповідають лідерам, позначеним F, позначені прозорими коронами. Перший екземпляр Bullshark замовляє якір у раунді 1, позначений зеленою галочкою, а потім обчислює нове відображення F' на основі інформації в причинно-наслідковій історії прив’язки. Лідери, визначені F', позначені кольоровими коронами.
Більше ніяких тайм-аутів
Тайм-аути відіграють вирішальну роль у всіх детермінованих частково синхронних реалізаціях BFT на основі лідера. Однак складність, яку вони вводять, збільшує кількість внутрішнього стану, яким потрібно керувати та спостерігати, що ускладнює процес налагодження та вимагає додаткових методів спостереження.
Тайм-аути також можуть значно збільшити затримку, оскільки їх важливо правильно налаштувати, і зазвичай їх потрібно регулювати динамічно, оскільки це сильно залежить від середовища (мережі). Протокол сплачує несправному лідеру повний штраф за затримку тайм-ауту перед переходом до наступного лідера. Тому параметр тайм-ауту не може бути надто консервативним, але якщо тайм-аут занадто короткий, протокол може пропустити хороших лідерів. Наприклад, ми помітили, що під високим навантаженням лідери в Jolteon/Hotstuff були перевантажені, і тайм-аути минали, перш ніж вони змогли підвищити прогрес.
На жаль, протоколи на основі лідерів, такі як Hotstuff і Jolteon, за своєю суттю вимагають тайм-аутів, щоб гарантувати, що протокол може прогресувати щоразу, коли лідер виходить з ладу. Без тайм-ауту навіть лідер, що впав, може призупинити протокол назавжди. Через неможливість відрізнити несправний лідер від повільного лідера під час асинхронізації, тайм-аути можуть призвести до того, що валідатори бачать зміни всіх лідерів без консенсусної жвавості.
У Bullshark тайм-аути використовуються в побудові DAG, щоб гарантувати, що під час синхронізації чесний лідер додає прив’язки до DAG досить швидко, щоб їх можна було впорядкувати.
Ми спостерігаємо, що конструкція DAG забезпечує «годинник» для оцінки швидкості мережі. За відсутності пауз раунди продовжують просуватися до тих пір, поки nf чесних валідаторів продовжують додавати вершини до DAG. Хоча Bullshark може не мати змоги сортувати на швидкості мережі (через проблемні лідери), DAG все ще зростає на швидкості мережі, незважаючи на деякі проблеми з лідером або асинхронність мережі. Згодом, коли безпомилковий лідер транслює ведучі досить швидко, уся причинно-наслідкова історія ведучих буде впорядкована.
У нашій оцінці ми порівнювали Bullshark із тайм-аутом і без нього в таких випадках:
Швидкий лідер, тобто принаймні швидше, ніж інші валідатори. У цьому випадку обидва методи забезпечують однакову затримку, оскільки прив’язки впорядковуються, а тайм-аути не використовуються.
Помилковий лідер, у цьому випадку Bullshark без пауз забезпечує кращу затримку, оскільки валідатори негайно пропускають свої прив’язки, тоді як валідатори з паузами чекатимуть їх прибуття, перш ніж продовжити Expect.
Повільний лідер, це єдиний випадок, коли Bullshark має кращу продуктивність тайм-ауту. Це пояснюється тим, що без паузи прив’язка може бути пропущена, оскільки ведучий не може транслювати її достатньо швидко, тоді як з паузою валідатори чекатимуть прив’язки.
У Shoal уникання тайм-аутів і лідерська репутація йдуть рука об руку. Повторне очікування повільного лідера збільшує затримку, а механізм репутації лідера запобігає обранню повільних валідаторів лідерами. Таким чином, система використовує вузли швидкої перевірки для роботи на швидкості мережі в усіх сценаріях реального світу.
Зверніть увагу, що результат неможливості FLP показує, що жоден детермінований консенсусний протокол не може уникнути тайм-аутів. Шол не може обійти цей результат, оскільки існує теоретичний розклад змагальних подій, які перешкоджають керуванню всіма якорями. Натомість Shoal повертається до тайм-ауту після настроюваної кількості послідовних пропусків прив’язки. На практиці це вкрай малоймовірно.
Загальна відповідь
Стаття Hotstuff популяризувала концепцію оптимістичної відповіді, яка, хоча формально не визначена, інтуїтивно означає, що протокол може працювати на швидкості мережі за хороших умов, включаючи швидкий лідер і синхронну мережу.
Shoal забезпечує ще кращу властивість, яку ми називаємо Universal Response. Зокрема, на відміну від Hotstuff, Shoal продовжує працювати на швидкості мережі, навіть якщо лідер виходить з ладу протягом заданої кількості послідовних раундів або асинхронних циклів, через які проходить мережа. Дивіться більш детальне порівняння в таблиці нижче.
Зауважте, що універсальна чутливість забезпечує чітко кращі гарантії прогресу під час асинхронних періодів і коли лідер зазнає невдачі. Під час синхронізації з повільним лідером ці властивості не можна порівнювати, оскільки це залежить від того, наскільки повільним є лідер. Однак, враховуючи репутацію лідера, повільні лідери повинні рідко з'являтися в Шол.
Оцініть
Ми реалізували Bullshark і Shoal поверх нашої реалізації Narwhal Quorum Store. Детальне порівняння між Shoal, Bullshark і Jolteon можна знайти в розділі оцінки статті Shoal, де ми надаємо деякі основні моменти.
По-перше, щоб продемонструвати силу асинхронної конструкції DAG, ми порівнюємо Bullshark із паузами та без них. Повний документ Bullshark передбачає асинхронну мережу, але забезпечує швидкий режим, що вимагає пауз під час усіх раундів. Ми називаємо цю версію Vanilla Bullshark. Ми спостерігаємо, що для гіпотетичних версій незалежної частково синхронної мережі не потрібні паузи в раундах голосування. Ми називаємо цю версію Vanilla Bullshark без тайм-ауту голосування без тайм-ауту голосування, Baseline Bullshark — це версія без тайм-ауту.
На графіку нижче порівнюється вплив тайм-аутів на затримку Bullshark зі збоями та без них. Очевидно, Baseline Bullshark (без тайм-ауту) найкраще працює у разі збою. Без збоїв Baseline Bullshark можна порівняти з Vanilla Bullshark без призупинення голосування. Це тому, що, як згадувалося раніше, без механізму репутації лідера тайм-аути можуть мати перевагу в ситуаціях, коли лідер хороший, але повільний.
Малюнок 6.: Вплив тайм-аутів на затримку Bullshark без збоїв (ліворуч) і зі збоями (праворуч), із 50 валідаторами у випадку збою
Далі ми створюємо екземпляр Shoal за допомогою Baseline Bullshark (без тайм-ауту) і демонструємо покращення затримки конвеєрної обробки та механізму репутації лідера зі збоями та без них, а для повноти ми також порівнюємо його з Jolteon із порівнянням збоїв та без них.
На малюнку 7 нижче показано безвідмовний випадок, і, хоча і конвеєр, і репутація лідера можуть зменшити затримку окремо, їх поєднання призводить до найкращої затримки.
Що стосується Jolteon, то він не може масштабуватися до більш ніж 20 валідаторів, і навіть якщо він працює в Quorum Store, він може досягти приблизно половини пропускної здатності Bullshark/Shoal, що усуває вузьке місце розповсюдження даних.
Результати показують, що Shoal значно покращує затримку Bullshark. Що стосується Jolteon, важливо зазначити, що хоча ми вимірювали лише затримку консенсусу. Оскільки Jolteon не може працювати нативно поверх DAG, йому потрібна додаткова затримка, щоб відокремити розповсюдження даних, яку ми не вимірювали. Тому за високого навантаження Shoal має відповідати наскрізній затримці Jolteon.
Малюнок 7: Пропускна здатність і затримка без збоїв, Shoal PL і Shaol LR підтримують лише конвеєрну роботу та репутацію лідера відповідно.
На рисунку 8 нижче показаний випадок невдачі з 50 валідаторами, де механізм репутації лідера значно покращує затримку, зменшуючи ймовірність того, що невдалий валідатор буде обраний лідером. Зауважте, що з 16 невдачами з 50, затримка Shoal була на 65% нижчою, ніж Baseline Bullshark.
Переглянути оригінал
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
Пояснення 4D Shoal Framework: як зменшити затримку Bullshark на Aptos?
Оригінал: Aptos Labs
Компіляція: Aptos Global
Огляд
Aptos labs вирішила дві важливі відкриті проблеми в DAG BFT, значно зменшивши затримку та вперше усунувши потребу в паузах у детермінованих практичних протоколах. Загалом це покращує затримку Bullshark на 40% у випадку відсутності збоїв і на 80% у випадку збою.
Shoal — це структура, яка покращує будь-який консенсусний протокол на основі Narwhal (наприклад, DAG-Rider, Tusk, Bullshark) за допомогою конвеєрної обробки та репутації лідера. Конвеєрна підготовка зменшує затримку впорядкування DAG, вводячи прив’язку на раунд, а репутація лідера додатково покращує затримку, гарантуючи, що прив’язки пов’язані з найшвидшими валідаторами. Крім того, репутація лідера дозволяє Shoal використовувати асинхронну конструкцію DAG для усунення тайм-аутів у всіх сценаріях. Це дозволяє Shoal надати властивість, яку ми назвали Universal Response, яка містить оптимістичну відповідь, яка зазвичай потрібна.
Наша техніка дуже проста, вона передбачає послідовне виконання кількох екземплярів основного протоколу один за одним. Таким чином, якщо створити екземпляр за допомогою Bullshark, ми отримаємо групу «акул», які беруть участь в естафеті.
Мотивація
У гонитві за високою продуктивністю в блокчейн-мережах постійна увага приділяється зменшенню складності зв’язку. Однак такий підхід не призвів до істотного збільшення пропускної здатності. Наприклад, реалізація Hotstuff у ранній версії Diem досягла лише 3500 TPS, що набагато нижче нашої мети досягти 100k+ TPS.
Однак нещодавні прориви пов’язані з усвідомленням того, що розповсюдження даних є головним вузьким місцем протоколів на основі лідерів і що воно може виграти від розпаралелювання. Система Narwhal відокремлює розповсюдження даних від основної консенсусної логіки та пропонує архітектуру, де всі валідатори поширюють дані одночасно, тоді як консенсусні компоненти впорядковують лише меншу кількість метаданих. Газета Narwhal повідомляє про продуктивність 160 000 TPS.
У попередній статті ми представили Quorum Store. Наша реалізація Narwhal відокремлює розповсюдження даних від консенсусу, і як ми використовуємо це для розширення нашого поточного протоколу консенсусу Jolteon. Jolteon — це провідний протокол, який поєднує швидкий лінійний шлях Tendermint зі змінами перегляду в стилі PBFT, щоб зменшити затримку Hotstuff на 33%. Однак очевидно, що консенсусний протокол на основі лідера не може повністю використати пропускну здатність Narwhal. Незважаючи на відокремлення розповсюдження даних від консенсусу, лідери Hotstuff/Jolteon все ще обмежені, оскільки пропускна здатність зростає.
Тому ми вирішили розгорнути Bullshark, консенсусний протокол із нульовими витратами на зв’язок, поверх Narwhal DAG. На жаль, структура DAG, яка підтримує високу пропускну здатність Bullshark, має 50% штраф за затримку порівняно з Jolteon.
У цій публікації ми описуємо, як Shoal досяг значного скорочення затримки Bullshark.
Фон DAG-BFT
Давайте почнемо з розуміння відповідної передісторії цієї статті. Щоб отримати детальний опис Narwhal і Bullshark, зверніться до публікації DAG зустрічає BFT.
Кожна вершина в DAG Narwhal пов’язана з круглим числом. Щоб увійти в раунд r, верифікатор повинен спочатку отримати nf вершин, що належать раунду r-1. Кожен верифікатор може транслювати одну вершину за раунд, і кожна вершина посилається принаймні на nf вершин у попередньому раунді. Через асинхронність мережі різні валідатори можуть спостерігати різні локальні перегляди DAG у будь-який момент часу. Ось ілюстрація можливого часткового перегляду:
Рисунок 1: Причинно-наслідкова історія вершин, визначених у раунді 2 перевірки, вузол 2 виділено зеленим кольором
Ключовою властивістю DAG є відсутність двозначності: два валідатори мають однакову причинно-наслідкову історію v, якщо вони мають однакову вершину v у своєму локальному представленні DAG.
Загальне замовлення
Можна узгодити загальний порядок усіх вершин у DAG без додаткових витрат на зв’язок. З цією метою валідатори в DAG-Rider, Tusk і Bullshark інтерпретують структуру DAG як консенсусний протокол, де вершини представляють пропозиції, а ребра представляють голоси.
Хоча логіка групового перетину відрізняється від структури DAG, усі існуючі консенсусні протоколи на основі Narwhal мають таку структуру:
Заздалегідь визначені якорі, буде заздалегідь визначений лідер кожні кілька раундів (наприклад, два раунди в Bullshark), а вершини лідера називаються якорями;
Упорядковуючи прив’язки, верифікатор незалежно, але детерміновано вирішує, які прив’язки замовляти, а які пропустити;
Порядок причинно-наслідкових історій, де валідатори обробляють свій упорядкований список прив’язок один за одним, і для кожного прив’язки сортують усі попередньо невпорядковані вершини в його причинно-наслідковій історії за якимось детермінованим правилом.
Рисунок 2: Ілюстрація можливого часткового вигляду DAG у протоколі Bullshark. У цьому прикладі червоні та жовті прив’язки сортуються, тоді як зелені (не в DAG) пропускаються. Тому, щоб упорядкувати DAG, валідатори спочатку детерміновано впорядковують історії причин червоних прив’язок, а потім жовтих прив’язок.
Ключ до забезпечення безпеки полягає в тому, щоб на кроці (2) вище всі чесні валідатори створили впорядкований список прив’язок, щоб усі списки мали однаковий префікс. У Shoal ми робимо такі зауваження щодо всіх наведених вище протоколів:
** Усі валідатори погоджуються щодо першого замовленого прив’язки. **
Затримка Bullshark
Затримка Bullshark залежить від кількості раундів між упорядкованими якорями в DAG. Хоча найбільш корисна частково синхронна версія Bullshark має кращу затримку, ніж асинхронна версія, вона далека від оптимальної.
Проблема 1: Середня затримка блоку. У Bullshark кожен парний раунд має якір, а вершини кожного непарного раунду інтерпретуються як голоси. Як правило, потрібно два раунди DAG, щоб упорядкувати прив’язки, однак вершини в причинно-наслідковій історії прив’язки потребують набагато більше раундів, щоб очікувати впорядкування прив’язки. У звичайному випадку вершини в непарних раундах вимагають трьох раундів, тоді як вершини без прив’язки в парних раундах вимагають чотирьох раундів (див. Малюнок 3).
Рисунок 3: У звичайному випадку прив’язки в раунді i+1 потрібно відсортувати для двох раундів. Вершини в раунді i сортуються одночасно, тому їх затримка становить три раунди. Однак вершини в раунді i+1 повинні чекати на сортування наступного прив’язки (той, що в раунді i+3), тому їхня затримка сортування становить чотири раунди.
Проблема 2: Затримка у випадку невдачі, наведений вище аналіз затримки застосовується до випадку без невдачі, з іншого боку, якщо лідер раунду не в змозі транслювати прив’язки досить швидко, прив’язки не можуть бути впорядковані (і, отже, пропускаються), тому всі невідсортовані вершини в попередніх раундах повинні чекати на сортування наступного прив’язки. Це може значно знизити продуктивність геореплікованої мережі, особливо тому, що Bullshark використовує тайм-аути в очікуванні лідера.
Рамка мілини
Shoal вирішує обидві ці проблеми із затримкою, покращуючи Bullshark (або будь-який інший протокол BFT на основі Narwhal) за допомогою конвеєрної обробки, дозволяючи прив’язку в кожному раунді та зменшуючи затримку всіх неприв’язаних вершин у DAG до трьох раундів. Shoal також впроваджує механізм репутації лідера без накладних витрат у DAG, який зміщує вибір на користь швидких лідерів.
виклик
У контексті протоколів DAG конвеєрне забезпечення та репутація лідера вважаються складними проблемами з таких причин:
Попередні конвеєрні спроби змінити основну логіку Bullshark, але це здається неможливим за своєю суттю
Репутація лідера, введена в DiemBFT і формалізована в Carousel, — це ідея динамічного вибору майбутніх лідерів (якорів у Bullshark) на основі минулої продуктивності валідаторів. Хоча розбіжності щодо ідентичності лідера не порушують безпеку в цих протоколах, у Bullshark це може призвести до зовсім іншого порядку, що потрапляє в суть питання, яке полягає в тому, що динамічний і детермінований вибір колісних якорів є рішенням для досягнення консенсусу, тоді як валідаторам потрібно узгодити впорядковану історію, щоб вибрати майбутні прив’язки.
Як доказ складності проблеми ми зауважимо, що реалізація Bullshark, включаючи поточну реалізацію у виробництві, не підтримує ці функції.
Угода
Незважаючи на вищезазначені проблеми, виявляється, що рішення, як то кажуть, ховаються за простотою.
У Shoal ми покладаємося на здатність виконувати локальні обчислення на DAG і реалізуємо здатність зберігати та переосмислювати інформацію з попередніх раундів. Маючи основне розуміння того, що всі валідатори погоджуються щодо першого впорядкованого прив’язки, Shoal конвеєрує їх, створюючи кілька екземплярів Bullshark так, щоб (1) перший упорядкований прив’язка була точкою перемикання для примірників, і (2) причинно-наслідкова історія якір використовується для розрахунку репутації лідера.
Конвеєрна розробка
Подібно до Bullshark, валідатори апріорі узгоджують потенційні прив’язки, тобто існує відоме відображення F: R -> V відображення раундів до лідерів. Shoal запускає екземпляри Bullshark один за одним таким чином, що для кожного екземпляра прив’язка заздалегідь визначена картою F. Кожен екземпляр замовляє якір, який запускає перехід до наступного екземпляра.
Спочатку Shoal запускає перший екземпляр Bullshark у першому раунді DAG і запускає його, доки не буде ідентифіковано перший впорядкований якір, скажімо, у раунді r. Усі валідатори згодні з цим прив’язкою. Таким чином, усі валідатори можуть детерміновано домовитися про те, щоб повторно інтерпретувати DAG, починаючи з раунду r+1. Шол щойно починає новий екземпляр Bullshark у раунді r+1.
У найкращому випадку це дозволяє Шоалу замовляти якір кожного раунду. Якір для першого раунду сортується за першим зразком. Потім Шол запускає новий екземпляр у другому раунді, який сам має якір, замовлений екземпляром, потім інший новий екземпляр замовляє якір у третьому раунді, і процес продовжується. Будь ласка, перегляньте ілюстрацію нижче:
Рисунок 4: Вершини, що відповідають лідерам, визначеним F, позначені короною.Перший екземпляр Bullshark спочатку інтерпретує DAG з якорями в раундах 1, 3 і 5. Bullshark визначає якорі в раунді 1 (зелена галочка mark) є першим, який сортується в першому випадку. (Зауважте, що в загальному випадку цей якір можна пропустити, тоді як деякі інші якорі будуть відсортовані першими.) Потім решта першого екземпляра ігнорується, а новий екземпляр Bullshark починається з раунду 2, точки прив’язки позначаються. у 2 і 4 раундах.
Репутація лідера
Збільшена затримка під час пропуску прив’язок під час сортування Bullshark. У цьому випадку техніка конвеєрної обробки безсила, оскільки новий екземпляр не може бути запущений, доки попередній екземпляр не замовить прив’язку. Shoal гарантує, що відповідний лідер з меншою ймовірністю буде обраний у майбутньому, щоб мати справу з втраченим якорем, використовуючи механізм репутації, щоб призначити кожному валідатору бал на основі його історії останніх дій. Валідатор, який відповідає та бере участь у протоколі, отримає високу оцінку, інакше валідатору буде присвоєно низький бал, оскільки він може вийти з ладу, бути повільним або шкідливим.
Ідея полягає в тому, щоб детерміновано повторно обчислювати попередньо визначене відображення F від раундів до лідерів при кожному оновленні балів, віддаючи перевагу лідерам з вищими балами. Для того, щоб валідатори погодилися щодо нового відображення, вони повинні узгодити оцінку і, отже, історію, використану для отримання оцінки.
У Shoal конвеєрну репутацію та репутацію лідера можна природно поєднати, оскільки обидва вони використовують ту саму основну техніку переосмислення DAG після узгодження першого впорядкованого якоря.
Фактично, єдина відмінність полягає в тому, що після сортування прив’язок у раунді r валідатору потрібно лише обчислити нове відображення F' із раунду r+1 на основі історії причин упорядкованих прив’язок у раунді r. Потім валідатор виконує новий екземпляр Bullshark, починаючи з раунду r+1, використовуючи оновлену функцію вибору прив’язки F'. Дивіться зображення нижче:
Рисунок 5. Вершини, що відповідають лідерам, позначеним F, позначені прозорими коронами. Перший екземпляр Bullshark замовляє якір у раунді 1, позначений зеленою галочкою, а потім обчислює нове відображення F' на основі інформації в причинно-наслідковій історії прив’язки. Лідери, визначені F', позначені кольоровими коронами.
Більше ніяких тайм-аутів
Тайм-аути відіграють вирішальну роль у всіх детермінованих частково синхронних реалізаціях BFT на основі лідера. Однак складність, яку вони вводять, збільшує кількість внутрішнього стану, яким потрібно керувати та спостерігати, що ускладнює процес налагодження та вимагає додаткових методів спостереження.
Тайм-аути також можуть значно збільшити затримку, оскільки їх важливо правильно налаштувати, і зазвичай їх потрібно регулювати динамічно, оскільки це сильно залежить від середовища (мережі). Протокол сплачує несправному лідеру повний штраф за затримку тайм-ауту перед переходом до наступного лідера. Тому параметр тайм-ауту не може бути надто консервативним, але якщо тайм-аут занадто короткий, протокол може пропустити хороших лідерів. Наприклад, ми помітили, що під високим навантаженням лідери в Jolteon/Hotstuff були перевантажені, і тайм-аути минали, перш ніж вони змогли підвищити прогрес.
На жаль, протоколи на основі лідерів, такі як Hotstuff і Jolteon, за своєю суттю вимагають тайм-аутів, щоб гарантувати, що протокол може прогресувати щоразу, коли лідер виходить з ладу. Без тайм-ауту навіть лідер, що впав, може призупинити протокол назавжди. Через неможливість відрізнити несправний лідер від повільного лідера під час асинхронізації, тайм-аути можуть призвести до того, що валідатори бачать зміни всіх лідерів без консенсусної жвавості.
У Bullshark тайм-аути використовуються в побудові DAG, щоб гарантувати, що під час синхронізації чесний лідер додає прив’язки до DAG досить швидко, щоб їх можна було впорядкувати.
Ми спостерігаємо, що конструкція DAG забезпечує «годинник» для оцінки швидкості мережі. За відсутності пауз раунди продовжують просуватися до тих пір, поки nf чесних валідаторів продовжують додавати вершини до DAG. Хоча Bullshark може не мати змоги сортувати на швидкості мережі (через проблемні лідери), DAG все ще зростає на швидкості мережі, незважаючи на деякі проблеми з лідером або асинхронність мережі. Згодом, коли безпомилковий лідер транслює ведучі досить швидко, уся причинно-наслідкова історія ведучих буде впорядкована.
У нашій оцінці ми порівнювали Bullshark із тайм-аутом і без нього в таких випадках:
Швидкий лідер, тобто принаймні швидше, ніж інші валідатори. У цьому випадку обидва методи забезпечують однакову затримку, оскільки прив’язки впорядковуються, а тайм-аути не використовуються.
Помилковий лідер, у цьому випадку Bullshark без пауз забезпечує кращу затримку, оскільки валідатори негайно пропускають свої прив’язки, тоді як валідатори з паузами чекатимуть їх прибуття, перш ніж продовжити Expect.
Повільний лідер, це єдиний випадок, коли Bullshark має кращу продуктивність тайм-ауту. Це пояснюється тим, що без паузи прив’язка може бути пропущена, оскільки ведучий не може транслювати її достатньо швидко, тоді як з паузою валідатори чекатимуть прив’язки.
У Shoal уникання тайм-аутів і лідерська репутація йдуть рука об руку. Повторне очікування повільного лідера збільшує затримку, а механізм репутації лідера запобігає обранню повільних валідаторів лідерами. Таким чином, система використовує вузли швидкої перевірки для роботи на швидкості мережі в усіх сценаріях реального світу.
Зверніть увагу, що результат неможливості FLP показує, що жоден детермінований консенсусний протокол не може уникнути тайм-аутів. Шол не може обійти цей результат, оскільки існує теоретичний розклад змагальних подій, які перешкоджають керуванню всіма якорями. Натомість Shoal повертається до тайм-ауту після настроюваної кількості послідовних пропусків прив’язки. На практиці це вкрай малоймовірно.
Загальна відповідь
Стаття Hotstuff популяризувала концепцію оптимістичної відповіді, яка, хоча формально не визначена, інтуїтивно означає, що протокол може працювати на швидкості мережі за хороших умов, включаючи швидкий лідер і синхронну мережу.
Shoal забезпечує ще кращу властивість, яку ми називаємо Universal Response. Зокрема, на відміну від Hotstuff, Shoal продовжує працювати на швидкості мережі, навіть якщо лідер виходить з ладу протягом заданої кількості послідовних раундів або асинхронних циклів, через які проходить мережа. Дивіться більш детальне порівняння в таблиці нижче.
Зауважте, що універсальна чутливість забезпечує чітко кращі гарантії прогресу під час асинхронних періодів і коли лідер зазнає невдачі. Під час синхронізації з повільним лідером ці властивості не можна порівнювати, оскільки це залежить від того, наскільки повільним є лідер. Однак, враховуючи репутацію лідера, повільні лідери повинні рідко з'являтися в Шол.
Оцініть
Ми реалізували Bullshark і Shoal поверх нашої реалізації Narwhal Quorum Store. Детальне порівняння між Shoal, Bullshark і Jolteon можна знайти в розділі оцінки статті Shoal, де ми надаємо деякі основні моменти.
По-перше, щоб продемонструвати силу асинхронної конструкції DAG, ми порівнюємо Bullshark із паузами та без них. Повний документ Bullshark передбачає асинхронну мережу, але забезпечує швидкий режим, що вимагає пауз під час усіх раундів. Ми називаємо цю версію Vanilla Bullshark. Ми спостерігаємо, що для гіпотетичних версій незалежної частково синхронної мережі не потрібні паузи в раундах голосування. Ми називаємо цю версію Vanilla Bullshark без тайм-ауту голосування без тайм-ауту голосування, Baseline Bullshark — це версія без тайм-ауту.
На графіку нижче порівнюється вплив тайм-аутів на затримку Bullshark зі збоями та без них. Очевидно, Baseline Bullshark (без тайм-ауту) найкраще працює у разі збою. Без збоїв Baseline Bullshark можна порівняти з Vanilla Bullshark без призупинення голосування. Це тому, що, як згадувалося раніше, без механізму репутації лідера тайм-аути можуть мати перевагу в ситуаціях, коли лідер хороший, але повільний.
Малюнок 6.: Вплив тайм-аутів на затримку Bullshark без збоїв (ліворуч) і зі збоями (праворуч), із 50 валідаторами у випадку збою
Далі ми створюємо екземпляр Shoal за допомогою Baseline Bullshark (без тайм-ауту) і демонструємо покращення затримки конвеєрної обробки та механізму репутації лідера зі збоями та без них, а для повноти ми також порівнюємо його з Jolteon із порівнянням збоїв та без них.
На малюнку 7 нижче показано безвідмовний випадок, і, хоча і конвеєр, і репутація лідера можуть зменшити затримку окремо, їх поєднання призводить до найкращої затримки.
Що стосується Jolteon, то він не може масштабуватися до більш ніж 20 валідаторів, і навіть якщо він працює в Quorum Store, він може досягти приблизно половини пропускної здатності Bullshark/Shoal, що усуває вузьке місце розповсюдження даних.
Результати показують, що Shoal значно покращує затримку Bullshark. Що стосується Jolteon, важливо зазначити, що хоча ми вимірювали лише затримку консенсусу. Оскільки Jolteon не може працювати нативно поверх DAG, йому потрібна додаткова затримка, щоб відокремити розповсюдження даних, яку ми не вимірювали. Тому за високого навантаження Shoal має відповідати наскрізній затримці Jolteon.
Малюнок 7: Пропускна здатність і затримка без збоїв, Shoal PL і Shaol LR підтримують лише конвеєрну роботу та репутацію лідера відповідно.
На рисунку 8 нижче показаний випадок невдачі з 50 валідаторами, де механізм репутації лідера значно покращує затримку, зменшуючи ймовірність того, що невдалий валідатор буде обраний лідером. Зауважте, що з 16 невдачами з 50, затримка Shoal була на 65% нижчою, ніж Baseline Bullshark.