Византийская отказоустойчивость

Материал из Minter Wiki


Византийская отказоустойчивость (англ. Byzantine fault tolerance) - свойство, которым обладает распределенная компьютерная сеть (Wide Area Network), направленное на функционирование по установленным правилам и обеспечение стабильного достижения определенного консенсуса, даже несмотря на то, что вредоносные узлы системы отказывают передавать данные или распространяют неверную информацию другим участникам сети.

История

Все началось с "Задачи двух генералов (1975 год)":

  • Два союзных предводителя (генерала) атакуют одного врага;
  • Первый генерал лидер, второй – последователь;
  • Войско каждого генерала слишком маленькое чтобы победить врага, им нужно атаковать только вместе. Этот сценарий выглядит просто, но есть некоторая загвоздка, а именно: для координации действий каждый генерал должен иметь гонцов, которые будут бегать и сообщать союзникам о планах наступления, ведь может быть сценарий, когда одна армия пойдет вперед, а другая будет стоять на месте. Итог - поражение. Посланник не должен быть захвачен врагами!
  • Даже если первое послание будет доставлено, то другой генерал должен подтвердить тот факт, что он осведомлен (acknowledge). Для этого необходимо отправить собственного гонца обратно;
  • Таким образом, он вызывает предыдущий сценарий, который может работать бесконечно долго:
2 генерала.png

Как итог - доказательство что "Задача двух генералов" не имеет решения.

Задача Византийских Генералов

В 1982 году Шостак, Лэмпорт и Пиз усложнили задачу:

  • Количество генералов больше двух;
  • Среди генералов могут быть предатели - они могут солгать о своих намерениях;
  • Для достижения полного консенсуса командир и подчиненный должны договориться об одном решении;
  • Если даже генерал предатель, консенсус все равно должен быть достигнут в процессе взаимодействия людей, которые ниже по рангу (капитаны, лейтенанты).

Решение (на примере подчиненных):

  • Командир отправляет свое решение каждому лейтенанту;
  • Если подчиненный не получает задание, или отказывается его исполнять, то он использует функцию ОТСТУПИТЬ;
  • В итоге консенсуса можно достигнуть только в том случае, когда 2\3 участников будут честны и подтвердят назначение командира.

Данная задача в разы сложнее, но у нее решение есть.

Применение в блокчейне

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

Если "Византийская отказоустойчивость" отсутствует в сети, то одноранговый узел может самостоятельно создавать и подтверждать ложные транзакции, тем самым дискредитировать всю систему. В этом случае децентрализация играет негативную роль, так как здесь нет контролирующего органа, который мог бы взять на себя ответственность подтвердить или отменить те или иные действия для того, чтобы исправить или предотвратить ущерб.

Когда Сатоши Накамото изобрел биткойн, то одним с первых решений, использованных им, было доказательства работы вероятностного решения задачи "Византийских генералов".

Выводы

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

Hyperledger, Cosmos Network, Minter, Zilliqa - все эти проекты используют "Византийскую отказоустойчивость" в качестве основного компонента своей инфраструктуры.

См. также

Epidemia.jpg
Author of this article is Epidemia
You could find out the author's contact information in profile.