Как Византия создала биткоин или немного математики
2 октября 2017. Разместил: mediapuls
ПОЛЕВОЙ Андрей
Одной из базовых задач современной криптографии остаётся так называемая «задача византийских генералов» (Byzantine fault tolerance (BFT) — о проблеме взаимодействия нескольких абонентов, которые получили приказ из центра. Причём несколько абонентов — и даже центр — могут оказаться на стороне врага. В таких условиях необходимо выработать единую стратегию действий, которая будет выигрышной для абонентов.
В художественном варианте ситуация выглядит следующим образом:
Византийская армия состоит из нескольких легионов, каждым из которых командует свой генерал. Также, у армии есть главнокомандующий, которому генералы подчиняются. Любой из генералов — и даже главнокомандующий — могут оказаться предателями Византии, заинтересованными в её поражении.
Ночью каждый из генералов получает от главнокомандующего приказ о варианте действий в некоторое время, а именно: «атаковать» или «отступать».
При этом возможны следующие варианты развития событий
Возможные исходы сражения:
Если все верные генералы атакуют — Византия уничтожит противника (благоприятный исход).
Если все верные генералы отступят — Византия сохранит свою армию (промежуточный исход).
Если некоторые верные генералы атакуют, а некоторые отступят — противник уничтожит всю армию Византии (неблагоприятный исход).
Также следует учитывать, что если главнокомандующий — предатель, то он может дать разным генералам противоположные приказы, чтобы обеспечить уничтожение армии.
Следовательно, генералам лучше не доверять его приказам.
Если каждый генерал будет действовать по собственному разумению, случайным образом, то вероятность благоприятного исхода весьма низка.
Для координаций действий генералы нуждаются в обмене информацией между собой, чтобы прийти к единому решению — и по возможности избежать рисков, связанных с недоверием друг другу и центру.
Определение и решение задачи византийских генералов в самом общем виде может быть описано так.
N византийских генералов готовятся атаковать врага. У них есть стабильная связь. При этом из N генералов M являются предателями, и пытаются внести максимальный хаос в решения, которые передаются по стабильной связи.
Согласие византийских генералов будет достигнуто тогда, когда все лояльные генералы узнают о численности других лояльных армий, и придут к единому мнению относительно состояния армий генералов-предателей. В таком случае будет возможным выработать стратегию, благодаря которой Византия победит. Или, в худшем случае, согласовенно отступит и сохранит войска.
Допустим, что из четырёх византийских генералов (N=4) один окажется предателем (M=1). Для нейтрализации вреда предателя всем генералам необходимо сделать такие действия.
Во-первых, каждый генерал посылает собратьям сообщение, в котором указывает численность своей армии. Лояльные генералы указывают истинное количество, а предатели могут указывать различные числа в разных сообщениях.
Генерал 1 указал число 1 (тысяча воинов), генерал 2 указал число 2, генерал 3 (предатель) указал трём остальным генералам соответственно случайные числа x, y, z, а генерал 4 — указал 4.
Во-вторых, каждый генерал формирует из имеющейся информации вектор.
Вектор 1 (1,2,x,4)
Вектор 2 (1,2,y,4)
Вектор 3 (1,2,3,4)
Вектор 4 (1,2,z,4)
Каждый генерал передаёт полученный вектор коллегам, причём генерал-предатель 3 снова искажает данные.
После этого у каждого генерала есть по четыре вектора, формирующие матрицу:
g1
g2
g3
g4
(1,2,x,4) (1,2,x,4) (1,2,x,4) (1,2,x,4)
(1,2,y,4) (1,2,y,4) (1,2,y,4) (1,2,y,4)
(a,b,c,d) (e,f,g,h) (1,2,3,4) (i,j,k,l)
(1,2,z,4) (1,2,z,4) (1,2,z,4) (1,2,z,4)
После чего каждый генерал определяет размер каждой армии.
Чтобы определить размер i-й армии, генерал берёт три числа — размеры этой армии, пришедшие от всех командиров, кроме командира самой i-й армии. Если какое-то значение повторяется среди этих трех чисел как минимум дважды или более, то оно помещается в результирующий вектор, иначе соответствующий элемент результирующего вектора помечается как неизвестное.
По результатам обмена каждый из лояльных генералов должен получить вектор целых чисел длины n, в котором i-й элемент либо равен истинной численности i-й армии (если её генерал лоялен), либо содержит дезинформацию о численности i-й армии (если её генерал предатель). При этом векторы, полученные всеми лояльными командирами должны быть полностью одинаковы.
В результате обмена все лояльные генералы получают один вектор (1,2,f(x,y,z), 4), где f(x,y,z) есть функция, число, которое встречается как минимум два раза среди значений (x,y,z), или «неизвестность», если все три числа (x,y,z) различны.
Поскольку значения x,y,z и их функция f(x,y,z) у всех лояльных генералов одни и те же, то согласие достигнуто.
Где это используется?
В самой популярной (и ряде других) криптовалюте биткоин — одном из самых главных информационных поводов этого года. Масса народа бросилась майнить биткоины с целью успеть на далеко ушедший «поезд» этого квазифинансового инструмента, для чего совсем не обязательно разбираться в деталях математической логики биткоинов.
В основе которой лежит задача византийских генералов.
Которая, в случае биткоина, расширена до неограниченного количества «генералов», при сохранении принципа обмена информацией.
В основе биткоина лежит технология блокчейн — «цепочка блоков». Блоки, из которых состоит цепочка — это специальные структуры, созданные в соответствии с конкретным алгоритмом, которые содержат запись всех транзакций, обмена информацией, между «генералами». Транзакция считается завершённой и достоверной («подтверждённой»), когда проверены её формат и подписи «генералов», и когда сама транзакция объединена в группу с несколькими другими и записана в специальную структуру — блок. Содержимое блоков может быть проверено, так как каждый блок содержит информацию о предыдущем блоке.
Все блоки выстроены в одну цепочку, которая содержит информацию обо всех совершённых когда-либо операциях в базе.
Блок состоит из заголовка и списка транзакций-действий в объединенной сети. Для того, чтобы «компактифицировать» информацию в блоке и его связи с другими блоками, используется хеш-функция. Хэширование — это преобразование массива входных данных в битовую строку фиксированной длины, выполняемое определённым алгоритмом.
Функция, реализующая алгоритм и выполняющая преобразование, называется «хеш-функцией. Результат преобразования (выходные данные) называется «хешем». Особенность хеша в том, что при изменении исходного текста даже на один знак, полностью меняется результат хеш-функции. Это свойтво хеш-функций позволяет применять их для подтверждения подлинности и цельности сообщения.
Каждый блок «цепочки блоков» включает в себя свой хеш, хеш предыдущего блока, хеши транзакций и дополнительную служебную информацию.
Примерно как в задаче византийских генералов. Из которой, кстати, проистекает интересное свойство биткоина.
Математик Лесли Лампорт доказал, что в «генштабе» с N генералами, согласия можно достичь только если число генералов-предателей не превышает N/2 минус 1 генерал. Эта зависимость работает и в биткоинах — она называется проблема 51%.
Если в распоряжении «предателей» находится больше мощности, чем у лоялистов, то последние не смогут выстроить корректную функцию из-за нехватки истинных данных.
В случае биткоина, это позволит «предателю» избирательно подтверждать чужие блоки, подтверждая только свои, а значит получить контроль над созданием новых блоков-биткоинов.
Впрочем, на данный момент для осуществления такой атаки в сети Bitcoin требуется вычислительная мощность во много раз превышающая мощность всех суперкомпьютеров мира. И, как и в случае генштаба, в котором предателей больше, чем лоялистов, при возникновении такой ситуации на практике проблемы будут лежать в совершенно иной плоскости, нежели коммуникация.
Вернуться назад