0%

zkRollup介绍 原理篇

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

zkRollup是什么

zkRollup就是基于零知识证明的二层扩容方案(layer2), zkRollup方案起源于18年下半年,由Barry WhitehatVitalik先后提出。Rollup顾名思义有“卷起”和“汇总”的意思,将大量的交易“卷起/汇总”打包成一个交易,zkRollup的原理一句话就可以讲清楚:链下进行复杂的计算和证明的生成,链上进行证明的校验并存储部分数据保证数据可用性。zkRollup数据可用性可以让任何人都能根据链上存储的交易数据,还原出账户的全局状态,从而消除由于数据可用性带来的安全风险(这里的数据可用性对比PlasmaPlasma之所以不能称为主流的扩容方案,在于Plasma的数据并没有提交到链上,所以在Plasma上退出一笔资产的周期会长达一周左右(争议期),如果在争议期间没有人提交欺诈证明,那么资产才可以安全退出到主链)

zkRollup工作原理

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

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

img

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

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

img

上链的数据中prve state rootpost state rootproof基本上是不会随着交易增长变化的,只有上图中黄色交易部分会随着交易增长变大,所以为了能在一个区块链中容纳更多的交易,需要对上链的交易进行压缩。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每笔交易数据的格式:

img

zkRollup性能

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

Contract Address Current Gas Cost Updated Gas Cost
ECADD 0x06 500 150
ECMUL 0x07 40,000 6,000
Pairing check 0x08 80,000 * k + 100,000 34,000 * k + 45,000

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-2028calldata的存储成本从每字节68 gas降低到每字节16 gaszkRollup的交易数据是存储在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费用计算公式为:

\[ \begin{aligned} VerificationGas = n & * ScalarMulGas \\ + & PairingBaseGas \\ + & 4 ∗ PairingPerPointGas \\ \end{aligned} \]

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

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

\[ [A]_1 \cdot [B]_2=[\alpha]_1 \cdot [\beta]_2 + \displaystyle \sum ^l _{i=0} a_i \lbrack \frac{\beta u_i(x) + \alpha v_i(x) + w_i(x)}{\gamma} \rbrack _1 \cdot \gamma _2 + [C]_1 \cdot [\delta]_2 \]

\[ \Downarrow \]

\[ e(\pi_A , \pi_B ) = e(\alpha, \beta) ⋅ e(pub, \gamma) ⋅ e(\pi_c , \delta) \]

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

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

Contract Address 伊斯坦布尔分叉前
ECADD 0x06 500
ECMUL 0x07 40,000
Pairing check 0x08 80,000 * k + 100,000

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

  • 计算零知识证明校验gas消耗:公式:VerificationGas = n * ScalarMulGas + PairingBaseGas + 4 ∗ PairingPerPointGas,其中:PairingBaseGas = 100,000 gasPairingPerPointGas=80,000ScalarMulGas=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
Contract Address 伊斯坦布尔分叉后
ECADD 0x06 150
ECMUL 0x07 6,000
Pairing check 0x08 34,000 * k + 45,000
  • 计算零知识证明校验gas消耗:公式:VerificationGas = n * ScalarMulGas + PairingBaseGas + 4 ∗ PairingPerPointGas,其中:PairingBaseGas = 45,000 gasPairingPerPointGas=34,000ScalarMulGas=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吞吐量的提升与单个交易成本降低有直接的关系。

Blockchain 单个交易gas成本 单个区块最大交易数量 TPS
主链 21,000 476 32
zkRollup(分叉前) 1,020 9,000 600
zkRollup(分叉后) 240 40,000 2,666

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