Интуитивное понимание ZKP: пещера Али-Бабы

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

Если доказывающий знает секрет, он всегда может убедить проверяющего. Честный доказывающий, соблюдающий протокол, добьётся успеха с вероятностью 1 (или с подавляющей вероятностью). Проверяющий не отклонит корректное доказательство.

Мошенничающий доказывающий, который не знает секрета, не может убедить проверяющего иначе как с пренебрежимо малой вероятностью. Каждый раунд взаимодействия уменьшает вероятность обмана — после k раундов вероятность успеха обманщика составляет не более 2^{-k}.

Проверяющий не узнаёт ничего, кроме того, что утверждение истинно. Формально: существует симулятор, который, не зная секрета, создаёт запись взаимодействия, неотличимую от взаимодействия настоящих доказывающего и проверяющего. Проверяющий не получает никаких дополнительных знаний.

В пещере есть кольцевой проход с волшебной дверью посередине. Доказывающая Алиса утверждает, что знает пароль. Проверяющий Боб ждёт снаружи. Алиса входит и идёт налево или направо. Боб кричит, с какой стороны ей выйти. Если Алиса знает пароль, она всегда выходит с нужной стороны. Вероятность обмана в каждом раунде: 1/2.

После 20 раундов обманщик добивается успеха с вероятностью 2^{-20} ≈ 1 к миллиону. Алиса, знающая пароль, добивается успеха каждый раз. Боб никогда не узнаёт пароль — он лишь видит, как Алиса выходит с указанной стороны. Это и есть нулевое разглашение.

Интерактивные ZKP требуют обмена сообщениями между доказывающим и проверяющим. Неинтерактивные ZKP используют преобразование Fiat-Shamir: заменяют случайный вызов проверяющего хешем обязательства (хеш = случайный оракул). В результате получается одна строка доказательства, которую может проверить любой.

ZKP является доказательством знания (PoK), если из стратегии доказывающего следует, что секрет можно извлечь. Это более сильное свойство, чем простое доказательство истинности утверждения. Подписи ECDSA и Schnorr являются неинтерактивными доказательствами знания закрытого ключа.

Аутентификация по паролю без отправки самого пароля. Проверка возраста без раскрытия даты рождения. Доказательства диапазона (ваша зарплата находится в заданном диапазоне) без раскрытия зарплаты. Блокчейн: доказать, что Вы знаете действительную транзакцию, не раскрывая саму транзакцию.

Совершенный ZK: вывод симулятора идентичен реальному транскрипту. Статистический ZK: транскрипты неразличимы, за исключением события с пренебрежимо малой вероятностью. Вычислительный ZK: транскрипты неразличимы для проверяющих, работающих за полиномиальное время. Более слабые гарантии = более эффективные доказательства.

Пещера — это протокол из трёх шагов: фиксация → вызов → ответ. Формально он называется сигма-протоколом. Большинство практических ZKP (Schnorr, Pedersen, Fiat-Shamir) являются сигма-протоколами или их композициями. Название происходит от формы Σ на диаграмме потока сообщений.

ZKP доказывают знание секрета, не раскрывая его. Три свойства: полнота, состоятельность, нулевое разглашение. Пещера Али-Бабы иллюстрирует интерактивный ZKP. Далее: сигма-протоколы и идентификация Schnorr.