miden_processor/operations/sys_ops/
sys_event_handlers.rs

1use alloc::vec::Vec;
2
3use vm_core::{
4    Felt, FieldElement, WORD_SIZE, Word, ZERO,
5    crypto::{
6        hash::{Rpo256, RpoDigest},
7        merkle::{EmptySubtreeRoots, SMT_DEPTH, Smt},
8    },
9    sys_events::SystemEvent,
10};
11use winter_prover::math::fft;
12
13use crate::{
14    AdviceProvider, AdviceSource, ExecutionError, Ext2InttError, Host, Process, ProcessState,
15    QuadFelt,
16};
17
18/// The offset of the domain value on the stack in the `hdword_to_map_with_domain` system event.
19const HDWORD_TO_MAP_WITH_DOMAIN_DOMAIN_OFFSET: usize = 8;
20
21/// Falcon signature prime.
22const M: u64 = 12289;
23
24impl Process {
25    pub(super) fn handle_system_event(
26        &self,
27        system_event: SystemEvent,
28        host: &mut impl Host,
29    ) -> Result<(), ExecutionError> {
30        let advice_provider = host.advice_provider_mut();
31        let process_state: ProcessState = self.into();
32        match system_event {
33            SystemEvent::MerkleNodeMerge => merge_merkle_nodes(advice_provider, process_state),
34            SystemEvent::MerkleNodeToStack => {
35                copy_merkle_node_to_adv_stack(advice_provider, process_state)
36            },
37            SystemEvent::MapValueToStack => {
38                copy_map_value_to_adv_stack(advice_provider, process_state, false)
39            },
40            SystemEvent::MapValueToStackN => {
41                copy_map_value_to_adv_stack(advice_provider, process_state, true)
42            },
43            SystemEvent::U64Div => push_u64_div_result(advice_provider, process_state),
44            SystemEvent::FalconDiv => push_falcon_mod_result(advice_provider, process_state),
45            SystemEvent::Ext2Inv => push_ext2_inv_result(advice_provider, process_state),
46            SystemEvent::Ext2Intt => push_ext2_intt_result(advice_provider, process_state),
47            SystemEvent::SmtPeek => push_smtpeek_result(advice_provider, process_state),
48            SystemEvent::U32Clz => push_leading_zeros(advice_provider, process_state),
49            SystemEvent::U32Ctz => push_trailing_zeros(advice_provider, process_state),
50            SystemEvent::U32Clo => push_leading_ones(advice_provider, process_state),
51            SystemEvent::U32Cto => push_trailing_ones(advice_provider, process_state),
52            SystemEvent::ILog2 => push_ilog2(advice_provider, process_state),
53
54            SystemEvent::MemToMap => insert_mem_values_into_adv_map(advice_provider, process_state),
55            SystemEvent::HdwordToMap => {
56                insert_hdword_into_adv_map(advice_provider, process_state, ZERO)
57            },
58            SystemEvent::HdwordToMapWithDomain => {
59                let domain = self.stack.get(HDWORD_TO_MAP_WITH_DOMAIN_DOMAIN_OFFSET);
60                insert_hdword_into_adv_map(advice_provider, process_state, domain)
61            },
62            SystemEvent::HpermToMap => insert_hperm_into_adv_map(advice_provider, process_state),
63        }
64    }
65}
66
67/// Reads elements from memory at the specified range and inserts them into the advice map under
68/// the key `KEY` located at the top of the stack.
69///
70/// Inputs:
71///   Operand stack: [KEY, start_addr, end_addr, ...]
72///   Advice map: {...}
73///
74/// Outputs:
75///   Operand stack: [KEY, start_addr, end_addr, ...]
76///   Advice map: {KEY: values}
77///
78/// Where `values` are the elements located in memory[start_addr..end_addr].
79///
80/// # Errors
81/// Returns an error:
82/// - `start_addr` is greater than or equal to 2^32.
83/// - `end_addr` is greater than or equal to 2^32.
84/// - `start_addr` > `end_addr`.
85pub fn insert_mem_values_into_adv_map(
86    advice_provider: &mut impl AdviceProvider,
87    process: ProcessState,
88) -> Result<(), ExecutionError> {
89    let (start_addr, end_addr) = get_mem_addr_range(process, 4, 5)?;
90    let ctx = process.ctx();
91
92    let mut values = Vec::with_capacity(((end_addr - start_addr) as usize) * WORD_SIZE);
93    for addr in start_addr..end_addr {
94        let mem_value = process.get_mem_value(ctx, addr).unwrap_or(ZERO);
95        values.push(mem_value);
96    }
97
98    let key = process.get_stack_word(0);
99    advice_provider.insert_into_map(key, values);
100
101    Ok(())
102}
103
104/// Reads two word from the operand stack and inserts them into the advice map under the key
105/// defined by the hash of these words.
106///
107/// Inputs:
108///   Operand stack: [B, A, ...]
109///   Advice map: {...}
110///
111/// Outputs:
112///   Operand stack: [B, A, ...]
113///   Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
114///
115/// Where KEY is computed as hash(A || B, domain), where domain is provided via the immediate
116/// value.
117pub fn insert_hdword_into_adv_map(
118    advice_provider: &mut impl AdviceProvider,
119    process: ProcessState,
120    domain: Felt,
121) -> Result<(), ExecutionError> {
122    // get the top two words from the stack and hash them to compute the key value
123    let word0 = process.get_stack_word(0);
124    let word1 = process.get_stack_word(1);
125    let key = Rpo256::merge_in_domain(&[word1.into(), word0.into()], domain);
126
127    // build a vector of values from the two word and insert it into the advice map under the
128    // computed key
129    let mut values = Vec::with_capacity(2 * WORD_SIZE);
130    values.extend_from_slice(&word1);
131    values.extend_from_slice(&word0);
132    advice_provider.insert_into_map(key.into(), values);
133
134    Ok(())
135}
136
137/// Reads three words from the operand stack and inserts the top two words into the advice map
138/// under the key defined by applying an RPO permutation to all three words.
139///
140/// Inputs:
141///   Operand stack: [B, A, C, ...]
142///   Advice map: {...}
143///
144/// Outputs:
145///   Operand stack: [B, A, C, ...]
146///   Advice map: {KEY: [a0, a1, a2, a3, b0, b1, b2, b3]}
147///
148/// Where KEY is computed by extracting the digest elements from hperm([C, A, B]). For example,
149/// if C is [0, d, 0, 0], KEY will be set as hash(A || B, d).
150pub fn insert_hperm_into_adv_map(
151    advice_provider: &mut impl AdviceProvider,
152    process: ProcessState,
153) -> Result<(), ExecutionError> {
154    // read the state from the stack
155    let mut state = [
156        process.get_stack_item(11),
157        process.get_stack_item(10),
158        process.get_stack_item(9),
159        process.get_stack_item(8),
160        process.get_stack_item(7),
161        process.get_stack_item(6),
162        process.get_stack_item(5),
163        process.get_stack_item(4),
164        process.get_stack_item(3),
165        process.get_stack_item(2),
166        process.get_stack_item(1),
167        process.get_stack_item(0),
168    ];
169
170    // get the values to be inserted into the advice map from the state
171    let values = state[Rpo256::RATE_RANGE].to_vec();
172
173    // apply the permutation to the state and extract the key from it
174    Rpo256::apply_permutation(&mut state);
175    let key = RpoDigest::new(
176        state[Rpo256::DIGEST_RANGE]
177            .try_into()
178            .expect("failed to extract digest from state"),
179    );
180
181    advice_provider.insert_into_map(key.into(), values);
182
183    Ok(())
184}
185
186/// Creates a new Merkle tree in the advice provider by combining Merkle trees with the
187/// specified roots. The root of the new tree is defined as `Hash(LEFT_ROOT, RIGHT_ROOT)`.
188///
189/// Inputs:
190///   Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
191///   Merkle store: {RIGHT_ROOT, LEFT_ROOT}
192///
193/// Outputs:
194///   Operand stack: [RIGHT_ROOT, LEFT_ROOT, ...]
195///   Merkle store: {RIGHT_ROOT, LEFT_ROOT, hash(LEFT_ROOT, RIGHT_ROOT)}
196///
197/// After the operation, both the original trees and the new tree remains in the advice
198/// provider (i.e., the input trees are not removed).
199///
200/// It is not checked whether the provided roots exist as Merkle trees in the advide providers.
201pub fn merge_merkle_nodes(
202    advice_provider: &mut impl AdviceProvider,
203    process: ProcessState,
204) -> Result<(), ExecutionError> {
205    // fetch the arguments from the stack
206    let lhs = process.get_stack_word(1);
207    let rhs = process.get_stack_word(0);
208
209    // perform the merge
210    advice_provider.merge_roots(lhs, rhs)?;
211
212    Ok(())
213}
214
215/// Pushes a node of the Merkle tree specified by the values on the top of the operand stack
216/// onto the advice stack.
217///
218/// Inputs:
219///   Operand stack: [depth, index, TREE_ROOT, ...]
220///   Advice stack: [...]
221///   Merkle store: {TREE_ROOT<-NODE}
222///
223/// Outputs:
224///   Operand stack: [depth, index, TREE_ROOT, ...]
225///   Advice stack: [NODE, ...]
226///   Merkle store: {TREE_ROOT<-NODE}
227///
228/// # Errors
229/// Returns an error if:
230/// - Merkle tree for the specified root cannot be found in the advice provider.
231/// - The specified depth is either zero or greater than the depth of the Merkle tree identified by
232///   the specified root.
233/// - Value of the node at the specified depth and index is not known to the advice provider.
234pub fn copy_merkle_node_to_adv_stack(
235    advice_provider: &mut impl AdviceProvider,
236    process: ProcessState,
237) -> Result<(), ExecutionError> {
238    let depth = process.get_stack_item(0);
239    let index = process.get_stack_item(1);
240    let root = [
241        process.get_stack_item(5),
242        process.get_stack_item(4),
243        process.get_stack_item(3),
244        process.get_stack_item(2),
245    ];
246
247    let node = advice_provider.get_tree_node(root, &depth, &index)?;
248
249    advice_provider.push_stack(AdviceSource::Value(node[3]))?;
250    advice_provider.push_stack(AdviceSource::Value(node[2]))?;
251    advice_provider.push_stack(AdviceSource::Value(node[1]))?;
252    advice_provider.push_stack(AdviceSource::Value(node[0]))?;
253
254    Ok(())
255}
256
257/// Pushes a list of field elements onto the advice stack. The list is looked up in the advice
258/// map using the specified word from the operand stack as the key. If `include_len` is set to
259/// true, the number of elements in the value is also pushed onto the advice stack.
260///
261/// Inputs:
262///   Operand stack: [..., KEY, ...]
263///   Advice stack: [...]
264///   Advice map: {KEY: values}
265///
266/// Outputs:
267///   Operand stack: [..., KEY, ...]
268///   Advice stack: [values_len?, values, ...]
269///   Advice map: {KEY: values}
270///
271/// The `key_offset` value specifies the location of the `KEY` on the stack. For example,
272/// offset value of 0 indicates that the top word on the stack should be used as the key, the
273/// offset value of 4, indicates that the second word on the stack should be used as the key
274/// etc.
275///
276/// The valid values of `key_offset` are 0 through 12 (inclusive).
277///
278/// # Errors
279/// Returns an error if the required key was not found in the key-value map or if stack offset
280/// is greater than 12.
281pub fn copy_map_value_to_adv_stack(
282    advice_provider: &mut impl AdviceProvider,
283    process: ProcessState,
284    include_len: bool,
285) -> Result<(), ExecutionError> {
286    let key = [
287        process.get_stack_item(3),
288        process.get_stack_item(2),
289        process.get_stack_item(1),
290        process.get_stack_item(0),
291    ];
292    advice_provider.push_stack(AdviceSource::Map { key, include_len })?;
293
294    Ok(())
295}
296
297/// Pushes the result of [u64] division (both the quotient and the remainder) onto the advice
298/// stack.
299///
300/// Inputs:
301///   Operand stack: [b1, b0, a1, a0, ...]
302///   Advice stack: [...]
303///
304/// Outputs:
305///   Operand stack: [b1, b0, a1, a0, ...]
306///   Advice stack: [q0, q1, r0, r1, ...]
307///
308/// Where (a0, a1) and (b0, b1) are the 32-bit limbs of the dividend and the divisor
309/// respectively (with a0 representing the 32 lest significant bits and a1 representing the
310/// 32 most significant bits). Similarly, (q0, q1) and (r0, r1) represent the quotient and
311/// the remainder respectively.
312///
313/// # Errors
314/// Returns an error if the divisor is ZERO.
315pub fn push_u64_div_result(
316    advice_provider: &mut impl AdviceProvider,
317    process: ProcessState,
318) -> Result<(), ExecutionError> {
319    let divisor = {
320        let divisor_hi = process.get_stack_item(0).as_int();
321        let divisor_lo = process.get_stack_item(1).as_int();
322
323        // Ensure the divisor is a pair of u32 values
324        if divisor_hi > u32::MAX.into() {
325            return Err(ExecutionError::NotU32Value(Felt::new(divisor_hi), ZERO));
326        }
327        if divisor_lo > u32::MAX.into() {
328            return Err(ExecutionError::NotU32Value(Felt::new(divisor_lo), ZERO));
329        }
330
331        let divisor = (divisor_hi << 32) + divisor_lo;
332
333        if divisor == 0 {
334            return Err(ExecutionError::DivideByZero(process.clk()));
335        }
336
337        divisor
338    };
339
340    let dividend = {
341        let dividend_hi = process.get_stack_item(2).as_int();
342        let dividend_lo = process.get_stack_item(3).as_int();
343
344        // Ensure the dividend is a pair of u32 values
345        if dividend_hi > u32::MAX.into() {
346            return Err(ExecutionError::NotU32Value(Felt::new(dividend_hi), ZERO));
347        }
348        if dividend_lo > u32::MAX.into() {
349            return Err(ExecutionError::NotU32Value(Felt::new(dividend_lo), ZERO));
350        }
351
352        (dividend_hi << 32) + dividend_lo
353    };
354
355    let quotient = dividend / divisor;
356    let remainder = dividend - quotient * divisor;
357
358    let (q_hi, q_lo) = u64_to_u32_elements(quotient);
359    let (r_hi, r_lo) = u64_to_u32_elements(remainder);
360
361    advice_provider.push_stack(AdviceSource::Value(r_hi))?;
362    advice_provider.push_stack(AdviceSource::Value(r_lo))?;
363    advice_provider.push_stack(AdviceSource::Value(q_hi))?;
364    advice_provider.push_stack(AdviceSource::Value(q_lo))?;
365
366    Ok(())
367}
368
369/// Pushes the result of divison (both the quotient and the remainder) of a [u64] by the Falcon
370/// prime (M = 12289) onto the advice stack.
371///
372/// Inputs:
373///   Operand stack: [a1, a0, ...]
374///   Advice stack: [...]
375///
376/// Outputs:
377///   Operand stack: [a1, a0, ...]
378///   Advice stack: [q1, q0, r, ...]
379///
380/// Where (a0, a1) are the 32-bit limbs of the dividend (with a0 representing the 32 least
381/// significant bits and a1 representing the 32 most significant bits).
382/// Similarly, (q0, q1) represent the quotient and r the remainder.
383///
384/// # Errors
385/// Returns an error if the divisor is ZERO.
386pub fn push_falcon_mod_result(
387    advice_provider: &mut impl AdviceProvider,
388    process: ProcessState,
389) -> Result<(), ExecutionError> {
390    let dividend_hi = process.get_stack_item(0).as_int();
391    let dividend_lo = process.get_stack_item(1).as_int();
392    let dividend = (dividend_hi << 32) + dividend_lo;
393
394    let (quotient, remainder) = (dividend / M, dividend % M);
395
396    let (q_hi, q_lo) = u64_to_u32_elements(quotient);
397    let (r_hi, r_lo) = u64_to_u32_elements(remainder);
398    assert_eq!(r_hi, ZERO);
399
400    advice_provider.push_stack(AdviceSource::Value(r_lo))?;
401    advice_provider.push_stack(AdviceSource::Value(q_lo))?;
402    advice_provider.push_stack(AdviceSource::Value(q_hi))?;
403
404    Ok(())
405}
406
407/// Given an element in a quadratic extension field on the top of the stack (i.e., a0, b1),
408/// computes its multiplicative inverse and push the result onto the advice stack.
409///
410/// Inputs:
411///   Operand stack: [a1, a0, ...]
412///   Advice stack: [...]
413///
414/// Outputs:
415///   Operand stack: [a1, a0, ...]
416///   Advice stack: [b0, b1...]
417///
418/// Where (b0, b1) is the multiplicative inverse of the extension field element (a0, a1) at the
419/// top of the stack.
420///
421/// # Errors
422/// Returns an error if the input is a zero element in the extension field.
423pub fn push_ext2_inv_result(
424    advice_provider: &mut impl AdviceProvider,
425    process: ProcessState,
426) -> Result<(), ExecutionError> {
427    let coef0 = process.get_stack_item(1);
428    let coef1 = process.get_stack_item(0);
429
430    let element = QuadFelt::new(coef0, coef1);
431    if element == QuadFelt::ZERO {
432        return Err(ExecutionError::DivideByZero(process.clk()));
433    }
434    let result = element.inv().to_base_elements();
435
436    advice_provider.push_stack(AdviceSource::Value(result[1]))?;
437    advice_provider.push_stack(AdviceSource::Value(result[0]))?;
438
439    Ok(())
440}
441
442/// Given evaluations of a polynomial over some specified domain, interpolates the evaluations
443///  into a polynomial in coefficient form and pushes the result into the advice stack.
444///
445/// The interpolation is performed using the iNTT algorithm. The evaluations are expected to be
446/// in the quadratic extension.
447///
448/// Inputs:
449///   Operand stack: [output_size, input_size, input_start_ptr, ...]
450///   Advice stack: [...]
451///
452/// Outputs:
453///   Operand stack: [output_size, input_size, input_start_ptr, ...]
454///   Advice stack: [coefficients...]
455///
456/// - `input_size` is the number of evaluations (each evaluation is 2 base field elements). Must be
457///   a power of 2 and greater 1.
458/// - `output_size` is the number of coefficients in the interpolated polynomial (each coefficient
459///   is 2 base field elements). Must be smaller than or equal to the number of input evaluations.
460/// - `input_start_ptr` is the memory address of the first evaluation.
461/// - `coefficients` are the coefficients of the interpolated polynomial such that lowest degree
462///   coefficients are located at the top of the advice stack.
463///
464/// # Errors
465/// Returns an error if:
466/// - `input_size` less than or equal to 1, or is not a power of 2.
467/// - `output_size` is 0 or is greater than the `input_size`.
468/// - `input_ptr` is greater than 2^32, or is not aligned on a word boundary.
469/// - `input_ptr + input_size * 2` is greater than 2^32.
470pub fn push_ext2_intt_result(
471    advice_provider: &mut impl AdviceProvider,
472    process: ProcessState,
473) -> Result<(), ExecutionError> {
474    let output_size = process.get_stack_item(0).as_int() as usize;
475    let input_size = process.get_stack_item(1).as_int() as usize;
476    let input_start_ptr = process.get_stack_item(2).as_int();
477
478    if input_size <= 1 {
479        return Err(Ext2InttError::DomainSizeTooSmall(input_size as u64).into());
480    }
481    if !input_size.is_power_of_two() {
482        return Err(Ext2InttError::DomainSizeNotPowerOf2(input_size as u64).into());
483    }
484    if input_start_ptr >= u32::MAX as u64 {
485        return Err(Ext2InttError::InputStartAddressTooBig(input_start_ptr).into());
486    }
487    if input_start_ptr % WORD_SIZE as u64 != 0 {
488        return Err(Ext2InttError::InputStartNotWordAligned(input_start_ptr).into());
489    }
490    if input_size > u32::MAX as usize {
491        return Err(Ext2InttError::InputSizeTooBig(input_size as u64).into());
492    }
493
494    let input_end_ptr = input_start_ptr + (input_size * 2) as u64;
495    if input_end_ptr > u32::MAX as u64 {
496        return Err(Ext2InttError::InputEndAddressTooBig(input_end_ptr).into());
497    }
498
499    if output_size == 0 {
500        return Err(Ext2InttError::OutputSizeIsZero.into());
501    }
502    if output_size > input_size {
503        return Err(Ext2InttError::OutputSizeTooBig(output_size, input_size).into());
504    }
505
506    let mut poly = Vec::with_capacity(input_size);
507    for addr in ((input_start_ptr as u32)..(input_end_ptr as u32)).step_by(4) {
508        let word = process
509            .get_mem_word(process.ctx(), addr)?
510            .ok_or(Ext2InttError::UninitializedMemoryAddress(addr))?;
511
512        poly.push(QuadFelt::new(word[0], word[1]));
513        poly.push(QuadFelt::new(word[2], word[3]));
514    }
515
516    let twiddles = fft::get_inv_twiddles::<Felt>(input_size);
517    fft::interpolate_poly::<Felt, QuadFelt>(&mut poly, &twiddles);
518
519    for element in QuadFelt::slice_as_base_elements(&poly[..output_size]).iter().rev() {
520        advice_provider.push_stack(AdviceSource::Value(*element))?;
521    }
522
523    Ok(())
524}
525
526/// Pushes the number of the leading zeros of the top stack element onto the advice stack.
527///
528/// Inputs:
529///   Operand stack: [n, ...]
530///   Advice stack: [...]
531///
532/// Outputs:
533///   Operand stack: [n, ...]
534///   Advice stack: [leading_zeros, ...]
535pub fn push_leading_zeros(
536    advice_provider: &mut impl AdviceProvider,
537    process: ProcessState,
538) -> Result<(), ExecutionError> {
539    push_transformed_stack_top(advice_provider, process, |stack_top| {
540        Felt::from(stack_top.leading_zeros())
541    })
542}
543
544/// Pushes the number of the trailing zeros of the top stack element onto the advice stack.
545///
546/// Inputs:
547///   Operand stack: [n, ...]
548///   Advice stack: [...]
549///
550/// Outputs:
551///   Operand stack: [n, ...]
552///   Advice stack: [trailing_zeros, ...]
553pub fn push_trailing_zeros(
554    advice_provider: &mut impl AdviceProvider,
555    process: ProcessState,
556) -> Result<(), ExecutionError> {
557    push_transformed_stack_top(advice_provider, process, |stack_top| {
558        Felt::from(stack_top.trailing_zeros())
559    })
560}
561
562/// Pushes the number of the leading ones of the top stack element onto the advice stack.
563///
564/// Inputs:
565///   Operand stack: [n, ...]
566///   Advice stack: [...]
567///
568/// Outputs:
569///   Operand stack: [n, ...]
570///   Advice stack: [leading_ones, ...]
571pub fn push_leading_ones(
572    advice_provider: &mut impl AdviceProvider,
573    process: ProcessState,
574) -> Result<(), ExecutionError> {
575    push_transformed_stack_top(advice_provider, process, |stack_top| {
576        Felt::from(stack_top.leading_ones())
577    })
578}
579
580/// Pushes the number of the trailing ones of the top stack element onto the advice stack.
581///
582/// Inputs:
583///   Operand stack: [n, ...]
584///   Advice stack: [...]
585///
586/// Outputs:
587///   Operand stack: [n, ...]
588///   Advice stack: [trailing_ones, ...]
589pub fn push_trailing_ones(
590    advice_provider: &mut impl AdviceProvider,
591    process: ProcessState,
592) -> Result<(), ExecutionError> {
593    push_transformed_stack_top(advice_provider, process, |stack_top| {
594        Felt::from(stack_top.trailing_ones())
595    })
596}
597
598/// Pushes the base 2 logarithm of the top stack element, rounded down.
599/// Inputs:
600///   Operand stack: [n, ...]
601///   Advice stack: [...]
602///
603/// Outputs:
604///   Operand stack: [n, ...]
605///   Advice stack: [ilog2(n), ...]
606///
607/// # Errors
608/// Returns an error if the logarithm argument (top stack element) equals ZERO.
609pub fn push_ilog2(
610    advice_provider: &mut impl AdviceProvider,
611    process: ProcessState,
612) -> Result<(), ExecutionError> {
613    let n = process.get_stack_item(0).as_int();
614    if n == 0 {
615        return Err(ExecutionError::LogArgumentZero(process.clk()));
616    }
617    let ilog2 = Felt::from(n.ilog2());
618    advice_provider.push_stack(AdviceSource::Value(ilog2))?;
619    Ok(())
620}
621
622/// Pushes onto the advice stack the value associated with the specified key in a Sparse
623/// Merkle Tree defined by the specified root.
624///
625/// If no value was previously associated with the specified key, [ZERO; 4] is pushed onto
626/// the advice stack.
627///
628/// Inputs:
629///   Operand stack: [KEY, ROOT, ...]
630///   Advice stack: [...]
631///
632/// Outputs:
633///   Operand stack: [KEY, ROOT, ...]
634///   Advice stack: [VALUE, ...]
635///
636/// # Errors
637/// Returns an error if the provided Merkle root doesn't exist on the advice provider.
638///
639/// # Panics
640/// Will panic as unimplemented if the target depth is `64`.
641pub fn push_smtpeek_result(
642    advice_provider: &mut impl AdviceProvider,
643    process: ProcessState,
644) -> Result<(), ExecutionError> {
645    let empty_leaf = EmptySubtreeRoots::entry(SMT_DEPTH, SMT_DEPTH);
646    // fetch the arguments from the operand stack
647    let key = process.get_stack_word(0);
648    let root = process.get_stack_word(1);
649
650    // get the node from the SMT for the specified key; this node can be either a leaf node,
651    // or a root of an empty subtree at the returned depth
652    let node = advice_provider.get_tree_node(root, &Felt::new(SMT_DEPTH as u64), &key[3])?;
653
654    if node == Word::from(empty_leaf) {
655        // if the node is a root of an empty subtree, then there is no value associated with
656        // the specified key
657        advice_provider.push_stack(AdviceSource::Word(Smt::EMPTY_VALUE))?;
658    } else {
659        let leaf_preimage = get_smt_leaf_preimage(advice_provider, node)?;
660
661        for (key_in_leaf, value_in_leaf) in leaf_preimage {
662            if key == key_in_leaf {
663                // Found key - push value associated with key, and return
664                advice_provider.push_stack(AdviceSource::Word(value_in_leaf))?;
665
666                return Ok(());
667            }
668        }
669
670        // if we can't find any key in the leaf that matches `key`, it means no value is
671        // associated with `key`
672        advice_provider.push_stack(AdviceSource::Word(Smt::EMPTY_VALUE))?;
673    }
674    Ok(())
675}
676
677// HELPER METHODS
678// --------------------------------------------------------------------------------------------
679
680/// Reads (start_addr, end_addr) tuple from the specified elements of the operand stack (
681/// without modifying the state of the stack), and verifies that memory range is valid.
682fn get_mem_addr_range(
683    process: ProcessState,
684    start_idx: usize,
685    end_idx: usize,
686) -> Result<(u32, u32), ExecutionError> {
687    let start_addr = process.get_stack_item(start_idx).as_int();
688    let end_addr = process.get_stack_item(end_idx).as_int();
689
690    if start_addr > u32::MAX as u64 {
691        return Err(ExecutionError::MemoryAddressOutOfBounds(start_addr));
692    }
693    if end_addr > u32::MAX as u64 {
694        return Err(ExecutionError::MemoryAddressOutOfBounds(end_addr));
695    }
696
697    if start_addr > end_addr {
698        return Err(ExecutionError::InvalidMemoryRange { start_addr, end_addr });
699    }
700
701    Ok((start_addr as u32, end_addr as u32))
702}
703
704fn u64_to_u32_elements(value: u64) -> (Felt, Felt) {
705    let hi = Felt::from((value >> 32) as u32);
706    let lo = Felt::from(value as u32);
707    (hi, lo)
708}
709
710/// Gets the top stack element, applies a provided function to it and pushes it to the advice
711/// provider.
712fn push_transformed_stack_top<A: AdviceProvider>(
713    advice_provider: &mut A,
714    process: ProcessState,
715    f: impl FnOnce(u32) -> Felt,
716) -> Result<(), ExecutionError> {
717    let stack_top = process.get_stack_item(0);
718    let stack_top: u32 = stack_top
719        .as_int()
720        .try_into()
721        .map_err(|_| ExecutionError::NotU32Value(stack_top, ZERO))?;
722    let transformed_stack_top = f(stack_top);
723    advice_provider.push_stack(AdviceSource::Value(transformed_stack_top))?;
724    Ok(())
725}
726
727fn get_smt_leaf_preimage<A: AdviceProvider>(
728    advice_provider: &A,
729    node: Word,
730) -> Result<Vec<(Word, Word)>, ExecutionError> {
731    let node_bytes = RpoDigest::from(node);
732
733    let kv_pairs = advice_provider
734        .get_mapped_values(&node_bytes)
735        .ok_or(ExecutionError::SmtNodeNotFound(node))?;
736
737    if kv_pairs.len() % WORD_SIZE * 2 != 0 {
738        return Err(ExecutionError::SmtNodePreImageNotValid(node, kv_pairs.len()));
739    }
740
741    Ok(kv_pairs
742        .chunks_exact(WORD_SIZE * 2)
743        .map(|kv_chunk| {
744            let key = [kv_chunk[0], kv_chunk[1], kv_chunk[2], kv_chunk[3]];
745            let value = [kv_chunk[4], kv_chunk[5], kv_chunk[6], kv_chunk[7]];
746
747            (key, value)
748        })
749        .collect())
750}
miden_processor/operations/sys_ops/sys_event_handlers.rs

miden_processor/operations/sys_ops/
sys_event_handlers.rs
