zkStark-FRI 算法拆解

Dora Dōjo
1

一、zkStark 算法整体结构

1、zk-stark vs zk-snark

如下图所示，我们将名称 zk-stark 和 zk-snark 根据功能特点分别分成四个部分，然后逐个比较分析。

image
image1920×1216 87.9 KB

1.1 Zk-stark => zk - s t ark

  • zk：零知识，表明隐私的输入将会被隐藏，除了证明者，其他任何人不会看见；
  • s：可扩展的，和Replay Computation的验证耗时相比，zk-stark的证明和验证耗时分别与之呈拟线性关系和对数关系；
  • t：透明的，STARK 不需要可信第三方 Setup，因此是抗量子计算的
  • ark：知识论证，只有知道private input的prover，才能生成有效的proof；

1.2 Zk-snark => zk - s n ark

  • zk：零知识，表明隐私的输入将会被隐藏，除了证明者，其他任何人不会看见；
  • s：简洁的，指的是生成的proof足够小和验证时间足够短；
  • n：非交互式的，Prover生成证明的过程中和verifier没有交互；
  • ark：知识论证，只有知道private input的prover，才能生成有效的proof；

1.3 Compare

相同点：

  1. 都实现了将隐私的输入可靠隐藏；
  2. 都是基于知识论证，不知道private input的prover生成不了有效的proof；
  3. SNARK 比 STARK 唯一多出的限制就是非交互性。尽管如此，STARK 一般都可以转化为非交互证明，转化的结果必然是一个 SNARK。在这种意义上，可以把 STARK 看做 SNARK 的子集。

不同点：

  1. zk-stark具有可扩展性，即证明和验证的耗时与原始计算的耗时分别呈拟线性关系（且线性因子为常量）和对数关系，这意味这，如果原始输入的数据集增大1000000倍，zk-stark的证明耗时增加线性倍数的时间，但验证时间仅仅增加21*log1000000 =~ 420倍。证明耗时呈线性关系基本满足所有的ZKP算法，但是验证时间呈对数关系，仅此一家，因此在扩展性上，zk-stark要胜一筹。
  2. zk-stark同样具有简洁性，但是是验证简洁性。所谓简洁性，通常是指即使验证程序很大，生成的proof size也不会很大，同时又能很快的完成验证（比native computation快很多）。相比对zk-snark，zk-stark的proof size要大的多，因此在简洁性上，zk-snark要胜一筹。

2、Zk-stark 证明系统

Zk-stark 算法大体可以分为两个部分：Arithmetization 和 Low Degree Testing。

  • Arithmetization 目的是将程序的执行过程转化为多项式形式，以便进行证明。通常是通过构建程序的代数中间表达(AIR)，用 s 个多项式描述当前执行状态与下一步状态的关系，并将 AIR 转换为多项式形式，得到多项式 P(x) 。
  • 低度测试（Low-Degree-Testing）是一种用于检测多项式是否为低度多项式的方法。所谓低度多项式，是指多项式的次数小于某个指定的上限。低度测试可以通过对函数进行少量的查询来判断函数是否为低度多项式。在 zk-STARK 中，FRI 协议是一种用于低度测试的协议，它可以检测多项式是否接近于另一个多项式，并证明多项式的次数小于一个固定的界限。低度测试在概率证明理论中是一个核心问题，也是STARK协议的关键之一。

总的来说，zk-STARK的证明思路是对多项式进行承诺，使用低度多项式测试来证明多项式的次数小于特定的次数，最终利用 FRI 证明多项式的次数小于一个固定界限。

  1. 对一个多项式进行承诺，即使用多项式承诺方案将其进行承诺。
  2. 从算术化的约束系统中，得到两种类型的witness，第一是整个待证明程序的执行轨迹，也叫做execution trace，第二是在执行过程中需要满足的约束条件，称为constraint。
  3. 使用低度多项式测试来证明一个多项式的次数小于特定的次数。
  4. 利用 FRI 证明了某一个多项式的次数是小于一个固定界限的，也就是所谓低度测试(Low-Degree-Testing)，而这个多项式表示了待证问题的计算过程。

2.1 证明生成过程：

  1. 构建程序 C 的代数中间表达(Algebraic Intermediate Representation, AIR)，用 s 个多项式描述当前执行状态与下一步状态的关系。
  2. 将 AIR 转换为多项式形式，得到多项式 P(x) 。
  3. 对多项式 P(x) 进行低度测试，判断其是否为低度多项式。
  4. 如果 P(x) 不是低度多项式，则将其分解为多个低度多项式的乘积。
  5. 对每个低度多项式进行证明，得到证明的集合。
  6. 将所有证明组合成一个完整的证明。

2.2 证明验证过程：

  1. 将证明分解为多个低度多项式的证明。
  2. 对每个低度多项式的证明进行验证。
  3. 将所有低度多项式的验证结果组合成一个完整的验证结果。
  4. 如果所有低度多项式的验证结果都为真，则认为整个证明是有效的。

二、FRI 协议

FRI（Fast Reed-Solomen Interactive Oracle Proofs of Proximity）算法的证明思路是将一个高次多项式转化为一个低次多项式，并且保证转化后的多项式与原多项式在特定点上的取值相同。具体来说，FRI 算法将多项式分解成多个级别，每个级别都是原多项式的一个低次近似。通过逐级逼近，可以将原多项式转化为一个低次多项式。

Commit阶段：

  • 在 Commit 阶段，证明者需要将多项式分解成多个级别，并将每个级别的多项式进行承诺。
  • 证明者需要提供每个级别的多项式在特定点上的取值，并将这些取值进行哈希。同时，需要验证每个级别的多项式在特定点上的取值是否满足特定的条件，以保证多项式的正确性和安全性。

Query阶段：

  • 在 Query 阶段，验证者需要向证明者发送一些查询，以验证多项式在特定点上的取值是否满足特定的条件。
  • 证明者需要回答验证者的查询，并提供多项式在特定点上的取值。
  • 验证者需要验证证明者提供的多项式在特定点上的取值是否满足特定的条件，以保证多项式的正确性和安全性。

概括来说，本质上，STARK 最终是利用 FRI 证明了某一个多项式的次数是小于一个固定界限的，也就是所谓低度测试 LDT ，而这个多项式表示了待证问题的计算过程。FRI 算法的优点是可以在多项式次数较高的情况下，仍然能够高效地进行证明，同时也可以避免使用复杂的数学工具。LDT 过程中，曾经选用「直接证明」方案进行，但由于算法效率过于低下逐渐被淘汰。

在有限域 F 上，存在一个乘法群 L0 ，群的阶为 2n ；

• 这时，证明者声称码字 f0 : L0 → F 是满足 RS[F,L0,ρ] 编码参数的一个码字，即 f0 的大部分点在一个阶为 d<ρ∗2n 的多项式上 P(x) 上，这里 ρ=2(−R) ；

因此, 当 f0=P 时, 存在阶满足 deg(P1、P2)<1/2∗ρ∗2n 关系的多项式 P1、P2 满足以下等式：

f0(x)=P(x)=P1(x2)+x∗P2(x2) – (1)

令 Q(x,y)=P1(y)+x∗P2(y) ，可以看出二元多项式 Q(x,y) 关于变量 x 的阶 d<2 ；关于变量 y 的阶 d<1/2∗ρ∗2n 且当 y=x2 ，有 Q(x,y)=f0(x) ；此时，验证者 V 随机选取一个值 x0 发送给证明者 P ，证明者 P 计算 Q(x0,y) 且令:

f1(y)=Q(x0,y)=P1(y)+x0∗P2(y) – (2)

对于多项式 f1(y) ，由于 y=x2 ，且 x 取值范围是群 L0 ，因此有等式 x(2n)=1 ，进一步转换为 (x2)n=1 ，因此，如果定义自变量 y 的取值范围为群 L1 ，则 L1 应具备以下属性：

• 群的阶为 2(n−1) ;

• 群 L1 的每个元素对应群 L0 的两个元素；即对于群 L1 的任意元素 y ，群 L0 都有两个元素 x 和 (−x)mod p ，满足 x2mod p=y && (−x)2mod p=y ；

至此，问题就转化为了证明者 P 证明多项式 f1(y) 的阶 满足 d<1/2∗ρ∗2n 问题；同时也要保证函数 f1 和 f0 的一致性，具体步骤如下：

a. 验证者 V 分别从群 L1 和群 L0 选取三个点 y,s0,s1 满足 s0!=s1 && s02=s12=y

b. 证明者 P 返回 f0(s0),f0(s1),f1(y) 三个值

c. 验证者 V 根据 f0(s0),f0(s1) 插值出一个阶 d<2 的多项式 g(x)

d. 验证者 V 验证 g(s0)=f1(y) ，不相等，则失败

e. //2022-01-11 修改错误描述 g(x0)=f1(y)

可靠性分析：如果函数 f1 不是由函数 f0 按照上述过程转换而来，那么公式 (1) 的多项式和 P1(x2) 和 P2(x2) 和公式 (2) 的多项式和 P1(y) 和 P2(y) 之间大概率互不相等。考虑到多项式的阶满足 d<1/2∗ρ∗2n ，变量的取值范围为 2(n−1) ,根据 Schwartz-Zippel 定理, 在这个范围内随机选取一个值,多项式相等的概率为 (1/2∗ρ∗2n) / 2(n−1)=ρ 。ρ 为编码 coderates，如果 ρ=2−8 ，那么一次校验成功的概率仅仅为 2−8 。如果经过 k 次验证，那么作恶成功的概率就等于 2−8k ，随着 k 的增大，概率无限接近 0。

三、zkStark技术发展趋势

zkStark技术的发展趋势是多方面的，包括技术创新、模块化区块链、公链集成、应用场景和未来趋势。这些趋势将为zkStark技术的应用提供更多可能性，并推动其在各个领域的发展。

  • 技术创新：隐私计算技术在2022年进一步发展，开发出了更加高效、安全的隐私保护技术，例如混合加密技术、私钥加密。
  • 模块化区块链：以太坊的发展趋势正越来越倾向于模块化区块链，这种架构下，以太坊上的交易计算和执行不再由主网来操作，这将为zkStark等零知识证明技术的应用提供更多可能性。
  • 公链集成：公链集成也是零知识证明技术发展的一项重要趋势，这主要是因为零知识证明技术的开发难度较大，公链集成可以降低开发难度。
  • 应用场景：零知识证明技术的应用场景正在不断扩展，例如金融、医疗、物联网等领域。
  • 未来趋势：零知识证明技术将成为区块链技术领域的分水岭，它将为区块链技术的发展带来重大变革。