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。
文章来源：https://www.toymoban.com/news/detail-768532.html
参考资料
[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)文章来源地址https://www.toymoban.com/news/detail-768532.html
到了这里，关于FRI及相关SNARKs的Fiat-Shamir安全的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
