Links

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
      ii
      exists
    • Default nullifier leaf: hashLeftRight(0, 0)
    • If nullifier of index
      ii
      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