本文主要是介绍FRI及相关SNARKs的Fiat-Shamir安全,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
1. 引言
本文主要参考:
- Alexander R. Block 2023年论文 Fiat-Shamir Security of FRI and Related SNARKs
- Albert Garreta 2023年9月在ZK Summit 10上分享 ZK10: Fiat-Shamir security of FRI and related SNARKs - Albert Garreta (Nethermind)
评估参数用的Sagemath code见:
- https://github.com/alexander-r-block/FRI-Parameter-Testing-Sagemath
2. 何为FRI-based SNARK?
何为FRI-based SNARK?
非正式来说,其为遵循如下配方的SNARK:
- 1)PIOP:Polynomial Interactive Oracle proof。
- 2)FRI + Merkle trees:将PIOP用FRI和Merkle trees进行compile。
- 3)Fiat-Shamir transform
2.1 何为PIOP?
PIOP=Polynomial Interactive Oracle proof。
PIOP是一种交互协议,有Prover和Verifier两种角色,有problem statement x x x,和仅对Prover已知的witness w w w。Prover和Verifier以一定轮数相互交换消息。
PIOP的独特性在于:
- Prover发送的消息 m i ( X ) m_i(X) mi(X)为“low degree” polynomials。
- 在交互阶段结束时,Verifier会在random points来open这些 m i ( X ) m_i(X) mi(X)多项式,并基于这些openings是否满足某些代数关系,来决定是accept还是reject。
当在对PIOP做安全性分析时,一个关键假设是:
- 假设攻击者(恶意Prover)发送的所有maps都是多项式。【这实际是一个很强的假设,从而让PIOP安全性分析相对简单。】
这样,对PIOP的安全性分析,通常会归结为争论:
- 除非Verifier(非常不幸)恰巧发送了某特定low-degree polynomial的root,否则攻击者无法破坏该PIOP协议。
而根据Schwartz-Zippel lemma有:“degree d d d多项式具有 ≤ d \leq d ≤d个roots”。
因此,攻击者破解该PIOP协议的概率 ≤ d / 2 λ \leq d/2^{\lambda} ≤d/2λ。
PIOP是一种对ZKP进行分析的很好的抽象框架,但实际上,PIOP存在如下问题:
- 1)Verifier如何检查Prover发送的是low degree多项式?
- 方法之一是:Verifier检查这些多项式的所有evaluations,来确认其是否与某多项式一致,但这会让Verifier非常慢。
- 2)maps m i ( X ) m_i(X) mi(X)太大,难以发送。这会让proof size巨大,可能会与Prover直接发送witness size相当。
因此,针对以上PIOP问题的解决方案为:
- Polynomial Commitment Scheme(PCS)多项式承诺方案:即使用某多项式承诺方案对该PIOP进行编译。此时:
- PIOP中Prover发送的消息为 m i ( X ) m_i(X) mi(X)多项式的承诺值 C m ( m i ( X ) ) Cm(m_i(X)) Cm(mi(X)),而不再是 m i ( X ) m_i(X) mi(X)多项式本身。
- 在交互协议阶段结束时,为获得在随机点的openings m i ( a ) m_i(a) mi(a),由于此时Verifier只有 m i ( X ) m_i(X) mi(X)的承诺值,其无法自己open,因此Verifier会根据特定的PCS规则 与Prover交互,以获得openings m i ( a ) m_i(a) mi(a)。
目前的PCS多项式承诺方案有:
- KZG多项式承诺方案
- IPA-based多项式承诺方案
- (FRI + Merkle tree)-based多项式承诺方案:本文重点关注本方案。因很多从业人员常使用(FRI + Merkle tree)-based多项式承诺方案,但实际上其需要在非常严格地配置下,才能将FRI用作PCS多项式承诺方案。而这种严格配置,会让(FRI + Merkle tree)-based PCS很慢。
因此实际应用时,会将FRI配置为非PCS,后续将详谈这个关键点。
在Marlin和Dark等论文中,有如下定理:
- 若PIOP和PCS是安全的,则新协议是安全的。
2.2 Fiat-Shamir transform
Fiat-Shamir transformation可:
- 移除交互性
- 对public coin协议,所有Verifier消息都是随机的
- 简单思路为:将Verifier的challenges替换为hashes。
- 将哈希函数 模型化为 a Random Oracle。
借助Fiat-Shamir转换为非交互式协议之后:
- Verifier会基于 ( x , m 1 , c 1 , ⋯ , m μ ) (x,m_1,c_1,\cdots,m_{\mu}) (x,m1,c1,⋯,mμ)的有效性来决定是accept还是reject。
- Verifier会检查 c i c_i ci是否“well hashed”。
当前FRI-based SNARKs有:
- STARK
- Plonky2
- RISC Zero
- Boojum
3. Fiat-Shamir issues
3.1 Fiat-Shamir转换的安全性
令:
- Π \Pi Π为某交互式协议
- F S ( Π ) FS(\Pi) FS(Π)为其Fiat-Shamir转换
则,有可能 Π \Pi Π是安全的,但 F S ( Π ) FS(\Pi) FS(Π)是不安全的。
如:
- 示例一: Π \Pi Π为sequential repetition of a “small” protocol。如某small protocol的sound error为 1 / 2 1/2 1/2,交互式重复该协议2次,则sound error变为 ( 1 / 2 ) 2 = 1 / 4 (1/2)^2=1/4 (1/2)2=1/4。
当但对该small协议做FS转换获得新协议时,则可能是灾难——其security仍为 1 / 2 1/2 1/2。 - 示例二: Π \Pi Π为parallel repetition of a “smaller” protocol Π 0 \Pi_0 Π0(Attema, Fehr, Kloss, 2022)。【本文重点关注这种并行重复执行协议示例】
假设 Π 0 \Pi_0 Π0 small协议的安全性为 ϵ \epsilon ϵ,为增加其安全性,并行对其进行重复执行——以2倍并行为例,Prover在每轮会发送2个消息,Verifier在每轮会应答2个challenges。这就相当于以2个线程来并行运行 Π 0 \Pi_0 Π0。 Π \Pi Π的Verifier会accept,当且仅当, Π 0 \Pi_0 Π0的Verifier会同时accept ( x , m 1 , c 1 , m 2 , c 2 , m 3 ) (x,m_1,c_1,m_2,c_2,m_3) (x,m1,c1,m2,c2,m3)和 ( x , m 1 ′ , c 1 ′ , m 2 ′ , c 2 ′ , m 3 ′ ) (x,m_1',c_1',m_2',c_2',m_3') (x,m1′,c1′,m2′,c2′,m3′)。这样 Π \Pi Π的安全性将是 Π 0 \Pi_0 Π0的二次方,即 ϵ 2 \epsilon^2 ϵ2。
parallel repetition场景下的FS攻击,攻击者攻击流程为:
- 1)Prover选择 ( m 1 , m 1 ′ ) (m_1,m_1') (m1,m1′)
- 2)计算 ( c 1 , c 1 ′ ) = H a s h ( x , m 1 , m 1 ′ ) (c_1,c_1')=Hash(x,m_1,m_1') (c1,c1′)=Hash(x,m1,m1′)
- 3)检查 c 1 c_1 c1是否为某“special” challenge,其使得 Π 0 \Pi_0 Π0的第一个proof ( x , m 1 , c 1 , m 2 , c 2 , m 3 ) (x,m_1,c_1,m_2,c_2,m_3) (x,m1,c1,m2,c2,m3)是有效的。如, c 1 c_1 c1可为特定多项式的root。【因此,实际需确保Verifier发送的challenge不是多项式的root,否则将破坏协议。】
- 4)若 c 1 c_1 c1不是特殊的challenge,则Prover rewinds,然后重复执行上面的步骤1)。
【原则上,Prover需要 ≈ 1 / ϵ = 2 λ \approx1/\epsilon=2^{\lambda} ≈1/ϵ=2λ次迭代即可成功。其中 λ \lambda λ为交互式协议的安全参数。】
然后,假设Prover最终找到了该特殊的challenge c 1 c_1 c1,并继续如下流程: - 1)令 m 2 m_2 m2为某消息,使得Prover可获得第一个有效proof ( x , m 1 , c 1 , m 2 , c 2 , m 3 ) (x,m_1,c_1,m_2,c_2,m_3) (x,m1,c1,m2,c2,m3)。
- 2)然后在另一线程中,重复之前的流程:
- 2.1)选择任意 m 2 ′ m_2' m2′
- 2.2)计算 ( c 2 , c 2 ′ ) = H a s h ( x , m 1 , m 1 ′ , c 1 , c 1 ′ , m 2 , m 2 ′ ) (c_2,c_2')=Hash(x,m_1,m_1',c_1,c_1',m_2,m_2') (c2,c2′)=Hash(x,m1,m1′,c1,c1′,m2,m2′)。
- 2.3)检查 c 2 ′ c_2' c2′是否为某“special” challenge,其使得 Π 0 \Pi_0 Π0的第二个proof ( x , m 1 ′ , c 1 ′ , m 2 ′ , c 2 ′ , m 3 ′ ) (x,m_1',c_1',m_2',c_2',m_3') (x,m1′,c1′,m2′,c2′,m3′)是有效的。如, c 2 ′ c_2' c2′可为特定多项式的root。【因此,实际需确保Verifier发送的challenge不是多项式的root,否则将破坏协议。】
- 2.4)若 c 2 ′ c_2' c2′不是特殊的challenge,则Prover rewinds,然后重复执行上面的步骤2.1)。
【原则上,Prover需要 ≈ 1 / ϵ = 2 λ \approx1/\epsilon=2^{\lambda} ≈1/ϵ=2λ次迭代即可成功。其中 λ \lambda λ为交互式协议的安全参数。】
结论为:
- 假设Prover为Round 1找到了特殊的 c 1 c_1 c1,为Round 2找到了特殊的 c 2 c_2 c2。
- 则 ( x , m 1 , c 1 , m 2 , c 2 , m 3 ) (x,m_1,c_1,m_2,c_2,m_3) (x,m1,c1,m2,c2,m3)和 ( x , m 1 ′ , c 1 ′ , m 2 ′ , c 2 ′ , m 3 ′ ) (x,m_1',c_1',m_2',c_2',m_3') (x,m1′,c1′,m2′,c2′,m3′)均为有效proofs。
- 找到该特殊 c i c_i ci需要约 ≈ 1 / ϵ = 2 λ \approx 1/\epsilon=2^{\lambda} ≈1/ϵ=2λ次迭代尝试。
- 总共,Prover需要 1 / ϵ + 1 / ϵ = 2 / ϵ 1/\epsilon +1/\epsilon=2/\epsilon 1/ϵ+1/ϵ=2/ϵ次迭代尝试。
- 这样,安全性仅增加了1个bit,尽管期待的是增加2倍,原因在于parallel repetition的交互版本具有的soundness为 1 / ϵ 2 1/\epsilon^2 1/ϵ2。
- 总的来说,第2个parallel repetition对soundness没有任何贡献。
相关经验法则为: - 令 Π 0 \Pi_0 Π0为 soundness error为 ϵ \epsilon ϵ的 μ \mu μ-round协议
- Π 0 ′ \Pi_0' Π0′为并行重复 Π 0 \Pi_0 Π0 t t t 次。
- 则 F S ( Π 0 ′ ) FS(\Pi_0') FS(Π0′)具有的soundness error 为 ≈ ϵ ⌈ t / μ ⌉ \approx \epsilon ^{\left \lceil t/\mu \right \rceil} ≈ϵ⌈t/μ⌉。
- 因此,所添加的 Π 0 \Pi_0 Π0并行实例个数,应为 μ \mu μ的倍数,才能实现在FS转换前类似的soundness。
3.2 何时FS转换是安全的?
以上面的结论和经验法则可知,存在如下情况:
- Π 0 ′ \Pi_0' Π0′具有soundness ϵ ′ \epsilon' ϵ′,但 F S ( Π 0 ′ ) FS(\Pi_0') FS(Π0′)具有低得多的soundness。
那么,问题来了,何时FS转换能保持相同量级的soundness?即何时FS转换后的协议与初始的交互协议具有相同的安全级别?
有2种概念:
- 1)Special soundness(Atttema, Fehr, Kloss, 2022):即证明初始交互协议满足某种特殊的soundness强概念。若初始交互协议是special sound的,则FS转换后的协议与该初始协议一样安全。
- 2)Round-by-Round (RBR) knowledge soundness(Chiesa, Manohar, Spooner, 2020):即若证明初始交互协议具有Round-by-Round (RBR) knowledge soundness,则FS转换后的协议与该初始协议一样安全。
所谓Round-by-Round (RBR) knowledge soundness:
- 在之前的2个例子(Sequential repetition和Parallel repetition)中,可称其为 “the overall soundness ϵ \epsilon ϵ of Π \Pi Π is the accumulation of smaller soundness errors throughout Π \Pi Π’s rounds”。
- 但这正是之前FS攻击所利用之处:攻击者其可rewind proofs,并试图破坏该small soundness checks,这些checks具有small soundness,然后Fiat-Shamir transform将不再按预期工作。
- 当满足如下情况时,则称该协议是RBR (knowledge) sound的:【协议的安全性,不是多个不太安全checks的累加】
- 即,当“each round of Π \Pi Π has soundness error ≈ \approx ≈ the overall error ϵ \epsilon ϵ of Π \Pi Π”时。
在Theorem (Block, G., Tiwari, Zajac) 中指出:
- RBR knowledge soundness => special soundness => RBR soundness。
4. FRI及其FS安全性
FRI协议:
- FRI是a IOP。
- FRI Prover具有某函数 f : F → F f:\mathbb{F}\rightarrow \mathbb{F} f:F→F。
- FRI Verifier可访问所有的 f ( v ) f(v) f(v),其中 v ∈ D v\in D v∈D, D ⊆ F D\subseteq \mathbb{F} D⊆F。
- 理想情况下,FRI协议的目的是:让Verifier信服 f ( X ) f(X) f(X)为某degree ≤ d \leq d ≤d的多项式。
- 实际情况下,FRI协议的目的是:让Verifier信服 f ( X ) f(X) f(X) 为 δ \delta δ-close 某degree ≤ d \leq d ≤d的多项式。
- 所谓 δ \delta δ-close,是指:在 D D D的相对大的子集 D 0 D_0 D0内, f ( X ) f(X) f(X)与某low degree多项式 agree,即 ∣ D 0 ∣ ≥ ( 1 − δ ) ∣ D ∣ |D_0|\geq (1-\delta)|D| ∣D0∣≥(1−δ)∣D∣,且 0 < δ < 1 0<\delta <1 0<δ<1。
Theorem (Block, G., Katz, Thaler, Tiwari, Zajac; StarkWare) 中指出:
- FRI协议是RBR (knowledge) sound的。【根据之前的RBR knowledge soundness => special soundness => RBR soundness,可知FRI协议也是special sound的。】
因此,FRI协议FS转换之后,其soundness ≈ Q ε F R I + Q 2 2 \approx \mathcal{Q}_{\varepsilon_{FRI}}+\frac{\mathcal{Q}^2}{2} ≈QεFRI+2Q2。即,可安全的对FRI进行Fiat-Shamir转换。
5. 使用FRI来编译PIOPs
5.1 FRI-based PCS in practice
当 “ δ \delta δ-close” 是 “very close”时,FRI可用于构建多项式承诺:
- 为验证 f ( z ) = y f(z)=y f(z)=y,需使用FRI来检查:“ q ( X ) : = f ( X ) − y X − z q(X):=\frac{f(X)-y}{X-z} q(X):=X−zf(X)−y” 为 “ δ \delta δ-close” to 某degree ≤ d − 1 \leq d-1 ≤d−1 多项式。
- 此处“very close”,是指:在 某unique decoding radius δ ≤ ( 1 − ( d + 1 ) / ∣ D ∣ ) / 2 \delta\leq (1-(d+1)/|D|)/2 δ≤(1−(d+1)/∣D∣)/2范围内。
- 但是,取如此小的 δ \delta δ值,在效率上是有开销的。会导致不具备实用性的不高效的FRI协议。也就是说,实际应用时,并不会取如此低的proximity参数。
- 实际上,当前所有的协议(如STARK、Plonky2、RISC Zero等),会取更大的proximity参数 δ \delta δ值,其最大为Johnson bound: 1 − ( d + 1 ) / ∣ D ∣ 1-\sqrt{(d+1)/|D|} 1−(d+1)/∣D∣。
- 这样的实际取值,导致以上"PCS"将不再是一个多项式承诺方案。原因在于:
- 可能有多个多项式,其均满足 δ \delta δ-close to the map q ( X ) q(X) q(X)。
- Prover可open这多个close多项式中的任意一个。【此时,Prover不再是对某多项式进行commit,而是对一组多项式进行commit。这是个问题。】
- 将FRI用作PCS beyond unique decoding radius的相关项目有:
- RedShift:Plonk + FRI —— 其soundness error随execution trace width指数级扩大。
- STARK-type协议:DEEP-FRI、ethSTARK等 + Hab¨ock。【其使用FRI来编译PIOPs,当不将FRI看成是多项式承诺方案。】【Polygon Labs Ulrich Hab¨ock 2022年论文《A summary on the FRI low degree test》中,对所评估的soundness进行了一点改进。】
为此,主要结论为:
- Theorem (Block, G., Katz, Thaler, Tiwari, Zajac) 中指出:有某large class C \mathscr{C} C of PIOPs,使得:
- 假设该初始PIOP是RBR (knowledge) sound的。
- 则所生成的FRI-based SNARG是knowledge sound的,即为a SNARK。
因此,关键点在于:
- 以上Theorem支持,仅通过看该PIOP,来证明该SNARK的安全性。这样通常相对更易于分析。
Alexander R. Block 2023年论文 Fiat-Shamir Security of FRI and Related SNARKs 中:
- 展示了ethSTARK和Plonky2作为PIOPs是RBR knowledge sound的,且在class C \mathscr{C} C中。
- 从而可推断出:ethSTARK和Plonky2作为SNARGs是knowledge sound的。
- 与此同时,StarkWare也展示了ethSTARK的相同结论。
- 称PIOPs in C \mathscr{C} C 0 0 0-correlated。
参考资料
[1] Alexander R. Block 2023年论文 Fiat-Shamir Security of FRI and Related SNARKs
[2] Albert Garreta 2023年9月在ZK Summit 10上分享 ZK10: Fiat-Shamir security of FRI and related SNARKs - Albert Garreta (Nethermind)
这篇关于FRI及相关SNARKs的Fiat-Shamir安全的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!