Notes and Accounts

Here we describe the basic shielder design, then: in section ZK-ID and Registrars we enrich it with ZK-IDs for sybil resistance and in section Anonymity Revokers we propose an improvement that helps in fighting bad actors.

The shielder is smart contract that holds:

• notes -- a binary Merkle Tree of a fixed depth H -- each node in this tree is a Scalar element. The leaves in the tree hold hashes of user Notes (see below).

• nullifier_set -- a set of elements of type Scalar whose purpose is to invalidate old notes

• roots -- a list of all historical Merkle roots, needed for technical reasons

• Other less relevant storage items that we omit for brevity.

Notes

Each leaf of the notes Merkle Tree is a hash of a note. The Note is a data structure

struct Note {
    id: Scalar, // the ZK-ID of a user
    trapdoor: Scalar, // a secret needed to prove ownership of the note
    nullifier: Scalar, // a secret used to invalidate the note
    account_hash: Scalar, // the hash of the user's Account state
} 

We note that because 1) we store hashes of Note in the Merkle Tree, and 2) because trapdoor stays secret forever (only the user knows it), the id and the account stay private even if nullifier is revealed.

The ZK-ID is discussed in ZK-ID and Registrars

Accounts

Instead of describing concretely what the Account structure is, we instead abstractly define the operations/properties that accounts should have. By adopting Rust terminology, we define the Account "trait", i.e., specify all the methods that should be defined on accounts.

• fn new() -> Account Creates a new account.

• fn hash(acc: Account) -> Scalar Hashing to a Scalar (field element)

• fn update(acc: Account, op: Operation) -> Account update is a state transition function for Accounts, given an Operation such as add 2 ETH or subtract 5 AZERO

The set of operations depends on what do we want to support exactly. But one should have in mind something akin to:

enum OperationSimple {
    depositFT(Amount, TokenId, AccountId),
    withdrawFT(Amount, TokenId, AccountId),
    depositNFT(Id, AccountId),
    withdrawNFT(Id, AccountId),
}

There are additional technical details regarding the description of operations that arise because of details on how accounts are represented and accessed, but they are not essential for high-level understanding.

The simplest possible account structure that supports just a fixed list of fungible tokens would look as follows:

AccountSimple {
    balance_AZERO: Scalar,
    balance_USDT: Scalar,
    balance_USDC: Scalar,
    balance_wETH: Scalar,    
}

this structure is very simple and allows to implement all the required methods assuming that there are just two possible operations depositFT and withdrawFT . The downside is that it's not easily extendable to more token types and/or NFTs. So it might be beneficial to use a more complex structure, like below

AccountAdvanced {
    balance_AZERO: Scalar,
    other: Array<Scalar, 256>,
}

The other field is meant to be an array of 256 entries, each of which is an asset, either FT or NFT, represented as a hash, for instance, hash(ETH, 4) would represent 4 ETH. This account structure is certainly more flexible but it poses an issue when it comes to hashing it and proving correct updates efficiently. More specifically, we are interested in efficiently proving the following ZK-relation:

relation R_update_account

inputs:
    - op: Operation // operation to be performed
    - h_acc_old: Scalar, 
    - h_acc_new: Scalar,
    
witnesses:
    - acc_new: Account,
    - acc_old: Account,

constraints:
    1. acc_new = Account::update(acc_old, op)
    2. h_acc_old = Account::hash(acc_old) // Account::hash is the hash method of the Account trait
    3. h_acc_new = Account::hash(acc_new) 

What matters to us is that R_update_account should be possible to write as a small arithmetic circuit so that SNARKs for R_update_account can be generated efficiently (prover efficiency). It is also not a coincidence that the public inputs of R_update_account are hashes of acc_old and acc_new and not the values itself. The account size might be significant (as in AccountAdvanced) and hence we don't want them explicitly included in the circuit. Even though the constraints mention acc_old and acc_new the circuit does not have to unpack whole accounts as long as the Account::hash is smart enough (for instance it can Merklize other in AccountAdvanced). This way there is hope to make the size of the R_update_account circuit logarithmic (or even constant) in the size of Account.

Operations

For maximum flexibility and to enable certain less trivial use patterns we introduce an abstraction layer on Operation. Namely we assume that each operation op: Operation can be broken into:

• op_priv: OpPriv - the "private" part of the operation that the user does not reveal

• op_pub: OpPub - the "public" part of the operation that is visible in the transaction

Moreover we assume there is a function

fn combine(op_priv: OpPriv, op_pub: OpPub) -> Option<Operation>

which allows to extract an Operation like above given the public and private counterparts. Note that the output of combine is Option<Operation> and not Operation to signify that it can fail -- it will be apparent from the subsequent examples why is that.

The intuition to keep in mind is that op_pub in plaintext will be attached to a transaction the user sends (part of calldata) whereas op_priv will be only part of the witness of a ZK-relation that the user proves when executing the transaction. Typically op_priv is used to hold one of:

• Data that the use wants to keep hidden. For instance when transferring funds to a different user the op_priv might contain the recipient "address" and transferred amount.

• Data that is not necessary for public execution (see below in the description of transaction) of the operation and is just a technical detail related to how Accounts are represented. For instance we might want to include details on which index of the other Array is used to save data about a particular asset when using AccountAdvanced

One interesting option would be to set op_priv = op and op_pub = hash(op) -- this makes the size of op_pub just 1 Scalar which is good for the verifier complexity. Using some salt, to randomize the hash can even allow us to gain full privacy. This however might not be viable for operations like Deposit where the shielder contract is required to accept a public token transfer of a particular amount, and thus couldn't be done when amount is private.

Examples:

• If we use AccountSimple as Account and the Operation type is similar to OperationSimple then we could just use OpPub = Operation and OpPriv = () (unit type -- "empty").

• If we use AccountAdvanced as Account then the Operation type needs to contain more details than just OperationSimple -- indeed if the user makes deposit operation with +10 ETH then op must contain information which cell of the other Array should be modified and how. So one can think that op_priv specifies the non-deterministic details of op while op_pub is just a "human readable" representation of op.

Updating Notes

Using R_update_account as a black box, we can formulate the relation that's needed to update notes

relation R_update_note

inputs:
    - op_pub: OpPub // the public part of  the operation to be performed
    - h_note_new: Scalar,
    - merkle_root: Scalar,
    - nullifier_old: Scalar,
    
witnesses:
    - note_new, note_old: Note,
    - trapdoor_new, trapdor_old: Scalar
    - nullifier_new: Scalar,
    - proof: MerkleProof
    - op_priv: OpPriv
    - id: Scalar
    
constraints:
    1. h_note_new = hash(note_new)
    2. note_new = Note { id, trapdoor_new, nullifier_new, h_acc_new }
    3. h_note_old = hash(note_old)
    4. note_old = Note { id, trapdoor_old, nullifier_old, h_acc_old }
    5. verify_merkle_proof(merkle_root, h_note_old, proof)
    6. op = combine(op_pub, op_priv)
    7. R_update_account(op, h_acc_old, h_acc_new)

Note: in practice, for efficiency the R_update_account instead of having op_pub as a public input would likely be parametrized by different "variants" the op_pub can come in. For instance we would have R_update_account_deposit and R_update_account_withdraw etc. that take input specific to deposit and withdraw variants. The reason this is better in practice is that the efficiency of the prover depends on the circuit size, and if we support all variants in one circuit, the circuit becomes unnecessarily big.

Transactions updating Notes

Finally we are able to write the pseudocode for a transaction the user sends to update its note

transaction update_note

inputs:
    - op_pub: OpPub,
    - proof: ZkProof,
    - nullifier_old: Scalar,
    - merkle_root: Scalar,
    - h_note_new: Scalar,
    
execution:
    - shielder.public_exec(op_pub)
    - assert: merkle_root is the current or historical root of shielder.notes
    - assert: nullifier_old not in shielder.nullifier_set
    - v = ZK-Verifier(R_update_note) // initialize verifier for the relation R_update_note
    - assert: v.verify(proof; (op_pub, h_note_new, merkle_root, nullifier_old))
    - shielder.notes.add_leaf(h_note_new)
    - shielder.nullifier_set.add(nullifier_old)

The above should be familiar for those who have studied privacy systems like ZCash.

The first instruction shielder.public_exec(op_pub) performs all operations on the "public state" that the operation op_pub requires. Below we give some examples. It is important to note that even though public_exec(op_pub) might perform some token transfers etc. as a first operation in the transaction, it will be rolled back in case some later operation fails (such as proof verification), so in fact it does not matter much where is this instruction placed within the function body.

Example: depositFT operation

// Below implementation for the depositFT variant
fn public_exec(op_pub: OpPub) {
    let depositFT { amount, token_id, user } = op_pub;
    assert allowance(user, shielder) >= amount;
    transfer amount of token_id token from user to shielder;
}

Note that in the above if the user has not given enough allowance to the shielder contract, then the assert fails and hence the execution of update_note fails too.

The above is what the "public" part of the operation does. As mentioned before, the "full" version op: Operation that arises when op_pub is combined with the op_priv part is used to update the user's private account. What Account::update(acc, op) should do in this case is quite straightforward, depending on the specifics of Account this might be:

• either incrementing one of the hardcoded fields (AccountSimple), or,

• adding the tokens to one of the cells in acc.other (AccountAdvanced).

Example: withdrawFT operation

// Below implementation for the withdrawFT variant
fn public_exec(op: Operation) {
    let withdrawFT { amount, token_id, user } = op_pub;
    transfer amount of token_id token from shielder to user;
}