Сказ о том, как византийцы криптовалюту придумали

Однажды судьбоносной ночью великая Византийская империя стояла на пороге решающего сражения – страна находилась в упадке, а противник собрал немалые силы. Недаром каждый из генералов, возглавлявших византийские легионы, одержим был нелегкими думами: не подкуплены ли оказались другие, стоит ли еще главнокомандующий на страже родины? Сколько осталось верных византийскому престолу воинов? Впрочем, предателей можно выловить и после – лишь бы не случилось катастрофы, лишь бы сообща действовали завтра верные легионы. Ведь если все верные генералы объявят наступление – враг будет повержен, если решат отступить – сохранят армию, но нельзя допустить, чтобы на поле сражения осталась только часть верных легионов, чего добиваются подкупленные противником командиры. А как узнать численность византийской армии, если не знаешь, кому можно верить?

Итак, встречайте, друзья: Византийская криптографическая задача. Спрашивается, при чем здесь криптография? Все очень просто. Цель генералов из глубокого прошлого – обменяться информацией о численности легионов, причем заранее известно, что, скажем, M из N генералов могут передавать заведомо ложную информацию, и на основе полученных данных выработать неважно какое именно, но – главное – единое для всех верных генералов решение: отступать или принять бой. Разумеется, у столь непростой жизненной ситуации должно быть изящное математическое решение!

В 1982 году Лесли Лампорт, американский ученый и первый лауреат премии Дейкстры, доказал, что если в системе строго больше 2/3 правильно работающих процессоров (или «лояльных генералов»), то достичь согласия вполне возможно, и даже предложил алгоритм, помогающий достичь такой договоренности. Давайте рассмотрим его на частном примере.

Будем рассматривать конкретные числа: M = 1 и N = 4, то есть среди четырех генералов один (например, третий) оказался предателем. Пусть теперь каждый из них отправляет всем остальным численность своего легиона – одно число. Генерал-предатель, чтобы запутать лояльных Византии командиров, может отослать им произвольные числа – обозначим их А, В и С. Теперь каждый генерал имеет вектор чисел – численность всех легионов, которая может быть недостоверной. На произвольные числа N и M это можно обобщить так: каждый из М предателей отсылает произвольные числа, поэтому итоговый вектор может иметь до М недостоверных значений. Обозначим в таблице цифрами численность соответствующих легионов:

Но мы же видим, что сейчас верные Византийскому трону генералы обладают разными сведениями! Необходим еще один обмен информацией: теперь командиры высылают друг другу весь вектор значений. При этом предатель опять может отправить любые числа. Точно так же действуем и для произвольных N и M.

Итак, теперь каждый генерал имеет 4 (или, в произвольном случае, N) вектора значений. А вот сейчас внимательно следите за руками: чтобы определить размер i-того легиона, каждый генерал берет (N – 1) чисел (в нашем случае – 3) – размеры этого легиона, пришедшие от всех, кроме его командира. Если же среди выбранных значений совпадает хотя бы (N – M – 1) чисел (в нашем случае – 2), то это значение добавляется в итоговый вектор, если же таких не обнаружено – численность легиона объявляется нулевой, ведь вполне вероятно, что его командир окажется предателем.

Что получат верные генералы при таком подходе? Итоговый вектор численности для них будет выглядеть одинаково: (1 – 2 – f (А, В, С) – 4), где f (А, В, С) – это одинаковая для всех функция выбора одинаковых значений. Для произвольных N и M вектор будет выглядеть сложнее, и переменных окажется в разы больше, однако факт останется неизменным – зная значения всех векторов и при одинаковой функции выбора лояльные генералы получат одинаковые сведения. Враг будет повержен!

Построение цепочек связанных последовательных блоков – блокчейна – было основано именно на алгоритме решения Задачи Византийских генералов. Впервые оно было использовано в криптовалюте «Биткоин» и позволило с приемлемым уровнем риска получить механизм динамического принятия решений для случая, когда некоторые узлы сети оказываются ненадежными: любая операция с криптовалютой считается состоявшейся лишь после проверки ее формата, заверения подписью «генералов» и объединения в блок с остальными операциями. Выходит, Лесли Лампорт и его византийские генералы придумали решение для любой системы, 1/3 пользователям которой не хватает доверия.