###### tags: `aztec3-speccing-book`

:::info
PROPOSAL
Author: Zac
:::

TODO: put together some data structure that allows contracts to check for the non-existence of data (e.g. a blacklist)

**IMPORTANT: this document is supplemented by a Discourse conversation [here](https://discourse.aztec.network/t/utxo-syntax-1-explicitly-specifying-the-utxo-owner/45)**

# UTXOs and Private State Semantics (in Smart Contracts)

Defining semantics to manipulate private state comes with unique difficulties due to its encrypted nature and the fact that private state is UTXO based.

## The UTXO problem

Unlike in Aztec 2, we cannot anticipate the data *type* of the state value.

If it is a simple numeric type, the contract developer may wish to have a private state slot represent an aggregateable value. It may be aggregateable but only depending on conditional logic.

If it is a struct, perhaps the developer may wish to aggregate subsets of the struct into a single value for a given decryption key.

There will be other usage patterns for UTXOs that develop over time that we cannot predict.

UTXOs add significant complexity to developing and managing a private dapp. Question is: who pays?

1. Protocol developers (hide UTXO nature from contract devs and app devs)
2. Contract developers (hide UTXO nature from app devs)
3. App developers (App devs need to understand state is UTXO based and write aggregation functions like we do in the Aztec Connect SDK)

The proposal is that we place the complexity burden on **contract developers** as far as is possible. They are the entity that understand the requirements of their contract and its logic. The protocol's resposibility is to provide clean, easy to express semantics to manipulate UTXOs such that their nature can be abstracted away from app developers.

These are the two 'win' conditions we must hit under this proposal:

> **All contract state required by a dapp can be accessed via contract getter functions.**

> **UTXO commitments are *never* passed in as input parameters to an external-facing contract function**

As an example of what *not* to aim for; in Aztec Connect the user must directly supply input/output note commitments to the join-split function.

## Definition of a private state commitment

A private state commitment is defined by the following:

1. contract address
2. storage slot
3. decryption key
5. state value (probably 32 bytes. TODO: define size)
6. nonce
7. salt

### Contract representation

Private state variables can be represented in one of two forms:

1. Singleton `mapping(address => Object)`
2. Unbounded Array `mapping(address => UArray(Object))`

TODO: How do we initialize singleton variables? (i.e. cannot use patter "pull old value out of the state tree and nullify it, there is no old value")

For a singleton variable, the explicit assumption here is that only the user will be making modifications (e.g. the Object type could be a struct, may, dynamic array etc.)

The `Object` is the type of the storage variable itself (e.g. `u64`). If it does not fit into a single state commitmet, the variable is split across multiple state commitments (and storage slots).

### Unbounded Array-based UTXOs

Simulating arrays is difficult because we need to enable users who are *not* the array owner to be able to *insert* objects into the array.

Beause of this, we cannot track an array length (without leaking information, as everybody would need to know it to perform an `insert`)

Without an array length, we cannot index specific array elements (the user may not know at which index they are inserting into).

#### What *can* be done with unbounded arrays?

* Anyone can `insert` into the array
* Array owners can `remove` array elements
* Array owners can `replace` array elements (syntactic sugar that removes an array element and inserts another in its place)

#### How can we access unbounded array elements

A contract function can request a fixed number of elements from the unbounded array.

We can use rust-style Option semantics to represent the fact that the array elements may be either 'real' or 'gibberish' notes.

### Unbounded array access semantics

(pseudocode)

function get(uint number, function SortFunction, function FilterFunction) returns [Option<ObjectType>; number]

The returned array elements are wrapped in a form of Option type with `is_some, is_none` methods that return boolean values depending on whether the element exists.

The `SortFunction` defines the ordering used. The function declaration is (pseudocode):

SortFunction(ObjectType left, ObjectType right) returns bool

Function returns `true` if `left` is ordered before `right`.

The `FilterFunction` acts similarly to the `SortFunction` and is used to omit UTXOs from the returned array:

FilterFunction(ObjectType v) returns bool

e.g. can be used to omit zero-valued notes.

If no sort/filter functions are provided, default behaviour is to return notes ordered by their position in the state tree.

Q: Is `sort`, `filter` sufficient to build up higher-level abstractions like `map`, `reduce`?

Q: Is it too confusing for `SortFunction` and `FilterFunction` to add constraints? The constraint conditions is weaker than the conditions that apply when operating natively (could call them `SortDirective`, `FilterDirective` to make their functions clearer)

### Sort/Filter semantics

The sort/filter functions generate constraints to ensure that the supplied UTXO objects match the criteria.

However we cannot ensure that UTXOs that *would* have passed the checks have been ommitted.

e.g:

> Alice has UTXO's with values [0, 1, 2].

> The contract has a getter function that gets 2 UTXOs that are sorted from lowest to largest.

> All of `[0, 1]`, `[1, 2]`, `[0, 2]` can be supplied as witnesses that satisfy the constraint checks.

It is impossible to enforce sort/filter logic across all UTXOs without iterating over all UTXOs in-circuit, which is not practical. We need to be able to express these limitations clearly to devs as this is a potential security footgun.

### Access methods for getter functions

We want to be able to support the creation of 'getter' methods that can be used by apps to extract required contract data (e.g. a user's balance of a shielded token).

This requires a method that can get *all* of a user's notes for a given variable.

We can do this by supporting *simulated* functions in Noir. These are functions that, when compiled, produce ACIR++, but *are not compiled into constraints*. i.e. you cannot 'call' these functions in a real transaction.

Simulated functions are not bounded by some Noir rules such as no unbounded loops (this requires extra ACIR++ opcodes that are only valid in a simulated context e.g. conditional branching)

Simulated functions can also access a get-all method on storage variables that returns a vector/dynamic array

get_all(function SortFunction, function FilterFunction) returns Vec<ObjectType>

## Example: re-creating the Join-Split transaction

TODO: use Noir syntax! This uses Solidity-style pseudocode (with rust's Option syntax grafted on...)

private mapping(address => bool) blackList;

function private addToBlackList()
{
    blackList[msg.sender] = true;
}

function private checkNotOnBlackList()
{
    bool isOnBlackList = blackList[msg.sender];
    
    require(isOnBlackList == false);
}

private mapping(address => UnboundedArray<uint256>) _notes;

private antiset(address) _badPeople; 

bool thing_init = false;

function private addBadPerson(address baddie)
{
    _badPeople.insert(baddie);
}

function private checkNotBad()
{
    require(_badPeople.notPresent(msg.sender));
}

function private gimmeThing()
{
    _thing[msg.sender] = 10;
    
    checkInit();
}

function public checkInit()
{
    require(thing_init == false);
    thing_init = true;
}
o
/**
 * combines the user's 2 highest-valued notes into a single note. 
 */
function consolidate()
{
    [Option<uint256>; 2] storage notes = _notes[msg.sender].get(2, sortNotes, filterNote);
    
    require(notes[0].is_some() && notes[1].is_some(), "not enough notes to consolidate");
    notes[0].replace(notes[0].unwrap() + notes[1].unwrap());

    // 2 output notes. Could call 'remove' to produce only 1 ouput note.
    notes[1].replace(0); 
}

/**
 * creates a j-s transaction that gives a note to 'to' worth 'value'
 *
 * Will throw if 2 largest notes are insufficiently large
 *
 * N.B. we could conditionally consolidate notes here if needed but would increase tx costs 
 */
function privateSend(address to, uint256 value)
{

    [Option<uint256>; 2] storage notes = _notes[msg.sender].get(2, sortNotes, filterNote);

    
    uint256 valueSum = notes[0].unwrap_or(0) + notes[1].unwrap_or(0);
    require(valueSum >= value, "insufficient note values. May need to consolidate");

    notes[0].replace(valueSum - value);
    
    // TODO: might need to create a specific option type for an optional-storage var instead of Option. Would be good to have a direct `remove` method on the option that produces a gibberish nullifier if the UTXO is gibberish
    notes[1].remove();
    
    // TODO: define syntax that declares the msg seder is not expected to know the viewing key to _notes[to] (e.g. some 'unknown' keyword)
    _notes[to].insert(value);
}

/**
 * Returns the user's shielded balance.
 * Is a simulate-only function that cannot be executed as part of a tx
 **/
function getShieldedBalance() simulated returns (uint256)
{
    // can only call get_all in simulated functions
    uint256[] storage notes = _notes[msg.sender].get_all(sortNotes, filterNote);
    
    uint256 balance = 0;
    // can have unbounded loops in simulated functions
    for (uint256 i = 0; i < notes.length; ++i)
    {
        balance += notes[i];
    }
    return balance;
}

/**
 * Computes number of note consolidations required before a user can send a note worth `target`.
 * Is a simulate-only function that cannot be executed as part of a tx
 **/
function numConsolidationsForSend(uint256 target) simulated returns (uint256)
{
    uint256[] storage notes = [e-mail]_all(sortNotes, filterNote);


    // uint256[] storage notes = _notes[msg.sender].get_all(sortNotes, filterNote);

    require(notes.length > 0, "insufficient balance");

    uint256 count = 0;
    uint256 consolidatedValue = notes[0];
    for (uint256 i = 1; i < notes.length; ++i)
    {
        if (notes[i] + consolidatedValue >= target)
        {
            return count;
        }
        consolidatedValue += notes[i];
        count++;
    }
    
    require(false, "insufficient balance");
}

## ACIR++ Changes

The `get` method used to extract state adds a significant complexity to ACIR++; the algorithm that is executed during the *simulation* is different to the algorithm that is constrained when generating a circuit.

### Simulated `get`

* Recover *all* UTXOs linked to a given storage key/user
* Iterate over all UTXOs and apply the `sortFunction` and `filterFunction` functions
* If the sorted/filtered UTXOs are less than `number`, add sufficient fake UTXOs
* Return a `number`-sized array

### Circuit `get`

* Present `number` of UTXO objects as witnesses
* Iterate over the UTXOs and apply the `sortFunction` and `filterFunction` functions

## Performing Non-Membership Checks

(TODO: should be moved to protocol architecture spec)

If we want the Noir++ to support 'antisets', datasets where users can prove the non-existence of a key.

We can expose a nullifier set as a basic primitive, but *secure* non-membership checks require specific a pattern is followed due to the following security requirement:

**A unique nullifier can only produce *one* non-membership check**

Non-membership checks are performed by exposing nullifiers to the rollup provider, who then performs the non-membership check into a nullifier set (to avoid race conditions. TODO link to a nullifiers primer)

Repeated exposure of the *same* nullifier reveals part of the transaction graph; that nullifier can becomes an identifier.

### Secure non-membership checks

Each antiset is assigned a state slot $slot_s$ and a nullifier slot $slot_n$

An antiset nullifier for a key $k \in \mathbb{F}$ requires a nullifier $nonce_k$ and is defined as:

$$
H(k, nonce_k, slot_n, contract)
$$

(contract = contract address)

#### Adding to the antiset

The initial nullifier for a given key $k$ uses a nonce value of $0$ i.e. the following nullifier is added:

$$
H(k, 0, slot_n, contract)
$$

(as with all nullifier insertions, the inserted nullifier must also pass a non membersihp check)

#### Proving non-membership of the antiset

For an input key $k$ and $nonce_k$, the circuit requires a non-membership check over the nullifier $H(k, nonce_k, slot_n, contract)$

If $n > 0$ the circuit must *also* prove the *existence* of a leaf in the **state tree** whose value is

$$
H(k, nonce_k, slot_s, contract)
$$

The circuit **adds** the following leaf to the state tree:

$$
H(k, nonce_k + 1, slot_s, contract)
$$

The circuit **adds** the following nullifier to the nullifier set:

$$
H(k, nonce_k + 1, slot_n, contract)
$$

#### Costs of non-membership checks

A non-membership check requires adding 1 note to the state tree and 1 note to the nullifier set i.e. not read-only!

### Privacy considerations for non-membership checks

If Alice wishes to add Bob to an antiset, she must choose a nullifier key $k$ that corresponds to Bob's identity.

This is not hiding. [TODO explain how hiding can be done in a semitrusted setting]

## Non-membership check contract semantics