FRI及相关SNARKs的Fiat-Shamir安全-Toy模板网

这篇具有很好参考价值的文章主要介绍了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$ ，和仅对Prover已知的witness $w$ 。Prover和Verifier以一定轮数相互交换消息。
fiat-shamir security of fri and relate,基础理论,基础理论
PIOP的独特性在于：

Prover发送的消息 $m_i(X)$ 为“low degree” polynomials。
在交互阶段结束时，Verifier会在random points来open这些 $m_i(X)$ 多项式，并基于这些openings是否满足某些代数关系，来决定是accept还是reject。

当在对PIOP做安全性分析时，一个关键假设是：

假设攻击者（恶意Prover）发送的所有maps都是多项式。【这实际是一个很强的假设，从而让PIOP安全性分析相对简单。】

这样，对PIOP的安全性分析，通常会归结为争论：

除非Verifier（非常不幸）恰巧发送了某特定low-degree polynomial的root，否则攻击者无法破坏该PIOP协议。
而根据Schwartz-Zippel lemma有：“degree $d$ 多项式具有 $\leq d$ 个roots”。
因此，攻击者破解该PIOP协议的概率 $\leq d/2^{\lambda}$ 。

PIOP是一种对ZKP进行分析的很好的抽象框架，但实际上，PIOP存在如下问题：

1）Verifier如何检查Prover发送的是low degree多项式？
- 方法之一是：Verifier检查这些多项式的所有evaluations，来确认其是否与某多项式一致，但这会让Verifier非常慢。
2）maps $m_i(X)$ 太大，难以发送。这会让proof size巨大，可能会与Prover直接发送witness size相当。

因此，针对以上PIOP问题的解决方案为：

Polynomial Commitment Scheme（PCS）多项式承诺方案：即使用某多项式承诺方案对该PIOP进行编译。此时：
- PIOP中Prover发送的消息为 $m_i(X)$ 多项式的承诺值 $Cm(m_i(X))$ ，而不再是 $m_i(X)$ 多项式本身。
- 在交互协议阶段结束时，为获得在随机点的openings $m_i(a)$ ，由于此时Verifier只有 $m_i(X)$ 的承诺值，其无法自己open，因此Verifier会根据特定的PCS规则与Prover交互，以获得openings $m_i(a)$ 。

fiat-shamir security of fri and relate,基础理论,基础理论
目前的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,\cdots,m_{\mu})$ 的有效性来决定是accept还是reject。
Verifier会检查 $c_i$ 是否“well hashed”。

当前FRI-based SNARKs有：

STARK
Plonky2
RISC Zero
Boojum

fiat-shamir security of fri and relate,基础理论,基础理论

3. Fiat-Shamir issues

3.1 Fiat-Shamir转换的安全性

令：

$\Pi$ 为某交互式协议
$FS(\Pi)$ 为其Fiat-Shamir转换

则，有可能 $\Pi$ 是安全的，但 $FS(\Pi)$ 是不安全的。
如：

示例一： $\Pi$ 为sequential repetition of a “small” protocol。如某small protocol的sound error为 $1/2$ ，交互式重复该协议2次，则sound error变为 $1/2)^2=1/4$ 。
当但对该small协议做FS转换获得新协议时，则可能是灾难——其security仍为 $1/2$ 。
示例二： $\Pi$ 为parallel repetition of a “smaller” protocol $\Pi_0$ （Attema, Fehr, Kloss, 2022）。【本文重点关注这种并行重复执行协议示例】
假设 $\Pi_0$ small协议的安全性为 $\epsilon$ ，为增加其安全性，并行对其进行重复执行——以2倍并行为例，Prover在每轮会发送2个消息，Verifier在每轮会应答2个challenges。这就相当于以2个线程来并行运行 $\Pi_0$ 。 $\Pi$ 的Verifier会accept，当且仅当， $\Pi_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')$ 。这样 $\Pi$ 的安全性将是 $\Pi_0$ 的二次方，即 $\epsilon^2$ 。

parallel repetition场景下的FS攻击，攻击者攻击流程为：

1）Prover选择 $m_1,m_1')$
2）计算 $c_1,c_1')=Hash(x,m_1,m_1')$
3）检查 $c_1$ 是否为某“special” challenge，其使得 $\Pi_0$ 的第一个proof $x,m_1,c_1,m_2,c_2,m_3)$ 是有效的。如， $c_1$ 可为特定多项式的root。【因此，实际需确保Verifier发送的challenge不是多项式的root，否则将破坏协议。】
4）若 $c_1$ 不是特殊的challenge，则Prover rewinds，然后重复执行上面的步骤1）。
【原则上，Prover需要 $\approx1/\epsilon=2^{\lambda}$ 次迭代即可成功。其中 $\lambda$ 为交互式协议的安全参数。】

然后，假设Prover最终找到了该特殊的challenge $c_1$ ，并继续如下流程：
1）令 $m_2$ 为某消息，使得Prover可获得第一个有效proof $x,m_1,c_1,m_2,c_2,m_3)$ 。
2）然后在另一线程中，重复之前的流程：
- 2.1）选择任意 $m_2'$
- 2.2）计算 $c_2,c_2')=Hash(x,m_1,m_1',c_1,c_1',m_2,m_2')$ 。
- 2.3）检查 $c_2'$ 是否为某“special” challenge，其使得 $\Pi_0$ 的第二个proof $x,m_1',c_1',m_2',c_2',m_3')$ 是有效的。如， $c_2'$ 可为特定多项式的root。【因此，实际需确保Verifier发送的challenge不是多项式的root，否则将破坏协议。】
- 2.4）若 $c_2'$ 不是特殊的challenge，则Prover rewinds，然后重复执行上面的步骤2.1）。
  【原则上，Prover需要 $\approx1/\epsilon=2^{\lambda}$ 次迭代即可成功。其中 $\lambda$ 为交互式协议的安全参数。】

结论为：

假设Prover为Round 1找到了特殊的 $c_1$ ，为Round 2找到了特殊的 $c_2$ 。
则 $x,m_1,c_1,m_2,c_2,m_3)$ 和 $x,m_1',c_1',m_2',c_2',m_3')$ 均为有效proofs。
找到该特殊 $c_i$ 需要约 $\approx 1/\epsilon=2^{\lambda}$ 次迭代尝试。
总共，Prover需要 $1/\epsilon +1/\epsilon=2/\epsilon$ 次迭代尝试。
这样，安全性仅增加了1个bit，尽管期待的是增加2倍，原因在于parallel repetition的交互版本具有的soundness为 $1/\epsilon^2$ 。
总的来说，第2个parallel repetition对soundness没有任何贡献。

相关经验法则为：
令 $\Pi_0$ 为 soundness error为 $\epsilon$ 的 $\mu$ -round协议
$\Pi_0'$ 为并行重复 $\Pi_0$ $t$ 次。
则 $FS(\Pi_0')$ 具有的soundness error 为 $\approx \epsilon ^{\left \lceil t/\mu \right \rceil}$ 。
因此，所添加的 $\Pi_0$ 并行实例个数，应为 $\mu$ 的倍数，才能实现在FS转换前类似的soundness。

3.2 何时FS转换是安全的？

以上面的结论和经验法则可知，存在如下情况：

$\Pi_0'$ 具有soundness $\epsilon'$ ，但 $FS(\Pi_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:\mathbb{F}\rightarrow \mathbb{F}$ 。
FRI Verifier可访问所有的 $f (v)$ ，其中 $v\in D$ ， $D\subseteq \mathbb{F}$ 。
理想情况下，FRI协议的目的是：让Verifier信服 $f (X)$ 为某degree $\leq d$ 的多项式。
实际情况下，FRI协议的目的是：让Verifier信服 $f (X)$ 为 $\delta$ -close 某degree $\leq d$ 的多项式。
- 所谓 $\delta$ -close，是指：在 $D$ 的相对大的子集 $D_0$ 内， $f (X)$ 与某low degree多项式 agree，即 $|D_0|\geq (1-\delta)|D|$ ，且 $0<\delta <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 $\approx \mathcal{Q}_{\varepsilon_{FRI}}+\frac{\mathcal{Q}^2}{2}$ 。即，可安全的对FRI进行Fiat-Shamir转换。

5. 使用FRI来编译PIOPs

5.1 FRI-based PCS in practice

当 “ $\delta$ -close” 是 “very close”时，FRI可用于构建多项式承诺：

为验证 $f (z) = y$ ，需使用FRI来检查：“ $q(X):=\frac{f(X)-y}{X-z}$ ” 为 “ $\delta$ -close” to 某degree $\leq d-1$ 多项式。
此处“very close”，是指：在某unique decoding radius $\delta\leq (1-(d+1)/|D|)/2$ 范围内。
但是，取如此小的 $\delta$ 值，在效率上是有开销的。会导致不具备实用性的不高效的FRI协议。也就是说，实际应用时，并不会取如此低的proximity参数。
实际上，当前所有的协议（如STARK、Plonky2、RISC Zero等），会取更大的proximity参数 $\delta$ 值，其最大为Johnson bound： $1-\sqrt{(d+1)/|D|}$ 。
这样的实际取值，导致以上"PCS"将不再是一个多项式承诺方案。原因在于：
- 可能有多个多项式，其均满足 $\delta$ -close to the map $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 $\mathscr{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 $\mathscr{C}$ 中。
从而可推断出：ethSTARK和Plonky2作为SNARGs是knowledge sound的。
与此同时，StarkWare也展示了ethSTARK的相同结论。
称PIOPs in $\mathscr{C}$ $0$ -correlated。

fiat-shamir security of fri and relate,基础理论,基础理论

参考资料

[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模板网！