Aptos Labs недавно решила две важные открытые проблемы в DAG BFT, значительно снизив задержки и впервые устранив необходимость в паузах в определенном реальном протоколе. В целом, задержка Bullshark улучшилась на 40% в условиях безотказной работы и на 80% в условиях с отказами.
Shoal является рамочной программой, которая улучшает любой протокол согласования на основе Narwhal (, такой как DAG-Rider, Tusk, Bullshark ), с помощью конвейера и репутации лидера. Конвейер уменьшает задержку сортировки DAG, вводя якорную точку в каждом круге, а репутация лидера дополнительно улучшает задержку, обеспечивая связь якорной точки с самыми быстрыми узлами валидации. Кроме того, репутация лидера позволяет Shoal использовать асинхронную конструкцию DAG для устранения таймаутов во всех сценариях. Это позволяет Shoal обеспечить атрибут, который мы называем универсальным откликом, который содержит обычно требуемый оптимистичный ответ.
С технической точки зрения, 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. К сожалению, структура DAG, поддерживающая Bullshark с высокой пропускной способностью, приводит к 50% затратам на задержку по сравнению с Jolteon.
В статье описывается, как 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 имеют следующую структуру:
Заказная опорная точка: каждые несколько раундов (, как в Bullshark, каждые два раунда ) будет заранее определенный лидер, вершина лидера называется опорной точкой;
Точка сортировки: валидаторы независимо, но с определенностью решают, какие точки сортировки использовать, а какие пропустить;
Упорядоченная причинно-следственная история: валидаторы обрабатывают список упорядоченных якорных точек по одному, сортируя все предыдущие неупорядоченные вершины в их причинно-следственной истории с помощью детерминированных правил для каждой якорной точки.
Ключ к обеспечению безопасности заключается в том, чтобы гарантировать, что в шаге (2) все честные проверочные узлы создают упорядоченный список опорных точек, который разделяет один и тот же префикс. В Shoal мы делаем следующие наблюдения по всем вышеупомянутым протоколам:
Все валидаторы согласны с первым упорядоченным якорем.
Задержка Bullshark зависит от количества раундов между упорядоченными якорными точками в DAG. Хотя у Bullshark более практичная часть синхронной версии имеет лучшую задержку по сравнению с асинхронной версией, она все же далеко не оптимальна.
Вопрос 1: Средняя задержка блока. В Bullshark в каждой четной итерации есть опорная точка, а вершины в каждой нечетной итерации интерпретируются как голосование. В обычных случаях требуется две итерации DAG для сортировки опорных точек, однако вершины в причинно-следственной истории опорной точки требуют больше итераций ожидания для сортировки опорной точки. В обычных случаях вершины в нечетной итерации требуют три итерации, а вершины в четной итерации, не являющиеся опорными, требуют четыре итерации.
Вопрос 2: Задержка в случаях сбоев. Указанный анализ задержки применяется в случае отсутствия сбоев; с другой стороны, если лидер раунда не успевает достаточно быстро транслировать опорную точку, то опорная точка не может быть отсортирована ( и, следовательно, пропускается ). Таким образом, все несортированные вершины из предыдущих раундов должны ждать, пока следующая опорная точка не будет отсортирована. Это значительно снижает производительность географически распределенной сети, особенно учитывая, что Bullshark использует таймаут для ожидания лидера.
Shoal решает эти две проблемы задержки, он улучшает Bullshark( или любой другой BFT протокол на основе Narwhal) за счет конвейерной обработки, позволяя в каждом раунде иметь одну опору и уменьшая задержку всех не-опорных вершин в DAG до трех раундов. Shoal также вводит механизм репутации лидера с нулевыми затратами в DAG, что делает выбор более склонным к быстрому лидеру.
Вызов
В контексте протокола DAG, проблемы с конвейерами и репутацией лидеров считаются сложными по следующим причинам:
Ранее конвейер пытался изменить основную логику Bullshark, но это, по сути, кажется невозможным.
Репутация лидера вводится в DiemBFT и формализуется в Carousel, основываясь на динамическом выборе будущих лидеров по прошлым достижениям валидаторов, идея якоря в Bullshark (. Хотя разногласия в лидерстве не нарушают безопасность этих протоколов, в Bullshark это может привести к совершенно разным порядкам, что поднимает суть проблемы: динамический и детерминированный выбор колесного якоря необходим для достижения консенсуса, и валидаторы должны согласовать упорядоченную историю для выбора будущих якорей.
В качестве доказательства сложности проблемы мы отметили, что реализация Bullshark, включая текущую реализацию в производственной среде, не поддерживает эти функции.
![Подробное объяснение структуры Shoal: как уменьшить задержку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-0b0928cb6240e994c1514c75e080a4b2.webp(
Соглашение
Несмотря на упомянутые выше проблемы, на самом деле решение скрыто в простоте.
В 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-м круге, валидатору нужно просто вычислить новое отображение F' начиная с r+1 круга, основываясь на причинно-следственной истории упорядоченных опорных точек в r-м круге. Затем, начиная с r+1 круга, узлы-валидаторы выполняют новый экземпляр Bullshark, используя обновленную функцию выбора опорных точек F'.
![Подробное объяснение рамки Shoal: Как уменьшить задержку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(
Нет больше тайм-аутов
Тайм-аут играет решающую роль во всех реализациях BFT с определённостью на основе лидера. Однако, сложность, которую они вводят, увеличивает количество внутренних состояний, которые необходимо управлять и наблюдать, что усложняет процесс отладки и требует больше технологий наблюдаемости.
Тайм-аут также значительно увеличивает задержку, потому что их правильная настройка очень важна и часто требует динамической корректировки, поскольку она сильно зависит от окружения ) сети (. Перед переходом к следующему лидеру протокол будет платить полное наказание за задержку тайм-аута для неработающего лидера. Поэтому настройки тайм-аута не могут быть слишком консервативными, но если время тайм-аута слишком короткое, протокол может пропустить хорошего лидера. Например, мы наблюдали, что в условиях высокой нагрузки лидеры в Jolteon/Hotstuff перегружены, и тайм-аут истекает, прежде чем они смогут продвинуться вперед.
This page may contain third-party content, which is provided for information purposes only (not representations/warranties) and should not be considered as an endorsement of its views by Gate, nor as financial or professional advice. See Disclaimer for details.
16 Лайков
Награда
16
4
Поделиться
комментарий
0/400
DeFiChef
· 15ч назад
Этот 40% прирост производительности просто шикарен!
Посмотреть ОригиналОтветить0
TokenEconomist
· 07-02 09:36
на самом деле, архитектура shoal - это шедевр теории игр. представьте себе это как равновесие Нэша, где валидаторы оптимизируют репутацию = f(скорость, надежность)...
Посмотреть ОригиналОтветить0
WhaleSurfer
· 07-02 09:33
бык бык бык突破上限啦
Посмотреть ОригиналОтветить0
TokenSleuth
· 07-02 09:24
Aptos эта оптимизация бык а задержка снизилась так сильно
Shoal 框架大幅降低Aptos 上Bullshark延迟 流水线和声誉机制显有提升性能
Shoal框架: Улучшение задержки Bullshark на Aptos
Aptos Labs недавно решила две важные открытые проблемы в DAG BFT, значительно снизив задержки и впервые устранив необходимость в паузах в определенном реальном протоколе. В целом, задержка Bullshark улучшилась на 40% в условиях безотказной работы и на 80% в условиях с отказами.
Shoal является рамочной программой, которая улучшает любой протокол согласования на основе Narwhal (, такой как DAG-Rider, Tusk, Bullshark ), с помощью конвейера и репутации лидера. Конвейер уменьшает задержку сортировки DAG, вводя якорную точку в каждом круге, а репутация лидера дополнительно улучшает задержку, обеспечивая связь якорной точки с самыми быстрыми узлами валидации. Кроме того, репутация лидера позволяет Shoal использовать асинхронную конструкцию DAG для устранения таймаутов во всех сценариях. Это позволяет Shoal обеспечить атрибут, который мы называем универсальным откликом, который содержит обычно требуемый оптимистичный ответ.
С технической точки зрения, 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. К сожалению, структура DAG, поддерживающая Bullshark с высокой пропускной способностью, приводит к 50% затратам на задержку по сравнению с Jolteon.
В статье описывается, как 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 имеют следующую структуру:
Заказная опорная точка: каждые несколько раундов (, как в Bullshark, каждые два раунда ) будет заранее определенный лидер, вершина лидера называется опорной точкой;
Точка сортировки: валидаторы независимо, но с определенностью решают, какие точки сортировки использовать, а какие пропустить;
Упорядоченная причинно-следственная история: валидаторы обрабатывают список упорядоченных якорных точек по одному, сортируя все предыдущие неупорядоченные вершины в их причинно-следственной истории с помощью детерминированных правил для каждой якорной точки.
Ключ к обеспечению безопасности заключается в том, чтобы гарантировать, что в шаге (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, проблемы с конвейерами и репутацией лидеров считаются сложными по следующим причинам:
Ранее конвейер пытался изменить основную логику Bullshark, но это, по сути, кажется невозможным.
Репутация лидера вводится в DiemBFT и формализуется в Carousel, основываясь на динамическом выборе будущих лидеров по прошлым достижениям валидаторов, идея якоря в Bullshark (. Хотя разногласия в лидерстве не нарушают безопасность этих протоколов, в Bullshark это может привести к совершенно разным порядкам, что поднимает суть проблемы: динамический и детерминированный выбор колесного якоря необходим для достижения консенсуса, и валидаторы должны согласовать упорядоченную историю для выбора будущих якорей.
В качестве доказательства сложности проблемы мы отметили, что реализация Bullshark, включая текущую реализацию в производственной среде, не поддерживает эти функции.
![Подробное объяснение структуры Shoal: как уменьшить задержку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-0b0928cb6240e994c1514c75e080a4b2.webp(
Соглашение
Несмотря на упомянутые выше проблемы, на самом деле решение скрыто в простоте.
В Shoal мы полагаемся на возможность выполнения локальных вычислений на DAG и реализуем возможность сохранения и переосмысления информации из предыдущих раундов. Благодаря тому, что все валидаторы согласны с основным пониманием первого упорядоченного якоря, Shoal последовательно комбинирует несколько экземпляров Bullshark для их обработки в конвейере, что делает ) первым упорядоченным якорем, а ( причинной историей якоря, используемой для вычисления репутации лидера.
Конвейер
V, которое сопоставляет раунды с лидерами. Shoal запускает экземпляры Bullshark один за другим, так что для каждого экземпляра якорь заранее определяется отображением F. Каждый экземпляр сортирует якорь, что вызывает переход к следующему экземпляру.
Сначала Shoal запустил первый экземпляр Bullshark в первом раунде DAG и продолжал его до определения первой упорядоченной вехи, например, в r-м раунде. Все валидаторы согласны с этой вехой. Таким образом, все валидаторы могут с уверенностью согласиться на повторную интерпретацию DAG, начиная со второго раунда (r+1). Shoal просто запустил новый экземпляр Bullshark в раунде r+1.
В наилучших условиях это позволяет Shoal сортировать якорь в каждом раунде. Якоря первого раунда сортируются по первому экземпляру. Затем Shoal начинает новый экземпляр во втором раунде, который сам имеет якорь, сортируемый этим экземпляром, затем другой новый экземпляр сортирует якоря в третьем раунде, и этот процесс продолжается.
! [万字详解Shoal框架:如何减少Aptos上的Bullshark延迟? ])https://img-cdn.gateio.im/webp-social/moments-859e732e16c3eee0e2c93422474debc2.webp(
Репутация лидера
Во время сортировки Bullshark, если пропустить опорные точки, задержка увеличивается. В этом случае технологии конвейера бесполезны, поскольку новая инстанция не может быть запущена до сортировки опорной точки предыдущей инстанции. Shoal использует механизм репутации для назначения балла каждому узлу проверки в зависимости от недавней активности, чтобы в будущем с меньшей вероятностью выбирать соответствующего лидера для обработки потерянных опорных точек. Проверяющие, которые реагируют и участвуют в протоколе, получат высокие баллы, в противном случае узлам проверки будут присвоены низкие баллы, так как они могут зависнуть, работать медленно или действовать злонамеренно.
Идея заключается в том, чтобы при каждом обновлении счета детерминированно пересчитывать предопределенное отображение F от раунда к лидеру, с уклоном в сторону лидеров с более высоким счетом. Чтобы валидаторы согласовали новое отображение, они должны достичь согласия по счету, таким образом достигая согласия по истории, используемой для выведения счета.
В Shoal поточные линии и репутация лидеров могут естественно сочетаться, поскольку они оба используют одну и ту же основную технологию, а именно переосмысляют DAG после достижения согласия по первому упорядоченному якорному пункту.
На самом деле, единственное отличие заключается в том, что после сортировки опорных точек в r-м круге, валидатору нужно просто вычислить новое отображение F' начиная с r+1 круга, основываясь на причинно-следственной истории упорядоченных опорных точек в r-м круге. Затем, начиная с r+1 круга, узлы-валидаторы выполняют новый экземпляр Bullshark, используя обновленную функцию выбора опорных точек F'.
![Подробное объяснение рамки Shoal: Как уменьшить задержку Bullshark на Aptos?])https://img-cdn.gateio.im/webp-social/moments-9f789cb669f6fcc244ea7ff7648e48b4.webp(
Нет больше тайм-аутов
Тайм-аут играет решающую роль во всех реализациях BFT с определённостью на основе лидера. Однако, сложность, которую они вводят, увеличивает количество внутренних состояний, которые необходимо управлять и наблюдать, что усложняет процесс отладки и требует больше технологий наблюдаемости.
Тайм-аут также значительно увеличивает задержку, потому что их правильная настройка очень важна и часто требует динамической корректировки, поскольку она сильно зависит от окружения ) сети (. Перед переходом к следующему лидеру протокол будет платить полное наказание за задержку тайм-аута для неработающего лидера. Поэтому настройки тайм-аута не могут быть слишком консервативными, но если время тайм-аута слишком короткое, протокол может пропустить хорошего лидера. Например, мы наблюдали, что в условиях высокой нагрузки лидеры в Jolteon/Hotstuff перегружены, и тайм-аут истекает, прежде чем они смогут продвинуться вперед.
К сожалению, основываясь на руководстве