ZKP и zk-SNARKs
Кратко
- zk-SNARKs = краткие неинтерактивные аргументы знания с нулевым разглашением
- Они позволяют одной стороне доказать, что она знает нечто, не раскрывая саму информацию
- Zcash использует zk-SNARKs, чтобы доказать, что транзакция действительна (корректные суммы, неизрасходованные входы) без раскрытия отправителя, получателя или суммы
- «Краткость» означает, что доказательство очень маленькое и быстро проверяется даже для сложных утверждений
- Пул Orchard использует Halo 2, систему zk-SNARK, для которой не требуется доверенная настройка
Что такое доказательство?
Доказательства — основа всей математики. Доказательство — это утверждение или теорема, которую вы пытаетесь доказать, и последовательность выводов, на основании которой объявляется, что теорема доказана. Например, то, что сумма всех углов треугольника равна 180°, может быть независимо проверено кем угодно (верификатором).
Доказательства
Доказывающий ---> Делает утверждение ---> Проверяющий выбирает ---> Принять/Отклонить
(И доказатель, и проверяющий являются алгоритмами)
В компьютерных науках термин для эффективно проверяемых доказательств — NP-доказательства. Эти короткие доказательства могут быть проверены за полиномиальное время. Общая идея такова: «Существует решение теоремы, и оно передаётся проверяющему для проверки».
В NP-языке должны выполняться два условия:
Полнота: истинные утверждения будут приняты проверяющим (честные доказывающие могут пройти проверку).
Корректность: ложные утверждения не будут иметь доказательств (для любой стратегии обманывающего доказывающего они не смогут доказать корректность неверного утверждения).
Интерактивные и вероятностные доказательства
Взаимодействие: Вместо простого чтения доказательства верификатор взаимодействует с доказывающей стороной в режиме диалога на протяжении нескольких раундов обмена сообщениями.
Случайность: Запросы верификатора к доказывающему рандомизированы, и доказывающий должен уметь корректно отвечать на каждый из них.
Используя вместе интерактивность и случайность, можно доказать утверждение слепому верификатору за вероятностное полиномиальное время (PPT).
Могут ли интерактивные доказательства эффективно проверять не только доказательства для NP?
NP-доказательства против IP-доказательств:
| Утверждение | NP | IP |
|---|
| NP | да | да |
| CO-NP | нет | да |
| #P | нет | да |
| PSPACE | нет | да |
NP — Существует решение для утверждения
CO-NP — доказательство того, что для утверждения не существует решений
#P — Чтобы подсчитать, сколько решений существует у утверждения
PSPACE — доказательство чередования различных утверждений
Что такое доказательство с нулевым разглашением?
То, что верификатор может вычислить после взаимодействия, идентично тому, что он мог доказать до него. Многораундовое взаимодействие между доказывающим и верификатором не увеличило вычислительную мощность верификатора.
Симуляция Paradigm
Этот эксперимент встречается во всей криптографии. В нём представлены «Реальный вид» и «Смоделированный вид».
Реальное представление: Все возможные истории взаимодействий между Доказывающим и Проверяющим (P,V)
Симулированный вид: верификатор моделирует все возможные взаимодействия между Prover и Verifier
Полиномиально-временной различитель пытается определить, наблюдает ли он реальное или симулированное представление, и многократно запрашивает образец из обоих.
Говорят, что два представления являются «вычислительно неразличимыми», если для всех алгоритмов/стратегий различения, даже после получения полиномиального числа образцов из реального или симулированного источника, вероятность составляет >1/2.
Аргументы знания с нулевым разглашением
Интерактивный протокол (P,V) является доказательством с нулевым разглашением, если существует симулятор (алгоритм) такой, что для каждого вероятностного полиномиального по времени верификатора (когда теорема верна) распределения вероятностей, определяющие реальное и симулированное представление, являются вычислительно неразличимыми.
Интерактивные протоколы полезны, когда есть один проверяющий. Примером может служить налоговый аудитор в приложении с нулевым разглашением «доказательство уплаты налогов».
Что такое SNARK?
Краткий неинтерактивный аргумент знания
Широкое определение — краткое доказательство того, что утверждение истинно. Доказательство должно быть коротким и быстро проверяемым. В SNARKS от Доказывающего к Проверяющему отправляется одно сообщение. Затем Проверяющий может принять его или отклонить.
пример утверждения: "Я знаю сообщение (m) такое, что SHA256(m)=0"
В zk-SNARK доказательство ничего не раскрывает о сообщении (m).
Многочлены: Суммы членов, содержащих константу (например, 1,2,3), переменные (например, x,y,z) и показатели степени переменных (например, x², y³).
пример: "3x² + 8x + 17"
Арифметическая схема: Модель для вычисления полиномов. В более общем смысле её можно определить как направленный ациклический граф, в котором в каждой вершине графа выполняется арифметическая операция. Схема состоит из вентилей сложения, вентилей умножения и некоторых константных вентилей. Подобно тому как булевы схемы передают биты по проводам, арифметические схемы передают целые числа.
В этом примере доказывающий хочет убедить проверяющего в том, что он знает решение арифметической схемы.
Коммитменты: Для этого доказатель поместит все значения (приватные и публичные), связанные со схемой, в коммитмент. Коммитменты скрывают свои входные данные, используя функцию, результат которой необратим.
Sha256 — это один из примеров хеш-функции, которая может использоваться в схеме обязательства.
После того как доказывающий фиксирует значения, коммитменты отправляются проверяющему (с уверенностью в том, что тот не сможет раскрыть ни одно из исходных значений). Затем доказывающий может продемонстрировать проверяющему знание каждого из значений в узлах графа.
Преобразование Фиата — Шамира
Чтобы сделать протокол неинтерактивным, доказывающая сторона генерирует случайность (используемую для скрытого вызова) от имени проверяющей стороны с помощью криптографической хеш-функции. Это известно как случайный оракул. Затем доказывающая сторона может отправить проверяющей стороне единственное сообщение, после чего та сможет проверить его корректность.
Чтобы сформировать SNARK, который можно использовать для схем общего назначения, требуются два элемента:
Функциональная схема обязательства: позволяет стороне, создающей обязательство, зафиксировать полином с помощью короткой строки, которую проверяющий может использовать для подтверждения заявленных значений этого полинома.
Интерактивный оракул полиномов: верификатор просит доказателя (алгоритм) раскрыть все коммитменты в различных точках по своему выбору, используя схему полиномиальных коммитментов, и проверяет, что между ними выполняется истинное тождество.
Настройка
Процедуры настройки помогают верификатору, суммируя схему и выводя публичные параметры.
Типы настройки предварительной обработки:
Доверенная настройка для каждой схемы — выполняется один раз для каждой схемы. Она специфична для схемы, а секретную случайность (Common Reference String) необходимо хранить в тайне и уничтожить.
Скомпрометированная настройка в этом методе означает, что нечестный доказывающий может доказать ложные утверждения.
Доверенная, но универсальная настройка — требуется выполнить trusted setup только один раз, после чего можно детерминированно предварительно обрабатывать несколько схем.
Прозрачная настройка (без доверенной настройки) — алгоритм предварительной обработки вообще не использует никакую секретную случайность.
Типы конструкций доказательств SNARK:
Groth16: Требует доверенной настройки, но имеет очень короткие доказательства, которые можно быстро проверить.
Sonic/Marlin/PLONK: Универсальная доверенная настройка.
DARK/Halo/STARK: Не требуют доверенной настройки, но создают немного более длинные доказательства или могут потребовать больше времени для работы прувера.
SNARKS полезны, когда требуется несколько верификаторов, например в блокчейне вроде Zcash или zk-Rollup, таком как Aztec, чтобы нескольким валидирующим узлам не приходилось взаимодействовать в течение нескольких раундов для каждого доказательства.
Как zk-SNARK реализованы в Zcash?
В целом доказательства с нулевым разглашением — это инструмент для обеспечения честного поведения в протоколах без раскрытия какой-либо информации.
Zcash — это публичный блокчейн, обеспечивающий приватные транзакции. zk-SNARK используются для доказательства того, что приватная транзакция является действительной в рамках правил консенсуса сети, не раскрывая при этом никаких других деталей о транзакции.
Видеообъяснение — в этой лекции Ариэль Габизон даёт описание Zcash дерева коммитментов заметок, слепой оценки полиномов и гомоморфно скрытых вызовов, а также того, как они реализованы в сети.
Подробнее см. в книге Halo2.
Другие применения доказательств с нулевым разглашением
zk-SNARKs предоставляют ряд преимуществ в самых разных приложениях. Давайте рассмотрим несколько примеров.
Масштабируемость: Это достигается за счёт «выноса вычислений». Для цепочки L1 нет строгой необходимости в доказательствах с нулевым разглашением, чтобы проверять работу офчейн-сервиса. Транзакции не обязательно являются приватными в zk-EVM.
Преимущество сервиса Rollup на основе доказательств (zk-Rollup) заключается в обработке пакета из сотен/тысяч транзакций, при этом L1 способен проверить краткое доказательство того, что все транзакции были обработаны корректно, увеличивая пропускную способность сети по транзакциям в 100 или 1000 раз.
Совместимость: Это достигается в zk-Bridge путём «блокировки» активов в исходной цепочке и доказательства целевой цепочке того, что активы были заблокированы (доказательство консенсуса).
Соответствие нормативным требованиям: Такие проекты, как Espresso, способны доказать, что приватная транзакция соответствует местному банковскому законодательству, не раскрывая деталей транзакции.
Борьба с дезинформацией: Среди нескольких примеров вне блокчейна и криптовалют — использование генерации доказательств для изображений, обработанных новостными и медиаресурсами, чтобы дать зрителям возможность независимо проверять источник изображения и все операции, выполненные над ним. https://medium.com/@boneh/using-zk-proofs-to-fight-disinformation-17e7d57fe52f
Дальнейшее изучение:
Библиография по доказательствам с нулевым разглашением - a16z Криптография]
zkSNARK'и с Hanh Huynh Huu](https://www.youtube.com/watch?v=zXF-BDohZjk)
Zcash: Halo 2 и SNARK без доверенной настройки — Sean Bowe в Dystopia Labs
Доказательства с нулевым разглашением с Ави Вигдерсоном - Numberphile]
Интерактивные доказательства с нулевым разглашением — статья Chainlink
Лекция 1: Введение и история ZKP - zklearning.org
Простое объяснение арифметических схем - Medium
Масштабируемость — это скучно, конфиденциальность мертва: доказательства с нулевым разглашением, для чего они нужны?](https://www.youtube.com/watch?v=AX7eAzfSB6w)
Связанные страницы
