FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) 协议用于证明多项式是低度的。
Commit
计算 domain
domain = [g^i for i in range(len(trace))]对 trace 应用 IFFT 得到 trace 多项式，然后在扩展后的陪集域上使用 FFT 对该多项式求值，得到扩展后的 trace
let trace_poly = domain.ifft(trace); let extended_domain = domain.get_coset(shift).extend(blowup); let extended_trace = extended_domain.fft(&trace_poly);使用 Merkle Tree 承诺扩展后的 trace
MerkleTreeMmcs::commit(extended_trace)
Open & Verify
证明函数 $f: H \rightarrow F$ 的次数不超过 $d$，其中 $d \ll |H| $
协议分为两阶段：提交和查询
- 在提交阶段，证明者在每一轮对折叠后的函数（会用到验证者提供的随机值）进行采用 Merkle 承诺
- 在查询阶段，证明者在验证者随机选择的点处提供一组对先前承诺的函数的求值
Commit Phase
用 $p_0$ 表示低次函数。在提交阶段，多项式 $p_0$ 被拆分为两个次数低于 $d/2$ 的多项式 $g_{0,1}, g_{0,2}$ ，使得：
$$ p_0(x) = g_{0,1}(x^2) + xg_{0,2}(x^2) $$
然后验证者发送 一个随机数 $v_0$，并要求证明者承诺多项式 $p_1(x)=g_{0,1}(x) + v_0g_{0,2}(x)$。注意，$p_1$ 的承诺不是在 $H$ 上，而是在 $H^2=\left\{x^2: x \in H\right\}$ 上。
然后，证明者继续将 $p_1$ 拆分为低于 $d/4$ 度的 $g_{1,1}$ 和 $g_{1,2}$，使用验证者发送的随机数 $v_1$ 构建 $p_2$，并对其承诺。
上述交互迭代了 $k=\text{log}d$ 次。最后，$deg(p_k)=0$ ，证明者向验证者发送一个常数 $p_k$，表示一个次数小于 1 的多项式。
点值形式的多项式折叠
给定多项式 $p(x)$ 可唯一分解为偶部和奇部：
$$ p(x) = p_e(x^2) + x \cdot p_o(x^2) $$
结合
$$ p(-x) = p_e(x^2) -x \cdot p_o(x^2) $$
可以得到
$$ \begin{align} &p_e(x^2) = \frac{p(x) + p(-x)} { 2} \\ &p_o(x^2) = \frac{p(x) - p(-x)} {2 x} \end{align} $$
在单位根 $g^i$（$g$ 为 n-次本原单位根）上，有
$$ \begin{align} &p_e(g^{2i})) = \frac{p(g^i) + p(g^{-i})}{2} \\ &p_o(g^{2i)}) = \frac{p(g^i) - p(g^{-i})}{2 g^i} \end{align} $$
因为 $g^{n/2}=-1$（单位根性质），所以有 $g^{n/2+i}=-g^i$，所以有
$$ \begin{align} &p_e(g^{2i}) = \frac{p(g^i) + p(g^{n/2 + i})}{2} \\ &p_o(g^{2i}) = \frac{p(g^i) - p(g^{n/2 + i})}{2 g^i} \end{align} $$
合并结果
$$ p_{new}(g^{2i}) = p_e(g^{2i}) + v \cdot p_o(g^{2i}) $$
其中 $v$ 是验证者提供的随机挑战值。
最终得到折叠后的式子
$$ p_{new}(g^{2i}) = (\frac{1}{2} + \frac{v}{2} g^{-i}) p(g^i) + (\frac{1}{2} - \frac{v}{2} g^{-i}) p(g^{n/2+i}) $$
Query Phase
在查询阶段，验证者向证明者发送一个随机数 $r \in H$ ，并查询评估值 $p_0(r)$, $p_0(-r)$ 和 $p_1(r^2)$ 。验证者根据 $p_0(r)$, $p_0(-r)$ 计算 $p_1(r^2)$，并检查其与证明者发送的 $p_1(r^2)$ 是否匹配。$p_1(r^2)$ 计算过程如下：
$$ \begin{align} &p_0(r) = g_{0,1}(r^2) + r \cdot g_{0,2}(r^2)\\ &p_0(-r) = g_{0,1}(r^2) - r \cdot g_{0,2}(r^2)\\ &p_1(r^2) = g_{0,1}(r^2) + v_0 \cdot g_{0,2}(r^2) \end{align} $$
先根据前两个式子算出 $g_{0,1}(r^2), g_{0,2}(r^2)$，然后根据第三个式子算出 $p_1(r^2)$
在下一次交互中，验证者查询 $p_1(-r^2)$ 和 $p_2(r^4)$ ，并像之前一样检查 $p_1,p_2$ 之间的一致性。该交互重复至常数 $p_k$ 。验证者检查证明者发送的值是否确实等于根据之前查询 $p_{k-1}$ 计算出的值。为了确保正确性，证明者必须在发送的评估结果中附带其存在证明（Merkle 树路径）。完成此过程后，验证者将确认在提交阶段 $p_0,p_1,...,p_k$ 提交的多项式彼此一致。
为了确保协议的健壮性，查询阶段会重复多次。
没有评论