Шифроденьги

Что такое Byzantine Fault Tolerance (BFT)?

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

Коротко о проблеме Византийских Генералов

Тема объемная, но я постараюсь сделать простую выжимку. Вообщем это мысленный эксперимент в Computer Science с 1982 года в котором дана следующая задача:

"N-ное кол-во генералов, которые думают нападать или не нападать на Римскую империю. При этом среди них ест M-ное кол-во предателей. Если все честные нападут или отступят (главное прийти к общему решению) - то всё будет ок, если хотя бы один из честных не распознает своих и доверится предателям, то Византия проиграет войну.

Вопрос: как честным генералам договорится и прийти к общему решению через удаленный канал связи?"

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

Условия на практике в Интернете

• Задержки в доставке сообщений или асинхронность (как итог неверный порядок cообщений)

• Предатель или плохая нода - это не только нода, которая сломалась (Crash Failures), но и нода, которая способна обманывать (Byzantine Failures)

• Компроментация канала связи (подделка сообщений)

• Спам сообщениями

• Сообщения могут не доходить вообще

Ну добавим сюда еще вызов: не ограничивать количество нод, т.е. сделать систему максимально открытой и децентрализованной

Какие есть решения и в чем различия?

В 1985 году думали, что решения вовсе нет и написали "доказательство" этого. К счастью те исследователи оказались не правы.

Первым решением был алгоритм Paxos, опубликованный в 1989 году. Но этот алгоритм не решал таких проблем, как: спам, компрометация канала связи, и Byzantine Failures, только лишь Crash Failures. И консенсус там достигался только в случае если более 3/4 нод - честные.

Все проблемы Paxos были решены в алгоритме Practical Byzantine Fault Tolerance 1999 года. В дальнейшем PBFT лег в основу алгоритмов консенсуса Hyperledger, Ripple, Stellar и Tendermint. И консенсус достигался уже если более 1/3 нод - честные и при условии, что нет проблем с доставкой сообщений. C появлением Bitcoin впервые решалась проблема Византийских Генералов с неограниченным количеством нод на практике. Однако это свойство несет с собой недостатки, как плохая масштабируемость и отсутствие быстрой "финальности" (речь о том, что надо ждать подтверждения транзакций). Точнее 100% "финальность" недостижима, по факту просто уменьшается вероятность отката транзакции с каждым подтверждением и этого вполне достаточно на практике.

#ликбез