> For the complete documentation index, see [llms.txt](https://unirep.gitbook.io/unirep-social/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://unirep.gitbook.io/unirep-social/definition/trees.md).

# Trees

The definition of trees used in Unirep

### User state tree

```
                              user state tree root
                              /                  \
  hash(DEFAULT_REP_HASH, 0xabc...)              hash(0xbcd..., 0xcde...)
         /        \                                      /         \
[No rep for leaf 0] [leaf 1: 0xabc...]              [leaf 2: 0xbcd...] [leaf 3: 0xcde...]
```

* Tree structure: Sparse merkle tree
* Leaf definition:
  * Hash of reputation
  * Default user state tree leaf: `hash5(0, 0, 0, 0, 0)`
  * User state tree leaf: `hash5( positive reputation, negative reputation, graffiti, 0, 0)`
* The index of each leaf is the attester id
* Updated when user state transition
* Only user has semaphore identity can generate his user state tree

### Global state tree

```
                            global state tree root
                            /                \
        hash(0xabc..., 0xcde...)         hash(0xdef..., DEFAULT_EMPTY_HASH)
               /        \                          /         \
[leaf_0: 0xabc...] [leaf_1: 0xcde...] [leaf_2: 0xdef...] [DEFAULT_EMPTY_HASH]
```

* Tree structure: Incremental merkle tree
* Leaf definition:  
  * Hash of user state
  * Default global state tree leaf: `hash5(0, default user state root, 0, 0, 0)`
  * Global state tree leaf: `hash5( user_id_commitment, user_state_tree_root, transitioned_positive_reputation, transitioned_negative_reputation, 0 )`
* The index is inserted from left (leaf index 0) to right, one by one, instead of inserted directly into the specified leaf index
* Updated when a new user signs up or user state transition
* Each epoch exists its global state tree
* Global state tree is public to every user

### Epoch tree

```
                              epoch tree root
                             /               \
    hash(DEFAULT_EMPTY_HASH, 0x123...)   hash(DEFAULT_EMPTY_HASH, 0x456...)
          /             \                      /                  \
[DEFAULT_EMPTY_HASH]  [epk_1: 0x123...]    [DEFAULT_EMPTY_HASH]  [epk_3: 0x456...]
```

* Tree structure: Sparse merkle tree
* Leaf definition: 
  * hash chain result of reputation received by an epoch key
  * default sealed hash chain result: `hash(1,0)`
  * Sealed hash chain result: `hashChainResult = hash( 1, hash(attestation_i, hash(attestation_{i-1}, hash(attestation_{i-2, ...))))`
* The index of each leaf is the epoch key
* Generated after epoch transition and it is used for user state transition
* Epoch tree is public to every user

### Nullifier tree

```
              nullifier tree root
            /                     \
    hash(1, 0)                     hash(0, 1)
   /          \                    /         \
[leaf 0: 1]  [leaf 1: 0]       [leaf_2: 0] [leaf_3: 1]
```

* Tree structure: Sparse merkle tree
* Leaf definition:
  * Indicate whether the nullifier of index $$i$$ exists
  * Default nullifier leaf: `hashLeftRight(0, 0)`
  * If nullifier of index $$i$$ exists, it leaf becomes: `hashLeftRight(1, 0)`
* The index of each leaf is the submitted nullifier
* Updated when attestation nullifiers, epoch key nullifiers and reputation nullifiers submitted
* Nullifier tree is public to every user