多项式承诺,正在重塑整个区块链

作者:Xiang|W3.Hitchhiker

修订:Evelyn|W3.Hitchhiker


不同多项式承诺方案列表

上表中,FRI 是 Starkware 采用的多项式承诺方案,可以实现量子级别的安全,但证明的数据量却是最大;IPA 是 Bulletproof 和 Halo2 零知识算法默认的多项式承诺方案,验证时间相对较长,采用的项目有门罗币,zcash 等,前两者是不需要初始可信设置的。

由上图可以看出在证明大小与验证时间上,KZG 多项式承诺的优势比较大,KZG 承诺也是目前应用最广的一种多项式承诺方式。但 KZG 是基于椭圆曲线,配对函数,需要初始可信设置的。

ETH 升级路线与多项式承诺的关联

在 ETH 相关生态及其未来升级路线中,都可以看到多项式承诺的踪影。

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 视频

在理解 KZG 之前,可以先了解一下多项式、群、环、域、椭圆曲线、生成元、配对公式、朗格朗日插值等数学定义。

具有可信设置的多项式承诺

单个证明

卡特证明单个数据的公式推衍如下,由于椭圆曲线群只支持加法同态,无法支持多项式之间的乘法,这是就需要通过配对函数解决,

由于椭圆曲线群并不支持运算多项式之间的乘法运算,所以此时得采用配对函数去解决

批量证明

具体应用场景

多项式承诺应用方向总结起来可以分为 3 大类:

  1. 数据可用性(ETH Surge 升级,ETH danksharding,降低 L2 成本,模块化数据可用性项目 Avails)

  2. 数据结构优化(MPT 树改为 Verkle 树,ETH Verge 升级,无状态客户端,实现 ETH 的轻量的验证节点)

  3. 零知识证明系统(Zksync,Zkswap,Scroll,PSE 给 Zk 提供多项式承诺方案,大大提升链的拓展能力)

1. 数据可用性

DAS(数据可用性抽样)

核心目的:数据缺失则无法通过大多数节点抽查

尽力做到:占用带宽小,抽样过程所需计算量小

纠删码(celestia)

纠删码会增加额外数据块,这种情况很容易通过抽样调查发现,从而提升安全性。

以上图为例,有 4 个数据,一次只能抽样一个,假设一个数据有问题,每个用户抽样发现错误的概率是 1/4,但是加入两数据块后,还是一个数据有问题,用户抽样发现的概率可以高达 1/2(3/6)。这样就能大幅提升安全性。

KZG 也可实现纠删码,利用拉格朗日公式:

比如把 (0,3),(1,6) 带入公式可得,y=3x+3

y1,y2 可以理解为要保存的数据,

对应点(2,8)(3,12) 等等,其中 y 值可以作为纠删码数据,其中任意两个点都可以推出原多项式公式系数。

不同数据可用性项目组成

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 多项式承诺(未定,方案目前仍在讨论)+ ETH 基础设施

EIP-4844 升级将在 The Merge 之后的下一个以太坊分叉升级中引入“proto-danksharding”并添加blob交易类型(EIP-4844),这有望将第 2 层 Rollup 的可扩展性提高,同时为实现完全分片(sharding)铺平道路。

Blob Transaction

  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 部分会在一段时间后过期删除

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

    (3)对 State Tree 的 PoI 有更高的性能要求

  2. 回顾 Data Availability 里的 KZG commitment

    1. 每个 leaf 都是 polynomial 上的点

    2. constant size proof,和 leaf 数量无关

3. Verkle Tree

在不同树结构中构建证明,更新证明,以及证明所需的复杂度:

Verkle 方案不需要以太坊客户端下载完整的状态数据,使得 ETH 验证者轻节点成为可能(甚至可支持手机运行),多项式承诺(Verkle 树的多项式承诺方案,早期考虑的 KZG,近期还是考虑用 IPA)需要的证明空间复杂度大幅降低,带宽量需求量也大幅减少。

3. 零知识证明系统

早期 zk 技术(Groth16)属于线性 PCP 类。 除要求可信设置外,主要缺点是如果需要为不同的计算(不同的电路/多项式)提供证明,都需要一次新的设置。近期 zk 技术 PIOP 类支持通用初始设置和透明设置(不需要信任假设)。

新的 zk 证明系统通常可以描述为 PIOP(Polynomial Interactive Oracle Proof,多项式交互预言证明)+ PCS(Polynomial Commitment Scheme,多项式承诺方案)。前者可被视为是证明者用来说服验证者的约定程序,而后者使用数学方法确保该程序不会遭到破坏。项目方可以按需修改 PIOP,且可以在不同 PCS 中进行选择。

由 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

官网:https://w3hitchhiker.com/

W3.Hitchhiker 官方推特:https://twitter.com/HitchhikerW3

Subscribe to W3.Hitchhiker
Receive the latest updates directly to your inbox.
Mint this entry as an NFT to add it to your collection.
Verification
This entry has been permanently stored onchain and signed by its creator.