# Protocol-Solidity Documentation¶

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

### Depositing¶

- 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
`executeProposal`

happens. The`AnchorHandler`

then 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
`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. - 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:

`secret`

`nullifier`

`pathElements[levels]`

, an array of the Merkle proof elements.`pathIndices[levels]`

, a binary array that indicates whether the corresponding`pathElement`

element is on the left or right side of the Merkle tree.`diffs[length]`

, an artifact of the`SetMembership`

gadget 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).`refund`

described in a section below (not used in any computation)`refreshCommitment`

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

The `Withdraw`

circuit is actually the composition of smaller gadget circuits:

- 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). - 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. - 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:

### 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 `nullifierHash`

es 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