miden_protocol/account/storage/map/
witness.rs

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

miden_protocol/account/storage/map/
witness.rs
