Shoal框架:оптимизация задержки соглашения Bullshark на Aptos

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

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

Технология 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.

Aptos ранее представил Quorum Store, то есть реализацию Narwhal, которая отделяет распространение данных от Соглашения, а также то, как использовать его для масштабирования текущего протокола Соглашения Jolteon. Jolteon — это протокол на основе лидера, который сочетает в себе линейный быстрый путь Tendermint и изменения вида в стиле PBFT, что позволяет снизить задержку Hotstuff на 33%. Однако очевидно, что Соглашение на основе лидера не может в полной мере использовать потенциал пропускной способности Narwhal. Несмотря на разделение распространения данных и Соглашения, с увеличением пропускной способности лидеры Hotstuff/Jolteon все еще ограничены.

Поэтому Aptos решил развернуть Bullshark над Narwhal DAG, протокол согласия с нулевыми затратами на связь. К сожалению, по сравнению с Jolteon, структура DAG, поддерживающая высокую пропускную способность Bullshark, приводит к 50% задержке.

! [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 сделаны следующие наблюдения по всем вышеупомянутым протоколам: все валидаторы согласны с первой упорядоченной якорной точкой.

Bullshark задержка

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

Существует две основные проблемы:

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

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

! [10 000 слов, объясняющих структуру Shoal: как уменьшить задержку Bullshark на Aptos?] ](https://img-cdn.gateio.im/webp-social/moments-46d37add0d9e81b2f295edf8eddd907f.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. Все валидаторы согласны с этой опорой. Таким образом, все валидаторы могут с уверенностью согласиться на переинтерпретацию 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)-го раунда. Затем узлы валидации начинают использовать обновленную функцию выбора опорных точек F' для выполнения нового экземпляра Bullshark, начиная с (r+1)-го раунда.

! [10 000 слов, объясняющих структуру Shoal: как уменьшить задержку Bullshark на Aptos?] ]###https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(

) Не требуется задержка

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

Время ожидания также значительно увеличит задержку, так как важно правильно их настраивать, и обычно требуется динамическая корректировка, поскольку это сильно зависит от окружения ### сети (. Прежде чем перейти к следующему лидеру, протокол выплачивает полное наказание за задержку времени ожидания для вышедшего из строя лидера. Поэтому настройки времени ожидания не должны быть слишком консервативными, но если время ожидания слишком короткое, протокол может пропустить хорошего лидера.

К сожалению, основанные на соглашении лидера ), такие как Hotstuff и Jolteon (, по сути требуют задержки, чтобы гарантировать, что каждый раз, когда лидер выходит из строя, соглашение может продвигаться вперед. Без задержки даже вышедший из строя лидер может навсегда остановить соглашение. Поскольку в асинхронный период невозможно отличить вышедшего из строя лидера от медленного лидера, задержка может привести к тому, что узлы проверки будут рассматривать изменения всех лидеров без активности согласия.

В Bullshark задержка используется для построения DAG, чтобы гарантировать, что честные лидеры добавят якорные точки к DA во время синхронизации.