浅谈零知识证明协议——zk-SNARK

 

一、介绍

简洁非交互式零知识证明（zero-knowledge succinct non-interactive argument of knowledge，以下简称zk-SNARKs）是一种新颖的零知识密码学形式，它指的是一种证据构造，在不泄露机密信息的情况下，人们可以证明自己拥有某些信息，能够满足一些预设的条件，同时在证明者和验证者之间无需任何交互。

二、zk-SNARKs概述及定义

zk-SNARK使得人们可以对形如“给定一个公开的谓词F,和一个公开输入x，我知道某个秘密输入w，使得F(x,w)为真”的语句进行证明和验证（比如“给定某个等式33a3-7b2+3=0，我知道某个数字a使得等式成立”）。zk-SNARKs协议由三个算法组成：Setup、Prover、Verify。zk-SNARKs的典型流程如图1所示。

                                                                          图1 zk-SNARKs方案典型流程

 

1. Setup算法接受一个以R1CS（Rank-1 Constranint System）的形式描述的谓词F作为输入，并输出两个公开的**：证明**pkF和验证**vkF。其中pkF用于生成证明，而任何人都可以通过vkF验证该证明的有效性。针对任意一个谓词F，该步骤仅需运行一次，生成的**可以反复用于关于该谓词的NP语句而不会影响其安全性。尽管生成的两个**是公开的，但是生成**过程中的所有中间运算结果都必须保密并且在**生成后销毁，否则攻击者可以利用这些结果伪造证明，因此这个步骤必须由可信机构进行。
2. Prover算法以pkF、一个公开输入x，以及一个秘密输入w作为输入，并输出一个证明π。π可以证明“对于公开输入F和x，我知道某个秘密输入w，使得F(x,w)为真”，同时不暴露任何关于秘密输入w的信息。
3. Verifier算法以vkF、x以及π作为输入，并根据π的有效性输出“接受”或者“拒绝”。

上述算法中，任何人都可以运行Prover和Verifier算法来进行证明的生成和验证。假设输入x的大小为k，F的“运行时间”为TF，zk-SNARKs的“简洁”特性使得Verifier算法的运行时间为O(k)，与F无关，并且生成的证明π的大小为常数，不随输入或F的规模增大而增大。此外pkF的大小也与k成正比。但是由于TF通常很大，而Setup和Prover的时间复杂度与TF相关，vkF的大小也与TF成正比，因此本文的设计目标以及实现目标之一就是尽量减小TF的大小和输入长度以提升算法的整体性能。

三、zk-SNARKs语言及接口

正如之前提到的，目前主流的zk-SNARKs实现方法接受以R1CS形式表述的谓词F。本节将首先介绍zk-SNARKs中用于描述计算实例的形式语言R1CS，然后给出zk-SNARKs的半形式化定义。

R1CS语言：与普通的计算模型不同，在zk-SNARKs中，所有的数据均为某个p阶的有限域F上的元素。一个在域F上的R1CS实例ϕ可以由一个五元组表示：ϕ=（k, N, M, a, b, c），其中k是输入的数量，N是所有变量的个数（包括公开输入和秘密输入，k≤N），M是约束个数，a, b, c均为(1+N)×M的矩阵。

ϕ的输入是一个向量 x∈，而一个见证（witness，也就是前文所说的秘密输入）是一个向量w∈。假向量z=(x||w||1)∈（其中‖为拼接操作，表示将两端的元素拼接在一起，因此z为一个N+1维向量），当且仅当式(2-1)成立时称输入(x,w)满足ϕ。

对于每一个j∈[M]，上述等式可以看作是一个关于输入的二次约束（Quadratic Constraint）。以下给出一个构造实例：

假定谓词Fa, b: a3+a+b=35，则可以构造如下二次约束：

假设要证明的NP语句为“给定某个公开的数字b，我知道某个a使得F(a,b)成立”。设公开输入x=(y)，秘密输入w=(a, var1, var2, var3)，再根据(2-2)式构造出a, b, c即完成了一个完整的R1CS实例构造。

zk-SNARK定义：一个zk-SNARK方案由三个算法组成：Setup S，Prover P，Verifier V。其定义如下：

1. Setup: 给定一个F上的R1CS实例ϕ=k, N, M, a, b, c，以及秘密随机输入r，S输出一个证明**pk以及验证**vk。
2. Prover：给定针对ϕ生成的pk、公开输入 x∈Fk以及见证w∈FN-k，P输出一个证明π，证明(x, w)满足ϕ。
3. Verifier：给定针对ϕ生成的vk、公开输入 x∈Fk以及证明π，V输出一个比特b，当b=1时表示接受证明π；b=0时表示拒绝证明π。

zk-SNARK性质：设pk、vk为算法S在ϕ上的输入，zk-SNARK具有以下性质：

1. 完整性（Completene）：对于任意满足ϕ的输入(x, w)，和π← P(pk, x, w)，均有 Vvk, x, π=1。
2. 可靠性（Soundness）：对于任意无法满足ϕ(x, ⋅)的输入x，没有一个计算上快速的方法可以生成使得Vvk, x, π=1的证明π。
3. 零知识（Zero-knowledge）：对任何满足ϕ的输入(x, w)，由π← P(pk, x, w)生成的证明π不泄露任何关于w的信息。
4. 简洁性（Succinctness）：π的大小为O(1)，并且V的运行时间为O(k)。

四、 zk-SNARK常用协议

目前比较常见的协议是基于Groth等人的工作（以下简称Groth16），它是目前性能最佳的zk-SNARK协议之一。本节简要描述Groth等人的方案构造。

QAP（Quadratic Span Programs）：为了使用该方案，首先需要将R1CS实例转化为QAP。一个QAP实例实质上是将其对应的R1CS约束打包到了一个多项式中，由一个元组(k, N, M, A,B,C,D)表示，其中 k, N, M的含义与之前相同，而A,B,C均为1+N维的多项式向量，由R1CS实例中的向量a, b, c通过插值得到；D是F的子集，大小为M。

在QAP中，输入仍为x∈Fk，见证则为(w,h)，其中w∈，h∈，令z=(x||w‖1)∈，则当且仅当式(2-3)成立的时候，我们称输入(x,(w,h))满足QAP(k, N, M, A,B,C,D)。

参考文献双线性映射群编码：Groth16需要用到双线性映射编码，此种编码依赖于双线性映射群。一个双线性映射编码中有三个群G1, G2, GT，其中G1, G2写作加法群，GT写作乘法群，并且它们的阶数均为素数p，另外有一个映射e:G1× G2→ GT，并且对任意α,β,s,t∈Fp满足e(α⋅s+β⋅t)=α⋅e(s)+β⋅e(t)。

 

[1] Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014). Succinct non-interactive zero knowledge for a von Neumann architecture. In 23rd {USENIX} Security Symposium ({USENIX} Security 14) (pp. 781-796).

[2] Wu, H., Zheng, W., Chiesa, A., Popa, R. A., & Stoica, I. (2018). {DIZK}: A Distributed Zero Knowledge Proof System. In 27th {USENIX} Security Symposium ({USENIX} Security 18) (pp. 675-692).