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