Trees
The definition of trees used in Unirep
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 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 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 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 indexexists
- Default nullifier leaf:
hashLeftRight(0, 0) - If nullifier of indexexists, 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
Last modified 1yr ago