1use crate::utils::string::ToString;
  2use winter_utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
  3
  4use super::{MerklePath, RpoDigest, SmtLeaf, SmtProofError, Word, SMT_DEPTH};
  5
  6/// A proof which can be used to assert membership (or non-membership) of key-value pairs in a
  7/// [`super::Smt`].
  8///
  9/// The proof consists of a Merkle path and leaf which describes the node located at the base of the
 10/// path.
 11#[derive(Clone, Debug, PartialEq, Eq)]
 12pub struct SmtProof {
 13    path: MerklePath,
 14    leaf: SmtLeaf,
 15}
 16
 17impl SmtProof {
 18    // CONSTRUCTOR
 19    // --------------------------------------------------------------------------------------------
 20
 21    /// Returns a new instance of [`SmtProof`] instantiated from the specified path and leaf.
 22    ///
 23    /// # Errors
 24    /// Returns an error if the path length is not [`SMT_DEPTH`].
 25    pub fn new(path: MerklePath, leaf: SmtLeaf) -> Result<Self, SmtProofError> {
 26        if path.len() != SMT_DEPTH.into() {
 27            return Err(SmtProofError::InvalidPathLength(path.len()));
 28        }
 29
 30        Ok(Self { path, leaf })
 31    }
 32
 33    /// Returns a new instance of [`SmtProof`] instantiated from the specified path and leaf.
 34    ///
 35    /// The length of the path is not checked. Reserved for internal use.
 36    pub(super) fn new_unchecked(path: MerklePath, leaf: SmtLeaf) -> Self {
 37        Self { path, leaf }
 38    }
 39
 40    // PROOF VERIFIER
 41    // --------------------------------------------------------------------------------------------
 42
 43    /// Returns true if a [`super::Smt`] with the specified root contains the provided
 44    /// key-value pair.
 45    ///
 46    /// Note: this method cannot be used to assert non-membership. That is, if false is returned,
 47    /// it does not mean that the provided key-value pair is not in the tree.
 48    pub fn verify_membership(&self, key: &RpoDigest, value: &Word, root: &RpoDigest) -> bool {
 49        let maybe_value_in_leaf = self.leaf.get_value(key);
 50
 51        match maybe_value_in_leaf {
 52            Some(value_in_leaf) => {
 53                // The value must match for the proof to be valid
 54                if value_in_leaf != *value {
 55                    return false;
 56                }
 57
 58                // make sure the Merkle path resolves to the correct root
 59                self.compute_root() == *root
 60            }
 61            // If the key maps to a different leaf, the proof cannot verify membership of `value`
 62            None => false,
 63        }
 64    }
 65
 66    // PUBLIC ACCESSORS
 67    // --------------------------------------------------------------------------------------------
 68
 69    /// Returns the value associated with the specific key according to this proof, or None if
 70    /// this proof does not contain a value for the specified key.
 71    ///
 72    /// A key-value pair generated by using this method should pass the `verify_membership()` check.
 73    pub fn get(&self, key: &RpoDigest) -> Option<Word> {
 74        self.leaf.get_value(key)
 75    }
 76
 77    /// Computes the root of a [`super::Smt`] to which this proof resolves.
 78    pub fn compute_root(&self) -> RpoDigest {
 79        self.path
 80            .compute_root(self.leaf.index().value(), self.leaf.hash())
 81            .expect("failed to compute Merkle path root")
 82    }
 83
 84    /// Consume the proof and returns its parts.
 85    pub fn into_parts(self) -> (MerklePath, SmtLeaf) {
 86        (self.path, self.leaf)
 87    }
 88}
 89
 90impl Serializable for SmtProof {
 91    fn write_into<W: ByteWriter>(&self, target: &mut W) {
 92        self.path.write_into(target);
 93        self.leaf.write_into(target);
 94    }
 95}
 96
 97impl Deserializable for SmtProof {
 98    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
 99        let path = MerklePath::read_from(source)?;
100        let leaf = SmtLeaf::read_from(source)?;
101
102        Self::new(path, leaf).map_err(|err| DeserializationError::InvalidValue(err.to_string()))
103    }
104}