Proposal to Make calculate_root a Native Function for Merkle Tree Root Calculation #269
Description
We currently implement Merkle root calculation manually using vector operations and hashing inside Move:
public(friend) fun calculate_root(leaves: &mut vector<vector<u8>>): vector<u8> {
let num_leaves = next_power_of_two(vector::length(leaves));
let empty_leaf = x"0000000000000000000000000000000000000000000000000000000000000000";
while (vector::length(leaves) < num_leaves) {
vector::push_back(leaves, empty_leaf);
};
while (num_leaves > 1) {
let next_level = vector::empty<vector<u8>>();
let i = 0;
vector::reverse(leaves);
while (i < num_leaves) {
let left = vector::pop_back(leaves);
let right = vector::pop_back(leaves);
let combined_hash = hash_pair(left, right);
vector::push_back(&mut next_level, combined_hash);
i = i + 2;
};
*leaves = next_level;
num_leaves = vector::length(leaves);
};
*vector::borrow(leaves, 0)
}Reason for Native Migration:
-
The current implementation involves:
- Repeated allocations and vector reversals.
- Multiple vector pops/pushes per iteration.
- Redundant hashing and copying.
-
It’s a common operation , and having a native implementation would:
- Greatly improve performance.
- Eliminate boilerplate padding and tree-walking logic.
Request:
Can we expose a native function like:
native public fun merkle_root(leaves: vector<vector<u8>>): vector<u8>;This would help standardize and optimize Merkle root computation across all Move-based chains using light clients or cross-chain proofs.