基于隐私外包计算技术实现zkSNARK生成证明加速

1

介绍

零知识简洁非交互式知识证明（zkSNARK）是一种证明系统，允许证明者说服验证者某个陈述为真，而不泄露有关证明者证据的任何信息。‘零知识’意味着由证明者生成的证明不会泄露有关证明者证据的任何证据信息。因此，zkSNARKs经常用于在区块链和加密货币中保护隐私。

例如，Groth16，是最重要的zkSNARK之一，比如加密货币zcash使用该技术以实现隐私交易。它可以证明交易有效，而不透露发送方、接收方和交易详情。因此，它为发送方和接收方提供了强大的隐私保护。

2

zkSNARK的算法和性质

形式上，关于 的zkSNARK是一个由算法元组 组成，定义如下：

1. 在输入安全参数 后，输出公共全局参数 。
2. 在输入公共全局参数 ，公共实例 和私有证人 后，输出证明 。
3. 在输入公共全局 ，公共实例 和证明 后，根据 是否有效，输出接受或拒绝。

zkSNARK 需要满足完整性、健全性和零知识，定义如下：

1. 完整性：如果一个陈述为真，并且一个诚实的证明者遵循协议，那么诚实的验证者将接受该证明。
2. 健全性：如果陈述为假，那么恶意的证明者只能以可忽略的概率说服验证者。
3. 零知识：由证明者生成的证明不会透露有关证明者证人的任何信息。

3

现有zkSNARK的优势和劣势

优势：

术语‘简洁’意味着可以在很短的时间内验证证明，并且存储在链上的最终证明非常小，例如基于KZG的zkSNARKs（如Groth16、Plonk和Marlin）的验证时间和证明大小与电路大小无关，这意味着验证时间和证明大小与电路中的门数量无关。

以下表格列出了一些主流的zkSNARKs的证明大小和验证时间。

证明系统	证明大小	验证器时间
Groth16	200字节	1.5毫秒
Plonk/Marlin	400字节	3毫秒
BulletProofs	1.5千字节	3秒

劣势：

目前，大多数现有的zkSNARKs，如Groth16、Marlin和Plonk，都依赖于复杂的密码操作，如椭圆曲线运算、多项式计算和其他数学变换。这些操作计算成本高昂，可能导致证明者时间的增加，这些操作的数量与电路的大小呈线性关系，这意味着证明者的工作几乎与电路大小成正比，例如，要证明传统SHA256压缩函数的原像，证明者需要在至少20000的多项式上执行多项式算术和椭圆曲线操作。

FFT和MSM是两个最耗时的操作，虽然FFT相对于传统的多项式乘法大大减少了操作的数量，但它仍然涉及大量的数学运算，其复杂度为 ，其中 是多项式的阶。

MSM总是用于计算对多项式的KZG承诺，并包括在大素数域上的群加法和乘法，群加法通常需要进行数十次域操作，而乘法则需要数千次，这使得MSM在计算上非常昂贵。

4

解决方案

研究人员通过从不同的角度考虑问题来解决问题，主要包括减少FFT操作的数量，优化在GPGA上的FFT和MSM以及将重型的证明计算委托给更强大的机器。

减少FFT操作的数量

FFT是生成证明的主要瓶颈，提高证明速度的一种方法是减少FFT操作的数量。许多研究人员使用多元多项式而不是单元多项式从而避免FFT操作，一些经典的zkSNARKs包括HyperPlonk、Libra和Virgo。

优化在FPGAs/GPUs上计算FFT和MSM的算法

FFT和MSM是证明生成的主要瓶颈，我们可以使用FPGA和GPU来对其进行加速。

FPGA和GPU都具有强大的并行处理能力。MSM和FFT中的许多计算步骤可以并行执行，使得这些硬件在加速这些任务方面非常高效。

此外，FPGA和GPU通常比通用的中央处理单元（CPU）更节能。它们专注于执行特定类型的计算，因此在相同功耗下提供更高的性能。

最后，MSM和FFT中的数据通常以类似流的方式进行处理。FPGA和GPU都可以实现有效的并行数据流处理，从而提高整体性能。

将证明计算委托给更强大的机器

DIZK将证明计算分发到几台强大的机器中，旨在优化每台机器的空间复杂度。然而，DIZK会向受委托的机器泄露证据，从而泄漏隐私，如果证人泄漏给任何第三方，恶意方可以为所欲为。例如，在隐私支付中，私钥是隐私信息的一部分，如果私钥泄漏，任何人都可以使用该密钥生成有效的交易并花费这笔钱。

为了解决隐私泄漏问题，我们专注于zkSNARK证明的委托证明，其中几台机器进行证明计算，而不知道有关证人的任何其他信息。在一系列博客中，我们将强调一些关于委托证明的最新工作。

5

实现方法

在大多数应用中，私有输入的隐私应得到保护。在本节中，我们将重点关注实现隐私代理的一些常见方法，主要包括全同态加密和安全多方计算。

全同态加密

全同态加密（FHE）是一种公钥加密方案，允许在加密数据上执行任意的加法和乘法计算。基于FHE的隐私代理模型非常简单，由委托者和代理者组成，委托者首先加密其证据，并直接将其发送给工作者，代理者在证据密文上计算证明，并将加密证明发送回来，最后，委托者解密证明。因此，既保护了隐私又实现了代理。

然而，在实际应用中，这是不切实际的，因为FHE在计算开销方面相对昂贵。代理者需要在计算开销较大的算法（即FHE）中调用另一个计算开销较大的算法（即zkSNARK证明生成器），从而显着降低效率。此外，计算资源受限的代理者可能也会因昂贵的同态加密和解密而受到影响。

安全多方计算

另一种方法是使用多方计算（MPC），它是一种允许多个方共同计算其输入函数，同时保护隐私输入的密码技术。

更详细地说，代理者首先将其证据使用秘密共享方案（例如Shamir Secret Sharing）生成碎片，每个碎片都不会透露有关证据的任何信息。之后，委托者将证人的份额发送给几名代理者，然后，这些代理者相互交互，并使用他们收到的碎片生成证明，最后，每个代理者得到一个证明的份额，委托者得到最终的证明。

与FHE相比，MPC的计算复杂性较低。它广泛用于许多实际应用中。因此，基于MPC的委托既能保护证据的隐私，也在实际环境中具有实用性。

6

结论

总的来说，尽管现有的zkSNARKs具有快速的验证时间和小的证明大小，但是生成证明的时间仍然是一个瓶颈，因为zkSNARK证明生成的计算依赖于昂贵的密码操作。

为了解决这些问题，我们可以将zkSNARK证明生成的计算委托给几台强大的机器，然而，大多数工作并未考虑到证据的隐私。如果证据泄漏给任何第三方，恶意方可以为所欲为，为了避免这种泄漏，我们在本文专注于zkSNARK证明的隐私代理。

翻译： 杨赟博

来源：https://blog.zk.link/from-zero-to-hero-how-to-speed-up-zero-knowledge-proofs-with-delegation-d57abc24b57b

END

热文推荐