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}