miden_crypto/merkle/mmr/
proof.rs

1/// The representation of a single Merkle path.
2use super::super::MerklePath;
3use super::{full::high_bitmask, leaf_to_corresponding_tree};
4
5// MMR PROOF
6// ================================================================================================
7
8#[derive(Debug, Clone, PartialEq)]
9#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
10pub struct MmrProof {
11    /// The state of the MMR when the MmrProof was created.
12    pub forest: usize,
13
14    /// The position of the leaf value on this MmrProof.
15    pub position: usize,
16
17    /// The Merkle opening, starting from the value's sibling up to and excluding the root of the
18    /// responsible tree.
19    pub merkle_path: MerklePath,
20}
21
22impl MmrProof {
23    /// Converts the leaf global position into a local position that can be used to verify the
24    /// merkle_path.
25    pub fn relative_pos(&self) -> usize {
26        let tree_bit = leaf_to_corresponding_tree(self.position, self.forest)
27            .expect("position must be part of the forest");
28        let forest_before = self.forest & high_bitmask(tree_bit + 1);
29        self.position - forest_before
30    }
31
32    /// Returns index of the MMR peak against which the Merkle path in this proof can be verified.
33    pub fn peak_index(&self) -> usize {
34        let root = leaf_to_corresponding_tree(self.position, self.forest)
35            .expect("position must be part of the forest");
36        let smaller_peak_mask = 2_usize.pow(root) as usize - 1;
37        let num_smaller_peaks = (self.forest & smaller_peak_mask).count_ones();
38        (self.forest.count_ones() - num_smaller_peaks - 1) as usize
39    }
40}
41
42// TESTS
43// ================================================================================================
44
45#[cfg(test)]
46mod tests {
47    use super::{MerklePath, MmrProof};
48
49    #[test]
50    fn test_peak_index() {
51        // --- single peak forest ---------------------------------------------
52        let forest = 11;
53
54        // the first 4 leaves belong to peak 0
55        for position in 0..8 {
56            let proof = make_dummy_proof(forest, position);
57            assert_eq!(proof.peak_index(), 0);
58        }
59
60        // --- forest with non-consecutive peaks ------------------------------
61        let forest = 11;
62
63        // the first 8 leaves belong to peak 0
64        for position in 0..8 {
65            let proof = make_dummy_proof(forest, position);
66            assert_eq!(proof.peak_index(), 0);
67        }
68
69        // the next 2 leaves belong to peak 1
70        for position in 8..10 {
71            let proof = make_dummy_proof(forest, position);
72            assert_eq!(proof.peak_index(), 1);
73        }
74
75        // the last leaf is the peak 2
76        let proof = make_dummy_proof(forest, 10);
77        assert_eq!(proof.peak_index(), 2);
78
79        // --- forest with consecutive peaks ----------------------------------
80        let forest = 7;
81
82        // the first 4 leaves belong to peak 0
83        for position in 0..4 {
84            let proof = make_dummy_proof(forest, position);
85            assert_eq!(proof.peak_index(), 0);
86        }
87
88        // the next 2 leaves belong to peak 1
89        for position in 4..6 {
90            let proof = make_dummy_proof(forest, position);
91            assert_eq!(proof.peak_index(), 1);
92        }
93
94        // the last leaf is the peak 2
95        let proof = make_dummy_proof(forest, 6);
96        assert_eq!(proof.peak_index(), 2);
97    }
98
99    fn make_dummy_proof(forest: usize, position: usize) -> MmrProof {
100        MmrProof {
101            forest,
102            position,
103            merkle_path: MerklePath::default(),
104        }
105    }
106}
miden_crypto/merkle/mmr/proof.rs

miden_crypto/merkle/mmr/
proof.rs
