Доказательство с нулевым разглашением позволяет проверить утверждение, сохранив секретные данные при себе. Например, убедить собеседника, что вы знаете пароль от двери, не произнося пароль. По-английски это zero-knowledge proof, или ZK-доказательство.
Eugen Voyager
Содержание
Пещера Али-Бабы помогает увидеть механизм: проверяющий выбирает испытание, которое человек без секрета способен пройти лишь случайно. Несколько независимых испытаний уменьшают вероятность такого обмана, а сам секрет остаётся скрытым.
Два коридора и одна секретная дверь
Представьте пещеру с одним входом. Внутри путь раздваивается: левый коридор A и правый коридор B огибают скалу и упираются в противоположные стороны волшебной двери. Дверь открывается паролем и позволяет перейти из A в B или обратно. Другого перехода между коридорами нет.
Алиса знает пароль и хочет убедить в этом Боба. Она выступает доказателем, Боб — проверяющим. Утверждение звучит так: «Я умею открывать эту дверь». Пароль — секрет, благодаря которому Алиса может выполнить проверку.
Боб остаётся снаружи и не видит, в какой коридор вошла Алиса. Когда она уже скрылась за развилкой, он подходит к развилке и просит выйти через A или через B. Из этого места Боб видит выход из обоих коридоров, но не дверь и не действия Алисы возле неё.
Зная пароль, Алиса выполнит любой из двух запросов. Если она уже в нужном коридоре, просто вернётся. Если в другом — откроет дверь, перейдёт на другую сторону и выйдет там, где попросил Боб.
Один раунд: сначала выбор, затем испытание
- Алиса входит. Она выбирает A или B, пока Боб не видит её путь.
- Боб задаёт случайный запрос. После выбора Алисы он с равными шансами требует выйти через A или B. Заранее сообщать запрос нельзя.
- Алиса отвечает действием. Она выходит из названного коридора. Боб проверяет, совпала ли сторона с запросом.
- Для следующего раунда всё начинается заново. Алиса снова скрыто выбирает путь, а Боб задаёт новый независимый запрос.
Порядок решает всё. Если Боб сначала скажет «выйди через A», человек без пароля просто войдёт в A, развернётся и выйдет обратно. Проверка сработает только тогда, когда первоначальный выбор уже сделан, а будущий запрос ещё неизвестен.
Почему вероятность обмана равна 2−n
Теперь вместо Алисы входит человек без пароля. Он может вернуться только по своему коридору: закрытая дверь не позволяет перейти на другую сторону. Независимо от того, выбрал он A или B, случайный запрос Боба совпадёт с этим выбором с вероятностью 1/2.
Чтобы пройти все n независимых раундов, приходится каждый раз угадывать. Вероятности перемножаются: (1/2)n = 2−n.
| Раундов подряд | Вероятность пройти все без пароля |
|---|---|
| 1 | 1/2 = 50% |
| 10 | 1/1 024 ≈ 0,0977% |
| 20 | 1/1 048 576 ≈ 0,0000954% |
Число 1/1 048 576 относится к попытке обманщика пройти заранее назначенные 20 проверок подряд. Боб считает каждый раунд: неудача тоже остаётся результатом. Если разрешить стирать неудачные попытки и показывать только успешные, получится совсем другая проверка.
Формула опирается на свежие независимые запросы с равными шансами A и B. Предсказуемая последовательность или подсказка о следующей стороне дают обманщику возможность заранее выбрать подходящий коридор.
Три свойства ZK на том же примере
Полнота: знающий секрет проходит проверку
Если Алиса знает пароль и участники соблюдают правила, она всегда может выйти с нужной стороны. Доказательство должно принимать правильный ответ честного участника. Это свойство называется полнотой — completeness.
Устойчивость к обману: незнающий редко убеждает проверяющего
Обманщик иногда угадает сторону, но независимые повторы уменьшают шанс пройти всю проверку. Это показывает смысл soundness: ложное утверждение не должно успешно проходить проверку, кроме как с ограниченной малой вероятностью. В пещере эту вероятность видно непосредственно — 2−n.
Нулевое разглашение: проверка не передаёт секрет
Боб слышит свои запросы и видит выход Алисы. Он не слышит пароль и не наблюдает, как открывается дверь. Но идея нулевого разглашения глубже, чем «пароль не произнесли»: увиденное не должно давать ему дополнительное знание о секрете сверх подтверждаемого утверждения.
Это удобно понять через запись разговора. Для неё можно заранее согласовать запросы: войти в A, получить запрос A, выйти из A; затем повторить с B. Для такого сценария пароль не нужен. Если выбирать стороны случайно, запись запросов и успешных выходов будет выглядеть так же, как запись честных испытаний.
В математическом определении используется похожая идея симуляции: наблюдения проверяющего можно воспроизвести, не получая секрет. Конкретный протокол должен доказывать это свойство для своей модели проверяющего. В пещере мы разобрали честного Боба, который следует оговорённой процедуре.
Почему видеозапись не заменяет проверяющего
Бобу важно, что именно он выбрал непредсказуемые запросы после входа Алисы. Зритель готового видео этого не знает: запросы могли согласовать заранее, а неудачные дубли — убрать. Самостоятельно убедившийся Боб и человек, которому переслали запись, находятся в разных условиях.
Поэтому сохранённый разговор сам по себе не становится неинтерактивным доказательством с нулевым разглашением — NIZK. В таком протоколе проверяющий получает доказательство и проверяет его без отдельного обмена запросами с доказателем. Для этого нужна специальная криптографическая конструкция; одной записи успешных ответов недостаточно.
Следующий шаг — преобразование Фиата—Шамира и неинтерактивное доказательство. Числовой пример Шнорра показывает, как проверить доказательство позже, не отправляя новый запрос.
От пещеры к криптографическому доказательству
В программе вместо проходов по пещере проверяются математические соотношения. Публичное утверждение известно проверяющему, а секретные данные позволяют построить принимаемое доказательство. Например, можно доказывать выполнение заданного условия, сохранив скрытыми данные, по которым его проверяют.
Один из практических примеров — закрытые платежи Zcash. Их доказательства zk-SNARK позволяют проверять условия операции, сохраняя скрытые данные у участников.
При чтении о ZK полезно различать три вопроса: что именно доказано, какие данные скрыты и кто способен проверить результат. Пещера объясняет порядок испытания и три свойства; карта ZK-платформ показывает, как задачи доказательств связаны с сетями, приватностью и рынками вычислений.
EV
Eugen Voyager
Крипто-аналитик и блокчейн-разработчик. В индустрии с 2018 года. Создатель блокчейна Telochain, GameFi-проекта Telomeme и платформы Yieldo. Автор Telegram-канала @tonsdot.
Как мы собираем и проверяем данные — методология Yieldo.
Как мы публикуем, датируем и исправляем материалы — редакционная политика.