本文介绍了一种新的SNARKs构造方法,用于在整数上进行计算,并提供了一种简单但新颖的方法来构建高效的证明系统。该方法通过使用多线性SNARKs,并结合“具有模余数的承诺方案”这一新工具,将现有的SNARKs“编译”成整数上的论证,实现了高效的范围检查、混合域仿真以及RSA群中的计算验证。
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 作为公共输入提供。 它还允许以相同数量的约束来模拟任何大小的域, 并在同一电路中模拟(并在它们之间切换)任意数量的不同域。
在上面的例子中,我们选择模数 p 为素数, 但对于复合模数 N,例如 RSA 模数 N=p⋅q,它同样适用。 例如,这允许在整数电路中有效地验证 RSA 签名和 RSA 累加器。
使用 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/(logB) 个。 因此我们选择 B st.
BlogB⋅1log2(y)<BlogB⋅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——在这种情况下,你有一个常规的多项式承诺方案。
至于海龟,它体型巨大,以至于船上的人 把它当成一个岛屿。一位商人报告说: “从海里升起,我们发现了一个岛屿,上面有 绿色植物,我们上岸挖坑生火做饭,然后岛屿开始移动,水手们说: “回到船上!这是一只海龟!火的热量 唤醒了他,我们会迷路的!”’
– 动物之书, 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 助手,为大家转译优秀英文文章,如有翻译不通的地方,还请包涵~
如果觉得我的文章对您有用,请随意打赏。你的支持将鼓励我继续创作!