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

Libra блокчейн обзор

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

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

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

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

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

Классические консенсусные алгоритмы удовлетворяют следующим общим свойствам.

Период действия — Если правильный процесс ппередает сообщение м , затем п в конце концов доставляет м ,

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

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

Общий заказ— для сообщений m1 а также м2 предположим п а также Q два правильных процесса, которые доставляют m1 а также м2, затем п обеспечивает m1 до м2 если и только если Qобеспечивает m1 до м2,

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

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

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

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

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

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

LibraBFT, HotStuff, pBFT и Tendermint

LibraBFT относится к классу согласованных алгоритмов BFT. Он основан на другом согласованном алгоритме под названием HotStuff (2), который в свою очередь заимствует часть своей согласованной логики из еще одного классического алгоритма BFT, называемого Практическая византийская устойчивость к ошибкам, pBFT (3).

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

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

N ≥ 3f + 1

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

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

Рис. 1 — согласованные раунды pBFT

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

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

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

Горячая штучка

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

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

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

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

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

Рис. 2 — цепочка HotStuff

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

LibraBFT

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

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

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

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

Рис. 3 — Процесс достижения согласия

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

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

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

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

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

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