zkBridge

zkBridge: Trustless Cross-chain Bridges Made Practical

当今时间，多种多样的区块链出现在人们的视野。多链世界的核心挑战是如何实现安全的跨链桥接，使不同区块链上的应用可以通过这些桥接进行通信。

区块链$C_1$和$C_2$之间桥梁的核心功能是向$C_2$上的应用程序证明某个事件发生在$C_1$上，反之亦然。

问题所在，虽然在实践中已经建立了跨链桥，但现有的解决方案要么性能不佳，要么依赖于中心方。

桥的运行取决于两个链的共识协议。如果$C_1$运行的是工作证明（Proof-of-Work），具体来说，$C_2$上的智能合约（用$SC_2$表示）将跟踪$C_1$的区块头，根据这些区块头，可以用 Merkle 证明来验证交易的包含（和其他事件）。但是，这种方法会产生巨大的计算和存储开销，因为$SC_2$需要验证所有区块头，并保存一个不断增长的冗长列表。

作为一种高效的替代方案，许多桥接协议
(PolyNetwork、Wormhole、Ronin 等）都采用了基于信任中介（Trust In­ter­me­di­ary）的方法，所使用的技术包括侧链（PolyNetwork），跨链委员会（Ronin），预言机（LayerZero）

Wormhole：https://docs.wormhole.com/wormhole/explore-wormhole/security

Poly Network：https://learnblockchain.cn/article/3300

此类方式需要有比较强的信任假设，也即假设跨链桥的结点有至少 2/3 是可信的，委员会中有至少 2/3 是可信的。

但是这种方式容易遭受到恶意的攻击。

为了降低对中介的信任依赖，一个比较简单的方式是不让中介传输数据，而是让中介对数据进行签名，之后由接受数据的链对签名进行验证即可

这个思路有点类似于轻量级客户端验证，只要客户端验证并持续追踪验证状态即可

举个例子，Cos­mos IBC 是一个用于 Cos­mos 链的跨链协议，这个协议会验证来自其他链的数据的区块首部，从而完成跨链数据的验证，不过此类方式也存在缺点，需要跨链的接收方部署这个 IBC 协议来完成数据验证（比如以太坊没有部署这个东西，就无法支持跨链）

或者向 NEAR Rain­bow bridge 那样的做法，将其以智能合约的形式部署于以太坊来支持跨链，但是这会导致链上验证的开销非常大

为了在消除中介的同时提供足够强的安全性，这里可以引入 ZKP 技术，主要思想和很多去中心化的协议类似，将对可信机构的信任转移至对密码学假设的依赖。

zkBridge 可以实现高效的跨链桥接，而无需信任中央委员会。其主要思想是利用 zk-SNARK，即简洁的非交互式知识证明（论证）

zk-SNARK能让证明者有效地让$SC_2$相信，在$C_1$上发生了某种状态转换。为此，$SC_2$将跟踪$SC_1$最新提示的摘要$D$。要使$SC_2$与$C_1$中的新区块同步，任何人都可以生成并提交 zk-SNARK，向$SC_2$证明$C_1$的顶端已经从 $D$推进到$D^\prime$。

好处：

zk-SNARK 的健全性确保了桥梁的安全性。除了底层区块链的安全性外，我们不需要额外的安全性要求。

通过专门构建的 zk-SNARK，$C_2$可以验证$C_1$的状态转换，远比在$SC_2$中编码$C_1$的共识逻辑更有效。

要使用 zk-SNARK 证明给定计算结果的正确性，首先需要将计算表达为算术电路。

虽然 zk-SNARK 验证速度很快（与电路的大小成对数关系，甚至是常数），但证明生成时间至少是线性的，而且在实践中可能昂贵得令人望而却步。

此外，现实世界中区块链使用的组件并不容易用算术电路来表示。例如，广泛使用的 EdDSA 数字签名方案在 CPU 上的验证效率很高，但要用算术电路表示却很昂贵，需要 200 多万个门。在跨链桥中，根据链的不同，每个状态转换可能需要验证数百个签名，这使得生成所需的 zk-SNARK 证明的成本过高。

因此，为了使 zkBridge 实用化，我们必须缩短证明生成时间。

我们发现跨链桥所使用的电路是数据并行的，因为它们包含一个较小的子电路的多个相同副本。具体来说，用于验证$N$数字签名的电路包含签名验证子电路的$N$个副本。因此，本文提出一种基于Virgo的分布式协议，deVirgo，如果证明生成分布在$M$台机器上，生成时间可减少$M$倍。

虽然 deVirgo 大大缩短了证明生成时间，但在链上验证 deVirgo 证明（尤其是 zkBridge 中的十亿门电路）对于计算资源极其有限的智能合约来说可能是昂贵的。

为了压缩证明大小和验证成本，本文使用 Groth 提出的经典 zk-SNARK 递归证明（可能很大）deVirgo 证明的正确性，以下简称 Groth16。Groth16 校验器能输出恒定大小的证明，EVM 区块链上的智能合约可以快速验证这些证明。我们强调，不能使用 Groth16 生成整个 zkBridge 证明，因为 zkBridge 所需的电路对于 Groth16 验证器来说太大了。

相反，我们使用 Groth16 压缩 deVirgo 证明的方法却能提供两全其美的效果：快速的 deVirgo 并行证明器可生成大部分证明，而生成的证明则被压缩为简洁的 Groth16 证明，可快速验证。

为了证明zkBridge的实用性，我们在Cosmos和以太坊之间实现了zkBridge的端到端原型，包括deVirgo和递归验证协议，以及交易中继应用。

Notation

$F$：有限域

$\lambda$：安全参数

$f(),h()$：多项式表达式

$x,y$：单一变量

$\vec{x},\vec{y}$：变量向量

$\vec{x}[i],\vec{x}[i:k]=(x_i,x_{i+1},...,x_k)$

Merkle Tree:

• $rt\leftarrow MT.Commit(\vec{x})$
• $(\vec{x}[i],\pi_i)\leftarrow MT.Open(\vec{x},i)$
• $\{1,0\}\leftarrow MT.Verify(\pi_i,\vec{x}[i],rt)$

$blk=\{blkh;trx_1,...,trx_t\}$：区块

$LOG_r^i=[blk_1,...,blk_r]$：账本，$r$是高度，$blk_{k\cdot ptr}=blkH_{k-1}$

一致性：对于诚实的节点$i,j$，一定有$LOG_i^{r_0}$是$LOG_j^{r_1}$的前缀。

有效性：如果一个诚实节点在某一轮 $r$ 收到了某笔交易$trx$，那么$trx$最终会被包含到所有诚实节点的区块链中。

$LightCC(LCS_{r-1},blkH_{r-1},blkH_r)\rightarrow \{true,false\}$：轻客户端的区块验证规则，其中$blkH_r$表示新的区块头，$blkH_{r-1}$旧的区块头，$LCS_{r-1}$当前的状态

**零知识证明：**当$\lambda$作为安全参数，$R$是一种$NP$关系，算法$(\mathcal{G,P,V})$对于$R$来说是零知识的，当其满足：

• Completeness：对于$\mathcal{G}(1^\lambda)$产生的参数$pp$，$(x;w)\in \mathcal{R},\pi\leftarrow \mathcal{P}(x,w,pp)$：

$Pr[\mathcal{V}(x,\pi,pp)=1]=1$

• Knowledge Soundness：对于PPT的证明者$\mathcal{P}^*$，存在一个PPT模拟器$\mathcal{E}$和辅助字符串$z$.$pp\leftarrow \mathcal{G}(1^\lambda),\pi^* \leftarrow P^*(x,z,pp),w,\mathcal{E}^{P^*(\cdot)}(x,z,pp)$：

Pr[(x;w)\notin R \and \mathcal{V}(x,\pi^*,pp)=1]\le negl(\lambda)

• Zero knowledge：存在一个PPT模拟器$S$对于PPT算法$\mathcal{V}^*$，$(x,w)\in \mathcal{R},pp\leftarrow \mathcal{G}(1^\lambda)$

$View(\mathcal{V}^*(pp,x))\approx \mathcal{S}^{\mathcal{V}^*}(x)$

我们说$(\mathcal{G,P,V})$是简洁的，当$\mathcal{P,V}$之间的总开销（证明大小）以及$\mathcal{V}$的运行时间，是$poly(\lambda,|x|,log|\mathcal{R}|)$的，其中$|R|$是电路的大小

zkBridge

注意：zkBridge两个方向的操作是一致的。

Overview

为了让不同的应用程序都能轻松地与 zkBridge 集成，我们采用了模块化设计，将特定于应用程序的逻辑（如验证智能合约状态）与核心桥接功能（即转发区块头）分离开来。

如图显示了zkBridge的架构和工作流程。核心桥接功能由一个区块头中继网络（仅在有效性方面受信任）提供，$\mathcal{C}_1$的中继块头提供正确性证明，$\mathcal{C}_2$的更新器合约验证和接收证明。

更新器合约维护最新的区块头列表，并在验证中继节点提交的证明后对其进行适当更新；它公开了一个简单且与应用程序无关的应用程序接口，应用程序智能合约可以从中获取发送方区块链的最新区块头，并在此基础上构建特定于应用程序的逻辑。

依赖于 zkBridge 的应用程序通常会在$\mathcal{C}_1$和$\mathcal{C}_2$上分别部署一对合约，即发送方合约和接收方合约。我们把它们统称为应用合约或依赖合约。接收者合约可以调用更新器合约来获取$\mathcal{C}_1$的块头，并在此基础上执行特定的应用任务。根据应用的不同，接收方合约可能还需要用户或第三方提供特定应用的证明，如智能合约状态的 Merkle 证明。

如图展示了跨链代币转移的工作流程。

假设用户$\mathcal{u}$想要在另一个区块链$\mathcal{C}_2$上的交易所交易她在$\mathcal{C}_1$的资产，即将资金从$\mathcal{C}_1$转移到$\mathcal{C}_2$上。

一对智能合约$SC_{lock}$和$SC_{mint}$分别部署在区块链$C_1$和$C_2$上。

为了转移资金，用户将 $v 代币锁定在$SC_{lock}$（图 1 中的步骤 1），然后请求$SC_{mint}$发行 $v 代币。

$SC_{mint}$只应在且仅在用户已锁定$C_1$上的代币时才发行新代币。这要求$SC_{mint}$从不同的区块链读取$SC_{lock}$的状态（$\mathcal{U}$的余额，在步骤 2 中更新），但它不能直接这样做。

zkBridge 通过将$C_1$的区块头和证明一起转发给$C_2$来实现这一点（步骤 3 和 4）。

$SC_{mint}$可以从智能合约前端（更新合约）获取区块头，检查用户$\mathcal{U}$的余额是否确实为 $v（步骤 5 ），然后能铸造 $v 代币（步骤 6 ）。

除了跨链代币转移，zkBridge 还能实现其他各种应用，如跨链抵押贷款、一般消息传递等。

detail

security and system model

为了建模桥，我们将区块链$\mathcal{C}$建模为区块编号索引的键值存储，表示为$\mathcal{C}[t]:\mathcal{K}\rightarrow \mathcal{V}$其中$t$是区块编号，$\mathcal{K}$和 $\mathcal{V}$分别是键和值空间。

例如，以太坊中，$\mathcal{V}=\{0,1\}^{256}$（每个地址存储32字节的值），密钥是智能合约标识符$\mathcal{SC}$和每个智能合约存储地址$\mathcal{K}$的连接。对于一个给定的合约$\mathcal{SC}$，我们将存储在地址$\mathcal{K}$区块编号$t$的值记作$\mathcal{SC}[t,\mathcal{K}]$，将$\mathcal{SC}[t,\cdot]$叫做$\mathcal{SC}$在区块编号为$t$的状态

我们关注于从$\mathcal{SC}_1$到$\mathcal{SC}_2$，记作$\mathcal{BR}[\mathcal{SC}_1\rightarrow \mathcal{SC}_2]$

Functional and security goals

我们要求桥$\mathcal{BR}[\mathcal{SC}_1\rightarrow \mathcal{SC}_2]$正确及时地反映$\mathcal{SC}_1$的状态：

正确性： 对于所有$t,\mathcal{K}$，$\mathcal{SC}_2$接受错误状态$\mathcal{V}\ne \mathcal{SC}_1[t,\mathcal{K}]$的概率可忽略不计。

有效性： 假设$\mathcal{SC}_2$需要验证$SC_1$在$(t,K)$处的状态，桥最终会提供必要的信息。

Security assumptions

为了保证正确性，除了底层区块链的信任假设外，zkBridge 没有引入额外的信任假设。也就是说，我们假设发送方区块链和接收方区块链都是一致的和有效的（第 2 节），并且发送方链有一个轻客户端协议，可以快速验证区块头。对于这两个特性，我们假设中继网络中至少有一个诚实节点，并且所使用的 zk-SNARK 是可靠的。

construction

如第 3 节所述，桥接器$\mathcal{BR}[\mathcal{SC}_1\rightarrow \mathcal{SC}_2]$由三个部分组成：区块头中继网络、更新合约和一个或多个应用合约。下面我们将说明每个组件的协议。

区块头中继网络：

块标头中继网络中的节点以更新合约的当前状态（$LCS_{r-1},blkH_{r-1}$）为输入，运行 RelayNextHeader。

中继节点连接到$C_1$中的全节点，并获得继$blkH_{r-1}$之后的块头$blkH_r$。中继节点生成一个 ZKP $\pi$，显示$blkH_r$的正确性，主要证明$blkH_r$在块$blkH_{r-1}$之后被$C_1$的轻客户端接受。

它将 ($\pi,blkH_r$) 发送给$C_2$上的更新合约。

为了避免因碰撞而浪费证明时间（注意，当多个中继节点同时发送时，只能接受一个证明），中继节点可以使用标准技术进行协调（例如，以循环方式发送）。

为了激励区块头中继节点，证明者可以在验证其证明后获得费用奖励。激励机制的设计留待今后研究。

我们注意到，这种设计依赖于发送者链的轻客户端验证器的安全性。例如，轻客户端验证器必须拒绝最终可能成为孤儿且不属于发件人链的有效块头。

更新者合约

更新器合约维护轻客户端的内部状态，包括 headerDAG 中$C_1$的区块头列表。它有两个公开暴露的函数。HeaderUpdate 函数可以可由任何区块头中继节点调用，并提供下一个区块头和一个证明作为输入。如果证明与当前轻客户端状态 $LCS$ 和 $blkH_{r-1}$ 一致，合约将对轻客户端进行进一步检查，然后相应地更新状态。由于该函数的调用者必须支付一定费用，因此自然可以防止$DoS$攻击。

接收合约可调用 GetHeader 函数来获取高度为 $t$ 的区块头。接收方合约可以使用获得的区块头完成特定应用验证，可能需要用户或第三方的帮助。

zkBridge 采用模块化设计，更新合约与应用程序无关。因此，在$\mathcal{BR}[\mathcal{SC}_1\rightarrow \mathcal{SC}_2]$中，由应用合约$SC_1$和$SC_2$决定桥接的信息是什么。一般来说，证明$SC_1[t,K]=V$的过程非常简单：$SC_2$可以请求获得与地址$K$对应的状态 Trie Tree 的叶子（位于区块编号 𝑡）的 Merkle 证明。接收方合约可以通过调用函数 $GetHeader(t)$，从更新方合约中获取$blkH_t$。然后，它可以根据$blkH_t$中的 Merkle 根验证$SC_1[t,K]=V$

下面的定理说明了 zkBridge 的安全性。
由协议 1 和 2 实现的桥$\mathcal{BR}[\mathcal{SC}_1\rightarrow \mathcal{SC}_2]$同时满足一致性和有效性，假设以下条件成立：

1. 在区块头中继网络中至少有一个诚实节点；
2. 发送方链是一致和有效的；
3. 发送方链有一个定义 2.1 中的轻客户端验证器；以及
4. 简洁证明系统是健全的。

Application cases

Transaction inclusion: a building block

跨链应用的一个常见构件是验证另一个区块链上的交易包含性。

具体来说，目的是使$C_2$上的接收方合约$SC_2$能够验证给定的交易$trx$已包含在高度为$t$的$C_1$上的区块$B_t$中。为此，接收方合约$SC_2$需要用户或第三方服务为$B_t$中的$trx$提供 Merkle 证明。然后，$SC_2$将调用更新器合约，检索高度为$t$的$C_1$的区块头，然后根据头中包含的 Merkle 根验证所提供的 Merkle 证明。

消息传递和数据分享

跨链消息传递是另一种常见的构建模块，可用于跨区块链共享链外数据等。消息传递可以通过在交易中嵌入消息，作为交易包含的简单扩展来实现。具体来说，要将$C_1$的消息$m$传递到$C_2$，用户可以将$m$嵌入事务$trx_m$，将$trx_m$发送到$C_1$，然后执行上述事务包含证明。

跨链交换资产

在此应用中，用户可以在发送方区块链$C_1$上注入一定数量的代币$T_A$，并在接收方区块链$C_2$上获得相同数量的代币$T_A$（如果符合条件，用于原生资产转移）或一定数量的价值大致相同的代币$T_B$（用于原生资产交换）。

首先，开发者会在$C_1$上部署一个锁合约$SC_{lock}$，在$SC$上部署一个合约$SC_{mint}$。如果用户想将$n_A$的代币$T_A$换成等值的代币$T_B$。

她将首先发送一个交易$trx_{lock}$，将$n_A$的代币$T_A$转移到$SC_{lock}$，同时发送一个地址$addr_{C_2}$，以便在$C_2$上接收代币$T_B$。在区块$B$中确认$trx_{lock}$后，用户将向$SC_{mint}$发送交易$trx_{mint}$，其中包括足够的信息来验证是否包含$trx_{lock}$。根据$trx_{mint}$中的信息，$SC_{mint}$将验证$C_1$上是否包含了$trx_{lock}$，并将相应的$T_B$代币转移到$trx_{lock}$中指定的地址$addr_{C_2}$上。

最后，$SC_{mint}$将标记$trx_{lock}$为铸币，以完成转账。

NFT的互操作

在不可兑换代币（NFT）的互操作应用中，用户总是在发送方区块链上锁定/标记 NFT，并在接收方区块链上获得铸币的 NFT 或 NFT 衍生物。通过设计 NFT 衍生物，跨链协议可以在两个区块链系统上分离 NFT 的所有权和效用，从而支持在发送方区块链上锁定 NFT 的所有权，在接收方区块链上获取效用。

efficient proof systems for zkBridge

当发送链和接收链使用不同的加密实现时，开销的一个主要来源是不同椭圆曲线之间的字段转换，这在实践中很常见。

为了使 zkBridge 实用化，我们提出了两个想法。

利用 deVirgo 缩短证明时间。我们发现，用于验证多个签名的 ZKP 电路由一个子电路的多个副本组成。我们的第一个想法是利用这一特殊结构，在多个服务器之间分布式生成证明。我们提出了一种名为 deVirgo 的新型分布式 ZKP 协议。

通过递归验证降低链上成本。虽然在普通 CPU 上验证 deVirgo 证明非常高效，但链上验证的成本仍然很高。为了进一步降低链上验证成本（计算和存储），我们使用递归验证：证明者递归地证明正确的证明。
证明者使用对智能合约友好的零知识协议递归证明一个（可能很大的）Virgo 证明的正确性，从而得到一个小的、验证者效率高的证明。

Distributed Proof Generation

快速验证时间的机会来自于验证$N$签名的电路由相同子电路的$N$副本组成这一事实。这种电路被称为数据并行电路

我们选择 Virgo 作为底层 ZKP 协议有两个原因：

• Virgo 不需要可信设置，而且是可信的后量子安全协议。

• Virgo 是最快的协议之一，验证时间简洁，证明规模简洁，可解决大规模问题。.

我们为数据并行算术电路提出了一种新的分布式 Virgo 版本，它能在证明大小不增加任何开销的情况下实现最佳可扩展性。具体地说，在使用$N$台并行机器、具有$N$个副本的数据并行电路上，我们的 deVirgo 协议比原始 Virgo 快$N$倍，而证明大小保持不变。我们的方案具有独立的意义，可以用于其他基于 Virgo 的系统，以提高效率。

假设证明者总共有$N$台机器，标记范围从$P_0$到$P_{N-1}$。

假设$P_0$是主节点，其他机器是普通节点。假设$v$是验证器。

给定一个由$N$个相同结构组成的数据并行算术电路，分布式 Virgo 的简单算法是将每个子电路分配给一个单独的节点。然后，每个节点分别运行 Virgo 生成证明。𝑁 证明的合并即为最终证明。

遗憾的是，这种天真算法的证明大小与子电路的数量成线性关系，这对于具有许多子副本的数据并行电路来说，可能大得令人望而却步。

为了解决这个问题，我们的方法通过在分布式机器之间聚合信息和证明，消除了证明大小中的$N$附加因子。具体来说，Virgo 的原始协议由两个主要构件组成。一个是 GKR 协议 [53]，它由深度为$d$的电路的sumcheck 协议组成。另一个是多项式承诺（PC）方案。我们分别为求和检查和多项式承诺 (PC) 设计了分布式方案。

在我们的分布式 sumcheck 协议中，主节点$P_0$会汇总来自所有机器的信息，然后在每一轮将汇总后的信息发送给 $v$，而不是直接将来自所有机器的信息发送给 𝒱。我们的分布式 sumcheck 协议与原始 sumcheck 协议的证明大小完全相同，因此比原始分布式协议节省了$N$倍。此外，在我们的分布式 PC 协议中，我们优化了承诺阶段，让$P_0$将$N$个承诺聚合成一个，而不是直接将$N$个承诺发送给$v$。在开局阶段，证明也可以聚合在一起，这样就能以多项式大小的对数因子来改善证明的大小。