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 - реалізацію 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 не є неоднозначною: якщо два вузли верифікації мають однакову вершину 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 фрейм

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

Виклик

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

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

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

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

Угода

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

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

Конвеєр

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 раунду. Потім валідаторні вузли починають виконувати новий екземпляр Bullshark з оновленою функцією вибору якорів F' з r+1 раунду.

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

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

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