Merkle-Sum Sparse Merkle tree

A Merkle-Sum Sparse Merkle tree (MS-SMT) is a specific variant of a Merkle tree that combines a Merkle sum tree and a Sparse Merkle tree. As any merkle root, the MS-SMT can store a huge amount of data, and you only have store the Hash, an ideal candidate to store and trace user created assets.

MS-SMT is a merkle sum tree

In Merkle sum tree, a numeric value is assigned to each leaf. Thanks to this property, it’s easy to check that the total amount of issued assets hasn’t changed.

graph TD SUM["Sum: 300
Root hash: jrudj7..."] SUM --> SUM01["Sum: 123
Root hash: le5f5j..."] SUM --> SUM02["Sum: 177
Root hash: jm5doe..."] SUM01 --> BALANCE01["Amount: 113
Root hash: 85hlpo..."] SUM01 --> BALANCE02["Amount: 10
Root hash: a5z9f2..."] SUM02 --> BALANCE03["null
Root hash: blf458..."] SUM02 --> BALANCE04["Amount: 177
Root hash: 69dfg5..."]

MS-SMT is a sparse merkle tree

In Sparse Merkle tree, data is linked to its position in the tree. Thanks to this property, it’s easy to check if a data is no longer in the tree, in our case, this means checking an existing asset knowing the position (positif is fixed).

This is how it would look like for a 2 bits key:

graph TD SUM["Hash (00, 01, null, 11)"] SUM --> HASH00-01["Hash (00, 01)"] SUM --> HASH10-11["Hash (null, 11)"] HASH00-01 --> HASH01["Hash (00)"] HASH00-01 --> HASH02["Hash (01)"] HASH10-11 --> HASH03["Hash (null)"] HASH10-11 --> HASH04["Hash (11)"] HASH01 --> POSITION00["Position 00
Data"] HASH02 --> POSITION01["Position 01
Data"] HASH03 --> POSITION10["Position 10
Null (no data)"] HASH04 --> POSITION11["Position 11
Data"]

A complete Merkle-Sum Sparse Merkle tree

The Taproot Assets Merkle-Sum Sparse Merkle tree has 2^256 leaves with a numeric value assigned to each leaf. This is how it looks like but, as 2^256 is a very large number, we can only draw a small part:

graph TD SUM["300, Taproot Assets Hash Root"] SUM -.-> HASH00-01["123, Hash (00, 01)"] SUM -.-> HASH10-11["177, Hash (null, 11)"] HASH00-01 --> HASH01["113, Hash (00)"] HASH00-01 --> HASH02["10, Hash (01)"] HASH10-11 --> HASH03["0, SumHash (null)"] HASH10-11 --> HASH04["177, Hash (11)"] HASH01 --> POSITION0["Position 1
Amount: 113 USDB"] HASH02 --> POSITION1["Position 2
Amount: 10 USDB"] HASH03 --> POSITION2["Position 3
Amount: 0 null"] HASH04 --> POSITION3["Position 4
Amount: 177 USDB"] SUM -.-> HASH255["..."] HASH255 -.-> HASH255_LEVEL2["0, Hash (2^256)"] HASH255_LEVEL2 -.-> POSITION4["Position 2^256
Amount: 0 null"]

Each account is identified by its 256-bit key, this means each leaf is one possible account. One leaf contains the account number and the amount this account has.

TODO Explain Asset leaves Each leaf contains a TLV (type, length, value) blob, akin to the TLV used in the Lightning Network. It contains information such as versions, asset id, amount, as well as data pertaining to previous transfers of this asset, such as signatures.