Merkle Sum Sparse Merkle Tree (MS-SMT)

Published by Mario Oettler on

A Merkle Sum Sparse Merkle Tree (MS-SMT) is a combination of a Merkle sum tree and a sparse Merkle tree.

Merkle Sum Sparse Merkle Tree.

In Taproot Assets, the data reflects the public key of the entity that holds the specific amount. For example, in the figure above, 111 would be the public key that holds an amount of 5.

With a Sparse Merkle Sum Sparse Merkle Tree, efficient proofs of non-inclusion and efficient verification of asset splits can be made. This is achieved by the fact that a leaf which does not contain any data is explicitly set to “Null”. The non-inclusion proof is done by walking down the tree and retrieving all hashes and their sum values. Since these trees in Taproot Assets have 256 levels, this means 256 iterations.