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