Skip to content

Protocol-Solidity Documentation

Suppose Alice wants to deposit on chain 1 and later wants to withdraw on chain 2.

Depositing

  1. 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.
    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.
  2. The anchor on chain 1 adds Alice's commitment to its Merkle Tree. This emits an event Deposit(_commitment, insertedIndex, block.timestamp).
  3. 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.
  4. This proposal is then voted on by the relayers.
    1. 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...
  5. If the proposal passes, then executeProposal happens. The AnchorHandler then updates Anchor 2's edge to Anchor 1.
  6. 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.

  1. Alice sends her secret and nullifier from 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.
  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 secret and 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 secret and nullifier.

So our first desiderata is that Alice should be able to withdraw without revealing her secret and 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 and levels . 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:

  1. secret
  2. nullifier
  3. pathElements[levels] , an array of the Merkle proof elements.
  4. pathIndices[levels] , a binary array that indicates whether the corresponding pathElement element is on the left or right side of the Merkle tree.
  5. diffs[length], an artifact of the SetMembership gadget that we describe below.

The public inputs to the circuit are:

  1. nullifierHash, which equals Poseidon(nullifier, nullifier). Its use is described in a section below.
  2. recipient, the address of the recipient (not used in computation).
  3. relayer, the address of the relayer (not used in computation).
  4. fee, the fee paid by Alice to the relayer (not used in computation).
  5. refund described in a section below (not used in any computation)
  6. refreshCommitmentdescribed in a section below (not used in any computation)
  7. chainID, the destination chain ID, or in our case 2.
  8. roots[length] the set of roots Alice's is proving membership in.

The Withdraw circuit is actually the composition of smaller gadget circuits:

  1. The CommitmentHasher circuit takes in the secret and nullifier and computes the commitment and the nullifierHash. Withdraw then checks that the computed nullifierHash is equal to the public input nulliferHash. This check is needed because otherwise, Alice can submit a bogus nullifierHash and double spend (more on this in a later section).
  2. The SetMembership gadget takes in an element and a set and checks whether that element is in the set. Actually, SetMembership also takes in diffs[length] but we will explain more about this later.
  3. The ManyMerkleTreeChecker gadget is responsible for checking the one-of-many Merkle proof. It takes in the commitment, pathElements[levels], pathIndices[levels] and computes the root of the Merkle tree corresponding to these inputs. It also takes in roots[length]and uses the SetMembership gadget to check whether the computed Merkle root (from the previous sentence) is in roots[length].

We describe the individual gadgets in more detail in the pages below:

DualMux

CommitmentHasher

SetMembership

ManyMerkleTreeChecker

Refund

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.

Refresh Commitment

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.

The 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.

References

https://github.com/tornadocash/tornado-core/blob/master/circuits/withdraw.circom