miden_processor/host/advice/mod.rs
1use alloc::vec::Vec;
2
3use vm_core::{
4 Felt,
5 crypto::{hash::RpoDigest, merkle::MerklePath},
6 mast::MastNodeExt,
7};
8
9use crate::{ErrorContext, ExecutionError, ProcessState, Word};
10
11mod inputs;
12pub use inputs::AdviceInputs;
13
14mod providers;
15pub use providers::{MemAdviceProvider, RecAdviceProvider};
16
17mod source;
18pub use source::AdviceSource;
19
20// ADVICE PROVIDER
21// ================================================================================================
22
23/// Defines behavior of an advice provider.
24///
25/// An advice provider is a component through which the host can interact with the advice provider.
26/// The host can request nondeterministic inputs from the advice provider (i.e., result of a
27/// computation performed outside of the VM), as well as insert new data into the advice provider.
28///
29/// An advice provider consists of the following components:
30/// 1. Advice stack, which is a LIFO data structure. The processor can move the elements from the
31/// advice stack onto the operand stack, as well as push new elements onto the advice stack.
32/// 2. Advice map, which is a key-value map where keys are words (4 field elements) and values are
33/// vectors of field elements. The processor can push the values from the map onto the advice
34/// stack, as well as insert new values into the map.
35/// 3. Merkle store, which contains structured data reducible to Merkle paths. The VM can request
36/// Merkle paths from the store, as well as mutate it by updating or merging nodes contained in
37/// the store.
38pub trait AdviceProvider: Sized {
39 // REQUIRED METHODS
40 // --------------------------------------------------------------------------------------------
41
42 // ADVICE STACK
43 // --------------------------------------------------------------------------------------------
44
45 /// Pops an element from the advice stack and returns it.
46 ///
47 /// # Errors
48 /// Returns an error if the advice stack is empty.
49 fn pop_stack(
50 &mut self,
51 process: ProcessState,
52 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
53 ) -> Result<Felt, ExecutionError>;
54
55 /// Pops a word (4 elements) from the advice stack and returns it.
56 ///
57 /// Note: a word is popped off the stack element-by-element. For example, a `[d, c, b, a, ...]`
58 /// stack (i.e., `d` is at the top of the stack) will yield `[d, c, b, a]`.
59 ///
60 /// # Errors
61 /// Returns an error if the advice stack does not contain a full word.
62 fn pop_stack_word(
63 &mut self,
64 process: ProcessState,
65 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
66 ) -> Result<Word, ExecutionError>;
67
68 /// Pops a double word (8 elements) from the advice stack and returns them.
69 ///
70 /// Note: words are popped off the stack element-by-element. For example, a
71 /// `[h, g, f, e, d, c, b, a, ...]` stack (i.e., `h` is at the top of the stack) will yield
72 /// two words: `[h, g, f,e ], [d, c, b, a]`.
73 ///
74 /// # Errors
75 /// Returns an error if the advice stack does not contain two words.
76 fn pop_stack_dword(
77 &mut self,
78 process: ProcessState,
79 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
80 ) -> Result<[Word; 2], ExecutionError>;
81
82 /// Pushes the value(s) specified by the source onto the advice stack.
83 ///
84 /// # Errors
85 /// Returns an error if the value specified by the advice source cannot be obtained.
86 fn push_stack(
87 &mut self,
88 source: AdviceSource,
89 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
90 ) -> Result<(), ExecutionError>;
91
92 /// Returns a slice of length `length` from the top of the advice stack.
93 /// If length = 0 returns the whole advice stack.
94 fn peek_stack(&self, length: usize) -> &[Felt];
95
96 // ADVICE MAP
97 // --------------------------------------------------------------------------------------------
98
99 /// Returns a reference to the value(s) associated with the specified key in the advice map.
100 fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]>;
101
102 /// Inserts the provided value into the advice map under the specified key.
103 ///
104 /// The values in the advice map can be moved onto the advice stack by invoking
105 /// [AdviceProvider::push_stack()] method.
106 ///
107 /// If the specified key is already present in the advice map, the values under the key
108 /// are replaced with the specified values.
109 fn insert_into_map(&mut self, key: Word, values: Vec<Felt>);
110
111 // MERKLE STORE
112 // --------------------------------------------------------------------------------------------
113
114 /// Returns a node at the specified depth and index in a Merkle tree with the given root.
115 ///
116 /// # Errors
117 /// Returns an error if:
118 /// - A Merkle tree for the specified root cannot be found in this advice provider.
119 /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
120 /// by the specified root.
121 /// - Value of the node at the specified depth and index is not known to this advice provider.
122 fn get_tree_node(
123 &self,
124 root: Word,
125 depth: &Felt,
126 index: &Felt,
127 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
128 ) -> Result<Word, ExecutionError>;
129
130 /// Returns a path to a node at the specified depth and index in a Merkle tree with the
131 /// specified root.
132 ///
133 /// # Errors
134 /// Returns an error if:
135 /// - A Merkle tree for the specified root cannot be found in this advice provider.
136 /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
137 /// by the specified root.
138 /// - Path to the node at the specified depth and index is not known to this advice provider.
139 fn get_merkle_path(
140 &self,
141 root: Word,
142 depth: &Felt,
143 index: &Felt,
144 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
145 ) -> Result<MerklePath, ExecutionError>;
146
147 /// Reconstructs a path from the root until a leaf or empty node and returns its depth.
148 ///
149 /// For more information, check [crate::crypto::MerkleStore::get_leaf_depth].
150 ///
151 /// # Errors
152 /// Will return an error if:
153 /// - The provided `tree_depth` doesn't fit `u8`.
154 /// - The conditions of [crate::crypto::MerkleStore::get_leaf_depth] aren't met.
155 fn get_leaf_depth(
156 &self,
157 root: Word,
158 tree_depth: &Felt,
159 index: &Felt,
160 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
161 ) -> Result<u8, ExecutionError>;
162
163 /// Updates a node at the specified depth and index in a Merkle tree with the specified root;
164 /// returns the Merkle path from the updated node to the new root, together with the new root.
165 ///
166 /// The tree is cloned prior to the update. Thus, the advice provider retains the original and
167 /// the updated tree.
168 ///
169 /// # Errors
170 /// Returns an error if:
171 /// - A Merkle tree for the specified root cannot be found in this advice provider.
172 /// - The specified depth is either zero or greater than the depth of the Merkle tree identified
173 /// by the specified root.
174 /// - Path to the leaf at the specified index in the specified Merkle tree is not known to this
175 /// advice provider.
176 fn update_merkle_node(
177 &mut self,
178 root: Word,
179 depth: &Felt,
180 index: &Felt,
181 value: Word,
182 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
183 ) -> Result<(MerklePath, Word), ExecutionError>;
184
185 /// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
186 /// specified roots. The root of the new tree is defined as `hash(left_root, right_root)`.
187 ///
188 /// After the operation, both the original trees and the new tree remains in the advice
189 /// provider (i.e., the input trees are not removed).
190 ///
191 /// It is not checked whether a Merkle tree for either of the specified roots can be found in
192 /// this advice provider.
193 fn merge_roots(
194 &mut self,
195 lhs: Word,
196 rhs: Word,
197 err_ctx: &ErrorContext<'_, impl MastNodeExt>,
198 ) -> Result<Word, ExecutionError>;
199}