1use alloc::vec::Vec;
  2
  3use super::{super::ZERO, Felt, MmrError, MmrProof, Rpo256, RpoDigest, Word};
  4
  5// MMR PEAKS
  6// ================================================================================================
  7
  8#[derive(Debug, Clone, PartialEq, Eq)]
  9#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
 10pub struct MmrPeaks {
 11    /// The number of leaves is used to differentiate MMRs that have the same number of peaks. This
 12    /// happens because the number of peaks goes up-and-down as the structure is used causing
 13    /// existing trees to be merged and new ones to be created. As an example, every time the MMR
 14    /// has a power-of-two number of leaves there is a single peak.
 15    ///
 16    /// Every tree in the MMR forest has a distinct power-of-two size, this means only the right-
 17    /// most tree can have an odd number of elements (e.g. `1`). Additionally this means that the
 18    /// bits in `num_leaves` conveniently encode the size of each individual tree.
 19    ///
 20    /// Examples:
 21    ///
 22    /// - With 5 leaves, the binary `0b101`. The number of set bits is equal the number of peaks,
 23    ///   in this case there are 2 peaks. The 0-indexed least-significant position of the bit
 24    ///   determines the number of elements of a tree, so the rightmost tree has `2**0` elements
 25    ///   and the left most has `2**2`.
 26    /// - With 12 leaves, the binary is `0b1100`, this case also has 2 peaks, the leftmost tree has
 27    ///   `2**3=8` elements, and the right most has `2**2=4` elements.
 28    num_leaves: usize,
 29
 30    /// All the peaks of every tree in the MMR forest. The peaks are always ordered by number of
 31    /// leaves, starting from the peak with most children, to the one with least.
 32    ///
 33    /// Invariant: The length of `peaks` must be equal to the number of true bits in `num_leaves`.
 34    peaks: Vec<RpoDigest>,
 35}
 36
 37impl MmrPeaks {
 38    // CONSTRUCTOR
 39    // --------------------------------------------------------------------------------------------
 40
 41    /// Returns new [MmrPeaks] instantiated from the provided vector of peaks and the number of
 42    /// leaves in the underlying MMR.
 43    ///
 44    /// # Errors
 45    /// Returns an error if the number of leaves and the number of peaks are inconsistent.
 46    pub fn new(num_leaves: usize, peaks: Vec<RpoDigest>) -> Result<Self, MmrError> {
 47        if num_leaves.count_ones() as usize != peaks.len() {
 48            return Err(MmrError::InvalidPeaks(format!(
 49                "number of one bits in leaves is {} which does not equal peak length {}",
 50                num_leaves.count_ones(),
 51                peaks.len()
 52            )));
 53        }
 54
 55        Ok(Self { num_leaves, peaks })
 56    }
 57
 58    // ACCESSORS
 59    // --------------------------------------------------------------------------------------------
 60
 61    /// Returns a count of leaves in the underlying MMR.
 62    pub fn num_leaves(&self) -> usize {
 63        self.num_leaves
 64    }
 65
 66    /// Returns the number of peaks of the underlying MMR.
 67    pub fn num_peaks(&self) -> usize {
 68        self.peaks.len()
 69    }
 70
 71    /// Returns the list of peaks of the underlying MMR.
 72    pub fn peaks(&self) -> &[RpoDigest] {
 73        &self.peaks
 74    }
 75
 76    /// Returns the peak by the provided index.
 77    ///
 78    /// # Errors
 79    /// Returns an error if the provided peak index is greater or equal to the current number of
 80    /// peaks in the Mmr.
 81    pub fn get_peak(&self, peak_idx: usize) -> Result<&RpoDigest, MmrError> {
 82        self.peaks
 83            .get(peak_idx)
 84            .ok_or(MmrError::PeakOutOfBounds { peak_idx, peaks_len: self.peaks.len() })
 85    }
 86
 87    /// Converts this [MmrPeaks] into its components: number of leaves and a vector of peaks of
 88    /// the underlying MMR.
 89    pub fn into_parts(self) -> (usize, Vec<RpoDigest>) {
 90        (self.num_leaves, self.peaks)
 91    }
 92
 93    /// Hashes the peaks.
 94    ///
 95    /// The procedure will:
 96    /// - Flatten and pad the peaks to a vector of Felts.
 97    /// - Hash the vector of Felts.
 98    pub fn hash_peaks(&self) -> RpoDigest {
 99        Rpo256::hash_elements(&self.flatten_and_pad_peaks())
100    }
101
102    /// Verifies the Merkle opening proof.
103    ///
104    /// # Errors
105    /// Returns an error if:
106    /// - provided opening proof is invalid.
107    /// - Mmr root value computed using the provided leaf value differs from the actual one.
108    pub fn verify(&self, value: RpoDigest, opening: MmrProof) -> Result<(), MmrError> {
109        let root = self.get_peak(opening.peak_index())?;
110        opening
111            .merkle_path
112            .verify(opening.relative_pos() as u64, value, root)
113            .map_err(MmrError::InvalidMerklePath)
114    }
115
116    /// Flattens and pads the peaks to make hashing inside of the Miden VM easier.
117    ///
118    /// The procedure will:
119    /// - Flatten the vector of Words into a vector of Felts.
120    /// - Pad the peaks with ZERO to an even number of words, this removes the need to handle RPO
121    ///   padding.
122    /// - Pad the peaks to a minimum length of 16 words, which reduces the constant cost of hashing.
123    pub fn flatten_and_pad_peaks(&self) -> Vec<Felt> {
124        let num_peaks = self.peaks.len();
125
126        // To achieve the padding rules above we calculate the length of the final vector.
127        // This is calculated as the number of field elements. Each peak is 4 field elements.
128        // The length is calculated as follows:
129        // - If there are less than 16 peaks, the data is padded to 16 peaks and as such requires 64
130        //   field elements.
131        // - If there are more than 16 peaks and the number of peaks is odd, the data is padded to
132        //   an even number of peaks and as such requires `(num_peaks + 1) * 4` field elements.
133        // - If there are more than 16 peaks and the number of peaks is even, the data is not padded
134        //   and as such requires `num_peaks * 4` field elements.
135        let len = if num_peaks < 16 {
136            64
137        } else if num_peaks % 2 == 1 {
138            (num_peaks + 1) * 4
139        } else {
140            num_peaks * 4
141        };
142
143        let mut elements = Vec::with_capacity(len);
144        elements.extend_from_slice(
145            &self
146                .peaks
147                .as_slice()
148                .iter()
149                .map(|digest| digest.into())
150                .collect::<Vec<Word>>()
151                .concat(),
152        );
153        elements.resize(len, ZERO);
154        elements
155    }
156}
157
158impl From<MmrPeaks> for Vec<RpoDigest> {
159    fn from(peaks: MmrPeaks) -> Self {
160        peaks.peaks
161    }
162}