This Request for Comment (RFC) proposes replacing the current Mutable Merkle Mountain Range (MMMR) data structure
used for tracking the commitment to the UTXO set, with a Sparse Merkle tree (SMT).
A sparse Merkle tree ([SMT]) is a Merkle-type structure, except the contained data is indexed, and each datapoint is
placed at the leaf that corresponds to that datapoint’s index. Empty nodes are represented by a predefined "null" value.
Since every empty node has the same hash, and the tree is sparse, it is possible to prune the tree in a way such
that only the non-zero leaf nodes and placeholders marking the empty sub-trees are stored. Therefore, SMTs are
relatively compact.
CjS77
commented
1 year ago
This Request for Comment (RFC) proposes replacing the current Mutable Merkle Mountain Range (MMMR) data structure used for tracking the commitment to the UTXO set, with a Sparse Merkle tree (SMT).
A sparse Merkle tree ([SMT]) is a Merkle-type structure, except the contained data is indexed, and each datapoint is placed at the leaf that corresponds to that datapoint’s index. Empty nodes are represented by a predefined "null" value.
Since every empty node has the same hash, and the tree is sparse, it is possible to prune the tree in a way such that only the non-zero leaf nodes and placeholders marking the empty sub-trees are stored. Therefore, SMTs are relatively compact.