Практическая византийская отказоустойчивость (pBFT)

Практическая византийская отказоустойчивость - это согласованный алгоритм, представленный в конце 90-х Барбарой Лисков и Мигелем Кастро. pBFT был разработан для эффективной работы в асинхронных (без верхней границы, когда будет получен ответ на запрос) системах. Он оптимизирован для сокращения накладных расходов. Его целью было решить многие проблемы, связанные с уже доступными решениями Visantine Fault Tolerance. Области применения включают распределенные вычисления и блокчейн.

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

Проблема византийских генералов
Проблема была точно объяснена в статье ЛЕСЛИ ЛАМПОРТА, Роберта Шостака и МАРШАЛЛА ПИЗА из Microsoft Research в 1982 году:

Imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messenger. After observing the enemy, they must decide upon a common plan of action. However, some of the generals may be traitors, trying to prevent the loyal generals from reaching an agreement. The generals must decide on when to attack the city, but they need a strong majority of their army to attack at the same time. The generals must have an algorithm to guarantee that (a) all loyal generals decide upon the same plan of action, and (b) a small number of traitors cannot cause the loyal generals to adopt a bad plan. The loyal generals will all do what the algorithm says they should, but the traitors may do anything they wish. The algorithm must guarantee condition (a) regardless of what the traitors do. The loyal generals should not only reach agreement, but should agree upon a reasonable plan.

Византийская отказоустойчивость может быть достигнута, если правильно работающие узлы в сети согласовывают свои значения. Отсутствующим сообщениям может быть присвоено значение голоса по умолчанию, т. Е. Мы можем предположить, что сообщение от определенного узла является «ошибочным», если сообщение не получено в течение определенного периода времени. Кроме того, мы также можем назначить ответ по умолчанию, если большинство узлов ответят правильным значением.

Лесли Лэмпорт доказал, что если у нас есть 3m + 1 правильно работающих процессоров, консенсус (соглашение об одном и том же состоянии) может быть достигнут, если не менее m процессоров неисправны, что означает, что строго более двух третей от общего числа процессоров должны быть честными.

Типы византийских неудач:
Рассматриваются две категории отказов. Один из них - отказоустойчивый (при котором узел выходит из строя и перестает работать), а другой - отказ произвольного узла. Некоторые из случайных отказов узлов приведены ниже:

• Невозможность вернуть результат
• Ответить с неверным результатом
• Ответить заведомо вводящим в заблуждение результатом
• Отвечайте разным результатом на разные части системы

Преимущества ПБФТ:

• Энергоэффективность : pBFT может достичь распределенного консенсуса без выполнения сложных математических вычислений (как в PoW). Zilliqa использует pBFT в сочетании с комплексными вычислениями, подобными PoW, для каждого сотого блока.
• Сделка завершенность: Операции не требуют несколько подтверждений (например , в случае механизма ПР в Bitcoin , где каждый узел индивидуально проверяет все транзакции перед добавлением нового блока к blockchain; Подтверждение может занять от 10-60 минут , в зависимости от того , сколько лиц подтверждения новый блок) после их доработки и согласования.
• Низкая дисперсия вознаграждения : каждый узел в сети участвует в ответе на запрос клиента, и, следовательно, каждый узел может быть стимулирован, что приводит к низкой дисперсии в вознаграждении узлов, которые помогают в принятии решений.

Как работает pBFT?
pBFT пытается обеспечить практическую репликацию византийского конечного автомата, которая может работать, даже когда в системе работают вредоносные узлы.
Узлы в распределенной системе с поддержкой pBFT упорядочиваются последовательно: один узел является первичным (или ведущим узлом), а другие называются вторичными (или резервными узлами). Обратите внимание, что любой подходящий узел в системе может стать основным путем перехода от вторичного к первичному (как правило, в случае отказа первичного узла). Цель состоит в том, чтобы все честные узлы помогли достичь консенсуса относительно состояния системы с использованием правила большинства.
Практическая византийская отказоустойчивая система может функционировать при условии, что максимальное количество вредоносных узлов не должно быть больше или равно одной трети всех узлов в системе. По мере увеличения количества узлов система становится более безопасной.

Раунды консенсуса pBFT разбиты на 4 фазы (см. изображение ниже):

• Клиент отправляет запрос на основной (ведущий) узел.
• Основной (ведущий) узел передает запрос всем вторичным (резервным) узлам.
• Узлы (первичный и вторичный) выполняют запрошенную услугу, а затем отправляют ответ клиенту.
• Запрос успешно обслуживается, когда клиент получает m + 1 ответов от разных узлов в сети с одинаковым результатом, где m - максимально допустимое количество неисправных узлов.

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

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

  • Атаки Сибиллы : механизмы pBFT восприимчивы к атакам Сивиллы, когда одна сущность (сторона) контролирует множество идентификаторов. По мере увеличения числа узлов в сети, атаки Сивиллы становится все труднее выполнять. Но поскольку механизмы pBFT также имеют проблемы с масштабируемостью, механизм pBFT используется в сочетании с другим механизмом (ами).
  • Масштабирование : pBFT плохо масштабируется из-за накладных расходов на связь (со всеми другими узлами на каждом этапе). По мере увеличения количества узлов в сети (увеличивается как O (n ^ k), где n - сообщения, а k - количество узлов), увеличивается и время, необходимое для ответа на запрос.

  
  Платформы, использующие варианты pBFT:

  • Zilliqa - pBFT в сочетании с консенсусом PoW
  • Hyperledger Fabric - разрешенная версия pBFT
  • Tendermint - pBFT + DPoS (Делегированное доказательство ставки)

  
  Варианты pBFT:
  Чтобы повысить качество и производительность pBFT для конкретных случаев и условий использования, было предложено и применено множество вариантов. Некоторые из них :

  • RBFT - Резервный BFT
  • РЕФЕРАТЫ
  • Q / U
  • HQ - протокол гибридного кворума для BFT
  • Адаптировать
  • Зиззива - Спекулятивная византийская отказоустойчивость
  • Трубкозуб