Anatomy of a STARk

作者: 雪落无留痕 | 来源:发表于2022-08-20 01:20 被阅读0次

STARKs是一类交互式证明系统，可以当用是一种特殊的SNARKs:

hash函数是唯的密码组件；
算术化基于AIR (algebraic intermediate representation)，将计算完整性问题约减为多项式低度测试问题；
低度多项式证明采用FRI 协议，FRI 采用 Merkle树实例化；
Zero-knowledge 是可选的。

概览

STARK 表示 Scalable Transparent ARgument of Knowledge.

证明者的运行时间是准线性的（quasilinear）;
验证者的时间复杂度是poly-logarithmic;
不需要可信设置；
非交互的 STARKs 可以看作是 SNARKs的一个子类。

STARK的实现可由下图表示：

计算

计算可以看一个程序，有输入和输出。程序由指令组成，用于操纵数据。

算术化和算术约束系统

算术化主要逻辑和算术的运算转换为有限域上的运算，其输出为：算术化约束系统，即一些等式方程。计算完整性的证明即找到满足方程的解。

STARK 证明状态计算由 $w$ 个寄存器表示，值为有限域 $\mathbb{F}$ 。状态转移函数为： $f: \mathbb{F} \rightarrow \mathbb{F}$ . AET (Algebraic execution trace) 是状态元组更新的列表。

算术化约束系统有两种约束：

边界约束：计算起始位置的值；
转移约束：连续状态元组的值转移的规则。

这些约束也称为为AIR (algebraic intermediate representation).

插值和多项式IOP

插值用来表示数值化约束系统的的多项式表示。IOP (interactive oracle proof) 是指抽象的黑盒函数，其中验证者可以进行随机查询。当对应低度多项式的时间，也称为多项式IOP.

对于STARK 证明，它计算 $w$ 个多项式 $t_i(X)$ ，对应域为 $D$ ，值为第 $i$ 个寄存器的AET。

插值将算术化约束系统的可满足性转变为多项式的低度问题。

FRI

FRI是STARK 的关键组件，采用基于Merkle 树的 Reed-Solomon 码字证明多项式度数的有界性。

FRI 表示： Fast Reed-Solomon IOP of Proximity, 是多项式低度证明协议。

![The STARK proof system revolves around the transformation of low-degree polynomials into new polynomials whose degree boundedness matches with the integrity of the computation.]

基本工具

有限域

选择一个大素数 $p$ , 有限域元素 $\mathbb{F}_p = \{0,1,\cdots, p-1\}$ . 逆元采用扩展的Euclidena算法实现。

STARKs 有限域需要一种特别的结构： $p = f\cdot 2^k +1$ ，其中 $f$ 为余因子， $k$ 为一个非常大的数。

单变量多项式

单变量多项式定义为： $f(X) = c_0 + c_1\cdot X + \cdots + c_dX^d$ , 其中 $c_i$ 称为系统， $d$ 为多项式的度。

多变量多项式

多变量扩展单变量多项式，有更多变量，如 $X, Y, Z$ 等，多变量多项式主要用来表述算术化约束。

Fiat-Shamir 变换

采用 proof stream 用来描述 Fiat-Shamir 变换，主要支持三个功能：

Pushing and pulling
Serialization and deserialization
Fiat-Shamir, 采用 SHAKE-256 算法。

Merkle 树

Merkle 树基于抗碰撞Hash函数构造的向量承诺方案。

Merkle 树构造需要有三种功能：

commit: 计算Merkle 根；
open: 计算Merkle 树的认证路径；
verify: 验证某个叶子节点的存在性。

FRI

FRI （Fast Reed Solomon IOP of Proximity）协议y主要用来证明承诺多项式具有有限的次数。FRI 采用 codewords 表示，对应着低度多项式的值，定义在域 $D$ 上。值的长度比多项式次数扩展，也称为blowup 因子，是代码率（code rate） $\rho$ 的倒数。

对于一般的多项式承诺方案，证明承诺多项式 $f(X)$ ，在指定的点 $z$ 打开, 值为 $f(z)$ :

commit: 计算多项式的绑定方案；
open: 生成证明 $f(z) = y$ ，对于指定承诺的多项式 $f(X)$ ;
verify: 验证证明。

FRI用于确定指定的codeword 属于低度多项式，低度表示多项式次数只有 codeword 长度的 $\rho$ 。

Split and Fold

在FRI 协议中，声明指定的codeword 对应着低度多项式，用 $N$ 表示codeword 的长度， $d$ 为多项式的最大次数，即多项式为 $f(X) = \sum_{i=0}^dc_iX^i, d=2^k-1$ , 。

采用FFT 分而治之的策略，多项式可以分为奇数和偶数两部分：

$f(X) = f_E(X^2) +X\cdot f_O(X^2)$ ，其中 $f_E(X^2) = \frac{f(X)+f(-X)}{2}, f_O(X^2) = \frac{f(X)-f(-X)}{2X}$

FRI 协议的关键步骤是从 $f(X)$ 得到 $f^*(X) = f_E(X)+ \alpha\cdot f_O(X)$ ，其中 $\alpha$ 是由验证者提供的随机标量。

定义 $D$ 为 $N$ 阶乘法群， $\omega$ 为子群的生成元： $<w> = D \subset \mathbb{F}_p \backslash \{0\}$

对于 $f(X)$ 的码字 $\lbrace f(\omega^i)\rbrace_{i=0}^{N-1}$ , 对应域为 $D$ ；设 $D^\star = \langle \omega^2 \rangle$ 为另一个域，长度减半， $\lbrace f_ E(\omega^{2i})\rbrace_{i=0}^{N/2-1}$ , $\lbrace f_ O(\omega^{2i})\rbrace_{i=0}^{N/2-1}$ , $\lbrace f^\star(\omega^{2i})\rbrace_ {i=0}^{N/2-1}$ 分别为 $f_E(X), f_O(X), f^\star(X)$ 的码字，定义域为 $D^\star$ ；
$\lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1} = \lbrace f_E(\omega^{2i}) + \alpha \cdot f_O(\omega^{2i})\rbrace_{i=0}^{N/2-1} .$
再次扩展得到：

$\lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1}$

$= \left\lbrace \frac{f(\omega^i) + f(-\omega^i)}{2} + \alpha \cdot \frac{f(\omega^i) - f(-\omega^i)}{2 \omega^i} \right\rbrace_{i=0}^{N/2-1}$

$= \lbrace 2^{-1} \cdot \left( ( 1 + \alpha \cdot \omega^{-i} ) \cdot f(\omega^i) + (1 - \alpha \cdot \omega^{-i} ) \cdot f(-\omega^i) \right) \rbrace_{i=0}^{N/2-1}$

由于 $w$ 的阶为 $N$ ， $w^{N/2}=-1$ ，因此 $f(-w^j)= f(w^{N/2+i})$

此时可以描述一轮的FRI 协议，证明者通过Merkle 根对 $f(X)$ 承诺，验证者响应随机挑战 $\alpha$ , 证明者计算 $f^\star(X)$ , 并进行承诺，将 $\lbrace f^\star(\omega^{2i})\rbrace_{i=0}^{N/2-1}$ 的根给验证者。

验证者验证对应的关系成立： $f^\star(X) = 2^{-1} \cdot \left( (1 + \alpha X^{-1}) \cdot f(X) + (1 - \alpha X^{-1} ) \cdot f(-X) \right)$

上面对应1轮FRI 协议，FRI 总共需要 $\lceil \log_2 (d+1) \rceil - 1$ 轮，其中 $d$ 为原始多项式的次数，最终变成一个常量多项式。

image.png

实际中，codeword 的长度约减不是2，而是2的幂次。

安全级别

需要进行多少次（colinearity）检查，才能实现 $\lambda$ 位的安全呢？

构建 Merkle 树的Hash函数需要至少 $2\lambda$ 位输出；
域至少需要 $2^{\lambda}$ 个元素；
对于每个colinearity 检查，可以增加 $\log_2 \rho^{-1}$ 位安全，所以为了达到 $\lambda$ 位安全，colinearity 检查次数需要为： $s = \lceil \lambda / \log_2 \rho^{-1} \rceil$

Coset-FRI

FRI定义域 $D$ 会和STARK 的域有重合的值，为了避免两者产生交集，采用陪集。

陪集的定义域为： $D = \{g\cdot w^i | i \in \mathbb{Z}\}$ ，一般 $g$ 为整个乘法群 $\mathbb{F}\backslash \{ 0\}$ . 下一轮码字的定义域为： $D^\star = \lbrace d^2 \vert d \in D\rbrace = \lbrace g^2 \cdot \omega^{2i} \vert i \in \mathbb{Z}\rbrace$ 。

Prove

FRI 协议分两个阶段：承诺和查询。在承诺阶段，证明给验证者发送codeword 的Merkle 根；验证者提供随机域元素，执行split-and-fold 过程。在查询阶段，验证者选择叶子节点的索引，然后证明者打开，检查者检查 colinearity 要求。

承诺阶段由以下一些轮组成：

码字的Merkle 根；
将Merkle 根发送给验证者；
验证者提供随机挑战 $\alpha$ ;
证明者根据split-and-fold 公式得到下一轮的码字；
证明者计算 $g$ 和 $w$ 的平方，使得 $\lbrace g\cdot w^i \vert i\in \mathbb{Z} \rbrace$ 对应着下一轮码字的定义域。

最后一轮的时候，证明者只剩下一个码字，将其直接发送给验证者。

Verify

验证者执行以下步骤：

从Proof stream 读取Merkle 根，通过Fiat-Shamir 重新生成随机标量 $\alpha$ ;
读取最后的码字，验证它对应着低度多项式和最后的Merkle 树根；
重新生成Fiat-Shamir 和随机索引，推断共线性检查的剩余索引；
从proof stream 读取Merkle 叶子节点和认证路径，验证其真实性；
对于每一对连续的码字，运行colinearity 检查。

参考

https://aszepieniec.github.io/stark-anatomy/

https://github.com/aszepieniec/stark-anatomy

https://aszepieniec.github.io/stark-brainfuck/

https://github.com/aszepieniec/stark-brainfuck

https://eprint.iacr.org/2021/582

Anatomy of a STARk

概览

计算

算术化和算术约束系统

插值和多项式IOP

FRI

基本工具

有限域

单变量多项式

多变量多项式

Fiat-Shamir 变换

Merkle 树

FRI

Split and Fold

安全级别

Coset-FRI

Prove

Verify

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读