Неинтерактивные ZK-доказательства: Фиат–Шамир на примере Шнорра

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

Начнём с трёх сообщений

Рассмотрим протокол идентификации Шнорра. Алиса хранит секретное число a и публикует A = ga mod p. Запись mod p означает остаток от деления на p. Публичные параметры задают группу, в которой вычислительно трудно восстановить a по известному A.

Алиса доказывает конкретную вещь: она знает показатель степени для этого A. Само существование подходящего показателя ещё не означает, что она его знает.

1. Алиса выбирает новое секретное случайное число v, вычисляет V = gv mod p и отправляет V. Это начальное сообщение называют commitment: Алиса фиксирует его до испытания.
2. Боб выбирает случайное испытание c и передаёт его Алисе.
3. Алиса отправляет ответ r = v − a × c mod q. Число q — порядок группы: через столько шагов показатели степени начинают повторяться.

Боб проверяет принадлежность публичных значений нужной группе и равенство V = gr × Ac mod p. Подстановка ответа объясняет, почему всё сходится: gv−ac × gac = gv. Ни a, ни v Алиса не отправляет.

Пусть испытание задаёт хеш

Фиат–Шамир заменяет сообщение Боба вычислением. Алиса сначала получает V, затем хеширует публичное утверждение, это сообщение и контекст протокола. Из результата получается c, и только после этого Алиса вычисляет ответ r.

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

Обе стороны должны одинаково записать входы в байтах. Простая склейка строк неоднозначна: «1» и «23» дают ту же строку «123», что «12» и «3». Длина перед каждым полем задаёт ясные границы. Название протокола и контекст привязывают результат к нужному применению.

Полный пример с числами

Возьмём p = 23, q = 11 и g = 2, чтобы пройти арифметику вручную. Степени двойки по модулю 23 повторяются через 11 шагов. Пусть секрет Алисы a = 3, а новое случайное число v = 6.

• Публичное утверждение: A = 23 mod 23 = 8.
• Первое сообщение: V = 26 mod 23 = 18.

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

yieldo:schnorr-example:v1
23
11
2
8
18
alice
article-2026-11-03

SHA-256 полученной последовательности байтов:

20334aa464de6ff6c3b5bb30644be32eb7f2fd4f187fbf1a96e8b85e00a1a79a

Прочитаем хеш как беззнаковое целое со старшим байтом первым и возьмём остаток от деления на 11. Получится c = 4. Ответ Алисы: r = (6 − 3 × 4) mod 11 = 5. Доказательство содержит V = 18, r = 5 и согласованный контекст. Секретную тройку оно не содержит.

Проверяющий повторяет хеширование, получает то же испытание 4, проверяет принадлежность публичного значения подгруппе (811 mod 23 = 1), а затем равенство:

2^5 mod 23 = 9
8^4 mod 23 = 2
9 × 2 mod 23 = 18 = V

Весь расчёт можно повторить со стандартной библиотекой Python:

import hashlib

p, q, g, a, v = 23, 11, 2, 3, 6
A, V = pow(g, a, p), pow(g, v, p)
fields = ["yieldo:schnorr-example:v1", str(p), str(q),
          str(g), str(A), str(V), "alice", "article-2026-11-03"]
encoded = b"".join(len(s.encode()).to_bytes(4, "big")
                   + s.encode() for s in fields)
c = int.from_bytes(hashlib.sha256(encoded).digest(), "big") % q
r = (v - a * c) % q
print(A, V, c, r)  # 8 18 4 5
print(pow(g, r, p) * pow(A, c, p) % p == V)  # True

Почему нельзя выбрать удобное испытание?

В анализе безопасности хеш рассматривают как случайный оракул: на новый вход он даёт независимый случайный ответ, а на повторный — тот же, что раньше. Настоящий хеш детерминирован. Случайный оракул — математическая модель анализа этой конструкции с предположениями об исходном протоколе и хеше.

Здесь же разрешается кажущееся противоречие нулевого разглашения. В доказательстве через симуляцию алгоритм может построить убедительную запись без секрета, задавая ответы оракула внутри модели. Обычный участник не может так перенастроить SHA-256. Симуляция устанавливает, какие сведения раскрывает доказательство; управления настоящим хешем она ему не даёт.

Зачем каждый раз новое случайное число?

Секретное случайное число v, которое называют nonce, скрывает секрет Алисы в ответе. Повтор этого числа при двух разных испытаниях раскрывает секрет обычным вычитанием. Пусть при том же v = 6 второе испытание c′ = 7 дало ответ r′ = 7. Получатель обеих записей восстановит:

a = (r − r′) / (c′ − c) mod 11
  = (5 − 7) / (7 − 4) mod 11
  = 3

Деление по модулю 11 означает умножение на обратное число. Для тройки это 4, потому что 3 × 4 mod 11 = 1. Поэтому −2 × 4 mod 11 = 3. Та же проблема возникает при повторе первого сообщения в разных контекстах, если они дают разные испытания.

Место Фиата–Шамира среди ZK-систем

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

Фиат–Шамир убирает сообщения проверяющего из подходящих протоколов, в которых испытания задаются публичной случайностью. Общая строка параметров, или CRS, описывает публичную настройку — другую часть устройства системы. Названия SNARK и STARK добавляют свои свойства и конструкции. Карта ZK-платформ связывает эти системы с сетями, приватными приложениями и рынками вычислений.