miden_core/advice/
map.rs

1use alloc::{
2    collections::{
3        BTreeMap,
4        btree_map::{Entry, IntoIter},
5    },
6    sync::Arc,
7    vec::Vec,
8};
9
10use crate::{
11    Felt, WORD_SIZE, Word,
12    crypto::hash::Poseidon2,
13    serde::{ByteReader, ByteWriter, Deserializable, DeserializationError, Serializable},
14};
15
16// ADVICE MAP
17// ================================================================================================
18
19/// Defines a set of non-deterministic (advice) inputs which the VM can access by their keys.
20///
21/// Each key maps to one or more field element. To access the elements, the VM can move the values
22/// associated with a given key onto the advice stack using `adv.push_mapval` instruction. The VM
23/// can also insert new values into the advice map during execution.
24///
25/// This type is a policy-free container. Execution-specific size limits for live advice map state
26/// are enforced by the processor's `AdviceProvider`, which owns the active execution options and
27/// live resource accounting.
28#[derive(Debug, Clone, Default, PartialEq, Eq)]
29#[cfg_attr(
30    all(feature = "arbitrary", test),
31    miden_test_serialization_macros::serialization_test
32)]
33pub struct AdviceMap(BTreeMap<Word, Arc<[Felt]>>);
34
35/// Pair representing a key-value entry in an [`AdviceMap`]
36type MapEntry = (Word, Arc<[Felt]>);
37
38impl AdviceMap {
39    /// Returns the values associated with given key.
40    pub fn get(&self, key: &Word) -> Option<&Arc<[Felt]>> {
41        self.0.get(key)
42    }
43
44    /// Returns true if the key has a corresponding value in the map.
45    pub fn contains_key(&self, key: &Word) -> bool {
46        self.0.contains_key(key)
47    }
48
49    /// Inserts a value, returning the previous value if the key was already set.
50    pub fn insert(&mut self, key: Word, value: impl Into<Arc<[Felt]>>) -> Option<Arc<[Felt]>> {
51        self.0.insert(key, value.into())
52    }
53
54    /// Removes the value associated with the key and returns the removed element.
55    pub fn remove(&mut self, key: &Word) -> Option<Arc<[Felt]>> {
56        self.0.remove(key)
57    }
58
59    /// Return an iteration over all entries in the map.
60    pub fn iter(&self) -> impl Iterator<Item = (&Word, &Arc<[Felt]>)> {
61        self.0.iter()
62    }
63
64    /// Returns the number of key value pairs in the advice map.
65    pub fn len(&self) -> usize {
66        self.0.len()
67    }
68
69    /// Returns true if the advice map is empty.
70    pub fn is_empty(&self) -> bool {
71        self.0.is_empty()
72    }
73
74    /// Returns the total number of field elements stored in this advice map's keys and values.
75    ///
76    /// Each key is a word, so every entry contributes [`WORD_SIZE`] key elements plus the number
77    /// of value elements associated with that key. Returns `None` if the count overflows `usize`.
78    pub fn total_element_count(&self) -> Option<usize> {
79        self.0.values().try_fold(0usize, |total, values| {
80            WORD_SIZE
81                .checked_add(values.len())
82                .and_then(|entry_elements| total.checked_add(entry_elements))
83        })
84    }
85
86    /// Returns a commitment to this advice map.
87    ///
88    /// Entries are committed in key order. Each entry is hashed as the key elements followed by the
89    /// value elements. [`Poseidon2::hash_elements`] binds the entry length, and
90    /// [`Poseidon2::merge_many`] folds the ordered entry commitments into the final map
91    /// commitment.
92    pub fn commitment(&self) -> Word {
93        let entry_commitments = self
94            .iter()
95            .map(|(key, values)| {
96                let mut elements = Vec::with_capacity(WORD_SIZE + values.len());
97                elements.extend_from_slice(key.as_elements());
98                elements.extend_from_slice(values);
99                Poseidon2::hash_elements(&elements)
100            })
101            .collect::<Vec<_>>();
102
103        Poseidon2::merge_many(&entry_commitments)
104    }
105
106    /// Gets the given key's corresponding entry in the map for in-place manipulation.
107    pub fn entry(&mut self, key: Word) -> Entry<'_, Word, Arc<[Felt]>> {
108        self.0.entry(key)
109    }
110
111    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
112    ///
113    /// If an entry from the new map already exists with the same key but different value,
114    /// an error is returned containing the existing entry along with the value that would replace
115    /// it. The current map remains unchanged.
116    pub fn merge(&mut self, other: &Self) -> Result<(), (MapEntry, Arc<[Felt]>)> {
117        if let Some(conflict) = self.find_conflicting_entry(other) {
118            Err(conflict)
119        } else {
120            self.merge_new(other);
121            Ok(())
122        }
123    }
124
125    /// Merges entries from `other`, but only for keys not already present in `self`.
126    fn merge_new(&mut self, other: &Self) {
127        for (key, value) in other.iter() {
128            self.0.entry(*key).or_insert_with(|| value.clone());
129        }
130    }
131
132    /// Finds the first key that exists in both `self` and `other` with different values.
133    ///
134    /// # Returns
135    /// - `Some` containing the conflicting key, its value from `self`, and the value from `other`.
136    /// - `None` if there are no conflicting values.
137    fn find_conflicting_entry(&self, other: &Self) -> Option<(MapEntry, Arc<[Felt]>)> {
138        for (key, new_value) in other.iter() {
139            if let Some(existing_value) = self.get(key)
140                && existing_value != new_value
141            {
142                // Found a conflict.
143                return Some(((*key, existing_value.clone()), new_value.clone()));
144            }
145        }
146        // No conflicts found.
147        None
148    }
149}
150
151impl From<BTreeMap<Word, Arc<[Felt]>>> for AdviceMap {
152    fn from(value: BTreeMap<Word, Arc<[Felt]>>) -> Self {
153        Self(value)
154    }
155}
156
157impl From<BTreeMap<Word, Vec<Felt>>> for AdviceMap {
158    fn from(value: BTreeMap<Word, Vec<Felt>>) -> Self {
159        value.into_iter().collect()
160    }
161}
162
163impl IntoIterator for AdviceMap {
164    type Item = (Word, Arc<[Felt]>);
165    type IntoIter = IntoIter<Word, Arc<[Felt]>>;
166
167    fn into_iter(self) -> Self::IntoIter {
168        self.0.into_iter()
169    }
170}
171
172impl<V> FromIterator<(Word, V)> for AdviceMap
173where
174    V: Into<Arc<[Felt]>>,
175{
176    fn from_iter<I>(iter: I) -> Self
177    where
178        I: IntoIterator<Item = (Word, V)>,
179    {
180        iter.into_iter()
181            .map(|(key, value)| (key, value.into()))
182            .collect::<BTreeMap<Word, Arc<[Felt]>>>()
183            .into()
184    }
185}
186
187impl<V> Extend<(Word, V)> for AdviceMap
188where
189    V: Into<Arc<[Felt]>>,
190{
191    fn extend<I>(&mut self, iter: I)
192    where
193        I: IntoIterator<Item = (Word, V)>,
194    {
195        self.0.extend(iter.into_iter().map(|(key, value)| (key, value.into())))
196    }
197}
198
199impl Serializable for AdviceMap {
200    fn write_into<W: ByteWriter>(&self, target: &mut W) {
201        target.write_usize(self.0.len());
202        for (key, values) in self.0.iter() {
203            target.write((key, values.to_vec()));
204        }
205    }
206
207    /// Returns the exact serialized size in bytes without allocating.
208    ///
209    /// # Panics
210    ///
211    /// Panics if the serialized size exceeds [`usize::MAX`].
212    fn get_size_hint(&self) -> usize {
213        self.0
214            .iter()
215            .try_fold(self.0.len().get_size_hint(), |size, (key, values)| {
216                let values_size = values.len().checked_mul(Felt::min_serialized_size())?;
217                size.checked_add(key.get_size_hint())?
218                    .checked_add(values.len().get_size_hint())?
219                    .checked_add(values_size)
220            })
221            .expect("advice map serialized size exceeds usize::MAX")
222    }
223}
224
225impl Deserializable for AdviceMap {
226    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
227        let mut map = BTreeMap::new();
228        let count = source.read_usize()?;
229        for _ in 0..count {
230            let (key, values): (Word, Vec<Felt>) = source.read()?;
231            if map.insert(key, Arc::from(values)).is_some() {
232                return Err(DeserializationError::InvalidValue(
233                    "duplicate advice map key in serialized payload".into(),
234                ));
235            }
236        }
237        Ok(Self(map))
238    }
239}
240
241#[cfg(test)]
242mod tests {
243    use super::*;
244
245    #[test]
246    fn test_advice_map_serialization() {
247        let mut map1 = AdviceMap::default();
248        map1.insert(Word::default(), vec![Felt::from_u32(1), Felt::from_u32(2)]);
249
250        let bytes = map1.to_bytes();
251
252        let map2 = AdviceMap::read_from_bytes(&bytes).unwrap();
253
254        assert_eq!(map1, map2);
255    }
256
257    #[test]
258    #[cfg_attr(
259        target_pointer_width = "32",
260        should_panic(expected = "advice map serialized size exceeds usize::MAX")
261    )]
262    fn size_hint_for_shared_values_exceeding_u32() {
263        // The values occupy 1 MiB, but serializing every reference would exceed 4 GiB.
264        let values: Arc<[Felt]> = vec![Felt::ZERO; 131_072].into();
265        let map: AdviceMap = (0..4096u32)
266            .map(|i| {
267                let key = Word::new([Felt::from_u32(i), Felt::ZERO, Felt::ZERO, Felt::ZERO]);
268                (key, Arc::clone(&values))
269            })
270            .collect();
271
272        let size = map.get_size_hint();
273        let expected = map.len().get_size_hint() as u64
274            + 4096
275                * (Word::SERIALIZED_SIZE as u64 + values.len().get_size_hint() as u64 + 1_048_576);
276        assert!(expected > u64::from(u32::MAX));
277        assert_eq!(size as u64, expected);
278    }
279
280    #[test]
281    fn read_from_rejects_duplicate_keys() {
282        use crate::serde::ByteWriter;
283
284        // Same key twice with different values. `write_into` never produces this, but a
285        // hand-written payload can.
286        let key = Word::default();
287        let mut bytes: Vec<u8> = Vec::new();
288        bytes.write_usize(2);
289        (key, vec![Felt::from_u32(1)]).write_into(&mut bytes);
290        (key, vec![Felt::from_u32(2)]).write_into(&mut bytes);
291
292        let err = AdviceMap::read_from_bytes(&bytes).unwrap_err();
293        assert!(matches!(err, DeserializationError::InvalidValue(_)));
294    }
295}
miden_core/advice/map.rs

miden_core/advice/
map.rs
