美文网首页
Anatomy of a STARk

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

      本文链接：https://www.haomeiwen.com/subject/gqspgrtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|Anatomy of a STARk|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！