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