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, консенсусний протокол з нульовими витратами на комунікацію. На жаль, структура DAG, що підтримує високу пропускну здатність Bullshark, має 50% затримки витрат.

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

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

Фон DAG-BFT

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

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

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

Bullshark затримка

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

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

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

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

Протокол

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

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

Конвеєр

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

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

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

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

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

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

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

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

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

![Великі деталі про фреймворк Shoal: Як зменшити затримку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-1baf540693f376d93cb18ef3193593cc.webp(

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

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

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