miden_processor/host/advice/
mod.rs

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

miden_processor/host/advice/
mod.rs
