miden_processor/host/advice/
mod.rs

1use alloc::{collections::BTreeSet, vec::Vec};
2
3use miden_core::{
4    Felt, WORD_SIZE, Word,
5    advice::{AdviceInputs, AdviceMap, AdviceStack},
6    crypto::{
7        hash::Poseidon2,
8        merkle::{InnerNodeInfo, MerkleError, MerklePath, MerkleStore, NodeIndex},
9    },
10};
11#[cfg(test)]
12use miden_core::{crypto::hash::Blake3_256, serde::Serializable};
13
14mod errors;
15pub use errors::AdviceError;
16
17use crate::{ExecutionOptions, host::AdviceMutation, processor::AdviceProviderInterface};
18
19// CONSTANTS
20// ================================================================================================
21
22/// Maximum number of elements allowed on the advice stack. Set to 2^17.
23pub const MAX_ADVICE_STACK_SIZE: usize = 1 << 17;
24
25trait MerkleStoreBudget {
26    fn contains_internal_node(&self, root: Word) -> bool;
27
28    fn new_internal_node_count<I>(&self, roots: I) -> usize
29    where
30        I: IntoIterator<Item = Word>;
31
32    fn new_path_node_count(
33        &self,
34        index: u64,
35        node: Word,
36        path: &MerklePath,
37    ) -> Result<usize, MerkleError>;
38}
39
40impl MerkleStoreBudget for MerkleStore {
41    fn contains_internal_node(&self, root: Word) -> bool {
42        self.get_node(root, NodeIndex::root()).is_ok()
43    }
44
45    fn new_internal_node_count<I>(&self, roots: I) -> usize
46    where
47        I: IntoIterator<Item = Word>,
48    {
49        let mut seen_roots = BTreeSet::new();
50        let mut count = 0;
51
52        for root in roots {
53            if seen_roots.insert(root) && !self.contains_internal_node(root) {
54                count += 1;
55            }
56        }
57
58        count
59    }
60
61    fn new_path_node_count(
62        &self,
63        index: u64,
64        node: Word,
65        path: &MerklePath,
66    ) -> Result<usize, MerkleError> {
67        path.authenticated_nodes(index, node)
68            .map(|nodes| self.new_internal_node_count(nodes.map(|node| node.value)))
69    }
70}
71
72// ADVICE PROVIDER
73// ================================================================================================
74
75/// An advice provider is a component through which the VM can request nondeterministic inputs from
76/// the host (i.e., result of a computation performed outside of the VM), as well as insert new data
77/// into the advice provider to be recovered by the host after the program has finished executing.
78///
79/// Advice map size limits are enforced here, rather than by `AdviceMap`, because they are part of
80/// execution policy. The provider owns the active `ExecutionOptions` and tracks the live advice map
81/// budget across initial advice, host mutations, and system-event inserts.
82///
83/// An advice provider consists of the following components:
84/// 1. Advice stack, which is a LIFO data structure. The processor can move the elements from the
85///    advice stack onto the operand stack, as well as push new elements onto the advice stack. The
86///    maximum number of elements that can be on the advice stack is 2^17.
87/// 2. Advice map, which is a key-value map where keys are words (4 field elements) and values are
88///    vectors of field elements. The processor can push the values from the map onto the advice
89///    stack, as well as insert new values into the map.
90/// 3. Merkle store, which contains structured data reducible to Merkle paths. The VM can request
91///    Merkle paths from the store, as well as mutate it by updating or merging nodes contained in
92///    the store.
93#[derive(Debug, Clone, PartialEq, Eq)]
94pub struct AdviceProvider {
95    stack: AdviceStack,
96    map: AdviceMap,
97    map_element_count: usize,
98    max_map_value_size: usize,
99    max_map_elements: usize,
100    store: MerkleStore,
101    merkle_store_node_count: usize,
102    max_merkle_store_nodes: usize,
103}
104
105impl Default for AdviceProvider {
106    fn default() -> Self {
107        Self::empty(&ExecutionOptions::default())
108    }
109}
110
111impl AdviceProvider {
112    /// Creates a new advice provider from the provided inputs and execution options.
113    ///
114    /// The advice map limits in `options` are enforced while loading the initial advice inputs.
115    pub fn new(inputs: AdviceInputs, options: &ExecutionOptions) -> Result<Self, AdviceError> {
116        let (stack, map, store) = inputs.into_parts();
117        let mut provider = Self::empty(options);
118        provider.extend_advice_stack(stack)?;
119        provider.extend_merkle_store(store.inner_nodes())?;
120        provider.extend_map(&map)?;
121        Ok(provider)
122    }
123
124    fn empty(options: &ExecutionOptions) -> Self {
125        let store = MerkleStore::default();
126        let merkle_store_node_count = store.num_internal_nodes();
127        Self {
128            stack: AdviceStack::new(),
129            map: AdviceMap::default(),
130            map_element_count: 0,
131            max_map_value_size: options.max_adv_map_value_size(),
132            max_map_elements: options.max_adv_map_elements(),
133            store,
134            merkle_store_node_count,
135            max_merkle_store_nodes: options.max_merkle_store_nodes(),
136        }
137    }
138
139    pub(crate) fn set_options(&mut self, options: &ExecutionOptions) -> Result<(), AdviceError> {
140        Self::validate_map_values(&self.map, options.max_adv_map_value_size())?;
141        let map_element_count =
142            self.map.total_element_count().ok_or(AdviceError::AdvMapElementBudgetExceeded {
143                current: self.map_element_count,
144                added: usize::MAX,
145                max: options.max_adv_map_elements(),
146            })?;
147        if map_element_count > options.max_adv_map_elements() {
148            return Err(AdviceError::AdvMapElementBudgetExceeded {
149                current: 0,
150                added: map_element_count,
151                max: options.max_adv_map_elements(),
152            });
153        }
154        if self.merkle_store_node_count > options.max_merkle_store_nodes() {
155            return Err(AdviceError::MerkleStoreNodeBudgetExceeded {
156                current: 0,
157                added: self.merkle_store_node_count,
158                max: options.max_merkle_store_nodes(),
159            });
160        }
161
162        self.map_element_count = map_element_count;
163        self.max_map_value_size = options.max_adv_map_value_size();
164        self.max_map_elements = options.max_adv_map_elements();
165        self.max_merkle_store_nodes = options.max_merkle_store_nodes();
166        Ok(())
167    }
168
169    #[cfg(test)]
170    #[expect(dead_code)]
171    pub(crate) fn merkle_store(&self) -> &MerkleStore {
172        &self.store
173    }
174
175    /// Applies the mutations given in order to the `AdviceProvider`.
176    pub fn apply_mutations(
177        &mut self,
178        mutations: impl IntoIterator<Item = AdviceMutation>,
179    ) -> Result<(), AdviceError> {
180        mutations.into_iter().try_for_each(|mutation| self.apply_mutation(mutation))
181    }
182
183    fn apply_mutation(&mut self, mutation: AdviceMutation) -> Result<(), AdviceError> {
184        match mutation {
185            AdviceMutation::ExtendStack { stack } => {
186                self.extend_advice_stack(stack)?;
187            },
188            AdviceMutation::ExtendMap { other } => {
189                self.extend_map(&other)?;
190            },
191            AdviceMutation::ExtendMerkleStore { infos } => {
192                self.extend_merkle_store(infos)?;
193            },
194        }
195        Ok(())
196    }
197
198    /// Returns a stable fingerprint of the advice state.
199    ///
200    /// The fingerprint is insensitive to advice-map insertion order and Merkle-store insertion
201    /// order, but it still reflects advice-stack order.
202    #[cfg(test)]
203    #[must_use]
204    pub(crate) fn fingerprint(&self) -> [u8; 32] {
205        let stack = self.stack.iter().copied().collect::<Vec<_>>().to_bytes();
206        let map = self.map.to_bytes();
207        let mut store_nodes = self
208            .store
209            .inner_nodes()
210            .map(|info| (info.value, info.left, info.right))
211            .collect::<Vec<_>>();
212        store_nodes.sort_unstable_by(|lhs, rhs| {
213            lhs.0
214                .cmp(&rhs.0)
215                .then_with(|| lhs.1.cmp(&rhs.1))
216                .then_with(|| lhs.2.cmp(&rhs.2))
217        });
218        let store = store_nodes
219            .into_iter()
220            .flat_map(|(value, left, right)| [value, left, right])
221            .collect::<Vec<_>>()
222            .to_bytes();
223        Blake3_256::hash_iter([stack.as_slice(), map.as_slice(), store.as_slice()].into_iter())
224            .into()
225    }
226
227    // ADVICE STACK
228    // --------------------------------------------------------------------------------------------
229
230    /// Pops an element from the advice stack and returns it.
231    ///
232    /// # Errors
233    /// Returns an error if the advice stack is empty.
234    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
235        self.stack.consume_element().ok_or(AdviceError::StackReadFailed)
236    }
237
238    /// Pops a word (4 elements) from the advice stack and returns it.
239    ///
240    /// Note: a word is popped off the stack element-by-element. For example, a `[d, c, b, a, ...]`
241    /// stack (i.e., `d` is at the top of the stack) will yield `[d, c, b, a]`.
242    ///
243    /// # Errors
244    /// Returns an error if the advice stack does not contain a full word.
245    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
246        self.stack.consume_word().ok_or(AdviceError::StackReadFailed)
247    }
248
249    /// Pops a double word (8 elements) from the advice stack and returns them.
250    ///
251    /// Note: words are popped off the stack element-by-element. For example, a
252    /// `[h, g, f, e, d, c, b, a, ...]` stack (i.e., `h` is at the top of the stack) will yield
253    /// two words: `[h, g, f,e ], [d, c, b, a]`.
254    ///
255    /// # Errors
256    /// Returns an error if the advice stack does not contain two words.
257    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
258        self.stack.consume_dword().ok_or(AdviceError::StackReadFailed)
259    }
260
261    /// Checks that pushing `count` elements would not exceed the advice stack size limit.
262    fn check_stack_capacity(&self, count: usize) -> Result<(), AdviceError> {
263        let resulting_size =
264            self.stack.len().checked_add(count).ok_or(AdviceError::StackSizeExceeded {
265                push_count: count,
266                max: MAX_ADVICE_STACK_SIZE,
267            })?;
268        if resulting_size > MAX_ADVICE_STACK_SIZE {
269            return Err(AdviceError::StackSizeExceeded {
270                push_count: count,
271                max: MAX_ADVICE_STACK_SIZE,
272            });
273        }
274        Ok(())
275    }
276
277    /// Pushes a single value onto the advice stack.
278    pub fn push_stack(&mut self, value: Felt) -> Result<(), AdviceError> {
279        self.check_stack_capacity(1)?;
280        self.stack.push_element(value);
281        Ok(())
282    }
283
284    /// Pushes a word (4 elements) onto the stack.
285    pub fn push_stack_word(&mut self, word: &Word) -> Result<(), AdviceError> {
286        self.check_stack_capacity(4)?;
287        self.stack.prepend_word(*word);
288        Ok(())
289    }
290
291    /// Fetches a list of elements under the specified key from the advice map and pushes them onto
292    /// the advice stack.
293    ///
294    /// If `include_len` is set to true, this also pushes the number of elements onto the advice
295    /// stack.
296    ///
297    /// If `pad_to` is not equal to 0, the elements list obtained from the advice map will be padded
298    /// with zeros, increasing its length to the next multiple of `pad_to`.
299    ///
300    /// Note: this operation doesn't consume the map element so it can be called multiple times
301    /// for the same key.
302    ///
303    /// # Example
304    /// Given an advice stack `[a, b, c, ...]`, and a map `x |-> [d, e, f]`:
305    ///
306    /// A call `push_stack(AdviceSource::Map { key: x, include_len: false, pad_to: 0 })` will result
307    /// in advice stack: `[d, e, f, a, b, c, ...]`.
308    ///
309    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 0 })` will result
310    /// in advice stack: `[3, d, e, f, a, b, c, ...]`.
311    ///
312    /// A call `push_stack(AdviceSource::Map { key: x, include_len: true, pad_to: 4 })` will result
313    /// in advice stack: `[3, d, e, f, 0, a, b, c, ...]`.
314    ///
315    /// # Errors
316    /// Returns an error if the key was not found in the key-value map.
317    pub fn push_from_map(
318        &mut self,
319        key: Word,
320        include_len: bool,
321        pad_to: u8,
322    ) -> Result<(), AdviceError> {
323        let values = self.map.get(&key).ok_or(AdviceError::MapKeyNotFound { key })?;
324
325        // Calculate total elements to push including padding and optional length prefix
326        let num_pad_elements = if pad_to != 0 {
327            values.len().next_multiple_of(pad_to as usize) - values.len()
328        } else {
329            0
330        };
331        let total_push = values
332            .len()
333            .checked_add(num_pad_elements)
334            .and_then(|n| n.checked_add(if include_len { 1 } else { 0 }))
335            .ok_or(AdviceError::StackSizeExceeded {
336                push_count: usize::MAX,
337                max: MAX_ADVICE_STACK_SIZE,
338            })?;
339        self.check_stack_capacity(total_push)?;
340
341        let mut stack = AdviceStack::new();
342        if include_len {
343            stack.append_element(Felt::new_unchecked(values.len() as u64));
344        }
345        stack.append_elements(values.iter().copied());
346
347        // if pad_to was provided (not equal 0), push some zeros to the advice stack so that the
348        // final (padded) elements list length will be the next multiple of pad_to
349        for _ in 0..num_pad_elements {
350            stack.append_element(Felt::default());
351        }
352        self.stack.prepend_stack(stack);
353        Ok(())
354    }
355
356    /// Returns the current stack as a vector ordered from top (index 0) to bottom.
357    pub fn stack(&self) -> Vec<Felt> {
358        self.stack.iter().copied().collect()
359    }
360
361    /// Extends the stack with typed advice stack values.
362    pub fn extend_advice_stack(&mut self, stack: AdviceStack) -> Result<(), AdviceError> {
363        self.check_stack_capacity(stack.len())?;
364        self.stack.prepend_stack(stack);
365        Ok(())
366    }
367
368    // ADVICE MAP
369    // --------------------------------------------------------------------------------------------
370
371    /// Returns true if the key has a corresponding value in the map.
372    pub fn contains_map_key(&self, key: &Word) -> bool {
373        self.map.contains_key(key)
374    }
375
376    /// Returns a reference to the value(s) associated with the specified key in the advice map.
377    pub fn get_mapped_values(&self, key: &Word) -> Option<&[Felt]> {
378        self.map.get(key).map(AsRef::as_ref)
379    }
380
381    /// Returns the current advice map.
382    pub fn map(&self) -> &AdviceMap {
383        &self.map
384    }
385
386    fn validate_map_values(map: &AdviceMap, max_value_size: usize) -> Result<(), AdviceError> {
387        for (_, values) in map.iter() {
388            if values.len() > max_value_size {
389                return Err(AdviceError::AdvMapValueSizeExceeded {
390                    size: values.len(),
391                    max: max_value_size,
392                });
393            }
394        }
395        Ok(())
396    }
397
398    fn entry_element_count(value_len: usize) -> Option<usize> {
399        WORD_SIZE.checked_add(value_len)
400    }
401
402    fn check_map_value_size(&self, size: usize) -> Result<(), AdviceError> {
403        if size > self.max_map_value_size {
404            return Err(AdviceError::AdvMapValueSizeExceeded {
405                size,
406                max: self.max_map_value_size,
407            });
408        }
409        Ok(())
410    }
411
412    fn check_map_element_budget(&self, added: usize) -> Result<(), AdviceError> {
413        let Some(new_total) = self.map_element_count.checked_add(added) else {
414            return Err(AdviceError::AdvMapElementBudgetExceeded {
415                current: self.map_element_count,
416                added,
417                max: self.max_map_elements,
418            });
419        };
420
421        if new_total > self.max_map_elements {
422            return Err(AdviceError::AdvMapElementBudgetExceeded {
423                current: self.map_element_count,
424                added,
425                max: self.max_map_elements,
426            });
427        }
428        Ok(())
429    }
430
431    fn check_merkle_store_node_budget(&self, node_count: usize) -> Result<(), AdviceError> {
432        if node_count > self.max_merkle_store_nodes {
433            return Err(AdviceError::MerkleStoreNodeBudgetExceeded {
434                current: self.merkle_store_node_count,
435                added: node_count.saturating_sub(self.merkle_store_node_count),
436                max: self.max_merkle_store_nodes,
437            });
438        }
439        Ok(())
440    }
441
442    fn check_merkle_store_node_addition(&self, added: usize) -> Result<(), AdviceError> {
443        let Some(node_count) = self.merkle_store_node_count.checked_add(added) else {
444            return Err(AdviceError::MerkleStoreNodeBudgetExceeded {
445                current: self.merkle_store_node_count,
446                added,
447                max: self.max_merkle_store_nodes,
448            });
449        };
450
451        self.check_merkle_store_node_budget(node_count)
452    }
453
454    /// Inserts the provided value into the advice map under the specified key.
455    ///
456    /// The values in the advice map can be moved onto the advice stack by invoking
457    /// the [AdviceProvider::push_from_map()] method.
458    ///
459    /// Returns an error if the specified key is already present in the advice map.
460    pub fn insert_into_map(&mut self, key: Word, values: Vec<Felt>) -> Result<(), AdviceError> {
461        match self.map.get(&key) {
462            Some(existing_values) => {
463                let existing_values = existing_values.as_ref();
464                if existing_values != values {
465                    return Err(AdviceError::MapKeyAlreadyPresent {
466                        key,
467                        prev_values: existing_values.to_vec(),
468                        new_values: values,
469                    });
470                }
471            },
472            None => {
473                self.check_map_value_size(values.len())?;
474                let added = Self::entry_element_count(values.len()).ok_or(
475                    AdviceError::AdvMapElementBudgetExceeded {
476                        current: self.map_element_count,
477                        added: usize::MAX,
478                        max: self.max_map_elements,
479                    },
480                )?;
481                self.check_map_element_budget(added)?;
482                self.map.insert(key, values);
483                self.map_element_count += added;
484            },
485        }
486        Ok(())
487    }
488
489    /// Merges all entries from the given [`AdviceMap`] into the current advice map.
490    ///
491    /// Returns an error if any new entry already exists with the same key but a different value
492    /// than the one currently stored. The current map remains unchanged.
493    pub fn extend_map(&mut self, other: &AdviceMap) -> Result<(), AdviceError> {
494        let mut added = 0usize;
495        for (key, values) in other.iter() {
496            if let Some(existing_values) = self.map.get(key) {
497                if existing_values.as_ref() != values.as_ref() {
498                    return Err(AdviceError::MapKeyAlreadyPresent {
499                        key: *key,
500                        prev_values: existing_values.to_vec(),
501                        new_values: values.to_vec(),
502                    });
503                }
504                continue;
505            }
506
507            self.check_map_value_size(values.len())?;
508            let entry_elements = Self::entry_element_count(values.len()).ok_or(
509                AdviceError::AdvMapElementBudgetExceeded {
510                    current: self.map_element_count,
511                    added: usize::MAX,
512                    max: self.max_map_elements,
513                },
514            )?;
515            added = added.checked_add(entry_elements).ok_or(
516                AdviceError::AdvMapElementBudgetExceeded {
517                    current: self.map_element_count,
518                    added: usize::MAX,
519                    max: self.max_map_elements,
520                },
521            )?;
522        }
523        self.check_map_element_budget(added)?;
524
525        self.map.merge(other).map_err(|((key, prev_values), new_values)| {
526            AdviceError::MapKeyAlreadyPresent {
527                key,
528                prev_values: prev_values.to_vec(),
529                new_values: new_values.to_vec(),
530            }
531        })?;
532        self.map_element_count += added;
533        Ok(())
534    }
535
536    // MERKLE STORE
537    // --------------------------------------------------------------------------------------------
538
539    /// Returns a node at the specified depth and index in a Merkle tree with the given root.
540    ///
541    /// # Errors
542    /// Returns an error if:
543    /// - A Merkle tree for the specified root cannot be found in this advice provider.
544    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
545    ///   by the specified root.
546    /// - Value of the node at the specified depth and index is not known to this advice provider.
547    pub fn get_tree_node(&self, root: Word, depth: Felt, index: Felt) -> Result<Word, AdviceError> {
548        let index = NodeIndex::from_elements(&depth, &index)
549            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
550        self.store.get_node(root, index).map_err(AdviceError::MerkleStoreLookupFailed)
551    }
552
553    /// Returns true if a path to a node at the specified depth and index in a Merkle tree with the
554    /// specified root exists in this Merkle store.
555    ///
556    /// # Errors
557    /// Returns an error if accessing the Merkle store fails.
558    pub fn has_merkle_path(
559        &self,
560        root: Word,
561        depth: Felt,
562        index: Felt,
563    ) -> Result<bool, AdviceError> {
564        let index = NodeIndex::from_elements(&depth, &index)
565            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
566
567        Ok(self.store.has_path(root, index))
568    }
569
570    /// Returns a path to a node at the specified depth and index in a Merkle tree with the
571    /// specified root.
572    ///
573    /// # Errors
574    /// Returns an error if:
575    /// - A Merkle tree for the specified root cannot be found in this advice provider.
576    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
577    ///   by the specified root.
578    /// - Path to the node at the specified depth and index is not known to this advice provider.
579    pub fn get_merkle_path(
580        &self,
581        root: Word,
582        depth: Felt,
583        index: Felt,
584    ) -> Result<MerklePath, AdviceError> {
585        let index = NodeIndex::from_elements(&depth, &index)
586            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
587        self.store
588            .get_path(root, index)
589            .map(|value| value.path)
590            .map_err(AdviceError::MerkleStoreLookupFailed)
591    }
592
593    /// Updates a node at the specified depth and index in a Merkle tree with the specified root;
594    /// returns the Merkle path from the updated node to the new root, together with the new root.
595    ///
596    /// # Errors
597    /// Returns an error if:
598    /// - A Merkle tree for the specified root cannot be found in this advice provider.
599    /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
600    ///   by the specified root.
601    /// - Path to the leaf at the specified index in the specified Merkle tree is not known to this
602    ///   advice provider.
603    pub fn update_merkle_node(
604        &mut self,
605        root: Word,
606        depth: Felt,
607        index: Felt,
608        value: Word,
609    ) -> Result<(MerklePath, Word), AdviceError> {
610        let node_index = NodeIndex::from_elements(&depth, &index)
611            .map_err(|_| AdviceError::InvalidMerkleTreeNodeIndex { depth, index })?;
612        let proof = self
613            .store
614            .get_path(root, node_index)
615            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
616        let path = proof.path;
617
618        if proof.value == value {
619            return Ok((path, root));
620        }
621
622        let added = self
623            .store
624            .new_path_node_count(node_index.position(), value, &path)
625            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
626        self.check_merkle_store_node_addition(added)?;
627
628        let new_root = self
629            .store
630            .add_merkle_path(node_index.position(), value, path.clone())
631            .map_err(AdviceError::MerkleStoreUpdateFailed)?;
632        self.merkle_store_node_count += added;
633        Ok((path, new_root))
634    }
635
636    /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
637    /// specified roots. The root of the new tree is defined as `hash(left_root, right_root)`.
638    ///
639    /// After the operation, both the original trees and the new tree remains in the advice
640    /// provider (i.e., the input trees are not removed).
641    ///
642    /// It is not checked whether a Merkle tree for either of the specified roots can be found in
643    /// this advice provider.
644    pub fn merge_roots(&mut self, lhs: Word, rhs: Word) -> Result<Word, AdviceError> {
645        let root = Poseidon2::merge(&[lhs, rhs]);
646        let added = self.store.new_internal_node_count([root]);
647        self.check_merkle_store_node_addition(added)?;
648
649        let root = self.store.merge_roots(lhs, rhs).map_err(AdviceError::MerkleStoreMergeFailed)?;
650        self.merkle_store_node_count += added;
651        Ok(root)
652    }
653
654    /// Returns true if the Merkle root exists for the advice provider Merkle store.
655    pub fn has_merkle_root(&self, root: Word) -> bool {
656        self.store.get_node(root, NodeIndex::root()).is_ok()
657    }
658
659    /// Extends the [MerkleStore] with the given nodes.
660    pub fn extend_merkle_store<I>(&mut self, iter: I) -> Result<(), AdviceError>
661    where
662        I: IntoIterator<Item = InnerNodeInfo>,
663    {
664        let nodes = iter.into_iter().collect::<Vec<_>>();
665        let added = self.store.new_internal_node_count(nodes.iter().map(|node| node.value));
666        self.check_merkle_store_node_addition(added)?;
667
668        self.store.extend(nodes);
669        self.merkle_store_node_count += added;
670        Ok(())
671    }
672
673    // MUTATORS
674    // --------------------------------------------------------------------------------------------
675
676    /// Extends the contents of this instance with the contents of an `AdviceInputs`.
677    pub fn extend_from_inputs(&mut self, inputs: &AdviceInputs) -> Result<(), AdviceError> {
678        self.extend_advice_stack(inputs.advice_stack())?;
679        self.extend_merkle_store(inputs.store.inner_nodes())?;
680        self.extend_map(&inputs.map)
681    }
682
683    /// Consumes `self` and return its parts (stack, map, store).
684    ///
685    /// The returned stack vector is ordered from top (index 0) to bottom.
686    pub fn into_parts(self) -> (Vec<Felt>, AdviceMap, MerkleStore) {
687        (self.stack.into_elements(), self.map, self.store)
688    }
689}
690
691// ADVICE PROVIDER INTERFACE IMPLEMENTATION
692// ================================================================================================
693
694impl AdviceProviderInterface for AdviceProvider {
695    #[inline(always)]
696    fn pop_stack(&mut self) -> Result<Felt, AdviceError> {
697        self.pop_stack()
698    }
699
700    #[inline(always)]
701    fn pop_stack_word(&mut self) -> Result<Word, AdviceError> {
702        self.pop_stack_word()
703    }
704
705    #[inline(always)]
706    fn pop_stack_dword(&mut self) -> Result<[Word; 2], AdviceError> {
707        self.pop_stack_dword()
708    }
709
710    #[inline(always)]
711    fn get_merkle_path(
712        &self,
713        root: Word,
714        depth: Felt,
715        index: Felt,
716    ) -> Result<Option<MerklePath>, AdviceError> {
717        self.get_merkle_path(root, depth, index).map(Some)
718    }
719
720    #[inline(always)]
721    fn update_merkle_node(
722        &mut self,
723        root: Word,
724        depth: Felt,
725        index: Felt,
726        value: Word,
727    ) -> Result<Option<MerklePath>, AdviceError> {
728        self.update_merkle_node(root, depth, index, value).map(|(path, _)| Some(path))
729    }
730}
731
732#[cfg(test)]
733mod tests {
734    use alloc::{collections::BTreeMap, vec, vec::Vec};
735
736    use miden_core::WORD_SIZE;
737
738    use super::AdviceProvider;
739    use crate::{
740        AdviceInputs, ExecutionOptions, Felt, Word,
741        advice::{AdviceError, AdviceMap, AdviceMutation, AdviceStack},
742        crypto::merkle::{MerkleStore, MerkleTree},
743    };
744
745    fn make_leaf(seed: u64) -> Word {
746        [
747            Felt::new_unchecked(seed),
748            Felt::new_unchecked(seed + 1),
749            Felt::new_unchecked(seed + 2),
750            Felt::new_unchecked(seed + 3),
751        ]
752        .into()
753    }
754
755    #[test]
756    fn fingerprint_is_stable_across_merkle_store_insertion_order() {
757        let tree_a =
758            MerkleTree::new([make_leaf(1), make_leaf(5), make_leaf(9), make_leaf(13)]).unwrap();
759        let tree_b =
760            MerkleTree::new([make_leaf(17), make_leaf(21), make_leaf(25), make_leaf(29)]).unwrap();
761
762        let mut store_a = MerkleStore::default();
763        store_a.extend(tree_a.inner_nodes());
764        store_a.extend(tree_b.inner_nodes());
765
766        let mut store_b = MerkleStore::default();
767        store_b.extend(tree_b.inner_nodes());
768        store_b.extend(tree_a.inner_nodes());
769
770        assert_eq!(store_a, store_b);
771
772        let provider_a = AdviceProvider::new(
773            AdviceInputs::default().with_merkle_store(store_a),
774            &Default::default(),
775        )
776        .unwrap();
777        let provider_b = AdviceProvider::new(
778            AdviceInputs::default().with_merkle_store(store_b),
779            &Default::default(),
780        )
781        .unwrap();
782
783        assert_eq!(provider_a, provider_b);
784        assert_eq!(provider_a.fingerprint(), provider_b.fingerprint());
785    }
786
787    #[test]
788    fn typed_advice_stack_mutation_prepends_values() {
789        let mut initial_stack = AdviceStack::new();
790        initial_stack.append_elements([Felt::new_unchecked(3), Felt::new_unchecked(4)]);
791        let mut mutation_stack = AdviceStack::new();
792        mutation_stack.append_elements([Felt::new_unchecked(1), Felt::new_unchecked(2)]);
793        let mut provider = AdviceProvider::new(
794            AdviceInputs::default().with_advice_stack(initial_stack),
795            &Default::default(),
796        )
797        .unwrap();
798
799        provider
800            .apply_mutations([AdviceMutation::extend_advice_stack(mutation_stack)])
801            .unwrap();
802
803        assert_eq!(
804            provider.stack(),
805            vec![
806                Felt::new_unchecked(1),
807                Felt::new_unchecked(2),
808                Felt::new_unchecked(3),
809                Felt::new_unchecked(4)
810            ]
811        );
812    }
813
814    #[test]
815    fn advice_map_insert_respects_element_budget() {
816        let options = ExecutionOptions::default().with_max_adv_map_elements(WORD_SIZE + 1);
817        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
818
819        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
820
821        let err = provider.insert_into_map(make_leaf(1), vec![Felt::ONE]).unwrap_err();
822        assert!(matches!(
823            err,
824            AdviceError::AdvMapElementBudgetExceeded { current: 5, added: 5, max: 5 }
825        ));
826
827        assert_eq!(provider.map.len(), 1);
828        assert!(provider.contains_map_key(&make_leaf(0)));
829        assert!(!provider.contains_map_key(&make_leaf(1)));
830    }
831
832    #[test]
833    fn advice_map_insert_respects_value_limit() {
834        let options = ExecutionOptions::default().with_max_adv_map_value_size(1);
835        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
836        let values = vec![Felt::ONE, Felt::new_unchecked(2)];
837
838        let err = provider.insert_into_map(make_leaf(0), values).unwrap_err();
839        assert!(matches!(err, AdviceError::AdvMapValueSizeExceeded { size: 2, max: 1 }));
840
841        assert_eq!(provider.map.len(), 0);
842    }
843
844    #[test]
845    fn advice_map_extend_respects_element_budget_atomically() {
846        let options = ExecutionOptions::default().with_max_adv_map_elements(2 * (WORD_SIZE + 1));
847        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
848        provider.insert_into_map(make_leaf(0), vec![Felt::ONE]).unwrap();
849        let other = advice_map_from_entries(1..3, 1);
850
851        let err = provider.extend_map(&other).unwrap_err();
852        assert!(matches!(
853            err,
854            AdviceError::AdvMapElementBudgetExceeded { current: 5, added: 10, max: 10 }
855        ));
856
857        assert_eq!(provider.map.len(), 1);
858        assert!(provider.contains_map_key(&make_leaf(0)));
859        assert!(!provider.contains_map_key(&make_leaf(1)));
860        assert!(!provider.contains_map_key(&make_leaf(2)));
861    }
862
863    #[test]
864    fn advice_map_extend_respects_value_limit_atomically() {
865        let options = ExecutionOptions::default().with_max_adv_map_value_size(1);
866        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
867        let other = advice_map_from_entries(0..2, 2);
868
869        let err = provider.extend_map(&other).unwrap_err();
870        assert!(matches!(err, AdviceError::AdvMapValueSizeExceeded { size: 2, max: 1 }));
871
872        assert_eq!(provider.map.len(), 0);
873    }
874
875    #[test]
876    fn initial_advice_map_respects_element_budget() {
877        let options = ExecutionOptions::default().with_max_adv_map_elements(WORD_SIZE);
878        let inputs = AdviceInputs::default().with_map([(make_leaf(0), vec![Felt::ONE])]);
879
880        let err = AdviceProvider::new(inputs, &options).unwrap_err();
881        assert!(matches!(
882            err,
883            AdviceError::AdvMapElementBudgetExceeded { current: 0, added: 5, max: 4 }
884        ));
885    }
886
887    #[test]
888    fn initial_merkle_store_respects_node_budget() {
889        let tree = merkle_tree_from_leaves(0..4);
890        let store = merkle_store_from_tree(&tree);
891        let options =
892            ExecutionOptions::default().with_max_merkle_store_nodes(store.num_internal_nodes() - 1);
893        let inputs = AdviceInputs::default().with_merkle_store(store);
894
895        let err = AdviceProvider::new(inputs, &options).unwrap_err();
896        assert!(matches!(
897            err,
898            AdviceError::MerkleStoreNodeBudgetExceeded {
899                current: _,
900                added: _,
901                max
902            } if max == options.max_merkle_store_nodes()
903        ));
904    }
905
906    #[test]
907    fn merkle_store_extend_respects_node_budget_atomically() {
908        let base_node_count = MerkleStore::default().num_internal_nodes();
909        let options = ExecutionOptions::default().with_max_merkle_store_nodes(base_node_count + 1);
910        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
911        let tree = merkle_tree_from_leaves(0..4);
912
913        let err = provider.extend_merkle_store(tree.inner_nodes()).unwrap_err();
914        assert!(matches!(
915            err,
916            AdviceError::MerkleStoreNodeBudgetExceeded {
917                current,
918                added: _,
919                max
920            } if current == base_node_count && max == base_node_count + 1
921        ));
922
923        assert_eq!(provider.merkle_store_node_count, base_node_count);
924        assert!(!provider.has_merkle_root(tree.root()));
925    }
926
927    #[test]
928    fn merkle_store_extend_allows_exact_node_budget() {
929        let base_node_count = MerkleStore::default().num_internal_nodes();
930        let tree = merkle_tree_from_leaves(0..2);
931        let options = ExecutionOptions::default().with_max_merkle_store_nodes(base_node_count + 1);
932        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
933
934        provider.extend_merkle_store(tree.inner_nodes()).unwrap();
935
936        assert_eq!(provider.merkle_store_node_count, base_node_count + 1);
937        assert!(provider.has_merkle_root(tree.root()));
938    }
939
940    #[test]
941    fn merkle_store_extend_counts_only_new_unique_nodes() {
942        let base_node_count = MerkleStore::default().num_internal_nodes();
943        let tree = merkle_tree_from_leaves(0..2);
944        let options = ExecutionOptions::default().with_max_merkle_store_nodes(base_node_count + 1);
945        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
946        let nodes = tree.inner_nodes().collect::<Vec<_>>();
947
948        provider
949            .extend_merkle_store(nodes.iter().cloned().chain(nodes.iter().cloned()))
950            .unwrap();
951        provider.extend_merkle_store(nodes).unwrap();
952
953        assert_eq!(provider.merkle_store_node_count, base_node_count + 1);
954        assert!(provider.has_merkle_root(tree.root()));
955    }
956
957    #[test]
958    fn merkle_store_merge_respects_node_budget_atomically() {
959        let base_node_count = MerkleStore::default().num_internal_nodes();
960        let options = ExecutionOptions::default().with_max_merkle_store_nodes(base_node_count);
961        let mut provider = AdviceProvider::new(AdviceInputs::default(), &options).unwrap();
962
963        let err = provider.merge_roots(make_leaf(0), make_leaf(4)).unwrap_err();
964        assert!(matches!(
965            err,
966            AdviceError::MerkleStoreNodeBudgetExceeded {
967                current,
968                added: 1,
969                max
970            } if current == base_node_count && max == base_node_count
971        ));
972
973        assert_eq!(provider.merkle_store_node_count, base_node_count);
974    }
975
976    #[test]
977    fn merkle_store_update_respects_node_budget_atomically() {
978        let tree = merkle_tree_from_leaves(0..4);
979        let store = merkle_store_from_tree(&tree);
980        let node_count = store.num_internal_nodes();
981        let options = ExecutionOptions::default().with_max_merkle_store_nodes(node_count);
982        let inputs = AdviceInputs::default().with_merkle_store(store);
983        let mut provider = AdviceProvider::new(inputs, &options).unwrap();
984
985        let err = provider
986            .update_merkle_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO, make_leaf(100))
987            .unwrap_err();
988        assert!(matches!(
989            err,
990            AdviceError::MerkleStoreNodeBudgetExceeded {
991                current,
992                added: _,
993                max
994            } if current == node_count && max == node_count
995        ));
996
997        assert_eq!(provider.merkle_store_node_count, node_count);
998        assert_eq!(
999            provider.get_tree_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO).unwrap(),
1000            make_leaf(0)
1001        );
1002    }
1003
1004    #[test]
1005    fn merkle_store_update_allows_exact_node_budget() {
1006        let tree = merkle_tree_from_leaves(0..4);
1007        let store = merkle_store_from_tree(&tree);
1008        let mut staged = store.clone();
1009        staged
1010            .set_node(
1011                tree.root(),
1012                miden_core::crypto::merkle::NodeIndex::new(2, 0).unwrap(),
1013                make_leaf(100),
1014            )
1015            .unwrap();
1016        let options =
1017            ExecutionOptions::default().with_max_merkle_store_nodes(staged.num_internal_nodes());
1018        let inputs = AdviceInputs::default().with_merkle_store(store);
1019        let mut provider = AdviceProvider::new(inputs, &options).unwrap();
1020
1021        provider
1022            .update_merkle_node(tree.root(), Felt::new_unchecked(2), Felt::ZERO, make_leaf(100))
1023            .unwrap();
1024
1025        assert_eq!(provider.merkle_store_node_count, staged.num_internal_nodes());
1026    }
1027
1028    fn advice_map_from_entries(keys: impl Iterator<Item = u64>, value_len: usize) -> AdviceMap {
1029        keys.map(|key| {
1030            let values = (0..value_len)
1031                .map(|offset| Felt::new_unchecked(key + offset as u64))
1032                .collect::<Vec<_>>();
1033            (make_leaf(key), values)
1034        })
1035        .collect::<BTreeMap<_, _>>()
1036        .into()
1037    }
1038
1039    fn merkle_tree_from_leaves(keys: impl Iterator<Item = u64>) -> MerkleTree {
1040        MerkleTree::new(keys.map(make_leaf).collect::<Vec<_>>()).unwrap()
1041    }
1042
1043    fn merkle_store_from_tree(tree: &MerkleTree) -> MerkleStore {
1044        let mut store = MerkleStore::default();
1045        store.extend(tree.inner_nodes());
1046        store
1047    }
1048}
miden_processor/host/advice/mod.rs

miden_processor/host/advice/
mod.rs
