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
a Merkle tree
tree
— a full binary tree with heightH
thus2^H
leaves. This will be held as a mappingu32 -> Scalar
whereu32
is the index of a node (standard way of numbering: root is1
and the children ofx
are2x
and2x+1
.) and the value is actually a Poseidon hash. The tree is supposed to holdnotes
in leaves, and be a standard Merkle tree otherwise, so for an internal vertex it's value isH(left, right)
-- hash of the left and right children.The history of merkle roots
merkle_roots
: a set ofScalar
holding historical merkle roots.The set of nullifiers
nullifiers
— a set ofScalar
, the purpose of this structure is to keep track of used notes.The set of registered tokens
registered_tokens
— a mappingTokenId -> AccountId
which says what token_id corresponds to which PSP22 token.
Contract Calls (Transactions)
deposit
inputs:
value: u128
token_id: TokenId
note: Scalar
proof: Proof<Deposit>
idea: send some tokens in the plain to the contract, create a note that represents shielded tokens.
what it does:
validate that the caller has given
>=value
allowance of tokenTokenId
to theShielder
contract, and transfervalue
toShielder
validate the
proof
, it should demonstrate that (for details take a look at the description of theDeposit
relation):There exist
t
,n
such thatnote = H(n, t, token_id, value)
Add the
note
at the next empty leaf spot in the merkle tree and updatetree
.Add the new
root
tomerkle_roots
withdraw
inputs:
value_out: u128
recipient: AccountId
fee_for_caller: u128
token_id: TokenId
merkle_root: Scalar
proof: Proof<Withdraw>
nullifier: Scalar
new_note: Scalar
idea: spend one note
note
ofvalue
tokens → take outvalue_out
tokens in the plain (out of whichfee_for_caller
goes to the caller and the rest goes torecipient
), and close the restvalue-value_out
tokens in a new notenew_note
.value_out=value
is allowed, in which case a note with0
tokens will be created, which is also fine.what it does:
validate that the
merkle_root
is some historical root, i.e., belongs tomerkle_roots
validate that
nullifier
is not yet innullifiers
validate that
fee_for_caller <= value_out
validate
proof
, it should demonstrate that (for details take a look at the description of theWithdraw
relation):There exists
note
andmerkle_root
such thatmerkle_proof
is a valid merkle proof frommerkle_root
tonote
There exist
t
andvalue
such thatnote = H(nullifier, t, token_id, value)
There exist
t'
,n'
andnew_value
such thatnew_note = H(n', t', token_id, new_value)
new_value>=0
andnew_value + value_out == value
Add the
new_note
at the next empty leaf spot in the merkle tree and updatetree
. Add the newroot
to themerkle_roots
Add
nullifier
tonullifiers
Unlock
value_out
oftoken_id
from the balance ofShielder
and sendfee_for_caller
to the caller andvalue_out - fee_for_caller
torecipient
merge
inputs:
token_id: TokenId
merkle_root: MerkleRoot
first_nullifier: Scalar
second_nullifier: Scalar
note: Scalar
proof: Proof<Merge>
idea: remove from the shielder two notes, holding the same token, and create one with combined values of both
deposit_and_merge
-- a combination ofdeposit
andmerge
. 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
:
public inputs:
note: Scalar
,token_id: TokenId
,value: u128
private inputs (witness):
t: Scalar
,n: Scalar
Constraints:
H(n, t, token_id, value) == note
Relation Withdraw
:
public inputs:
nullifier: Scalar
,merkle_root: Scalar
,new_note: Scalar
,token_id: TokenId
,value_out: u128
private inputs (witness):
t, t': Scalar
,n': Scalar
,merkle_proof: MerklePath
,note: Scalar
,new_value: u128, value: u128
Constraints:
merkle_proof
is a valid merkle proof frommerkle_root
tonote
note == H(nullifier, t, token_id, value)
new_note == H(n', t', token_id, new_value)
new_value>=0
andnew_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 updated