miden_objects/account/storage/map/
witness.rs

1use alloc::collections::BTreeMap;
2
3use miden_crypto::merkle::{InnerNodeInfo, SmtProof};
4
5use crate::Word;
6use crate::account::StorageMap;
7use crate::errors::StorageMapError;
8
9/// A witness of an asset in a [`StorageMap`](super::StorageMap).
10///
11/// It proves inclusion of a certain storage item in the map.
12///
13/// ## Guarantees
14///
15/// This type guarantees that the raw key-value pairs it contains are all present in the
16/// contained SMT proof. Note that the inverse is not necessarily true. The proof may contain more
17/// entries than the map because to prove inclusion of a given raw key A an
18/// [`SmtLeaf::Multiple`](miden_crypto::merkle::SmtLeaf::Multiple) may be present that contains both
19/// keys hash(A) and hash(B). However, B may not be present in the key-value pairs and this is a
20/// valid state.
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct StorageMapWitness {
23    proof: SmtProof,
24    /// The entries of the map where the key is the raw user-chosen one.
25    ///
26    /// It is an invariant of this type that the map's entries are always consistent with the SMT's
27    /// entries and vice-versa.
28    entries: BTreeMap<Word, Word>,
29}
30
31impl StorageMapWitness {
32    // CONSTRUCTORS
33    // --------------------------------------------------------------------------------------------
34
35    /// Creates a new [`StorageMapWitness`] from an SMT proof and a provided set of map keys.
36    ///
37    /// # Errors
38    ///
39    /// Returns an error if:
40    /// - Any of the map keys is not contained in the proof.
41    pub fn new(
42        proof: SmtProof,
43        raw_keys: impl IntoIterator<Item = Word>,
44    ) -> Result<Self, StorageMapError> {
45        let mut entries = BTreeMap::new();
46
47        for raw_key in raw_keys.into_iter() {
48            let hashed_map_key = StorageMap::hash_key(raw_key);
49            let value =
50                proof.get(&hashed_map_key).ok_or(StorageMapError::MissingKey { raw_key })?;
51            entries.insert(raw_key, value);
52        }
53
54        Ok(Self { proof, entries })
55    }
56
57    /// Creates a new [`StorageMapWitness`] from an SMT proof and a set of raw key value pairs.
58    ///
59    /// # Warning
60    ///
61    /// This does not validate any of the guarantees of this type. See the type-level docs for more
62    /// details.
63    pub fn new_unchecked(
64        proof: SmtProof,
65        raw_key_values: impl IntoIterator<Item = (Word, Word)>,
66    ) -> Self {
67        Self {
68            proof,
69            entries: raw_key_values.into_iter().collect(),
70        }
71    }
72
73    // PUBLIC ACCESSORS
74    // --------------------------------------------------------------------------------------------
75
76    /// Returns a reference to the underlying [`SmtProof`].
77    pub fn proof(&self) -> &SmtProof {
78        &self.proof
79    }
80
81    /// Looks up the provided key in this witness and returns:
82    /// - a non-empty [`Word`] if the key is tracked by this witness and exists in it,
83    /// - [`Word::empty`] if the key is tracked by this witness and does not exist,
84    /// - `None` if the key is not tracked by this witness.
85    pub fn get(&self, raw_key: &Word) -> Option<Word> {
86        let hashed_key = StorageMap::hash_key(*raw_key);
87        self.proof.get(&hashed_key)
88    }
89
90    /// Returns an iterator over the key-value pairs in this witness.
91    ///
92    /// Note that the returned key is the raw map key.
93    pub fn entries(&self) -> impl Iterator<Item = (&Word, &Word)> {
94        self.entries.iter()
95    }
96
97    /// Returns an iterator over every inner node of this witness' merkle path.
98    pub fn authenticated_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
99        self.proof
100            .path()
101            .authenticated_nodes(self.proof.leaf().index().value(), self.proof.leaf().hash())
102            .expect("leaf index is u64 and should be less than 2^SMT_DEPTH")
103    }
104}
105
106impl From<StorageMapWitness> for SmtProof {
107    fn from(witness: StorageMapWitness) -> Self {
108        witness.proof
109    }
110}
111
112#[cfg(test)]
113mod tests {
114    use assert_matches::assert_matches;
115
116    use super::*;
117    use crate::account::StorageMap;
118
119    #[test]
120    fn creating_witness_fails_on_missing_key() {
121        // Create a storage map with one key-value pair
122        let key1 = Word::from([1, 2, 3, 4u32]);
123        let value1 = Word::from([10, 20, 30, 40u32]);
124        let entries = [(key1, value1)];
125        let storage_map = StorageMap::with_entries(entries).unwrap();
126
127        // Create a proof for the existing key
128        let proof = storage_map.open(&key1).into();
129
130        // Try to create a witness for a different key that's not in the proof
131        let missing_key = Word::from([5, 6, 7, 8u32]);
132        let result = StorageMapWitness::new(proof, [missing_key]);
133
134        assert_matches!(result, Err(StorageMapError::MissingKey { raw_key }) => {
135            assert_eq!(raw_key, missing_key);
136        });
137    }
138}
miden_objects/account/storage/map/witness.rs

miden_objects/account/storage/map/
witness.rs
