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

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

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

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

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

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

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

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

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

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

Соглашение — если сообщение к 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.

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. По завершению, цепочка с незафиксированными блоками до соответствующего блока становятся зафиксированными.

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