Как византийские генералы помогли создать современную криптовалюту

Одним из важнейших критериев надежности вычислительных систем является сохранение работоспособности даже при неполадках в одном или нескольких узлах. Под неполадками в данном случае подразумевается ситуация, когда узел отправляет противоречивые данные в разных направлениях. Для понимания ключевой проблемы современной криптографии – коммуникации абонентов, получающих информацию из центра, – существует ее художественная интерпретация: задача о византийских генералах. Ее решение использовалось при создании биткоина.

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

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

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

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

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

Условие задачи византийских генералов

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

Варианты решения задачи

Предположим, что один из четырех генералов оказался предателем (N = 4 , M = 1). Следовательно, трое верных военачальников пошлют верные сведения о количестве своих легионеров, а в сообщениях предателя цифры могут быть какими угодно. Допустим, первый генерал сообщил, что в составе его легиона есть 1 тысяча воинов, у второго – 2 тысячи, у четвертого – 4 тысячи. Третий генерал (перебежчик) указал остальным случайно выбранные цифры x, y, z.
Из полученных данных каждый военачальник формирует свой вектор:

• 1-й вектор — 1,2,x,4;
• 2-й вектор — 1,2,y,4;
• 3-й вектор — 1,2,3,4;
• 4-й вектор — 1,2,z,4.

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

Затем генералы определяют количество воинов в каждом легионе. Для расчета первого легиона берется три числа: численность этого легиона, известная из сообщений всех генералов за исключением командующего самим первым легионом. Если одно из 3-х чисел повторяется дважды или трижды, оно помещается в итоговый вектор. Если совпадений нет, значение итогового вектора определяется как «неизвестное».

В итоге каждый верный генерал получает свой вектор N, в котором первый элемент равняется действительной численности войск первого легиона (в случае, если его командир не является предателем) или содержит неправдивые данные (если ее генерал работает на врага). При этом векторы всех верных генералов должны получиться идентичными.

Результат выглядит следующим образом: ( 1,2,f (x,y,z), 4 ), где f (x,y,z) – значение, встречающееся как минимум дважды среди чисел x,y,z или «неизвестное» в случае, если все 3 числа различны. Поскольку x,y,z и функция f (x,y,z) у всех верных генералов совпали, следовательно, согласие достигнуто и враг будет разбит.

Практическое применение задачи

Алгоритм решения этой задачи был использован при создании самой популярной криптовалюты – биткоина (ВТС). Так, майнинг цифровых монет и их перераспределение внутри системы происходит с участием византийских генералов, которые обмениваются между собой сводками о состоянии своих войск. Обращение bitcoin осуществляется в децентрализованной сети, построенной на технологии blockchain. Каждый блок создан в соответствии с определенным алгоритмом, содержащим записи обо всех платежных операциях (обмене сообщениями между генералами). Любая операция считается состоявшейся лишь после проверки ее формата, заверения подписью генералов и объединения в блок с остальными транзакциями. Содержимое блоков можно проверить, начиная с самой первой операции, поскольку все они выстроены в последовательную общую цепь.

Блоки состоят из заглавий и перечня завершенных транзакций. Для передачи информации между блоками и их «компактификации» применяется хеш – преобразование вводных данных в бит-строку определенного размера. Для вычисления хеша используется специальный математический алгоритм.

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

Доказательство устойчивости криптовалютных систем

Еще одно свойство биткоина было обнаружено известным американским ученым Лесли Лэмпортом. Он доказал, что согласия в штабе N генералов можно достичь лишь в случае, если количество перебежчиков не превышает N/2 минус один генерал. Это правило, работающее при генерации биткоинов, получило название «правило 51 процента». Говоря проще, если мощности предателей превышают мощности честных генералов, то последние не смогут построить корректную систему векторов по причине недостатка правильной информации. В случае с биткоинами это позволит «перебежчикам» выборочно подтверждать чужие блоки, а значит, контролировать процесс добычи криптовалюты.

Почему же тогда за восемь лет существования еще никому не удалось взломать сеть Bitcoin? Потому что на сегодня для подобной атаки потребуются мощности, многократно превышающие мощности вместе взятых компьютеров мира. И, как и в случае с генеральным штабом, в котором изменников больше, чем лояльных генералов, причины возникновения подобной ситуации будут лежать в абсолютно другой плоскости, нежели обмен информацией.

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