FRI的Commit、Query以及FRI Batching内部机制

1. 引言

前序博客见：

FRI用途：

FRI工作原理：

Reed-Solomon Codes及其与RISC Zero zkVM的关系博客中指出：RISC Zero中的Reed-Solomon Codes处理流程为：

1）Step 1 生成trace columns：在RISC Zero zkVM中执行某二进制文件，并记录其execution trace。
2）Step 2 将trace columns转换为trace blocks：采用Reed-Solomon Encoding对execution trace中的每列进行编码。
3）Step 3 对trace blocks之上的constraints进行evaluate，然后计算quotients：对trace blocks做STARK数学运算。
4）Step 4 应用FRI Protocol：让Verifier信服该结果是a valid Reed-Solomon codeword。

本文重点关注Step 4中的FRI协议。

本文内容框架为：

对vector [Z, K, S, U, M, M, I, T]的承诺，可以Merkle tree表示为：
在这里插入图片描述
其中：

也可从多项式承诺的角度来看：
在这里插入图片描述
其中：

该Merkle tree可叶子节点可看成是 $f$ 的evaluations值，其中 $f$ 为某多项式，满足 $f(g^0)=Z,f(g^1)=K, f(g^2)=S,f(g^3)=U,f(g^4)=M,f(g^5)=M,f(g^6)=I,f(g^7)=T$ 。

如何让持怀疑态度的Verifier信服以上承诺在的正确性呢？有2种方案：

1）直观方案：
- 1.1）Prover将所有数据直接都发送给Verifier：Prover所需发送给Verifier数据量太大了。
- 1.2）Verifier接收到所有数据后，自己插值来验证：对Verifier来说，插值运算太昂贵了。
2）高效方案为：使用FRI协议。

FRI基本结构示意为：
在这里插入图片描述
FRI基本流程为：

1）首先：Prover发送 $f_0$ 的Merkle root。
2）Commit Round 1：
- Verifier发送随机值 $r_1$
- Prover split $f_0$ ，然后使用 $r_1$ mix 获得 $f_1$
- Prover发送 $f_1$ 的Merkle root。
3）Commi Round 2：
- Verifier发送随机值 $r_2$
- Prover split $f_1$ ，然后使用 $r_2$ mix 获得 $f_2$
- Prover发送 $f_2$ 的Merkle root。

其中：

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
除最后一轮为plaintext commitment之外，之前所有轮均为Merkle tree commitments。

假设28为所选域的32-th root of unity，则有：
在这里插入图片描述

FRI机制中的queries用作随机挑战值。

blow-up factor为4，则意味着query有约3/4的概率可抓到作弊的Prover。

粗略来看：

在这里插入图片描述

当需对多个多项式应用FRI协议时，可使用FRI Batching。
在这里插入图片描述
FRI Batching时，使用上面的mix操作，来将多个多项式压缩为单个多项式。
当前FRI Batching主要有2种方式：

1）Affine batching： $g_{batched}=g_0+r_1\cdot g_1+\cdots +r_n\cdot g_n$ 。即选择多个不同的随机值来压缩。【StarkWare的ethSTARK采用的是Affine batching方式。】
2）Parametric batching： $g_{batched}=g_0+r^1\cdot g_1+\cdots +r^n\cdot g_n$ 。即选择单个随机值，但使用该随机值的不同powers来压缩。【RISC Zero和Polygon Hermez均采用的是Parametric batching方式。】