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    chiplets::hasher,
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. [`hasher::hash_elements`] binds the entry length, and
90    /// [`hasher::hash_words`] folds the ordered entry commitments into the final map commitment.
91    pub fn commitment(&self) -> Word {
92        let entry_commitments = self
93            .iter()
94            .map(|(key, values)| {
95                let mut elements = Vec::with_capacity(WORD_SIZE + values.len());
96                elements.extend_from_slice(key.as_elements());
97                elements.extend_from_slice(values);
98                hasher::hash_elements(&elements)
99            })
100            .collect::<Vec<_>>();
101
102        hasher::hash_words(&entry_commitments)
103    }
104
105    /// Gets the given key's corresponding entry in the map for in-place manipulation.
106    pub fn entry(&mut self, key: Word) -> Entry<'_, Word, Arc<[Felt]>> {
107        self.0.entry(key)
108    }
109
110    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
111    ///
112    /// If an entry from the new map already exists with the same key but different value,
113    /// an error is returned containing the existing entry along with the value that would replace
114    /// it. The current map remains unchanged.
115    pub fn merge(&mut self, other: &Self) -> Result<(), (MapEntry, Arc<[Felt]>)> {
116        if let Some(conflict) = self.find_conflicting_entry(other) {
117            Err(conflict)
118        } else {
119            self.merge_new(other);
120            Ok(())
121        }
122    }
123
124    /// Merges entries from `other`, but only for keys not already present in `self`.
125    fn merge_new(&mut self, other: &Self) {
126        for (key, value) in other.iter() {
127            self.0.entry(*key).or_insert_with(|| value.clone());
128        }
129    }
130
131    /// Finds the first key that exists in both `self` and `other` with different values.
132    ///
133    /// # Returns
134    /// - `Some` containing the conflicting key, its value from `self`, and the value from `other`.
135    /// - `None` if there are no conflicting values.
136    fn find_conflicting_entry(&self, other: &Self) -> Option<(MapEntry, Arc<[Felt]>)> {
137        for (key, new_value) in other.iter() {
138            if let Some(existing_value) = self.get(key)
139                && existing_value != new_value
140            {
141                // Found a conflict.
142                return Some(((*key, existing_value.clone()), new_value.clone()));
143            }
144        }
145        // No conflicts found.
146        None
147    }
148}
149
150impl From<BTreeMap<Word, Arc<[Felt]>>> for AdviceMap {
151    fn from(value: BTreeMap<Word, Arc<[Felt]>>) -> Self {
152        Self(value)
153    }
154}
155
156impl From<BTreeMap<Word, Vec<Felt>>> for AdviceMap {
157    fn from(value: BTreeMap<Word, Vec<Felt>>) -> Self {
158        value.into_iter().collect()
159    }
160}
161
162impl IntoIterator for AdviceMap {
163    type Item = (Word, Arc<[Felt]>);
164    type IntoIter = IntoIter<Word, Arc<[Felt]>>;
165
166    fn into_iter(self) -> Self::IntoIter {
167        self.0.into_iter()
168    }
169}
170
171impl<V> FromIterator<(Word, V)> for AdviceMap
172where
173    V: Into<Arc<[Felt]>>,
174{
175    fn from_iter<I>(iter: I) -> Self
176    where
177        I: IntoIterator<Item = (Word, V)>,
178    {
179        iter.into_iter()
180            .map(|(key, value)| (key, value.into()))
181            .collect::<BTreeMap<Word, Arc<[Felt]>>>()
182            .into()
183    }
184}
185
186impl<V> Extend<(Word, V)> for AdviceMap
187where
188    V: Into<Arc<[Felt]>>,
189{
190    fn extend<I>(&mut self, iter: I)
191    where
192        I: IntoIterator<Item = (Word, V)>,
193    {
194        self.0.extend(iter.into_iter().map(|(key, value)| (key, value.into())))
195    }
196}
197
198impl Serializable for AdviceMap {
199    fn write_into<W: ByteWriter>(&self, target: &mut W) {
200        target.write_usize(self.0.len());
201        for (key, values) in self.0.iter() {
202            target.write((key, values.to_vec()));
203        }
204    }
205}
206
207impl Deserializable for AdviceMap {
208    fn read_from<R: ByteReader>(source: &mut R) -> Result<Self, DeserializationError> {
209        let mut map = BTreeMap::new();
210        let count = source.read_usize()?;
211        for _ in 0..count {
212            let (key, values): (Word, Vec<Felt>) = source.read()?;
213            if map.insert(key, Arc::from(values)).is_some() {
214                return Err(DeserializationError::InvalidValue(
215                    "duplicate advice map key in serialized payload".into(),
216                ));
217            }
218        }
219        Ok(Self(map))
220    }
221}
222
223#[cfg(test)]
224mod tests {
225    use miden_crypto::hash::eidos::Eidos;
226
227    use super::*;
228
229    #[test]
230    fn test_advice_map_serialization() {
231        let mut map1 = AdviceMap::default();
232        map1.insert(Word::default(), vec![Felt::from_u32(1), Felt::from_u32(2)]);
233
234        let bytes = map1.to_bytes();
235
236        let map2 = AdviceMap::read_from_bytes(&bytes).unwrap();
237
238        assert_eq!(map1, map2);
239    }
240
241    #[cfg(feature = "arbitrary")]
242    ::proptest::proptest! {
243        /// The duplicate-key rejection covers the FULL repetition class: a repeated key
244        /// is rejected even when the two values are EQUAL (the map is a set of bindings,
245        /// not a multiset), and for arbitrary keys and values — `write_into` never
246        /// produces a repeated key (the BTreeMap source cannot), but a hand-written
247        /// payload can.
248        #[test]
249        fn prop_rejects_generated_duplicate_key_payloads(
250            (key, first, second) in (
251                proptest::prelude::any::<Word>(),
252                proptest::prelude::any::<Vec<Felt>>(),
253                proptest::prelude::any::<Vec<Felt>>(),
254            ),
255        ) {
256            use crate::serde::ByteWriter;
257
258            for (repeated, label) in [(second, "different value"), (first.clone(), "equal value")]
259            {
260                let mut bytes = Vec::new();
261                bytes.write_usize(2);
262                (key, first.clone()).write_into(&mut bytes);
263                (key, repeated).write_into(&mut bytes);
264
265                let err = AdviceMap::read_from_bytes(&bytes).unwrap_err();
266                let DeserializationError::InvalidValue(message) = err else {
267                    panic!("expected InvalidValue for a duplicate key with {label}, got {err:?}");
268                };
269                assert_eq!(
270                    message, "duplicate advice map key in serialized payload",
271                    "expected the duplicate-key rejection for {label}",
272                );
273            }
274        }
275    }
276
277    #[test]
278    fn advice_map_commitment_matches_eidos_primitive() {
279        let low_key =
280            Word::new([Felt::from_u32(1), Felt::from_u32(2), Felt::from_u32(3), Felt::from_u32(4)]);
281        let high_key =
282            Word::new([Felt::from_u32(9), Felt::from_u32(8), Felt::from_u32(7), Felt::from_u32(6)]);
283        let low_values = [Felt::from_u32(11), Felt::from_u32(12)];
284        let high_values = [Felt::from_u32(21), Felt::from_u32(22), Felt::from_u32(23)];
285
286        // Insert in reverse key order to pin that the BTreeMap's canonical key order is what gets
287        // committed.
288        let map = AdviceMap::from_iter([
289            (high_key, high_values.to_vec()),
290            (low_key, low_values.to_vec()),
291        ]);
292        let low_entry = [low_key.as_elements(), low_values.as_slice()].concat();
293        let high_entry = [high_key.as_elements(), high_values.as_slice()].concat();
294        let expected = Eidos::hash_words(&[
295            Eidos::hash_elements(&low_entry),
296            Eidos::hash_elements(&high_entry),
297        ]);
298
299        assert_eq!(map.commitment(), expected);
300    }
301
302    #[test]
303    fn read_from_rejects_duplicate_keys() {
304        use crate::serde::ByteWriter;
305
306        // Same key twice with different values. `write_into` never produces this, but a
307        // hand-written payload can.
308        let key = Word::default();
309        let mut bytes: Vec<u8> = Vec::new();
310        bytes.write_usize(2);
311        (key, vec![Felt::from_u32(1)]).write_into(&mut bytes);
312        (key, vec![Felt::from_u32(2)]).write_into(&mut bytes);
313
314        let err = AdviceMap::read_from_bytes(&bytes).unwrap_err();
315        assert!(matches!(err, DeserializationError::InvalidValue(_)));
316    }
317}
miden_core/advice/map.rs

miden_core/advice/
map.rs
