zkRollup

0 / 115

zkRollup 介绍 原理篇

17 年出现了一款非常火爆的 Dapp 应用叫加密猫,加密猫曾造成以太坊主网大规模的拥堵,造成拥堵的原因是以太坊当时的 TPS 只有 15,这意味着以太坊每秒只能处理 15 笔交易,如此低的 TPS 严重限制了区块链应用的大规模落地,所以有人开始研究区块链扩容的问题,目的就是为了提高链上的 TPS。但区块链扩容受到 Vitalik 提出的不可能三角的限制,不可能三角是指区块链系统设计无法同时兼顾可扩展性,去中心化和安全性,三者只能取其二。这是一个很让人失望的结论,但我们必须知道,一切事物都有自己的边界,公链不应该做所有的事情,公链应该做它该做的事情:“公链是以最高效率达成共识的工具,能够以最低成本来构建信任”。作为共识的工具,信任的引擎,公链不应该为了可扩展性放弃去中心化与安全性。那么公链的 TPS 这么低,该怎么使用呢?我们是否可以将大量的工作放到链下去解决,仅仅将最重要的数据提交到区块链主链上,让所有节点都能够验证这些链下的工作都是准确可靠的呢?社会的发展带来的是更精细化的分工,区块链的技术发展也是如此,在底层区块链(Layer1)上构建一个扩展层(Layer2),Layer1 来保证安全和去中心化,绝对可靠、可信;它能做到全球共识,并作为“加密法院”,通过智能合约设计的规则进行仲裁,以经济激励的形式将信任传递到 Layer2 上,而 Layer2 追求极致的性能,它只能做到局部共识,但是能够满足各类商业场景的需求。

zkRollup 是什么

zkRollup 就是基于零知识证明的二层扩容方案(layer2), zkRollup 方案起源于 18 年下半年,由 Barry Whitehat 和 Vitalik 先后提出。Rollup 顾名思义有“卷起”和“汇总”的意思,将大量的交易“卷起/汇总”打包成一个交易,zkRollup 的原理一句话就可以讲清楚:链下进行复杂的计算和证明的生成,链上进行证明的校验并存储部分数据保证数据可用性。

zkRollup 数据可用性可以让任何人都能根据链上存储的交易数据,还原出账户的全局状态,从而消除由于数据可用性带来的安全风险(这里的数据可用性对比 Plasma,Plasma 之所以不能称为主流的扩容方案,在于 Plasma 的数据并没有提交到链上,所以在 Plasma 上退出一笔资产的周期会长达一周左右(争议期),如果在争议期间没有人提交欺诈证明,那么资产才可以安全退出到主链)

zkRollup 工作原理

zkRollup 在链下利用 Merkle tree 存储账户状态,由 Operator 收集用户的交易,交易收集完成后 Operator 会执行每个交易(校验余额,校验 nonce,校验签名,执行状态转换),当交易执行完成后会产生一个新的 Merkle tree Root,为了证明链下状态转移是正确的,Operator 会在交易执行完成后生成一个零知识证明的 proof。

下图表示 Operator 工作过程,黄色的表示用户发送的交易,绿色的表示 Operator 中维护的 merkle tree,Operator 执行交易后本地的 merkle tree root 会由 prev state root 转换成 post state root,图中蓝色的表示 Operator 生成证明账户状态转移有效的零知识证明。

zkRollup 介绍 原理篇

Operator 把 prev state root,post state root,交易数据和 proof 证明提交至链上合约,合约校验 proof 通过后会将来新的状态写入到链上,合约不需要单独校验每笔交易的合法性,只需要校验 proof 是否有效,降低了链上 gas 消耗,其中交易数据是存储在较便宜的位置 CALLDATA 上。链下每一次的状态转变都需要提供零知识证明,由主链上的合约进行验证,只有验证通过才能更改状态。即每一次状态转变都严格依赖密码学证明。

zkRollup 生成的证明大小(很小),验证时间(很快基本上是常数),不会随着交易数量的增长而变大,所以 zkRollup 可以极大地提高 TPS。影响 zkRollup 链上性能的只有链上 CALLDATA 存储数据的成本,随着以太坊 Istanbul 升级,CALLDATA 使用成本降为原来的 1/4,zkRollup 的性能则获得 4 倍提升,TPS 可达到近 2000 左右。

zkRollup 介绍 原理篇

上链的数据中 prve state root,post state root 与 proof 基本上是不会随着交易增长变化的,只有上图中黄色交易部分会随着交易增长变大,所以为了能在一个区块链中容纳更多的交易,需要对上链的交易进行压缩。zkRollup 使用 merkle tree 来记录地址,这样地址就可以表示成 merkle tree 的索引值,地址数据的大小就从原本的 20 bytes 减少到 3 bytes,在以太坊上金额用 32 个字节 256 位的大整型来表示,这里压缩到 6 个字节,货币最小单位从 wei 变成 Mwei=10^6 wei,手续费压缩到 1 个字节,nonce 压缩到 2 个字节,nonce 的范围 0~65535,也就是说一个账户最多可以发送 65535 笔交易,交易的签名直接删除了,不出现交易中,因为每笔交易的合法性在链下都通过零知识证明的电路约束校验过了。

下图是压缩后 zkRollup 每笔交易数据的格式:

zkRollup 介绍 原理篇

zkRollup 性能

2019 年 12 月 7 号发生的伊斯坦布尔硬分叉中有两个降低在链上执行零知识证明运算 gas 费用的提案:EIP-1108 与 EIP-2028

EIP-1108

下面是引用 EIP-1108 提案中的部分原文:

The elliptic curve arithmetic precompiles are currently overpriced. Re-pricing the precompiles would greatly assist a number of privacy solutions and scaling solutions on Ethereum.

目前,椭圆曲线运算所需的 gas 费用太高,为了帮助隐私方案以及扩容方案在以太坊上的大规模应用,EIP-1108 对椭圆曲线运算的 gas 费用进行了降价。

以下是伊斯坦布尔分叉前后的椭圆曲线运算的 gas 费用对比

zkRollup 介绍 原理篇

ECADD 表示椭圆曲线加法运算,ECMUL 表示椭圆曲线乘法运算,Pairing check 表示椭圆曲线双线性映射运算。

EIP-2028

下面是引用 EIP-2028 提案中的部分原文:

We propose to reduce the gas cost of Calldata (GTXDATANONZERO) from its current value of 68 gas per byte to 16 gas per byte, to be backed by mathematical modeling and empirical estimates. The mathematical model is the one used in the works of Sompolinsky and Zohar [1] and Pass, Seeman and Shelat [2], which relates network security to network delay. We shall (1) evaluate the theoretical impact of lower Calldata gas cost on network delay using this model, (2) validate the model empirically, and (3) base the proposed gas cost on our findings.

EIP-2028 将 calldata 的存储成本从每字节 68 gas 降低到每字节 16 gas,zkRollup 的交易数据是存储在 calldata 上,这意味着我们可以在 calldata 上存储更多的交易数据,极大提高了吞吐率。

现在我们已经了解了 EIP-1108,EIP-2028 两个提案为 zkRollup 扩容带来的好处,下面我们具体分下一下 zkRollup 的 TPS。

当前以太坊主链

· 当前以太坊区块最大的 gas limit 为 10,000,000 gas
· 以太坊是一个最简单交易的 gas 费用为:21,000 gas
· 以太坊每个区块产生的时间为 15s

根据上面的数据,我们可以计算出以太坊主链的最大吞吐量:

· 一个区块中可最多容纳的交易数量:10M / 21k = 476 tx
· 计算 TPS:476 tx / 15s = 32 tx/s

ZkRollup (伊斯坦布尔分叉前)

· 每个交易的大小为:from(3 bytes) + to(3 bytes)+ value(6 bytes)+ fee(1 bytes)+ nonce(2 bytes)= 15 bytes
· 伊斯坦布尔分叉前 calldata 的 gas 为每字节 68 gas,所以给个交易的成本为:15 bytes * 68 gas/byte = 1020 gas
· 零知识证明校验的 gas 费用计算公式为:

zkRollup 介绍 原理篇

ScalarMulGas 表示一个椭圆曲线乘法消耗的 gas,如果涉及到多个椭圆曲线乘法运算那么消耗的 gas 为:n * ScalarMulGas,PairingBaseGas 表示椭圆曲线双线性映射运算基础 gas 费用,PairingPerPointGas 表示每个椭圆曲线双线性映射运算 gas 费用。

在 zkRollup 中零知识证明算法使用的是 groth16,下方是 groth16 校验证明的公式:

zkRollup 介绍 原理篇

e(x,x)表示一个椭圆曲线双线性映射运算,所以在 groth16 校验中一共涉及到 4 次椭圆曲线双线性映射运算。

下表是伊斯坦布尔分叉前椭圆曲线运算消耗的 gas 详情:

zkRollup 介绍 原理篇

80,000 * k + 100,000 中的 k 表示有几个椭圆曲线双线性映射运算,100,000 表示椭圆曲线双线性映射运算基础 gas 费用。

· 计算零知识证明校验 gas 消耗:公式:VerificationGas = n * ScalarMulGas + PairingBaseGas + 4 ∗ PairingPerPointGas,其中:PairingBaseGas = 100,000 gas,PairingPerPointGas=80,000,ScalarMulGas=40,000 ,假设 zkRollup 只涉及到一个 public input,所以 n=1。VerificationGas = 1 * 40,000 + 100,000 + 80,000 * 4 = 460,000 gas

· 计算区块中可用于容纳交易的空间:10,000,000 - 460,000 = 9,540,000 gas
· 计算 zkRollup 单个交易 gas 成本:15 byte * 68 gas/byte = 1020 gas
· 计算单个区块可容纳交易个数:9,540,000 gas / 1020 gas = 9,000 tx
· 计算 TPS:9,000 tx / 15s = 600 tx/s

ZkRollup (伊斯坦布尔分叉后)

每个交易的大小为:from(3 bytes) + to(3 bytes)+ value(6 bytes)+ fee(1 bytes)+ nonce(2 bytes)= 15 bytes

伊斯坦布尔分叉后 calldata 的 gas 为每字节 16 gas,所以给个交易的成本为:15 bytes * 16 gas/byte = 240 gas

zkRollup 介绍 原理篇

· 计算零知识证明校验 gas 消耗:公式:VerificationGas = n * ScalarMulGas + PairingBaseGas + 4 ∗ PairingPerPointGas,其中:PairingBaseGas = 45,000 gas,PairingPerPointGas=34,000,ScalarMulGas=6,000 ,假设 zkRollup 只涉及到一个 public input,所以 n=1。VerificationGas = 1 * 6,000 + 45,000 + 34,000 * 4 = 187,000 gas

· 计算区块中可用于容纳交易的空间:10,000,000 - 187,000 = 9,813,000 gas
· 计算 zkRollup 单个交易 gas 成本:15 byte * 16 gas/byte = 240 gas
· 计算单个区块可容纳交易个数:9,813,000 gas / 240 gas = 40,000 tx
· 计算 TPS:40,000 tx / 15s = 2,666 tx/s

表格对比

从下图可以 zkRollup 吞吐量的提升与单个交易成本降低有直接的关系。

zkRollup 介绍 原理篇

上面我们计算出伊斯坦布尔升级后 zkRollup 的 TPS 可以达到 2,666,但这只是理论值,我们并没有将生成零知识证明的时间计算在里面,实际上生成零知识证明是非常昂贵的事情,通常生成一个包含大量交易的零知识证明需要花费几分钟时间,显然生成零知识证明的时间将是限制 TPS 达到理论值的瓶颈。目前可以通过并行化生成证明,这可以将证明生成时间从几分钟减少到几秒钟。