miden_core_lib/handlers/
smt_peek.rs

1//! SMT_PEEK system event handler for the Miden VM.
2//!
3//! This handler implements the SMT_PEEK operation that pushes the value associated
4//! with a specified key in a Sparse Merkle Tree defined by the specified root onto
5//! the advice stack.
6
7use alloc::{format, string::String, vec, vec::Vec};
8
9use miden_core::{
10    Felt, WORD_SIZE, Word,
11    crypto::merkle::{EmptySubtreeRoots, SMT_DEPTH, Smt},
12    events::EventName,
13};
14use miden_processor::{ProcessorState, advice::AdviceMutation, event::EventError};
15
16/// Event name for the smt_peek operation.
17pub const SMT_PEEK_EVENT_NAME: EventName =
18    EventName::new("miden::core::collections::smt::smt_peek");
19
20/// SMT_PEEK system event handler.
21///
22/// Pushes onto the advice stack the value associated with the specified key in a Sparse
23/// Merkle Tree defined by the specified root.
24///
25/// If no value was previously associated with the specified key, [ZERO; 4] is pushed onto
26/// the advice stack.
27///
28/// Inputs:
29///   Operand stack: [event_id, KEY, ROOT, ...]
30///   Advice stack: [...]
31///
32/// Outputs:
33///   Advice stack: [VALUE, ...]
34///
35/// # Errors
36/// Returns an error if the provided Merkle root doesn't exist on the advice provider.
37///
38/// # Panics
39/// Will panic as unimplemented if the target depth is `64`.
40pub fn handle_smt_peek(process: &ProcessorState) -> Result<Vec<AdviceMutation>, EventError> {
41    let empty_leaf = EmptySubtreeRoots::entry(SMT_DEPTH, SMT_DEPTH);
42    // fetch the arguments from the operand stack
43    // Stack at emit: [event_id, KEY, ROOT, ...] where KEY and ROOT are structural words.
44    let key = process.get_stack_word(1);
45    let root = process.get_stack_word(5);
46
47    // get the node from the SMT for the specified key; this node can be either a leaf node,
48    // or a root of an empty subtree at the returned depth
49    // K[3] is used as the leaf index (most significant in BE ordering)
50    let node = process
51        .advice_provider()
52        .get_tree_node(root, Felt::new(SMT_DEPTH as u64), key[3])
53        .map_err(|err| SmtPeekError::AdviceProviderError {
54            message: format!("Failed to get tree node: {}", err),
55        })?;
56
57    if node == *empty_leaf {
58        // if the node is a root of an empty subtree, then there is no value associated with
59        // the specified key
60        let mutation = AdviceMutation::extend_stack(Smt::EMPTY_VALUE);
61        Ok(vec![mutation])
62    } else {
63        let leaf_preimage = get_smt_leaf_preimage(process, node)?;
64
65        for (key_in_leaf, value_in_leaf) in leaf_preimage {
66            if key == key_in_leaf {
67                // Found key - push value associated with key, and return
68                let mutation = AdviceMutation::extend_stack(value_in_leaf);
69                return Ok(vec![mutation]);
70            }
71        }
72
73        // if we can't find any key in the leaf that matches `key`, it means no value is
74        // associated with `key`
75        let mutation = AdviceMutation::extend_stack(Smt::EMPTY_VALUE);
76        Ok(vec![mutation])
77    }
78}
79
80// HELPER FUNCTIONS
81// ================================================================================================
82
83/// Retrieves the preimage of an SMT leaf node from the advice provider.
84fn get_smt_leaf_preimage(
85    process: &ProcessorState,
86    node: Word,
87) -> Result<Vec<(Word, Word)>, SmtPeekError> {
88    let kv_pairs = process
89        .advice_provider()
90        .get_mapped_values(&node)
91        .ok_or(SmtPeekError::SmtNodeNotFound { node })?;
92
93    if kv_pairs.len() % (WORD_SIZE * 2) != 0 {
94        return Err(SmtPeekError::InvalidSmtNodePreimage { node, preimage_len: kv_pairs.len() });
95    }
96
97    Ok(kv_pairs
98        .chunks_exact(WORD_SIZE * 2)
99        .map(|kv_chunk| {
100            let key = [kv_chunk[0], kv_chunk[1], kv_chunk[2], kv_chunk[3]];
101            let value = [kv_chunk[4], kv_chunk[5], kv_chunk[6], kv_chunk[7]];
102
103            (key.into(), value.into())
104        })
105        .collect())
106}
107
108// ERROR TYPES
109// ================================================================================================
110
111/// Error types that can occur during SMT_PEEK operations.
112#[derive(Debug, thiserror::Error)]
113pub enum SmtPeekError {
114    /// Advice provider operation failed.
115    #[error("advice provider error: {message}")]
116    AdviceProviderError { message: String },
117
118    /// SMT node not found in the advice provider.
119    #[error("SMT node not found: {node:?}")]
120    SmtNodeNotFound { node: Word },
121
122    /// SMT node preimage has invalid length.
123    #[error("invalid SMT node preimage length for node {node:?}: got {preimage_len}, expected multiple of {}", WORD_SIZE * 2)]
124    InvalidSmtNodePreimage { node: Word, preimage_len: usize },
125}
miden_core_lib/handlers/smt_peek.rs

miden_core_lib/handlers/
smt_peek.rs
