miden_crypto/merkle/mmr/
peaks.rs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
use super::{super::ZERO, Felt, MmrError, MmrProof, Rpo256, RpoDigest, Word};
use alloc::vec::Vec;

// MMR PEAKS
// ================================================================================================

#[derive(Debug, Clone, PartialEq, Eq)]
#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
pub struct MmrPeaks {
    /// The number of leaves is used to differentiate MMRs that have the same number of peaks. This
    /// happens because the number of peaks goes up-and-down as the structure is used causing
    /// existing trees to be merged and new ones to be created. As an example, every time the MMR
    /// has a power-of-two number of leaves there is a single peak.
    ///
    /// Every tree in the MMR forest has a distinct power-of-two size, this means only the right-
    /// most tree can have an odd number of elements (e.g. `1`). Additionally this means that the
    /// bits in `num_leaves` conveniently encode the size of each individual tree.
    ///
    /// Examples:
    ///
    ///    - With 5 leaves, the binary `0b101`. The number of set bits is equal the number
    ///      of peaks, in this case there are 2 peaks. The 0-indexed least-significant position of
    ///      the bit determines the number of elements of a tree, so the rightmost tree has `2**0`
    ///      elements and the left most has `2**2`.
    ///    - With 12 leaves, the binary is `0b1100`, this case also has 2 peaks, the
    ///      leftmost tree has `2**3=8` elements, and the right most has `2**2=4` elements.
    num_leaves: usize,

    /// All the peaks of every tree in the MMR forest. The peaks are always ordered by number of
    /// leaves, starting from the peak with most children, to the one with least.
    ///
    /// Invariant: The length of `peaks` must be equal to the number of true bits in `num_leaves`.
    peaks: Vec<RpoDigest>,
}

impl MmrPeaks {
    // CONSTRUCTOR
    // --------------------------------------------------------------------------------------------

    /// Returns new [MmrPeaks] instantiated from the provided vector of peaks and the number of
    /// leaves in the underlying MMR.
    ///
    /// # Errors
    /// Returns an error if the number of leaves and the number of peaks are inconsistent.
    pub fn new(num_leaves: usize, peaks: Vec<RpoDigest>) -> Result<Self, MmrError> {
        if num_leaves.count_ones() as usize != peaks.len() {
            return Err(MmrError::InvalidPeaks);
        }

        Ok(Self { num_leaves, peaks })
    }

    // ACCESSORS
    // --------------------------------------------------------------------------------------------

    /// Returns a count of leaves in the underlying MMR.
    pub fn num_leaves(&self) -> usize {
        self.num_leaves
    }

    /// Returns the number of peaks of the underlying MMR.
    pub fn num_peaks(&self) -> usize {
        self.peaks.len()
    }

    /// Returns the list of peaks of the underlying MMR.
    pub fn peaks(&self) -> &[RpoDigest] {
        &self.peaks
    }

    /// Converts this [MmrPeaks] into its components: number of leaves and a vector of peaks of
    /// the underlying MMR.
    pub fn into_parts(self) -> (usize, Vec<RpoDigest>) {
        (self.num_leaves, self.peaks)
    }

    /// Hashes the peaks.
    ///
    /// The procedure will:
    /// - Flatten and pad the peaks to a vector of Felts.
    /// - Hash the vector of Felts.
    pub fn hash_peaks(&self) -> RpoDigest {
        Rpo256::hash_elements(&self.flatten_and_pad_peaks())
    }

    pub fn verify(&self, value: RpoDigest, opening: MmrProof) -> bool {
        let root = &self.peaks[opening.peak_index()];
        opening.merkle_path.verify(opening.relative_pos() as u64, value, root)
    }

    /// Flattens and pads the peaks to make hashing inside of the Miden VM easier.
    ///
    /// The procedure will:
    /// - Flatten the vector of Words into a vector of Felts.
    /// - Pad the peaks with ZERO to an even number of words, this removes the need to handle RPO
    ///   padding.
    /// - Pad the peaks to a minimum length of 16 words, which reduces the constant cost of
    ///   hashing.
    pub fn flatten_and_pad_peaks(&self) -> Vec<Felt> {
        let num_peaks = self.peaks.len();

        // To achieve the padding rules above we calculate the length of the final vector.
        // This is calculated as the number of field elements. Each peak is 4 field elements.
        // The length is calculated as follows:
        // - If there are less than 16 peaks, the data is padded to 16 peaks and as such requires
        //   64 field elements.
        // - If there are more than 16 peaks and the number of peaks is odd, the data is padded to
        //   an even number of peaks and as such requires `(num_peaks + 1) * 4` field elements.
        // - If there are more than 16 peaks and the number of peaks is even, the data is not padded
        //   and as such requires `num_peaks * 4` field elements.
        let len = if num_peaks < 16 {
            64
        } else if num_peaks % 2 == 1 {
            (num_peaks + 1) * 4
        } else {
            num_peaks * 4
        };

        let mut elements = Vec::with_capacity(len);
        elements.extend_from_slice(
            &self
                .peaks
                .as_slice()
                .iter()
                .map(|digest| digest.into())
                .collect::<Vec<Word>>()
                .concat(),
        );
        elements.resize(len, ZERO);
        elements
    }
}

impl From<MmrPeaks> for Vec<RpoDigest> {
    fn from(peaks: MmrPeaks) -> Self {
        peaks.peaks
    }
}