Введение в интерактивные Zero-Knowledge Proofs
Это первая публикация в серии исследовательских статей, связанных с Zero Knowledge от исследовательской группы Chainlink Labs.
Автор: Сяо Ванг
Соавторы: Лоренц Брайденбах, Алекс Ковентри, Сиам Хуссейн, Далия Малхи, Александр Топличану, Ченкай Вэн, Фань Чжан.
Вступление
Доказательства с нулевым разглашением (“ZKP”) привлекли большое внимание в мире блокчейна. Основное внимание уделяется обеспечению возможности публичного совершения транзакций на блокчейне с обеспечением компактности и/или конфиденциальности. Как правило, в этом случае требуется проверка любым человеком в любое время, следовательно, ZKP должны быть неинтерактивными.
Существует другой тип доказательств c нулевым разглашением — интерактивные доказательства (“IR-ZKP”), которые уникально подходят для области технологии оракулов. Вкратце, оракулы образуют децентрализованную офф-чейн сеть, которая координирует задачи на основе консенсуса. Оракулы могут помочь децентрализовать системы доказательств вне блокчейн (офф-чейн) с минимальным доверием. То есть, они могут помочь в выполнении задач доказательства без единой точки централизации или доверия, координируя результат как группа. В частности, оракулы могут участвовать в интерактивных ZK-диалогах с проверяющими (provers) и совместно подтверждать результаты проверки. В этой серии будет опубликована серия статей, объясняющих современные протоколы IR-ZKP и конкретные случаи их использования.
Доказательства с нулевым разглашением
Учитывая некоторую открытую функцию f и значение y, протокол доказательства с нулевым разглашением (ZKP) позволяет стороне (она же проверяющий) показать проверяющему, что она знает некоторое x, такое, что f(x; y)=1, не раскрывая значения x. Например, следующий протокол ZKP Coke-or-Pepsi позволяет проверяющему показать, что он знает, как отличить колу от пепси, не раскрывая, каким образом:
- Проверяющий готовит стакан с колой и пепси и случайным образом перемешивает их.
- Проверяющий, не глядя на верификатора, наблюдает/пробует оба стакана и решает, какой из них кока-кола.
- Повторите этот процесс 40 раз, и верификатор согласится с тем, что проверяющий действительно знает, как отличить колу от пепси, если он каждый раз будет прав.
Приведенный выше протокол ZKP не обязательно полезен, но на самом деле любая функция f, выполняющаяся в полиномиальном пространстве, может быть доказана с нулевым разглашением.
Неинтерактивные в сравнении с интерактивными ZK
Традиционно многие протоколы ZKP можно сделать неинтерактивными, так называемыми неинтерактивными доказательствами с нулевым разглашением (NIZK). Это означает, что проверяющему достаточно запустить программу, принимающую (f, x, y) в качестве входных данных, и вывести доказательство pi. Любой верификатор, имеющий (f, y, pi), может проверить его и убедиться, что доказывающий (prover) действительно знает x, не видя его. Процесс работы NIZK напоминает цифровую подпись: Подписывающий подписывает открытый документ, используя свой закрытый ключ подписи, и генерирует подпись; любой проверяющий, имеющий документ, подпись и ключ проверки, может проверить достоверность подписи.
NIZK нашли множество применений в блокчейне благодаря своей привлекательной особенности — возможности их передачи: Проверяющий, не зная личности проверяемого, может создать одно доказательство, которое может быть использовано для убеждения любого, кто его получит. NIZK с очень маленькими доказательствами обычно классифицируются как zk-SNARKs (многие NIZK имеют доказательство постоянного размера; в то время как другие имеют полилогарифмический размер доказательства. Мы рассматриваем их все как zk-SNARK). Они особенно подходят для открытых систем, где может быть много верификаторов, заинтересованных в проверке доказательства. В этом случае доказательство нужно вычислить только один раз и дёшево проверить многими верификаторами. Однако эти преимущества сжатых ZK имеют и некоторые недостатки: Сукцинкные NIZT часто имеют большие накладные расходы со стороны проверяющего на вычисления и память. Ресурс, необходимый для доказательства функции, на порядки выше, чем тот, который требуется для оценки функции в чистом виде.
Другим типом протокола ZKP является интерактивный ZKP. Приведенный выше пример Coke-or-Pepsi — это интерактивный ZKP между доказателем и проверяющим: две стороны должны общаться в раундах с информацией, текущей в обоих направлениях на протяжении всего протокола. За пределами области ZK интерактивные протоколы широко используются на практике. Например, для аутентификации пользователя по паролю он может запустить интерактивный протокол:
- Сервер посылает nonce y клиенту.
- Клиент отвечает серверу значением H(username || password || nonce) для некоторой криптографической хэш-функции H.
- Сервер проверяет правильность значения, пересчитывая то же значение локально.
Интерактивный протокол позволяет использовать генерируемый сервером nonce и таким образом предотвращает атаки повторного воспроизведения (когда злоумышленник перехватывает сообщение и повторно отправляет его в более позднее время на сервер для аутентификации). Разрешение раунда взаимодействия имеет решающее значение, поскольку предотвращение атак повторного воспроизведения будет намного сложнее, если аутентификация пароля будет состоять только из одного сообщения от клиента к серверу.
Следующие публикации
Интерактивные ZKP — это в целом более широкий набор протоколов, содержащий протоколы NIZK (в частности, всегда можно добавить взаимодействие к NIZK, чтобы превратить его в интерактивный ZKP). Однако взаимодействие может привести к таким свойствам, которые сжатые NIZK не показывают, например, высокая масштабируемость до очень больших состояний, дешевые вычисления, отказ от доверенной установки и минимальное использование памяти. Это полезно, когда утверждение должно быть доказано только для небольшого и известного набора сторон. В серии статей мы познакомимся с основами современных интерактивных протоколов ZK. Мы рассмотрим следующее содержание:
- Сложность памяти при оценке схемы работы. Здесь мы углубимся в детали оценки схемы, чтобы понять, почему многие ZK-протоколы должны использовать огромное количество памяти и как преодолеть эту проблему.
- ZK-доказательства с малым объемом памяти: сложности и компромиссы. В качестве первого шага к уменьшению потребления памяти мы представим некоторые протоколы ZK, которые отличаются небольшой сложностью памяти. Несмотря на небольшое потребление памяти, эти протоколы не показывают хороших результатов по другим параметрам.
- Масштабируемый и доступный интерактивный ZK на основе интерактивного выполнения обязательств. Мы поговорим об интерактивных ZK, которые можно рассматривать как интерактивные вариации вышеупомянутого протокола. Эти протоколы опираются на особый тип обязательств и отличаются супердешевым вычислением, хотя они требуют линейной коммуникации.
- Последние достижения в области интерактивных обязательств. Мы говорим о том, как инстанцировать обязательства, необходимые в интерактивных протоколах ZK, основываясь на последних работах по разделению секретов функций и генераторам псевдослучайных корреляций. Для этого необходимо квантово-безопасное предположение, называемое “обучение четности с шумом”.
- Обзор технических трудностей и будущих разработок. Наконец, мы поговорим о трудностях, связанных с обеспечением эффективности этих интерактивных протоколов ZK, и о передовых направлениях исследований.
