Source-linked AI summary
zkBridge: Trustless Cross-chain Bridges Made Practical
Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, Dan Boneh, Dawn Song
TL;DR
Existing cross-chain bridges face performance limitations or committee-based trust assumptions, motivating a secure and efficient alternative for heterogeneous blockchain ecosystems. zkBridge combines succinct proofs, distributed proof generation, recursive verification, and modular bridge logic, and its prototypes demonstrate sub-20-second proof generation with less than 230K gas for on-chain verification.
Problem
Cross-chain bridges must connect heterogeneous blockchains, but existing solutions either have performance issues or rely on committee trust assumptions that weaken security.
Method
zkBridge uses sound zk-SNARKs, purpose-built succinct proof protocols including data-parallel deVirgo, recursive verification, and modular separation of bridging from application logic.
Results
Less than 20 seconds: zkBridge generates proofs for its Cosmos-to-Ethereum prototype, while on-chain verification costs less than 230K gas.
Takeaways & Limitations
zkBridge provides a practical bridge design that avoids additional trust assumptions beyond the underlying blockchains and supports applications built on verified cross-chain state.
Takeaways & Limitations
Incentive design for proof relayers is left for future work, and correctness assumes consistent, live blockchains, a sender-chain light client, an honest relay node, and a sound zk-SNARK.
Abstract
from arXiv · showhide
Blockchains have seen growing traction with cryptocurrencies reaching a market cap of over 1 trillion dollars, major institution investors taking interests, and global impacts on governments, businesses, and individuals. Also growing significantly is the heterogeneity of the ecosystem where a variety of blockchains co-exist. Cross-chain bridge is a necessary building block in this multi-chain ecosystem. Existing solutions, however, either suffer from performance issues or rely on trust assumptions of committees that significantly lower the security. Recurring attacks against bridges have cost users more than 1.5 billion USD. In this paper, we introduce zkBridge, an efficient cross-chain bridge that guarantees strong security without external trust assumptions. With succinct proofs, zkBridge not only guarantees correctness, 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 use cases and capabilities, including message passing, token transferring, and other computational logic operating on state changes from different chains. To demonstrate the practicality of zkBridge, we implemented a prototype bridge from Cosmos to Ethereum, a particularly challenging direction that involves large proof circuits that existing systems cannot efficiently handle. Our evaluation shows that zkBridge achieves practical performance: proof generation takes less than 20 seconds, while verifying proofs on-chain costs less than 230K gas. For completeness, we also implemented and evaluated the direction from Ethereum to other EVM-compatible chains (such as BSC) which involves smaller circuits and incurs much less overhead.
1 INTRODUCTION
zkBridge targets secure, efficient interoperability across heterogeneous blockchains without committee-based trust. It combines modular bridge design with distributed and recursive succinct proofs, achieving practical relay and verification performance.
- The problem: Existing bridges either have poor performance or rely on central parties, while committee-based designs add trust assumptions and can create single-point failures.These limitations complicate downstream security analysis and motivate a trustless alternative.
- Proof systems: Recursive Groth16 proofs reduce Cosmos-to-Ethereum verification cost from ∼80M gas to less than 230K gas.The recursive layer compresses potentially large deVirgo proofs into constant-size proofs suitable for EVM smart contracts.
- Proof systems: deVirgo exploits data-parallel circuits to distribute proof generation across machines with perfect linear scalability.For M machines, proof generation time can be reduced by a factor of M.
- Capabilities: zkBridge separates bridge verification from application logic, supporting permissionless relaying and extensible applications such as message passing and asset transfers.Applications can retrieve verified block headers and perform application-specific checks separately.
2 BACKGROUND
The background defines blockchain, light-client, smart-contract, and succinct-proof concepts needed to understand zkBridge. It emphasizes that consensus verification, computation, and storage can be costly on-chain.
- Blockchain fundamentals: A blockchain is a distributed protocol whose nodes maintain an ordered ledger of blocks containing headers and transactions.Block headers link to prior blocks and include transaction commitments and validity proofs.
- Blockchain fundamentals: Blockchain security is characterized here by consistency across honest nodes and eventual transaction inclusion through liveness.These properties describe agreement on ledger views and eventual processing of received transactions.
- Smart contracts and gas: Smart contracts are stateful, user-defined programs whose persistent state can be viewed as a key-value store.Transactions invoke contracts and may alter their state.
- Smart contracts and gas: On-chain computation and storage are scarce and expensive; verifying one EdDSA signature on Ethereum costs about 500K gas.The passage contrasts this with CPU verification of 71000 EdDSA signatures per second.
- Light clients: Light clients store block headers rather than full blockchain histories, so their verification capabilities depend on the underlying consensus protocol.Bitcoin SPV uses Merkle proofs, while Proof-of-Stake and BFT systems require consensus-specific checks.
- Light clients: A light-client protocol synchronizes blockchain headers with succinct state updates, liveness, and consistency requirements.The abstract validation rule checks whether a new header is a valid successor under the current light-client state.
- Zero-knowledge proofs: A zero-knowledge argument of knowledge lets a prover convince a verifier that a witness satisfies an NP relation while providing completeness, knowledge soundness, and zero knowledge.A succinct argument additionally bounds proof size and verifier runtime by poly(λ, |x|, log|ℛ|).
3 ZKBRIDGE PROTOCOL
zkBridge separates generic cross-chain state verification from application logic and uses succinct proofs to relay block headers without committee-based security. Its modular bridge supports applications such as token transfers while targeting practical verification and proof-generation costs.
- zkBridge models a bridge as a service that securely transfers verifiable state between smart contracts on different blockchains.
- The modular design separates block-header relaying from application-specific logic, allowing receiver contracts to retrieve verified headers and perform their own checks.
- zkBridge relays new sender-chain headers by having relay nodes obtain headers, generate correctness proofs, and submit them to the updater contract.
- In token transfer, users lock tokens on the sender chain, then the receiver contract verifies the corresponding state before minting tokens.
- The bridge’s consistency and liveness rely on an honest relay node, consistent and live chains, a sender-chain light-client verifier, and a sound succinct proof system.
4 DISTRIBUTED PROOF GENERATION
The proof-generation system exploits data-parallel circuits, distributing repeated sub-circuits across machines while aggregating their proofs. deVirgo provides linear prover speedups, and recursive commitments reduce proof-size and verification overhead.
- Data-parallel circuits contain identical sub-circuits without wiring connections across copies, enabling each copy to be processed separately.
- Virgo is chosen because it requires no trusted setup, is plausibly post-quantum secure, and offers fast proving with succinct verification and proofs.
- deVirgo distributes Virgo’s work across machines and achieves N-times faster proving on N parallel machines without increasing proof size.
- Distributed polynomial commitment: The distributed polynomial-commitment protocol aggregates commitments and openings, reducing proof-size overhead while validating multiple evaluations efficiently.
- Distributed sumcheck: The distributed sumcheck protocol assigns sub-circuit work to separate provers, aggregates univariate polynomials, and preserves a proof size of O(ℓ).
- Protocol 8 is complete and knowledge-sound for relations composed of N identical circuit copies, while achieving optimal linear scalability.
5 REDUCING
zkBridge uses two-layer recursive proofs to compress large deVirgo proofs into succinct proofs suitable for on-chain verification. The design exploits data-parallel circuits while keeping recursive verification largely independent of the number of signatures.
- Groth16 recursively proves deVirgo verification, producing a shorter second proof that Ethereum can verify efficiently.
- For N signatures, deVirgo’s data-parallel circuit contains N copies of a signature-verification sub-circuit.
- The verification circuit’s sumcheck component stays constant as copies increase, while the polynomial-commitment component grows sub-linearly.
- Less than 2.3×10^5 gas is required for recursive on-chain verification, compared with an estimated ∼8×10^7 gas without compression.
6 IMPLEMENTATION AND EVALUATION
zkBridge’s evaluation demonstrates practical cross-chain bridging across Cosmos-to-Ethereum and Ethereum-to-EVM-compatible directions, combining distributed proof generation, recursive verification, batching, and light-client operation. The Cosmos-to-Ethereum prototype achieves sub-20-second proof generation, low on-chain verification cost, and measured deployment costs.
- Implementation: zkBridge prototypes bridge Cosmos to Ethereum and Ethereum to EVM-compatible chains, with the former requiring the full protocol and the latter incurring less overhead.The Cosmos-to-Ethereum direction uses deVirgo, while Ethereum-to-EVM-compatible chains do not require it.
- Proof generation: 13.28 seconds: deVirgo generates a correctness proof for a Cosmos header with 128 signatures, versus more than 400 seconds with original Virgo.This corresponds to a reported 30x speedup.
- Proof size: 1.9 MB to 131 bytes: recursive verification reduces proof size by around 14,000x for N=32, with about a 25% increase in prover time.The paper identifies reducing proof size and verification cost as the main benefit of recursive verification.
- On-chain verification: 227K gas: recursive verification makes on-chain verification cost constant, compared with an estimated 78M gas for direct Virgo-proof verification.The recursive proof is 131 bytes and requires three pairings; direct verification exceeds Ethereum’s 30M single-block gas limit.
- Latency: Under 2 minutes: batching delivers zkBridge confirmation latency, including three 32-second block waits and 20 seconds of proof generation.The paper contrasts this with a four-hour challenge window for NEAR’s Rainbow Bridge.
- Cost analysis: $0.02 per block: a Hetzner cloud deployment of 32 machines is estimated at around $8,100 per month, while self-hosting costs about $0.012 per block in electricity.The self-hosted setup requires an estimated $144,000 initial hardware cost and $5,184 monthly electricity cost.
- Cost analysis: Less than $230K gas: efficient batched proofs cost roughly $7.36 per batch, or $0.23 per block for N=32 under the paper’s August 2022 prices.The bulk of batched on-chain verification cost is verifying one Groth16 proof.
- Ethereum-to-EVM evaluation: 10 seconds: a single machine can generate an Ethereum PoW proof because the EthHash circuit has around 2 million constraints, while EVM-compatible receivers retain similar on-chain costs.The updater contract verifies Groth16 proofs in these cases.
7 RELATED WORK
Existing cross-chain bridges use committee- or incentive-based trust models and can incur long confirmation delays, while zkBridge combines cryptographic assurance with efficiency. Its novel proof techniques target the large circuits required for practical trustless bridging.
- Existing bridges include guardian committees, side-chain relays, and collateral-backed watchdog designs with differing security assumptions.Wormhole relies on two-thirds of its guardian committee being honest, while Nomad and Rainbow Bridge rely on collateral and monitoring.
- 4 hours of confirmation latency and 20 ETH of collateral are required by Near’s optimistic bridge design.zkBridge avoids both issues according to the paper.
- zkBridge provides efficiency and cryptographic assurance without extra assumptions beyond the blockchains and underlying cryptographic protocols.It also avoids the long confirmation period of optimistic protocols.
- 100x faster proof protocols and proof recursion make ZKP-based bridging practical for the large circuits targeted by zkBridge.The protocol exploits circuit data parallelism and uses recursion for efficient on-chain verification.
A BACKGROUND:
The sumcheck protocol is presented as Protocol 3.
- Protocol 3 gives the sumcheck protocol.
B THE DISTRIBUTED SUMCHECK PROTOCOL
The distributed sumcheck protocol is presented as Protocol 4.
- Protocol 4 gives the distributed sumcheck protocol.
C BACKGROUND: THE GKR PROTOCOL
The GKR protocol represents circuit-layer values as multilinear extensions and recursively checks claims through sumcheck. Random linear combinations combine layer claims so verification can continue toward the input layer.
- Notations in GKR protocol: The i-th circuit layer has S_i gates, s_i = ⌈log S_i⌉, and V_i maps each gate label to that gate’s output.V_0 corresponds to the circuit output.
- The GKR Protocol: The verifier uses sumcheck because each V_i is expressed as a summation over the next layer’s values.The equation is rewritten using multilinear extensions because sumcheck operates on polynomials over F.
- The GKR Protocol: The prover sends the claimed circuit output, after which the verifier evaluates the corresponding polynomial at a random point and invokes sumcheck recursively.The verifier computes wiring polynomials locally and requests evaluations from the prover as the protocol proceeds.
- Combining two claims using a random linear combination: Random linear combinations merge two claims about V_i into one expression before the next sumcheck invocation.The verifier samples α_i,1 and α_i,2 from F and combines the claims using Equation 5.
- The GKR Protocol: The verifier recursively repeats this process through the circuit layers until reaching the input layer.After each sumcheck, it receives two claims about the next layer and combines them again.
- The GKR Protocol: The formal GKR protocol is presented in Protocol 5.
D THE DISTRIBUTED PC PROTOCOL
The distributed PC protocol distributes polynomial-computation work across machines while coordinating through a master node and verifier. It uses sumcheck rounds and final input evaluations to validate the computation.
- Distributed sumcheck: Protocol 4 distributes a polynomial f across N machines, with P0 serving as master and the verifier coordinating three phases over ℓ rounds.Each machine holds a restricted polynomial f^(i), while P0 aggregates messages and relays verifier challenges.
- Distributed sumcheck: Each sumcheck round checks the previous claim against evaluations at 0 and 1, then sends a random field challenge to the master.The master relays each challenge to the remaining machines.
- Distributed sumcheck: At the final distributed round, machines evaluate their polynomials at the verifier’s challenges, and P0 constructs a multilinear polynomial from those values.The resulting polynomial supports the remaining verifier interaction.
- GKR verification: In GKR verification, the verifier applies sumcheck recursively across circuit layers and checks the claimed input-layer evaluations against the actual input.A failed check aborts with output 0; successful input checks produce output 1.
E BACKGROUND: THE VIRGO PROTOCOL
Virgo combines GKR with polynomial commitments to produce a zero-knowledge protocol for layered arithmetic circuits. Its stated complexity is near-linear prover time with polylogarithmic proof and verification costs.
- Virgo construction: Virgo combines the GKR protocol with polynomial commitments to prove the function computed by a layered arithmetic circuit.Protocol 7 commits to the input-layer multilinear extension and opens the claimed evaluations during verification.
- Protocol characterization: Protocol 7 is described as a knowledge argument system rather than a zero-knowledge proof protocol in the construction.The text notes that the knowledge argument system is what the construction actually uses.
- Polynomial commitment: Distributed PC commits each machine’s polynomial, aggregates commitments with a Merkle-tree commitment, and verifies queried evaluations against the combined polynomial.The verifier checks the weighted sum of machine evaluations and the corresponding Merkle openings.
- Complexity: The Virgo prover runs in O(|C|+m log m), while proof size and verification time are O(d log|C|+λ log^2 m).These bounds apply to a d-layer circuit with m inputs.
F THE DISTRIBUTED VIRGO PROTOCOL
The distributed Virgo protocol is obtained by combining distributed polynomial commitment with distributed sumcheck. This extends Virgo to data-parallel circuits evaluated across N distributed machines.
- Construction: The formal deVirgo protocol combines Protocol 6, the distributed polynomial commitment, with Protocol 4, the distributed sumcheck protocol.The paper presents this combination as the construction of deVirgo.
- Components: deVirgo uses distributed polynomial commitment and distributed sumcheck as its two protocol components.The combination preserves the named roles of both underlying protocols.
- Formal protocol: The resulting protocol is presented as the formal protocol of deVirgo.The passage identifies Protocol 8 as that formal protocol.
G ON-CHAIN GAS COST OPTIMIZATION
The gas-cost optimization shifts proof submission from provers to users and makes verification demand-driven. It avoids routine on-chain costs for unpopular chains while retaining on-demand verification for users who need proofs.
- Design: The optimization avoids immediate on-chain proof verification and block-header storage by having users submit the proofs they need.The design is intended to reduce on-chain gas costs for a universal zkBridge.
- Design: Proofs cover every 2^d blocks, and provers post them to users rather than immediately posting the batch Merkle root on-chain.Users retrieve and submit proofs when verification is required.
- Benefits: The authors state that the incentive-based design can benefit both provers and users by eliminating prover gas costs and supporting on-demand access.Users may be encouraged to submit proofs as a possible investment, while provers no longer pay for on-chain verification.
- Demand regimes: With high demand, each proof is submitted immediately, and each user pays for at most one on-chain proof verification.This case degenerates into the original batched-proof approach with verification costs shifted to users.
- Demand regimes: For unpopular sender chains, proofs are not submitted for costly verification until a user requests bridging.A user can retrieve the needed proofs from provers and submit them individually.