# Что такое ZK-SNARK и как они работают By [Iryna](https://paragraph.com/@iryna-2) · 2023-05-04 --- ZK-SNARK Определение Свойства ZK-SNARK Системы доказательств PLONKish ZK-SNARK 3.1 Коротко о PLONKish ZK-SNARK и их роли 3.2 Схемы обязательств 3.3 Интерактивное доказательство Oracle 3.4 Эвристика Fiat-Shamir 3.5. Как работают системы проверки PLONKish ZK-SNARK 3.6 Немного о продвинутых аспектах PLONKish ZK-SNARK Введение -------- ZK-SNARK — это система криптографического доказательства. Это позволяет некоторой сущности доказать, что что-то верно, не раскрывая другой информации. ZK-SNARK полезны в нескольких приложениях и областях, таких как блокчейны и поддающиеся проверке вычисления. Одним из известных приложений блокчейна является его использование в ZK-Rollups. ZK-Rollups — это блокчейны второго уровня, построенные поверх других блокчейнов (таких как Ethereum), которые используют ZK-SNARK (или другие системы криптографического подтверждения) для подтверждения правильности переходов состояний. То есть при каждом новом обновлении сети (когда добавляется новый пакет транзакций) вычисляется новое состояние сети и генерируется доказательство достоверности этого состояния. Важно отметить, что только одна организация должна создать это доказательство, после чего любой может убедиться в его достоверности. Желательными свойствами, которые обеспечивают ZK-Rollups, обычно являются (i) масштабируемость и/или (ii) сохранение конфиденциальности. Когда масштабируемость является единственным желаемым свойством, накопительные пакеты ZK иногда называют накопительными пакетами достоверности. Для вычисления доказательства в ZK-Rollups, предназначенных для масштабирования EVM Ethereum, используется ZK-EVM. По строгому определению, ZK-EVM — это набор криптографических программ (схем), которые отвечают за генерацию доказательства с нулевым разглашением (ZKP), хотя иногда в просторечии он относится ко всей совокупности ZK-свертывания общего назначения с поддержкой EVM. Определение ZK-SNARK -------------------- SNARK является кратким доказательством того, что утверждение верно. Формально это доказывает знание трассы выполнения алгоритма, который выдает правильное решение для определенной задачи. Точнее, доказывает знание непубличных и неконстантных значений трассировки выполнения. Эти значения в целом обычно называют свидетелем. Элементы свидетеля, входящие в состав входных данных алгоритма, составляют независимые свидетели, поскольку они существуют до выполнения алгоритма и не определяются другими элементами трассы выполнения. Публичные непостоянные значения трассировки выполнения, которые определяют экземпляр проблемы, решаемой алгоритмом, мы называем публичным оператором. ![](https://storage.googleapis.com/papyrus_images/77f70dd5d80108b165cdec7360d4b271ca851b90d00dcf5582e750e9bc2ac609.webp) 2\. Время проверки t\_v должно расти не быстрее, чем некоторые константы, умноженные на квадрат логарифма размера свидетеля w, и линейно зависеть от размера публичного высказывания x (при достаточно больших x и w, когда меняется только одно из них его размер): ![](https://storage.googleapis.com/papyrus_images/20857282ed4aa79fd90af5862b4c3b58609481898449c857efb51b661dee14c5.webp) N — Non-Interactive — генерация доказательства выполняется без получения каких-либо данных от верификатора. ARK — Аргумент знаний — аналогично обычному доказательству, но достоверность верна только против полиномиально ограниченного доказывающего, в то время как в доказательстве достоверность верна против вычислительно неограниченного доказывающего. Мы обсудим понятие надежности в следующем разделе. ZK — Zero-Knowledge — неразглашение свидетеля. Свойства ZK-SNARK ----------------- Есть три основных свойства ZK-SNARK, которые рассматриваются ниже. Полнота: если доказывающий знает правильную трассировку выполнения алгоритма, проверяющий должен быть убежден, что доказывающий обладает этим знанием. Надежность знаний: доказывающий может убедить проверяющего в том, что он знает правильную трассировку выполнения, только если доказывающий действительно знает ее, за исключением очень малой вероятности. Нулевое знание: верификатор ничего не знает о трассировке выполнения, кроме ее правильности. Системы доказательств PLONKish ZK-SNARK --------------------------------------- Коротко о PLONKish ZK-SNARK и их роли Для применения к некоторому алгоритму системе доказательства ZK-SNARK необходимо знать систему уравнений над конечным полем, описывающую отношения между значениями в таблице трассировки выполнения этого алгоритма (структура данных для хранения трассировки выполнения) таким образом, чтобы гарантировать целостность вычислений. Язык, используемый для выражения этой системы уравнений (также называемой системой ограничений), называется арифметизацией. Системы доказательства PLONKish ZK-SNARK используют арифметизацию с более высокой выразительной силой по сравнению со старыми системами доказательства. Первые позволяют использовать уравнения системы ограничений в виде произвольных полиномов от переменных с ограничениями, в то время как для более старых систем доказательств (т.е. основанных на R1CS) эти уравнения имеют вид линейных и квадратичных полиномов. Эта особенность систем доказательства PLONKish ZK-SNARK оказывает благотворное влияние на эффективность вычислений доказывающего и упрощает применение ZK-SNARK к различным алгоритмам. В результате в последнее время появилось много PLONKish систем доказательства ZK-SNARK: классический PLONK, Halo2, Kimchi, Plonky2, HyperPlonk и т. д. В Taiko мы используем вариант системы доказательства Halo2, основанный на полиномиальной схеме обязательств KZG. --- *Originally published on [Iryna](https://paragraph.com/@iryna-2/zk-snark)*