Шаблон Shoal: как уменьшить задержку Bullshark на Aptos

Обзор

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

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

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

! [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 протоколыConsensus имеют следующую структуру:

1. Забронированная опорная точка: каждые несколько раундов (, как в Bullshark, через два раунда ) будет заранее определенный лидер, вершина которого называется опорной точкой;

2. Сортировка якорей: валидаторы независимо, но детерминированно решают, какие якоря сортировать, а какие пропускать;

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

Ключом к обеспечению безопасности является гарантирование того, что в шаге (2) все честные узлы проверки создают упорядоченный список анкерных точек, который имеет одинаковый префикс. В Shoal мы делаем следующие наблюдения по всем вышеупомянутым протоколам:

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

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

Bullshark задержка

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

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

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

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

Шаблон Shoal

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

Вызов

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

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

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

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

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

Протокол

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

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

Конвейер

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-9f789cb669f6fcc244ea7ff7648e48b4.webp(

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

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

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

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

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

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

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

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

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