zkCNN: Zero Knowledge Proofs for Convolutional Neural Network Predictions and Accuracy

* 关于卷积神经网络的零知识证明
* 看起来很有意思

## 摘要

* 本文提供了一种方法允许向他人证明，对于样本的预测结果是由当前CNN推理得到，并且不会泄露关于CNN的模型参数数据。方案也可以被推广，用于证明秘密CNN模型在公共数据集上的准确性。
* zkCNN的基础是一个新的sumcheck协议，用于线性时间证明快速傅里叶变换和卷积，这甚至比直接计算结果要快。我们还介绍了关于CNN预测的交互式证明的几个改进和推广，包括验证卷积层、ReLU的激活函数和最大池化。
* zkCNN可以支持具有15M参数和16层的VGG16的大型CNN。只需要88.3秒就能生成证明，比现有方案快1264倍。证明的大小为341KB，验证者的时间仅为59.3毫秒。方案可以进一步扩展，以证明相同的CNN在20张图像上的准确性。

## 前置知识

### 神经网络

* 本文仅针对含有 Conv, Act, ReLU, Pooling 的线性神经网络，针对 VGG16。

### 交互式证明

* 交互式证明就是有一个证明者(Prover) 和一个验证者(Validator)，通过证明者和验证者多轮交流，让验证者相信，证明者以接近于1的概率是真的。

### 多项式承诺

* 为了使得证明者不能再交互过程中，根据交互内容而修改自己操作，所以对于需要用到的一些多项式先做一些承诺(Commitment)。
* 最直观的方案就是把多项式的多个点的取值通过默克尔树Hash起来，这样就不可以再次更改这个多项式了。但是这个极为简单的方案不隐藏多项式的任何部分，证明起来也费时费力。
* [Kate多项式承诺](https://www.iacr.org/archive/asiacrypt2010/6477178/6477178.pdf)又称KZG承诺，利用椭圆曲线可以构造非常短的证明，而且验证起来也非常快，并且可以在多项式的任意一个点验证多项式的值。
* 下图是另一种利用全0多项式的方案，参考自[这里](https://learnblockchain.cn/article/2165)
* ![title](https://leanote.com/api/file/getImage?fileId=638c1d03ab64411710a6cdcf)

### Sumcheck 协议

* 用于让验证者相信，证明者正确的计算了 ![title](https://leanote.com/api/file/getImage?fileId=63899abeab64411709a86893)。
* 流程如下
* ![title](https://leanote.com/api/file/getImage?fileId=63899ad1ab64411710a6bb4a)

### Multilinear Extension

* Multilinear Extension 是把任意离散映射转化为多项式的方式。
* 我们可以构造一个等于函数 *$\beta(x,y)$ = 1 if $x = y$ else $0$*, 我们可以把这个拓展到多bit ![title](https://leanote.com/api/file/getImage?fileId=6389a799ab64411709a868fd)
* 同样，对于一个数组映射 $V[i]$，我们就可以造一个*多项式* $\tilde{V}$ 满足 $\tilde{V}(i) = V[i]$，并且 $\tilde{V}$ 是一个sumcheck的形式。
* ![title](https://leanote.com/api/file/getImage?fileId=6389ab6aab64411709a8691d)
* 那么我们可以用sumcheck的方式验证一方是否对这个数组求和了。
* 同样利用 Multilinear Extension， 我们可以把数组和矩阵编码成多项式。

### GKR 协议

* 算数电路：由加法门和乘法门构成的电路。
* GKR协议可以验证证明者是否真的执行该算数电路。
* 首先把电路分成很多层，第 $i$ 层有 $s_i$ 个门。定义电路连接算符 $add$ 为 *$add(g,x,y) = 1$ if 加法门g使用了上一层门x和门y的输出作为输入 else $0$*，同理可以定义乘法连接。定义 add 和 mul 函数只是为了用多项式描述电路连接。
* 令 $V_0$ 是电路的输出，$V_d$ 是电路的输入。那么电路第 $i$ 层第 $g$ 个门的输出 $V_i(g)$可以写为 Multilinear Extension的形式：![title](https://leanote.com/api/file/getImage?fileId=6389b7a9ab64411710a6bc3a)
* 那么通过 sumcheck 协议，就可以检查证明者是否执行了某一层的电路计算，验证者只需要验证一个 $f_i(g,x,y)$。这样可以一路归约到最初的数据输入层，把最终的输出变成对两个输入的验证。

### 零知识论证（Zero Knowledge Arguments）

* 零知识论证与零知识证明的区别在于零知识论证假设证明者是 probabilistic polynomial time 的，而零知识证明则假设证明者是 Unbounded 的。

### 零知识多项式承诺（PC）

* 本文使用的多项式承诺方案是基于离散对数群的IPA协议，但也可以换成别的zkPC。如果多项式大小是d，IPA的证明大小和验证时间是 $O(\log d)$，而构造证明的时间则是 $O(d)$。
* Schwartz–Zippel lemma: 用于验证一个概率多项式是否是0-多项式（即处处等于0），具体操作为随便找个地方求个值看看是不是0。
* 结合多项式承诺，GKR协议就可以拓展到证明者可以先对自己的多项式做承诺，从而在不泄露输入数据的情况下，证明结果是从该数据计算得到的。

### QAP问题

* QAP 问题是这样一个NP问题：给定一系列的多项式，以及给定一个目标多项式，找出多项式的组合能整除目标多项式。
* 利用QAP问题求解困难但验证简单的特点，证明者可以在不给出自己数据的前提下，证明自己执行了某个程序。
* 本文并没有用到QAP，只是提到了一些基于QAP的通用可验证计算方式。

### 之前的神经网络计算验证方案

* 比如可以使用对于算数电路的GKR协议，直接验证卷积计算，但这样的电路大小是 $O(n^2w^2)$的。
* 第二种是把直接卷积电路改成FFT算法对应的电路，电路大小是 $O(n^2\log n)$的，由于 $n >> w$，所以并不比上面好多少。
* 第三种是把卷积变成多项式乘法，电路大小是 $O(n^2 + w^2)$，但由于需要使用到大量的多项式承诺，所以实际运行起来额外开销也很大。
* 本文的证明时间是 $O(n^2)$，并且额外开销很小。

## 主要方法

### 针对卷积的 Sumcheck

* 这块的核心idea是利用 sumcheck 的形式把矩阵乘法求和给放进去，从而降低复杂度。
* 一维傅里叶变换可以写成乘以傅里叶矩阵的形式 $\mathbf{a} = F \cdot \mathbf{c}$。
* ![title](https://leanote.com/api/file/getImage?fileId=6389f144ab64411709a86ba0)
* 我们要把对 $\mathbf{a}$ 的正确性验证变为对 $\mathbf{c}$ 的正确性验证。
* 也就是我们要针对如下式子验证
* ![title](https://leanote.com/api/file/getImage?fileId=638a0f2bab64411710a6bf2b)
* 用如下方式就可以 $O(M+N)$ 的时间内构造大小为 $O(\log N)$ 的证明
* ![title](https://leanote.com/api/file/getImage?fileId=638a186bab64411710a6bf72)
* 验证只需要 $\mathbf{c}$ 和 $\mathbf{F}$ 就可以了，通过简单的算法技巧就能得到时间复杂度为 $O(\log^2 N)$ 的验证复杂度。
* 如上是针对一维卷积的，改到二维卷积也很简单，只需要把二维卷积核padding到和图像一样大小然后拍平就行。

### 针对卷积神经网络的GKR

* 这一部分拓展了一下 GKR，将加法门和乘法门的输入从两个拓展到多个。
* ![title](https://leanote.com/api/file/getImage?fileId=638b2f66ab64411710a6c74b)
* ![title](https://leanote.com/api/file/getImage?fileId=638b2f8aab64411710a6c74d)
* 显然这也是一个 sumcheck。
* 以及作者表示本方法兼容[Zhang提出](https://eprint.iacr.org/2020/1247)的可以使用前面任意层作为输入，而非仅前一层。
* 如果按照正常的实现，就需要evaluate 两个输入，作者用random linear combination方法降低成验证一个输入：
* ![title](https://leanote.com/api/file/getImage?fileId=638b40e4ab64411710a6c7b5)
* 那么这个式子继续套用 sumcheck 之后就只需要一个值了！

### 进一步优化卷积

* 上面只是解决了卷积操作，实际的卷积有很多个 Kernel，需要操作$C_{out}$次卷积。
* 对于卷积核而言就是要计算：
* ![title](https://leanote.com/api/file/getImage?fileId=638b4633ab64411710a6c7d9)
* 直接使用多次卷积，证明时间是 $O(C_{in}C_{out}n^2)$，但可以利用FFT的线性性，在IFFT的时候，从而降低一个 $C_{in}$。
* ![title](https://leanote.com/api/file/getImage?fileId=638b46b1ab64411710a6c7dd)
* 虽然FFT操作没有被优化，理论复杂度也没变，但是IFFT变快了，常数上快了一倍。

### 一些额外细节

* 量化：因为实际权重是浮点，但zkCNN需要数字范围是离散的，所有的数字都进行 Q 比特量化。（本来神经网络在实际部署的时候，也需要进行量化操作）
* ReLU+Pooling：average pooling 很好说，因为就是个线性操作。只要能把ReLU和MaxPooling 描述成等于零的多项式等式，就能通过检查一个多项式是否是零来检查是否满足要求。
* ReLU:![title](https://leanote.com/api/file/getImage?fileId=638b4a32ab64411709a8751a)![title](https://leanote.com/api/file/getImage?fileId=638b4a3bab64411710a6c7f3)
* Pooling:![title](https://leanote.com/api/file/getImage?fileId=638b4a45ab64411710a6c7f4)
* ReLU+Pooling：这部分证明者需要额外提供的信息也就只有 $\bar{x_{max}}$ 和计算时的位宽。
* 最终网络的样子会如下：![title](https://leanote.com/api/file/getImage?fileId=638b4b06ab64411710a6c7f8) 其中 W 和 bit-decomposition 都会提前使用多项式承诺保证不会被修改。

### 最终复杂度分析

* 证明的总构造时间复杂度为 ![title](https://leanote.com/api/file/getImage?fileId=638b4bdeab64411710a6c802)
* 证明大小和验证时间为 ![title](https://leanote.com/api/file/getImage?fileId=638b4bfcab64411709a87528)![title](https://leanote.com/api/file/getImage?fileId=638b4c07ab64411709a87529)
* 所需的多项式承诺大小为 ![title](https://leanote.com/api/file/getImage?fileId=638b4c1fab64411709a8752a)，多项式承诺的构造时间为 ![title](https://leanote.com/api/file/getImage?fileId=638b4c4aab64411709a8752c)，验证时间为 ![title](https://leanote.com/api/file/getImage?fileId=638b4c55ab64411710a6c806)
* 利用 Fiat-Shamir heuristic 可以轻易的把交互式的证明，变成非交互的证明以提升通讯效率（即把所有需要发送的随机数，除了第一个以外，改成第一个随机数与中间结果一块的Hash值）。

## 性能评估

* ![title](https://leanote.com/api/file/getImage?fileId=638b5056ab64411709a8754a)
* ![title](https://leanote.com/api/file/getImage?fileId=638b506dab64411710a6c825)
* 可以看到比之前使用大量加乘门的通用算法效率高很多。

## 总结

### 优点

* 相比之前的方法，在构造卷积的证明上显著降低了复杂度，更加实用了。
* 由于理论复杂度降低，而且实际应用中常数也不错，所有速度非常快，证明也很小。
* 证明构造时间达到了理论最低值（即模型的大小）。

### 缺点

* 需要公开模型结构，但模型结构往往和参数一样重要。
* 速度不够快，仅针对VGG16都要90s左右时间构造证明。对于常用大模型（例如Latent Diffusion 和各种BeRT）构造时间可能需要超过一天，远大于模型推理时间。
* 证明构造部分使用了大量的递归证明，导致无法并行，从而在大规模数据下很难加速。
* 构造证明的时间不可能低于模型大小，所以很难再进一步从理论上提升速度。

### 可能的改进

* 对于区块链验证神经网络计算方面，或许可以不从可验证计算角度考虑，从带有相应奖惩机制的交叉验证方向去考虑。最坏情况就是随机两个矿工执行了同样的计算，如果结果不一致两者都没有收益，这只需要额外一倍的计算量，会显著快于当前可验证计算方案。如果利用了Batch的特性，上百个矿工之间互相交叉部分验证，额外计算量甚至可以降低到5%以内。
* 把能并行的部分全都交给CUDA，甚至特质FPGA或者ASIC（因为GPU没有对FFT的加速），能否把这个证明构造时间再加速几个数量级，这样这个东西就很实用了！
* 现在只针对一个输入样例（Batchsize=1）构造了证明，考虑进Batch那么平均构造时间就会低很多了！

### 启发

* 把原来一些大量的低级操作（例如直接基于加乘门实现）改为根据特点执行的高级操作（分析卷积特性），可以有很好的优化空间。

wuvin

导航

最近发表

友情链接