> For the complete documentation index, see [llms.txt](https://unirep.gitbook.io/unirep/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/protocol/glossary/trees.md).

# Trees

The tree structures that are used in UniRep protocol.

## **User state tree**

* A user state tree is a **sparse merkle tree** with it's leaves storing reputation received from each attester, e.g.,
  * a user state tree leaf = hash of the reputation

![An example of user state tree with only reputation from attester 3.](https://1939836936-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mb9Vp6gNlb57m_A4qKo%2Fuploads%2F7DgZz7SavZtxQPdvDN2Q%2F2.png?alt=media\&token=21957d4e-d77f-47fb-bd0f-79a32150afcb)

* Hash of the reputation:

```typescript
const hashReputation = hash(posRep, negRep, graffiti, signUp)
```

where

* `posRep` is the positive reputation given by the attester 
* `negRep` is the negative reputation given by the attester 
* `graffiti` is the message given by the attester 
* `signUp` indicates if the attester authenticates the user

If there is no reputation from attester, then the leaf stores a default reputation:

```typescript
const defaultReputation = hash(0,0,0,0)
```

{% hint style="info" %}
The index `0` is reserved to have no reputation (default reputation) since the attester ID starts from index `1`.
{% endhint %}

## **Global state tree**

* A global state tree stores the updated user state after a user signs up and a user performs the [user state transition](/unirep/protocol/glossary/user-state-transition.md).
* It is an **incremental merkle tree** with it's leaves storing users' `identityCommitment`s and `userStateRoot`s, e.g.,
  * a global state tree leaf: `hash(`<mark style="color:green;">`identityCommitment`</mark>`,`` `<mark style="color:red;">`userStateTreeRoot`</mark>`)`
  * The default leaf is `0`

![An example of global state tree](https://1939836936-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mb9Vp6gNlb57m_A4qKo%2Fuploads%2FAU9COFiupghXkQaGJKtz%2F3.png?alt=media\&token=cfde226e-835e-4082-bc32-64bd5306c28b)

{% hint style="info" %}
**NOTE:** this is an incremental merkle tree so leaves are inserted from left (leaf index 0) to right, one by one, instead of inserted directly into the specified leaf index.

**NOTE:** since global state tree leaf is the hash of `identityCommitment` and `userStateRoot`, others will be not be able to tell which user (his `identityCommitment`) inserted his user state into global state tree.
{% endhint %}

## **Epoch tree**

* An epoch tree is used to **prevent users from omitting any attestation** attesting to the user. If the user skip one attestation, the hash chain and the output epoch tree root will be different from others.
* An epoch tree is a **sparse merkle tree** with it's leaves storing hashchain results of each epoch key, e.g.,
  * leaf index: epoch key
  * leaf value: sealed hash chain\
    The sealed hash chain is computed by

```typescript
const hashChainResult = hash(attestation_3, hash(attestation_2, hash(attestation_1, 0)))
const sealedHashChain = hash(1, hashChainResult)
```

{% hint style="info" %}
The hash chain is **sealed** because it prevents epoch keys from receiving attestations anymore.\
See: [Epoch Transition](/unirep/protocol/glossary/epoch-transition.md)
{% endhint %}

![An example of epoch tree with epoch key 1 and epoch key 3 has non-zero attestations.](https://1939836936-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-Mb9Vp6gNlb57m_A4qKo%2Fuploads%2FaLGqVJPZXkZlnmemwGsU%2Fepoch%20tree.png?alt=media\&token=76cad797-a24c-4c08-be83-3790133f1cb1)

An attestation includes the following data:

```solidity
struct Attestation {
  // The attester’s ID
  uint256 attesterId;
  // Positive reputation
  uint256 posRep;
  // Negative reputation
  uint256 negRep;
  // A hash of an arbitary string
  uint256 graffiti;
  // A flag to indicate if user has signed up in this leaf
  uint256 signUp;
}
```

{% hint style="info" %}
A reputation includes the following data: `posRep, negRep, graffiti, signUp`.\
It does not include `attesterId` like an attestation does because reputation is already stored in user state tree with `attesterId` as leaf index\
See: [Reputation](/unirep/protocol/glossary/reputation.md)
{% endhint %}