Sparse Merkle Tree

A Sparse Merkle Tree (SMT) is a data structure which allows for non-inclusion proofs. Using an SMT, it can be efficiently proven that specific data doesn’t exist within a given Merkle Tree. In an SMT, the location of a piece of data (which leaf of the tree) and the data itself are bound to each other. This means that for a given piece of data, there is only one location within the tree at which that data could be placed. If that location is empty, the data is not present in the entire tree. To obtain this property, the contents of a leaf are hashed and a Merkle Tree is created in which the leaf’s position corresponds to the hash. This requires a Merkle Tree of 256 levels and 2^256 leaves. Generating such a large tree is efficient because the vast majority of the leaves are empty. !Sparse Merkle tree