zkBridge: Trustless Cross-chain Bridges Made Practical

Tiancheng Xie · Jiaheng Zhang · Zerui Cheng · Fan Zhang · Yupeng Zhang · Yongzheng Jia · Dan Boneh · Dawn Song  |  https://arxiv.org/pdf/2210.00264.pdf  |  ACM Conference on Computer and Communications Security (CCS) 2022  |  Follow us on Twitter: @zkcollective

Blockchain ecosystem has seen growing heterogeneity where a variety of blockchains co-exist. And cross-chain bridge is a necessary and critical building block in this multi-chain ecosystem. Existing solutions, however, rely on strong trust assumptions that significantly lower the security. Recurring attacks against bridges have cost users more than 1.5 billion USD to date.

In this paper, we present zkBridge, the first trustless, permissionless, extensible, universal, and efficient cross-chain bridge. With succinct proofs, zkBridge not only guarantees strong security without external assumptions, but also significantly reduces on-chain verification cost. We propose novel succinct proof protocols that are orders-of-magnitude faster than existing solutions for workload in zkBridge. With a modular design, zkBridge enables a broad spectrum of applications, including message passing, token transferring, and other computational logic operating on state changes from different chains. We have already implemented zkBridge between certain chains and evaluated its end-to-end performance.

We encourage community members to join us to extend zkBridge to other chains; please fill in the form if you are interested in contributing to this project towards building a universal, secure foundation for multi-chain interoperability.

Our Advantages Compared with Other Cross-chain Bridges

Cross-chain bridges enable secure and efficient communication between two blockchains.
It has been widely acknowledged that the blockchain ecosystem will get into a multi-chain future.
Thus cross-chain bridges are extremely critical for multi-chain interoperability.

There are quite a few cross-chain bridge projects deployed today.
However, most of them suffer from either inefficiency or poor security.
Till the time of writing (Sep 2022), more than $1.5 billion has been stolen by attackers from bridges.

Compared with existing cross-chain bridge projects, the overall advantages of zkBridge can be summarized as follows:

1. Trustless and Secure

The correctness of block headers on remote blockchains is proven by zk-SNARKs,
and thus no external trust assumptions are introduced.
Indeed, as long as the connected blockchains and the underlying light-client protocols are secure,
and there exists at least one honest node in the block header relay network, zkBridge is secure.

2. Permissionless and Decentralized

Any node can freely join the network to relay the block headers, generate proofs, and claim the rewards.
Due to the elimination of the commonly-used central or Proof-of-Stake style committee for block header validation,
zkBridge also enjoys better decentralization.

3. Extensible

zkBridge allows maximum extensibility,
in that applications can invoke the updater contract to retrieve verified block headers,
and then perform their application-specific verification and functionality in addition for wider usage.
(e.g., verifying a transaction through auxiliary Merkle proof)
By separating the bridge from application-specific logic,
zkBridge makes it easy to enable additional applications on top of the bridge.

4. Universal

The block header relay network and the underlying proof scheme in zkBridge is universal
as long as the blockchain supports a light client protocol to synchronize the block headers of the state of the blockchain.

5. Efficient

With our highly optimized recursive proof scheme,
block headers can be relayed within a short time (usually tens of seconds for proof generation),
and the relayed information can be quickly finalized as long as the proof is verified,
thus supporting fast and flexible processing on information of remote blockchains.

In summary, our completely new design is a huge leap towards building a secure, trustless foundation for blockchain interoperability.

Design Rationale and the Underlying Proof System

In the following, we introduce the design rationale and our highly optimized proof system of zkBridge in more detail.

zkBridge Protocol

Concretely, zkBridge consists of the following components: a block header relay network and an updater contract. In the block header relay network, relayers retrieve the block headers from the sender blockchain C1, generate proofs of validity of the block headers, and send the headers along with the proofs to the updater contract which is set up on the receiver blockchain C2. For the updater contract, the corresponding block headers of C1 are stored once the associated proofs pass the verification. Furthermore, the updater contract also maintains a light-client state. Once a new block header is added, the contract renews the light-client state just like other light clients on C1, and updates the current main chain of C1. The updater contract also exposes a function to applications, through which an application on C2 can obtain the block header of a given height on C1. After getting the block header information, the application can do more verification (such as a specific transaction) and build their own applications.

deVirgo and Recursive Proof

To make the underlying zk-SNARK system compatible with on-chain usage, both fast proof generation and low on-chain proof verification cost are required. We use a 2-layer recursive proof system to satisfy both properties . In the first layer, we present deVirgo, a distributed version of the Virgo proof system. deVirgo combines distributed sumcheck and distributed polynomial commitment to achieve optimal parallelism, and is able to accelerate the proof generation by orders of magnitude when running on distributed machines. However, the verification cost of deVirgo proof on-chain is still too high to be put into practice, and thus we apply recursive proof as a second layer to address the issue. In the second layer, we use Groth16 to prove that the previously generated proof by deVirgo indeed proves the corresponding block headers, which significantly reduces on-chain verification gas cost from ~80M to ~227K. Through the 2-layer recursive proof scheme, we perfectly achieve fast proof generation and low verification cost at the same time.

Future of zkBridge

We have already implemented zkBridge between certain chains.
Given the trustless and full decentralization nature of zkBridge,
we encourage community members to join us to extend zkBridge to other chains,
and make it a universal, secure foundation for multi-chain interoperability.
If you are interested in contributing, please fill in the form,
and we'll follow up to contact you for later steps.

Should you have further questions, welcome to email us at zkbridgeproj@gmail.com.