A week ago, I posted an SMT construction on A nearly-trivial-on-zero-inputs 32-bytes-long collision-resistant hash function - #29 by jjyr
The advantage of this construction encourage me to post it again:
- this construction does not lose any security compare to others
- no pre-calculated hash set, which is perfect for contracts.
After a week of work, I optimized the storage, and now it takes 2n + log(n) size to store an SMT; log(n) times hashing and inserting for key-value updating.
The code is implemented in Rust GitHub - jjyr/sparse-merkle-tree
Pros:
-
no pre-calculated hash set
-
support both exist proof and non-exists proof
-
efficient storage and key updating
This is just another construction of SMT, no magic improvement compare to other constructions, see this comment:
To save your time, you can stop reading if you already follow the discussions mentioned by the comment.
Trick 1: Optimized hash function for 0 value.
We define the hash merge function as below:
-
if L == 0, return R
-
if R == 0, return L
-
otherwise sha256(L, R)
Follow this rule; an empty SMT is constructed by zeros nodes; it brings an advantage: we do not need a pre-calculated hash set.
This function has one issue, merge(L, 0) == merge(0, L) , which can easily construct a conflicted merkle root from a different set of leaves.
To fix this, instead of use hash(value) , we compute a leaf_hash = hash(key, value) as leaf’s value to merge with its sibling.
(we store leaf_hash -> value in a map to indexed to the original value).
Security proof:
-
Since the key is hashing into the leaf_hash, no matter what the
valueis, the leaves’ hashes are unique. -
Since all leaves have a unique hash, nodes at each height will either merged by two different hashes or merged by a hash with a zero(for a non-zero parent, since the child hash is unique, the parent is surely unique at the height).
-
For the root, if the tree is empty, we got zero, or if the tree is not empty, the root must merge from two hashes or a hash with a zero, it’s still unique.
So from construction, this SMT is security because we can’t get a collision root hash.
Trick 2: A node structure to compress the tree.
The classical node structure is Node {left, right}, it works fine if we insert every node from root of the tree to bottom, but mostly node is duplicated, we want our tree only store unique nodes.
The idea is simple: for a one leaf SMT, we only store the leaf itself, when inserting new leaves, we magically extract location info from internal tree node, and decide how to merge nodes.
The key to this problem is the “key”. Each key in the SMT can be seen as a path from the root of the tree to leaves, so the idea is we store the key in node, and when we need to merge two nodes, we extract the location info from the keys:
We can calculate the common height of two keys, which is exactly the height the two nodes be merged.
fn common_height(key1, key2) {
for i in 255..0 {
if key1.get_bit(i) != key2.get_bit(i) {
// common height
return i;
}
}
return 0;
}
The node structure BranchNode { fork_height, key, node, sibling}, can use one unique node to expression all duplicated nodes on the “key” path between height [node.fork_height, 255].
-
fork_heightis the height when the node created; for a leaf, it is 0. -
keyis the key of a child’s key when constructing the node. for a leaf node, the key is leaf’s key. -
nodeandsiblingis like theleftandrightin the classical structure; the only difference is their position is not fixed.
To get a left child of a node in height H:
-
check
H-th bit of key -
if it is
1means thenodeis on the right at heightH, sosiblingis the left child -
if the
0means thenodeis on the left
// get children at height
// return value is (left, right)
fn children(branch_node, height) {
let is_rhs = branch_node.key.get_bit(height);
if is_rhs {
return (branch_node.sibling, branch_node.node)
} else {
return (branch_node.node, branch_node.sibling)
}
}
To get a key from SMT, we walk down the tree from root to bottom:
fn get(key) {
let node = root;
// path order by height
let path = BTreeMap::new();
loop {
let branch_node = match map.get(node) {
Some(b) => b,
None => break,
}
// common height may be lower than node.fork_height
let height = max(common_height(key, node.key), node.fork_height);
if height > node.fork_height {
// node is sibling, end search
path.push(heignt, node);
break;
}
// node is parent
// extract children position from branch
let (left, right) = children(branch_node, height);
// extract key positon
let is_right = key.get_bit(height);
if is_right {
path.push(height, left);
node = right;
} else {
path.push(height, right);
node = left;
}
}
return self.leaves[node];
}
There is nothing special for other operations: updating, merkle proof. It just works as expected.