miden_processor/host/advice/
mod.rs

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

miden_processor/host/advice/
mod.rs
