[区块链]基于 MPC 的零知识证明协议

参考文献：

1. Jawurek, M., F. Kerschbaum, and C. Orlandi. 2013. “Zero-knowledge using garbled circuits: how to prove non-algebraic statements efficiently”. In: ACM CCS 13: 20th Conference on Computer and Communications Security. Ed. by A.-R. Sadeghi, V. D. Gligor, and M. Yung. ACM Press. 955–966.
2. Evans D, Kolesnikov V, Rosulek M. A pragmatic introduction to secure multi-party computation[J]. Foundations and Trends? in Privacy and Security, 2018, 2(2-3): 70-246.
3. 应用密码学：协议、算法与C源程序（机工社大黑皮）

ZKP

零知识证明协议的基本定义在这篇文章。

交互式

最近看到了另一种描述 ZKP 的表述：

1. Verifier拥有一个困难问题实例$H_1$，Prover声明自己拥有$H_1$的解法$S_1$
2. Prover利用$1$个随机数$r$，将这个难题实例$H_1$，转变为另一个同构的难题实例$H_2$。同时，依据$S_1$和$r$，得到对应的解法$S_2$
3. Prover对解法$S_2$做承诺，然后将难题$H_2$和承诺值$c$都发送给Verifier
4. Verifier随机要求Prover给出如下两个声明之一的Proof：
   1. 要求Prover证明两个难题同构，$H_1?H_2$
   2. 要求Prover公开$S_2$，并证明$S_2$是$H_2$的正确解法
5. Prover给出所要求的Proof，Verifier验证它
6. 两者反复执行$n$次 step 1 ~ step 5，直到Verifier相信Prover确实拥有$S_1$（一般而言，$n=10$就很好了）

完备性：诚实的Prover拥有$S_1$，他总是可以给出 step 4 中所要求的两种Proof，因此Verifier最终会相信他。

可靠性：一个恶意的Prover，他没有$S_1$，为了通过 step 4 的验证，他不得不猜测Verifier的选择。如果猜测Verifier会执行 step 4.1，那么敌手就在 step 2 中选择一个$H_2?H_1$，同时他不拥有对应的$S_2$。如果猜测Verifier会执行 step 4.2，那么敌手就在 step 2 中随机生成一个难题$H_2^{\prime }$以及对应的解法$S_2^{\prime }$，但同时他无法证明$H_1?H_2^{\prime }$。

零知识性：一个恶意的Verifier，他无法让第三方Alice相信上述 Proof 的有效性。假设敌手用一个摄像机记录协议的每一步，即使视频中显示Prover总是给出了正确的 Proof，Alice也总是可以质疑：每当Prover猜对了，Verifier就保留视频；每当Prover猜错了，Verifier就删除视频。人们无法区分真实记录（in the real world）和伪造记录（in the ideal world）！

人们已经证明：

1. 任何 NP 命题都包含一个 ZKP
2. 任何数学证明都能转化为一个 ZKP
3. 能使用交互式证明完成的任何事，也能用交互式 ZKP 完成

非交互式

上述的Alice不相信的原因是，她没有介入 ZKP 的交互。为了Prover为了让任何人相信他的Proof，他需要一个非交互式的ZKP。每当Prover发布Proof后，任何人都可以验证这个Proof是否有效（身份认证协议、签名协议）。

利用 Hash 函数$H$代替了 Verifier：

1. Prover声明自己拥有一个困难问题实例$H$的解法$S$
2. Prover利用$n$个随机数 { r i } \{r_i\} {ri?}，将这个难题实例$H$，转变为随机的$n$个同构的难题实例 { H i } \{H_i\} {Hi?}。同时，依据$S$和 { r i } \{r_i\} {ri?}，得到对应的解法 { S i } \{S_i\} {Si?}
3. Prover对解法 { S i } \{S_i\} {Si?}做承诺，然后将难题 { H i } \{H_i\} {Hi?}和承诺值 { c i } \{c_i\} {ci?}都公开
4. Prover计算 b = H ( { c i } ) b = H(\{c_i\}) b=H({ci?})，截取前$n$比特$b=b[1:n]$，然后依据 b [ i ] ∈ { 0 , 1 } b[i] \in \{0,1\} b[i]∈{0,1}给出如下两个声明之一的Proof：
   1. 当$b[i]=0$，Prover证明两个难题同构，$H?H_i$
   2. 当$b[i]=1$，Prover公开$S_i$，并证明$S_i$是$H_i$的正确解法
5. Prover公布 step 4 中的$n$个Proof，任何人都可以验证它：先根据 { c i } \{c_i\} {ci?}计算出$b$，然后依次检查第$i$个Proof是否是关于$b[i]$声明的合法证明。

这儿的$H$扮演了无偏随机比特发生器的角色。如果恶意Prover不拥有$S$，那么他最多只能给出 step 4 中的某一个Proof，而不能同时都给出Proof，因此为了欺骗，他必须能够预测$H$的输出。

当然，是Prover（而非Verifier）来挑选的$b$，因此敌手完全可以随机猜测$b$的前$n$位，然后尝试不同的 { S i } \{S_i\} {Si?}组合，直到全部猜对$n$个比特。此时，敌手就可以给出一个合法的 Proof 了。为了抵挡敌手的穷举攻击，我们需要将$n$设置的比较大，例如$64,128$

JKO（2013）

ZKP 可以作为一种特殊的 malicious secure computation，根据声明$y$构造电路$C(?,y)$（$C(x,y)=1?(x,y)\in R$），其中作为Prover的一方输入证据$x$，作为Verifier的一方什么也不输入，最后电路结果$C(x,y)$输出给Prover。

很明显，利用任意的 cut-and-choose-based 2PC protocol，总是可以实现上述的恶意敌手安全的两方计算。但是，直接使用 C&C 技术的 2PC 协议，对应的混淆电路过于巨大。

Jawurek, Kerschbaum 和 Orlandi 观察到：由于 Verifier 没有输入，因此如果让他来生成 GC，那么这个 GC 可以同时用来 checking 和 evaluation：翻转角色，我们让 Verifier 生成一个Yao’s Garbled Circuit，在打开后 Prover 虽然能观察到全部的 label，理论上可以获得 Verifier 的任意明文输入比特，但是奈何 Verifier 根本就没有隐私输入。因此，只需要令重复因子为$\rho =1$，C&C 技术下的混淆电路规模大幅减小。

JKO协议如下：

1. Verifier $P_1$ 生成$C(?,y)$的$1$个混淆电路 GC，发送给 Prover $P_2$
2. $P_2$ 利用 OT 协议获得 $x$ 对应的混淆输入，计算电路得到证明结果 v ∈ { 0 , 1 } v \in \{0,1\} v∈{0,1}的混淆输出$k_{out}^v$
3. $P_2$对$k_{out}^v$做承诺，只将承诺值$c=commit(k_{out}^v,r)$发送给$P_1$
4. 接收到$c$后，$P_1$打开 GC，$P_2$检查它是否正确，
   1. 如果电路正确，那么$P_2$发送$(k_{out}^v,r)=decommit(c)$给$P_1$
   2. 如果电路错误，那么$P_2$终止协议（发现恶意Verifier）
5. $P_1$验证解承诺是否合法，
   1. 如果合法，$P_1$输出标签$k_{out}^v$对应的明文输出$v$（当$v=1$时，$P_1$相信$P_2$证明了$(x,y)\in R$）
   2. 如果非法，$P_1$输出$0$（发现恶意Prover）

明显上述的非交互式 ZKP 协议是完备的。下面讨论其安全性：

1. secure against a cheating verifier（可靠性）：在 Verifier 打开 GC 之前，Prover 已经对输出结果做了承诺，因此恶意的Prover难以在不知道$x$的情况下计算出$k_{out}^1$
2. secure against a cheating prover（零知识性）：只有当 Prover 验证这个 GC 确实是电路$C(?,y)$ 的正确的混淆版本之后，才会揭露最终计算结果$k_{out}^v$，因此 Verifier 无法利用错误的电路来学习到关于$x$的任何信息。