miden_crypto/merkle/smt/full/
proof.rs

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

miden_crypto/merkle/smt/full/
proof.rs
