miden_processor/host/advice/
providers.rs

1use alloc::{collections::BTreeMap, vec::Vec};
2
3use vm_core::{
4    crypto::merkle::{MerkleStore, NodeIndex, StoreNode},
5    mast::MastNodeExt,
6};
7
8use super::{
9    AdviceInputs, AdviceProvider, AdviceSource, ExecutionError, Felt, MerklePath, RpoDigest, Word,
10};
11use crate::{
12    ErrorContext, ProcessState,
13    utils::collections::{KvMap, RecordingMap},
14};
15
16// TYPE ALIASES
17// ================================================================================================
18
19type SimpleMerkleMap = BTreeMap<RpoDigest, StoreNode>;
20type RecordingMerkleMap = RecordingMap<RpoDigest, StoreNode>;
21
22type SimpleAdviceMap = BTreeMap<RpoDigest, Vec<Felt>>;
23type RecordingAdviceMap = RecordingMap<RpoDigest, Vec<Felt>>;
24
25// BASE ADVICE PROVIDER
26// ================================================================================================
27
28/// An in-memory [AdviceProvider] implementation which serves as the base for advice providers
29/// bundles with Miden VM.
30#[derive(Debug, Clone, Default)]
31pub struct BaseAdviceProvider<M, S>
32where
33    M: KvMap<RpoDigest, Vec<Felt>>,
34    S: KvMap<RpoDigest, StoreNode>,
35{
36    stack: Vec<Felt>,
37    map: M,
38    store: MerkleStore<S>,
39}
40
41impl<M, S> From<AdviceInputs> for BaseAdviceProvider<M, S>
42where
43    M: KvMap<RpoDigest, Vec<Felt>>,
44    S: KvMap<RpoDigest, StoreNode>,
45{
46    fn from(inputs: AdviceInputs) -> Self {
47        let (mut stack, map, store) = inputs.into_parts();
48        stack.reverse();
49        Self {
50            stack,
51            map: map.into_iter().collect(),
52            store: store.inner_nodes().collect(),
53        }
54    }
55}
56
57impl<M, S> AdviceProvider for BaseAdviceProvider<M, S>
58where
59    M: KvMap<RpoDigest, Vec<Felt>>,
60    S: KvMap<RpoDigest, StoreNode>,
61{
62    // ADVICE STACK
63    // --------------------------------------------------------------------------------------------
64
65    fn pop_stack(
66        &mut self,
67        process: ProcessState,
68        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
69    ) -> Result<Felt, ExecutionError> {
70        self.stack
71            .pop()
72            .ok_or(ExecutionError::advice_stack_read_failed(process.clk(), err_ctx))
73    }
74
75    fn pop_stack_word(
76        &mut self,
77        process: ProcessState,
78        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
79    ) -> Result<Word, ExecutionError> {
80        if self.stack.len() < 4 {
81            return Err(ExecutionError::advice_stack_read_failed(process.clk(), err_ctx));
82        }
83
84        let idx = self.stack.len() - 4;
85        let result =
86            [self.stack[idx + 3], self.stack[idx + 2], self.stack[idx + 1], self.stack[idx]];
87
88        self.stack.truncate(idx);
89
90        Ok(result)
91    }
92
93    fn pop_stack_dword(
94        &mut self,
95        process: ProcessState,
96        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
97    ) -> Result<[Word; 2], ExecutionError> {
98        let word0 = self.pop_stack_word(process, err_ctx)?;
99        let word1 = self.pop_stack_word(process, err_ctx)?;
100
101        Ok([word0, word1])
102    }
103
104    fn push_stack(
105        &mut self,
106        source: AdviceSource,
107        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
108    ) -> Result<(), ExecutionError> {
109        match source {
110            AdviceSource::Value(value) => {
111                self.stack.push(value);
112            },
113            AdviceSource::Word(word) => {
114                self.stack.extend(word.iter().rev());
115            },
116            AdviceSource::Map { key, include_len } => {
117                let values = self
118                    .map
119                    .get(&key.into())
120                    .ok_or(ExecutionError::advice_map_key_not_found(key, err_ctx))?;
121
122                self.stack.extend(values.iter().rev());
123                if include_len {
124                    self.stack
125                        .push(Felt::try_from(values.len() as u64).expect("value length too big"));
126                }
127            },
128        }
129
130        Ok(())
131    }
132
133    fn peek_stack(&self, length: usize) -> &[Felt] {
134        if length == 0 {
135            &self.stack
136        } else {
137            &self.stack[0..length]
138        }
139    }
140
141    // ADVICE MAP
142    // --------------------------------------------------------------------------------------------
143
144    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
145        self.map.get(key).map(|v| v.as_slice())
146    }
147
148    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>) {
149        self.map.insert(key.into(), values);
150    }
151
152    // MERKLE STORE
153    // --------------------------------------------------------------------------------------------
154
155    fn get_tree_node(
156        &self,
157        root: Word,
158        depth: &Felt,
159        index: &Felt,
160        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
161    ) -> Result<Word, ExecutionError> {
162        let index = NodeIndex::from_elements(depth, index)
163            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
164        self.store
165            .get_node(root.into(), index)
166            .map(|v| v.into())
167            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
168    }
169
170    fn get_merkle_path(
171        &self,
172        root: Word,
173        depth: &Felt,
174        index: &Felt,
175        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
176    ) -> Result<MerklePath, ExecutionError> {
177        let index = NodeIndex::from_elements(depth, index)
178            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
179        self.store
180            .get_path(root.into(), index)
181            .map(|value| value.path)
182            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
183    }
184
185    fn get_leaf_depth(
186        &self,
187        root: Word,
188        tree_depth: &Felt,
189        index: &Felt,
190        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
191    ) -> Result<u8, ExecutionError> {
192        let tree_depth = u8::try_from(tree_depth.as_int())
193            .map_err(|_| ExecutionError::invalid_merkle_tree_depth(*tree_depth, err_ctx))?;
194        self.store
195            .get_leaf_depth(root.into(), tree_depth, index.as_int())
196            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
197    }
198
199    fn update_merkle_node(
200        &mut self,
201        root: Word,
202        depth: &Felt,
203        index: &Felt,
204        value: Word,
205        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
206    ) -> Result<(MerklePath, Word), ExecutionError> {
207        let node_index = NodeIndex::from_elements(depth, index)
208            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
209        self.store
210            .set_node(root.into(), node_index, value.into())
211            .map(|root| (root.path, root.root.into()))
212            .map_err(|err| ExecutionError::merkle_store_update_failed(err, err_ctx))
213    }
214
215    fn merge_roots(
216        &mut self,
217        lhs: Word,
218        rhs: Word,
219        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
220    ) -> Result<Word, ExecutionError> {
221        self.store
222            .merge_roots(lhs.into(), rhs.into())
223            .map(|v| v.into())
224            .map_err(|err| ExecutionError::merkle_store_merge_failed(err, err_ctx))
225    }
226}
227
228// MEMORY ADVICE PROVIDER
229// ================================================================================================
230
231/// An in-memory `[AdviceProvider]` implementation which uses [BTreeMap]s as its backing storage.
232#[derive(Debug, Clone, Default)]
233pub struct MemAdviceProvider {
234    provider: BaseAdviceProvider<SimpleAdviceMap, SimpleMerkleMap>,
235}
236
237impl From<AdviceInputs> for MemAdviceProvider {
238    fn from(inputs: AdviceInputs) -> Self {
239        let provider = inputs.into();
240        Self { provider }
241    }
242}
243
244/// Accessors to internal data structures of the provider used for testing purposes.
245#[cfg(any(test, feature = "testing"))]
246impl MemAdviceProvider {
247    /// Returns the current state of the advice stack.
248    pub fn stack(&self) -> &[Felt] {
249        &self.provider.stack
250    }
251
252    /// Returns the current state of the advice map.
253    pub fn map(&self) -> &SimpleAdviceMap {
254        &self.provider.map
255    }
256
257    // Returns the current state of the Merkle store.
258    pub fn store(&self) -> &MerkleStore<SimpleMerkleMap> {
259        &self.provider.store
260    }
261
262    /// Returns true if the Merkle root exists for the advice provider Merkle store.
263    pub fn has_merkle_root(&self, root: crate::crypto::RpoDigest) -> bool {
264        self.provider.store.get_node(root, NodeIndex::root()).is_ok()
265    }
266}
267
268/// Pass-through implementations of [AdviceProvider] methods.
269///
270/// TODO: potentially do this via a macro.
271#[rustfmt::skip]
272impl AdviceProvider for MemAdviceProvider {
273    fn pop_stack(&mut self, process: ProcessState,
274        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
275    )-> Result<Felt, ExecutionError> {
276        self.provider.pop_stack(process, err_ctx)
277    }
278
279    fn pop_stack_word(&mut self, process: ProcessState,
280        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
281    ) -> Result<Word, ExecutionError> {
282        self.provider.pop_stack_word(process, err_ctx)
283    }
284
285    fn pop_stack_dword(&mut self, process: ProcessState,
286        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
287    ) -> Result<[Word; 2], ExecutionError> {
288        self.provider.pop_stack_dword(process, err_ctx)
289    }
290
291    fn push_stack(&mut self, source: AdviceSource, err_ctx: &ErrorContext<impl MastNodeExt>) -> Result<(), ExecutionError> {
292        self.provider.push_stack(source, err_ctx)
293    }
294
295    fn peek_stack(&self, length: usize,
296    )-> &[Felt] {
297        self.provider.peek_stack(length)
298    }
299
300    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>)  {
301        self.provider.insert_into_map(key, values)
302    }
303
304    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
305        self.provider.get_mapped_values(key)
306    }
307
308    fn get_tree_node(&self, root: Word, depth: &Felt, index: &Felt,
309        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
310    ) -> Result<Word, ExecutionError> {
311        self.provider.get_tree_node(root, depth, index, err_ctx)
312    }
313
314    fn get_merkle_path(&self, root: Word, depth: &Felt, index: &Felt, 
315        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
316    ) -> Result<MerklePath, ExecutionError> {
317        self.provider.get_merkle_path(root, depth, index, err_ctx)
318    }
319
320    fn get_leaf_depth(&self, root: Word, tree_depth: &Felt, index: &Felt,
321        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
322    ) -> Result<u8, ExecutionError> {
323        self.provider.get_leaf_depth(root, tree_depth, index, err_ctx)
324    }
325
326    fn update_merkle_node(&mut self, root: Word, depth: &Felt, index: &Felt, value: Word,
327        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
328    ) -> Result<(MerklePath, Word), ExecutionError> {
329        self.provider.update_merkle_node(root, depth, index, value, err_ctx)
330    }
331
332    fn merge_roots(&mut self, lhs: Word, rhs: Word,
333        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
334    ) -> Result<Word, ExecutionError> {
335        self.provider.merge_roots(lhs, rhs, err_ctx)
336    }
337}
338
339impl MemAdviceProvider {
340    // FINALIZATION
341    // --------------------------------------------------------------------------------------------
342    /// Consumes the [MemAdviceProvider] and returns a `(Vec<Felt>, SimpleAdviceMap, MerkleStore)`,
343    /// containing the stack, map, store respectively, of the advice provider.
344    pub fn into_parts(self) -> (Vec<Felt>, SimpleAdviceMap, MerkleStore) {
345        let BaseAdviceProvider { stack, map, store } = self.provider;
346        (stack, map, store)
347    }
348}
349
350// RECORDING ADVICE PROVIDER
351// ================================================================================================
352
353/// An in-memory `[AdviceProvider]` implementation with support for data access recording.
354///
355/// The recorder can be converted into a proof which can be used to provide the non-deterministic
356/// inputs for program execution.
357#[derive(Debug, Clone, Default)]
358pub struct RecAdviceProvider {
359    provider: BaseAdviceProvider<RecordingAdviceMap, RecordingMerkleMap>,
360    init_stack: Vec<Felt>,
361}
362
363impl From<AdviceInputs> for RecAdviceProvider {
364    fn from(inputs: AdviceInputs) -> Self {
365        let init_stack = inputs.stack().to_vec();
366        let provider = inputs.into();
367        Self { provider, init_stack }
368    }
369}
370
371/// Accessors to internal data structures of the provider used for testing purposes.
372#[cfg(any(test, feature = "testing"))]
373impl RecAdviceProvider {
374    /// Returns the current state of the advice stack.
375    pub fn stack(&self) -> &[Felt] {
376        &self.provider.stack
377    }
378
379    /// Returns the current state of the advice map.
380    pub fn map(&self) -> &RecordingAdviceMap {
381        &self.provider.map
382    }
383
384    // Returns the current state of the Merkle store.
385    pub fn store(&self) -> &MerkleStore<RecordingMerkleMap> {
386        &self.provider.store
387    }
388
389    /// Returns true if the Merkle root exists for the advice provider Merkle store.
390    pub fn has_merkle_root(&self, root: crate::crypto::RpoDigest) -> bool {
391        self.provider.store.get_node(root, NodeIndex::root()).is_ok()
392    }
393}
394
395/// Pass-through implementations of [AdviceProvider] methods.
396///
397/// TODO: potentially do this via a macro.
398#[rustfmt::skip]
399impl AdviceProvider for RecAdviceProvider {
400    fn pop_stack(&mut self, process: ProcessState,
401        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
402    ) -> Result<Felt, ExecutionError> {
403        self.provider.pop_stack(process,err_ctx)
404    }
405
406    fn pop_stack_word(&mut self, process: ProcessState, 
407        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
408    ) -> Result<Word, ExecutionError> {
409        self.provider.pop_stack_word(process,err_ctx)
410    }
411
412    fn pop_stack_dword(&mut self, process: ProcessState,
413        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
414    ) -> Result<[Word; 2], ExecutionError> {
415        self.provider.pop_stack_dword(process, err_ctx)
416    }
417
418    fn push_stack(&mut self, source: AdviceSource, err_ctx: &ErrorContext<impl MastNodeExt>) -> Result<(), ExecutionError> {
419        self.provider.push_stack(source, err_ctx)
420    }
421
422    fn peek_stack(&self, length: usize) -> &[Felt] {
423        self.provider.peek_stack(length)
424    }
425
426    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>)  {
427        self.provider.insert_into_map(key, values)
428    }
429
430    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
431        self.provider.get_mapped_values(key)
432    }
433
434    fn get_tree_node(&self, root: Word, depth: &Felt, index: &Felt,
435        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
436    ) -> Result<Word, ExecutionError> {
437        self.provider.get_tree_node(root, depth, index, err_ctx)
438    }
439
440    fn get_merkle_path(&self, root: Word, depth: &Felt, index: &Felt, 
441        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
442    ) -> Result<MerklePath, ExecutionError> {
443        self.provider.get_merkle_path(root, depth, index, err_ctx)
444    }
445
446    fn get_leaf_depth(&self, root: Word, tree_depth: &Felt, index: &Felt, 
447        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
448    ) -> Result<u8, ExecutionError> {
449        self.provider.get_leaf_depth(root, tree_depth, index, err_ctx)
450    }
451
452    fn update_merkle_node(&mut self, root: Word, depth: &Felt, index: &Felt, value: Word,
453        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
454    ) -> Result<(MerklePath, Word), ExecutionError> {
455        self.provider.update_merkle_node(root, depth, index, value, err_ctx)
456    }
457
458    fn merge_roots(&mut self, lhs: Word, rhs: Word,
459        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
460    ) -> Result<Word, ExecutionError> {
461        self.provider.merge_roots(lhs, rhs, err_ctx)
462    }
463}
464
465impl RecAdviceProvider {
466    // FINALIZATION
467    // --------------------------------------------------------------------------------------------
468
469    /// Consumes the advice provider and returns an `(AdviceInputs, Vec<Felt>, SimpleAdviceMap,
470    /// MerkleStore)` tuple.
471    ///
472    /// The [AdviceInputs] can be used to re-execute the program. The returned [AdviceInputs]
473    /// instance will contain only the non-deterministic inputs which were requested during program
474    /// execution.
475    ///
476    /// The `Vec<Felt>`, `SimpleAdviceMap`, and `MerkleStore` represent the stack, map, and Merkle
477    /// store of the advice provider at the time of finalization.
478    pub fn finalize(self) -> (AdviceInputs, Vec<Felt>, SimpleAdviceMap, MerkleStore) {
479        let Self { provider, init_stack } = self;
480        let BaseAdviceProvider { stack, map, store } = provider;
481
482        let (map, map_proof) = map.finalize();
483        let (store, store_proof) = store.into_inner().finalize();
484
485        let proof = AdviceInputs::default()
486            .with_stack(init_stack)
487            .with_map(map_proof)
488            .with_merkle_store(store_proof.into());
489
490        (proof, stack, map, store.into())
491    }
492}
miden_processor/host/advice/providers.rs

miden_processor/host/advice/
providers.rs
