微软推出首个无信任设置的zkSNARK技术方案Spartan，数据并行工作负载速度快16倍

“Microsoft （微软）宣布推出一种高效且通用的零知识证明技术方案 Spartan，该方案能在更短时间内以更高效的方式实现简洁非交互的零知识证明（zkSNARK），是首个无需做可信设置的 zkSNARK 方案。”

本文介绍了Spartan，这是用于rank-1约束满足性（R-1CS）的零知识简洁非交互式知识参数（zkSNARKs）家族中的一位新成员，R-1CS是一种可归纳算术电路可满足性的NP完备语言。 Spartan包含了一项独特功能，它为NP提供了第一个没有受信任设置（即透明的）的zkSNARK，验证证明时会产生亚线性成本，无需NP语句结构的一致性。 此外，Spartan还为zkSNARK提供了一种时间最佳证明者。

为了实现这些结果，我们引入了新的技术，这些技术与总和检查（sum-check）协议（一种开创性的交互式证明协议）进行结合：（

（1）计算commitment，一种用于创建对计算描述的简洁commitment的原语；该技术对于验证者在投资一次的公共计算以预处理给定的NP语句之后获得亚线性成本至关重要；

（2）SPARK，一种将所有现有的可提取多项式commitment方案转换为有效处理稀疏多线性多项式的密码编译器。该技术对于实现时间最优证明者至关重要。

（3）将R-1CS的压缩编码为低次多项式。最终结果是NP的公共代币简洁的交互式知识参数（可以看作是总和检查协议的简洁变体）；我们使用现有技术将其转换为zkSNARK。

通过将SPARK应用于不同的commitment方案，我们获得四个zkSNARK，其中验证者的成本和证明大小取决于基础commitment方案（从O（log ^ 2n）到O（√n））（n表示NP语句的大小） 。这些方案中的三种不需要可信的设置，而一种方案则需要通用且可更新的一次性可信设置。

通过约8,000行Rust语言代码，我们将Spartan作为一个库来实现。 我们使用该库在随机预言模型中构建一种透明的zkSNARK，其中安全性在离散对数假设下成立。 我们通过实验对其进行评估，并将其与最新的zkSNARKs进行比较，以将R1CS实例的大小限制为大约2 ^ {20}。在没有受信任设置的方案中，Spartan可以提供最快的证明者，依据基准线的加速比为大约36-152倍，产生的证明短于1.2–416倍，并且以3.6–1326倍的速度提升产生最少的验证时间。 与具有受信任设置的最新zkSNARK相比，Spartan的证明者对于任意R1CS实例的速度快2倍，对于数据并行工作负载的速度快16倍。

《 Spartan zkSNARK库 》下载