В детской игре «испорченный телефон» достаточно одного шептуна, чтобы фраза превратилась в бессмыслицу. А что, если в сети из сотни компьютеров каждый второй намеренно искажает слова, а некоторые и вовсе сочиняют небылицы? Именно эту головоломку — под названием «византийское соглашение» — десятилетиями разгадывают криптографы. Д.ф.-м.н., профессор Ульяновского государственного университета Сергей Рацеев в своём обзоре объясняет, как честным участникам договориться о едином результате, даже если предатели контролируют половину узлов. Без таких протоколов невозможно представить ни криптовалюты, ни надёжное облачное хранение — ведь там никто не назначает «главного», а полагаться приходится на математику.
В чем суть задачи
Представьте, что у каждого компьютера в сети есть своё число или слово. В конце все честные компьютеры должны выдать одно и то же значение. Если изначально у всех честных было слово «победа», то и результатом должно стать «победа» — это требование достоверности. Кроме того, любые два честных компьютера не могут разойтись: если один выдал «победа», другой не может выдать «поражение». Это требование договорённости. Отдельная, но похожая задача — широковещательная передача. Один компьютер (дилер) рассылает всем своё сообщение. Даже если дилер жулик и шлёт разным людям разную информацию, все честные получатели в итоге должны прийти к одному и тому же значению. Две эти задачи тесно связаны: научившись решать одну, можно решить и другую. Главная трудность — сделать это быстро и без пересылки огромных объёмов данных.
Почему нельзя просто переслать все подряд
Самый простой способ передать длинное сообщение — разбить его на отдельные биты (нолики и единички) и каждый бит обсуждать отдельно. Если в сети 1000 компьютеров и для согласования одного бита нужно переслать примерно миллион бит служебной информации, то для сообщения в мегабайт объём пересылаемых данных станет просто чудовищным — как если бы вы вместо одной фотографии пересылали тысячу её копий разными маршрутами. Поэтому исследователи придумали протоколы расширения. Они позволяют передавать длинные сообщения так, что объём трафика растёт почти пропорционально длине сообщения и числу участников, а не квадрату числа участников. Это как ехать не по всем улицам города подряд, а по оптимальному маршруту.
Когда предателей меньше трети — можно обойтись без криптографии
Если в сети не больше трети жуликов, можно использовать протокол, который защищён даже от самого могущественного противника — хоть с бесконечным компьютером. Один из классических протоколов работает так: сначала все участники рассылают свои биты всем остальным. Затем каждый считает, сколько раз он получил ноль и сколько — единицу. Если единиц пришло больше определённого порога, участник временно решает, что правильный ответ — единица, иначе — ноль. Потом специально выбранный координатор (каждый раунд — новый) сообщает всем свой ответ, и если чей-то ответ слишком сильно отличается от мнения большинства, он его исправляет. После нескольких таких итераций все честные приходят к единому мнению.
Для длинных сообщений этот подход не подходит — слишком много пересылок. Поэтому Сергей Рацеев описывает другой, более хитрый метод. Каждый участник разбивает своё длинное сообщение на несколько кусочков и «упаковывает» их в математическую кривую — многочлен. Это похоже на то, как если бы вы по нескольким точкам восстановили целый график. Затем участники обмениваются между собой значениями этой кривой и строят карту доверия: рисуют связи между теми, кто согласен друг с другом. На этой карте ищут особую фигуру — «звезду». Звезда — это когда есть группа участников (ядро), каждый из которых соединён с другой большой группой. Если звезда найдена, то можно выделить ядро честных, и с помощью той же математической кривой восстановить общее сообщение. Весь процесс занимает всего три раунда обмена, а объём пересылаемых данных растёт линейно с длиной сообщения.
Когда предателей до половины — приходится использовать «отпечатки пальцев»
Если жуликов может быть до половины всех участников, задача становится сложнее. Противник может скоординированно врать так, что честные не смогут определить правду. Здесь на помощь приходят хеш-функции — это такие «сжиматели», которые превращают любое длинное сообщение в короткий уникальный отпечаток. Если два сообщения разные, то их отпечатки почти наверняка будут разными. Вероятность случайного совпадения — одна миллионная доля. Это как сравнить два огромных романа не по тексту, а по короткому резюме — если резюме разные, то и романы точно разные.
Протокол для такого случая работает в три этапа. Сначала все участники публикуют отпечатки своих сообщений. Если не менее n−t человек выдали одинаковый отпечаток, они образуют «клуб согласных». Затем члены этого клуба помогают остальным: каждый, кто не в клубе, получает сообщение от своего «наставника» из клуба. Получатель сверяет отпечаток — если он совпадает с общим, значит, он теперь тоже знает правильное сообщение. Если не совпадает — значит, наставник жулик, и эта парочка заносится в чёрный список. В конце концов формируется новая группа «хороших» участников, большинство из которых честны. На третьем этапе каждый из «хороших» снова кодирует своё сообщение в математическую кривую, но теперь уже более низкой степени (то есть нужно меньше точек для восстановления). Они рассылают всем значения кривой и отпечатки этих значений. Даже те, кто не вошёл в «хорошую» группу, могут отбросить поддельные значения — потому что отпечаток не совпадёт — и по оставшимся точкам восстановить исходное сообщение. Всё это требует чуть больше ресурсов, чем в случае с третью предателей, но всё ещё почти линейно по длине сообщения.
Когда предателей может быть сколько угодно — останавливаем игру
А если жуликов может быть почти столько же, сколько и честных, или даже больше? В такой ситуации добиться гарантированного соглашения невозможно — противник всегда сможет запутать честных. Но можно договориться по-другому: либо протокол успешно завершается и все честные получают одинаковый результат, либо он прерывается, и тогда все честные просто выдают сигнал «ошибка». Никто не обязан получать результат, если обнаружен обман. Это называется безопасным прерыванием и широко используется на практике.
Самый простой протокол с прерыванием работает в два раунда. Дилер рассылает сообщение всем. Затем каждый участник пересылает полученное всем остальным. Если у какого-то участника все пересланные значения совпадают между собой и с тем, что он получил от дилера, он выдаёт это значение. Если есть хоть одно расхождение — выдаёт «ошибку». Этот метод работает при любом числе жуликов, но для длинных сообщений неэффективен: каждый участник вынужден пересылать всем копию всего сообщения, что приводит к квадратичному росту трафика.
Поэтому для длинных сообщений используют другой трюк. Сообщение разбивается на небольшие блоки. Для каждого блока запускается подпротокол, который отслеживает споры: если два участника не согласны о том, какое значение блока правильное, их пара заносится в список спорщиков. В следующих блоках эти двое уже не тратят время на попытки убедить друг друга — они просто игнорируют друг друга. Это резко снижает объём пересылаемых данных. В результате удаётся достичь почти линейной сложности по длине сообщения. Правда, если нужна абсолютная, информационно-теоретическая стойкость (то есть защита даже от бесконечно мощного противника), то объём трафика становится заметно больше — добавляются дополнительные проверки, но зато гарантия стопроцентная.
Что в итоге
Сергей Рацеев в своём обзоре показывает: для любого уровня недоверия — от редких предателей до почти всеобщего хаоса — существует математически строгий протокол, позволяющий честным компьютерам либо прийти к единому мнению, либо хотя бы вовремя остановиться с сигналом ошибки. И самое удивительное, что эти протоколы не требуют гигантских затрат: объём пересылаемых данных растёт почти пропорционально длине сообщения, а не квадрату числа участников. В основе лежат простые идеи: поиск «звезды» в карте доверия, сравнение отпечатков вместо целых текстов, восстановление сообщения по нескольким точкам. Эти методы уже сегодня работают в блокчейнах, децентрализованных базах данных и спутниковых системах. А понимание их пределов помогает инженерам строить более быстрые и надёжные распределённые системы — те самые, на которых держится современный цифровой мир.
Исследование опубликовано в журнале «Прикладная дискретная математика»
