Zero Knowledge Proofs
ZKP Applications Overview & zkBridge, Trustless Bridge Made Practical
Instructors: Dan Boneh, Shafi Goldwasser, Dawn Song, Justin Thaler, Yupeng ZhangzkBridge: TrustlessBridge Made Practical

ZKP MOOC
Credit: Faithie/ShutterstockCross-chain Bridges▪
▪
▪

Multi-chain Universe
Bridge: generic and efficient communication cross blockchains
Desirable properties▪ Generality (support many applications)▪ Efficient▪ Secure with trust minimization (particularly crucial)

Sender chain

Receiver chain

ZKP MOOC

Current Common Bridge Approach: Trust Intermediary

Sender chain

Existing Approach: intermediary▪
▪
▪

Side chain (PolyNetwork, Axelar)
Committee (Wormhole, Ronin)
Oracles (LayerZero)

Receiver chain
Trust Assumptions• 2/3 honest nodes• 2/3 honest committee• independence between Oracle and Relayer

Pros: Simple & efficient on-chain verification (e.g., multisig)
Cons: Need to rely on external trust on intermediaries
ZKP MOOC

Over $2B Lost in Cross-chain Bridge Attacks in last 18 months
BridgeProtocolHackedTime

Total
Loss

BSC Bridge

2022-10

$568M

Nomad

2022-08$200M

Harmony2022-06

$100M

Ronin

2022-03$600M

Wormhole(Solana)2022-02$325M

PolyNetwork

2021-08$600M

Cause: Private KeyLeakage

ZKP MOOC

Remove Trust on Intermediary▪

Light client verification:▪
▪

▪

Cosmos IBC▪
▪

▪

Verifying certain correctness properties of state transition in consensus protocol
E.g., for BFT-based consensus, a light client needs to verify validator signaturesand keeps track of validator rotation
Validators verifies block header information of another chain, performing lightclient verification
Cons: require each chain to implement IBC client to perform the verification

NEAR Rainbow bridge▪
▪

Implement light client verification as a smart contract in Ethereum
Cons: on-chain verification is very expensive

ZKP MOOC

zkBridge—Trustless Bridge Made Practical▪

With ZKP, we replace honesty assumptions with Cryptographic
assurance
Zero-knowledge
proofs▪

Efficient on-chain verification using ZKP

Xie-Zhang-Cheng-Zhang-Zhang-Jia-Boneh-Song, “zkBridge: trustless bridge made practical”, ACM CCS 2022 (zkbridge.org)

ZKP MOOC

zkBridge—Trustless Bridge Made Practical▪
▪

𝛑: proving ht+1 is correct given ht (and other info)(consensus-specific light client verification) with SNARKsE.g., “∃ sigs by a majority of C1 committee on ht+1”

Verifier

Proverht

ht+1ht, ht+1, 𝛑Updater
Contract

Application
Contracts

Receiver chain

Sender chain
Block Header Relayer

Xie-Zhang-Cheng-Zhang-Zhang-Jia-Boneh-Song, “zkBridge: trustless bridge made practical”, ACM CCS 2022 (zkbridge.org)

ZKP MOOC

Advantages of zkBridge (zkbridge.org)▪

Minimized trust▪

▪

Efficient on-chain verification▪

▪

purpose-built zkSNARK enables efficient on-chain verification

Permissionless and Decentralized▪

▪

Cryptographic soundness instead of honest assumptionsProvers are not trusted so anyone can join

Extensible and Universal▪

Developers can develop their own application on top

ZKP MOOC

Challenges▪
▪

SNARKs are expensive
Blockchains are not designed to be “ZK friendly”▪

EdDSA digital signature is expensive to express as an arithmetic
circuit (~2M gates)
h, ht

▪

▪

t+1, 𝛑Each state transition can involve hundreds of sig verifications=> Computing 𝛑 naively can be prohibitively expensive

Block Header
Relayer
ZKP MOOC

Making zkBridge practical▪

▪
▪

deVirgo: a distributed version of Virgo(IEEE S&P 2020)▪ Exploits “data parallelism”▪ Optimal parallelization ---- 100x speedup with 128 machines▪ Practical communication ---- less than 20% of proving time
Reducing proof size by recursion▪ run deVirgo verifier in Groth16
Batching

deVirgo: fast proof generation, relatively
big proof
Groth16: slower proof generation,
constant proof & verification.

Constant size proofs & verification
with only a slight increase in provertime

ZKP MOOC

Approach: deVirgo & 2-layer Proof Composition
deVirgo Verifier
Largescale
Arithmetic
Circuit CdeVirgo Prover(distributedmachines)proof
π1

Layer 1: Distributed Proof
Generation on Distributed Machinestranslate theverification
process into acircuit C2(much smaller thanC1)

proof

Groth16 Verifier( on-chain smartcontract)π2

Groth16 Prover

Final Verification Result:
True/False

Layer 2:
Proof Composition

Efficient On-chain Proof
Verification

ZKP MOOC

Performance of zkBridge proofs

More results in paper: https://zkbridge.org.

ZKP MOOC

Extensibility of zkBridge
Application Layer(user-specified cross-chain applications)Application Contracts(can be both embedded on C1 or C2)

The updater contract
exposes an API forapplications to learn
the latest state of theother blockchain.

UpdaterContract

Base Layer(for block header synchronization)(deployed on C2)

Block Header
Relay Nodes
Sender chain

Generate proofs for block headers& relay the headers with proofs

Receiver chain

Extensibility & Applications
zkBridge has great extensibility
Developers can build application contracts to achieve more advanced functionalities such as:
1. Message Passing
2. Cross-chain Assets Transfer/Swap

3. cross-chain NFT Interoperations

ZKP MOOC

Application Layer Components
Application

User UThe application deploys smart contracts using zkBridge and interact
with them based on users’ requests.

Base Layer
Sender chain

Block Header Relay
Nodes

Updater
Contract

Receiver chain

ZKP MOOC

Application Layer Use Case 1: Message Passing
Application

User UThe user wants to use the application for passing message
from sender chain C1 to receiver chain C2.
The send contract is
deployed on C1.

Base Layer
Block Header
Relay Nodes

Sender chain
andUpdater
Contract

Both the updater contract
and the verify contract are
deployed on C2.

Receiver chain

provides a message-passing service that other applications can use

ZKP MOOC

Application Layer Use Case 1: Message Passing
Verification details:❶ Identify the blockcontaining m andverify the block is on
the main chain of DAG;

Applications❷ Write message mon sender chain C1❸ Relay header with proofs❹ Verify and accept

Base Layer

Updater
Contract

Block Header
Relay Nodes

Sender chain

Step ❸ ❹ aredone in base layer.

Receiver chain❷ Verify submitted
Merkle proof ofmessage m in thecorresponding block.
❻ Retrieve block header
DAG from updater contract
and verify message m.
Upon verification, message
m is made available torelevant applications on C2.

Defense-in-Depth▪
▪

Base layer of zkBridge presents a unified interface forsyncing block header from another chain
Improving security with defense-in-depth▪

▪

Combining multiple implementations: proof-diversity, nversion programming, combining with other approaches
such as optimistic solutions
Design different policies for combining different
implementations▪

E.g., Hashi (https://github.com/gnosis/hashi): an EVM
Header Oracle Aggregator
ZKP MOOC

zkBridge: trustless bridge made practical•••••

Minimized trust
Efficient on-chain verification
Efficient proof generation
Permissionless & decentralized by design
Extensible and universal• To learn more: https://zkbridge.org,
https://rdi.berkeley.edu/research• Tiancheng Xie, Jiaheng Zhang, Zerui Cheng, Fan Zhang, Yupeng Zhang, Yongzheng Jia, DanBoneh, Dawn Song, “zkBridge: trustless bridge made practical”, ACM CCS 2022

ZKP MOOC

zkBridge Technology Enables Other Capabilities▪

State proof▪

▪

zk-based light client verification▪

▪

A cryptographic proof of state changes that occur in agiven set of blocks (e.g., Algorand State Proof)Support efficient light client verification, including
mobile use case (e.g., Celo Plumo)

zkBridge can be extended to privacy chains with privacy
protectionZKP MOOC

zkBridge Track in ZKP/Web3 Hackathon

ZKP MOOC