Что такое Byzantine Fault Tolerance (BFT) и какие есть решения?

Что такое 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 нод - честные. Но в PBFT есть одно ограничение - система работает только если все сообщения доставляются, хоть и с задержкой.

C появлением Bitcoin впервые решалась проблема Византийских Генералов с неограниченным количеством нод на практике. Однако это свойство несет с собой недостатки, как плохая масштабируемость и отсутствие быстрой "финальности" (речь о том, что надо ждать подтверждения транзакций). Точнее 100% "финальность"  недостижима, по факту просто уменьшается вероятность отката транзакции с каждым подтверждением и этого вполне достаточно на практике. 

Другие современные протоколы, такие как PoS в Cardano, dPoS в EOS, dBFT в NEO, тоже являются BFT алгоритмами, со своими преимуществами и недостатками, о которых я хочу написать несколько отдельных постов с детальным сравнением. 

Выводы
Алгоритмы dBFT, FBA и dPos имеют фиксированное кол-во генералов, что вызывает критику о централизации и плутократии, зато они быстрые и относительно безопасные. Биткоин же медленный и не масштабируется, но зато это самая честная и децентрализованная система, которая заслужила самый большой кредит доверия.

Я думаю, что не стоит размышлять о том, какие системы победят, а какие проиграют. Я ставлю на то, что Биткоин будет побеждать в функции "цифрового золота" и необходимость в суперскорости отпадет, а также на то, что под каждое приложение - возможно нужен свой блокчейн, со своими правилами, со своими схемами governance. Также как в реальном мире, странах, компаниях - люди организовываются каждый на свой лад и по своим схемам управления. Так и будет происходить в блокчейнах и децентрализованных автономных организациях дальше.

В этой перспективе мне нравится идея о платформах по созданию своих блокчейнов под свое приложение, типо того как делают Cosmos.

Телеграм канал: https://t.me/encryptmymoney