Specification (Legacy, not up-to date)

This page gives a quite detailed specification of the Shielder. We refer to 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.

Notation and Definitions

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

Contract Storage

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.

Contract Calls (Transactions)

  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.

Relations

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.

PreviousUser WalletNextTutorial (Legacy, not up-to date)

Last updated