pub trait AdviceProvider: Sized {
Show 37 methods // Required methods fn pop_stack<S: ProcessState>( &mut self, process: &S ) -> Result<Felt, ExecutionError>; fn pop_stack_word<S: ProcessState>( &mut self, process: &S ) -> Result<Word, ExecutionError>; fn pop_stack_dword<S: ProcessState>( &mut self, process: &S ) -> Result<[Word; 2], ExecutionError>; fn push_stack(&mut self, source: AdviceSource) -> Result<(), ExecutionError>; fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]>; fn insert_into_map( &mut self, key: Word, values: Vec<Felt> ) -> Result<(), ExecutionError>; fn get_signature( &self, kind: SignatureKind, pub_key: Word, msg: Word ) -> Result<Vec<Felt>, ExecutionError>; fn get_tree_node( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<Word, ExecutionError>; fn get_merkle_path( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<MerklePath, ExecutionError>; fn get_leaf_depth( &self, root: Word, tree_depth: &Felt, index: &Felt ) -> Result<u8, ExecutionError>; fn find_lone_leaf( &self, root: Word, root_index: NodeIndex, tree_depth: u8 ) -> Result<Option<(NodeIndex, Word)>, ExecutionError>; fn update_merkle_node( &mut self, root: Word, depth: &Felt, index: &Felt, value: Word ) -> Result<(MerklePath, Word), ExecutionError>; fn merge_roots( &mut self, lhs: Word, rhs: Word ) -> Result<Word, ExecutionError>; fn get_store_subset<I, R>(&self, roots: I) -> MerkleStore where I: Iterator<Item = R>, R: Borrow<RpoDigest>; // Provided methods fn set_advice<S: ProcessState>( &mut self, process: &S, advice_injector: &AdviceInjector ) -> Result<HostResponse, ExecutionError> { ... } fn get_advice<S: ProcessState>( &mut self, process: &S, advice_extractor: &AdviceExtractor ) -> Result<HostResponse, ExecutionError> { ... } fn insert_mem_values_into_adv_map<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn insert_hdword_into_adv_map<S: ProcessState>( &mut self, process: &S, domain: Felt ) -> Result<HostResponse, ExecutionError> { ... } fn insert_hperm_into_adv_map<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn merge_merkle_nodes<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn copy_merkle_node_to_adv_stack<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn copy_map_value_to_adv_stack<S: ProcessState>( &mut self, process: &S, include_len: bool, key_offset: usize ) -> Result<HostResponse, ExecutionError> { ... } fn push_u64_div_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_ext2_inv_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_ext2_intt_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_signature<S: ProcessState>( &mut self, process: &S, kind: SignatureKind ) -> Result<HostResponse, ExecutionError> { ... } fn push_leading_zeros<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_trailing_zeros<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_leading_ones<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_trailing_ones<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_ilog2<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn update_operand_stack_merkle_node<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn get_operand_stack_merkle_path<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_smtpeek_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_smtget_inputs<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn push_smtset_inputs<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError> { ... } fn by_ref(&mut self) -> &mut Self { ... }
}
Expand description

Defines behavior of an advice provider.

An advice provider is a component through which the host can interact with the advice provider. The host can request nondeterministic inputs from the advice provider (i.e., result of a computation performed outside of the VM), as well as insert new data into the advice provider.

An advice provider consists of the following components:

  1. Advice stack, which is a LIFO data structure. The processor can move the elements from the advice stack onto the operand stack, as well as push new elements onto the advice stack.
  2. Advice map, which is a key-value map where keys are words (4 field elements) and values are vectors of field elements. The processor can push the values from the map onto the advice stack, as well as insert new values into the map.
  3. Merkle store, which contains structured data reducible to Merkle paths. The VM can request Merkle paths from the store, as well as mutate it by updating or merging nodes contained in the store.

Required Methods§

source

fn pop_stack<S: ProcessState>( &mut self, process: &S ) -> Result<Felt, ExecutionError>

Pops an element from the advice stack and returns it.

§Errors

Returns an error if the advice stack is empty.

source

fn pop_stack_word<S: ProcessState>( &mut self, process: &S ) -> Result<Word, ExecutionError>

Pops a word (4 elements) from the advice stack and returns it.

Note: a word is popped off the stack element-by-element. For example, a [d, c, b, a, ...] stack (i.e., d is at the top of the stack) will yield [d, c, b, a].

§Errors

Returns an error if the advice stack does not contain a full word.

source

fn pop_stack_dword<S: ProcessState>( &mut self, process: &S ) -> Result<[Word; 2], ExecutionError>

Pops a double word (8 elements) from the advice stack and returns them.

Note: words are popped off the stack element-by-element. For example, a [h, g, f, e, d, c, b, a, ...] stack (i.e., h is at the top of the stack) will yield two words: [h, g, f,e ], [d, c, b, a].

§Errors

Returns an error if the advice stack does not contain two words.

source

fn push_stack(&mut self, source: AdviceSource) -> Result<(), ExecutionError>

Pushes the value(s) specified by the source onto the advice stack.

§Errors

Returns an error if the value specified by the advice source cannot be obtained.

source

fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]>

Returns a reference to the value(s) associated with the specified key in the advice map.

source

fn insert_into_map( &mut self, key: Word, values: Vec<Felt> ) -> Result<(), ExecutionError>

Inserts the provided value into the advice map under the specified key.

The values in the advice map can be moved onto the advice stack by invoking AdviceProvider::push_stack() method.

If the specified key is already present in the advice map, the values under the key are replaced with the specified values.

source

fn get_signature( &self, kind: SignatureKind, pub_key: Word, msg: Word ) -> Result<Vec<Felt>, ExecutionError>

Returns a signature on a message using a public key.

source

fn get_tree_node( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<Word, ExecutionError>

Returns a node at the specified depth and index in a Merkle tree with the given root.

§Errors

Returns an error if:

  • A Merkle tree for the specified root cannot be found in this advice provider.
  • The specified depth is either zero or greater than the depth of the Merkle tree identified by the specified root.
  • Value of the node at the specified depth and index is not known to this advice provider.
source

fn get_merkle_path( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<MerklePath, ExecutionError>

Returns a path to a node at the specified depth and index in a Merkle tree with the specified root.

§Errors

Returns an error if:

  • A Merkle tree for the specified root cannot be found in this advice provider.
  • The specified depth is either zero or greater than the depth of the Merkle tree identified by the specified root.
  • Path to the node at the specified depth and index is not known to this advice provider.
source

fn get_leaf_depth( &self, root: Word, tree_depth: &Felt, index: &Felt ) -> Result<u8, ExecutionError>

Reconstructs a path from the root until a leaf or empty node and returns its depth.

For more information, check MerkleStore::get_leaf_depth.

§Errors

Will return an error if:

source

fn find_lone_leaf( &self, root: Word, root_index: NodeIndex, tree_depth: u8 ) -> Result<Option<(NodeIndex, Word)>, ExecutionError>

Returns node value and index of a leaf node in the subtree of the specified root, if and only if this is the only leaf in the entire subtree. Otherwise, None is returned.

The root itself is assumed to be located at the specified index in a tree with the provided depth.

§Errors

Returns an error if a three for the specified root does not exist in the advice provider.

source

fn update_merkle_node( &mut self, root: Word, depth: &Felt, index: &Felt, value: Word ) -> Result<(MerklePath, Word), ExecutionError>

Updates a node at the specified depth and index in a Merkle tree with the specified root; returns the Merkle path from the updated node to the new root, together with the new root.

The tree is cloned prior to the update. Thus, the advice provider retains the original and the updated tree.

§Errors

Returns an error if:

  • A Merkle tree for the specified root cannot be found in this advice provider.
  • The specified depth is either zero or greater than the depth of the Merkle tree identified by the specified root.
  • Path to the leaf at the specified index in the specified Merkle tree is not known to this advice provider.
source

fn merge_roots(&mut self, lhs: Word, rhs: Word) -> Result<Word, ExecutionError>

Creates a new Merkle tree in the advice provider by combining Merkle trees with the specified roots. The root of the new tree is defined as hash(left_root, right_root).

After the operation, both the original trees and the new tree remains in the advice provider (i.e., the input trees are not removed).

§Errors

Returns an error if a Merkle tree for either of the specified roots cannot be found in this advice provider.

source

fn get_store_subset<I, R>(&self, roots: I) -> MerkleStore
where I: Iterator<Item = R>, R: Borrow<RpoDigest>,

Returns a subset of this Merkle store such that the returned Merkle store contains all nodes which are descendants of the specified roots.

The roots for which no descendants exist in this Merkle store are ignored.

Provided Methods§

source

fn set_advice<S: ProcessState>( &mut self, process: &S, advice_injector: &AdviceInjector ) -> Result<HostResponse, ExecutionError>

Handles the specified advice injector request.

source

fn get_advice<S: ProcessState>( &mut self, process: &S, advice_extractor: &AdviceExtractor ) -> Result<HostResponse, ExecutionError>

Handles the specified advice extractor request.

source

fn insert_mem_values_into_adv_map<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Reads words from memory at the specified range and inserts them into the advice map under the key KEY located at the top of the stack.

Inputs: Operand stack: [KEY, start_addr, end_addr, …] Advice map: {…}

Outputs: Operand stack: [KEY, start_addr, end_addr, …] Advice map: {KEY: values}

Where values are the elements located in memory[start_addr..end_addr].

§Errors

Returns an error:

  • start_addr is greater than or equal to 2^32.
  • end_addr is greater than or equal to 2^32.
  • start_addr > end_addr.
source

fn insert_hdword_into_adv_map<S: ProcessState>( &mut self, process: &S, domain: Felt ) -> Result<HostResponse, ExecutionError>

Reads two word from the operand stack and inserts them into the advice map under the key defined by the hash of these words.

Inputs: Operand stack: [B, A, …] Advice map: {…}

Outputs: Operand stack: [B, A, …] Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}

Where KEY is computed as hash(A || B, domain), where domain is provided via the immediate value.

source

fn insert_hperm_into_adv_map<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Reads three words from the operand stack and inserts the top two words into the advice map under the key defined by applying an RPO permutation to all three words.

Inputs: Operand stack: [B, A, C, …] Advice map: {…}

Outputs: Operand stack: [B, A, C, …] Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}

Where KEY is computed by extracting the digest elements from hperm([C, A, B]). For example, if C is [0, d, 0, 0], KEY will be set as hash(A || B, d).

source

fn merge_merkle_nodes<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Creates a new Merkle tree in the advice provider by combining Merkle trees with the specified roots. The root of the new tree is defined as Hash(LEFT_ROOT, RIGHT_ROOT).

Inputs: Operand stack: [RIGHT_ROOT, LEFT_ROOT, …] Merkle store: {RIGHT_ROOT, LEFT_ROOT}

Outputs: Operand stack: [RIGHT_ROOT, LEFT_ROOT, …] Merkle store: {RIGHT_ROOT, LEFT_ROOT, hash(LEFT_ROOT, RIGHT_ROOT)}

After the operation, both the original trees and the new tree remains in the advice provider (i.e., the input trees are not removed).

§Errors

Return an error if a Merkle tree for either of the specified roots cannot be found in this advice provider.

source

fn copy_merkle_node_to_adv_stack<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes a node of the Merkle tree specified by the values on the top of the operand stack onto the advice stack.

Inputs: Operand stack: [depth, index, TREE_ROOT, …] Advice stack: […] Merkle store: {TREE_ROOT<-NODE}

Outputs: Operand stack: [depth, index, TREE_ROOT, …] Advice stack: [NODE, …] Merkle store: {TREE_ROOT<-NODE}

§Errors

Returns an error if:

  • Merkle tree for the specified root cannot be found in the advice provider.
  • The specified depth is either zero or greater than the depth of the Merkle tree identified by the specified root.
  • Value of the node at the specified depth and index is not known to the advice provider.
source

fn copy_map_value_to_adv_stack<S: ProcessState>( &mut self, process: &S, include_len: bool, key_offset: usize ) -> Result<HostResponse, ExecutionError>

Pushes a list of field elements onto the advice stack. The list is looked up in the advice map using the specified word from the operand stack as the key. If include_len is set to true, the number of elements in the value is also pushed onto the advice stack.

Inputs: Operand stack: […, KEY, …] Advice stack: […] Advice map: {KEY: values}

Outputs: Operand stack: […, KEY, …] Advice stack: [values_len?, values, …] Advice map: {KEY: values}

The key_offset value specifies the location of the KEY on the stack. For example, offset value of 0 indicates that the top word on the stack should be used as the key, the offset value of 4, indicates that the second word on the stack should be used as the key etc.

The valid values of key_offset are 0 through 12 (inclusive).

§Errors

Returns an error if the required key was not found in the key-value map or if stack offset is greater than 12.

source

fn push_u64_div_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the result of u64 division (both the quotient and the remainder) onto the advice stack.

Inputs: Operand stack: [b1, b0, a1, a0, …] Advice stack: […]

Outputs: Operand stack: [b1, b0, a1, a0, …] Advice stack: [q0, q1, r0, r1, …]

Where (a0, a1) and (b0, b1) are the 32-bit limbs of the dividend and the divisor respectively (with a0 representing the 32 lest significant bits and a1 representing the 32 most significant bits). Similarly, (q0, q1) and (r0, r1) represent the quotient and the remainder respectively.

§Errors

Returns an error if the divisor is ZERO.

source

fn push_ext2_inv_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Given an element in a quadratic extension field on the top of the stack (i.e., a0, b1), computes its multiplicative inverse and push the result onto the advice stack.

Inputs: Operand stack: [a1, a0, …] Advice stack: […]

Outputs: Operand stack: [a1, a0, …] Advice stack: [b0, b1…]

Where (b0, b1) is the multiplicative inverse of the extension field element (a0, a1) at the top of the stack.

§Errors

Returns an error if the input is a zero element in the extension field.

source

fn push_ext2_intt_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Given evaluations of a polynomial over some specified domain, interpolates the evaluations into a polynomial in coefficient form and pushes the result into the advice stack.

The interpolation is performed using the iNTT algorithm. The evaluations are expected to be in the quadratic extension.

Inputs: Operand stack: [output_size, input_size, input_start_ptr, …] Advice stack: […]

Outputs: Operand stack: [output_size, input_size, input_start_ptr, …] Advice stack: [coefficients…]

  • input_size is the number of evaluations (each evaluation is 2 base field elements). Must be a power of 2 and greater 1.
  • output_size is the number of coefficients in the interpolated polynomial (each coefficient is 2 base field elements). Must be smaller than or equal to the number of input evaluations.
  • input_start_ptr is the memory address of the first evaluation.
  • coefficients are the coefficients of the interpolated polynomial such that lowest degree coefficients are located at the top of the advice stack.
§Errors

Returns an error if:

  • input_size less than or equal to 1, or is not a power of 2.
  • output_size is 0 or is greater than the input_size.
  • input_ptr is greater than 2^32.
  • input_ptr + input_size / 2 is greater than 2^32.
source

fn push_signature<S: ProcessState>( &mut self, process: &S, kind: SignatureKind ) -> Result<HostResponse, ExecutionError>

Pushes values onto the advice stack which are required for verification of a DSA in Miden VM.

Inputs: Operand stack: [PK, MSG, …] Advice stack: […]

Outputs: Operand stack: [PK, MSG, …] Advice stack: [DATA]

Where:

  • PK is the digest of an expanded public.
  • MSG is the digest of the message to be signed.
  • DATA is the needed data for signature verification in the VM.

The advice provider is expected to contain the private key associated to the public key PK.

source

fn push_leading_zeros<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the number of the leading zeros of the top stack element onto the advice stack.

Inputs: Operand stack: [n, …] Advice stack: […]

Outputs: Operand stack: [n, …] Advice stack: [leading_zeros, …]

source

fn push_trailing_zeros<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the number of the trailing zeros of the top stack element onto the advice stack.

Inputs: Operand stack: [n, …] Advice stack: […]

Outputs: Operand stack: [n, …] Advice stack: [trailing_zeros, …]

source

fn push_leading_ones<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the number of the leading ones of the top stack element onto the advice stack.

Inputs: Operand stack: [n, …] Advice stack: […]

Outputs: Operand stack: [n, …] Advice stack: [leading_ones, …]

source

fn push_trailing_ones<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the number of the trailing ones of the top stack element onto the advice stack.

Inputs: Operand stack: [n, …] Advice stack: […]

Outputs: Operand stack: [n, …] Advice stack: [trailing_ones, …]

source

fn push_ilog2<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes the base 2 logarithm of the top stack element, rounded down. Inputs: Operand stack: [n, …] Advice stack: […]

Outputs: Operand stack: [n, …] Advice stack: [ilog2(n), …]

§Errors

Returns an error if the logarithm argument (top stack element) equals ZERO.

source

fn update_operand_stack_merkle_node<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Updates the node of a Merkle tree specified by the values on the top of the operand stack. Returns the path from the updated node to the new root of the tree to the caller.

Inputs: Operand stack: [OLD_NODE, depth, index, OLD_ROOT, NEW_NODE, …] Advice: […] Merkle store: {…}

Outputs: Operand stack: [OLD_NODE, depth, index, OLD_ROOT, NEW_NODE, …] Advice stack: […] Merkle store: {path, …} Return: [path]

source

fn get_operand_stack_merkle_path<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Extracts a Merkle path for the node specified by the values at the top of the operand stack and returns it to the caller.

§Errors

Returns an error if the Merkle store does not contain the specified Merkle path.

Inputs: Operand stack: [WORD, depth, index, ROOT, …] Advice stack: […] Advice map: {…} Merkle store: {path, …}

Outputs: Operand stack: [WORD, depth, index, ROOT, …] Advice stack: […] Advice map: {…} Merkle store: {path, …} Return: [path]

source

fn push_smtpeek_result<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Pushes onto the advice stack the value associated with the specified key in a Sparse Merkle Tree defined by the specified root.

If no value was previously associated with the specified key, [ZERO; 4] is pushed onto the advice stack.

Inputs: Operand stack: [KEY, ROOT, …] Advice stack: […]

Outputs: Operand stack: [KEY, ROOT, …] Advice stack: [VALUE, …]

§Errors

Returns an error if the provided Merkle root doesn’t exist on the advice provider.

§Panics

Will panic as unimplemented if the target depth is 64.

source

fn push_smtget_inputs<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Currently unimplemented

source

fn push_smtset_inputs<S: ProcessState>( &mut self, process: &S ) -> Result<HostResponse, ExecutionError>

Currently unimplemented

source

fn by_ref(&mut self) -> &mut Self

Creates a “by reference” advice provider for this instance.

The returned adapter also implements AdviceProvider and will simply mutably borrow this instance.

Object Safety§

This trait is not object safe.

Implementations on Foreign Types§

source§

impl<'a, T> AdviceProvider for &'a mut T
where T: AdviceProvider,

source§

fn pop_stack<S: ProcessState>( &mut self, process: &S ) -> Result<Felt, ExecutionError>

source§

fn pop_stack_word<S: ProcessState>( &mut self, process: &S ) -> Result<Word, ExecutionError>

source§

fn pop_stack_dword<S: ProcessState>( &mut self, process: &S ) -> Result<[Word; 2], ExecutionError>

source§

fn push_stack(&mut self, source: AdviceSource) -> Result<(), ExecutionError>

source§

fn insert_into_map( &mut self, key: Word, values: Vec<Felt> ) -> Result<(), ExecutionError>

source§

fn get_signature( &self, kind: SignatureKind, pub_key: Word, msg: Word ) -> Result<Vec<Felt>, ExecutionError>

source§

fn get_mapped_values(&self, key: &RpoDigest) -> Option<&[Felt]>

source§

fn get_tree_node( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<Word, ExecutionError>

source§

fn get_merkle_path( &self, root: Word, depth: &Felt, index: &Felt ) -> Result<MerklePath, ExecutionError>

source§

fn get_leaf_depth( &self, root: Word, tree_depth: &Felt, index: &Felt ) -> Result<u8, ExecutionError>

source§

fn find_lone_leaf( &self, root: Word, root_index: NodeIndex, tree_depth: u8 ) -> Result<Option<(NodeIndex, Word)>, ExecutionError>

source§

fn update_merkle_node( &mut self, root: Word, depth: &Felt, index: &Felt, value: Word ) -> Result<(MerklePath, Word), ExecutionError>

source§

fn merge_roots(&mut self, lhs: Word, rhs: Word) -> Result<Word, ExecutionError>

source§

fn get_store_subset<I, R>(&self, roots: I) -> MerkleStore
where I: Iterator<Item = R>, R: Borrow<RpoDigest>,

Implementors§

source§

impl AdviceProvider for MemAdviceProvider

Pass-through implementations of AdviceProvider methods.

TODO: potentially do this via a macro.

source§

impl AdviceProvider for RecAdviceProvider

Pass-through implementations of AdviceProvider methods.

TODO: potentially do this via a macro.