Лаборатории Aptos решили две важные открытые проблемы в DAG BFT, значительно уменьшив задержку и впервые устранив необходимость в паузах в детерминированных практических протоколах. В целом, это уменьшает задержку Bullshark на 40 % в случае безотказной работы и на 80 % в случае сбоя.
Shoal — это фреймворк, улучшающий любой консенсусный протокол на основе Narwhal (например, DAG-Rider, Tusk, Bullshark) за счет конвейеризации и репутации лидера. Конвейерная обработка уменьшает задержку заказа DAG, вводя привязку на раунд, а репутация лидера еще больше сокращает задержку, гарантируя, что привязки связаны с самыми быстрыми валидаторами. Кроме того, репутация лидера позволяет Shoal использовать асинхронное построение DAG для устранения тайм-аутов во всех сценариях. Это позволяет Shoal предоставлять свойство, которое мы назвали Universal Response, которое содержит оптимистичный ответ, который обычно требуется.
Наша методика очень проста, она включает в себя запуск нескольких экземпляров базового протокола последовательно один за другим. Итак, при создании экземпляра с помощью Bullshark мы получаем группу «акул», которые участвуют в эстафете.
Мотивация
В погоне за высокой производительностью в сетях блокчейна постоянно уделялось внимание снижению сложности связи. Однако такой подход не привел к значительному увеличению пропускной способности. Например, реализация Hotstuff в ранней версии Diem достигла только 3500 TPS, что намного ниже нашей цели — более 100 000 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 и Bullshark см. в посте DAG и BFT.
Каждая вершина в DAG нарвала связана с круглым числом. Чтобы войти в раунд r, верификатор должен сначала получить nf вершин, принадлежащих раунду r-1. Каждый верификатор может передать одну вершину за раунд, и каждая вершина ссылается как минимум на nf вершин в предыдущем раунде. Из-за сетевой асинхронности разные валидаторы могут наблюдать разные локальные представления группы обеспечения доступности баз данных в любой момент времени. Вот иллюстрация возможного частичного вида:
Ключевым свойством DAG не является двусмысленность: два валидатора имеют точно такую же причинно-следственную историю v, если у них есть одна и та же вершина v в их локальном представлении DAG.
Общий заказ
Можно согласовать общий порядок всех вершин в DAG без дополнительных затрат на связь. С этой целью валидаторы в DAG-Rider, Tusk и Bullshark интерпретируют структуру DAG как протокол консенсуса, где вершины представляют предложения, а ребра представляют голоса.
Хотя логика пересечения групп отличается в структуре DAG, все существующие протоколы консенсуса на основе Narwhal имеют следующую структуру:
Предопределенные якоря, каждые несколько раундов будет предопределенный лидер (например, два раунда в Bullshark), а вершины лидера называются якорями;
Заказывая якоря, верификатор самостоятельно, но детерминированно решает, какие якоря заказывать, а какие пропускать;
Упорядочивание причинно-следственных связей, когда валидаторы обрабатывают свой упорядоченный список якорей один за другим и для каждого якоря сортируют все ранее неупорядоченные вершины в его причинно-следственной истории по некоторому детерминированному правилу.
Рисунок 2: Иллюстрация возможного частичного представления DAG в протоколе Bullshark. В этом примере красные и желтые привязки сортируются, а зеленые (не в DAG) пропускаются. Поэтому, чтобы упорядочить DAG, валидаторы детерминистически упорядочивают сначала причинно-следственные истории красных якорей, а затем желтых.
Ключом к обеспечению безопасности является обеспечение того, чтобы на шаге (2) выше все честные валидаторы создавали упорядоченный список якорей таким образом, чтобы все списки имели один и тот же префикс. В Shoal мы делаем следующие наблюдения для всех вышеперечисленных протоколов:
** Все валидаторы согласны с первым заказанным анкором. **
Задержка Bullshark
Задержка Bullshark зависит от количества раундов между упорядоченными якорями в DAG. Хотя наиболее полезная частично синхронная версия Bullshark имеет лучшую задержку, чем асинхронная версия, она далека от оптимальной.
Проблема 1: Средняя задержка блока. В Bullshark у каждого четного раунда есть якорь, а вершины каждого нечетного раунда интерпретируются как голоса. Как правило, для заказа якорей требуется два раунда DAG, однако вершинам в причинно-следственной истории якоря требуется гораздо больше раундов, чтобы дождаться заказа якоря. В общем случае вершины в нечетных раундах требуют трех раундов, в то время как непривязанные вершины в четных раундах требуют четырех раундов (см. рис. 3).
Рисунок 3: В общем случае якоря в раунде i+1 необходимо отсортировать за два раунда. Вершины в раунде i сортируются одновременно, поэтому их задержка составляет три раунда. Однако вершины в раунде i+1 должны ждать сортировки следующего якоря (тот, что в раунде i+3), поэтому задержка их сортировки составляет четыре раунда.
Проблема 2: задержка в случае сбоя. Приведенный выше анализ задержки применим к безотказному случаю, с другой стороны, если лидеру раунда не удается достаточно быстро транслировать якоря, якоря не могут быть заказаны (и, следовательно, пропускаются), поэтому все несортированные вершины в предыдущих раундах должны дождаться сортировки следующего якоря. Это может значительно снизить производительность геореплицированной сети, тем более что Bullshark использует тайм-ауты ожидания лидера.
Каркас мелководья
Shoal решает обе эти проблемы с задержкой, улучшая Bullshark (или любой другой протокол BFT на основе Narwhal) путем конвейерной обработки, позволяя использовать якорь в каждом раунде и уменьшая задержку всех неякорных вершин в DAG до трех раундов. Shoal также вводит механизм репутации лидера с нулевыми накладными расходами в DAG, который смещает выбор в пользу быстрых лидеров.
испытание
В контексте протоколов DAG конвейеризация и репутация лидера считаются сложными проблемами по следующим причинам:
Предыдущая конвейерная обработка пытается изменить основную логику Bullshark, но это кажется невозможным по своей сути.
Лидерская репутация, представленная в DiemBFT и формализованная в Carousel, — это идея динамического выбора будущих лидеров (якорей в Bullshark) на основе прошлых показателей валидаторов. В то время как разногласия по поводу личности лидера не нарушают безопасность в этих протоколах, в Bullshark это может привести к совершенно другому порядку, который затрагивает суть вопроса, заключающегося в том, что динамический и детерминированный выбор колесных якорей является решением для достижения необходимого консенсуса. в то время как валидаторы должны согласовать упорядоченную историю, чтобы выбрать будущие якоря.
В качестве доказательства сложности проблемы отметим, что реализация Bullshark, включая текущую реализацию в продакшене, не поддерживает эти возможности.
соглашение
Несмотря на вышеупомянутые проблемы, оказывается, что решения, как говорится, кроются за простотой.
В Shoal мы полагаемся на возможность выполнять локальные вычисления в DAG и реализовывать возможность сохранения и повторной интерпретации информации из предыдущих раундов. Опираясь на основное понимание того, что все валидаторы соглашаются с первым якорем по порядку, Shoal объединяет несколько экземпляров Bullshark, компонуя их последовательно таким образом, что (1) первый якорь по порядку является точкой переключения для экземпляров, и (2) причинно-следственная связь. история якорей используется для расчета репутации лидера.
Конвейерная обработка
Как и в случае с Bullshark, валидаторы априори договариваются о потенциальных якорях, т. е. существует известное отображение F: R -> V, отображающее раунды в лидеры. Shoal запускает экземпляры Bullshark один за другим, так что для каждого экземпляра привязка предопределяется картой F. Каждый экземпляр заказывает якорь, который запускает переключение на следующий экземпляр.
Первоначально Shoal запускает первый экземпляр Bullshark в первом раунде DAG и запускает его до тех пор, пока не будет идентифицирован первый упорядоченный якорь, скажем, в раунде r. Все валидаторы согласны с этим якорем. Следовательно, все валидаторы могут детерминистически согласиться переинтерпретировать DAG, начиная с раунда r+1. Shoal просто запускает новый экземпляр Bullshark в раунде r+1.
В лучшем случае это позволяет Shoal заказывать якорь каждый раунд. Якоря для первого раунда сортируются по первому экземпляру. Затем Shoal запускает новый экземпляр во втором раунде, который сам имеет якорь, упорядоченный экземпляром, затем другой новый экземпляр упорядочивает якоря в третьем раунде, и процесс продолжается. Пожалуйста, смотрите иллюстрацию ниже:
Рисунок 4: Вершины, соответствующие лидерам, определенным F, отмечены короной Первый экземпляр Bullshark сначала интерпретирует DAG с якорями в раундах 1, 3 и 5. Bullshark определяет якоря в раунде 1 (зеленая галочка). mark) является первым, который будет отсортирован в первом экземпляре. (Обратите внимание, что в общем случае этот якорь можно пропустить, в то время как некоторые другие якоря будут отсортированы первыми.) Затем остальная часть первого экземпляра игнорируется, и начинается новый экземпляр Bullshark со 2-го раунда. Точки привязки отмечаются во 2 и 4 раундах.
Репутация лидера
Увеличена задержка при пропуске якорей во время сортировки Bullshark. В этом случае метод Pipelining бессилен, поскольку новый экземпляр нельзя запустить, пока предыдущий экземпляр не заказал привязку. Shoal гарантирует, что соответствующий лидер с меньшей вероятностью будет избран в будущем, чтобы иметь дело с потерянным якорем, используя механизм репутации для присвоения каждому валидатору оценки на основе его истории недавней активности. Валидатору, который отвечает и участвует в протоколе, будет присвоен высокий балл, в противном случае валидатору будет присвоен низкий балл, потому что он может дать сбой, быть медленным или быть вредоносным.
Идея состоит в том, чтобы детерминистически пересчитывать предопределенное отображение F из раундов в лидеров при каждом обновлении результатов, отдавая предпочтение лидерам с более высокими баллами. Чтобы валидаторы согласились с новым сопоставлением, они должны согласовать оценку и, следовательно, историю, используемую для получения оценки.
В Shoal конвейеризация и репутация лидера могут естественным образом сочетаться, потому что они оба используют один и тот же основной метод переосмысления DAG после согласования первого заказанного якоря.
На самом деле, единственное отличие состоит в том, что после сортировки якорей в раунде r валидатору нужно только вычислить новое отображение F' из раунда r+1 на основе причинно-следственной истории упорядоченных якорей в раунде r. Затем валидатор запускает новый экземпляр Bullshark, начиная с раунда r+1, используя обновленную функцию выбора привязки F'. Смотрите изображение ниже:
Рис. 5. Вершины, соответствующие лидерам, обозначенным буквой F, отмечены прозрачными коронами. Первый экземпляр Bullshark заказывает привязку в раунде 1, отмеченную зеленой галочкой, а затем вычисляет новое отображение F' на основе информации из причинно-следственной истории привязки. Лидеры, определяемые F', отмечены цветными коронами.
Нет больше тайм-аутов
Тайм-ауты играют решающую роль во всех детерминированных частично синхронных реализациях BFT на основе лидеров. Однако сложность, которую они вносят, увеличивает объем внутреннего состояния, которым необходимо управлять и наблюдать, что усложняет процесс отладки и требует дополнительных методов наблюдения.
Тайм-ауты также могут значительно увеличить задержку, поскольку важно правильно их настроить, и обычно их необходимо настраивать динамически, поскольку они сильно зависят от среды (сети). Протокол выплачивает неисправному лидеру полный штраф за задержку тайм-аута перед переходом к следующему лидеру. Поэтому установка тайм-аута не может быть слишком консервативной, но если тайм-аут слишком короткий, протокол может пропустить хороших лидеров. Например, мы заметили, что при высокой нагрузке лидеры в Jolteon/Hotstuff были перегружены, и тайм-ауты истекали, прежде чем они могли ускорить прогресс.
К сожалению, протоколы на основе лидеров, такие как Hotstuff и Jolteon, по своей сути требуют тайм-аутов, чтобы гарантировать, что протокол может продвигаться вперед каждый раз, когда лидер терпит неудачу. Без тайм-аута даже разбившийся лидер может навсегда остановить протокол. Из-за невозможности отличить неисправного лидера от медленного лидера во время асинхронности, тайм-ауты могут привести к тому, что валидаторы увидят изменения во всех лидерах без согласованности.
В Bullshark тайм-ауты используются при построении DAG, чтобы во время синхронизации честный лидер добавлял якоря в DAG достаточно быстро, чтобы их можно было заказать.
Мы видим, что конструкция DAG предоставляет «часы» для оценки скорости сети. При отсутствии пауз раунды продолжаются до тех пор, пока nf честных валидаторов продолжают добавлять вершины в DAG. Хотя Bullshark не может сортировать на скорости сети (из-за проблемных лидеров), DAG по-прежнему растет со скоростью сети, несмотря на некоторые проблемы с лидерами или асинхронность сети. В конце концов, когда безупречный лидер достаточно быстро транслирует якоря, вся причинно-следственная история якорей будет упорядочена.
В нашей оценке мы сравнили Bullshark с тайм-аутом и без него в следующих случаях:
Быстрый лидер, то есть как минимум быстрее других валидаторов. В этом случае оба метода обеспечивают одинаковую задержку, поскольку якоря упорядочены, а тайм-ауты не используются.
Ложный лидер, в этом случае Bullshark без пауз обеспечивает лучшую задержку, так как валидаторы будут сразу пропускать его анкоры, а валидаторы с паузами будут ждать их прихода, прежде чем продолжить Expect.
Медленный лидер, это единственный случай, когда у Bullshark лучше показатели таймаута. Это связано с тем, что без паузы анкор может быть пропущен, потому что лидер не может транслировать его достаточно быстро, а с паузой валидаторы будут ждать анкора.
В Shoal избегание тайм-аутов и репутация лидера идут рука об руку. Многократное ожидание медленного лидера увеличивает задержку, а механизм репутации лидера не позволяет медленным валидаторам быть избранными лидерами. Таким образом, система использует узлы быстрой проверки для работы на скорости сети во всех реальных сценариях.
Обратите внимание, что результат невозможности FLP показывает, что ни один протокол детерминированного консенсуса не может избежать тайм-аутов. Мелководье не может обойти этот исход, потому что существует теоретический график враждебных событий, который не позволяет управлять всеми якорями. Вместо этого Shoal возвращается к тайм-ауту после настраиваемого количества последовательных пропусков привязки. На практике это крайне маловероятно.
Общий ответ
В документе Hotstuff популяризирована концепция оптимистического ответа, которая, хотя и не определена формально, интуитивно означает, что протокол может работать на скорости сети в хороших условиях, включая быстрый лидер и синхронную сеть.
Shoal обеспечивает еще лучшее свойство, которое мы называем Universal Response. В частности, в отличие от Hotstuff, Shoal продолжает работать со скоростью сети, даже если лидер выходит из строя в течение заданного количества последовательных раундов или асинхронных циклов, через которые проходит сеть. Более подробное сравнение смотрите в таблице ниже.
Обратите внимание, что универсальная отзывчивость обеспечивает строго лучшие гарантии прогресса в асинхронные периоды и при сбое лидера. При синхронизации с медленным лидером эти свойства несопоставимы, поскольку зависят от того, насколько медленный лидер. Однако, учитывая репутацию лидера, медлительные лидеры редко должны появляться в Shoal.
Оценивать
Мы внедрили Bullshark и Shoal поверх нашей реализации Quorum Store в Narwhal. Подробное сравнение между Shoal, Bullshark и Jolteon можно найти в разделе оценки документа Shoal, где мы приводим некоторые основные моменты.
Во-первых, чтобы продемонстрировать мощь асинхронного построения DAG, мы сравним Bullshark с паузами и без них. Полный документ Bullshark предполагает асинхронную сеть, но обеспечивает режим быстрого пути, что требует пауз во всех раундах. Мы называем эту версию Vanilla Bullshark. Заметим, что для независимых частично синхронных гипотетических версий сети паузы в раундах голосования не требуются. Мы называем эту версию Vanilla Bullshark без таймаута голосования без таймаута голосования, Baseline Bullshark — это версия без таймаута.
На приведенном ниже графике сравнивается влияние тайм-аутов на задержку Bullshark со сбоями и без них. Судя по всему, Baseline Bullshark (без тайм-аута) лучше всего работает в случае сбоя. Без сбоев Baseline Bullshark сопоставим с Vanilla Bullshark без приостановки голосования. Это связано с тем, что, как упоминалось ранее, без механизма репутации лидера тайм-ауты могут иметь преимущество в ситуациях, когда лидер хорош, но медлителен.
Рисунок 6.: Влияние тайм-аутов на задержку Bullshark без сбоев (слева) и со сбоями (справа), с 50 валидаторами в случае сбоя
Затем мы создаем экземпляр Shoal с помощью Baseline Bullshark (без тайм-аута) и демонстрируем улучшение задержки конвейерной обработки и механизма репутации лидера с ошибкой и без нее, а для полноты картины мы также сравниваем ее с Jolteon с сбоем и без него.
На рис. 7 ниже показан безотказный случай, и хотя конвейерная обработка и репутация лидера могут уменьшить задержку по отдельности, их сочетание приводит к наилучшей задержке.
Что касается Jolteon, он не может масштабироваться до более чем 20 валидаторов, и даже если он работает в Quorum Store, его пропускная способность составляет примерно половину пропускной способности Bullshark/Shoal, что устраняет узкое место в распространении данных.
Результаты показывают, что Shoal значительно улучшает задержку Bullshark. Что касается Jolteon, важно отметить, что хотя мы измеряли только задержку консенсуса. Поскольку Jolteon изначально не может работать поверх DAG, для разделения распространения данных требуется дополнительная задержка, которую мы не измеряли. Следовательно, при высокой нагрузке Shoal должен соответствовать сквозной задержке Jolteon.
Рисунок 7: Пропускная способность и задержка без сбоев, Shoal PL и Shaol LR поддерживают только конвейерную обработку и репутацию лидера соответственно.
На рис. 8 ниже показан случай сбоя с 50 валидаторами, где механизм репутации лидера значительно уменьшает задержку, уменьшая вероятность того, что отказавший валидатор будет избран лидером. Обратите внимание, что при 16 сбоях из 50 задержка Shoal была на 65% ниже, чем у базовой версии Bullshark.
Посмотреть Оригинал
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.
Объяснение 4D Shoal Framework: как уменьшить задержку Bullshark на Aptos?
Оригинал: Aptos Labs
Сборник: Aptos Global
Обзор
Лаборатории Aptos решили две важные открытые проблемы в DAG BFT, значительно уменьшив задержку и впервые устранив необходимость в паузах в детерминированных практических протоколах. В целом, это уменьшает задержку Bullshark на 40 % в случае безотказной работы и на 80 % в случае сбоя.
Shoal — это фреймворк, улучшающий любой консенсусный протокол на основе Narwhal (например, DAG-Rider, Tusk, Bullshark) за счет конвейеризации и репутации лидера. Конвейерная обработка уменьшает задержку заказа DAG, вводя привязку на раунд, а репутация лидера еще больше сокращает задержку, гарантируя, что привязки связаны с самыми быстрыми валидаторами. Кроме того, репутация лидера позволяет Shoal использовать асинхронное построение DAG для устранения тайм-аутов во всех сценариях. Это позволяет Shoal предоставлять свойство, которое мы назвали Universal Response, которое содержит оптимистичный ответ, который обычно требуется.
Наша методика очень проста, она включает в себя запуск нескольких экземпляров базового протокола последовательно один за другим. Итак, при создании экземпляра с помощью Bullshark мы получаем группу «акул», которые участвуют в эстафете.
Мотивация
В погоне за высокой производительностью в сетях блокчейна постоянно уделялось внимание снижению сложности связи. Однако такой подход не привел к значительному увеличению пропускной способности. Например, реализация Hotstuff в ранней версии Diem достигла только 3500 TPS, что намного ниже нашей цели — более 100 000 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 и Bullshark см. в посте DAG и BFT.
Каждая вершина в DAG нарвала связана с круглым числом. Чтобы войти в раунд r, верификатор должен сначала получить nf вершин, принадлежащих раунду r-1. Каждый верификатор может передать одну вершину за раунд, и каждая вершина ссылается как минимум на nf вершин в предыдущем раунде. Из-за сетевой асинхронности разные валидаторы могут наблюдать разные локальные представления группы обеспечения доступности баз данных в любой момент времени. Вот иллюстрация возможного частичного вида:
Рисунок 1. Причинная история вершин, идентифицированных узлом проверки 2 раунда 2, выделена зеленым цветом.
Ключевым свойством DAG не является двусмысленность: два валидатора имеют точно такую же причинно-следственную историю v, если у них есть одна и та же вершина v в их локальном представлении DAG.
Общий заказ
Можно согласовать общий порядок всех вершин в DAG без дополнительных затрат на связь. С этой целью валидаторы в DAG-Rider, Tusk и Bullshark интерпретируют структуру DAG как протокол консенсуса, где вершины представляют предложения, а ребра представляют голоса.
Хотя логика пересечения групп отличается в структуре DAG, все существующие протоколы консенсуса на основе Narwhal имеют следующую структуру:
Предопределенные якоря, каждые несколько раундов будет предопределенный лидер (например, два раунда в Bullshark), а вершины лидера называются якорями;
Заказывая якоря, верификатор самостоятельно, но детерминированно решает, какие якоря заказывать, а какие пропускать;
Упорядочивание причинно-следственных связей, когда валидаторы обрабатывают свой упорядоченный список якорей один за другим и для каждого якоря сортируют все ранее неупорядоченные вершины в его причинно-следственной истории по некоторому детерминированному правилу.
Рисунок 2: Иллюстрация возможного частичного представления DAG в протоколе Bullshark. В этом примере красные и желтые привязки сортируются, а зеленые (не в DAG) пропускаются. Поэтому, чтобы упорядочить DAG, валидаторы детерминистически упорядочивают сначала причинно-следственные истории красных якорей, а затем желтых.
Ключом к обеспечению безопасности является обеспечение того, чтобы на шаге (2) выше все честные валидаторы создавали упорядоченный список якорей таким образом, чтобы все списки имели один и тот же префикс. В Shoal мы делаем следующие наблюдения для всех вышеперечисленных протоколов:
** Все валидаторы согласны с первым заказанным анкором. **
Задержка Bullshark
Задержка Bullshark зависит от количества раундов между упорядоченными якорями в DAG. Хотя наиболее полезная частично синхронная версия Bullshark имеет лучшую задержку, чем асинхронная версия, она далека от оптимальной.
Проблема 1: Средняя задержка блока. В Bullshark у каждого четного раунда есть якорь, а вершины каждого нечетного раунда интерпретируются как голоса. Как правило, для заказа якорей требуется два раунда DAG, однако вершинам в причинно-следственной истории якоря требуется гораздо больше раундов, чтобы дождаться заказа якоря. В общем случае вершины в нечетных раундах требуют трех раундов, в то время как непривязанные вершины в четных раундах требуют четырех раундов (см. рис. 3).
Рисунок 3: В общем случае якоря в раунде i+1 необходимо отсортировать за два раунда. Вершины в раунде i сортируются одновременно, поэтому их задержка составляет три раунда. Однако вершины в раунде i+1 должны ждать сортировки следующего якоря (тот, что в раунде i+3), поэтому задержка их сортировки составляет четыре раунда.
Проблема 2: задержка в случае сбоя. Приведенный выше анализ задержки применим к безотказному случаю, с другой стороны, если лидеру раунда не удается достаточно быстро транслировать якоря, якоря не могут быть заказаны (и, следовательно, пропускаются), поэтому все несортированные вершины в предыдущих раундах должны дождаться сортировки следующего якоря. Это может значительно снизить производительность геореплицированной сети, тем более что Bullshark использует тайм-ауты ожидания лидера.
Каркас мелководья
Shoal решает обе эти проблемы с задержкой, улучшая Bullshark (или любой другой протокол BFT на основе Narwhal) путем конвейерной обработки, позволяя использовать якорь в каждом раунде и уменьшая задержку всех неякорных вершин в DAG до трех раундов. Shoal также вводит механизм репутации лидера с нулевыми накладными расходами в DAG, который смещает выбор в пользу быстрых лидеров.
испытание
В контексте протоколов DAG конвейеризация и репутация лидера считаются сложными проблемами по следующим причинам:
Предыдущая конвейерная обработка пытается изменить основную логику Bullshark, но это кажется невозможным по своей сути.
Лидерская репутация, представленная в DiemBFT и формализованная в Carousel, — это идея динамического выбора будущих лидеров (якорей в Bullshark) на основе прошлых показателей валидаторов. В то время как разногласия по поводу личности лидера не нарушают безопасность в этих протоколах, в Bullshark это может привести к совершенно другому порядку, который затрагивает суть вопроса, заключающегося в том, что динамический и детерминированный выбор колесных якорей является решением для достижения необходимого консенсуса. в то время как валидаторы должны согласовать упорядоченную историю, чтобы выбрать будущие якоря.
В качестве доказательства сложности проблемы отметим, что реализация Bullshark, включая текущую реализацию в продакшене, не поддерживает эти возможности.
соглашение
Несмотря на вышеупомянутые проблемы, оказывается, что решения, как говорится, кроются за простотой.
В Shoal мы полагаемся на возможность выполнять локальные вычисления в DAG и реализовывать возможность сохранения и повторной интерпретации информации из предыдущих раундов. Опираясь на основное понимание того, что все валидаторы соглашаются с первым якорем по порядку, Shoal объединяет несколько экземпляров Bullshark, компонуя их последовательно таким образом, что (1) первый якорь по порядку является точкой переключения для экземпляров, и (2) причинно-следственная связь. история якорей используется для расчета репутации лидера.
Конвейерная обработка
Как и в случае с Bullshark, валидаторы априори договариваются о потенциальных якорях, т. е. существует известное отображение F: R -> V, отображающее раунды в лидеры. Shoal запускает экземпляры Bullshark один за другим, так что для каждого экземпляра привязка предопределяется картой F. Каждый экземпляр заказывает якорь, который запускает переключение на следующий экземпляр.
Первоначально Shoal запускает первый экземпляр Bullshark в первом раунде DAG и запускает его до тех пор, пока не будет идентифицирован первый упорядоченный якорь, скажем, в раунде r. Все валидаторы согласны с этим якорем. Следовательно, все валидаторы могут детерминистически согласиться переинтерпретировать DAG, начиная с раунда r+1. Shoal просто запускает новый экземпляр Bullshark в раунде r+1.
В лучшем случае это позволяет Shoal заказывать якорь каждый раунд. Якоря для первого раунда сортируются по первому экземпляру. Затем Shoal запускает новый экземпляр во втором раунде, который сам имеет якорь, упорядоченный экземпляром, затем другой новый экземпляр упорядочивает якоря в третьем раунде, и процесс продолжается. Пожалуйста, смотрите иллюстрацию ниже:
Рисунок 4: Вершины, соответствующие лидерам, определенным F, отмечены короной Первый экземпляр Bullshark сначала интерпретирует DAG с якорями в раундах 1, 3 и 5. Bullshark определяет якоря в раунде 1 (зеленая галочка). mark) является первым, который будет отсортирован в первом экземпляре. (Обратите внимание, что в общем случае этот якорь можно пропустить, в то время как некоторые другие якоря будут отсортированы первыми.) Затем остальная часть первого экземпляра игнорируется, и начинается новый экземпляр Bullshark со 2-го раунда. Точки привязки отмечаются во 2 и 4 раундах.
Репутация лидера
Увеличена задержка при пропуске якорей во время сортировки Bullshark. В этом случае метод Pipelining бессилен, поскольку новый экземпляр нельзя запустить, пока предыдущий экземпляр не заказал привязку. Shoal гарантирует, что соответствующий лидер с меньшей вероятностью будет избран в будущем, чтобы иметь дело с потерянным якорем, используя механизм репутации для присвоения каждому валидатору оценки на основе его истории недавней активности. Валидатору, который отвечает и участвует в протоколе, будет присвоен высокий балл, в противном случае валидатору будет присвоен низкий балл, потому что он может дать сбой, быть медленным или быть вредоносным.
Идея состоит в том, чтобы детерминистически пересчитывать предопределенное отображение F из раундов в лидеров при каждом обновлении результатов, отдавая предпочтение лидерам с более высокими баллами. Чтобы валидаторы согласились с новым сопоставлением, они должны согласовать оценку и, следовательно, историю, используемую для получения оценки.
В Shoal конвейеризация и репутация лидера могут естественным образом сочетаться, потому что они оба используют один и тот же основной метод переосмысления DAG после согласования первого заказанного якоря.
На самом деле, единственное отличие состоит в том, что после сортировки якорей в раунде r валидатору нужно только вычислить новое отображение F' из раунда r+1 на основе причинно-следственной истории упорядоченных якорей в раунде r. Затем валидатор запускает новый экземпляр Bullshark, начиная с раунда r+1, используя обновленную функцию выбора привязки F'. Смотрите изображение ниже:
Рис. 5. Вершины, соответствующие лидерам, обозначенным буквой F, отмечены прозрачными коронами. Первый экземпляр Bullshark заказывает привязку в раунде 1, отмеченную зеленой галочкой, а затем вычисляет новое отображение F' на основе информации из причинно-следственной истории привязки. Лидеры, определяемые F', отмечены цветными коронами.
Нет больше тайм-аутов
Тайм-ауты играют решающую роль во всех детерминированных частично синхронных реализациях BFT на основе лидеров. Однако сложность, которую они вносят, увеличивает объем внутреннего состояния, которым необходимо управлять и наблюдать, что усложняет процесс отладки и требует дополнительных методов наблюдения.
Тайм-ауты также могут значительно увеличить задержку, поскольку важно правильно их настроить, и обычно их необходимо настраивать динамически, поскольку они сильно зависят от среды (сети). Протокол выплачивает неисправному лидеру полный штраф за задержку тайм-аута перед переходом к следующему лидеру. Поэтому установка тайм-аута не может быть слишком консервативной, но если тайм-аут слишком короткий, протокол может пропустить хороших лидеров. Например, мы заметили, что при высокой нагрузке лидеры в Jolteon/Hotstuff были перегружены, и тайм-ауты истекали, прежде чем они могли ускорить прогресс.
К сожалению, протоколы на основе лидеров, такие как Hotstuff и Jolteon, по своей сути требуют тайм-аутов, чтобы гарантировать, что протокол может продвигаться вперед каждый раз, когда лидер терпит неудачу. Без тайм-аута даже разбившийся лидер может навсегда остановить протокол. Из-за невозможности отличить неисправного лидера от медленного лидера во время асинхронности, тайм-ауты могут привести к тому, что валидаторы увидят изменения во всех лидерах без согласованности.
В Bullshark тайм-ауты используются при построении DAG, чтобы во время синхронизации честный лидер добавлял якоря в DAG достаточно быстро, чтобы их можно было заказать.
Мы видим, что конструкция DAG предоставляет «часы» для оценки скорости сети. При отсутствии пауз раунды продолжаются до тех пор, пока nf честных валидаторов продолжают добавлять вершины в DAG. Хотя Bullshark не может сортировать на скорости сети (из-за проблемных лидеров), DAG по-прежнему растет со скоростью сети, несмотря на некоторые проблемы с лидерами или асинхронность сети. В конце концов, когда безупречный лидер достаточно быстро транслирует якоря, вся причинно-следственная история якорей будет упорядочена.
В нашей оценке мы сравнили Bullshark с тайм-аутом и без него в следующих случаях:
Быстрый лидер, то есть как минимум быстрее других валидаторов. В этом случае оба метода обеспечивают одинаковую задержку, поскольку якоря упорядочены, а тайм-ауты не используются.
Ложный лидер, в этом случае Bullshark без пауз обеспечивает лучшую задержку, так как валидаторы будут сразу пропускать его анкоры, а валидаторы с паузами будут ждать их прихода, прежде чем продолжить Expect.
Медленный лидер, это единственный случай, когда у Bullshark лучше показатели таймаута. Это связано с тем, что без паузы анкор может быть пропущен, потому что лидер не может транслировать его достаточно быстро, а с паузой валидаторы будут ждать анкора.
В Shoal избегание тайм-аутов и репутация лидера идут рука об руку. Многократное ожидание медленного лидера увеличивает задержку, а механизм репутации лидера не позволяет медленным валидаторам быть избранными лидерами. Таким образом, система использует узлы быстрой проверки для работы на скорости сети во всех реальных сценариях.
Обратите внимание, что результат невозможности FLP показывает, что ни один протокол детерминированного консенсуса не может избежать тайм-аутов. Мелководье не может обойти этот исход, потому что существует теоретический график враждебных событий, который не позволяет управлять всеми якорями. Вместо этого Shoal возвращается к тайм-ауту после настраиваемого количества последовательных пропусков привязки. На практике это крайне маловероятно.
Общий ответ
В документе Hotstuff популяризирована концепция оптимистического ответа, которая, хотя и не определена формально, интуитивно означает, что протокол может работать на скорости сети в хороших условиях, включая быстрый лидер и синхронную сеть.
Shoal обеспечивает еще лучшее свойство, которое мы называем Universal Response. В частности, в отличие от Hotstuff, Shoal продолжает работать со скоростью сети, даже если лидер выходит из строя в течение заданного количества последовательных раундов или асинхронных циклов, через которые проходит сеть. Более подробное сравнение смотрите в таблице ниже.
Обратите внимание, что универсальная отзывчивость обеспечивает строго лучшие гарантии прогресса в асинхронные периоды и при сбое лидера. При синхронизации с медленным лидером эти свойства несопоставимы, поскольку зависят от того, насколько медленный лидер. Однако, учитывая репутацию лидера, медлительные лидеры редко должны появляться в Shoal.
Оценивать
Мы внедрили Bullshark и Shoal поверх нашей реализации Quorum Store в Narwhal. Подробное сравнение между Shoal, Bullshark и Jolteon можно найти в разделе оценки документа Shoal, где мы приводим некоторые основные моменты.
Во-первых, чтобы продемонстрировать мощь асинхронного построения DAG, мы сравним Bullshark с паузами и без них. Полный документ Bullshark предполагает асинхронную сеть, но обеспечивает режим быстрого пути, что требует пауз во всех раундах. Мы называем эту версию Vanilla Bullshark. Заметим, что для независимых частично синхронных гипотетических версий сети паузы в раундах голосования не требуются. Мы называем эту версию Vanilla Bullshark без таймаута голосования без таймаута голосования, Baseline Bullshark — это версия без таймаута.
На приведенном ниже графике сравнивается влияние тайм-аутов на задержку Bullshark со сбоями и без них. Судя по всему, Baseline Bullshark (без тайм-аута) лучше всего работает в случае сбоя. Без сбоев Baseline Bullshark сопоставим с Vanilla Bullshark без приостановки голосования. Это связано с тем, что, как упоминалось ранее, без механизма репутации лидера тайм-ауты могут иметь преимущество в ситуациях, когда лидер хорош, но медлителен.
Рисунок 6.: Влияние тайм-аутов на задержку Bullshark без сбоев (слева) и со сбоями (справа), с 50 валидаторами в случае сбоя
Затем мы создаем экземпляр Shoal с помощью Baseline Bullshark (без тайм-аута) и демонстрируем улучшение задержки конвейерной обработки и механизма репутации лидера с ошибкой и без нее, а для полноты картины мы также сравниваем ее с Jolteon с сбоем и без него.
На рис. 7 ниже показан безотказный случай, и хотя конвейерная обработка и репутация лидера могут уменьшить задержку по отдельности, их сочетание приводит к наилучшей задержке.
Что касается Jolteon, он не может масштабироваться до более чем 20 валидаторов, и даже если он работает в Quorum Store, его пропускная способность составляет примерно половину пропускной способности Bullshark/Shoal, что устраняет узкое место в распространении данных.
Результаты показывают, что Shoal значительно улучшает задержку Bullshark. Что касается Jolteon, важно отметить, что хотя мы измеряли только задержку консенсуса. Поскольку Jolteon изначально не может работать поверх DAG, для разделения распространения данных требуется дополнительная задержка, которую мы не измеряли. Следовательно, при высокой нагрузке Shoal должен соответствовать сквозной задержке Jolteon.
Рисунок 7: Пропускная способность и задержка без сбоев, Shoal PL и Shaol LR поддерживают только конвейерную обработку и репутацию лидера соответственно.
На рис. 8 ниже показан случай сбоя с 50 валидаторами, где механизм репутации лидера значительно уменьшает задержку, уменьшая вероятность того, что отказавший валидатор будет избран лидером. Обратите внимание, что при 16 сбоях из 50 задержка Shoal была на 65% ниже, чем у базовой версии Bullshark.