miden_crypto/merkle/smt/full/
proof.rs

1use alloc::string::ToString;
2
3use super::{MerklePath, RpoDigest, SmtLeaf, SmtProofError, Word, SMT_DEPTH};
4use crate::utils::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable};
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::InvalidMerklePathLength(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}
miden_crypto/merkle/smt/full/proof.rs

miden_crypto/merkle/smt/full/
proof.rs
