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

Все валидаторы согласны с первой упорядоченной опорной точкой.

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

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, начиная с раунда r+1. Shoal просто запустил новый экземпляр Bullshark в раунде r+1.

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

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

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

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

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

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

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

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

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

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