Polygon ID

Merkle Trees

Merkle trees allow us to quickly check membership through Merkle proofs. When searching for a data block’s presence within a Merkle Tree, all that’s needed are the blocks on the path from the data block to the root and each of the data block’s siblings on the way up. The rest of the tree is ignored, as these blocks are enough to allow verification of the hashes all the way up to the root of the tree. The idea is to recalculate the root by recursively hashing the data. If the calculated root is equal to the on-chain root, it proves that the data block exists within the Merkle tree.

This means that if there are n nodes in the tree, only about log(n) items need to be shown. Since each step just requires computing the hash of the child block, it takes about log(n) time for us to verify it. Even if the Merkle tree contains a very large number of blocks, we can still prove membership in a relatively short time.

In the following example we generate a sparse merkle tree proof, publishing the transit state on chain through our issuer identity.

Sparse Merkle Tree

As we’ve learned, a Merkle Tree is a crypto-graphically verifiable data structure where every leaf node contains the cryptographic hash of a data block, and every non-leaf node contains the cryptographic hash of its child nodes.

The Merkle Trees used in Iden3 protocol are Sparse. In Sparse Merkle Trees each data block has an associated index that determines its position inside the tree. Additionally, to inheriting the tamper-resistance and proof-of-membership properties from standard merkle trees, a Sparse Merkle Tree has other features:

• The insert order of data blocks doesn't influence the final Merkle Tree Root. A data block A with index 1 and a data block B with index 4 will always occupy the same positions inside the tree despite the insert order
• Some leaves remain empty
• It's possible to prove that certain data is not included in the tree (proof of non-membership)

A Sparse Merkle Tree is the core data structure used in Iden3 protocol to represent an identity. In particular, the leaves of a Sparse Merkle Tree are the claims issued by an identity.