0xMiden / 0xMiden/miden-vm

MmrPeaks::hash_peaks doesn't bind forest shape, allowing collision between structurally distinct MMRs

Open
#3,512 14 comments 0 reactions 0 assignees View on GitHub
corelib merkle
Dominant language
Rust
Stars
772
Forks
352
Avg merge
1d 12h
Merged PRs (30d)
93

Description

The `hash_peaks` method hashes only the peak values without including the forest field that encodes the MMR structure. Two MMRs with different shapes but the same peak values will produce identical hashes, breaking the uniqueness guarantee.

The root cause is incomplete data binding in the hash computation. At miden-crypto/src/merkle/mmr/peaks.rs:118-120, `hash_peaks` calls `Poseidon2::hash_elements(&self.flatten_and_pad_peaks())` which only includes peak hashes. However, the `forest` field (line 33) encodes which peaks exist via its bit pattern - a 5-leaf MMR (binary `0b101`) has different structure than an 8-leaf MMR (binary `0b1000`) even if they happen to have overlapping peak values.

Without binding the forest shape, the hash can't uniquely identify the MMR state. An attacker could craft two structurally different MMRs that hash to the same value, potentially causing the implementation to accept incorrect Merkle paths or perform subtree merges at wrong heights.

To fix this, include the forest's leaf count in the hash input by prepending `Felt::new(self.forest.num_leaves() as u64)` to the elements passed to `hash_elements`, or by using a domain-separated hash that commits to both peaks and structure.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.