Аналіз рамки Shoal: значне падіння затримки Bullshark на Aptos

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

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

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

Фон та мотивація

При досягненні високої продуктивності блокчейн-мережі, Падіння складності комунікації завжди було в центрі уваги. Однак цей підхід не приніс значного підвищення пропускної здатності. Наприклад, раніше реалізований у Diem Hotstuff досяг лише 3500 TPS, що значно нижче цільового показника 100 000+ TPS.

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

Aptos раніше представив Quorum Store, а саме реалізацію Narwhal, яка відокремлює розповсюдження даних від консенсусу, щоб розширити поточний протокол консенсусу Jolteon. Jolteon поєднує лінійний швидкий шлях Tendermint і зміни візу PBFT, що дозволяє зменшити затримку Hotstuff на 33%. Проте, консенсусний протокол на основі лідера не може у повній мірі використовувати потенціал пропускної спроможності Narwhal.

Тому Aptos вирішив розгорнути Bullshark, протокол консенсусу з нульовими витратами на зв'язок, на основі Narwhal DAG. Проте, у порівнянні з Jolteon, DAG-структура, що підтримує Bullshark з високою пропускною здатністю, має 50% падіння.

Shoal框架 призначений для значного Падіння затримки Bullshark.

Фон 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-f6b6281c928e3fa7a2412a480c9c1806.webp)

Загальна послідовність

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

Усі консенсусні протоколи на основі Narwhal мають таку структуру:

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

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

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

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

Bullshark затримка

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

Основні проблеми:

1. Середня затримка блоку: У звичайних випадках, вершина непарного раунду потребує трьох раундів, а вершина парного раунду без прив'язки потребує чотирьох раундів для сортування.

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

! [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 у поточному виробничому середовищі не підтримують ці функції.

) Протокол

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

1. Першою впорядкованою точкою якоря є точка переключення екземпляра
2. Історія причинно-наслідкових зв'язків якоря використовується для обчислення репутації лідера

Конвеєр

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

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

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

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

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

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

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

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

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

Усунення затримки

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

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

На жаль, протоколи, засновані на лідерах, такі як Hotstuff і Jolteon ), по суті, потребують затримки, щоб забезпечити прогрес протоколу кожного разу, коли лідер виходить з ладу. Без затримки навіть зламаний лідер може назавжди зупинити протокол. Оскільки під час асинхронного періоду неможливо відрізнити зламаного та повільного лідера, затримка може призвести до того, що вузли верифікації будуть обмінювати всіх лідерів без активності консенсусу.

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

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

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

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

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

( Загальна чутливість

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

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

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

Оцінка

Aptos реалізував Bullshark і Shoal на Quorum Store, реалізованому в Narwhal. Нижче наведено деякі ключові моменти оцінки:

По-перше, для виступу