DLT Interoperability and More ⛓️#13 ⛓️ — zkBridge: Trustless Cross-chain Bridges Made Practical

In this series, we analyze papers on blockchain and interoperability.

This edition covers a recent paper on a zero-knowledge-based cross-chain bridge.

Grey Concrete Bridge on Body of Water Under Blue and White Sky during Daytime by Klas Tauberman

➡️ Title: zkBridge: Trustless Cross-chain Bridges Made Practical
➡️ Authors: Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, Dawn Song

➡️ Paper source: https://arxiv.org/abs/2208.07119

➡️ Background:

This paper presents a bridge that is secured by SNARKs (the authors adopt a succinct non-interactive arguments of knowledge (SNARK) scheme satisfying completeness and knowledge soundness, and not zero-knowledge). Curiosity: just after a few days after this paper was released, and a few weeks after our own, there was yet another bridge hack: this time, the Binance bridge, for a total of around $560M.

The security assumptions of the bridge are 1) the underlying blockchains are secure, i.e., consistent and live, 2) underlying light client protocols and their implementation are secure, 3) there exists at least one honest node in the block header relay network.

Typically smart contracts implementing bridges can invoke a contract to retrieve verified block headers. After that, one can submit a Merkle proof to prove transaction inclusion (for example, that an asset is locked). This enables use cases as bridges. Thus, the light client is the entity that verifies block headers, and the applications using them are decoupled from the bridge. zk-SNARKS are used to prove that a block header is valid, namely because it follows the update rules for block headers. In Ethereum 2.0, the logic for a valid update is described here.

The technical challenges to implementing such a system are multiple. First, the light client update logic needs to be expressed as an arithmetic circuit. The EdDSA signature verification logic needs to be expressed as circuits because verifying the signatures from the light sync committee is necessary. While cheap to verify on CPUs, verifying EdDSA signatures on arithmetic circuits is expensive.

➡️ Contributions:

• The authors propose a bridge whose security relies on cryptographic primitives behind zero-knowledge technology, namely zk-SNARKS (mitigating the required trust assumptions for a bridge).
• The authors propose deVirgo, a distributed zero-knowledge proofs protocol that reduces proof generation time (reducing proof generation time). Essentially, deVirgo explores data parallelism by proving the correctness of N signatures, by dividing the load into N machines. After that, the proof is compressed using a recursive technique. The compressed proof is gas-efficient because it occupies less on-chain storage, therefore, it is cheaper.
• The authors implement two scenarios: a light client from Cosmos to Ethereum (very interesting because, for example, conventional techniques using IBC are known for gas costs to be prohibitively high — for that, other techniques are available), and from Ethereum to BSC.

In this article, we will focus on the first contribution.

➡️ The bridge:

The idea is relatively simple: we have a set of relayers and a set of smart contracts. The relayers obtain block headers from the source chain, compute a proof of correctness (that asserts the new block header is valid), and send them to a smart contract on the target blockchain (the light client — which the authors call the updater contract). Now, there are different ways to do these proofs of correctness —e.g., e a notary signature, a multi-sig, using multi-party computation, or, in this case, zk-SNARKs. The proof is computed off-chain (expensive to calculate) and then sent to this light client contract.

The light client now is responsible for verifying the SNARK proof. Upon right validation, the new block header is accepted and exposed to a third-party contracts that want to use the light client. Bridges can be built on top of this light client, namely with the following logic: 1) we lock an asset on the source chain; 2) the process described above generates a proof that the new block header is X, 3) the light client takes the proof and verifies it. If correct, it exposes a list of updated block headers. The bridge consumes these block headers and basically exposes an interface for users (or parties operated by the bridge) to verify Merkle proofs. Then these proofs are validated against the new block header. If the proof is valid, it means that a transaction locking an asset took place on the source blockchain, and now we can mint tokens as part of the bridging process. This decoupling is powerful because it allows arbitrary cross-chain use cases to be developed, powered by a decentralized bridge.

💪 Strong points:

• The explanation of how such a system works is clear, simple, and in-depth.
• The efficient proof systems for zkBridge are properly formalized, with the specified protocols and proofs.
• A very detailed analysis explicating off-chain and on-chain costs is available.

🤞 Suggestions for improvement:

• The security model should go a bit more in-depth on the liveness considerations: “the sender chain has a light client protocol to enable fast block header verification” — what is fast block header verification? In fact, ideally, the relayer system should be able to generate a SNARK proof in less time than the block production time from the source chain, otherwise, cross-chain latency will be higher. It would be interesting to see the authors explain this trade-off in detail.
• Protocol 1: How to assure enough client diversity in obtaining the block headers (considering that, for example, there might be different valid competing, forking blocks). In this case, which is the block header that the relay accepts as the one to prove valid? In other words, how is finality handled?
• What is the interface of the updater contract? While true that the interface of the updater contract is subsumed by the “light client state”, which is generic for a light client protocol implementation, this paper proposes a bridge, not a light client verification protocol. Therefore, the interfaces of this contract would be important to be known.
• There is no open-source implementation and evaluation, and thus it is not possible to reproduce the study.
• Would be interesting to see a latency and cost comparison with other types of bridges than optimistic (known for having long confirmation times). For example, classic light client solutions.
• The evaluation also does not evaluate the main scope of the paper: the bridge system. The cross-chain throughput, cost, and latency of an asset transfer are not measured.
• “Our prover machine doesn’t need to be highly reliable since proof generation can be interrupted and restart at any time so we choose consumer-grade hardware to be cost-effective.” — I would argue that the prover machine needs to be very reliable, otherwise it could sacrifice the updater contract liveness.

🔥 Points of interest:

• It is said that “incentivize block header relay nodes, provers may be rewarded with fees after validating their proofs”. How would this be realized? Creating a relay consortium with a currency, e.g., blockchain? Introduce yet another token that incentivizes the relayers?
• The light client contract maintains the light client state, namely a list of valid block headers. Those are exposed to other smart contracts for them to implement their use case (e.g., bridge).
• Sections 4 and 5 have the “magic” details of the inner workings of the system.
• The authors state “our implementation can handle 1 second block time in Cosmos with 120+ capable relayers in the network.”. I wonder if these 120 relayers are producing proofs in parallel?
• It is possible to balance operational cost with expected latency: if the light client provides updates in shorter intervals, the latency for the availability of block headers will be lower, but the cost higher (because more updates per unit of time need to be done).
• Not a limitation of this paper, but rather of this solution type: off-chain cost in terms of electricity/hardware is very high: somewhere from $5,000 to around $8,000 per month.
• Not clear to me: is the bridge compatible with post-merge Ethereum?

🚀 How does it relate to our work at Técnico Lisboa, INESC-ID, and Blockdaemon? (views are my own and do not necessarily reflect the opinions of my employer)

• Enabling secure, scalable interoperability is an important part of what we do at Blockdaemon. Studying cross-chain bridge implementations allows a better understanding of the technology.

🚀 What are the implications for our work?

• This work helps us build more secure blockchain interoperability middleware.