Comment on page

# Specification

This page gives a quite detailed specification of the

`Shielder`

. We refer to Introduction for a high level explanation of the `Shielder`

and to github for a reference implementation as a smart contract in ink! (see also Aleph Zero smart contracts basics for an introduction to ink!). This page assumes certain level of familiarity with zk-SNARKs. In particular SNARK relations, proofs, private and public inputs.

`Scalar`

— element of the scalar field of BLS12-381 (the curve we work over)`H`

— a hash function. This typically takes as input a few scalars and outputs one scalar. For practical efficiency the best choice is a snark-friendly hash function, such as `Poseidon`

.`TokenId`

— some type that uniquely identifies a token, we could use `AccountId`

— the address of the token — but by using a shorter identifier, we can save a lot of gas. Concretely, `TokenId`

could be just `4`

or even `2`

bytes.`Proof<Rel>`

— a type representing a snark proof for a particular relation `Rel`

`MerkleProof`

— as the name suggests, a merkle branch**Def:**A note is a hash

`H(nullifier, trapdoor, token_id, value)`

where `nullifier: Scalar`

, `trapdoor: Scalar`

, `token_id: TokenId`

and `value: u128`

The

`Shielder`

contract stores the following data- 1.a Merkle tree
`tree`

— a full binary tree with height`H`

thus`2^H`

leaves. This will be held as a mapping`u32 -> Scalar`

where`u32`

is the index of a node (standard way of numbering: root is`1`

and the children of`x`

are`2x`

and`2x+1`

.) and the value is actually a Poseidon hash. The tree is supposed to hold`notes`

in leaves, and be a standard Merkle tree otherwise, so for an internal vertex it's value is`H(left, right)`

-- hash of the left and right children. - 2.The history of merkle roots
`merkle_roots`

: a set of`Scalar`

holding historical merkle roots. - 3.The set of nullifiers
`nullifiers`

— a set of`Scalar`

, the purpose of this structure is to keep track of used notes. - 4.The set of registered tokens
`registered_tokens`

— a mapping`TokenId -> AccountId`

which says what token_id corresponds to which PSP22 token.

- 1.
`deposit`

- 1.
**inputs**:- 1.
`value: u128`

- 2.
`token_id: TokenId`

- 3.
`note: Scalar`

- 4.
`proof: Proof<Deposit>`

- 2.
**idea**: send some tokens in the plain to the contract, create a note that represents shielded tokens. - 3.
**what it does**:- 1.validate that the caller has given
`>=value`

allowance of token`TokenId`

to the`Shielder`

contract, and transfer`value`

to`Shielder`

- 2.validate the
`proof`

, it should demonstrate that (for details take a look at the description of the`Deposit`

relation):- There exist
`t`

,`n`

such that`note = H(n, t, token_id, value)`

- 3.Add the
`note`

at the next empty leaf spot in the merkle tree and update`tree`

. - 4.Add the new
`root`

to`merkle_roots`

- 2.
`withdraw`

- 1.
**inputs**:- 1.
`value_out: u128`

- 2.
`recipient: AccountId`

- 3.
`fee_for_caller: u128`

- 4.
`token_id: TokenId`

- 5.
`merkle_root: Scalar`

- 6.
`proof: Proof<Withdraw>`

- 7.
`nullifier: Scalar`

- 8.
`new_note: Scalar`

- 2.
**idea:**spend one note`note`

of`value`

tokens → take out`value_out`

tokens in the plain (out of which`fee_for_caller`

goes to the caller and the rest goes to`recipient`

), and close the rest`value-value_out`

tokens in a new note`new_note`

.`value_out=value`

is allowed, in which case a note with`0`

tokens will be created, which is also fine. - 3.
**what it does**:- 1.validate that the
`merkle_root`

is some historical root, i.e., belongs to`merkle_roots`

- 2.validate that
`nullifier`

is not yet in`nullifiers`

- 3.validate that
`fee_for_caller <= value_out`

- 4.validate
`proof`

, it should demonstrate that (for details take a look at the description of the`Withdraw`

relation):- There exists
`note`

and`merkle_root`

such that`merkle_proof`

is a valid merkle proof from`merkle_root`

to`note`

- There exist
`t`

and`value`

such that`note = H(nullifier, t, token_id, value)`

- There exist
`t'`

,`n'`

and`new_value`

such that`new_note = H(n', t', token_id, new_value)`

`new_value>=0`

and`new_value + value_out == value`

- 5.Add the
`new_note`

at the next empty leaf spot in the merkle tree and update`tree`

. Add the new`root`

to the`merkle_roots`

- 6.Add
`nullifier`

to`nullifiers`

- 7.Unlock
`value_out`

of`token_id`

from the balance of`Shielder`

and send`fee_for_caller`

to the caller and`value_out - fee_for_caller`

to`recipient`

- 3.
`merge`

- 1.
**inputs**:- 1.
`token_id: TokenId`

- 2.
`merkle_root: MerkleRoot`

- 3.
`first_nullifier: Scalar`

- 4.
`second_nullifier: Scalar`

- 5.
`note: Scalar`

- 6.
`proof: Proof<Merge>`

- 2.
**idea:**remove from the shielder two notes, holding the same token, and create one with combined values of both

- 4.
`deposit_and_merge`

-- a combination of`deposit`

and`merge`

. A new deposit, instead of being added to the tree, is merged with an already existing note.

We provide detailed descriptions of relations that are used for building snarks for

`Deposit`

and `Withdraw`

. The remaining two relations `Merge`

and `DepositAndMerge`

are not described in this specification because they are analogous to the ones below. An interested reader we refer to the actual implementations in our repository.Relation

`Deposit`

:- 1.public inputs:
`note: Scalar`

,`token_id: TokenId`

,`value: u128`

- 2.private inputs (witness):
`t: Scalar`

,`n: Scalar`

- 3.Constraints:
- 1.
`H(n, t, token_id, value) == note`

Relation

`Withdraw`

:- 1.public inputs:
`nullifier: Scalar`

,`merkle_root: Scalar`

,`new_note: Scalar`

,`token_id: TokenId`

,`value_out: u128`

- 2.private inputs (witness):
`t, t': Scalar`

,`n': Scalar`

,`merkle_proof: MerklePath`

,`note: Scalar`

,`new_value: u128, value: u128`

- 3.Constraints:
`merkle_proof`

is a valid merkle proof from`merkle_root`

to`note`

`note == H(nullifier, t, token_id, value)`

`new_note == H(n', t', token_id, new_value)`

`new_value>=0`

and`new_value + value_out == value`

Note: we also need to include

`recipient`

and `fee`

in the context of the snark, to prevent malleability (see for instance this description). Otherwise one could capture a `tx`

, copy the snark proof, and send a new `tx`

with a different recipient.Last modified 7mo ago