Skip to main content
Version: next

Trees

Each attester has an epoch tree and a state tree that is overwritten each epoch. Attesters also have a history tree that stores all the final state tree/epoch tree root combinations.

State tree

  • The state tree stores the updated user state after a user signs up and after a user state transition is performed.

  • This is an incremental merkle tree, with its leaves storing users' identitySecrets and starting data, e.g.

    • a state tree leaf: H(H(identitySecret, attesterId + (epoch << 160) + (chainId << 208)), H(data))
      The combined field looks like:

      chain idepochattester id
      36 bits48 bits160 bits
    • The hashchain of data is computed by: hashchain = H(hashchain, data[i])

    • The default state tree leaf is 0

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 state tree leaf is the hash of identitySecret and other values, observers are not able to determine which user has inserted leaves into the tree.

Epoch tree

  • An epoch tree is used to track the data received by epoch keys. Non-repudiability is enforced at the circuit and smart contract level.

  • This is an incremental merkle tree, with its leaves storing the hash of epoch key and data received, e.g.,

    • leaf value: H(epochKey, H(data[0]), H(data[1]), ... H(data[n]))

The epoch tree exists onchain and is overwritten each epoch. Only the tree root is stored.

info

See also: Data

History tree

  • The history tree tracks valid combinations of state tree roots and epoch tree roots. When an epoch ends an entry is added.

  • This is an incremental merkle tree with it's leaves storing the hash of a state tree root and epoch tree root

    • leaf value: H(stateTreeRoot, epochTreeRoot)

The history tree exists onchain. Each attester has their own history tree.