miden_processor/host/advice/
providers.rs

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

miden_processor/host/advice/
providers.rs
