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::StorageMap;
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<Word, 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        raw_keys: impl IntoIterator<Item = Word>,
45    ) -> Result<Self, StorageMapError> {
46        let mut entries = BTreeMap::new();
47
48        for raw_key in raw_keys.into_iter() {
49            let hashed_map_key = StorageMap::hash_key(raw_key);
50            let value =
51                proof.get(&hashed_map_key).ok_or(StorageMapError::MissingKey { raw_key })?;
52            entries.insert(raw_key, value);
53        }
54
55        Ok(Self { proof, entries })
56    }
57
58    /// Creates a new [`StorageMapWitness`] from an SMT proof and a set of raw key value pairs.
59    ///
60    /// # Warning
61    ///
62    /// This does not validate any of the guarantees of this type. See the type-level docs for more
63    /// details.
64    pub fn new_unchecked(
65        proof: SmtProof,
66        raw_key_values: impl IntoIterator<Item = (Word, Word)>,
67    ) -> Self {
68        Self {
69            proof,
70            entries: raw_key_values.into_iter().collect(),
71        }
72    }
73
74    // PUBLIC ACCESSORS
75    // --------------------------------------------------------------------------------------------
76
77    /// Returns a reference to the underlying [`SmtProof`].
78    pub fn proof(&self) -> &SmtProof {
79        &self.proof
80    }
81
82    /// Looks up the provided key in this witness and returns:
83    /// - a non-empty [`Word`] if the key is tracked by this witness and exists in it,
84    /// - [`Word::empty`] if the key is tracked by this witness and does not exist,
85    /// - `None` if the key is not tracked by this witness.
86    pub fn get(&self, raw_key: &Word) -> Option<Word> {
87        let hashed_key = StorageMap::hash_key(*raw_key);
88        self.proof.get(&hashed_key)
89    }
90
91    /// Returns an iterator over the key-value pairs in this witness.
92    ///
93    /// Note that the returned key is the raw map key.
94    pub fn entries(&self) -> impl Iterator<Item = (&Word, &Word)> {
95        self.entries.iter()
96    }
97
98    /// Returns an iterator over every inner node of this witness' merkle path.
99    pub fn authenticated_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_ {
100        self.proof
101            .path()
102            .authenticated_nodes(self.proof.leaf().index().value(), self.proof.leaf().hash())
103            .expect("leaf index is u64 and should be less than 2^SMT_DEPTH")
104    }
105}
106
107impl From<StorageMapWitness> for SmtProof {
108    fn from(witness: StorageMapWitness) -> Self {
109        witness.proof
110    }
111}
112
113#[cfg(test)]
114mod tests {
115    use assert_matches::assert_matches;
116
117    use super::*;
118    use crate::account::StorageMap;
119
120    #[test]
121    fn creating_witness_fails_on_missing_key() {
122        // Create a storage map with one key-value pair
123        let key1 = Word::from([1, 2, 3, 4u32]);
124        let value1 = Word::from([10, 20, 30, 40u32]);
125        let entries = [(key1, value1)];
126        let storage_map = StorageMap::with_entries(entries).unwrap();
127
128        // Create a proof for the existing key
129        let proof = storage_map.open(&key1).into();
130
131        // Try to create a witness for a different key that's not in the proof
132        let missing_key = Word::from([5, 6, 7, 8u32]);
133        let result = StorageMapWitness::new(proof, [missing_key]);
134
135        assert_matches!(result, Err(StorageMapError::MissingKey { raw_key }) => {
136            assert_eq!(raw_key, missing_key);
137        });
138    }
139}
miden_protocol/account/storage/map/witness.rs

miden_protocol/account/storage/map/
witness.rs
