Технический взгляд на алгоритм Facebook LibraBFT Consensus

Краткое описание

  • Блокчейн Libra будет использовать надежную и эффективную систему репликации конечного узла под названием LibraBFT
  • LibraBFT относится к классу согласованных алгоритмов BFT. Он основан на другом согласованном алгоритме под названием HotStuff [2], который в свою очередь заимствует часть своей согласованной логики из еще одного классического алгоритма BFT под называнием практическая византийская устойчивость к ошибкам pBFT.
  • LibraBFT является усовершенствованной версией HotStuff с подробной спецификацией и реализацией механизма Pacemaker. Он также является анализом жизнеспособности, который состоит из конкретных границ для совершения транзакции

Обзор Блокчейна Libra

На днях Facebook представил свою новую криптовалюту Libra с низкой волатильностью, основанную на платформе умного контракта, которая разработана с целью быть «безопасной, масштабируемой и надежной».

Libra Blockchain использует надежную и эффективную систему репликации конечных узлов под названием LibraBFT [1], которая является центром этого технического анализа. Мы обсудим его свойства и сравним его с другими общепринятыми протоколами византийской отказоустойчивости (BFT) с аналогичными свойствами.

Классический и Накамото консенсус

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

  • Алгоритмы в Накамото — этот класс консенсусных алгоритмов популяризируемый биткойном, который случайным образом выбирает лидера с помощью криптографической головоломки и отправляет блок транзакций вместе с доказательством работ (PoW) всем другим участникам сети. Заключительное решение склоняется в сторону к более длинной цепочки, в которой наибольшее количество доказательств работ (PoW). Если большая часть цепи контролируется честными транзакциями, данная цепь будет расти быстрее всех и опережать любые конкурирующие цепочки.

 

  • Классические алгоритмы консенсуса — в этом классе алгоритмов участники достигают консенсуса, используя множественные циклы обмена сообщениями с правом голоса и с доказательством безопасности. Основная часть процесса должна согласовать голоса и доказательства безопасности, чтобы достичь консенсуса.

Классические консенсусные алгоритмы приходят к соглашению следующим образом.

Срок действия — если p передает сообщение m с правильным процессом, то в конечном итоге доставляет сообщение m.

Соглашение — если сообщение к m доставляется с каким-либо правильным процессом, то в конечном итоге доставляется с каждым правильным процессом.

Целостность — ни один правильный процесс не доставляет одно и то же сообщение более одного раза; более того, если сообщение доставляется с правильным процессом к исообщение от p к mявляется верным, то m оповестит p.

Общий порядок — предположим для сообщений m1 и m2, что p и q — два правильных процесса, которые доставляют m1 и m2 . Тогда pдоставляет m1 до m2 только тогда, когда q доставляет m1 до m2.

Крах и византийские неудачи

Когда сеть с несопоставимыми процессами участвует в согласованном консенсусе, возникают сбои. Например, процессы могут прекратить работу аварийно, может произойти сбой питания, сбой сети или процесс просто не сможет прийти к соглашению. Как правило, они классифицируются как аварийные сбои . С другой стороны, некоторые процессы могут преднамеренно действовать злонамеренно, чтобы достичь консенсуса в свою пользу. Такие неудачи называются византийскими неудачами. Согласованные алгоритмы, которые допускают византийские неудачи, называются алгоритмами византийской отказоустойчивости (BFT). Согласованные алгоритмы BFT также способны автоматически обрабатывать сбои.

Разрешенные и запрещенные сети

Сеть процессов участвующие в согласованном процессе, могут быть сконфигурированы как разрешенные или запрещенные.

  1. Разрешенная сеть. В разрешенной сети идентификация и количество процессов в сети известны всем процессам. Таким образом, процесс может доверять сообщению исходящее от другого процесса в той же сети. Хотя процессы могут выходить из сети и присоединяться к ней по желанию, их идентификационные данные должны быть известны априори всем процессам в сети.
  2. Запрещенные сети без права доступа. В сети без прав доступа ни идентификаторы процессов, ни их количество не известны другим процессам. Таким образом, когда новый процесс присоединяется к сети, он должен предоставить некоторую форму подтверждения работы, чтобы подтвердить свое участие в других процессах.

Libra Blockchain будет настроен как разрешенная сеть при запуске с известным набором процессов, под названием валидаторы. Это означает, что все валидаторы в сети Libra знают личность друг друга.

LibraBFT, HotStuff, pBFT и Tendermint

LibraBFT относится к классу согласованных алгоритмов BFT. Он основан на другом согласованном алгоритме под названием HotStuff [2], который, в свою очередь заимствует часть своей согласованной логики из еще одного классического алгоритма BFT, под названием Practical Byzantine Fault Tolerance, pBFT [3].

Практическая византийская устойчивость к ошибкам

pBFT использует системную модель, которая предполагает асинхронную распределенную систему, в которой процессы связаны сетью. Сеть может не доставлять сообщения, задерживать их, дублировать их или доставлять их не по порядку. Если N — общее количество процессов в сети, а f — количество неисправных (в том числе византийских) процессов, тогда pBFT требует:

N ≥ 3f + 1

чтобы обеспечить устойчивость против византийских неудач.

Алгоритм согласования pBFT хорошо себя зарекомендовал в мульти-циклах, где каждый цикл достигает согласия на этапах процесса согласования. На рис. 1 показаны согласованные циклы pBFT, которые выглядят следующим образом.

  1. Клиент C отправляет запрос на совершение операции к первичному процессу 0 . Это лидер данного консенсуса.
  2. 1, 2 и 3 — процессы называемые репликами.
  3. Реплики выполняют запрос и отправляют ответ клиенту.
  4. Клиент ожидает f + 1 ответов от разных реплик с одинаковым результатом;

Протокол гарантирует жизнеспособность , если лидер не выйдет из строя/откажется. В случае выхода из строя лидера, запускается протокол изменения вида по истечении тайм-аута, чтобы предотвратить постоянное ожидание реплик сообщений от лидера. В географически распределенной асинхронной сети, сбои лидера могут быть более распространенными чем можно себе представить, поэтому триггеры смены также могут быть обычным явлением. Таким образом, сложность выполнения pBFT с изменением вида составляет O ( n 3), где n — количество процессов в сети.

Протокол обеспечивает безопасность, если все исправные реплики вычисляют и выдают один и тот же результат. Это означает, что процессы ( Nf ) должны вычислить один и тот же результат и отправить результаты клиенту, чтобы гарантировать безопасность.

HotStuff

Алгоритм согласования HotStuff пытается решить проблему сложности O ( n 3) pBFT. Свойство жизнеспособности требует, чтобы ( N-f ) исправные реплики выполняли команды одинаково и каждой команда выдавала одинаковый ответ для. Как это часто бывает с частично синхронной моделью связи, в соответствии с которой известное ограничение — ∆ — на передачу сообщений сохраняется после некоторого неизвестного времени (GST). В этой модели N ≥ 3f + 1 требуется, чтобы исправные реплики согласовали одни и те же команды в одном и том же порядке и прогресс может быть обеспечен детерминистически только после GST. HotStuff улучшает pBFT со следующими двумя дополнительными свойствами.

  1. Изменение линейного вида — после GST любой лидер с правильным процессом, отправляет только O (n) аутентификатор для принятия согласованного решения. Это включает случай, когда лидер процесса заменяется. Следовательно, нагрузка на сеть для достижения консенсуса после GST является O (n2) аутентификатором, который в худшем случае является сбоем каскадного лидера.
  2. Оптимистическая отзывчивость. После GST любому правильному лидеру, назначенному однажды нужно ждать только первые (N — f) ответы, чтобы гарантировать, что он может создать предложение, которое будет прогрессировать. Это включает случай, когда лидер процесса заменяется.

В приведенной ниже таблице показано улучшение сложности сообщения. С правильным лидером сложность улучшилась с O (n2) до O (n). С отказом лидера и получающимся протоколом изменения вида сложности улучшилась от O (n3) до O (n).

Сравнение сложности сообщений некоторых классических алгоритмов согласования BFT.

В pBFT каждый цикл консенсуса выполняет аналогичную работу (например сбор голосов от реплик и т. Д.), которую HotStuff оптимизирует путем создания цепочки сертификатов кворума(QC), как показано на рис. 2. Таким образом, циклы консенсуса могут быть объединены в цепочку, что повышает жизнеспособность . Для k -изменений требуется k + 2 цикла вместо 2 * k.

Цепочка HotStuff

HotStuff также включает механизм под названием Pacemaker, который гарантирует жизнеспособность сети после GST. Кардиостимулятор а) синхронизирует все правильные реплики уникального лидера в общую длину транзакции в течение достаточно длительного периода времени. Он выбирает уникального лидера таким образом, что правильные синхронизированные реплики будут прогрессировать с выбранным лидером. Этот механизм отделяет жизнеспособность от протокола, который в свою очередь отделяет его от безопасности .

LibraBFT

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

В LibraBFT процессы называются валидаторами и они прогрессируют в раундах, каждый из которых имеет назначенного валидатора именуемым лидером. Лидеры несут ответственность за предоставление новых блоков и получение подписанных голосов от валидатора по их предложению. LibraBFT следует модели Chained HotStuff, описанной на рис. 2, который работает следующим образом.

  1. Цикл — это коммуникационная фаза с одним назначенным лидером, а предложение лидеров объединяются в цепочку с использованием криптографических хэшей.
  2. В течение цикла лидер предлагает блок, который дополняет самую длинную цепочку, которую он знает.
  3. Если предложение является действительным и своевременным, каждый честный узел подпишет его и отправит на голосование лидеру.
  4. После того, как лидер набрал достаточно голосов для достижения кворума он объединяет голоса в Сертификат кворума (QC), который снова дополняет ту же цепочку.
  5. QC транслируется каждому узлу.
  6. Если лидеру не удается собрать QC, участники берут тайм-аут и переходят к следующему циклу.
  7. В конце концов, достаточное количество блоков и контроля качества будет своевременно дополнять цепочку и блок будет соответствовать правилу фиксации протокола.
  8. По завершению, цепочка с незафиксированными блоками до соответствующего блока становятся зафиксированными.

Вышеуказанный процесс согласования можно сравнить с другим популярным классическим алгоритмом согласования BFT, Tendermint [4], который показан на рис. 3.

Процесс достижения консенсуса Tendermind

Как и LibraBFT, Tendermint работает так что — перед голосованием, с предварительной фиксацией он собирает подписи валидатора для каждого цикла, аналогично QC в LibraBFT. Основное различие между этими двумя алгоритмами состоит в том, что в Tendermint каждый цикл имеет тайм-аут и валидаторы ждут, даже если один из них заканчивает цикл раньше, тогда как в LibraBFT сеть является синхронной и скорость протокола зависит от задержки сети.

Протокол завершается без ожидания тайм-аута, только если лидер верен. Если он терпит неудачу, протокол изменения вида срабатывает после GST и хотя изменение вида является линейным и оптимизируется по сравнению с pBFT, он может работать не лучше, чем реализация Tendermint.

Практическое значение LibraBFT

Валидаторы-основатели включают в себя Uber, Visa, MasterCard, PayPal и т. Д. Члены-основатели обязаны соблюдать строгие правила, чтобы быть частью Валидаторов. Например, крипто хедж-фонды должны были иметь AUM свыше 1 миллиарда долларов, в то время как хранители ориентированные на цифровые активы, должны были хранить не менее 100 миллионов долларов. Некриптовым фирмам необходимо иметь рыночную капитализацию более 1 миллиарда долларов или баланс клиентов равный более 500 миллионам долларов. При наличии таких строгих требований можно предположить, что валидаторы с большей вероятностью будут работать в центрах обработки данных с частной или высоконадежной сетью, соединяющей их. Вероятно всего они устойчивы к сбоям, необходимой для запуска Cosmos Validators (в которых используется алгоритм консенсуса Tendermint). Все другие улучшения конструкции могут быть менее полезны при практическом развертывании, описанном выше. С другой стороны если предполагается, что сеть ненадежна, предположения о правильности лидеров для быстрого завершения процесса могут фактически потерпеть неудачу, что приведет к ухудшению производительности.

Рекомендации

  1. LibraBFT — https://developers.libra.org/docs/assets/papers/libra-consensus-state-machine-replication-in-the-libra-blockchain.pdf
  2. Консенсус HotStuff BFT — https://arxiv.org/pdf/1803.05069.pdf
  3. Практическая византийская терпимость к ошибкам — http://pmg.csail.mit.edu/papers/osdi99.pdf
  4. Алгоритм консенсуса нежной мяты — https://arxiv.org/pdf/1807.04938.pdf

Наш канал в телеграм. Присоединяйтесь!

 

Добавить комментарий

Ваш e-mail не будет опубликован.


7 + 4 =