Руководство для начинающих по доказательствам с нулевым знанием: История развития, применение и основные принципы

Текущие темпы роста проектов с доказательством нулевого знания (ZKP) в индустрии блокчейна поражают воображение, особенно рост числа приложений ZKP на двух уровнях - расширения и защиты конфиденциальности, что привело к появлению множества проектов с доказательством нулевого знания. Из-за чрезвычайно математической природы ZKP, энтузиастам шифрования значительно сложнее понять ZK досконально. Поэтому мы также надеемся разобраться с некоторыми изменениями в теории и применении ZKP с самого начала, а также изучить влияние и значение для криптоиндустрии вместе с читателями - учиться вместе в нескольких отчетах, которые также служат кратким изложением мыслей исследовательской команды HashKey Capital. Эта статья - первая в серии, в ней рассказывается об истории развития, применении и некоторых основных принципах ZKP.

1. История доказательств с нулевым знанием

Современная система доказательств с нулевым знанием возникла из работы, совместно опубликованной Голдвассером, Микали и Рэкоффом: The Knowledge Complexity of Interactive Proof Systems (GMR85), которая была предложена в 1985 году и опубликована в 1989. В этой статье главным образом объясняется, каким количеством знаний необходимо обменяться после K раундов взаимодействий в интерактивной системе, чтобы доказать, что утверждение верно. Если обмен знаниями можно сделать нулевым, это называется доказательством с нулевыми знаниями. Предполагается, что у проверяющего есть неограниченные ресурсы, а у верификатора - только ограниченные. Проблема с интерактивными системами заключается в том, что доказательство не является полностью математически доказуемым, а является верным в вероятностном смысле, хотя вероятность этого очень мала (1/2^n).

Поэтому интерактивная система не совершенна и имеет лишь приблизительную полноту. Неинтерактивная система (NP), рожденная на этой основе, обладает полнотой и становится идеальным выбором для системы доказательств с нулевым знанием.

Ранние системы доказательств с нулевым знанием не отличались эффективностью и удобством использования, поэтому они всегда оставались на теоретическом уровне. Только в последние 10 лет они начали процветать. По мере того, как криптография становилась все более заметной, доказательства с нулевым знанием вышли на первый план и стали важнейшим направлением. В частности, разработка общего, неинтерактивного протокола доказательства с нулевым знанием и ограниченным размером доказательства - одно из наиболее важных направлений исследований.

По сути, доказательство с нулевым знанием - это компромисс между скоростью доказательства, скоростью проверки и размером доказательства. Идеальный протокол - это быстрое доказательство, быстрая проверка и небольшой размер доказательства.

Самым важным прорывом в доказательстве с нулевым знанием является статья Грофа 2010 года "Short Pairing-based Non-interactive Zero-Knowledge Arguments", которая также является теоретическим родоначальником самой важной группы zk-SNARKs в ZKP.

Самым важным событием в применении доказательств с нулевым знанием является система доказательств с нулевым знанием, использованная Z-cash в 2015 году, которая защитила конфиденциальность транзакций и сумм. Позже она превратилась в комбинацию zk-SNARK и смарт-контрактов, и zk-SNARK вошла в более широкие сценарии применения.

К числу важных академических достижений этого периода относятся:

1. Пиноккио (PGHR13) в 2013 году: Pinocchio: Nearly Practical Verifiable Computation, который сокращает время доказательства и верификации до допустимых пределов, также является базовым протоколом, используемым в Zcash.
2. Groth16 в 2016 году: On the Size of Pairing-based Non-interactive Arguments", который упрощает размер доказательства и повышает эффективность проверки, в настоящее время является наиболее широко используемым базовым алгоритмом ZK.
3. Bulletproofs (BBBPWM17) Bulletproofs: Короткие доказательства для конфиденциальных транзакций и многое другое В 2017 году был предложен алгоритм Bulletproof - очень короткое неинтерактивное доказательство с нулевым знанием, которое не требует доверенной установки. Он будет применен к Monero через 6 месяцев и очень быстро. Сочетание теории и применения.
4. В 2018 году в работе zk-STARKs (BBHR18) Scalable, transparent, and post-quantum secure computational integrity был предложен протокол алгоритма ZK-STARK, который не требует доверенных настроек. Это еще одно привлекательное направление развития ZK в настоящее время, и оно также основано на этом, на основе чего родился StarkWare, самый важный проект ZK.

Другие разработки, включая PLONK, Halo2 и т.д., также являются чрезвычайно важным прогрессом и также внесли некоторые улучшения в zk-SNARK.

2. Краткое описание применения доказательства нулевой осведомленности

Два наиболее распространенных применения доказательств с нулевым знанием - это защита конфиденциальности и расширение возможностей. В самом начале, с запуском транзакций конфиденциальности и нескольких известных проектов, таких как Zcash и Monero, транзакции конфиденциальности однажды стали очень важной категорией. Однако из-за того, что необходимость в операциях с конфиденциальной информацией оказалась не столь заметной, как рассчитывала индустрия, этот тип представительских проектов начал замедляться. Медленно переходите в лагеря второго и третьего эшелонов (не уходите с исторической сцены). На уровне приложений потребность в расширении возросла настолько, что в 2020 году Ethereum 2.0 (который был переименован в слой консенсуса) превратится в маршрут, ориентированный на роллы. Серия ZK официально вернулась к вниманию индустрии и стала центром внимания.

Конфиденциальные транзакции: Существует множество проектов, в которых реализованы приватные транзакции, включая Zcash, использующий SNARK, Tornado, Monero, использующий bulletproof, и Dash. Dash использует не ZKP в строгом смысле этого слова, а простую и грубую систему смешивания валют, которая может скрыть только адрес, но не сумму. Я не буду упоминать об этом здесь.

Этапы транзакции zk-SNARKs, применяемые Zcash, выглядят следующим образом:

Источник: Разъяснение роли zk-SNARK в Zcash

1. На этапе настройки системы генерируется ключ доказательства (полином доказательства шифрования) и ключ проверки, используя функцию KeyGen.
2. CPA-фаза Метод шифрования ECIES (Elliptic Curve Integrated Encryption Scheme) используется для генерации открытого и закрытого ключей
3. Этап "Чеканка монет", количество сгенерированных новых монет. Публичное выступление и посвящение монеты
4. На этапе заливки генерируется сертификат zk-SNARK и добавляется в книгу транзакций заливки.
5. На этапе верификации верификатор проверяет правильность объемов транзакций Mint и Pour.
6. На этапе приема приемник получает монеты. Если Вы хотите использовать полученные монеты, продолжайте звонить в Pouring, чтобы пройти верификацию zk-SNARK, повторите описанные выше шаги 4-6, чтобы завершить транзакцию.

Zcash все еще имеет ограничения в использовании нулевого знания, т.е. он основан на UTXO, поэтому часть информации о транзакциях лишь экранируется, но не скрывается по-настоящему. Поскольку это отдельная сеть, основанная на дизайне Биткойна, ее трудно расширить (объединить с другими приложениями). Фактический уровень использования экранирования (то есть частных сделок) составляет менее 10%, что говорит о том, что частные сделки не были успешно расширены. (с 2202)

Единый большой пул, используемый в Tornado, более универсален и основан на такой "проверенной и испытанной" сети, как Ethereum. Torndao - это, по сути, пул для смешивания валют, использующий zk-SNARK, а настройки доверия основаны на документе Groth 16. Среди возможностей, доступных с Tornado Cash, - следующие:

1. Вывести можно только внесенные монеты.
2. Никакие монеты не могут быть выведены дважды
3. Процесс доказательства связан с уведомлением об обнулении валюты (Nullifier). Хэш одного и того же доказательства, но с разным Nullifier, не позволит вывести монеты.
4. Защита составляет 126 бит и не снижается из-за состава.

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

Расширение: Расширение ZK может происходить как в сети первого уровня, например, Mina, так и в сети второго уровня, то есть zk-roll up. Идея свертывания ZK, возможно, возникла из сообщения Виталика в 2018 году "Масштабирование цепочки до потенциально ~500 ткс/сек за счет массовой проверки ткс".

В ZK-rollup есть два типа ролей, одна из которых - Sequencer, а другая - Aggregator. Секвенсор отвечает за упаковку транзакций, а Агрегатор - за объединение большого количества транзакций, создание рулона и формирование доказательства SNARK (это также может быть доказательство с нулевым знанием, основанное на других алгоритмах). Это доказательство будет сравниваться с предыдущим состоянием Layer1, а затем обновлять дерево Меркла Ethereum, вычисляя новое дерево состояний.

Источник: Polygon

Преимущества и недостатки сворачивания ZK:

1. Преимущества: низкая стоимость, в отличие от ОП, который будет подвергаться экономическим атакам, нет необходимости откладывать транзакции, конфиденциальность может быть защищена, а окончательный результат может быть достигнут быстро
2. Недостатки: Формирование ZK-доказательства требует большого объема вычислений, проблемы с безопасностью (SNARK требует доверенного окружения), не устойчив к квантовым атакам (SNARK, STARK могут), порядок транзакций может быть изменен

Источник: Исследование Ethereum

Основываясь на доступности данных и методах доказательства, Starkware предлагает классическую схему классификации L2 (уровень доступности данных Volition можно выбрать on-chain или off-chain):

Источник: Starkware

Наиболее конкурентоспособные проекты ZK rollup, представленные в настоящее время на рынке, включают: Starkware's StarkNet, Matterlabs's zkSync и Aztec's Aztec connect, Polygon's Hermez и Miden, Loopring, Scroll и т.д.

В основном, технический путь заключается в выборе SNARK (и его улучшенных версий) и STARK, а также в поддержке EVM (включая совместимость или эквивалентность).

1. Компания Aztec разработала обобщенный протокол SNARK - протоколlonk. Работающий Aztec3 может поддерживать EVM, но конфиденциальность имеет приоритет над совместимостью с EVM.
2. Starnet использует zk-STARK, zkp, который не требует доверенных настроек, но в настоящее время не поддерживает EVM и имеет свой собственный компилятор и язык разработки.
3. zkSync также использует plonk и поддерживает EVM. zkSync 2.0 совместим с EVM и имеет свой собственный zkEVM
4. Scroll, EVM-совместимый роллап ZK, команда также вносит важный вклад в проект zkEVM от Ethereum Foundation.

Кратко обсудите проблемы совместимости EVM:

Совместимость между системой ZK и EVM всегда была головной болью, и большинство проектов выбирают между ними. Те, кто делает упор на ZK, могут создать виртуальную машину в своей собственной системе, иметь свой собственный язык ZK и компилятор, но это усложнит процесс обучения для разработчиков, а поскольку это не открытый исходный код, он превратится в "черный ящик". Вообще говоря, в настоящее время у индустрии есть два варианта. Одна из них - полная совместимость с опкодами Solidity, а другая - разработка новой виртуальной машины, дружественной к ZK и совместимой с Solidity. Вначале индустрия не ожидала такой быстрой интеграции, но быстрая итерация технологии в последние год-два вывела совместимость EVM на новый уровень, и разработчики могут достичь определенной степени бесшовной миграции (то есть перехода от главной цепочки Ethereum к ZK rollup) - это захватывающее развитие, которое повлияет на экологию развития ZK и конкурентную среду. Мы подробно обсудим этот вопрос в последующих отчетах.

3. Основные принципы реализации ZK SNARK

Голдвассер, Микали и Ракофф предложили, чтобы доказательства с нулевым знанием обладали тремя свойствами:

1. Полнота: Каждое утверждение, имеющее разумных свидетелей, может быть проверено проверяющим.
2. Разумность: Каждое утверждение с необоснованными свидетелями не должно проверяться верификатором
3. Нулевая осведомленность: Процесс верификации - это процесс с нулевым знанием

Поэтому, чтобы понять ZKP, мы начнем с zk-SNARK, потому что многие современные блокчейн-приложения начинаются с SNARK. Сначала давайте посмотрим на zk-SNARK.

zk-SNARK означает: Zero-knowledge proof (zh-SNARK) - это нулевое доказательство, состоящее из последовательных неинтерактивных аргументов знания.

1. Нулевое знание: Процесс доказательства не требует никаких знаний и не раскрывает лишней информации.
2. Лаконичность: небольшой размер проверки
3. Неинтерактивный: неинтерактивный процесс
4. Аргументы: Вычисления надежны, то есть проверяющий с ограниченной вычислительной мощностью не может подделать доказательство, а проверяющий с неограниченной вычислительной мощностью может подделать доказательство.
5. Знания: Доказатель не может построить параметр и доказательство, не зная достоверной информации
6. Доказатель не может построить набор параметров и доказательство, не зная свидетеля (например, вход хэш-функции или путь для определения узла дерева Меркле).

Принцип доказательства zk-SNARK Грофа16 заключается в следующем:

Источник: https://learnblockchain.cn/article/3220

Шаги таковы:

1. Преобразуйте проблему в схему
2. Сплющите схему в форме R1CS.
3. Преобразование R1CS в формат QAP (Quadratic Arithmetic Programs)
4. Создайте доверенную установку и сгенерируйте случайные параметры, включая PK (ключ доказательства) и VK (ключ проверки).
5. Генерация доказательств и проверка zk-SNARK

В следующей статье мы начнем изучать принципы и применение zk-SNARK, рассмотрим развитие ZK-SNARK на примере нескольких случаев и исследуем его связь с zk-STARK.

Отказ от ответственности：

1. Эта статья перепечатана с сайта[HashKey Capital]. Все авторские права принадлежат оригинальному автору[HashKey Capital]. Если у Вас есть возражения против этой перепечатки, пожалуйста, свяжитесь с командой Gate Learn, и они незамедлительно рассмотрят их.
2. Предупреждение об ответственности: Мнения и взгляды, выраженные в этой статье, принадлежат исключительно автору и не являются инвестиционным советом.
3. Перевод статьи на другие языки осуществляется командой Gate Learn. Если не указано, копирование, распространение или плагиат переведенных статей запрещены.