miden_crypto/merkle/smt/full/
proof.rs

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

miden_crypto/merkle/smt/full/
proof.rs
