zk-SNARKs: A gentle introduction
发表信息
作者
- Anca Nitulescu
笔记
Zero-Knowledge Succinct Non-interactive Arguments of Knowledge (zk-SNARKs) are non-interactive systems with short proofs (i.e., independent of the size of the witness) that enable verifying NP computations with substantially lower complexity than that required for classical NP verification. This is a short, gentle introduction to zk-SNARKs. It recalls some important advancements in the history of proof systems in cryptography following the evolution of the soundness notion, from first interactive proof systems to arguments of knowledge. The main focus of this introduction is on zk-SNARKs from first constructions to recent efficient schemes. For the latter, it provides a modular presentation of the frameworks for state-of-the-art SNARKs. In brief, the main steps common to the design of two wide classes of SNARKs are: • finding a “good” NP characterisation, or arithmetisation • building an information-theoretic proof system • compiling the above proof system into an efficient one using cryptographic tools Arithmetisation is translating a computation or circuit into an equivalent arithmetic relation. This new relation allows to build an information-theoretic proof system that is either inefficient or relies on idealized components called oracles. An additional cryptographic compilation step will turn such a proof system into an efficient one at the cost of considering only computationally bounded adversaries. Depending on the nature of the oracles employed by the initial proof system, two classes of SNARKs can be considered. This introduction aims at explaining in detail the specificity of these general frameworks
以下是中文翻译：
零知识简洁非交互式知识论证（Zero-Knowledge Succinct Non-interactive Arguments of Knowledge，简称zk-SNARKs）是一种具有简短证明（即，与见证规模无关）的非交互式系统，它能够以远低于经典NP验证所需复杂度的方式来验证NP计算。
这是一篇关于zk-SNARKs的简短而通俗的介绍。文章回顾了密码学中证明系统发展史上的一些重要进展，追溯了从最初的交互式证明系统到知识论证的演变过程，重点关注可靠性概念的发展。
本介绍主要聚焦于zk-SNARKs，从最初的构造到近期的高效方案。对于后者，文章以模块化的方式介绍了当前最先进的SNARKs框架。
简而言之，两大类SNARKs设计的主要共同步骤是： • 寻找”良好的”NP特征刻画，或算术化（arithmetisation） • 构建信息论证明系统 • 使用密码学工具将上述证明系统编译成高效系统
算术化是指将计算或电路转换为等价的算术关系。这种新的关系允许构建信息论证明系统，该系统要么效率低下，要么依赖于称为预言机（oracle）的理想化组件。额外的密码学编译步骤将这样的证明系统转变为高效系统，代价是只考虑计算能力有限的对手。根据初始证明系统所使用的预言机的性质，可以考虑两类SNARKs。本介绍旨在详细解释这些通用框架的特性。