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 branchDef: 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 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. - 2.The history of merkle roots
merkle_roots
: a set ofScalar
holding historical merkle roots. - 3.The set of nullifiers
nullifiers
— a set ofScalar
, the purpose of this structure is to keep track of used notes. - 4.The set of registered tokens
registered_tokens
— a mappingTokenId -> 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 tokenTokenId
to theShielder
contract, and transfervalue
toShielder
- 2.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)
- 3.Add the
note
at the next empty leaf spot in the merkle tree and updatetree
. - 4.Add the new
root
tomerkle_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
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. - 3.what it does:
- 1.validate that the
merkle_root
is some historical root, i.e., belongs tomerkle_roots
- 2.validate that
nullifier
is not yet innullifiers
- 3.validate that
fee_for_caller <= value_out
- 4.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
- 5.Add the
new_note
at the next empty leaf spot in the merkle tree and updatetree
. Add the newroot
to themerkle_roots
- 6.Add
nullifier
tonullifiers
- 7.Unlock
value_out
oftoken_id
from the balance ofShielder
and sendfee_for_caller
to the caller andvalue_out - fee_for_caller
torecipient
- 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 ofdeposit
andmerge
. 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 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 modified 7mo ago