miden_crypto/merkle/mmr/
proof.rs

1/// The representation of a single Merkle path.
2use super::super::MerklePath;
3use super::forest::Forest;
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: Forest,
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        self.forest
27            .leaf_relative_position(self.position)
28            .expect("position must be part of the forest")
29    }
30
31    /// Returns index of the MMR peak against which the Merkle path in this proof can be verified.
32    pub fn peak_index(&self) -> usize {
33        self.forest.tree_index(self.position)
34    }
35}
36
37// TESTS
38// ================================================================================================
39
40#[cfg(test)]
41mod tests {
42    use super::{MerklePath, MmrProof};
43    use crate::merkle::mmr::forest::Forest;
44
45    #[test]
46    fn test_peak_index() {
47        // --- single peak forest ---------------------------------------------
48        let forest = Forest::new(11);
49
50        // the first 4 leaves belong to peak 0
51        for position in 0..8 {
52            let proof = make_dummy_proof(forest, position);
53            assert_eq!(proof.peak_index(), 0);
54        }
55
56        // --- forest with non-consecutive peaks ------------------------------
57        let forest = Forest::new(11);
58
59        // the first 8 leaves belong to peak 0
60        for position in 0..8 {
61            let proof = make_dummy_proof(forest, position);
62            assert_eq!(proof.peak_index(), 0);
63        }
64
65        // the next 2 leaves belong to peak 1
66        for position in 8..10 {
67            let proof = make_dummy_proof(forest, position);
68            assert_eq!(proof.peak_index(), 1);
69        }
70
71        // the last leaf is the peak 2
72        let proof = make_dummy_proof(forest, 10);
73        assert_eq!(proof.peak_index(), 2);
74
75        // --- forest with consecutive peaks ----------------------------------
76        let forest = Forest::new(7);
77
78        // the first 4 leaves belong to peak 0
79        for position in 0..4 {
80            let proof = make_dummy_proof(forest, position);
81            assert_eq!(proof.peak_index(), 0);
82        }
83
84        // the next 2 leaves belong to peak 1
85        for position in 4..6 {
86            let proof = make_dummy_proof(forest, position);
87            assert_eq!(proof.peak_index(), 1);
88        }
89
90        // the last leaf is the peak 2
91        let proof = make_dummy_proof(forest, 6);
92        assert_eq!(proof.peak_index(), 2);
93    }
94
95    fn make_dummy_proof(forest: Forest, position: usize) -> MmrProof {
96        MmrProof {
97            forest,
98            position,
99            merkle_path: MerklePath::default(),
100        }
101    }
102}
miden_crypto/merkle/mmr/proof.rs

miden_crypto/merkle/mmr/
proof.rs
