🎉 Gate xStocks 交易开启啦,现货、合约、Alpha齐上线!
📝 在Gate广场发帖,晒出你的交易体验或精彩截图,瓜分$1,000大奖池!
🎁 广场优质创作者5名,每人独享$100合约体验券!
🎉 帖文同步分享到X(推特),浏览量前十再得$50奖励!
参与方式:
1️⃣ 关注 @Gate广场_Official
2️⃣ 带 #Gate xStocks 交易体验# ,原创发帖(不少于20字,仅用活动标签)
3️⃣ 若分享到推特,请将链接提交表单:https://www.gate.com/questionnaire/6854
注:表单可多次提交,发布更多帖文可提升获奖机会!
📅 7月3日16:00—7月9日24:00(UTC+8)
详情:https://www.gate.com/announcements/article/45926
每一条体验,都有机会赢取大奖!快在Gate广场show出你的操作吧!
zk-SNARK的构建及案例
TL;DR
待证明的问题-算术电路-R1CS-多项式
因为多项式的特性有效的缩短了验证时间,实现了简洁性。
简单来说,就是在推导多项式的过程中,多选取两个随机数,以此推导出的多项式能让验证者无法从中获取原多项式的系数,即证明者的秘密输入,以此实现 ZK。
在证明开始前,引入了一个第三方,即可信设置,将原本验证者挑选随机数的任务交给了可信设置,从而实现验证者和证明者之间的非交互。
ZK 技术近两年在 Web3 领域备受关注。从 Rollup 开始,越来越多不同赛道的项目都开始尝试使用 ZK 技术。在这之中,SNARK 和 STARK 是大家最常听到的两个名词,为了后期更好地理解ZK技术的应用,本文将从非技术的角度简化阐述 SNARK 的证明逻辑,然后会以 Scroll 的 zk Rollup 为例来说明 zk 证明系统的运行。
文章旨在阐述基本逻辑,便于阅读,会尽量避免术语使用,且不会深入探讨数学转换等细节,如有疏漏,敬请谅解。
2012年1月,加州大学伯克利分校教授 Alessandro Chiesa 与人合作撰写了 SNARK 的论文,提出了术语 zk-SNARK。
zk-SNARK,全称 Zero-Knowledge-Succinct Non-Interactive Argument of Knowledge,是使用了 ZK技术的一种证明系统。需要注意的是,SNARK 是一类方案的名称,有很多不同的组合方法都可以实现 SNARK。
zk-SNARK 要解决的是“计算验证问题”,即验证者能否在不知道证明者隐私的情况下,高效地验证计算结果。
下面将以 zk-SNARK 的简化版构建流程来说****明该系统是如何结合零知识达到高效验证的。
zk-SNARK 的构建
将待证明问题转化为多项式
简单来说,SNARK 的思路是将证明陈述是否成立转换成证明多项式等式是否成立。
整个转换过程:待求证的问题➡算术电路➡R1CS➡多项式➡多项式之间的转换
待求证的问题➡算术电路
要通过计算证明一个问题是否为真,首先就要将待证明的问题转化成一个计算问题,而任何计算都可以描述为一个算术电路。
算术电路通常由常数、“加法门”、“乘法门”组成,通过门的叠加,我们可以构建出复杂的多项式。
上图中的算术电路构建的多项式为:(Inp1+Inp2)*(-1)= Output
现实中的问题要转为算术电路极其复杂,我们可以将之简单理解为:输入一些内容,内容经过电路转化,最终输出一个结果。即:
基于算术电路的概念,我们构造一个用于生成证明的算术电路,即:
该电路中包含了两组输入,公开输入 x 和秘密输入w。公开输入x意味该内容是待证明问题的固定值,验证者和证明者都知晓,秘密输入 w 则意味着该内容只有证明者知晓。
我们构建的算术电路为 C( x, w ) = 0,即通过电路输入x与w,最终的输出结果为0。证明者和验证者知道电路输出为0,且公有输入为x的情况下,证明者需要证明自己知道秘密输入 w。
算术电路➡R1CS
我们最终需要一个多项式,但算术电路不能直接转化为多项式,需要 R1CS 作为二者间的媒介,故先将算术电路转换为 R1CS。
R1CS,全名为 Rank-1 Constraints (一阶约束系统),是一种描述电路的语言,本质上是一种矩阵向量方程。具体来说,R1CS 是由三个向量 (a,b,c) 组成的序列,R1CS 的解是一个向量 s,其中 s 必须满足方程:
其中 . 代表内积运算。
此间具体的数学转换可以参见 Vatalik:Quadratic Arithmetic Programs: from Zero to Hero
我们只需要知道,R1CS 的作用是对算术电路中的每个门的描述进行限定,使得每个门之间的向量满足以上关系。
R1CS➡多项式
在得到 R1CS 这个媒介后,我们就可以将其等价转换成多项式。
矩阵和多项式之间可以进行如下图所示的等价转换:
多项式
转化为矩阵
根据上述等价转换的性质,对于满足 R1CS 的矩阵,我们可以使用拉格朗日插值法,还原出多项式每一项系数,基于这个关系,我们可以将 R1CS 矩阵推导为多项式关系,即:
注:A, B, C分别代表一个多项式
一个多项式对应我们想要证明的问题所对应的一个R1CS矩阵约束,通过以上转化,我们可以知道,多项式之间满足以上关系,就说明我们的R1CS矩阵是正确的,从而说明证明者在算术电路中的秘密输入也是正确的。
到这我们的问题就简化为:验证者随机挑选一个数 x,让证明者证明 A(x) * B(x)=C(x) 成立,如果成立,说明证明者的秘密输入正确。
多项式之间的转换
复杂的算术电路中,有成千上万个门,我们需要对每个门验证其是否满足R1CS约束。换句话说,我们需要验证数次 A(x) * B(x)=C(x) 等式成立,但是逐次单独验证的效率太低,如何能做到一次性验证所有门的约束的正确性?
为了方便理解,我们引入一个 P(x),令 P(x) = A(x) * B(x) – C(x)
我们知道,任意的一个多项式只要它有解,就可以将它分解成线性多项式。故我们将 P(x) 拆分为 F(x) 和 H(x),即:
然后将 F(x) 公开,这就意味着存在一个 H(x) = P(x)/F(x) ,从而我们要验证的多项式最终转变为 :
A(x) * B(x) – C(x):包含多项式的系数,只有证明者知,即秘密输入。
F(x) :一个公开的多项式,验证者和证明者皆知,即公开输入。
H(x) :证明者通过计算得知,验证者不可知。
而最终要证明的问题为:多项式等式 A(x) * B(x) – C(x) = F(x) * H(x),在所有x上都成立。
现在只需要验证一次多项式就可以验证所有约束是否满足矩阵关系。
到这里我们就完成了将待证明的问题转化成只需要验证一次的多项式,实现了系统的简洁性。
但是这个实现的简洁性是让验证者的验证时间缩短,那证明大小呢?
简单来说,在证明协议中,使用的是 Merkle 树的结构,这有效的降低了证明的大小。
整个转换过程完成以后,自然而然的会产生两个问题:
因为多项式实现了证明的简洁性。零知识证明的问题就是验证计算满足多个约束的问题,而多项式可以一个点验证多个约束。换句话说,验证者本来要验证 n 次才能确认的问题,现在只需要验证一次就能极大概率地确认证明的正确性。
这是由多项式的特性决定的,即:一个多项式在任意点的计算结果都可以看做是其唯一身份的表示。对于两个多项式,它们只会在有限的点上相交。
对于上述的两个 d 阶多项式:A(x) * B(x) – C(x) 和 F(x) * H(x),如果它们不相等,它们最多只会在d 个点上相交,也就是在 d 个点上的解相同。
完成了多项式的转换,我们就要进入多项式证明阶段。
证明多项式成立
为了便于阐述,我们采用多项式 P(x) = F(x) * H(x)。
现在,证明者要证明的问题是:在所有 x 上,P(x) = F(x) * H(x)。
证明者和验证者对以上多项式的验证过程如下:
但是我们仔细思考就会发现以上流程存在一些问题:
针对上述问题,我们进行以下优化:
优化以后我们发现证明系统依旧需要验证者和证明者之间进行交互,如何才能实现非交互?
实现非交互
为了实现非交互,SNARK 引入了可信设置(Setup)。
换句话说,在证明开始前,将原本属于验证者的选择随机挑战点的权力交给一个可信的第三方,第三方选择了随机参数 λ 后,将加密后的 λ 放在 R1CS 电路中,以此生成 CRS(Common Reference String,公共参考字串)。验证方能从 CRS 中获取属于自己的 Sv,证明方能从 CRS 中获取属于自己的 Sp。
需要注意的是,λ 在生成 Sv 和 Sp 后,需要被销毁,若 λ 被泄露,可能被用来通过虚假验证伪造交易。
zk-SNARK 工作流程
在明白 SNARK 的构建流程后,基于我们构造的可生成证明的算术电路,zk-SNARK 的证明流程如下:
通过电路 C 和随机参数 λ ,生成后续证明者和验证者使用的随机参数 Sv、Sp。
证明者通过随机参数 Sp,公共输入 x,秘密输入 w,计算出证明 Π。
验证者通过随机参数 Sv,公共输入 x 和证明 Π 来验证是否存在 C(x,w)=0。同时,验证证明是否是通过电路 C 计算得出。
到此,我们就完成了整个 zk-SNARK 的讲解,下面来看看实际运用的案例。
案例:以 Scroll 的 zk Rollup 为例
证明系统的作用是让证明者说服验证者相信一件事;
对于 zk 证明系统而言,是要让验证者相信由 zk 算法计算出的 Zero-Knowledge Proof(零知识证明)为真。
我们以 Scroll 的 zk Rollup 为例来说明 zk 证明系统的运行。
Rollup 是指链下计算,链上验证。对 zk Rollup 而言,交易在链下执行后,证明者需要对交易执行后产生的新的状态根生成 zk 证明,再将证明传到 L1 Rollup 合约进行链上验证。
需要注意的是,在 zk Rollup 中存在两类区块:
以下是 Scroll 的 zk Rollup 的工作流程:
从以上流程可以看到,Roller 是该系统中的证明者,Rollup 合约是验证者。Roller 对在链下执行的交易生成一个 zk 证明;Rollup 合约验证该证明,若验证通过,Rollup 合约就会直接采纳提交的状态根作为自己新状态根。