第2章 隐私保护技术

2.1 零知识证明

2.1.1 概念与理论介绍

1.概念介绍

零知识证明（Zero Knowledge Proof，ZKP）是由S.Goldwasser、S.Micali及C.Rackoff在20世纪80年代初提出的，其是指证明方能够在不向验证方提供任何有用信息的情况下，使验证方相信某个论断是正确的。零知识证明实质上是一种涉及两方或多方的协议，即两方或多方完成一项任务所需采取的一系列步骤。证明方向验证方证明并使其相信自己知道或拥有某一消息，但在证明过程中不能向验证方泄露任何关于被证明消息的信息。大量事实证明，零知识证明在密码学中非常有用，如果能够将零知识证明用于验证，将可以有效解决许多问题。

在有必要证明一个命题是否正确，又不需要提示与这个命题相关的任何信息时，零知识证明系统（也称为最小泄露证明系统）是不可或缺的。零知识证明系统包括两部分：宣称某一命题为真的证明方（Prover）和确认该命题确实为真的验证方（Verifier）。证明是通过这两部分之间的交互来执行的。在零知识协议的结尾，只有当命题为真时，验证方才会确认。但是，如果证明方试图证明一个错误的命题，那么验证方完全可能发现这个错误。这种思想源自交互式证明系统。交互式证明系统在计算复杂度理论方面已经具有非常独立的地位。

零知识证明起源于最小泄露证明。设P表示掌握某些信息并希望证实相关事实的实体，设V是证明这一事实的实体。假如某个协议向V证明P的确掌握某些信息，但V无法推断这些信息是什么，我们称P实现了最小泄露证明。而如果V除知道P能够证明某一事实外，不能得到任何其他知识，我们称P实现了零知识证明，相应的协议称为零知识协议。

基本的零知识证明是交互式的，需要验证方向证明方不断询问一系列有关其所掌握的“知识”的问题，如果证明方均能够给出正确回答，那么从概率上来讲，证明方的确很有可能知道其所声称的“知识”。例如，某人声称自己知道一个数独难题的答案，一种零知识证明的方式是验证方随机指定这一次按列、按行还是按九宫格来检测，每次检测不需要看到数字摆放的具体位置，只需检测出来是否包含数字1～9即可，只要验证的次数足够多，那么可以大概率相信证明方是知道数独题目的解的。但是，这样简单的方式还不能让人相信证明方和验证方均没有作假，在数独的案例中，两者有可能事先串通好，从而使得证明方在不知道答案的前提下通过验证。如果他们想让第三方信服，验证方必须也要证明自己每次的检测方案是随机的，且自己没有和证明方串通。

由于第三方观察者难以验证交互式零知识证明的结果，因此当我们向多人证明某些内容时，需要付出额外的努力和成本。而非交互式的零知识证明不需要互动过程，避免了串通的可能性，但是可能额外需要一些机器和程序来决定试验的序列。例如，在数独的案例中，通过程序的方式来决定哪一次按行、哪一次按列来检测，但是这个试验序列必须保密，否则验证方如果预先知道了试验的序列，就有可能利用这个信息提前准备，在并不知道真实“知识”的情况下通过验证。

零知识证明的内容可以概括为以下两类。

（1）“事实”陈述：如证明“一个特定的图可以进行三着色”或者“一个数是合数”；

（2）关于个人知识的陈述：如“我知道这个特定图的染色方案”或者“我知道一个数的因式分解”。

对于零知识证明，很多问题都有对应的加密方案，但并不是所有问题都有零知识证明的加密方案，S.Goldreich、S.Micali和C.Wigderson给出了理论上存在零知识证明解的有效范围。他们发现，在多项式时间内可以验证解的决策问题（问题的答案仅为是/否）存在已知的零知识证明的加密方案。只需在这样的NP问题中找到想要证明的论述，并转化为三色问题的一个实例，那么就可以利用已有的协议实现零知识证明。由于三色问题属于NPC问题（NP完全问题），任何NP问题都可以转化为这个问题的实例。

2.ZKP性质

（1）正确性。P无法欺骗V，换言之，若P不知道一个定理的证明方法，则P使V相信其会证明定理的概率很低。

（2）完备性。V无法欺骗P，若P知道一个定理的证明方法，则P（以极大概率）使V相信其能证明定理。

（3）零知识性。V无法获取任何额外的知识。

3.ZKP属性

（1）如果语句为真，诚实的验证方（正确遵循协议的验证方）将由诚实的证明方确信这一事实；

（2）如果语句为假，不排除“欺骗者可以说服诚实的验证方其是真的”的可能性；

（3）如果语句为真，证明方的目的就是向验证方证明并使验证方相信自己知道或拥有某一“知识”，而在证明过程中不可向验证方泄露任何有关被证明“知识”的内容。

零知识证明并不是数学意义上的证明，因为它存在小概率的误差，欺骗者有可能通过虚假陈述骗过证明方。换句话来说，零知识证明是概率证明而不是确定性证明，但是也存在一些技术能将误差降低到可以忽略的范围内。零知识的形式定义必须使用一些计算模型，最常见的是图灵机的计算模型。

2.1.2 zkSNARKs的设计与实现

简洁的非交互式零知识证明（zero-knowledge Succint Non-interactive Arguments of Knowledge，zkSNARK）的常用简称有zkSNARKs、zkSNARK、zk-SNARKs、zk-SNARK、zkSnarks、zkSnark、zk-Snarks、zk-Snark等。本书统一使用通用简称zkSNARKs。

zero-knowledge：证明的零知识性，不泄露要证明的“知识”；

Succinct：证明的数据量比较小；

Non-interactive：没有或者只有很少的交互；

Arguments：验证方只对计算能力有限的证明方有效，拥有足够计算能力的证明方可以伪造证明，这也称为“计算可靠性”（相对的还有“完美可靠性”）；

Knowledge：对证明方来说，在不知道证据（Witness，如一个哈希函数的输入或者一个确定默克尔树的节点的路径）的情况下，构造出一组参数和证明是不可能的。

zkSNARKs由以下四部分组成。

（1）多项式问题转化。

把需要验证的程序编写为一个二次多项式方程，即t（x）h（x）=w（x）v（x），当且仅当程序的计算结果正确时这个等式才成立，而证明者需要说服验证者这个等式成立。

（2）简单随机取样。

验证方随机选择一个秘密评估点s，将多项式乘法和验证多项式函数相等的问题简化为简单的数值乘法和验证等式t（s）h（s）=w（s）v（s）的问题。相对于验证多项式相等，随机取样验证简单、验证数据少。随机取样验证的安全性不及多项式等式验证，但如果足够随机，其安全性还是相当高的。

（3）同态编码/加密。

使用具有一些同态性质的编码/加密函数E（但不是全同态加密），这允许在只知道E（s）但不知道s的情况下计算E（t（s）） E（h（s）） E（w（s）） E（v（s））。“同态”是函数的特殊性质，包括加法同态性和乘法同态性。加法同态性指E（x+y）可以由E（x）和E（y）计算得出，乘法同态性指E（xy）可以由E（x）和E（y）计算得出。

（4）零知识。

证明方通过将E（t（s）） E（h（s）） E（w（s）） E（v（s））乘以一个数来替换其值，这样验证方就可以在不知道真实编码值的情况下验证E（t（s）） E（h（s）） E（w（s）） E（v（s））正确的结构。

有一个简单的想法是这样的，因为验证t（s）h（s）=w（s）v（s）和验证t（s）h（s）k=w（s）v（s）k（k≠0且是秘密随机数）几乎是完全一样的，而不同的地方在于如果你只接收到了t（s）h（s）k和w（s）v（s）k，那么从中获取t（s）h（s）或者w（s）v（s）的值就几乎是不可能的了。

当然了，这些都只是表层的部分，是为了更好地理解zkSNARKs的本质，下面我们开始详细介绍zkSNARKs。

1.NP问题及归约

解决一个问题需要花费一定的时间，如果解决问题需要的时间与问题的规模是多项式关系，则可以称该问题具有多项式复杂度。一般问题可分成两类：P问题和NP问题。P问题指在多项式时间内可解的问题；NP问题指不能在多项式时间内可解，但是可以在多项式时间内验证的问题。

很显然，P问题也是NP问题，但是对于NP问题是否也是P问题，目前还没有人能证明。一般认为，NP问题不等于P问题，也就是说，NP问题不存在多项式解法。

归约（Reduction）可以理解成问题的转化。任意一个程序A的输入，都能按某种法则将其变换成程序B的输入，使二者的输出相同，那么可以说，问题A可归约为问题B。

NPC问题即NP完全问题，其中，完全指图灵完备。所有的NP问题都能归约为NPC问题。简单来说，NP问题之间可以相互归约，如果一个NP问题可求解，那么其他NP问题一样能求解。

下面我们举例说明NP问题及NP问题的归约。

1）SAT问题

SAT问题即布尔公式满足性（Boolean Formula Satisfiability）问题。布尔公式定义如下：

（1）任意变量x₁、x₂、x₃…是布尔公式。

（2）假设f是布尔公式，?f（取反）也是布尔公式。

（3）假设f和g是布尔公式，f∧g（与）和f∨g（或）也是布尔公式。

若一个布尔公式是可满足的，则其输入为0或1，其输出为真。

SAT问题即找出所有可满足的布尔公式。

直观来看，SAT问题的求解除了枚举一个个可能的布尔公式，没有更好的办法，也就是在多项式时间内不可解。而如果知道一个可满足的布尔公式，验证其是SAT问题的一个解则非常方便（在输入是0/1的情况下，看其输出是否为真）。因此，SAT问题是一个NP问题。

2）PolyZero问题

如果f是一个变量都来自集合{0，1}的多项式，并且其中包含一个零项，那么PolyZero（f）=1。

一个布尔公式f可以通过如下的归约函数r转化为多项式：

r(x_i)=1-x_i

r(?f)=(1-r(f))

r(f∧g)=(1-(1-r(f))(1-r(g)))

r(f∨g)=r(f)r(g)

也就是说，一个SAT问题通过归约函数r，可以归约为一个PolyZero问题：当且仅当r（f）含有{0，1}中的一个0时，SAT（f）=PolyZero（r（f））或者f是可满足的。

总结一下，NP问题是在多项式时间内无解，但可以在多项式时间验证的问题，NP问题可以相互归约。

2.QSP问题

需要证明的问题肯定是NP问题，如果是P问题，则不存在问题解的“寻找”，也就不存在证明。简言之，zkSNARKs问题处理的都是NP问题。既然NP问题可以相互归约，首先确定一个NP问题，其他NP问题都可以归约为这个NP问题，再进行证明。也就是说，证明了一个NP问题，就可以证明所有NP问题。

QSP（Quadratic Span Programs）问题是NP问题，也特别适合zkSNARKs。QSP问题如下：给定一系列多项式，并给定一个目标多项式，找出多项式的组合以使其能整除目标多项式。

输入为n位的QSP问题定义如下。

（1）多个多项式：v₀，…，v_m，w₀，…，w_m；

（2）目标多项式：t；

（3）映射函数f：{（i，j）|1≤i≤n，j∈{0，1}}→{1，…，m}。

给定一个证据（Witness）u，若满足如下条件，即可验证u是QSP问题的解：

（1）a_k，b_k=1，k=f（i，u[i]_），其中u[i]是u的第i个比特位。

（2）a_k，b_k=0，k=f（i，1-u[i]）.

（3）v_aw_b能整除t，其中

v_a=v₀+a₁v₁+…+a_mv_m

w_b=w₀+b₁w₁+…+b_mw_m

对证据u的每位进行两次映射计算（u[i]及1-u[i]），确定多项式之间的系数，如果2n＜m，那么多项式的选择还是有很大的灵活性的。

如果证明方知道QSP问题的解，则需要提供证据u。验证方在获知证据u的情况下，按照上述规则恢复多项式的系数，验证v_aw_b是否能整除t，即th=v_aw_b。为了方便验证方验证，证明方可以同时提供h。在多项式维度比较大的情况下，多项式的乘法还是比较复杂的。

如前文所述，有个简单的做法，验证方与其验证整个多项式是否相等，不如随机挑选数值进行验证。假设验证方随机挑选验证数s，验证方只需验证t（s）h（s）=v_a（s）w_b（s）。

以上是基础知识，下面开始介绍zkSNARKs的证明过程。在深入QSP问题的证明细节之前，我们先介绍一个多项式问题的证明过程。

3.多项式问题的证明过程

假设一个多项式f（x）=a₀+a₁x+a₂x²+…+a_d-1x^d-1+a_dx^d，要证明一个多项式，即给定一个输入x，提供f（x）的证明。

1）有限群论基础（椭圆曲线）

选定一个椭圆曲线有限群，生成元是g，阶为n，则该群包含以下元素：g⁰，g¹，…，g^n-1。通过有限群加密的方式很简单，即E（x）=g^x。

2）选定随机数

验证方随机选择一个有限群中的元素并将其作为秘密域元素s，计算并发布以下结果（s不同阶的加密结果）：E（s⁰），E（s¹），…，E（s^d），其中，d为所有多项式的最大阶数，然后销毁s。

3）E（f（s））计算

对于任意多项式f，证明方可以根据E（s⁰），E（s¹），…，E（s^d），在不知道s的情况下，计算出E（f（s））。假设多项式为f（x）=4x²+2x+4，则

4）α对

由于秘密域元素s被销毁，验证方无法检验证明方计算的多项式的正确性。验证方随机选择另一个秘密域元素α，计算并发布以下偏移的加密值：E（αs⁰），E（αs¹），…，E（αs^d），然后销毁α。利用这些加密值，证明方可以计算E（αf（s））。对于f（x）=4x²+2x+4，E（αf（s））=E（4αs²+2αs+4α）=E（αs²）⁴E（αs¹）²E（αs⁰）⁴。因此，证明方需要发布A=E（f（s））和B=E（αf（s））。

A=E(f(s))=E(s²)⁴E(s¹)²E(s⁰)⁴

B=E(αf(s))=E(αs²)⁴E(αs¹)²E(αs⁰)⁴

验证方使用配对函数检验这些值是否匹配。

5）配对函数e

配对函数e定义：对于所有的x、y，有

e(g^x,g^y)=e(g,g)^xy

验证方使用配对函数e检验等式e（A，g^α）=e（B，g）。推导过程如下：

e(A,g^α)=e(E(f(x)),g^α)=e(g^f(x),g^α)=e(g,g)^αf(x)

e(B,g)=e(E(αf(x)),g)=e(g^αf(x),g)=e(g,g)^αf(x)

在验证方提供α对的情况下，证明方可以证明通过某个多项式计算出某个结果，而验证方不知道具体的多项式参数。

6）δ偏移

更进一步，证明方采用δ偏移，甚至不想让验证方知道E（f（x））。在采用δ偏移时，证明方不再提供A和B，而是随机进行一个δ偏移，提供A＇和B＇。

A＇=E(δ+f(s))=g^δ+f(s)=g^δg^f(s)=E(δ)E(f(s))=E(δ)A

B＇=E(α(δ+f(s)))=E(αδ+αf(s))=g^αδ+αf(s)=E(α)^δE(αf(s))=E(α)^δB

e(A＇,g^α)=e(E(δ+f(s)),g^α)=e(g^δ+f(s),g^α)=e(g,g)^α(δ+f(s))

e(B＇,g)=e(E(α(δ+f(s))),g)=e(g^α(δ+f(s)),g)=e(g,g)^α(δ+f(s))

7）小结

至此我们完成了多项式的证明过程。完整的多项式证明过程如图2-1-1所示。

4.QSP问题的zkSNARKs证明

zkSNARKs证明过程分为三个阶段：初始化设置阶段、证明方提供证据阶段、验证方验证阶段。

QSP问题：已知多项式v₀，…，v_m，w₀，…，w_m，目标多项式t（不超过d阶）及输入二进制串u，证明方找到a₁，…，a_m，b₁，…，b_m（在一定程度上取决于u）及多项式h满足：

th=(v₀+a₁v₁+…+a_mv_m)(w₀+b₁w₁+…+b_mw_m)

1）初始化设置阶段

初始化公共参考串（Common Reference String，CRS），即预先初始化的公开信息。选定秘密参数s和α，发布以下信息。

（1）s和α的计算结果：

E(s⁰),E(s¹),…,E(s^d),E(αs⁰),E(αs¹),…,E(αs^d)

（2）多项式的α对计算结果：

E(t(s)),E(αt(s))

E(v₀(s)),…,E(v_m(s)),E(αv₀(s)),…,E(αv_m(s))

E(w₀(s)),…,E(w_m(s)),E(αw₀(s)),…,E(αw_m(s))

（3）多项式的秘密参数β_v、β_w、γ的计算结果：

E(γ),E(β_vγ),E(β_wγ)

E(β_vv₁(s)),…,E(β_vv_m(s)),E(β_ww₁(s)),…,E(β_ww_m(s))

E(β_vt(s)),E(β_wt(s))

2）证明方提供证据阶段

在QSP的映射函数中，如果2n＜m，则1，…，m中有些数字没有映射到。这些没有映射到的数字组成I_free，并定义v_free（x）=∑_ka_kv_k（x），其中，k为未映射到的数字。

证明方需要提供的证据u如下：

其中，、W/W＇、H/H＇是α对，用于验证v_free、w、h是否是多项式形式；t是已知的、公开的；Y用来确保v_free（s）和w（s）的计算采用一致的参数。

3）验证方验证阶段

在QSP的映射函数中，如果2n＜m，则将1，…，m中所有映射到的数字作为系数组成的二项式定义为v_in（x）=∑_ka_kv_k（x），其与v_free互补。

验证方需要验证如下等式是否成立：

式（2-1-1）验证、W/W＇、H/H＇是否是α对。

式（2-1-2）验证V_free和W的计算是否采用一致的参数。因为v_free和w都是多项式，因此它们的和也是多项式，所以采用γ参数进行确认。验证过程如下：

因此，等式e（E（γ），Y）=e（E（β_vγ），V_free）e（E（β_wγ），W）成立。

式（2-1-3）验证v（s）w（s）=h（s）t（s），其中v（s）=v₀（s）+v_in（s）+v_free（s）。简言之，在逻辑上确认v、w、h是多项式，并且v、w采用同样的参数，满足v（s）w（s）=h（s）t（s）。

至此，整个QSP的zkSNARKs证明过程已见雏形，如图2-1-2所示。

4）δ偏移

为了进一步“隐藏”V_free和W，需要额外选取两个偏移δ_free和δ_w。对v_free（s）、w（s）、h（s）进行如下变形，验证方用同样的逻辑验证。

v _free(s)→v_free(s)+δ_freet(s)

w(s)→w(s)+δ_wt(s)

h(s)→h(s)+δ_free(w₀(s)+w(s))+δ_w(v₀(s)+v_in(s)+v_free(s))+δ_freeδ_wt(s)

5）小结

至此，zkSNARKs的推导逻辑就基本完整了。zkSNARKs的证明过程分为以下几步。

（1）问题转化：将一个需要证明的NP问题转化为选定的NP问题（如QSP问题）；

（2）参数设置：设置参数的过程也是挑选随机数的过程，同时提供CRS；

（3）证明方获取证据u，通过CRS计算证据；

（4）验证方验证证据及响应的证据。