miden_processor/host/advice/
mod.rs

1use alloc::{collections::VecDeque, vec::Vec};
2
3use miden_core::{
4    Felt, WORD_SIZE, Word,
5    advice::{AdviceInputs, AdviceMap},
6    crypto::merkle::{InnerNodeInfo, MerklePath, MerkleStore, NodeIndex},
7    precompile::PrecompileRequest,
8};
9#[cfg(test)]
10use miden_core::{crypto::hash::Blake3_256, serde::Serializable};
11
12mod errors;
13pub use errors::AdviceError;
14
15use crate::{ExecutionOptions, host::AdviceMutation, processor::AdviceProviderInterface};
16
17// CONSTANTS
18// ================================================================================================
19
20/// Maximum number of elements allowed on the advice stack. Set to 2^17.
21const MAX_ADVICE_STACK_SIZE: usize = 1 << 17;
22
23// ADVICE PROVIDER
24// ================================================================================================
25
26/// An advice provider is a component through which the VM can request nondeterministic inputs from
27/// the host (i.e., result of a computation performed outside of the VM), as well as insert new data
28/// into the advice provider to be recovered by the host after the program has finished executing.
29///
30/// Advice map size limits are enforced here, rather than by `AdviceMap`, because they are part of
31/// execution policy. The provider owns the active `ExecutionOptions` and tracks the live advice map
32/// budget across initial advice, host mutations, and system-event inserts.
33///
34/// An advice provider consists of the following components:
35/// 1. Advice stack, which is a LIFO data structure. The processor can move the elements from the
36///    advice stack onto the operand stack, as well as push new elements onto the advice stack. The
37///    maximum number of elements that can be on the advice stack is 2^17.
38/// 2. Advice map, which is a key-value map where keys are words (4 field elements) and values are
39///    vectors of field elements. The processor can push the values from the map onto the advice
40///    stack, as well as insert new values into the map.
41/// 3. Merkle store, which contains structured data reducible to Merkle paths. The VM can request
42///    Merkle paths from the store, as well as mutate it by updating or merging nodes contained in
43///    the store.
44/// 4. Deferred precompile requests containing the calldata of any precompile requests made by the
45///    VM. The VM computes a commitment to the calldata of all the precompiles it requests. When
46///    verifying each call, this commitment must be recomputed and should match the one computed by
47///    the VM. After executing a program, the data in these requests can either
48///    - be included in the proof of the VM execution and verified natively alongside the VM proof,
49///      or,
50///    - used to produce a STARK proof using a precompile VM, which can be verified in the epilog of
51///      the program.
52#[derive(Debug, Clone, PartialEq, Eq)]
53pub struct AdviceProvider {
54    stack: VecDeque<Felt>,
55    map: AdviceMap,
56    map_element_count: usize,
57    max_map_value_size: usize,
58    max_map_elements: usize,
59    store: MerkleStore,
60    pc_requests: Vec<PrecompileRequest>,
61}
62
63impl Default for AdviceProvider {
64    fn default() -> Self {
65        Self::empty(&ExecutionOptions::default())
66    }
67}
68
69impl AdviceProvider {
70    /// Creates a new advice provider from the provided inputs and execution options.
71    ///
72    /// The advice map limits in `options` are enforced while loading the initial advice inputs.
73    pub fn new(inputs: AdviceInputs, options: &ExecutionOptions) -> Result<Self, AdviceError> {
74        let AdviceInputs { stack, map, store } = inputs;
75        let mut provider = Self::empty(options);
76        provider.extend_stack(stack)?;
77        provider.extend_merkle_store(store.inner_nodes());
78        provider.extend_map(&map)?;
79        Ok(provider)
80    }
81
82    fn empty(options: &ExecutionOptions) -> Self {
83        Self {
84            stack: VecDeque::new(),
85            map: AdviceMap::default(),
86            map_element_count: 0,
87            max_map_value_size: options.max_adv_map_value_size(),
88            max_map_elements: options.max_adv_map_elements(),
89            store: MerkleStore::default(),
90            pc_requests: Vec::new(),
91        }
92    }
93
94    pub(crate) fn set_options(&mut self, options: &ExecutionOptions) -> Result<(), AdviceError> {
95        Self::validate_map_values(&self.map, options.max_adv_map_value_size())?;
96        let map_element_count =
97            self.map.total_element_count().ok_or(AdviceError::AdvMapElementBudgetExceeded {
98                current: self.map_element_count,
99                added: usize::MAX,
100                max: options.max_adv_map_elements(),
101            })?;
102        if map_element_count > options.max_adv_map_elements() {
103            return Err(AdviceError::AdvMapElementBudgetExceeded {
104                current: 0,
105                added: map_element_count,
106                max: options.max_adv_map_elements(),
107            });
108        }
109
110        self.map_element_count = map_element_count;
111        self.max_map_value_size = options.max_adv_map_value_size();
112        self.max_map_elements = options.max_adv_map_elements();
113        Ok(())
114    }
115
116    #[cfg(test)]
117    #[expect(dead_code)]
118    pub(crate) fn merkle_store(&self) -> &MerkleStore {
119        &self.store
120    }
121
122    /// Applies the mutations given in order to the `AdviceProvider`.
123    pub fn apply_mutations(
124        &mut self,
125        mutations: impl IntoIterator<Item = AdviceMutation>,
126    ) -> Result<(), AdviceError> {
127        mutations.into_iter().try_for_each(|mutation| self.apply_mutation(mutation))
128    }
129
130    fn apply_mutation(&mut self, mutation: AdviceMutation) -> Result<(), AdviceError> {
131        match mutation {
132            AdviceMutation::ExtendStack { values } => {
133                self.extend_stack(values)?;
134            },
135            AdviceMutation::ExtendMap { other } => {
136                self.extend_map(&other)?;
137            },
138            AdviceMutation::ExtendMerkleStore { infos } => {
139                self.extend_merkle_store(infos);
140            },
141            AdviceMutation::ExtendPrecompileRequests { data } => {
142                self.extend_precompile_requests(data);
143            },
144        }
145        Ok(())
146    }
147
148    /// Returns a stable fingerprint of the advice state.
149    ///
150    /// The fingerprint is insensitive to advice-map insertion order and Merkle-store insertion
151    /// order, but it still reflects advice-stack order and precompile-request order.
152    #[cfg(test)]
153    #[must_use]
154    pub(crate) fn fingerprint(&self) -> [u8; 32] {
155        let stack = self.stack.iter().copied().collect::<Vec<_>>().to_bytes();
156        let map = self.map.to_bytes();
157        let mut store_nodes = self
158            .store
159            .inner_nodes()
160            .map(|info| (info.value, info.left, info.right))
161            .collect::<Vec<_>>();
162        store_nodes.sort_unstable_by(|lhs, rhs| {
163            lhs.0
164                .cmp(&rhs.0)
165                .then_with(|| lhs.1.cmp(&rhs.1))
166                .then_with(|| lhs.2.cmp(&rhs.2))
167        });
168        let store = store_nodes
169            .into_iter()
170            .flat_map(|(value, left, right)| [value, left, right])
171            .collect::<Vec<_>>()
172            .to_bytes();
173        let precompile_requests = self.pc_requests.to_bytes();
174        Blake3_256::hash_iter(
175            [
176                stack.as_slice(),
177                map.as_slice(),
178                store.as_slice(),
179                precompile_requests.as_slice(),
180            ]
181            .into_iter(),
182        )
183        .into()
184    }
185
186    // ADVICE STACK
187    // --------------------------------------------------------------------------------------------
188
189    /// Pops an element from the advice stack and returns it.
190    ///
191    /// # Errors
192    /// Returns an error if the advice stack is empty.
193    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
194        self.stack.pop_front().ok_or(AdviceError::StackReadFailed)
195    }
196
197    /// Pops a word (4 elements) from the advice stack and returns it.
198    ///
199    /// Note: a word is popped off the stack element-by-element. For example, a `[d, c, b, a, ...]`
200    /// stack (i.e., `d` is at the top of the stack) will yield `[d, c, b, a]`.
201    ///
202    /// # Errors
203    /// Returns an error if the advice stack does not contain a full word.
204    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
205        if self.stack.len() < 4 {
206            return Err(AdviceError::StackReadFailed);
207        }
208
209        let w0 = self.stack.pop_front().expect("checked len");
210        let w1 = self.stack.pop_front().expect("checked len");
211        let w2 = self.stack.pop_front().expect("checked len");
212        let w3 = self.stack.pop_front().expect("checked len");
213
214        Ok(Word::new([w0, w1, w2, w3]))
215    }
216
217    /// Pops a double word (8 elements) from the advice stack and returns them.
218    ///
219    /// Note: words are popped off the stack element-by-element. For example, a
220    /// `[h, g, f, e, d, c, b, a, ...]` stack (i.e., `h` is at the top of the stack) will yield
221    /// two words: `[h, g, f,e ], [d, c, b, a]`.
222    ///
223    /// # Errors
224    /// Returns an error if the advice stack does not contain two words.
225    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
226        let word0 = self.pop_stack_word()?;
227        let word1 = self.pop_stack_word()?;
228
229        Ok([word0, word1])
230    }
231
232    /// Checks that pushing `count` elements would not exceed the advice stack size limit.
233    fn check_stack_capacity(&self, count: usize) -> Result<(), AdviceError> {
234        let resulting_size =
235            self.stack.len().checked_add(count).ok_or(AdviceError::StackSizeExceeded {
236                push_count: count,
237                max: MAX_ADVICE_STACK_SIZE,
238            })?;
239        if resulting_size > MAX_ADVICE_STACK_SIZE {
240            return Err(AdviceError::StackSizeExceeded {
241                push_count: count,
242                max: MAX_ADVICE_STACK_SIZE,
243            });
244        }
245        Ok(())
246    }
247
248    /// Pushes a single value onto the advice stack.
249    pub fn push_stack(&mut self, value: Felt) -> Result<(), AdviceError> {
250        self.check_stack_capacity(1)?;
251        self.stack.push_front(value);
252        Ok(())
253    }
254
255    /// Pushes a word (4 elements) onto the stack.
256    pub fn push_stack_word(&mut self, word: &Word) -> Result<(), AdviceError> {
257        self.check_stack_capacity(4)?;
258        for &value in word.iter().rev() {
259            self.stack.push_front(value);
260        }
261        Ok(())
262    }
263
264    /// Fetches a list of elements under the specified key from the advice map and pushes them onto
265    /// the advice stack.
266    ///
267    /// If `include_len` is set to true, this also pushes the number of elements onto the advice
268    /// stack.
269    ///
270    /// If `pad_to` is not equal to 0, the elements list obtained from the advice map will be padded
271    /// with zeros, increasing its length to the next multiple of `pad_to`.
272    ///
273    /// Note: this operation doesn't consume the map element so it can be called multiple times
274    /// for the same key.
275    ///
276    /// # Example
277    /// Given an advice stack `[a, b, c, ...]`, and a map `x |-> [d, e, f]`:
278    ///
279    /// A call `push_stack(AdviceSource::Map { key: x, include_len: false, pad_to: 0 })` will result
280    /// in advice stack: `[d, e, f, a, b, c, ...]`.
281    ///
282    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 0 })` will result
283    /// in advice stack: `[3, d, e, f, a, b, c, ...]`.
284    ///
285    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 4 })` will result
286    /// in advice stack: `[3, d, e, f, 0, a, b, c, ...]`.
287    ///
288    /// # Errors
289    /// Returns an error if the key was not found in the key-value map.
290    pub fn push_from_map(
291        &mut self,
292        key: Word,
293        include_len: bool,
294        pad_to: u8,
295    ) -> Result<(), AdviceError> {
296        let values = self.map.get(&key).ok_or(AdviceError::MapKeyNotFound { key })?;
297
298        // Calculate total elements to push including padding and optional length prefix
299        let num_pad_elements = if pad_to != 0 {
300            values.len().next_multiple_of(pad_to as usize) - values.len()
301        } else {
302            0
303        };
304        let total_push = values
305            .len()
306            .checked_add(num_pad_elements)
307            .and_then(|n| n.checked_add(if include_len { 1 } else { 0 }))
308            .ok_or(AdviceError::StackSizeExceeded {
309                push_count: usize::MAX,
310                max: MAX_ADVICE_STACK_SIZE,
311            })?;
312        self.check_stack_capacity(total_push)?;
313
314        // if pad_to was provided (not equal 0), push some zeros to the advice stack so that the
315        // final (padded) elements list length will be the next multiple of pad_to
316        for _ in 0..num_pad_elements {
317            self.stack.push_front(Felt::default());
318        }
319
320        // Treat map values as already canonical sequences of FELTs.
321        // The advice stack is LIFO; extend in reverse so that the first element of `values`
322        // becomes the first element returned by a subsequent `adv_push`.
323        for &value in values.iter().rev() {
324            self.stack.push_front(value);
325        }
326        if include_len {
327            self.stack.push_front(Felt::new_unchecked(values.len() as u64));
328        }
329        Ok(())
330    }
331
332    /// Returns the current stack as a vector ordered from top (index 0) to bottom.
333    pub fn stack(&self) -> Vec<Felt> {
334        self.stack.iter().copied().collect()
335    }
336
337    /// Extends the stack with the given elements.
338    pub fn extend_stack<I>(&mut self, iter: I) -> Result<(), AdviceError>
339    where
340        I: IntoIterator<Item = Felt>,
341    {
342        let values: Vec<Felt> = iter.into_iter().collect();
343        self.check_stack_capacity(values.len())?;
344        for value in values.into_iter().rev() {
345            self.stack.push_front(value);
346        }
347        Ok(())
348    }
349
350    // ADVICE MAP
351    // --------------------------------------------------------------------------------------------
352
353    /// Returns true if the key has a corresponding value in the map.
354    pub fn contains_map_key(&self, key: &Word) -> bool {
355        self.map.contains_key(key)
356    }
357
358    /// Returns a reference to the value(s) associated with the specified key in the advice map.
359    pub fn get_mapped_values(&self, key: &Word) -> Option<&[Felt]> {
360        self.map.get(key).map(AsRef::as_ref)
361    }
362
363    fn validate_map_values(map: &AdviceMap, max_value_size: usize) -> Result<(), AdviceError> {
364        for (_, values) in map.iter() {
365            if values.len() > max_value_size {
366                return Err(AdviceError::AdvMapValueSizeExceeded {
367                    size: values.len(),
368                    max: max_value_size,
369                });
370            }
371        }
372        Ok(())
373    }
374
375    fn entry_element_count(value_len: usize) -> Option<usize> {
376        WORD_SIZE.checked_add(value_len)
377    }
378
379    fn check_map_value_size(&self, size: usize) -> Result<(), AdviceError> {
380        if size > self.max_map_value_size {
381            return Err(AdviceError::AdvMapValueSizeExceeded {
382                size,
383                max: self.max_map_value_size,
384            });
385        }
386        Ok(())
387    }
388
389    fn check_map_element_budget(&self, added: usize) -> Result<(), AdviceError> {
390        let Some(new_total) = self.map_element_count.checked_add(added) else {
391            return Err(AdviceError::AdvMapElementBudgetExceeded {
392                current: self.map_element_count,
393                added,
394                max: self.max_map_elements,
395            });
396        };
397
398        if new_total > self.max_map_elements {
399            return Err(AdviceError::AdvMapElementBudgetExceeded {
400                current: self.map_element_count,
401                added,
402                max: self.max_map_elements,
403            });
404        }
405        Ok(())
406    }
407
408    /// Inserts the provided value into the advice map under the specified key.
409    ///
410    /// The values in the advice map can be moved onto the advice stack by invoking
411    /// the [AdviceProvider::push_from_map()] method.
412    ///
413    /// Returns an error if the specified key is already present in the advice map.
414    pub fn insert_into_map(&mut self, key: Word, values: Vec<Felt>) -> Result<(), AdviceError> {
415        match self.map.get(&key) {
416            Some(existing_values) => {
417                let existing_values = existing_values.as_ref();
418                if existing_values != values {
419                    return Err(AdviceError::MapKeyAlreadyPresent {
420                        key,
421                        prev_values: existing_values.to_vec(),
422                        new_values: values,
423                    });
424                }
425            },
426            None => {
427                self.check_map_value_size(values.len())?;
428                let added = Self::entry_element_count(values.len()).ok_or(
429                    AdviceError::AdvMapElementBudgetExceeded {
430                        current: self.map_element_count,
431                        added: usize::MAX,
432                        max: self.max_map_elements,
433                    },
434                )?;
435                self.check_map_element_budget(added)?;
436                self.map.insert(key, values);
437                self.map_element_count += added;
438            },
439        }
440        Ok(())
441    }
442
443    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
444    ///
445    /// Returns an error if any new entry already exists with the same key but a different value
446    /// than the one currently stored. The current map remains unchanged.
447    pub fn extend_map(&mut self, other: &AdviceMap) -> Result<(), AdviceError> {
448        let mut added = 0usize;
449        for (key, values) in other.iter() {
450            if let Some(existing_values) = self.map.get(key) {
451                if existing_values.as_ref() != values.as_ref() {
452                    return Err(AdviceError::MapKeyAlreadyPresent {
453                        key: *key,
454                        prev_values: existing_values.to_vec(),
455                        new_values: values.to_vec(),
456                    });
457                }
458                continue;
459            }
460
461            self.check_map_value_size(values.len())?;
462            let entry_elements = Self::entry_element_count(values.len()).ok_or(
463                AdviceError::AdvMapElementBudgetExceeded {
464                    current: self.map_element_count,
465                    added: usize::MAX,
466                    max: self.max_map_elements,
467                },
468            )?;
469            added = added.checked_add(entry_elements).ok_or(
470                AdviceError::AdvMapElementBudgetExceeded {
471                    current: self.map_element_count,
472                    added: usize::MAX,
473                    max: self.max_map_elements,
474                },
475            )?;
476        }
477        self.check_map_element_budget(added)?;
478
479        self.map.merge(other).map_err(|((key, prev_values), new_values)| {
480            AdviceError::MapKeyAlreadyPresent {
481                key,
482                prev_values: prev_values.to_vec(),
483                new_values: new_values.to_vec(),
484            }
485        })?;
486        self.map_element_count += added;
487        Ok(())
488    }
489
490    // MERKLE STORE
491    // --------------------------------------------------------------------------------------------
492
493    /// Returns a node at the specified depth and index in a Merkle tree with the given root.
494    ///
495    /// # Errors
496    /// Returns an error if:
497    /// - A Merkle tree for the specified root cannot be found in this advice provider.
498    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
499    ///   by the specified root.
500    /// - Value of the node at the specified depth and index is not known to this advice provider.
501    pub fn get_tree_node(&self, root: Word, depth: Felt, index: Felt) -> Result<Word, AdviceError> {
502        let index = NodeIndex::from_elements(&depth, &index)
503            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
504        self.store.get_node(root, index).map_err(AdviceError::MerkleStoreLookupFailed)
505    }
506
507    /// Returns true if a path to a node at the specified depth and index in a Merkle tree with the
508    /// specified root exists in this Merkle store.
509    ///
510    /// # Errors
511    /// Returns an error if accessing the Merkle store fails.
512    pub fn has_merkle_path(
513        &self,
514        root: Word,
515        depth: Felt,
516        index: Felt,
517    ) -> Result<bool, AdviceError> {
518        let index = NodeIndex::from_elements(&depth, &index)
519            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
520
521        Ok(self.store.has_path(root, index))
522    }
523
524    /// Returns a path to a node at the specified depth and index in a Merkle tree with the
525    /// specified root.
526    ///
527    /// # Errors
528    /// Returns an error if:
529    /// - A Merkle tree for the specified root cannot be found in this advice provider.
530    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
531    ///   by the specified root.
532    /// - Path to the node at the specified depth and index is not known to this advice provider.
533    pub fn get_merkle_path(
534        &self,
535        root: Word,
536        depth: Felt,
537        index: Felt,
538    ) -> Result<MerklePath, AdviceError> {
539        let index = NodeIndex::from_elements(&depth, &index)
540            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
541        self.store
542            .get_path(root, index)
543            .map(|value| value.path)
544            .map_err(AdviceError::MerkleStoreLookupFailed)
545    }
546
547    /// Updates a node at the specified depth and index in a Merkle tree with the specified root;
548    /// returns the Merkle path from the updated node to the new root, together with the new root.
549    ///
550    /// The tree is cloned prior to the update. Thus, the advice provider retains the original and
551    /// the updated tree.
552    ///
553    /// # Errors
554    /// Returns an error if:
555    /// - A Merkle tree for the specified root cannot be found in this advice provider.
556    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
557    ///   by the specified root.
558    /// - Path to the leaf at the specified index in the specified Merkle tree is not known to this
559    ///   advice provider.
560    pub fn update_merkle_node(
561        &mut self,
562        root: Word,
563        depth: Felt,
564        index: Felt,
565        value: Word,
566    ) -> Result<(MerklePath, Word), AdviceError> {
567        let node_index = NodeIndex::from_elements(&depth, &index)
568            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
569        self.store
570            .set_node(root, node_index, value)
571            .map(|root| (root.path, root.root))
572            .map_err(AdviceError::MerkleStoreUpdateFailed)
573    }
574
575    /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
576    /// specified roots. The root of the new tree is defined as `hash(left_root, right_root)`.
577    ///
578    /// After the operation, both the original trees and the new tree remains in the advice
579    /// provider (i.e., the input trees are not removed).
580    ///
581    /// It is not checked whether a Merkle tree for either of the specified roots can be found in
582    /// this advice provider.
583    pub fn merge_roots(&mut self, lhs: Word, rhs: Word) -> Result<Word, AdviceError> {
584        self.store.merge_roots(lhs, rhs).map_err(AdviceError::MerkleStoreMergeFailed)
585    }
586
587    /// Returns true if the Merkle root exists for the advice provider Merkle store.
588    pub fn has_merkle_root(&self, root: Word) -> bool {
589        self.store.get_node(root, NodeIndex::root()).is_ok()
590    }
591
592    /// Extends the [MerkleStore] with the given nodes.
593    pub fn extend_merkle_store<I>(&mut self, iter: I)
594    where
595        I: IntoIterator<Item = InnerNodeInfo>,
596    {
597        self.store.extend(iter);
598    }
599
600    // PRECOMPILE REQUESTS
601    // --------------------------------------------------------------------------------------------
602
603    /// Returns a reference to the precompile requests.
604    ///
605    /// Ordering is the same as the order in which requests are issued during execution. This
606    /// ordering is relied upon when recomputing the precompile sponge during verification.
607    pub fn precompile_requests(&self) -> &[PrecompileRequest] {
608        &self.pc_requests
609    }
610
611    /// Extends the precompile requests with the given entries.
612    pub fn extend_precompile_requests<I>(&mut self, iter: I)
613    where
614        I: IntoIterator<Item = PrecompileRequest>,
615    {
616        self.pc_requests.extend(iter);
617    }
618
619    /// Moves all accumulated precompile requests out of this provider, leaving it empty.
620    ///
621    /// Intended for proof packaging, where requests are serialized into the proof and no longer
622    /// needed in the provider after consumption.
623    pub fn take_precompile_requests(&mut self) -> Vec<PrecompileRequest> {
624        core::mem::take(&mut self.pc_requests)
625    }
626
627    // MUTATORS
628    // --------------------------------------------------------------------------------------------
629
630    /// Extends the contents of this instance with the contents of an `AdviceInputs`.
631    pub fn extend_from_inputs(&mut self, inputs: &AdviceInputs) -> Result<(), AdviceError> {
632        self.extend_stack(inputs.stack.iter().cloned())?;
633        self.extend_merkle_store(inputs.store.inner_nodes());
634        self.extend_map(&inputs.map)
635    }
636
637    /// Consumes `self` and return its parts (stack, map, store, precompile_requests).
638    ///
639    /// The returned stack vector is ordered from top (index 0) to bottom.
640    pub fn into_parts(self) -> (Vec<Felt>, AdviceMap, MerkleStore, Vec<PrecompileRequest>) {
641        (self.stack.into_iter().collect(), self.map, self.store, self.pc_requests)
642    }
643}
644
645// ADVICE PROVIDER INTERFACE IMPLEMENTATION
646// ================================================================================================
647
648impl AdviceProviderInterface for AdviceProvider {
649    #[inline(always)]
650    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
651        self.pop_stack()
652    }
653
654    #[inline(always)]
655    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
656        self.pop_stack_word()
657    }
658
659    #[inline(always)]
660    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
661        self.pop_stack_dword()
662    }
663
664    #[inline(always)]
665    fn get_merkle_path(
666        &self,
667        root: Word,
668        depth: Felt,
669        index: Felt,
670    ) -> Result<Option<MerklePath>, AdviceError> {
671        self.get_merkle_path(root, depth, index).map(Some)
672    }
673
674    #[inline(always)]
675    fn update_merkle_node(
676        &mut self,
677        root: Word,
678        depth: Felt,
679        index: Felt,
680        value: Word,
681    ) -> Result<Option<MerklePath>, AdviceError> {
682        self.update_merkle_node(root, depth, index, value).map(|(path, _)| Some(path))
683    }
684}
685
686#[cfg(test)]
687mod tests {
688    use alloc::{collections::BTreeMap, vec, vec::Vec};
689
690    use miden_core::WORD_SIZE;
691
692    use super::AdviceProvider;
693    use crate::{
694        AdviceInputs, ExecutionOptions, Felt, Word,
695        advice::{AdviceError, AdviceMap},
696        crypto::merkle::{MerkleStore, MerkleTree},
697    };
698
699    fn make_leaf(seed: u64) -> Word {
700        [
701            Felt::new_unchecked(seed),
702            Felt::new_unchecked(seed + 1),
703            Felt::new_unchecked(seed + 2),
704            Felt::new_unchecked(seed + 3),
705        ]
706        .into()
707    }
708
709    #[test]
710    fn fingerprint_is_stable_across_merkle_store_insertion_order() {
711        let tree_a =
712            MerkleTree::new([make_leaf(1), make_leaf(5), make_leaf(9), make_leaf(13)]).unwrap();
713        let tree_b =
714            MerkleTree::new([make_leaf(17), make_leaf(21), make_leaf(25), make_leaf(29)]).unwrap();
715
716        let mut store_a = MerkleStore::default();
717        store_a.extend(tree_a.inner_nodes());
718        store_a.extend(tree_b.inner_nodes());
719
720        let mut store_b = MerkleStore::default();
721        store_b.extend(tree_b.inner_nodes());
722        store_b.extend(tree_a.inner_nodes());
723
724        assert_eq!(store_a, store_b);
725
726        let provider_a = AdviceProvider::new(
727            AdviceInputs::default().with_merkle_store(store_a),
728            &Default::default(),
729        )
730        .unwrap();
731        let provider_b = AdviceProvider::new(
732            AdviceInputs::default().with_merkle_store(store_b),
733            &Default::default(),
734        )
735        .unwrap();
736
737        assert_eq!(provider_a, provider_b);
738        assert_eq!(provider_a.fingerprint(), provider_b.fingerprint());
739    }
740
741    #[test]
742    fn advice_map_insert_respects_element_budget() {
743        let options = ExecutionOptions::default().with_max_adv_map_elements(WORD_SIZE + 1);
744        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
745
746        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
747
748        let err = provider.insert_into_map(make_leaf(1), vec![Felt::ONE]).unwrap_err();
749        assert!(matches!(
750            err,
751            AdviceError::AdvMapElementBudgetExceeded { current: 5, added: 5, max: 5 }
752        ));
753
754        assert_eq!(provider.map.len(), 1);
755        assert!(provider.contains_map_key(&make_leaf(0)));
756        assert!(!provider.contains_map_key(&make_leaf(1)));
757    }
758
759    #[test]
760    fn advice_map_insert_respects_value_limit() {
761        let options = ExecutionOptions::default().with_max_adv_map_value_size(1);
762        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
763        let values = vec![Felt::ONE, Felt::new_unchecked(2)];
764
765        let err = provider.insert_into_map(make_leaf(0), values).unwrap_err();
766        assert!(matches!(err, AdviceError::AdvMapValueSizeExceeded { size: 2, max: 1 }));
767
768        assert_eq!(provider.map.len(), 0);
769    }
770
771    #[test]
772    fn advice_map_extend_respects_element_budget_atomically() {
773        let options = ExecutionOptions::default().with_max_adv_map_elements(2 * (WORD_SIZE + 1));
774        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
775        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
776        let other = advice_map_from_entries(1..3, 1);
777
778        let err = provider.extend_map(&other).unwrap_err();
779        assert!(matches!(
780            err,
781            AdviceError::AdvMapElementBudgetExceeded { current: 5, added: 10, max: 10 }
782        ));
783
784        assert_eq!(provider.map.len(), 1);
785        assert!(provider.contains_map_key(&make_leaf(0)));
786        assert!(!provider.contains_map_key(&make_leaf(1)));
787        assert!(!provider.contains_map_key(&make_leaf(2)));
788    }
789
790    #[test]
791    fn advice_map_extend_respects_value_limit_atomically() {
792        let options = ExecutionOptions::default().with_max_adv_map_value_size(1);
793        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
794        let other = advice_map_from_entries(0..2, 2);
795
796        let err = provider.extend_map(&other).unwrap_err();
797        assert!(matches!(err, AdviceError::AdvMapValueSizeExceeded { size: 2, max: 1 }));
798
799        assert_eq!(provider.map.len(), 0);
800    }
801
802    #[test]
803    fn initial_advice_map_respects_element_budget() {
804        let options = ExecutionOptions::default().with_max_adv_map_elements(WORD_SIZE);
805        let inputs = AdviceInputs::default().with_map([(make_leaf(0), vec![Felt::ONE])]);
806
807        let err = AdviceProvider::new(inputs, &options).unwrap_err();
808        assert!(matches!(
809            err,
810            AdviceError::AdvMapElementBudgetExceeded { current: 0, added: 5, max: 4 }
811        ));
812    }
813
814    fn advice_map_from_entries(keys: impl Iterator<Item = u64>, value_len: usize) -> AdviceMap {
815        keys.map(|key| {
816            let values = (0..value_len)
817                .map(|offset| Felt::new_unchecked(key + offset as u64))
818                .collect::<Vec<_>>();
819            (make_leaf(key), values)
820        })
821        .collect::<BTreeMap<_, _>>()
822        .into()
823    }
824}
miden_processor/host/advice/mod.rs

miden_processor/host/advice/
mod.rs
