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, що значно нижче нашої мети у 100000+ TPS.

Але недавній прорив зумовлений усвідомленням того, що поширення даних є основним вузьким місцем на базі протоколу лідерів, і може виграти від паралелізації. Система Narwhal відокремлює поширення даних від основної логіки консенсусу, пропонуючи архітектуру, в якій усі валідатори одночасно поширюють дані, а компоненти консенсусу лише впорядковують невелику кількість метаданих. У документі Narwhal повідомляється про пропускну здатність 160000 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 та Bullshark, будь ласка, зверніться до статті DAG meets 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-f6b6281c928e3fa7a2412a480c9c1806.webp)

Повний порядок

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

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

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

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

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

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

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

Bullshark затримка

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

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

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

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

Shoal рамка

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

Виклик

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

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

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

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

) угода

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

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

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

) Обробка конвеєра

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-0b0928cb6240e994c1514c75e080a4b2.webp)

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

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

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

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

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

Немає більше затримок

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

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