Stone Cairo STARK Prover 概述

介绍

大约一个月前，Starkware 开源了其 Stone Prover，该验证器目前在 Starknet 中投入生产。它是一个允许使用 STARK（可扩展的透明知识论证）生成计算完整性证明的库。

该代码库大约有 10 万行代码，主要用 C++ 编写。它有以下主要组件：

• AIR：包含 CAIRO 的代数中间表示 (algebraic intermediate representation) 的约束。
• Channel（STARK Platinum 中的 transcript）：包含 prover 和 verifier 之间的交互，并提供采样随机 challenges 的方法。
• Composition polynomial。AIR 的约束在 trace polynomials 上强制执行，并随机组合成单个 polynomial。
• Commitment schemes：包含（以密码学方式）提交到一系列 polynomial evaluations 的方法。
• FRI，快速里德所罗门交互式 oracle 邻近证明：执行低阶测试，允许证明函数接近低阶 polynomial。

在 Lambdaclass，我们正在开发我们的 Cairo prover，STARK Platinum（用 Rust 编写），使其与 Stone Prover 兼容，以便任何人都可以使用 Rust 版本为构建在 Starknet 之上的不同应用程序生成有效的证明。我们希望我们的 prover 的性能和可用性能够帮助社区采用它。

在这篇文章中，我们将分析 Stone Prover 的一些组件，并解释它们的工作原理和实现。有关 STARK 的介绍，请参阅我们之前的文章或 STARK Platinum 文档。

域 (Domains)

每个实现的域 FF 都有一个单位群 F×F× 的生成器 ωω。它们可以通过调用 PrimeFieldElement 的类方法 Generator 获得。Stark252Field 的生成器是 ω=3ω=3（这里 和 这里）。

表示域的类是 ListOfCosets。TraceGenerator 方法返回一个 trace length 2n2n 阶的单位本原根 gg，它生成一个域 DD。它被计算为 g=ω(p−1)/2ng=ω(p−1)/2n。然后，LDE 表示为一系列陪集 hiwD:i=0,…,k−1hiwD:i=0,…,k−1，所有陪集的大小与 DD 相同，这样它们的并集就是实际的 LDE 域：

DLDE=wD,∪,hwD,∪,h2wD,∪,⋯,∪,hk−1wD,DLDE=wD,∪,hwD,∪,h2wD,∪,⋯,∪,hk−1wD,

其中 h=w(p−1)/2n+kh=w(p−1)/2n+k。

Transcript

Stone prover 使用 NonInteractiveProverChannel 类来处理其与 transcript 的交互。有两个基本操作：

• SendBytes：prover 将字节附加到 transcript。
• ReceiveBytes：prover 从 transcript 接收字节。

这些操作是更复杂操作的构建块，例如采样 FieldElement 或数字。可以使用多种哈希函数与 transcript 交互（例如，Keccak、Pedersen）。

这些操作主要在 HashChain 类中实现，其他类只是委托给它。它具有以下属性：

• self.counter：计算已使用的 KK 字节块的数量。
• self.hash：保存哈希函数的当前状态。
• self.spare_bytes：当用户请求 TT 字节，而 TT 不是 KK 的倍数时，它会存储它们以供以后使用。

这里，KK 是存储所选哈希函数输出所需的字节数（例如，Keccack256 为 32 字节）。

附加到 Transcript

当字节 XX 附加到 transcript 时，获取当前摘要 DD 并将其解释为 BigInt。然后，将 seed increment 添加到其中。这个新 seed 和 XX 的连接是哈希函数的最新状态。

伪代码:

def append(new_bytes, seed_increment):
    digest = self.hash.digest()
    new_seed = digest + self.seed_increment
    self.hash = Hash(new_seed || bytes)

这里，|| 是连接运算符。

从 Transcript 中抽样

伪代码:

def sample_block():
    counter_bytes = | 24 bytes of 0x00 | counter as u64 | # This depends on the "block" size, the hash size.
    self.counter++
    return Hash(self.hash.digest() || counter).digest()

def sample(number_bytes):
    for chunk32 in split(number_bytes, 32):
        result = result + sample_block()
    return result

这是一个简化版本的代码。这里，假设哈希大小为 32 字节（256 位）。此外，此伪代码不处理程序员请求的字节数不是哈希大小的倍数的情况。

Transcript 初始化 (Strong Fiat-Shamir)

主要的prover和verifier可执行文件使用 Fiat-Shamir 策略初始化 transcript。这意味着使用公共参数更新哈希函数。

有两种实现：Fibonacci AIR 和 Cairo AIR (CpuAir)。

• Fibonacci：transcript 使用 claimed_index_in_64_bit_big_endian || claimed_value_in_montgomery_form 初始化
• Cairo：transcript 使用 n_steps、rc_min、rc_max 和公共内存初始化。布局在此处描述here。

记录交互

当执行主prover时，可以启用标志 -generate_annotations 。这会记录 prover 和 verifier 之间的交互，并有助于调试和解决兼容性问题。注释将添加到证明的输出 JSON 文件中。

哈希函数

默认情况下，使用 keccak256 哈希函数。

这是支持的选项列表：

using HashTypes = InvokedTypes<
    Blake2s256, Keccak256, Pedersen, MaskedHash<Keccak256, 20, true>,
    MaskedHash<Blake2s256, 20, true>, MaskedHash<Blake2s256, 20, false>,
    MaskedHash<Keccak256, 20, false>>;

Composition Polynomial

这里 是如何实例化 composition polynomial 并计算其 evaluations 的示例。它可以像 Fibonacci 示例一样运行。

相关类

• CompositionPolynomial：定义接口的抽象类。它只有两个子类

  • CompositionPolynomialImpl：上述的具体实现。它不遵循 pimpl 模式。它只是一个子类。
  • CompositionPolynomialMock：用于测试。
• CompositionOracleProver：CompositionPolynomial 的一个包装器，它也知道 interpolation 的 polynomial（称为 traces）、interpolation 的域和 transcript。

笔记

尽管名称如此，但类 CompositionPolynomialImpl 不负责 composition polynomial 的实际计算。它不处理收集约束的所有单独 evaluations 并将它们粘合在一起以形成 composition poly 的逻辑。它处理并行化并格式化所有输入以将它们传递给 Air::ConstraintsEval。这是 constraints 被 evaluating和聚合以获得 composition polynomial 的 evaluation 的方法。因此，Air 的每个实现都负责所有 constraint evaluations 的正确聚合步骤。

有两件事很突出：

• 没有degree调整。这在 Fibonacci Air 和 Cairo Air 中可以看出。
• 用于聚合所有项的系数都是单个 challenge 的幂。

Evaluation

为了计算 composition polynomial evaluations，prover 调用 CompositionOracleProver::EvalComposition(n_tasks)。这将返回 dd cosets 中 composition polynomial 的 evaluation 集，其中 dd 被选择为最小整数，使得 composition polynomial 的 degree bound 小于 2nd2nd（有关域和陪集的详细信息，请参见 域 部分）。然后，oracle 使用其指向 trace polynomials 的指针在 LDE 域中 evaluating 它们（或使用来自先前 commitment 阶段的缓存计算）。然后，oracle 将其与陪集偏移量和其他域相关数据一起传递给 CompositionPolynomial::EvalOnCosetBitReversedOutput()。此方法启动多个任务，这些任务调用 Air::ConstraintEval 以计算 LDE 上的一个点的单个 evaluation。这是最终完成计算的方法。

打破组合Polynomial

组合polynomial HH 总是被分成 d=deg(H)/2nd=deg(H)/2n 部分，其中 2n2n 是trace长度，

H=H0(Xd)+XH1(Xd)+⋯+Xd−1Hd−1(Xd).H=H0(Xd)+XH1(Xd)+⋯+Xd−1Hd−1(Xd).

为此，在计算 HH 的 evaluation 之后，计算每个 HiHi 的一种方法是插值 HH，然后在其系数上拆分单项式基。Stone prover 中的该方法是对此的优化。他们只执行 log(d)log⁡(d) 步 IFFT，而不是运行完整的 IFFT 来插值 HH，如果 dd 是 2 的幂，则得到每个 HiHi 的 evaluations。

DEEP Composition Polynomial

一个奇怪的设计选择是重用 AIR 和 composition polynomial 机制来构建 DEEP composition polynomial。deep composition polynomial 被视为特定 AIR 的 composition polynomial，称为 BoundaryAIR（参见 这里 和 这里）。它与边界约束无关。它仅用于构建 DEEP composition poly。它是同一个类，与用于算术化要证明的程序的 FibonacciAIR、CpuAir 或任何其他 AIR 无关。deep composition polynomial 在主要的 ProveStark 方法中称为 oods_composition_oracle。

这样做的一个副作用是使注释变得混乱。看起来 verifier 选择了两次用于构建 composition polynomial 的 challenge：

...
V->P: /STARK/Out Of Domain Sampling: Constraint polynomial random element
...
V->P: /STARK/Out Of Domain Sampling: Constraint polynomial random element

第一次指的是 composition polynomial 的 challenge。第二次指的是构建 DEEP composition polynomial 的 challenge。

Commitment Scheme

• 这里 是一个 Python 代码示例。

commitment 算法在其核心很简单，但是许多类相互交互以生成 commitment。此外，还有一些设置和其他因素可以改变 commitment 的方式。例如，由于其大小，在 LDE 上 evaluating 的 trace 可能不适合 RAM，从而改变了 commitment 策略。让我们首先分析核心算法，假设 LDE 适合 RAM 并且不使用任何特殊设置。

这里的策略是构建一个 Merkle 树。为了生成这个 Merkle 树，我们需要知道如何制作树的叶子以及如何将两个节点合并为一个节点以用于下一层。

假设我们要提交以下trace：

我们参考 域 部分以了解域详细信息和陪集。整个 LDE 域由 ww 偏移，hh 的幂表示该值所在的陪集，而 gg 的幂表示该陪集内的索引。在提交 trace 之前，stone prover 会置换行的顺序。

首先，following 按位逆序对陪集进行置换。例如，如果我们有：

| coset 1 | coset 2 | coset 3 | coset 4 |

应用按位逆序置换：

| coset 1 | coset 3 | coset 2 | coset 4 |

然后，再次应用按位逆序，但要在每个陪集内单独应用。最终的置换 trace 将如下所示：

在这种情况下，我们只有两个陪集，因此应用按位逆序没有任何作用，并且这两个陪集保持在相同的位置。然后，重新排序每个陪集内的元素。现在我们有了正确的顺序，我们可以开始构建 Merkle 树的叶子。

每个叶子将对应于一行。这是因为每次 prover 打开 ti(z)ti(z) 时，它都会在相同的值 zz 处打开所有其他列 tj(z)tj(z)，因此将它们存储在同一叶子并对它们使用相同的身份验证路径是有意义的。

如果每列都有 |LDE||LDE| 行，我们将有 |LDE||LDE| 个叶子，每个叶子都有其哈希。第 ii 个叶子是通过哈希第 ii 行中所有列的连接而得到的哈希。因此，例如，本例中的第一个叶子是 H(t0(wh0g0)||t1(wh0g0))H(t0(wh0g0)||t1(wh0g0))。

请注意，stone prover 将其 field elements 存储在蒙哥马利形式中，以提高其运算的性能。当使用 field element 的字节对其进行哈希时，field element 保持为蒙哥马利形式（它不会转换为标准格式）。此外，表示 field element 的 limbs 从最低有效位存储在位置 0，到最高有效位存储在末尾。

现在我们有了叶子，我们的树的第一层，我们可以通过合并节点来构建下一层。为此，Stone Prover 通过连接其哈希并获得新父级的哈希来连接两个连续的节点。重复此操作会将每个步骤中的节点数减半，直到 Merkle 树完成。

有关一个简单的示例，请查看 python 代码。

查看 Fibonacci 示例，了解如何实例化与 commitments 相关的类。

TableProver

TableProver 抽象类及其实现 TableProverImpl 是用于处理 field elements 的二维数组的 commitments 和 decommitments 的高级接口。它主要由一个 commitment scheme 组成，但也有一个指向 ProverChannel 的指针，用于从 verifier 发送和接收元素。

有一个 TableProverFactory 和一个 utils function 来实例化它。还有一个在 测试 中使用的 helper。

TableProverImpl 有一个 Commit 方法，该方法又调用其 commitment_scheme_ 成员的 Commit 方法，该成员是指向 CommitmentSchemeProver 的指针。

CommitmentSchemeProver

此类 实现了 commitment scheme 的逻辑。

有一个 commitment scheme 构建器，它调用另一个方法 这里，该方法通过 交替调用PackagingCommitmentSchemeProver 和 CachingCommitmentSchemeProver 来构造 CommitmentSchemeProver。

段 (Segments)

处理太大而无法装入 RAM 的 traces 或 LDE 时，需要考虑多个细节。

多项式在 LDE 上的 evaluations 被分成段。每个段都包含行的连续子集。为每个部分构建一个 Merkle 树。然后，在此之上构建另一个 Merkle 树，其中叶子是每个段的 Merkle 树的根。

两个注释有助于理解 这里 和 这里

CachingCommitmentSchemeProver

prover 可能希望在 commitment 之后存储整个 Merkle 树，以便在执行 openings 时，无需重新计算它们。但是，如果这太消耗内存，prover 可能会选择不存储它并在以后重新计算它。CachingCommitmentSchemeProver 实现了这个逻辑。

PackagingCommitmentSchemeProver

它有一个内部的 commitment scheme，它将事物分成包并将它们传递给内部的 commitment scheme。

FRI

FRI 部分负责生成 FRILayers、生成查询点和生成证明。该证明由来自每一层 Merkle 树的几个元素加上包含证明（身份验证路径）组成。

Frifolder 从前一层中获取两个 evaluations，并使用 FriFolderBase 类计算当前层的 evaluation。FRI 协议允许提交到某些层的子组（例如，每隔一层）。可以改变提交的层数，但这会使逻辑更加复杂。建议在此 issue 中提交每三层。但是，FRI 步长向量使新用户更难使用 prover，并且我们不认为它在性能方面特别有优势。

该协议区分数据查询和完整性查询；如果 evaluation 是完整性查询的一部分，则它不作为证明的一部分提供。这是因为完整性查询可以从前几层的元素中推断出来。我们不需要直接检查该值；如果我们正确计算了该值，则包含证明应该通过。更具体地说，如果 prover 发送与 pk(xi)pk(xi) 和 pk(−xi)pk(−xi) 对应的值，则 verifier 可以计算 pk+1(x2i)pk+1(xi2)。需要此值来检查 Merkle 树中的包含证明；如果我们使用错误的值，则验证应该失败（除非哈希函数发生冲突）。

该协议在 proof 大小方面进行了优化，因为它避免了从完整性查询发送不必要的信息，成对的值分组在 Merkle 树的同一分支中，并且该协议在达到零度之前完成。

结论

在这篇文章中，我们介绍了 Stone prover 的不同组件、它们的工作原理以及它们对 proof 大小的一些影响。Starkware 在开发 prover 和开源方面做得非常出色。仍然有一些部分需要改进，但这在软件中总是如此。

我们目前正在努力实现 Stone 和 STARK Platinum 之间的兼容性。为了实现这个目标，我们需要调整不同的部分，以便我们生成的 challenges 相同，并且我们得到的 proof（从采样查询中）及其序列化和反序列化也完全相同。我们将继续解释 Stone Prover 的工作原理以及我们添加到 STARK Platinum 中的优化，以提高其性能，同时保持兼容性。

我们采访了正在开发 Iroh 的团队，Iroh 是一个可以正常工作的 Rust 对等库。

简介\ \ 交互式证明是两方（prover PP 和 verifier VV）之间的协议，其中 prover 尝试说服 verifier 证明声明的有效性。通过利用随机性和交互，verifier 可以比完成所有事情更有效地检查声明

TL;DR：这篇文章讨论了 Pod，这是一种新的共识概念，它通过消除副本间通信来实现一次往返（约 200 毫秒）的最佳延迟。我们相信这篇论文和 pod network 的工作具有开创性，我们希望其他人也分享我们对他们工作的兴奋和热情，

• 原文链接： blog.lambdaclass.com/ove...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～