# Note Attestation Spec Implementation
An external partner (who wishes to remain anonymous) did some work on note attestation. These are their notes:

Contracts and frontend: https://github.com/AztecProtocol/token-partition-table

## Original Spec
Reference: https://hackmd.io/O7RKI5lfQnqVVVKQYer75g

### Token
The contract extends the normal token contract by adding a Partition table to each note.

struct Shield {
    id: u32,
    value: U128,
}

struct PartitionTable {
    shields: Shield[],
    attestations: Address[],
    is_table_cleared: bool,
    max_block_number: u64,
}

#### Transfers
Each transfer (join-split interaction) then should follow the following rules:
* If `isTableCleared = true` for any input note, `isTableCleared = true` for all output notes and shields is empty
* If `isTableCleared = false` for all input notes, the shields entries for all output notes are consistent with the sheilds entries for all input notes
* `blockNumber` for all output notes is the max value of `blockNumber` for all input notes
* The `attestations` array for output notes is the set intersection of input note attestations

#### Unshielding
On `unshield`, the list of all `attestations` should be optionally broadcast as events.

#### Interface

#[aztec(private)]
fn request_attestation(note: TokenNote, attestor: AztecAddress) -> bool;
#[aztec(public)]
fn has_attestation(note: TokenNote, attestors: [AztecAddress]) -> bool;

### Attestor
The attestor contract contains a list of blacklisted shield IDs and must be accessible via private functions.

#### Interface

#[aztec(public)]
pub fn add_to_blacklist(token_address: AztecAddress, shield_id: u32);
#[aztec(public)]
pub fn remove_from_blacklist(token_address: AztecAddress, shield_id: u32);

#[aztec(private)]
pub fn request_attestation(table: PartitionTable, attestor: AztecAddress) -> bool;

## Work done
### Token
The token contract with partition table extends the [sample token contract](https://github.com/AztecProtocol/aztec-packages/tree/4064e1808c7113e2f5cbc2ce8fbb05b8c70f0b97/noir-projects/noir-contracts/contracts/token_contract) in the Aztec monorepo.

#### State
A new field `num_shields` is added to track the total number of shielded notes.

struct Storage {
    ...
    balances: BalancesMap<TokenNote>,
    pending_shields: PrivateSet<TransparentNote>,
    num_shields: PublicMutable<u32>,
}

A `partition_table` field is added to `TokenNote` as described in the spec.

struct TokenNote {
    ...
    partition_table: PartitionTable,
}

A `block_number` field is added to `TransparentNote` which stores the block number at which the note was shielded. This field is zero for notes minted through `mint_private`.

struct TransparentNote {
    ...
    block_number: Field,
}

#### `shield`
Modified to include the current `block_number` value in the created `TransparentNode`.

#[aztec(public)]
fn shield(from: AztecAddress, amount: Field, secret_hash: Field, nonce: Field) {
    if (!from.eq(context.msg_sender())) {
        // The redeem is only spendable once, so we need to ensure that you cannot insert multiple shields from the same message.
        assert_current_call_valid_authwit_public(&mut context, from);
    } else {
        assert(nonce == 0, "invalid nonce");
    }

    let amount = U128::from_integer(amount);
    let from_balance = storage.public_balances.at(from).read() - amount;

    let pending_shields = storage.pending_shields;
-    let mut note = TransparentNote::new(amount.to_integer(), secret_hash);
+    let mut note = TransparentNote::new(amount.to_integer(), context.block_number(), secret_hash);


    storage.public_balances.at(from).write(from_balance);
    pending_shields.insert_from_public(&mut note);
}

#### `redeem_shield`
Modified to add a partition table to the created token note. There are two cases depending on if the call follows a:

* Mint transaction –> table is empty and `max_block_number` is zero
* Shield transaction –> table is initialized with the current `num_shields` as the single shield ID and `max_block_number` is set as the block number from the transparent note

#[aztec(private)]
-fn redeem_shield(to: AztecAddress, amount: Field, secret: Field) {
+fn redeem_shield(to: AztecAddress, amount: Field, block_number: u64, secret: Field, num_shields: u32) {
    let pending_shields = storage.pending_shields;
    let secret_hash = compute_secret_hash(secret);
    // Get 1 note (set_limit(1)) which has amount stored in field with index 0 (select(0, amount)) and secret_hash
    // stored in field with index 1 (select(1, secret_hash)).
    let options = NoteGetterOptions::new().select(TransparentNote::properties().amount, amount, Option::none()).select(
        TransparentNote::properties().secret_hash,
        secret_hash,
        Option::none()
    ).select(
        TransparentNote::properties().is_shield,
        is_shield,
        Option::none()
    ).set_limit(1);
    let notes = pending_shields.get_notes(options);
    let note = notes[0].unwrap_unchecked();
    // Remove the note from the pending shields set
    pending_shields.remove(note);

+    let pt = if block_number > 0 {
+        let selector = FunctionSelector::from_signature("_assert_num_shields_and_increment(Field)");
+        let _void = context.call_public_function(context.this_address(), selector, [num_shields.to_field()]);
+        PartitionTable::default().set_max_block_number(block_number).add_shield_id(num_shields)
+    } else {
+        PartitionTable::default()
+    };
    // Add the token note to user's balances set
-    storage.balances.add(to, U128::from_integer(amount));
+    storage.balances.add(to, U128::from_integer(amount), pt);
}

* `block_number`: Block number at which shield was called. Zero if mint was called
* `num_shields`: Current value of public `num_shields` state variable (can be omitted when private calls can access public state)

#### `transfer`
A transfer consumes 𝑁 input notes of the sender and creates two output notes, one for the receiver containing the amount sent and one for the sender containing the change left.

The transfer function is modified to account for splitting and joining partition tables during a token transfer.

#[aztec(private)]
fn transfer(from: AztecAddress, to: AztecAddress, amount: Field, nonce: Field) {
    // docs:start:assert_current_call_valid_authwit
    if (!from.eq(context.msg_sender())) {
        assert_current_call_valid_authwit(&mut context, from);
    } else {
        assert(nonce == 0, "invalid nonce");
    }
    // docs:end:assert_current_call_valid_authwit

    let amount = U128::from_integer(amount);
-    storage.balances.sub(from, amount);
+    let pt = storage.balances.sub(from, amount);
    // docs:start:increase_private_balance
-    storage.balances.add(to, amount);
+    storage.balances.add(to, amount, pt);
    // docs:end:increase_private_balance
}

The `sub` function contains the logic of choosing which notes to consume 𝑁 and returns a partition table generated by combining the consumed notes.

pub fn sub<T_SERIALIZED_LEN>(
    self: Self,
    owner: AztecAddress,
    subtrahend: U128
-) where T: NoteInterface<T_SERIALIZED_LEN> + OwnedNote {
+) -> PartitionTable where T: NoteInterface<T_SERIALIZED_LEN> + OwnedNote {
    // docs:start:get_notes
    let options = NoteGetterOptions::with_filter(filter_notes_min_sum, subtrahend);
    let maybe_notes = self.map.at(owner).get_notes(options);
    // docs:end:get_notes

+    let mut pt1 = PartitionTable::default();
+    let mut pt2 = PartitionTable::default();
    let mut minuend: U128 = U128::from_integer(0);
    for i in 0..maybe_notes.len() {
        if maybe_notes[i].is_some() {
            let note = maybe_notes[i].unwrap_unchecked();

            // Removes the note from the owner's set of notes.
            // This will call the the `compute_nullifer` function of the `token_note`
            // which require knowledge of the secret key (currently the users encryption key).
            // The contract logic must ensure that the spending key is used as well.
            // docs:start:remove
            self.map.at(owner).remove(note);
            // docs:end:remove

+            pt1 = pt1.join(note.get_partition_table());
+            pt2 = note.get_partition_table();

            minuend = minuend + note.get_amount();
        }
    }

    // This is to provide a nicer error msg,
    // without it minuend-subtrahend would still catch it, but more generic error then.
    // without the == true, it includes 'minuend.ge(subtrahend)' as part of the error.
    assert(minuend >= subtrahend, "Balance too low");
-    self.add(owner, minuend - subtrahend);
+    self.add(owner, minuend - subtrahend, pt2);

    pt1
}

At the moment, the function doesn't use the `is_table_cleared` flag from the spec and only enforces the following constraints when combining partition tables

* `shield_ids` are the set union of the `shield_ids` of consumed partition tables
* `attestations` are the set intersection of the `attestations` of partition tables
* `max_block_number` is the maximum of the `max_block_number` of partition tables

while the partition table of the change note that is left is the same as the partition table of the last partially consumed note.

Note

At a high level, a correct transfer can be thought of as a function that consumes 𝑁 input notes to create 𝑀 output notes where the constraints are:

* $\sum_{N} Amount_{input} = \sum_{M} Amount_{output}$
* Partition table consistency

This can be thought of an instance of the [partition problem](https://en.wikipedia.org/wiki/Partition_problem) with more constraints to check partition table consistency. An ideal solution would be to compute the partitions (notes) off-chain and only verify the solution inside the contract.

One way to do it in Aztec would be to fetch the notes to be consumed off-chain, come up with output notes that satisfy the consistency checks and then call a `transfer` function with both sets. The contract would then do the following:
* Check sender has/owns the input notes
* Check input and output notes are consistent based on the above constraints
* Do appropriate transfers

To check partition table consistency, you might also have to send how subsets of input notes are combined to get output notes.

The issue is that in Aztec/Noir, there's no easy way to enforce the first check. Notes are stored in a usually accessed by [`PrivateSet::get_note()`](https://github.com/AztecProtocol/aztec-packages/blob/4064e1808c7113e2f5cbc2ce8fbb05b8c70f0b97/noir-projects/aztec-nr/aztec/src/state_vars/private_set.nr#L73-L89) which requires a [`NoteGetterOptions`](https://github.com/AztecProtocol/aztec-packages/blob/4064e1808c7113e2f5cbc2ce8fbb05b8c70f0b97/noir-projects/aztec-nr/aztec/src/note/note_getter_options.nr#L81-L89) argument. Iterating over each note and calling this function to check a note's existence increases complexity.

To make the problem simpler, I've assumed 𝑀=2 output notes and the heuristic for combining notes is just a greedy algorithm where you consume notes in the order they were created until you reach the required amount.

#### `request_attestation`
Wrapper around an attestor's `request_attestation`. Since notes cannot be passed as arguments, it instead finds the unattested note at offset `note_offset` and calls the attestor with the partition table of this note. If none of the note's `shield_ids` are in the attestor's blacklist, the attestor returns true and the attestor's address is added to the partition table's `attestations` array.

#[aztec(private)]
fn request_attestation(
    from: AztecAddress,
    attestor: AztecAddress,
    note_offset: u32,
    proofs: [Field; DEPTH * BOUNDED_VEC_LEN],
    blacklist_root: Field,
    nonce: Field
) {
    if (!from.eq(context.msg_sender())) {
        assert_current_call_valid_authwit(&mut context, from);
    } else {
        assert(nonce == 0, "invalid nonce");
    }

    let maybe_note = storage.balances.unattested_note_at_offset(from, attestor, note_offset);
    let mut attested = false;

    if maybe_note.is_some() {
        let note = maybe_note.unwrap_unchecked();
        attested = Attestor::at(attestor).request_attestation(&mut context, note.partition_table, proofs, blacklist_root)[0] as bool;
    }

    if attested {
        storage.balances.add_attestation(from, maybe_note.unwrap(), attestor);
    }
}

* `from`: Address requesting an attestation
* `attestor`: Address of the attestor contract
* `note_offset`: Offset of the note to request attestation for (out of all unattested notes for this attestor)
* `proofs`: Flat array containing non-inclusion proofs of each shield_id in partition table
* `blacklist_root`: Current blacklist root for the calling token in the attestor contract (can be omitted when private calls can access public state)

#### `unshield`
Consumes 𝑁 notes and adds the cumulative amount to public balance. Modified to emit attestations of the combined consumed notes as public logs.

#[aztec(private)]
fn unshield(from: AztecAddress, to: AztecAddress, amount: Field, nonce: Field) {
    if (!from.eq(context.msg_sender())) {
        assert_current_call_valid_authwit(&mut context, from);
    } else {
        assert(nonce == 0, "invalid nonce");
    }

-    storage.balances.sub(from, U128::from_integer(amount));
+    let pt = storage.balances.sub(from, U128::from_integer(amount));

+    for i in 0..pt.attestations.max_len() {
+        if i < pt.attestations.len() {
+            emit_unencrypted_log_from_private(&mut context, pt.attestations.at(i));
+        }
+    }

    let selector = FunctionSelector::from_signature("_increase_public_balance((Field),Field)");
    let _void = context.call_public_function(context.this_address(), selector, [to.to_field(), amount]);
}

### Attestor
The blacklist is maintained off-chain as a sparse merkle tree (SMT) and the attestor stores the root of this tree in public state.

#### State

struct Storage {
    admin: PublicMutable<AztecAddress>,
    blacklists: Map<AztecAddress, PublicMutable<Field>>,
}

* `admin`: Address of account that can modify the contract state
* `blacklists`: Mapping between a token address and the current root of the blacklist SMT for this token

#### `add_to_blacklist`
Adds a `shield_Id` to a token's blacklist and updates the blacklist's merkle root. It first verifies that shield_id not already present in the blacklist.

#[aztec(public)]
pub fn add_to_blacklist(token: AztecAddress, shield_id: Field, proof: [Field; DEPTH]) {
    assert(storage.admin.read().eq(context.msg_sender()), "caller is not admin");

    let mut old_root = storage.blacklists.at(token).read();
    if old_root == 0 {
        old_root = EMPTY_ROOT;
    }
    let new_root = smt::insert(shield_id, old_root, proof);

    storage.blacklists.at(token).write(new_root);

    emit_unencrypted_log(&mut context, token);
    emit_unencrypted_log(&mut context, shield_id);
}

* `token`: Address of the token for fetching the blacklist
* `shield_id`: Element that should be added to the blacklist
* `proof`: Merkle proof that `shield_id` is not present in blacklist

#### `remove_from_blacklist`
Removes a `shield_Id` from a token's blacklist and updates the blacklist's merkle root. It first verifies that `shield_id` is present in the blacklist.

#[aztec(public)]
pub fn remove_from_blacklist(token: AztecAddress, shield_id: Field, proof: [Field; DEPTH]) {
    assert(storage.admin.read().eq(context.msg_sender()), "caller is not admin");

    let old_root = storage.blacklists.at(token).read();
    let new_root = smt::remove(shield_id, old_root, proof);

    storage.blacklists.at(token).write(new_root);

    emit_unencrypted_log(&mut context, token);
    emit_unencrypted_log(&mut context, shield_id);
}

* `token`: Address of the token for fetching the blacklist
* `shield_id`: Element that should be removed from the blacklist
* `proof`: Merkle proof that `shield_id` is present in blacklist

#### `request_attestation`
A token contract calls this function with a partition_table that needs attestation along with merkle proofs that the `shield_ids` in the partition_table are not part of the blacklist. The function iterates over all the `shield_ids` and returns true if none of them is part of the blacklist. This is done using a non-inclusion check in an SMT.

#[aztec(private)]
fn request_attestation(
    partition_table: PartitionTable,
    proofs: [Field; DEPTH * BOUNDED_VEC_LEN],
    blacklist_root: Field
) -> bool {
    let token = context.msg_sender();

    let selector = FunctionSelector::from_signature("_assert_blacklist_root((Field),Field)");
    context.call_public_function(
        context.this_address(),
        selector,
        [token.to_field(), blacklist_root]
    );

    let shield_ids = partition_table.shield_ids;
    let mut res = true;
    let mut proof = [0; DEPTH];
    for i in 0..shield_ids.max_len() {
        if i < shield_ids.len() {
            for j in 0..DEPTH {
                proof[j] = proofs[i * DEPTH + j];
            }
            if !smt::verify(shield_ids.at(i), blacklist_root, proof) {
                res = false;
            }
        }
    }
    res
}

* `partition_table`: Partition table of the note that needs to be attested
* `proofs`: Flat array containing non-inclusion proofs of each shield_id in partition table
* `blacklist_root`: Current blacklist root for the calling token (can be omitted when private calls can access public state)

## Future work
* Update partition table consitency check to take `is_table_cleared` flag into account
* Recursively call `request_attestation` for all notes in a call
* Use `SharedMutable` when ready instead of passing public state values and asserting in a public function
* More esoteric ways of combining notes during a transfer
* Replace `shield_id` array with a merkle tree and do inclusion checks when needed
* Partition table consistency and blacklist non-intersection check can possibly be written in a separate SNARK and only recursively verified in the contract