Trees
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
- Hash of the reputation:
const hashReputation = hash(posRep, negRep, graffiti, signUp)
where
posRep
is the positive reputation given by the attesternegRep
is the negative reputation given by the attestergraffiti
is the message given by the attestersignUp
indicates if the attester authenticates the user
If there is no reputation from attester, then the leaf stores a default reputation:
const defaultReputation = hash(0,0,0,0)
The index 0
is reserved to have no reputation (default reputation) since the attester ID starts from index 1
.
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.
- It is an incremental merkle tree with it's leaves storing users'
identityCommitment
s anduserStateRoot
s, e.g.,- a global state tree leaf:
hash(identityCommitment, userStateTreeRoot)
- The default leaf is
0
- a global state tree leaf:
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.
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
const hashChainResult = hash(attestation_3, hash(attestation_2, hash(attestation_1, 0)))
const sealedHashChain = hash(1, hashChainResult)
The hash chain is sealed because it prevents epoch keys from receiving attestations anymore.
See: Epoch Transition
An attestation includes the following data:
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;
}
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