ZNARKs：整数上的SNARKs - ZKSECURITY

ZNARKs - 面向整数的 SNARKs

SNARKs 总是用于有限域上的计算吗？事实证明并非如此。

今天，我们将探讨我们最近的预印本中提出的技术 从第一性原理出发，构建面向整数的完全简洁的论证， 该论文研究了面向整数电路的 SNARKs 的构建。 这项工作提供了一种简单但新颖的方法来构建高效的证明系统， 用于涉及整数的计算，它避开了处理整数时通常遇到的许多复杂情况。 这些技术使我们能够使用一种新工具将现有的（多线性） SNARKs “编译”成面向整数的论证：具有模余数的多项式承诺。

应用

现有的 SNARKs（通常）是为有限域上的计算而设计的： 有限域上电路的可满足性或程序的执行。 一些工作也探索了其他有限环上的 SNARKs，通常是 Z2k，即 k 位整数。 在这两种情况下，这意味着计算中的每个值都具有预先有界的有限大小。 在这项最新的工作中，我们引入了第一个（完全简洁的）面向整数的 SNARK： 面向整数的 SNARK 允许电路赋值（或程序中的内存）取 Z 中的任何值。 无论计算中的值有多大，证明都保持可靠和简洁。

面向整数的计算有许多潜在的有趣应用， 包括模拟（甚至非常小的）素数域。 我们博客的普通读者都知道所有适用于有限域的电路“技巧”， 但可能不太熟悉面向整数的计算/电路， 让我们首先探讨一些面向整数的 SNARKs 可能特别有用的应用示例。

使用平方和的高效范围检查

整数上的范围检查不需要将值分解为位， 这意味着范围检查的成本与范围的大小无关。 诀窍在于观察到所有非负整数都可以表示为四个平方数的和， 换句话说，对于任何 n≥0，证明者都可以（高效地）找到 a,b,c,d 使得：

n=a2+b2+c2+d2

使用这种技术，你可以通过证明你知道 a1,b1,c1,d1 和 a2,b2,c2,d2 使得：来证明 n∈[0,B]

n=a12+b12+c12+d12

B−n=a22+b22+c22+d22

换句话说，n≥0 且 B−n≥0。 这可以优化，Couteau, Peters 和 Pointcheval 表明 n∈[low,high] 等价于存在 a,b,c 使得：

4⋅(n−low)⋅(high−n)+1=a2+b2+c2

因此，你可以通过 4 个 R1CS 约束或单个 PlonKish 门获得恒定成本的范围检查。

高效的混合域模拟

我们可以很容易地在整数电路中模拟素数域：值 x¯∈Fp 表示为整数 x∈Z 使得 x≡x¯modp。给定两个值 x,y∈Z, 我们可以通过要求以下条件来约束它们的乘积为 z≡x⋅ymodp：

z=x⋅y−q⋅p

对于证明者选择的某个 q∈Z。加法也是类似的。 请注意，我们不要求证明者完全减少结果， 因为没有“模数溢出”，即使证明者使用等价类的大代表值，电路也能正常工作：他只是让一切变得更慢。 如果需要唯一的代表值，你可以简单地使用上面（非常有效）的范围检查来检查 z∈[0,p−1]。

这甚至允许模拟“动态”选择的域 Fp，例如，其中 p 作为公共输入提供。 它还允许以相同数量的约束来模拟任何大小的域， 并在同一电路中模拟（并在它们之间切换）任意数量的不同域。

验证 RSA 群中的计算

在上面的例子中，我们选择模数 p 为素数， 但对于复合模数 N，例如 RSA 模数 N=p⋅q，它同样适用。 例如，这允许在整数电路中有效地验证 RSA 签名和 RSA 累加器。

一种智力上的好奇：Q-电路

使用 Z 的证明系统来证明关于有理数 Q 的陈述是相当容易的： 我们将有理数表示为表示分数 n/d 的整数对 (n,d)。 只要需要，我们可以通过对某个 sign∈Z 强制执行 d⋅sign∈[1,∞) 来强制 d≠0，\ 并使用“平方和”技术来强制范围检查。\ 请注意，可以通过计算 d1⋅d2⋅…⋅dn 并强制该乘积不为零来批量处理许多非零检查。

为了强制执行分数 n1/d1⋅n2/d2=n3/d3 的乘积，我们可以要求：

n3=n1⋅n2 d3=d1⋅d2

除法可以类似地强制执行为：

n3=n1⋅d2 d3=d1⋅n2

可以通过强制执行以下条件来检查相等性：

d1⋅n2=d2⋅n1

最难的部分是分数的和，这需要一个公分母：

n3=n1⋅f1+n2⋅f2 d3=d1⋅f1 d1⋅f1=d2⋅f2 f1≠0 f2≠0

对于证明者选择的 f1,f2。

我不知道 Q-电路有任何实际用途， 但你可以为一个特征为零的域拥有一个 SNARK，这有点有趣。

题外话：指纹识别

在我们深入研究如何构建面向整数的 SNARKs 的细节之前，让我们先稍微了解一下“指纹识别”： 假设你有一个面向整数的电路 C，它由加法和乘法 门组成，扇入为 2，扇出任意。 例如，它可能看起来像这样：

假设你想说服某人你知道一个见证 w=(X,Y,Z) 使得 C(w)=0。 对于上面的电路，一个简单的协议就足够了：证明者只需发送 w，验证者检查 C(w)=0。

然而，请注意，乘法增加了电路内部值的大小： 乘积 (X⋅Y)⋅Z 的大小是 X、Y 和 Z 的大小之和。 事实上，因为你可以在电路的每一层连续地乘以中间结果，所以内部值的大小随着电路深度的增加呈指数增长。 例如，计算 x2k 的电路的深度为 k，在每一层计算 x2i=x2i−1⋅x2i−1， 但 x2k 的大小为 O(2k⋅|x|)。 因此，仅对于小深度的电路，直接验证电路的计算是可行的…

我们能做得更好吗？

当然可以！即使用一种称为“指纹识别”的技术，它依赖于随机性。 该技术在 计算复杂性：一种现代方法 由 Sanjeev Arora 和 Boaz Barak 撰写。 这个想法非常简单，而不是天真地重新计算电路， 在收到见证 w 后， 验证者选择一个随机素数 p 并计算电路模 p。 如果结果为零， 那么验证者确信该见证是正确的。

稍微不正式地说：

Prp[C(w,x) mod p=0]>ϵ⟺C(w,x)=0

为什么这行得通？ 好吧，假设 y=C(x,w) 且 y≠0，即电路不满足，但说服验证者它满足。 y 的最大值是：

|y|≤max{|x|,|w|}2d

其中 d 是电路的深度。 现在 y=0 mod p 当且仅当 p 除以 y。 有多少个不同的素数可以除以 y？好吧，一个非常粗略的估计小于 log2⁡(y)。 此外，小于 B 的素数大约有 B/(log⁡B) 个。 因此我们选择 B st.

Blog⁡B⋅1log2⁡(y)<Blog⁡B⋅1log2⁡(max{|x|,|w|})⋅2d<ϵ

那么，如果 ϵ 非常小，我们的随机素数 p 应该有多大？

从上面的等式可以清楚地看出，如果我们选择 B≫2d，那么 ϵ 将很小。 换句话说，素数的大小需要大致与电路的（乘法）深度成正比。

向下迈出指数级的一步

我们论文中的关键思想是通过使电路仅具有恒定深度来“缩小”这个想法。 幸运的是，恒定深度电路是 ZK 证明系统中的常态： 通过引入新变量，将更大深度的电路展平为恒定深度电路， 例如，检查 R1CS 关系的电路的乘法深度为 1。

素数的使用 允许我们使用现有的 SNARK 技术有效地证明电路的可满足性，因为我们只需要证明素数域上电路的可满足性。

具有模余数的多项式承诺

在上一节中，验证者从证明者那里收到了整个见证 w∈Zn。 这是一个问题：我们正在尝试构建一个 SNARK，并且我们希望通信量尽可能小。 解决方案是让证明者承诺 w 并发送承诺给我们。

由于之后我们需要计算 “C(w) mod p”， 因此拥有一个多项式承诺方案来处理多线性多项式 f(X1,…,Xk)∈Z[X1,…,Xn] 会很有用。 该方案允许在 x1,…,xk 模任意素数 p 处打开多项式， 显示： y=f(x1,…,xk) mod p 关键是你可以在承诺多项式后选择 p。 这与通常的多项式承诺方案形成对比， 在通常的多项式承诺方案中，素数在承诺时是固定的。 这个新原语显然比通常的多项式承诺方案更强大： 你总是可以只固定素数 p——在这种情况下，你有一个常规的多项式承诺方案。

Zaratan

至于海龟，它体型巨大，以至于船上的人 把它当成一个岛屿。一位商人报告说： “从海里升起，我们发现了一个岛屿，上面有 绿色植物，我们上岸挖坑生火做饭，然后岛屿开始移动，水手们说： “回到船上！这是一只海龟！火的热量 唤醒了他，我们会迷路的！”’

– 动物之书, Zakariya al-Qazwini (13th Century)

Zaratan 是我们用于整数的新 SNARK。 它结合了使用类似 DARK 的技术构建的具有模余数的多项式承诺 以及一个标准的素数域上的多线性 SNARK：在我们的例子中是 Spartan。

由于技术原因，我们不能将我们的构建基于 DARK 承诺： DARK 承诺仅对有理函数 f(X1,…,Xk)/N 类具有约束力，其中 N 是一个小的整数。 这对于有限域上的 SNARKs 来说是可以的，因为 N−1 mod p 是一个域元素（除非 p|N）， 这意味着 f(X1,…,Xk)/N mod p 是一个域上的多项式， 然而，这对于我们的应用来说是不够的，因为我们需要它是一个整数上的多项式。 相反，我们需要从 Block et al. 的效率远低于的多项式承诺方案中推导出一个方案。

然而, 由于我们只需要一个具有模余数的多线性多项式承诺方案 来编译标准的现成的多线性 SNARK（例如 Spartan 或 HyperPlonk）, 我们有一些想法，可以从非常不同的技术中创建更有效的实例化。敬请期待!

• 原文链接： blog.zksecurity.xyz/post...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～