# Change Tree

An efficient approach to state managment in unirep.

## Requirements

The `Epoch Tree` data structure stores the changes that have been applied to each epoch key within an epoch. In this tree we must do an inclusion proof and a non-inclusion proof.

The user must prove that their changes are some value `X` and that this value exists at a specific place in the tree; or the user must prove that their changes are 0 and their leaf either does not exist in the tree, or has a 0 value.

## Current Approach

We use a sparse merkle tree to store the changes for each epoch key. The index of each key in the tree is calculated psuedo-randomly using a hash function modulus the cardinality of the leaves. As a result the tree must be large to prevent collisions.

We use a ZK proof to build the tree offchain and publish only the root onchain.

## New Approach

Instead of a sparse merkle tree we can use a sorted incremental merkle tree to prove both inclusion and non-inclusion. This approach adds some complexity in constructing the tree, but should reduce the size of the tree by up to 60-80%. e.g. 2^100 elements reduced to 2^20.

The number of leaves in the tree determines the number of unique epoch keys that can receive attestations in a single epoch. Depending on the epoch length this could be a relatively small tree.

## Advantages

### No collision risk

Epoch keys do not need to have a modulus applied. We can use the full hash value as the user identifier and reduce the risk of collision.

### No modulus bias

To make the large epoch tree more efficient we use a non-binary tree. We then take the epoch key hash modulus the number of leaves in the tree. Because the numbers are not evenly divisible there is a modulus bias introduced, where some numbers are more likely than others.

### Reduced UST time complexity

By reducing the tree size we make the UST proof much smaller. It becomes feasible to increase the number of epoch keys per epoch without the proof becoming intractable on a user device.

## Disadvantages

### ModExp

The polynomial hash function requires modular exponentiation over the curve field in solidity. This requires us to use the modexp precompile and introduces some complexity.

This can be isolated in a library and made easy to use via addition/subtraction functions.

### Complexity

This approach is marginally more complex than the existing hashchain approach. The ZK proofs used by the attester will be more complex, but much smaller.

### Processing

This approach requires the epoch to be sealed before the tree ZK proofs are made. This introduces a small delay between when an epoch starts and when a user can execute a UST.

A similar delay exists in the current system, but the attester can avoid it by pre-processing epoch keys before the epoch ends. If keys are changed the attester simply has to make extra proofs.

## Implementation

The scheme for building a sorted incremental tree is very similar to building a large SMT in ZK. As attestations are made we build a set of epoch keys and their balances on chain. This can be stored in a mapping.

As epoch keys are seen a hashchain is built with each key as an entry. This hashchain is of the form: `epk1 * R + epk2 * R^2 + epk3 * R^3 + ...` where `R` is a strong random value. Using this approach each epoch key has an index in the hashchain, and the hashchain can be built out of order. e.g. `epk3 * R^3 + epk1 * R + epk2 * R^2`. Individual elements in the chain can be efficiently updated by subtracting the old value and adding the new value (without recalculating all other values).

This hashchain will contain not just the epoch key, but instead `H(epk, posRep, negRep, graffiti, timestamp)`.

When the epoch ends we build the incremental tree offchain in ZK. For simplicity assume we're doing one large proof. The epoch keys are provided to the proof in sorted order. Each epoch key must be greater than the previous epoch key during insertion. Duplicate entries are not allowed. Included with each epoch key is the `posRep`, `negRep`, `graffiti`, `timestamp` and `hashchainIndex`. The proof outputs a merkle root, and calculates the hashchain of all the keys that were processed.

This proof is verified onchain, and the hashchain output is compared to the value stored onchain. If the values match the epoch is sealed and users can begin executing user state transitions.

### User State Transitions

During UST for each epoch key the user will either prove the balance in the change tree, or prove that the epoch key does not exist in the change tree.

If the key exists in the tree an inclusion proof is made. This is the same as proving inclusion in any other tree, simply provide a list of sibling leaves.

If the key does not exist in the tree a non-inclusion proof must be made. This is done by proving that a key greater than and a key less than the user epoch key exists in the tree, and that the keys are next to each other. This could be said as: if element X were to exist in a sorted list it must be between element W and element Y. If element W and Y are next to each other element X does not exist in the list.

Technically a non-inclusion proof is two separate inclusion proofs, but because the leaves are next to each other they must share a common merkle path and can thus be optimized to cost the same as a single inclusion proof.