Token shortlist

On this page, we explain how to update Version 0.10 circuits – supporting only the native AZERO token – to handle more tokens. Due to note structure limitations, in this update we choose around 5-30 tokens to support, and we call the list of chosen tokens the token shortlist. Full ERC20 support is expected in future releases.

We only discuss the Withdrawcircuit, as the remaining circuits should be easy to implement if the design of Withdrawis known.

We represent the account balances as a 6-tuple. We assume that there are 2 destination addresses (for the recipient and for the fee), and we do not differentiate between them. The circuit receives 2 indexes of modified balances as public inputs, and performs range checks just on the 2 new balances.

In the future, we will be able to extend the length of the tuple with small changes to the circuits and no note migration. We describe such an extension in the last section.

Alternative designs

We considered storing the shortlisted balances as a tree of height 2, but abandoned this idea because it visibly increases circuit complexity without significant performance gains for the expected number of shortlisted tokens.

Note representation

We represent the account balances of all tokens, including AZERO, as the following tuple:

const NUM_SLOTS: usize = 6;

type Account = [Scalar; NUM_SLOTS];

We do not need to decide in advance, which tokens occupy all NUM_SLOTSslots. We may define the slot mapping in the contract just for a subset of slots, and make the contract reject attempts to use the unused slots. In any case, the NewAccountcircuit should properly initialize all slots.

Our note struct is given by:

struct Note {
    version: Scalar,
    id: Scalar,
    nullifier: Scalar,
    trapdoor: Scalar,
    h_acc: Scalar,          // hash of the `Account` tuple
} 

For an account tuple acc, we define its hash as:

h_acc = poseidon2(acc[0], ..., acc[5], 0).      

Withdrawrelation

We are ready to define the Withdrawrelation:

relation Withdraw

inputs:
    - merkle_root:      Scalar
    - h_nullifier_old:  Scalar
    - h_note_new:       Scalar
    - value_1:          Scalar    // amount that goes to the 1st recipient
    - value_2:          Scalar    // amount that goes to the 2nd recipient
    - idx_1:            Scalar    // 0-based index of token sent to the 1st recipient
    - idx_2:            Scalar    // 0-based index of token sent to the 2nd recipient
    - commitment:       Scalar    // Keccak hash of values that do not need
                                  // to be unpacked inside the circuit
    
witnesses:
    - note_old:            Note
    - note_new:            Note
    - acc_old:             Account
    - acc_new:             Account
    - merkle_path:         [[Scalar; MERKLE_ARITY]; MERKLE_HEIGHT]

constraints:
    // (C1)
    - for j ∈ { 0, ..., NUM_SLOTS - 1 }:
      acc_new[j] = ⎧ acc_old[j] - value_1 - value_2,     if j = idx_1 = idx_2,
                   ⎪ acc_old[j] - value_1,               if j = idx_1 != idx_2,
                   ⎪ acc_old[j] - value_2,               if j = idx_2 != idx_1,
                   ⎩ acc_old[j],                         otherwise
       
    // (C2) Range check, prevents overflow after subtraction.            
    - acc_new[j] <= AMOUNT_BOUND                         for j ∈ { idx_1, idx_2 }
        
    // Updated hash application:
    - note_old.h_acc is a correct hash of acc_old
    - note_new.h_acc is a correct hash of acc_new
    
    // Same as before.
    - note_new.id = note_old.id
    - h_note_new = hash(note_new)
    - h_nullifier_old = hash(note_old.nullifier)
    - hash(note_old) belongs to the first layer of merkle_path
    - merkle_path is a valid path to merkle_root

The definition above does not immediately translate to a circuit description because of the way constraint groups (C1) and (C2) are defined. These constraint groups may be implemented in a circuit as follows:

Implementing constraint group (C1) in a circuit

First, we introduce auxiliary private witnesses idx_i_j ∈ {0, 1}such that:

idx_i_j = 1 iff idx_i = j, for i ∈ {1, 2}, j ∈ {0, ..., NUM_SLOTS - 1}.

Then, for every j ∈ {0, ..., NUM_SLOTS - 1}, we add the following constraint:

acc_new[j] = acc_old[j] - value_1 * idx_1_j - value_2 * idx_2_j.

We create the above constraints using a custom gate.

Implementing constraint group (C2) – the range check – in a circuit

We just add the following constraint, for i ∈ {1, 2}:

∑_{j ∈ {0, ..., NUM_SLOTS - 1}} idx_i_j * acc_new[j] <= AMOUNT_BOUND

Increasing balance tuple size

We may increase NUM_SLOTS. We always require NUM_SLOTSto be a multiple of 6.

For NUM_SLOTS = 6k > 6, we define h_acc = h(acc, 0), where h(acc, i)is recursively defined as:

h(acc, i) =
    ⎧ poseidon2(acc[i], ..., acc[i + 5], 0), 
    |       if i = NUM_SLOTS - 6 or acc[i + 6..NUM_SLOTS] has only zeroes,
    | poseidon2(
    |     acc[i],
    |     ...,
    |     acc[i + 5],
    |     h(acc, i + 6)
    ⎩ ),                                                      otherwise.       

For example:

• The hash of (1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0) is poseidon2(1, 2, 3, 4, 5, 6, 0).

• The hash of (1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 1) is poseidon2(1, 2, 3, 4, 5, 6, poseidon2(0, 0, 0, 0, 0, 1, 0)).

Note that we do not allow (1, 2, 3, 4, 5, 6, 0, 0, 0, 0, 0, 0) to be hashed as poseidon2(1, 2, 3, 4, 5, 6, poseidon2(0, 0, 0, 0, 0, 0, 0)). This way, every balance tuple has a deterministic hash value.

This change requires updating NUM_SLOTSand the hashing logic in the circuits, but no note migration.