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

Огляд

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

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

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

Мотивація

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

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

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

Отже, на Narwhal DAG було розгорнуто Bullshark, протокол консенсусу з нульовими витратами на зв'язок. На жаль, порівняно з Jolteon, DAG-структура, що підтримує високий пропуск Bullshark, має 50% затримки витрат.

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

Фон DAG-BFT

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

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

Загальний порядок

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

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

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

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

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

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

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

Bullshark затримка

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

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

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

Косяки

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

Виклик

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

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

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

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

Протокол

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

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

Конвеєр

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

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

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

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

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

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

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

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

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

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

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

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

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