零知识证明 - 证明隐私代理方案

这几天在看zkSummit7峰会视频。第一个Topic就把我吸引了：

https://www.youtube.com/watch?v=SCIuwh9ya8U

Efficient Private Delegation of zkSNARK Provers，即高效zkSNARK证明隐私代理。

Pratyush Mishra的演讲比较精彩，清晰明了的讲解了代理方案的缘由，以及实现的原理。建议对这个topic感兴趣的小伙伴都听一听。这篇文章结合视频的内容，讲解我的理解。

先回顾一下zkSNARKs的场景的应用模型：Prover进行相关的证明，并把证明传输给Verifier进行验证。注意的是，这个证明生成是在Prover本地。

ZKP的应用越来越多，有这样一个场景：电路的证明在Prover本地生成不太合适，亦或电路的证明时间太长，亦或Prover计算能力有限。很自然的就有了将ZKP的证明外包的想法。

ZKP的证明外包的想法非常自然，但是，有个非常大的隐患：信息泄漏。本来ZKP是用来保护信息的，简单的外包协议有可能泄漏相关隐私数据。如何保证隐私的情况下做到ZKP证明外包是这个Topic的目标：

目标有两点：1/ 生成证明的高效。如果采用复杂的协议，证明生成比本地还慢就没有啥意义了。2/ 原来的所有witness信息都必须保护。

也许有人会说，可以用全同态来解决这个问题。但是，全同态的代价比较大，不合适。

可以结合基于域值的隐私方案做到零知识证明生成外包。

也就是说，只要有1个worker是诚实的，证明的隐私信息就是安全的。思路有了，就是详细地看看zkSNARK协议的可行性了。

目前的隐私的代理协议能支持基于PIOP的证明系统。支持的证明系统的特点：1/ 采用KZG或者内积乘法之类的多项式承诺方案 2/ 采用PIOP框架。至于性能，整个演讲的最后给出了更多的数据。

整个方案是基于MPC实现：

是时候考虑一些细节了。采用MPC，需要考虑证明系统的复杂性。整个证明系统可以看成两部分组成：1/ PIOP 2/ 多项式承诺。

详细分析每个部分如何采用MPC实现代理前，回顾一下采用PIOP以及多项式承诺的零知识证明方案的框架：

多项式通过承诺，并且承诺值作为Oracle的输入，产生随机抽查的点（Query）。在query的点上进行多项式打开和证明。深入细节之前，基于加法的密钥信息共享方法是几个基础。

如果密钥信息分割成几部分，并且整个协议是支持加法同态，也就是能支持隐私代理。针对零知识证明协议的两大部分，实现相对应的MPC方案，最终实现零知识证明的证明代理。

整体的流程如下图所示：

详细看看两部分MPC实现的细节。先看看PIOP的部分：

PIOP的部分的计算主要涉及到四种：前三种都是线性的（也就是说“加法同态”），最后一种计算多项式乘法并不是加法同态。一般情况下，计算两个多项式的乘法分为三步：

通过FFT获取在2d域上的多项式值。获得多项式的值的乘法结果后，通过iFFT获取乘法结果的多项式系数。第一步和第三步都是加法同态的。但是第二步的乘法不是。可以想象一下，多个worker是想在不暴露所有的信息数据的前提下，获取乘法结果的多项式的部分数据。在这样的前提下，这些worker可以将多项式的分割信息发回给Delegator。因为Delegator是可以看到所有信息的，Delegator可以进行多项式还原，并做乘法后，将结果再进行分割后发给多个worker。

由于Delegator的参与，PIOP的过程可以实现Delegate了：

接着看多项式承诺和打开的逻辑，这部分逻辑天然是支持加法同态的，显得就比较自然和简单：

最后，演讲给出了一些初步的测试数据：

通过零知识证明的代理，性能会大幅提高，支持的电路也能扩大。

总结：

随着ZKP的应用越来越多，零知识证明的证明隐私代理也变的越来越重要。在一些场景下，本地证明的生成时间比较长，如何既保证数据的隐私同时实现快速的证明外包是一个很有意义的话题。在zkSummit7的这个演讲给出一个方案：在PIOP+多项式承诺的零知识证明方案中，可以结合MPC实现证明隐私代理。

本文首发于：https://mp.weixin.qq.com/s/j4tbBYYRIWqQ70rBfZ3c4w