Zero-Knowledge Proof: Доказательство с нулевым разглашением для гамильтонова цикла

Zero-Knowledge Proof (ZKP или Доказательство с нулевым разглашением) - это передовая технология, которая уже используется во многих современных продуктах, которыми вы даже может быть пользовались. Давайте посмотрим, как это работает на примере абстрактных задач, а после попробуем решить уже вполне конкретную, используя графы и их свойства.

Что такое доказательство с нулевым разглашением?

Думаю, что сухое определение - это явно не то, зачем вы сюда пришли. Поэтому давайте взглянем на примеры, которые в своё время помогли лично мне понять в какой области задач можно применять ZKP:

Пример 1. Базовый.

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

Чтобы доказать, что Алиса действительно знает пароль от почтового ящика, она отворачивается, просит Боба написать на листочке любое число и бросить его в её ящик. После этого Алиса просит Боба отойти, открывает свой почтовый ящик с помощью пароля и говорит вслух число Боба.

Алиса доказала Бобу, что знает пароль, а Боб не получил никакой конфиденциальной информации Алисы. Хотя более корректно будет сказать, что Боб вообще не получил никакой новой информации.

Пример 2. Расширенный.

Айтишники имеют небольшое преимущество в понимании ZKP, так как есть очень простая аналогия. Представим у вас есть пароль mycoolpassword. Вы вычислили значение хеш-функции sha256 от него: 835d052d985517cb1fa5fc4bf44228f898f7a2233383feaf5cd23ea2fd9b2a3f.

Доказательством с нулевым разглашением будет такое решение, которое позволит доказать, что вы знаете захешированное значение в 835d052d985517cb1fa5fc4bf44228f898f7a2233383feaf5cd23ea2fd9b2a3f не разглашая само это значене (тот самый пароль mycoolpassword).

К сожалению, я не смогу привести доказательство с нулевым разглашением для этой задачи в рамках данной статьи, поскольку оно очень сложное, но этот пример показывает логику ZKP и где их можно применять.

Кто-то сказал графы?

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

Что такое граф?

Обычно, графы изображают (простите за каламбур) графически. Выглядит это как-то так:

0, 1, 2, 3, 4, 5, 6 - это вершины графа.
0-1, 0-2, 1-2, 1-3 и т. д. - это рёбра графа (попарное соединение вершин).

Список смежности

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

Путь в графе

На примере данного графа 0-1-2 - это путь.

А 0-2-6 - нет, потому что даже учитывая, что существует соединение между вершинами 0 и 2, соединения между вершинами 2 и 6 нет (нет такого ребра).

Гамильтонов путь

Например, в нашем графе есть такой гамильтонов путь 0-1-3-4-2-5-6:

Гамильтонов цикл

В нашем графе вершина под номером 6 не имеет второго ребра и поэтому граф априори не может иметь гамильтонов цикл.

Для примера рассмотрим другой граф:

В этом графе можно найти следующий гамильтонов цикл: 1-4-3-2. Последняя вершина пути (вершина 2) имеет общее ребро с первой вершиной пути (вершиной 1).

ZKP и графы

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

Задача

У Боба есть граф G. Боб заказал у Алисы поиск гамильтонова цикла в своём графе за 100 рублей. Алиса нашла гамильтонов цикл, но сначала хочет получить от Боба оплату, поскольку после его разглашения Боб может получить решение и не заплатить за него.

Нужно помочь Алисе доказать, что она знает гамильтонов цикл в графе Боба без его разглашения.

Решение

В глянем на решение Алисы в графе Боба:

Алиса нашла цикл a-b-c-d-e-f-g. Вершина g имеет общее ребро с вершиной a, поэтому это точно гамильтонов цикл. Давайте построим список смежности для этого графа:

Чтобы помочь Алисе нам потребуется сделать изоморфный граф. Грубо говоря мы просто возьмём все вершины и перемешаем их названия. Из такого определения легко понять, что свойства графа никак не изменятся, поскольку связи между вершинами (пусть и переименованными) остаются неизменными.

Опишем найденный ранее гамильтонов цикл с помощью новых названий вершин: f-g-a-e-d-c-b.

Таблица смежности для нового графа будет выглядеть таким образом:

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

Теперь мы можем предоставить такой граф Бобу. У него есть возможность задать один из двух вопросов:

• Точно ли этот граф изоморфный? (Алиса покажет, как именно она поменяла вершины)

• Точно ли в таком графе есть гамильтонов цикл? (Алиса покажет гамильтонов цикл в изоморфном графе)

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

Если Боб задаёт вопросы полностью случайно, то Алиса не знает какой вопрос задаст Боб. Соответственно, если Алиса пытается соврать, то она сможет подготовить ответ только на один вопрос:

• либо то, что граф изоморфный (но тогда если Боб спросит гамильтонов цикл, то Алиса правильно ответить не сможет)

• либо то, что гамильтонов цикл в графе есть (но тогда если Боб спросит об изоморфности, то Алиса не сможет доказать Бобу, что это его исходный граф)

Получается, вероятность, что Алиса угадает вопрос и подстроит под него решение - 1/2.

Далее Алиса и Боб могут повторять эту процедуру нужное Бобу количество раз. Если вероятность Алисы успешно соврать 1/2, то для 2 прогонов такого сценария 1/2 * 1/2 = 1/4 и так далее.

А теперь на языке математики

Обозначим исходный граф Боба G с вершинами V как G(V). Тогда можем обозначить найденый гамильтонов цикл как функцию от графа H(G). Алиса преобразует граф G(V) в изоморфный с помощью функции P: P(G). Гамильтонов цикл для нового графа: H(P(G)).

Лучший алгоритм поиска гамильтонова цикла в графе с n вершинами сейчас имеет сложность:

$$O(n * 2^n)$$

Быстрого алгоритма для восстановления оригинального графа из изоморфного нет. Боб не сможет за полиномиальное время выполнить эту задачу и ему придётся перебрать все возможные варианты. Сложность такого алгоритма для графов с n вершинами:

$$O(n!)$$

Можем сравнить графики алгоритмических сложностей этих алгоритмов наглядно (зелёный - алгоритм поиска гамильтонова цикла, синий - алгоритм перебора изоморфного графа):

Как видно из этого графика, сложность намного быстрее возрастает для алгоритма полного перебора графа: уже для 10 вершин это 3 628 800 комбинаций, когда для алгоритма нахождения гамильтонова цикла количество комбинаций всего 10 240.

При этом, проверить решение Алисы таким способом очень просто и быстро. Боб сможет сделать это за линейное время. Алгоритмическая сложность для графа с n вершинами:

$$O(n)$$

Также, поскольку Боб задаёт вопросы равновероятно, то шанс, что Алиса сможет успешно обмануть Боба каждый из n раз:

$$P = \frac{1}{2^n}$$

Для 300 раз вероятность обмануть Боба становится уже 2^300, что оценивается как "супер-пупер-дупер крайне маловероятно". Для сравнения, количество частиц в наблюдаемой вселенной оценивается как 10^87, но:

$$10^{87} < 2^{300}$$

Алгоритм решения

1. Найти в графе G(V) гамильтонов цикл H(G)

2. Создать изоморфный граф G' = P(G)

3. Переименовать точки в ранее найденом гамильтоновом цикле согласно полученному изоморфному графу: H' = P(H(G))

4. Предоставить получившийся изоморфный граф G' Бобу

5. Боб может задать один из двух вопросов:

   1. Как именно был переименован граф? Мы предоставляем сопоставление точек изоморфного графа G' и оригинального графа G

   2. Какой гамильтонов цикл в графе? Мы предоставляем для графа G' найденый гамильтонов цикл H'

6. Если Бобу нужно ещё доказательство, то возвращаемся на шаг 2