Нулевое разглашение

Нулевое разглашение (англ. zero-knowledge proof, ZKP) — это криптографический протокол, позволяющий одной стороне (доказывающему) убедить другую сторону (проверяющего) в истинности некоторого утверждения, не раскрывая при этом никакой дополнительной информации, кроме самого факта истинности утверждения. Ключевое свойство протокола заключается в том, что проверяющий не получает никаких данных, которые позволили бы ему воспроизвести доказательство или узнать что-либо о скрытой информации.

Основные свойства

Любой протокол нулевого разглашения должен удовлетворять трём фундаментальным свойствам:

Полнота (Completeness): Если утверждение истинно, и доказывающий и проверяющий следуют протоколу, то проверяющий с высокой вероятностью (обычно 1) примет доказательство. Иными словами, честный доказывающий всегда сможет убедить честного проверяющего.
Корректность (Soundness): Если утверждение ложно, то никакой нечестный доказывающий (даже обладающий неограниченными вычислительными ресурсами) не сможет убедить проверяющего в обратном, за исключением пренебрежимо малой вероятности ошибки. Это свойство защищает от мошенничества.
Нулевое разглашение (Zero-Knowledge): В результате выполнения протокола проверяющий не узнаёт ничего, кроме того, что утверждение истинно. Он не может извлечь никакой информации о том, почему утверждение истинно, или о скрытых данных, на которых оно основано. Формально это означает, что для любого проверяющего существует симулятор, который, не взаимодействуя с доказывающим, может сгенерировать «транскрипт» диалога, неотличимый от настоящего.

История

Концепция нулевого разглашения была впервые формально введена в 1985 году в работе Шафи Гольдвассера, Сильвио Микали и Чарльза Ракоффа «The Knowledge Complexity of Interactive Proof Systems». За эту работу Гольдвассер и Микали в 2012 году получили премию Тьюринга. Изначально идея была предложена в контексте интерактивных доказательств, где доказывающий и проверяющий обмениваются последовательностью сообщений.

Позднее, в 1988 году, Мануэль Блюм, Пол Фельдман и Сильвио Микали предложили неинтерактивные доказательства с нулевым разглашением (NIZK), которые не требуют многократного обмена сообщениями. Это стало важным шагом для практического применения, так как позволило использовать ZKP в блокчейн-системах и других распределённых протоколах.

Классификация протоколов

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

По типу взаимодействия

Интерактивные (Interactive ZKP): Доказывающий и проверяющий обмениваются несколькими раундами сообщений. Проверяющий задаёт случайные вопросы («вызовы»), а доказывающий должен на них ответить, не раскрывая секрета. Классический пример — протокол «Пещера Али-Бабы» (см. пример ниже).
Неинтерактивные (Non-Interactive ZKP, NIZK): Доказывающий создаёт одно сообщение (доказательство), которое может быть проверено любым проверяющим без дальнейшего взаимодействия. Для этого используется общая эталонная строка (Common Reference String, CRS) или модель случайного оракула (Random Oracle Model). NIZK широко применяются в криптовалютах (например, zk-SNARKs).

По вычислительным ресурсам

Статистические (Statistical ZKP): Даже обладая неограниченными вычислительными ресурсами, проверяющий не может извлечь никакой информации. Это наиболее сильная форма нулевого разглашения.
Вычислительные (Computational ZKP): Информация может быть извлечена только в том случае, если проверяющий обладает неограниченными вычислительными ресурсами. Для практических целей, где ресурсы атакующего ограничены, этого достаточно. Большинство современных протоколов (например, zk-SNARKs) являются вычислительными.

По типу доказательства

Доказательства (Proofs): Гарантируют корректность с вероятностью 1 (или близкой к 1) для любого утверждения, независимо от вычислительных ресурсов доказывающего. Обычно требуют интерактивности.
Аргументы (Arguments): Гарантируют корректность только для доказывающих с ограниченными вычислительными ресурсами. Если доказывающий обладает неограниченной мощностью, он может обмануть. Однако на практике это несущественно, так как реальные атакующие ограничены. Аргументы, как правило, более эффективны по размеру и времени.

Примеры и аналогии

«Пещера Али-Бабы» (интерактивный протокол)

Классическая иллюстрация, предложенная Жан-Жаком Кискатром и Луи Гийу. Представьте себе пещеру, которая имеет два входа (A и B), соединённых проходом, закрытым волшебной дверью. Дверь открывается только при знании секретного слова. Доказывающий (Пегги) хочет убедить проверяющего (Виктора), что знает секрет, не называя его.

Виктор стоит снаружи пещеры и не видит, куда заходит Пегги.
Пегги заходит в пещеру через вход A или B (по своему выбору).
Виктор громко кричит, из какого входа (A или B) Пегги должна выйти.
Если Пегги знает секрет, она может открыть дверь и выйти из нужного входа, независимо от того, куда зашла. Если не знает, она может выйти только из того входа, в который зашла, и вероятность угадать правильный ответ — 50%.
Повторяя протокол много раз (например, 20 раз), Виктор может быть уверен, что Пегги знает секрет (вероятность случайного угадывания становится пренебрежимо малой — 2<sup>-20</sup>). При этом Виктор не узнаёт сам секрет.

Математический пример: изоморфизм графов

Доказывающий знает изоморфизм (перестановку вершин) между двумя графами G1 и G2. Он хочет доказать это, не раскрывая саму перестановку.

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

Применение

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

Криптовалюты и блокчейн

zk-SNARKs (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge): Компактные неинтерактивные аргументы, используемые в криптовалюте Zcash для обеспечения анонимности транзакций. Позволяют доказать, что отправитель имеет достаточный баланс и что транзакция корректна, не раскрывая сумму, отправителя и получателя.
zk-STARKs (Zero-Knowledge Scalable Transparent Argument of Knowledge): Более масштабируемая и прозрачная альтернатива zk-SNARKs, не требующая доверенной настройки (CRS). Используются в некоторых блокчейн-проектах (например, StarkNet).
Проверка валидности блоков: В некоторых решениях для масштабирования (например, zk-Rollups) используется ZKP для доказательства того, что все транзакции в пакете обработаны корректно, без необходимости проверять каждую транзакцию в отдельности.

Идентификация и аутентификация

Системы «доказательство личности» (Proof of Identity): Пользователь может доказать, что он является владельцем учётной записи или обладает определёнными правами (например, возраст старше 18 лет), не раскрывая свой пароль, дату рождения или другие личные данные.
Аутентификация без пароля: Протоколы, такие как SRP (Secure Remote Password), основаны на идее, что сервер может убедиться, что клиент знает пароль, не получая его самого.

Конфиденциальные вычисления

Облачные вычисления: Клиент может загрузить зашифрованные данные в облако и попросить сервер выполнить над ними вычисления. Сервер может предоставить доказательство с нулевым разглашением того, что вычисления были выполнены корректно, не расшифровывая данные.
Базы данных: Можно доказать, что запись в базе данных удовлетворяет некоторому условию (например, «зарплата сотрудника больше 100 000 рублей»), не раскрывая саму зарплату.

Другие области

Электронное голосование: Избиратель может доказать, что его голос учтён корректно, не раскрывая, за кого он проголосовал.
Судебная экспертиза: Можно доказать, что образец ДНК совпадает с образцом подозреваемого, не раскрывая полную последовательность ДНК.

Критика и ограничения

Несмотря на мощные теоретические основы, практическое применение ZKP сталкивается с рядом проблем:

Вычислительная сложность: Генерация доказательств (особенно для zk-SNARKs) может быть очень ресурсоёмкой и требовать значительного времени и памяти. Это ограничивает их использование в приложениях с низкой задержкой.
Доверенная настройка (Trusted Setup): Многие протоколы (например, zk-SNARKs) требуют создания общей эталонной строки (CRS) в процессе, который должен быть выполнен честно. Если участники настройки сговорятся, они смогут подделывать доказательства. zk-STARKs лишены этого недостатка, но имеют больший размер доказательства.
Размер доказательства: Хотя zk-SNARKs очень компактны (несколько сотен байт), другие протоколы могут генерировать доказательства размером в килобайты или мегабайты, что может быть проблематично для хранения в блокчейне.
Сложность реализации: Разработка корректных и безопасных протоколов ZKP требует глубоких знаний в криптографии и теории чисел. Ошибки в реализации могут привести к уязвимостям.

Источники

Goldwasser, S., Micali, S., & Rackoff, C. (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1), 186–208.
Blum, M., Feldman, P., & Micali, S. (1988). Non-interactive zero-knowledge and its applications. Proceedings of the twentieth annual ACM symposium on Theory of computing, 103–112.
Quisquater, J. J., & Guillou, L. C. (1990). How to explain zero-knowledge protocols to your children. Advances in Cryptology — CRYPTO'89 Proceedings, 628–631.
Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014). Succinct non-interactive zero knowledge for a von Neumann architecture. 23rd USENIX Security Symposium (USENIX Security 14), 781–796.
Ben-Sasson, E., Bentov, I., Horesh, Y., & Riabzev, M. (2018). Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptology ePrint Archive, 2018/046.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →