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, что далеко от целевого показателя в 100k+ TPS.

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

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

Таким образом, на Narwhal DAG была развернута Bullshark, протокол консенсуса с нулевыми затратами на связь. К сожалению, по сравнению с Jolteon, поддержка Bullshark в DAG-структуре с высокой пропускной способностью приводит к 50%-ному увеличению задержки.

В этой статье рассказывается о том, как Shoal значительно уменьшает задержку Bullshark.

! 万字详解Shoal框架:如何减少Aptos上的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框架:如何减少Aptos上的Bullshark延迟?

Рамка Shoal

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

Вызов

В контексте протокола DAG, проблемы конвейера и репутации лидера считаются сложными по следующим причинам:

1. Ранее попытки изменить основную логику Bullshark на конвейере, но это, по сути, кажется невозможным.

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

В качестве доказательства сложности задачи реализация Bullshark ( не поддерживает эти функции, включая текущие реализации в производственной среде ).

! 万字详解Shoal框架:如何减少Aptos上的Bullshark延迟?

Соглашение

Несмотря на вышеперечисленные проблемы, решение скрыто в простоте.

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

Конвейер

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

Сначала Shoal запускает первый экземпляр Bullshark в первом раунде DAG и работает до тех пор, пока не будет определена первая упорядоченная опорная точка, например, в раунде r. Все валидаторы согласны с этой опорной точкой. Таким образом, все валидаторы могут с уверенностью согласиться на переинтерпретацию DAG, начиная со второго раунда. Shoal просто запускает новый экземпляр Bullshark в раунде r+1.

В наилучшем случае это позволяет Shoal заказывать якорь в каждом раунде. Якорные точки первого раунда сортируются по первому экземпляру. Затем Shoal начинает новый экземпляр во втором раунде, у которого есть собственная якорная точка, которая сортируется по этому экземпляру, затем другой новый экземпляр заказывает якорные точки в третьем раунде, и процесс продолжается.

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

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

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

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

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

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

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

Тайм-аут также значительно увеличивает задержку, потому что их правильная настройка очень важна и обычно требует динамической корректировки, поскольку она сильно зависит от среды ( сети ). Перед тем как перейти к следующему лидеру, протокол будет выплачивать полное наказание за задержку тайм-аута для вышедшего из строя лидера. Поэтому настройки тайм-аута не могут быть слишком консервативными, но если время тайм-аута слишком короткое, протокол может пропустить хорошего лидера. Например, мы наблюдали, что при высокой нагрузке лидеры в Jolteon/Hotstuff перегружены, и тайм-аут истек до того, как прогресс был осуществлён.

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

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