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    // ADVICE MAP
134    // --------------------------------------------------------------------------------------------
135
136    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
137        self.map.get(key).map(|v| v.as_slice())
138    }
139
140    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>) {
141        self.map.insert(key.into(), values);
142    }
143
144    // MERKLE STORE
145    // --------------------------------------------------------------------------------------------
146
147    fn get_tree_node(
148        &self,
149        root: Word,
150        depth: &Felt,
151        index: &Felt,
152        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
153    ) -> Result<Word, ExecutionError> {
154        let index = NodeIndex::from_elements(depth, index)
155            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
156        self.store
157            .get_node(root.into(), index)
158            .map(|v| v.into())
159            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
160    }
161
162    fn get_merkle_path(
163        &self,
164        root: Word,
165        depth: &Felt,
166        index: &Felt,
167        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
168    ) -> Result<MerklePath, ExecutionError> {
169        let index = NodeIndex::from_elements(depth, index)
170            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
171        self.store
172            .get_path(root.into(), index)
173            .map(|value| value.path)
174            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
175    }
176
177    fn get_leaf_depth(
178        &self,
179        root: Word,
180        tree_depth: &Felt,
181        index: &Felt,
182        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
183    ) -> Result<u8, ExecutionError> {
184        let tree_depth = u8::try_from(tree_depth.as_int())
185            .map_err(|_| ExecutionError::invalid_merkle_tree_depth(*tree_depth, err_ctx))?;
186        self.store
187            .get_leaf_depth(root.into(), tree_depth, index.as_int())
188            .map_err(|err| ExecutionError::merkle_store_lookup_failed(err, err_ctx))
189    }
190
191    fn update_merkle_node(
192        &mut self,
193        root: Word,
194        depth: &Felt,
195        index: &Felt,
196        value: Word,
197        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
198    ) -> Result<(MerklePath, Word), ExecutionError> {
199        let node_index = NodeIndex::from_elements(depth, index)
200            .map_err(|_| ExecutionError::invalid_merkle_tree_node_index(*depth, *index, err_ctx))?;
201        self.store
202            .set_node(root.into(), node_index, value.into())
203            .map(|root| (root.path, root.root.into()))
204            .map_err(|err| ExecutionError::merkle_store_update_failed(err, err_ctx))
205    }
206
207    fn merge_roots(
208        &mut self,
209        lhs: Word,
210        rhs: Word,
211        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
212    ) -> Result<Word, ExecutionError> {
213        self.store
214            .merge_roots(lhs.into(), rhs.into())
215            .map(|v| v.into())
216            .map_err(|err| ExecutionError::merkle_store_merge_failed(err, err_ctx))
217    }
218}
219
220// MEMORY ADVICE PROVIDER
221// ================================================================================================
222
223/// An in-memory `[AdviceProvider]` implementation which uses [BTreeMap]s as its backing storage.
224#[derive(Debug, Clone, Default)]
225pub struct MemAdviceProvider {
226    provider: BaseAdviceProvider<SimpleAdviceMap, SimpleMerkleMap>,
227}
228
229impl From<AdviceInputs> for MemAdviceProvider {
230    fn from(inputs: AdviceInputs) -> Self {
231        let provider = inputs.into();
232        Self { provider }
233    }
234}
235
236/// Accessors to internal data structures of the provider used for testing purposes.
237#[cfg(any(test, feature = "testing"))]
238impl MemAdviceProvider {
239    /// Returns the current state of the advice stack.
240    pub fn stack(&self) -> &[Felt] {
241        &self.provider.stack
242    }
243
244    /// Returns the current state of the advice map.
245    pub fn map(&self) -> &SimpleAdviceMap {
246        &self.provider.map
247    }
248
249    // Returns the current state of the Merkle store.
250    pub fn store(&self) -> &MerkleStore<SimpleMerkleMap> {
251        &self.provider.store
252    }
253
254    /// Returns true if the Merkle root exists for the advice provider Merkle store.
255    pub fn has_merkle_root(&self, root: crate::crypto::RpoDigest) -> bool {
256        self.provider.store.get_node(root, NodeIndex::root()).is_ok()
257    }
258}
259
260/// Pass-through implementations of [AdviceProvider] methods.
261///
262/// TODO: potentially do this via a macro.
263#[rustfmt::skip]
264impl AdviceProvider for MemAdviceProvider {
265    fn pop_stack(&mut self, process: ProcessState,
266        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
267    )-> Result<Felt, ExecutionError> {
268        self.provider.pop_stack(process, err_ctx)
269    }
270
271    fn pop_stack_word(&mut self, process: ProcessState,
272        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
273    ) -> Result<Word, ExecutionError> {
274        self.provider.pop_stack_word(process, err_ctx)
275    }
276
277    fn pop_stack_dword(&mut self, process: ProcessState,
278        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
279    ) -> Result<[Word; 2], ExecutionError> {
280        self.provider.pop_stack_dword(process, err_ctx)
281    }
282
283    fn push_stack(&mut self, source: AdviceSource, err_ctx: &ErrorContext<impl MastNodeExt>) -> Result<(), ExecutionError> {
284        self.provider.push_stack(source, err_ctx)
285    }
286
287    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>)  {
288        self.provider.insert_into_map(key, values)
289    }
290
291    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
292        self.provider.get_mapped_values(key)
293    }
294
295    fn get_tree_node(&self, root: Word, depth: &Felt, index: &Felt,
296        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
297    ) -> Result<Word, ExecutionError> {
298        self.provider.get_tree_node(root, depth, index, err_ctx)
299    }
300
301    fn get_merkle_path(&self, root: Word, depth: &Felt, index: &Felt, 
302        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
303    ) -> Result<MerklePath, ExecutionError> {
304        self.provider.get_merkle_path(root, depth, index, err_ctx)
305    }
306
307    fn get_leaf_depth(&self, root: Word, tree_depth: &Felt, index: &Felt,
308        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
309    ) -> Result<u8, ExecutionError> {
310        self.provider.get_leaf_depth(root, tree_depth, index, err_ctx)
311    }
312
313    fn update_merkle_node(&mut self, root: Word, depth: &Felt, index: &Felt, value: Word,
314        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
315    ) -> Result<(MerklePath, Word), ExecutionError> {
316        self.provider.update_merkle_node(root, depth, index, value, err_ctx)
317    }
318
319    fn merge_roots(&mut self, lhs: Word, rhs: Word,
320        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
321    ) -> Result<Word, ExecutionError> {
322        self.provider.merge_roots(lhs, rhs, err_ctx)
323    }
324}
325
326impl MemAdviceProvider {
327    // FINALIZATION
328    // --------------------------------------------------------------------------------------------
329    /// Consumes the [MemAdviceProvider] and returns a `(Vec<Felt>, SimpleAdviceMap, MerkleStore)`,
330    /// containing the stack, map, store respectively, of the advice provider.
331    pub fn into_parts(self) -> (Vec<Felt>, SimpleAdviceMap, MerkleStore) {
332        let BaseAdviceProvider { stack, map, store } = self.provider;
333        (stack, map, store)
334    }
335}
336
337// RECORDING ADVICE PROVIDER
338// ================================================================================================
339
340/// An in-memory `[AdviceProvider]` implementation with support for data access recording.
341///
342/// The recorder can be converted into a proof which can be used to provide the non-deterministic
343/// inputs for program execution.
344#[derive(Debug, Clone, Default)]
345pub struct RecAdviceProvider {
346    provider: BaseAdviceProvider<RecordingAdviceMap, RecordingMerkleMap>,
347    init_stack: Vec<Felt>,
348}
349
350impl From<AdviceInputs> for RecAdviceProvider {
351    fn from(inputs: AdviceInputs) -> Self {
352        let init_stack = inputs.stack().to_vec();
353        let provider = inputs.into();
354        Self { provider, init_stack }
355    }
356}
357
358/// Accessors to internal data structures of the provider used for testing purposes.
359#[cfg(any(test, feature = "testing"))]
360impl RecAdviceProvider {
361    /// Returns the current state of the advice stack.
362    pub fn stack(&self) -> &[Felt] {
363        &self.provider.stack
364    }
365
366    /// Returns the current state of the advice map.
367    pub fn map(&self) -> &RecordingAdviceMap {
368        &self.provider.map
369    }
370
371    // Returns the current state of the Merkle store.
372    pub fn store(&self) -> &MerkleStore<RecordingMerkleMap> {
373        &self.provider.store
374    }
375
376    /// Returns true if the Merkle root exists for the advice provider Merkle store.
377    pub fn has_merkle_root(&self, root: crate::crypto::RpoDigest) -> bool {
378        self.provider.store.get_node(root, NodeIndex::root()).is_ok()
379    }
380}
381
382/// Pass-through implementations of [AdviceProvider] methods.
383///
384/// TODO: potentially do this via a macro.
385#[rustfmt::skip]
386impl AdviceProvider for RecAdviceProvider {
387    fn pop_stack(&mut self, process: ProcessState,
388        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
389    ) -> Result<Felt, ExecutionError> {
390        self.provider.pop_stack(process,err_ctx)
391    }
392
393    fn pop_stack_word(&mut self, process: ProcessState, 
394        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
395    ) -> Result<Word, ExecutionError> {
396        self.provider.pop_stack_word(process,err_ctx)
397    }
398
399    fn pop_stack_dword(&mut self, process: ProcessState,
400        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
401    ) -> Result<[Word; 2], ExecutionError> {
402        self.provider.pop_stack_dword(process, err_ctx)
403    }
404
405    fn push_stack(&mut self, source: AdviceSource, err_ctx: &ErrorContext<impl MastNodeExt>) -> Result<(), ExecutionError> {
406        self.provider.push_stack(source, err_ctx)
407    }
408
409    fn insert_into_map(&mut self, key: Word, values: Vec<Felt>)  {
410        self.provider.insert_into_map(key, values)
411    }
412
413    fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]> {
414        self.provider.get_mapped_values(key)
415    }
416
417    fn get_tree_node(&self, root: Word, depth: &Felt, index: &Felt,
418        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
419    ) -> Result<Word, ExecutionError> {
420        self.provider.get_tree_node(root, depth, index, err_ctx)
421    }
422
423    fn get_merkle_path(&self, root: Word, depth: &Felt, index: &Felt, 
424        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
425    ) -> Result<MerklePath, ExecutionError> {
426        self.provider.get_merkle_path(root, depth, index, err_ctx)
427    }
428
429    fn get_leaf_depth(&self, root: Word, tree_depth: &Felt, index: &Felt, 
430        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
431    ) -> Result<u8, ExecutionError> {
432        self.provider.get_leaf_depth(root, tree_depth, index, err_ctx)
433    }
434
435    fn update_merkle_node(&mut self, root: Word, depth: &Felt, index: &Felt, value: Word,
436        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
437    ) -> Result<(MerklePath, Word), ExecutionError> {
438        self.provider.update_merkle_node(root, depth, index, value, err_ctx)
439    }
440
441    fn merge_roots(&mut self, lhs: Word, rhs: Word,
442        err_ctx: &ErrorContext<'_, impl MastNodeExt>,
443    ) -> Result<Word, ExecutionError> {
444        self.provider.merge_roots(lhs, rhs, err_ctx)
445    }
446}
447
448impl RecAdviceProvider {
449    // FINALIZATION
450    // --------------------------------------------------------------------------------------------
451
452    /// Consumes the advice provider and returns an `(AdviceInputs, Vec<Felt>, SimpleAdviceMap,
453    /// MerkleStore)` tuple.
454    ///
455    /// The [AdviceInputs] can be used to re-execute the program. The returned [AdviceInputs]
456    /// instance will contain only the non-deterministic inputs which were requested during program
457    /// execution.
458    ///
459    /// The `Vec<Felt>`, `SimpleAdviceMap`, and `MerkleStore` represent the stack, map, and Merkle
460    /// store of the advice provider at the time of finalization.
461    pub fn finalize(self) -> (AdviceInputs, Vec<Felt>, SimpleAdviceMap, MerkleStore) {
462        let Self { provider, init_stack } = self;
463        let BaseAdviceProvider { stack, map, store } = provider;
464
465        let (map, map_proof) = map.finalize();
466        let (store, store_proof) = store.into_inner().finalize();
467
468        let proof = AdviceInputs::default()
469            .with_stack(init_stack)
470            .with_map(map_proof)
471            .with_merkle_store(store_proof.into());
472
473        (proof, stack, map, store.into())
474    }
475}
miden_processor/host/advice/providers.rs

miden_processor/host/advice/
providers.rs
