电路中的 Verkle Trie

电路内 Verkle 树

这是一个项目提案草案，当前该项目的目标是获得电路内 Pedersen 哈希和承诺的基准，该基准用于 Verkle 树与用于 MPT 的 Keccak 哈希，使事情过于复杂毫无意义

VKT - verkle 树 MPT - merkle patricia 树

本文档的目的是描述一个项目提案，用于在电路内创建一个 verkle 树数据结构，这意味着状态变化的执行可以在 zk 电路中有效地证明（因为消除了主要的瓶颈 - keccak-sha3）。

动机

为了使以太坊更具可扩展性、去中心化和安全性，提出了一种新的存储数据结构：Verkle 树。更多信息请参见： https://verkle.info/

（不确定 VKT 是否为以太坊增加了更多安全性， 我认为 MPT 比 VKT 更安全，因为 keccak 的量子安全性高于 ECC， 但在接下来的 5-10 年里我们仍然应该没问题（目前还没有量子计算机）） - 至少这是我目前的理解 编辑： 存在“功能承诺”，它们是后量子安全的、加法同态的，但它们需要某种可信设置，我正在学习这是否可以在电路内高效实现，这是论文：https://eprint.iacr.org/2022/1368.pdf

来自 Lev（https://github.com/Lev-Stambler/CP22-function-commitment）关于他在这项功能承诺方面的工作以及他的回答的评论：

• 这篇论文的问题在于，它强迫人们使用布尔字段而不是更大的算术字段。 这对整个电路造成了巨大的打击，更不用说还有一个常数级的膨胀（例如，每个布尔值都用约 1_000 位表示）。

从 MPT 过渡到 VKT 的两个原因是，它将帮助以太坊实现弱无状态，并帮助引导更多验证者（更多去中心化），而且它比在 zk rollup 的电路中证明 merkle 树便宜且容易得多（更多可扩展性），这意味着应该更容易拥有 1 类 zk-evm（因为消除了 keccak 并具有椭圆曲线运算（pedersen 承诺 + IPA））- 这应该更容易在 zk 电路中验证。

我已在 Ethereum R&D discord 的 "verkle-trie-migration" 频道中询问是否有人已经在电路内使用 VKT， 似乎没有这样的项目，所以我认为研究它是有意义的。来自 Scroll 团队的 Zhang Zhuo (https://github.com/lispc/) 已经提供了帮助。

我在阅读 bandersnatch 椭圆曲线论文时产生了这一想法：https://eprint.iacr.org/2021/1152.pdf 并做了小型黑客马拉松项目。

因此，选择该曲线是为了对 zk-snarks 友好，并且标量乘法效率高，并且 pedersen 承诺在电路内应该很高效。该项目的目标是了解所有这些内容，并针对电路内实现的 MPT 原语（主要是 keccak）进行基准测试。例如，证明时间。

项目描述

我们需要的东西的高级概述：

• 具有 GLV 自同态的 bandersnatch 椭圆曲线，用于更快的标量乘法（GLV 可能没有必要在电路中使用）：https://eprint.iacr.org/2021/1152.pdf
• banderwagon 子群：https://hackmd.io/@6iQDuIePQjyYBqDChYw_jg/BJ2-L6Nzc
• pedersen 承诺 + IPA（内积参数）-- https://dankradfeist.de/ethereum/2021/07/27/inner-product-arguments.html
• verkle 树结构（内部节点、扩展节点和后缀节点、叶节点），具有 256 个子节点，以及用于添加、编辑和删除键值的逻辑（计算每个父节点直至根节点的承诺和最终 IPA 证明）：https://notes.ethereum.org/@vbuterin/verkle_tree_eip

由于 Ethereum PSE 团队正在使用 halo2 库开发 ZKEVM 1 类，我想了解更多相关信息并开始为 VKT 编写电路。到目前为止，我已经编写了小型项目，例如： https://github.com/dragan2234/fibosquared-halo2

此外，对于第一次迭代，我认为我们可以只让 VKT 电路正确运行，而不与 zkevm 项目集成。然后我们将针对 MPT 电路进行基准测试。基准测试示例：

• VKT 与 MPT 见证计算，用于插入、删除和更新 1 个值：证明时间

由于 zkevm 项目的 MPT 电路开发持续了 2 年，因此该项目并非易事，但仍然不应该那么复杂。本届 cohort 结束时的任何产出都应该是有用的。

有用的链接：

• 用于在电路中构建 ECC 的 Axioms 框架：https://github.com/axiom-crypto/halo2-lib#halo2-ecc
• https://verkle.info/
• https://verkle.dev/ -- 该网站目前正在建设中，但它应该有一些内容

规范

待定。

路线图

• 实现 bandersnatch 椭圆曲线
• 实现标量乘法
• 实现 banderwagon
• 实现 pedersen 承诺
• 实现 ipa_multiproof
• 实现 VKT 结构

可能的挑战

• 个人是 VKT、MPT 和 halo2-lib 的初学者

关于挑战的更新：

• 因此，选择 bandersnatch 曲线时考虑了 bls12-381，因为 bandersnatch 的基础字段 == bls12-381 的标量字段。这样做的原因是使其对 snark 友好，但以太坊对预编译使用 bn254，并且大多数 rollup 也在证明器中使用 bn254 进行 kzg 承诺
• 至少从我的调查来看，没有 rollup 使用 bls12-381
• 到目前为止，我意识到的唯一使用 bls12-381 的证明系统是 marlin
• 我不知道拥有 plonk + kzg 之类的证明系统的分支有多难，但使用 bls12-381 并让 halo2 api 在该后端上工作
• 在 Grumpkin 曲线（类似于 bandersnatch 但用于 bn254）上使用 verkle 树是否有意义？ Aztec 使用了这条曲线，可能还有更多差异，但它们也进行 pedersen 承诺，因此应该相同。但我认为这不属于 1 类兼容性，因为曲线不同，并且 pedersen 哈希也会不同。但这仍然有利于电路内 pedersen 承诺与电路内 keccak 的基准测试

在挑战中的更新 2：

• 目前没有证明系统和 rollup 使用 bls12-381 曲线。 Halo2 是最灵活的证明系统，并且有一个 PR 即将完成，因此 bls12-381 可以“轻松”合并到使用 halo2 仓库的证明系统中：https://github.com/privacy-scaling-explorations/halo2curves/pull/38

更新 3：

• 总的想法：将这个 repo：https://github.com/crate-crypto/rust-verkle 合并到 http://github.com/paradigmxyz/reth，然后再合并到 https://github.com/risc0/zeth
• 这似乎是拥有带有 Verkle 树的 zkEVM 1 类，并衡量这将如何提高性能/证明时间的最简单方法
• 项目想法：采用 keccak 和 pedersen 承诺的 rust 代码在VKT中指定，并使用 risc0 技术对其进行基准测试。理解改进应该不会太难

更新 4： 来自 https://github.com/asanso 的评论，关于 banderwagon 在电路中是否高效： 是的，它将提供与 https://github.com/zhenfeizhang/bandersnatch#examples “示例”部分中的来自 bandersnatch r1cs contraints 基准测试类似的基准。

基准： bandersnatch: base var 的 cs：5 标量 var 的 cs：256 mul 的 cs：2869 result var 的 cs：27 equality 的 cs：20 总约束数：3177

jubjub: base var 的 cs：21 标量 var 的 cs：256 mul 的 cs：3325 result var 的 cs：21 equality 的 cs：2

带有 glv 的 bandersnatch: setup 的 cs：16 endomorphism var 的 cs：6 标量分解 var 的 cs：405 msm 的 cs：2176 result var 的 cs：16 equality 的 cs：2 总约束数：2621

• 也许对 banderwagon 进行这样的基准测试也是有意义的

项目目标

• 了解 verkle 树中使用的密码学和数据结构，并使用 halo2 库编写电路。
• 对电路内 VKT 与 MPT 进行基准测试， 并对电路内 VKT 的效率得出一些结论，因为与 EVM 兼容的 L2 解决方案将需要它。

合作者

研究员

有几个人对此感兴趣，并非所有人都来自 EPF 项目。 我们将在启动时在此处添加每个人。

导师

• Ignacio Hagopian

资源

• 用于在电路中构建 ECC 的 Axioms 框架：https://github.com/axiom-crypto/halo2-lib#halo2-ecc
• https://learn.0xparc.org/halo2/ - 使用 halo2 lib 编写电路的教程
• https://verkle.info/
• https://verkle.dev/ – 该网站目前正在建设中，但随着时间的推移，它应该会有一些有用的文档

更多更新（稍后将清理整个文件）：

• 可能有用的这个 repo，因为它是 bls12-381：https://github.com/ZK-Garage/plonk
• 此项目的目的是获得电路内 pedersen 哈希的基准，使事情过于复杂毫无意义
• 如何使用 verkle 树使 kakarot zkevm 成为 1 类：https://hackmd.io/CmCJxFBkT7u-bIQ9Y7tKyQ

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