Suppose Alice wants to deposit on chain 1 and later wants to withdraw on chain 2.
- She deposits funds and a commitment (
hash(destinationChainID, nullifier, secret)) from her account on chain 1 to the anchor (a smart contract) on chain 1.
- The form of the commitment means that Alice must pre-commit to which chain she will withdraw or refresh (more on this later) on, in this case, chain 2.
- The anchor on chain 1 adds Alice's commitment to its Merkle Tree. This emits an
event Deposit(_commitment, insertedIndex, block.timestamp).
- A relayer picks up this event and opens a proposal to update (or add, if an edge does not already exist) Anchor 2's edge to Anchor 1. Anchor 2 stores a cache of Anchor 1's last 30 historical Merkle roots. If the proposal succeeds, Anchor 1's Merkle root will be added to this cache.
- This proposal is then voted on by the relayers.
- This begs the question, why do we have to vote. This is because relayers may choose to submit bogus proposals (of deposits that never happened) or ignore some deposits or do other malicious activities...
- If the proposal passes, then
AnchorHandlerthen updates Anchor 2's edge to Anchor 1.
- At this point Anchor 2 is "aware" of Alice's deposit into Anchor 1. By this we mean Alice can now submit a valid zero-knowledge proof to withdraw into chain 2 (more on this in the sections below).
Basics of Zero-Knowledge Proofs¶
- Suppose we have an arithmetic circuit.
- A satisfying assignment to the circuit consists of inputs such that all the constraints of the circuit are satisfied.
- A proof of a satisfying assignment for the circuit is a proof that we know some satisfying assignment to the circuit (note the most obvious way to do this is to just provide a satisfying assignment).
- Now, lets call some of the inputs to the circuit as public and some as private. A zero-knowledge proof of a satisfying assignment for the circuit is a proof that we know some satisfying assignment to the circuit without revealing any information about the private inputs.
Withdrawing without Taking Privacy¶
An action which takes privacy is any action that provides information about private data.
Alice wishes to withdraw in a way which takes the least amount of privacy possible.
Recall that each anchor stores a cache of the last 30 historical Merkle roots of each anchor it has an edge to. To withdraw on chain 2, Alice must prove to the anchor 2 that her deposit commitment is a leaf on a Merkle tree with root in one of these caches. We call such a proof a one-of-many Merkle proof.
Let's look at a naive approach that Alice can take to achieve this.
- Alice sends her
nullifierfrom her address on chain 2 to the anchor on chain 2. She also sends a one-of-many Merkle proof that
Poseidon(destinationChainID = 2, nullifier, secret)is a leaf in a Merkle tree with root in one of the caches maintained by anchor 2.
- The anchor on chain 2 can then verify the one-of-many Merkle proof and release funds to Alice's account on chain 2.
Let's now understand where privacy is being taken in this approach.
When Alice deposited, she submitted funds along with a commitment to the anchor on chain 1. This data is available to the public. Now, if she publicly reveals her
nullifier when she withdraws on chain 2, anyone can can calculate
Poseidon(destinationChainID = 2, nullifier, secret) and see that it equals her deposit commitment on chain 1. At this point everyone knows that Alice's accounts on chain 1 and chain 2 are controlled by the same person. If someone knows Alice's address on chain 1, then they also know it on chain 2. Thus, Alice's transfer of funds from chain 1 to chain 2 takes a large amount of privacy if she reveals the
So our first desiderata is that Alice should be able to withdraw without revealing her
nullifier. In a similar vein, sending a one-of-many Merkle proof also requires Alice to reveal her deposit commitment, which in turn takes her privacy. So our second desiderata is that Alice should be able to withdraw without revealing the one-of-many Merkle proof.
In the next section, we show how Alice can achieve these two desiderata using zero-knowledge proofs.
There is one last thing to consider. If Alice sends the withdrawal proof to chain 2's anchor from her own account, anyone who knows Alice's address on chain 2, knows that it is her executing the withdrawal. To make this process more private, Alice can instead send the proof to a relayer which then submits the proof to anchor. The relayer sets the
recipient of the withdrawal funds to be a fresh new account, which Alice controls. This improves Alice's privacy since noone can link her to the fresh new account.
So our third desiderata is that Alice should withdraw using a relayer.
Using Zero-Knowledge Proofs for Withdrawals¶
We describe a
Withdraw circuit such that the constrainsts of these circuits are satisfied if and only if Alice can validly withdraw on chain 2. The
Withdraw circuit contains two paramters
length is the number of anchors connected via an edge across the bridge.
levels is the height of the anchor Merkle trees.
The private inputs to the circuit are:
pathElements[levels], an array of the Merkle proof elements.
pathIndices[levels], a binary array that indicates whether the corresponding
pathElementelement is on the left or right side of the Merkle tree.
diffs[length], an artifact of the
SetMembershipgadget that we describe below.
The public inputs to the circuit are:
nullifierHash, which equals
Poseidon(nullifier, nullifier). Its use is described in a section below.
recipient, the address of the recipient (not used in computation).
relayer, the address of the relayer (not used in computation).
fee, the fee paid by Alice to the relayer (not used in computation).
refunddescribed in a section below (not used in any computation)
refreshCommitmentdescribed in a section below (not used in any computation)
chainID, the destination chain ID, or in our case 2.
roots[length]the set of roots Alice's is proving membership in.
Withdraw circuit is actually the composition of smaller gadget circuits:
CommitmentHashercircuit takes in the
nullifierand computes the
Withdrawthen checks that the computed
nullifierHashis equal to the public input
nulliferHash. This check is needed because otherwise, Alice can submit a bogus
nullifierHashand double spend (more on this in a later section).
SetMembershipgadget takes in an
setand checks whether that
elementis in the
SetMembershipalso takes in
diffs[length]but we will explain more about this later.
ManyMerkleTreeCheckergadget is responsible for checking the one-of-many Merkle proof. It takes in the
pathIndices[levels]and computes the root of the Merkle tree corresponding to these inputs. It also takes in
roots[length]and uses the
SetMembershipgadget to check whether the computed Merkle root (from the previous sentence) is in
We describe the individual gadgets in more detail in the pages below:
Suppose a relayer submits a correct proof to an anchor on chain 2 and funds are withdrawn into a fresh new account for Alice. Suppose these funds are non-native tokens. Then, Alice cannot spend these tokens since she cannot pay the gas fees for transactions.
A way around this is for Alice to pay the relayer an amount equal to
fee + refund and have the relayer deposit an amount equal to
refund into the fresh account.
Preventing Double Spending¶
How do we prevent Alice from double spending her deposit. We split our discussion into to cases:
Case 1: Double spending the same deposit on the same chain: This is impossible due to the
nullifierHash. When Alice withdraws on chain 2 the
nullifierHash = Poseidon(nullifier, nullifier) is stored by the anchor. When she tries to withdraw with the same commitment the anchor will check its set of stored
nullifierHashes and will realize she is trying to double spend.
Case 2: Double spending the same deposit on different chains: This is impossible because the commitment contains the destination chain. Therefore, if Alice tries to withdraw a commitment with destination chain ID equal to 2 on chain 3, the verifier will reject Alice's proof.
Recall that Alice must commit to her destination chain when she deposits. Suppose Alice wants to change her destination chain from chain 2 to chain 3. She would have to withdraw on chain 2 and then redeposit into the anchor on chain 2 with her destination chain set to chain 3.
A refresh commitment allows these two steps to be combined into one function call. It allows Alice to add a commitment to the Merkle tree on anchor 2 with the destination chain set to chain 3, while simultaneously guaranteeing that she can no longer withdraw her original deposit.
refreshCommitment signal in the
Withdraw circuit is set to this new commitment if a refresh commitment is being done. If a traditional withdrawal is being made, the
refreshCommitment signal is set to 0.