# 多项式承诺，正在重塑整个区块链 By [W3.Hitchhiker](https://paragraph.com/@w3hitchhiker) · 2022-11-03 --- _作者：_**_Xiang｜W3.Hitchhiker_** _修订：Evelyn｜W3.Hitchhiker_ * * * 不同多项式承诺方案列表 ----------- ![](https://storage.googleapis.com/papyrus_images/d27f58da1d035f9ab3cc3a69c006a5327e9d3753e363b35a63430a45a430e0a1.png) 上表中，FRI 是 Starkware 采用的多项式承诺方案，可以实现量子级别的安全，但证明的数据量却是最大；IPA 是 Bulletproof 和 Halo2 零知识算法默认的多项式承诺方案，验证时间相对较长，采用的项目有门罗币，zcash 等，前两者是不需要初始可信设置的。 由上图可以看出在证明大小与验证时间上，KZG 多项式承诺的优势比较大，KZG 承诺也是目前应用最广的一种多项式承诺方式。但 KZG 是基于椭圆曲线，配对函数，需要初始可信设置的。 ETH 升级路线与多项式承诺的关联 ----------------- 在 ETH 相关生态及其未来升级路线中，都可以看到多项式承诺的踪影。 ![](https://storage.googleapis.com/papyrus_images/2fa3f387a09511c7edd62fe979fe6cc0ec5494c915265f4aa9c1c6c188d513fa.png) **The Merge：** 现时的以太坊主链和 Beacon Chain 将会合并，原本的 PoW (工作量证明) 共识将会转变成 PoS (权益证明)。 **The Surge：** 添加DAS（数据可抽样性功能），极大的提高ETH的扩展性，通过 Danksharding 增强 rollup 性能。 **The Verge：** 引入 Verkle 树 (Verkle Trees) 的设计来优化以太坊上的数据存储。 **The Purge：** 通过剔除历史数据和消除技术债务，验证者不再需要使用大量硬盘空间去进行验证工作。 **The Splurge：** 四个不同部分升级后的协调，旨在减少错误 (Bugs) 的出现和确保网络能畅顺运作，还有就是 EVM 改进和添加账号抽象模型等。 其中 The Surge 升级将借鉴多项式承诺技术实现数据可抽样性功能，The Verge 升级将利用多项式承诺来优化其数据结构，ETH L2 的 zkrollup 也都采用了多项式承诺来实现其零知识证明带来的性能拓展。 什么是 KZG 多项式承诺 ------------- 此文这里只介绍较好理解的 KZG 多项式承诺，KZG 多项式承诺（KZG Polynomial Commitment）也被称为卡特多项式承诺方案，是 Kate，Zaverucha 和 Goldberg 一起发表的。在一个多项式方案中，证明者计算一个多项式的承诺，并可以在多项式的任意一点进行打开，该承诺方案能证明多项式在特定位置的值与指定的值一致。 之所以被称为承诺，是因为当一个承诺值（椭圆曲线上的一个点）发送给某对象(验证者)时，证明者不可以改变当前计算的多项式。他们只能够对一个多项式提供有效的证明；当试图作弊时，它们要不无法提供证明，要不证明被验证者拒绝。 KZG 数学原理 -------- 详细可参考 Qi Zhou 博士在 Dapp Learning 讲解的关于 [KZG 视频](https://www.youtube.com/watch?v=n4eiiCDhTes)。 在理解 KZG 之前，可以先了解一下多项式、群、环、域、椭圆曲线、生成元、配对公式、朗格朗日插值等数学定义。 ![](https://storage.googleapis.com/papyrus_images/d0651fc031dd45b57d85a22af765280d3d35f20fb09ef985d882fbeb40684a80.png) ### 具有可信设置的多项式承诺 ![](https://storage.googleapis.com/papyrus_images/5b9ea70c1ddaef502bdc3e542d4b3bd4ebd21690cc769bd5857eefba40273644.png) ### 单个证明 卡特证明单个数据的公式推衍如下，由于椭圆曲线群只支持加法同态，无法支持多项式之间的乘法，这是就需要通过配对函数解决， ![](https://storage.googleapis.com/papyrus_images/655d2ddb3a806fb909954a0df71c7e52fd100949d2b9d128b6e086febec2db89.png) 由于椭圆曲线群并不支持运算多项式之间的乘法运算，所以此时得采用配对函数去解决 ![](https://storage.googleapis.com/papyrus_images/8aad9fefcdfbc04728dfaffadb63abea0c9065f293ce3760228f18d0f6a22249.png) ### 批量证明 ![](https://storage.googleapis.com/papyrus_images/8c6451d697221d2f08812654ed3232148e2c21dd492d10790efca19076e6f119.png) 具体应用场景 ------ **多项式承诺应用方向总结起来可以分为 3 大类：** 1. **数据可用性**（ETH Surge 升级，ETH danksharding，降低 L2 成本，模块化数据可用性项目 Avails） 2. **数据结构优化**（MPT 树改为 Verkle 树，ETH Verge 升级，无状态客户端，实现 ETH 的轻量的验证节点） 3. **零知识证明系统**（Zksync，Zkswap，Scroll，PSE 给 Zk 提供多项式承诺方案，大大提升链的拓展能力） ### 1\. 数据可用性 ### DAS（数据可用性抽样） 核心目的：数据缺失则无法通过大多数节点抽查 尽力做到：占用带宽小，抽样过程所需计算量小 ### 纠删码（celestia） ![](https://storage.googleapis.com/papyrus_images/c366ab4d6dbf8fbbc4079be41217ba4eb690576c202efcbca29422b70f7c586c.png) 纠删码会增加额外数据块，这种情况很容易通过抽样调查发现，从而提升安全性。 以上图为例，有 4 个数据，一次只能抽样一个，假设一个数据有问题，每个用户抽样发现错误的概率是 1/4，但是加入两数据块后，还是一个数据有问题，用户抽样发现的概率可以高达 1/2（3/6）。这样就能大幅提升安全性。 KZG 也可实现纠删码，利用拉格朗日公式： 比如把 (0,3)，(1,6) 带入公式可得，`y=3x+3` `y1，y2` 可以理解为要保存的数据， 对应点（2,8）(3,12) 等等，其中 `y` 值可以作为纠删码数据，其中任意两个点都可以推出原多项式公式系数。 ![](https://storage.googleapis.com/papyrus_images/21507e95e89969301a04a2c0ae57b768bf9c018b35468628c26eb2e524c30836.png) ### 不同数据可用性项目组成 **Celestia = Tendermint (cosmos) + 2d 纠删码 + 欺诈证明 + Namespace merkle tree + IPFS 基础设施（数据存储用的 IPFS Blockstore，传输网络用的 IPFS 的 Libp2p 与 bitswap，数据模型用的 IPFS 的 Ipld）** **Polygon Avail = Substrate(Polkadot) + 2d 纠删码 + KZG 多项式承诺 + IPFS 基础设施** **ETHprotoDankSharding = Blobs 数据（数据可用性的存储，替换现有的 calldata）+ 2d 纠删码 + KZG 多项式承诺（未定，**[**方案**](https://ethresear.ch/t/arithmetic-hash-based-alternatives-to-kzg-for-proto-danksharding-eip-4844/13863)**目前仍在讨论）+ ETH 基础设施** **EIP-4844 升级将在 The Merge 之后的下一个以太坊分叉升级中引入“proto-danksharding”并添加blob交易类型（EIP-4844），这有望将第 2 层 Rollup 的可扩展性提高，同时为实现完全分片（sharding）铺平道路。** ### Blob Transaction [ Sharding-format blob-carrying transactions - HackMD --------------------------------------------------- Simple Summary Introduce a new transaction format for "blob-carrying transactions" which conta https://notes.ethereum.org ![](https://storage.googleapis.com/papyrus_images/c0ad2cff31ba696f94fe7c69e3620ae023ccce89c3c1f4f16363ddcb58c01235.png) ](https://notes.ethereum.org/@vbuterin/blob_transactions) 1. 增加一种新的交易类型，这种交易包含额外的存储空间 —— Blobs 2. Blob 开始只有 128 KiB 的存储空间 （1）一个交易最多包含 2 个 Blob，即 256 KiB （2）一个 Block 最多包含 16 个，即 2 MiB；Target 是 8 个，即 1 MiB（可扩大） 3. Blob 以 KZG Commitment Hash 作为 Hash，用于数据验证，作用和 Merkle 类似 4. 节点同步链上的 Blob Transaction 后，Blob 部分会在一段时间后过期删除 ![](https://storage.googleapis.com/papyrus_images/3356e738cdb6d5fb515c2926b0eef9220a57e30af5920b64dde843ce91f58537.png) L2 需要通过更新目前在 L1 的合约，以支持 DankSharding。 Celestia 通过欺诈证明实现。当见证人发现数据没有被正确采用删码技术，那么这个人就会将欺诈证明提交从而来提醒其他节点。但是这里需要最少诚实假设（至少连接到一个诚实节点）和同步假设（当有人给我发送欺诈证明的时候，需要确保我能在一定时间内收到通知）。 protoDanksharding 后的以太坊和 Polygon Avail 则采用了 KZG 多项式承诺（KZG commitments) 的方法。 KZG 多项式承诺方案，理论上要优于欺诈证明方案，带宽需求更小，抽样所需计算量也更小，也免去了欺诈证明中的包括少数诚实假设和同步假设等的安全假设。 未来 ETH 也有意引入抗后量子密码学(参考 stark，采用哈希，不在使用椭圆曲线作为基础)，避免量子计算机攻击。 ### 2\. 数据结构优化 Verkle Tree Verkle Tree 的概念在 2018 年推出，作为 ETH 升级的一个重要部分，其相比于 Merkle Tree，在 Proof 的大小上，有着很大的提升；对于规模在十亿级别的数据，Merkle Tree 的 proof 大约需要 1kB，而对于 Verkle Tree， 它将小于 150Bytes。 与 Merkle Tree 一样 Verkle Tree 也能实现 Proof of Inclusion（PoI），而且只需 KZG root 和 Data 就能验证，不需要额外的 Proof，更省**带宽**。 1. 需求：Stateless Client （1）节点不存完整的 State Tree，只获取需要的 State 来验证 Block （2）[Portal Network](https://github.com/ethereum/portal-network-specs) （3）对 State Tree 的 PoI 有更高的性能要求 2. 回顾 Data Availability 里的 [KZG commitment](https://www.notion.so/caa896aae59d489b98f2448f17b01640) 1. 每个 leaf 都是 polynomial 上的点 2. constant size proof，和 leaf 数量无关 ![](https://storage.googleapis.com/papyrus_images/45dff6d49971b15625f0aa670f28468268f6e1dadbc48afc24c1a9243d44d4a8.png) 3\. Verkle Tree [ Verkle tree structure | Ethereum Foundation Blog ------------------------------------------------ A Verkle tree is a commitment scheme that works similar to a Merkle tree, but has much smaller witnesses. It works by replacing the hashes in a Merkle tree with a vector commitment, which makes wider branching factors more efficient. Thanks to Kevaundray Wedderburn for feedback on the post. https://blog.ethereum.org ![](https://storage.googleapis.com/papyrus_images/e12f8c24c2711d7c52fa168870610664d68da4a29c1198b1bff2abb4897586f7.jpg) ](https://blog.ethereum.org/2021/12/02/verkle-tree-structure) ![](https://storage.googleapis.com/papyrus_images/5eaefb3b499034f19d42ff6769df7fd5085f3ae616949e99f3de7b45e4c118fc.png) ![](https://storage.googleapis.com/papyrus_images/ec6593082249a66083752bed1c96df17bbae2dd12e5a169c90a29ff0dce980e1.png) 在不同树结构中构建证明，更新证明，以及证明所需的复杂度： ![](https://storage.googleapis.com/papyrus_images/9f2a999668ddaa85310bfad372be4864a6621a8a17b705b35bff140a37e212c2.png) ![](https://storage.googleapis.com/papyrus_images/749cbcb0dcec7d0c365b434620f305e76b64c2b11586e7f203ad9e15eaaac6c7.png) Verkle 方案不需要以太坊客户端下载完整的状态数据，使得 ETH 验证者轻节点成为可能(甚至可支持手机运行)，多项式承诺（Verkle 树的多项式承诺方案，早期考虑的 KZG，近期还是考虑用 IPA）需要的证明空间复杂度大幅降低，带宽量需求量也大幅减少。 ### 3\. 零知识证明系统 ![](https://storage.googleapis.com/papyrus_images/c4b8784077bfc0178995a700132de8f1131d2976e744d8a21bb7f98296caaf8c.png) 早期 zk 技术（Groth16）属于线性 PCP 类。 除要求可信设置外，主要缺点是如果需要为不同的计算（不同的电路/多项式）提供证明，都需要一次新的设置。近期 zk 技术 PIOP 类支持通用初始设置和透明设置（不需要信任假设）。 新的 zk 证明系统通常可以描述为 PIOP（Polynomial Interactive Oracle Proof，多项式交互预言证明）+ PCS（Polynomial Commitment Scheme，多项式承诺方案）。前者可被视为是证明者用来说服验证者的约定程序，而后者使用数学方法确保该程序不会遭到破坏。项目方可以按需修改 PIOP，且可以在不同 PCS 中进行选择。 ![](https://storage.googleapis.com/papyrus_images/169ec615a4405103ef7783e6eec6958b53698eb78cc7692d1a40637175c9db72.png) 由 Amber 文章里的图可以看到 zk 系公链项目采用 KZG 方案的最多，有 Ploygon Hermez，Scoll，Zksync2.0，Aztec，Aleo，Manta，以太坊基金会支持的 PSE（隐私与扩展探索团队）也采用的 KZG 方案。而 Starknet，Risc0，Polygon Miden 采用的是 FRI 方案，Ploygon Zkvm(Hermez) 则是 FRI 与 KZG 的结合。 值得一提是，一些新的零知识证明系统支持多项式承诺方案的切换，KZG 未来也可以切换成其他多项式承诺方案。 总的来说，多项式承诺正在重塑整个区块链的架构，不论是在链的数据结构优化上，模块化区块链的数据可用性上，还是零知识证明系统上都将大有作为。其他地方是否还存在应用场景也是非常值得探索与跟进的。 * * * > _声明：本文内容仅供参考、交流，不构成任何投资建议。若存在明显的理解或数据的错误，欢迎反馈。_ > > _本文内容系 W3.Hitchhiker 原创，如需转载请标明出处。_ > > _商务合作：_[_rex@w3hitchhiker.com_](mailto:rex@w3hitchhiker.com) > > _官网：_[_https://w3hitchhiker.com/_](https://w3hitchhiker.com/) > > _W3.Hitchhiker 官方推特：_[_https://twitter.com/HitchhikerW3_](https://twitter.com/HitchhikerW3) --- *Originally published on [W3.Hitchhiker](https://paragraph.com/@w3hitchhiker/oampmfwsqnGgVozZCyrc)*