# 2.0.0-alpha-4

A wholistic overview of the Universal Reputation protocol.

## Functional overview

UniRep is a protocol for storing arbitrary user data for a private key. We store a total of 1024 bits of data for each private key. This data cannot be mapped to a user without knowing the user private key. **User data can only be revealed with user consent.**

- The first 512 bits are combined using addition.
- The remaining 512 bits are combined using a repacement scheme
- The first 256 bits of this is data that can be replaced, the second 256 bits is the last replacemement timestamp (using only 64 bits).

We represent each block of 256 bits as an unsigned integer. We define a schema for this data:

- `uint256[0]`: positive reputation
- `uint256[1]`: negative reputation
- `uint256[2]`: graffiti
- `uint256[3]`: timestamp

Note that in future versions we will likely allow attesters to define their own schema.

## Data structures

Some data structures you will need to understand.

### Incremental Merkle Tree

A merkle tree where leaves are incrementally added.

Anonymous operations:
- prove membership

### Sparse Merkle Tree

A merkle tree where the index of each leaf is deterministic (typically the result of a hash function).

Anonymous operations:
- prove membership
- prove non-membership

### Hashchain

A hashchain is created by hashing many elements together in sequence.

For items `[v0, v1, v2, v3]`

chain = H(v3, H(v2, H(v1, H(0, v0))))

alternatively with pseudo code

func hash2(items: [])

const items: bigint[4]
let chain = hash2([0, items[0]])
chain = hash2([chain, items[1]])
chain = hash2([chain, items[2]])
chain = hash2([chain, items[3]])

## Architecture

We store userdata on behalf of attesters. Each user has different data for each attester. Data is accessed by calculating a path of combination through the data structures. This path is mostly calculated using the private key and hash operations.

### Unirep

The Unirep contract stores a mapping of attesters. Each attester is identified by Ethereum address. Attesters may be contracts or EOA.

### Attester

Each attester has a struct in the Unirep contract:

struct AttesterData {
  // epoch keyed to tree data
  mapping(uint256 => IncrementalTreeData) stateTrees;
  // epoch keyed to root keyed to whether it's valid
  mapping(uint256 => mapping(uint256 => bool)) stateTreeRoots;
  // epoch keyed to root
  mapping(uint256 => uint256) epochTreeRoots;
  uint256 startTimestamp;
  uint256 currentEpoch;
  uint256 epochLength;
  mapping(uint256 => bool) identityCommitments;
  IncrementalTreeData semaphoreGroup;
  // attestation management
  mapping(uint256 => EpochKeyState) epochKeyState;
}

This forms a few logical structures:

#### Semaphore group

Each attester has a semaphore group. A user joins the group when they signup by adding their [identity commitment]() to an incremental merkle tree `semaphoreGroup`. We also store a boolean mapping for non-anonymous queries `identityCommitments`.

See the "Semaphore Identity" section [here](https://semaphore.appliedzkp.org/docs/glossary#semaphore-identity) to understand the `identityCommitment`.

#### Division of time into epochs

Each attester has a `startTimestamp`, `epochLength` and `currentEpoch`.

We define the current epoch as `Math.floor((block.timestamp - startTimestamp)/epochLength)`.

We use `currentEpoch` to track which epoch the attester has seen.

#### Proofs about user data (State Tree)

To participate in an epoch a user must assert some truth about their user data. Specifically they must calculate a publicly seen value containing their current reputation balance.

This value is used to prove the user data at the start of the epoch.

We can define the latest user data as `start data + previous epoch changes`.

The user inserts a leaf into this tree so that they can make proofs about their start balance anonymously for the rest of the epoch.

#### Changes to user data (Epoch Tree)

When a user receives an attestation, the attester is asserting a change to the user data. If you combine all the changes received by a single user, you have the latest user state.

The epoch tree stores the combined changes for each epoch key, for a single epoch.

If you combine the balance for the epoch keys a user controls you have the balance received for a user in an epoch. If you combine all the balances received by all the user epoch keys, in all epochs, you have the user total balance.

Each attester has a new epoch tree for each epoch. The index of the leaf in the epoch tree is the epoch key.

Attesters can give reputation to members by epoch key. One function of an epoch key is that of inbox.

#### Constructing epoch tree

The epoch tree has to be very large because each epoch key is a hash. Thus epoch keys are distributed randomly over the leaves of the tree. Therefore we need a number of leaves that is collision resistant, minimum `2^100`.

As a result it's not feasible to store the entire tree on chain.

Instead we store only the root onchain and build the root in ZK. To do this we have to track a few things.

Each attester has an `EpochKeyState` for each epoch.

struct EpochKeyState {
  mapping(uint256 => EpochKeyHashchain) hashchain;
  uint256 totalHashchains;
  uint256 processedHashchains;
  mapping(uint256 => Reputation) balances;
  mapping(uint256 => bool) isKeyOwed;
  uint256[] owedKeys;
}

When an epoch key receives an attestation it is combined with the other attestations the epoch key has received. The total epoch key balance is stored publicly on chain.

To update the epoch tree we generate a zk proof that inserts some number of leaves into the tree.

The proof outputs a hashchain of the leaves that were inserted into the tree. See the hashchain proof ([aggregate epoch key proof](https://developer.unirep.io/docs/next/circuits-api/circuits#aggregate-epoch-keys)).

Note the input `epoch_key_balances`. We take these as private inputs and make sure they are included in the hashchain. As a result we can insert an arbitrary number of leaves into the tree using a single public output.

## Operations

Actors in the system can prove truths about the system state using ZK, and modify the internal state of the system. ZK lets us prove some computations happened and created some output.

### User state transition

In the current protocol there are two ways for a user to generate a state tree leaf:

- signup
- perform a user state transition

In the user state transition the user generates a membership proof for the last epoch state, and (multiple) membership proofs for the current epoch tree.

The user combines their start balance with the changes received at each epoch key they control. The user thus proves their latest balance, and outputs it in a state tree leaf for the new epoch.

### Attestation

An attester makes an attestation to an epoch key, which specifies some change to the user data. This change is applied to the `epochKeyState` for the attester current epoch.

The attester uses the aggregate epoch key proof to finalize epoch key balances into the epoch tree root.