RISC Zero ZKP协议中的商多项式

1. 引言

前序博客见：

Reed-Solomon Codes及其与RISC Zero zkVM的关系

RISC Zero zkVM主要针对可验证计算，其具有隐私和可扩展属性：
在这里插入图片描述

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 3中的quotient商多项式：

商多项式用于哪？
- 用于整个ZKP协议中。
为何需要商多项式？
- 为强化多项式承诺的约束。（To enforce constraints on polynomial commitments.）

本文内容基本结构为：

回顾多项式承诺方案
回顾多项式代数运算：即用于强化约束（Enforcing Constraints）。
STARKs、KZG&DEEP上下文中的商多项式

2. 多项式承诺方案回顾

2.1 何为承诺方案？

所谓承诺方案，是指：

一种确保某人在应答后无法修改答案的方式。

所有的承诺方案：

都具有binding属性
不一定都具有hiding属性。某些承诺方案也还可能具有hiding属性。

承诺方案中包括：

commit函数：对data数据进行承诺。
reveal函数：公开该承诺值的片段信息。
check函数：检查所公开的片段信息是否与原始承诺值匹配。

RISC Zero的承诺方案是基于Merkle trees的：

commit函数：用于构建a Merkle tree。
reveal函数：用于show该Merkle tree的某叶子节点。
check函数：检查相应的Merkle branch。

2.2 何为多项式承诺方案？

当所承诺的data数据源自某多项式的evaluation时，则将相应的承诺方案，称为多项式承诺方案。

在基于Merkle的多项式承诺方案中，该Merkle tree中的每个叶子节点，都对应某“evaluation domain”内的一个点。

3. 回顾多项式代数运算：即用于强化约束（Enforcing Constraints）

3.1 多项式代数运算

多项式具有如下分解属性：

若 $f (x)$ 为某多项式，且有 $f (3) = 0$ ，则 $\frac{f(x)}{x-3}$ 也是一个多项式。
若 $f (x)$ 为某多项式，但有 $f(3)\neq 0$ ，则 $\frac{f(x)}{x-3}$ 为一个“rational function”。
若 $f (x)$ 为某多项式，且有 $f (3) = 5$ ，则 $\frac{f(x)-f(3)}{x-3}=\frac{f(x)-5}{x-3}$ 也是一个多项式。
若 $f (x)$ 为某多项式，但有 $f(3)\neq 5$ ，则 $\frac{f(x)-f(3)}{x-3}=\frac{f(x)-5}{x-3}$ 为一个“rational function”。

如：

$f(x)=x^3-5x-12=(x-3)(x^2+3x+4)$ 为多项式，且 $f (3) = 0$ ，则 $\frac{f(x)}{x-3}=(x^2+3x+4$ 也是多项式。
$f(x)=x^3-5x-7$ 为多项式， $f(x)-5=x^3-5x-12=(x-3)(x^2+3x+4)$ 为多项式：
- 且有 $f (3) = 5$ ，则 $\frac{f(x)-f(3)}{x-3}=\frac{f(x)-5}{x-3}$ 也是一个多项式。
- 但有 $f(3)\neq 5$ ，则 $\frac{f(x)-f(3)}{x-3}=\frac{f(x)-5}{x-3}$ 为一个“rational function”。

3.2 利用多项式代数运算来强化约束

已知某多项式 $f$ ，如何来强化如下约束呢？

$f (1) = 0$
$f (2) = 0$
$f (3) = 0$
$f (4) = 0$

答案就是：当且仅当 $\frac{f(x)}{(x-1)(x-2)(x-3)(x-4)}$ 为一个多项式时，以上约束成立。

同理，已知某多项式 $f$ ，如何来强化如下约束呢？（其中 $w$ 为root of unity，便于后续用FFT加速）

$f(w^0) = 0$
$f(w^1) = 0$
$f(w^2) = 0$
$f(w^3) = 0$

答案就是：当且仅当 $\frac{f(x)}{(x-w^0)(x-w^1)(x-w^2)(x-w^3)}$ 为一个多项式时，以上约束成立。

4. STARKs、KZG&DEEP上下文中的商多项式

4.1 STARKs上下文中的商多项式

STARKs上下文中，Prover的处理流程为：

1）Prover对execution trace $f$ 进行承诺
2）Prover断言在所有相关点的约束evaluation值均为0：
- $C(f(w^0))=0$
- $C(f(w^1))=0$
- $\cdots$
- $C(f(w^{n-1}))=0$
3）Prover通过展示 $\frac{C(f(x))}{(x-w^0)(x-w^1)(x-w^2)\cdots (x-w^{n-1})}$ 为一个多项式，来证明以上断言的正确。

4.2 DEEP上下文中的商多项式

DEEP为Degree Extension for Elimination of Pretenders的简称。

DEEP上下文中，Prover的处理流程为：

1）Prover对多项式 $f$ 进行承诺，并断言 $f (5) = 2$ 。
2）Prover有2个选项：
- 2.1）选项1：公开 $f (5)$ ，并提供相应的opening proof。
- 2.2）选项2：公开 $f (5)$ ，并提供一个DEEP Quotient：
  - 2.2.1）Prover对第二个多项式 $q(x)=\frac{f(x)-2}{x-5}$ 进行承诺。【其核心思想为：若 $f(5)\neq 2$ ，则 $q$ 将不会是一个多项式。】
  - 2.2.2）Prover对“ $q$ 为多项式”提供FRI proof。（注意，不对“ $f$ 为多项式”提供FRI proof。）

引入DEEP商多项式：

好处在于：可在Merkle tree之外工作。
劣势在于：需额外引入一轮交互开销。

4.3 RISC Zero中的商多项式

RISC Zero ZKP协议中有2个关键的商多项式：

1）针对validity witness的商多项式：在使用随机值将各个约束组合之后，将组合后的结果除以相应的vanishing多项式，获得的即是针对validity witness的商多项式。
2）针对DEEP的商多项式：为证明execution trace承诺值的“openings”是真实有效的，同时为证明其validity witness是有效的，RISC使用DEEP协议，并需计算针对DEEP的商多项式：