Shoal框架:як зменшити затримку Bullshark на Aptos?

Огляд

Aptos labs вирішила дві важливі відкриті проблеми в DAG BFT, суттєво Падіння затримки та вперше усунула потребу в таймаутах у детермінаційних реальних протоколах. Загалом, у випадку безвідмовної роботи затримка Bullshark покращилась на 40%, а в умовах відмови – на 80%.

Shoal є платформою, яка підсилює протокол консенсусу на базі Narwhal ( за допомогою конвеєра та репутації лідера, як-от DAG-Rider, Tusk, Bullshark ). Конвеєр зменшує затримку сортування DAG, вводячи анкор у кожному раунді, а репутація лідера подальшою покращує проблему затримки, забезпечуючи асоціацію анкорів з найбільш швидкими вузлами верифікації. Крім того, репутація лідера дозволяє Shoal використовувати асинхронну побудову DAG для усунення тайм-аутів у всіх сценаріях. Це дозволяє Shoal пропонувати властивість, відому як загальна реакція, яка містить зазвичай необхідну оптимістичну реакцію.

Ця технологія дуже проста, вона передбачає послідовне виконання кількох екземплярів базового протоколу. Тому, коли ми інстанціюємо Bullshark, ми отримуємо групу "акул", які беруть участь у естафеті.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ](https://img-cdn.gateio.im/webp-social/moments-8d6acd885bad7b8f911bdce15a7c884f.webp)

Мотивація

У процесі прагнення до високої продуктивності блокчейн-мережі люди завжди звертали увагу на Падіння складності комунікації. Проте цей підхід не призвів до значного збільшення пропускної здатності. Наприклад, 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, це протокол консенсусу з нульовими витратами на зв'язок. На жаль, у порівнянні з Jolteon, структура DAG, яка підтримує високу пропускну здатність Bullshark, має 50% Падіння.

У цій статті розглядається, як Shoal реалізує значне зменшення затримки Bullshark.

Фон DAG-BFT

Кожна вершина в Narwhal DAG асоціюється з певним раундом. Щоб увійти в раунд r, валідатор спочатку повинен отримати n-f вершин, що належать до раунду r-1. Кожен валідатор може транслювати одну вершину за раунд, причому кожна вершина повинна принаймні посилатися на n-f вершин з попереднього раунду. Через асинхронність мережі різні валідатори можуть у будь-який момент часу спостерігати різні локальні уявлення DAG.

Ключовою властивістю DAG є відсутність двозначності: якщо два вузли перевірки мають однакову вершинy v у своїх локальних уявленнях про DAG, то вони мають абсолютно ідентичну причинно-історичну структуру v.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ](https://img-cdn.gateio.im/webp-social/moments-f6b6281c928e3fa7a2412a480c9c1806.webp)

Загальний рейтинг

Можна досягти узгодженості загального порядку всіх вершин у DAG без додаткових витрат на зв'язок. Для цього валідатори в DAG-Rider, Tusk та Bullshark інтерпретують структуру DAG як консенсусний протокол, в якому вершини представляють пропозиції, а ребра представляють голосування.

Хоча логіка групового перетину в структурі DAG відрізняється, всі існуючі консенсусні протоколи на основі Narwhal мають таку структуру:

1. Запланована точка прив'язки: кожні кілька раундів (, наприклад, у Bullshark через два раунди ) буде заздалегідь визначений лідер, вершина якого називається точкою прив'язки;

2. Точки прив'язки: валідатори незалежно, але детерміновано вирішують, які точки прив'язки замовити, а які пропустити;

3. Порядок причинно-наслідкової історії: валідатори один за одним обробляють свої впорядковані списки якорів, і для кожного якоря, за допомогою деяких детермінованих правил, впорядковують всі попередні невпорядковані вершини в його причинно-наслідковій історії.

Ключем досягнення безпеки є забезпечення того, щоб на етапі (2) всі чесні вузли верифікації створили упорядкований список якорів, щоб всі списки ділилися одним і тим же префіксом. У Shoal ми робимо такі спостереження щодо всіх вищезазначених протоколів:

Усі валідатори погоджуються з першим упорядкованим якорем.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ](https://img-cdn.gateio.im/webp-social/moments-b7ed8888da112bae8d34c0fdb338b138.webp)

Bullshark затримка

Затримка Bullshark залежить від кількості обертів між впорядкованими анкерами в DAG. Хоча часткова синхронізація Bullshark є більш практичною, ніж асинхронна версія, вона все ще далека від оптимальної.

Питання 1: середній час затримки блоку. У Bullshark кожен парний раунд має анкор, а вершини непарного раунду трактуються як голосування. У звичайних випадках потрібно два раунди DAG, щоб замовити анкори, однак вершини в причинно-історичному контексті анкера потребують більше раундів для очікування, поки анкор буде відсортовано. У звичайних випадках вершини в непарному раунді потребують трьох раундів, а вершини неанкорів в парному раунді потребують чотирьох раундів.

Проблема 2: затримка випадків відмови, наведений аналіз затримки застосовується до безвідмовних ситуацій, з іншого боку, якщо лідер раунду не встигає достатньо швидко транслювати якорі, то неможливо впорядкувати якорі (, тому вони пропускаються ), отже, всі непорядковані вершини в перших раундах повинні чекати, поки наступний якорь буде впорядковано. Це суттєво знижує продуктивність географічної реплікаційної мережі, особливо через те, що таймаут Bullshark використовується для очікування лідера.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ](https://img-cdn.gateio.im/webp-social/moments-46d37add0d9e81b2f295edf8eddd907f.webp)

Shoal фрейм

Shoal вирішив ці дві затримки, він через конвеєр покращив Bullshark( або будь-який інший BFT-протокол на основі Narwhal), дозволяючи в кожному раунді мати одну опору, і зменшив затримку всіх неякірних вершин у DAG до трьох раундів. Shoal також впровадив у DAG механізм репутації лідера без витрат, що дозволяє вибір на користь швидких лідерів.

Виклик

У контексті протоколу DAG, конвеєри та репутація лідерів вважаються складними питаннями, з таких причин:

1. Раніше конвеєри намагалися змінити основну логіку Bullshark, але це, по суті, здається неможливим.

2. Репутація лідера була введена в DiemBFT і офіційно закріплена в Carousel, що є динамічним вибором майбутніх лідерів на основі минулих показників валідаторів, ідея якого полягає в якорі в Bullshark (. Хоча розбіжності в статусі лідера не порушують безпеку цих протоколів, у Bullshark це може призвести до зовсім іншого порядку, що піднімає основне питання, а саме, що динамічний і детермінований вибір ротаційного якоря є необхідним для вирішення консенсусу, при цьому валідатори повинні досягти згоди щодо впорядкованої історії для вибору майбутнього якоря.

Як доказ складності проблеми, ми звертаємо увагу на реалізацію Bullshark, яка наразі не підтримує ці функції у виробничому середовищі.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ])https://img-cdn.gateio.im/webp-social/moments-0b0928cb6240e994c1514c75e080a4b2.webp(

Протокол

Незважаючи на вищезгадані виклики, як кажуть, рішення, як правило, приховане в простоті.

У Shoal ми покладаємось на здатність виконувати локальні обчислення на DAG та реалізуємо можливість зберігати та повторно інтерпретувати інформацію з попередніх раундів. Завдяки тому, що всі валідатори погоджуються з першим впорядкованим якорем, основна ідея полягає в тому, що Shoal послідовно комбінує кілька екземплярів Bullshark для їх конвеєрної обробки, що робить )1( перше впорядковане якорем точкою перемикання екземплярів, а також )2( історія причинності якоря використовується для обчислення репутації лідера.

Конвеєр

V, яке відображає раунди на лідера. Shoal по черзі запускає екземпляри Bullshark, так що для кожного екземпляра якір заздалегідь визначений відображенням F. Кожен екземпляр замовляє якір, що викликає переключення на наступний екземпляр.

Спочатку Shoal запустив перший екземпляр Bullshark на першому раунді DAG і працював з ним до визначення першої впорядкованої опори, наприклад, на раунді r. Усі валідатори погодилися з цією опорою. Таким чином, усі валідатори можуть впевнено погодитися на повторну інтерпретацію DAG, починаючи з раунду r+1. Shoal просто запустив новий екземпляр Bullshark на раунді r+1.

У найкращих умовах це дозволяє Shoal замовляти якорі в кожному раунді. Перший раунд якорів сортується за першим екземпляром. Потім Shoal розпочинає новий екземпляр у другому раунді, у якого сам є якір, що сортується за цим екземпляром, а потім ще один новий екземпляр замовляє якорі в третьому раунді, і цей процес триває.

! [10 000 слів, що пояснюють рамки Shoal: як зменшити затримку Bullshark на Aptos?] ])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(

Репутація лідера

При пропуску анкерних точок під час сортування Bullshark, затримка збільшується. У цьому випадку технологія конвеєра безсила, оскільки новий екземпляр не може бути запущений до того, як буде замовлена попередня анкерна точка. Shoal забезпечує, щоб відповідний лідер для обробки втрачених анкерних точок був менш імовірним у майбутньому, використовуючи механізм репутації для надання кожному валідаційного вузла балу на основі історії нещодавньої активності кожного валідаційного вузла. Валідаційні вузли, які відповідають і беруть участь у протоколі, отримають високі бали, в іншому випадку валідаційні вузли отримають низькі бали, оскільки вони можуть бути зламані, повільні або зловмисні.

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

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

Фактично, єдина різниця полягає в тому, що після сортування анкорів у r-му раунді, валідатору потрібно лише на основі причинно-історичного зв'язку впорядкованих анкорів у r-му раунді почати обчислення нового відображення F' з r+1 раунду. Потім, з r+1 раунду, валідатор використовує оновлену функцію вибору анкорів F' для виконання нового екземпляра Bullshark.

![Тисячослівний аналіз рамки Shoal: як зменшити затримку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(

Немає більше тайм-аутів

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

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