Анализ фрейма 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)

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

При стремлении к высокой производительности блокчейн-сетей падение сложности коммуникаций всегда было в центре внимания. Однако этот подход не привел к значительному увеличению пропускной способности. Например, реализованный в раннем Diem Hotstuff достигал лишь 3500 TPS, что значительно ниже целевого значения в 100000+ 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. Упорядоченная причинно-следственная история: валидаторы поочередно обрабатывают упорядоченный список анкорных точек, сортируя ранее неупорядоченные вершины в причинно-следственной истории каждой анкорной точки.

Ключевой момент безопасности заключается в том, чтобы гарантировать, что в шаге (, все честные узлы верификации создают упорядоченный список якорных точек, которые имеют одинаковый префикс. 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.

Эти вызовы привели к тому, что реализации 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-46d37add0d9e81b2f295edf8eddd907f.webp(

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

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

Каждый раз при обновлении баллов необходимо детерминированно пересчитывать предопределенное отображение F от раунда к лидеру, ориентируясь на лидера с высоким баллом. Чтобы валидаторы согласовали новое отображение, им необходимо достичь согласия по баллам, тем самым согласовываясь на исторических данных, используемых для производных баллов.

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

Единственное отличие заключается в том, что после сортировки якорей на r-м раунде валидатор начинает рассчитывать новое отображение F' на основе причинно-следственной истории упорядоченных якорей r-го раунда. Затем узлы валидации начиная с r+1 раунда используют обновленную функцию выбора якорей F' для выполнения нового экземпляра Bullshark.

Устранение задержки

Таймаут играет ключевую роль во всех реализациях 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. Ниже приведены некоторые ключевые моменты оценки:

Сначала, для演