tasm_lib/hashing/
merkle_step_mem_u64_index.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::hashing::merkle_step_u64_index::MerkleStepU64Index;
6use crate::prelude::*;
7use crate::traits::basic_snippet::Reviewer;
8use crate::traits::basic_snippet::SignOffFingerprint;
9
10/// Similar to instruction `merkle_step_mem`, but for index of type `u64`
11/// instead of the native `u32`. The most notable difference is that the stack
12/// element with index 6 (“`st6`”) will generally be modified.
13///
14/// ### Behavior
15///
16/// ```text
17/// BEFORE: _ ram_ptr  [merkle_tree_node_index: u64] [node: Digest]
18/// AFTER:  _ ram_ptr' [merkle_tree_parent_node_index: u64] [parent_node: Digest]
19/// ```
20///
21/// ### Preconditions
22///
23/// - all input arguments are properly [`BFieldCodec`] encoded
24///
25/// ### Postconditions
26///
27/// - all output is properly [`BFieldCodec`] encoded
28/// - the `ram_ptr` is incremented by [`Digest::LEN`]
29#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
30pub struct MerkleStepMemU64Index;
31
32impl BasicSnippet for MerkleStepMemU64Index {
33    fn parameters(&self) -> Vec<(DataType, String)> {
34        vec![
35            (DataType::VoidPointer, "ram pointer".to_owned()),
36            (DataType::U64, "merkle tree node index".to_owned()),
37            (DataType::Digest, "node".to_owned()),
38        ]
39    }
40
41    fn return_values(&self) -> Vec<(DataType, String)> {
42        vec![
43            (DataType::VoidPointer, "ram pointer".to_owned()),
44            (DataType::U64, "merkle tree parent node index".to_owned()),
45            (DataType::Digest, "parent node".to_owned()),
46        ]
47    }
48
49    fn entrypoint(&self) -> String {
50        "tasmlib_hashing_merkle_step_mem_u64_index".to_owned()
51    }
52
53    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
54        triton_asm!(
55            {self.entrypoint()}:
56                merkle_step_mem
57                // _ ptr' mt_idx_hi (mt_idx_lo / 2) [parent_node: Digest]
58
59                {&MerkleStepU64Index::make_u64_index_consistent()}
60                // _ ptr' (mt_index / 2)_hi (mt_index / 2)_lo [parent_node: Digest]
61
62                return
63        )
64    }
65
66    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
67        let mut sign_offs = HashMap::new();
68        sign_offs.insert(Reviewer("ferdinand"), 0xb5f098c6c0c971c3.into());
69        sign_offs
70    }
71}
72
73#[cfg(test)]
74mod tests {
75    use std::collections::VecDeque;
76
77    use super::*;
78    use crate::test_prelude::*;
79
80    impl MerkleStepMemU64Index {
81        fn set_up_initial_state(
82            &self,
83            ram_ptr: BFieldElement,
84            leaf_index: u64,
85        ) -> ReadOnlyAlgorithmInitialState {
86            let mut stack = self.init_stack_for_isolated_run();
87            push_encodable(&mut stack, &ram_ptr);
88            push_encodable(&mut stack, &leaf_index);
89            push_encodable(&mut stack, &rand::random::<Digest>());
90
91            let mut nondeterminism = NonDeterminism::default();
92            encode_to_memory(&mut nondeterminism.ram, ram_ptr, &rand::random::<Digest>());
93
94            ReadOnlyAlgorithmInitialState {
95                stack,
96                nondeterminism,
97            }
98        }
99    }
100
101    impl ReadOnlyAlgorithm for MerkleStepMemU64Index {
102        fn rust_shadow(
103            &self,
104            stack: &mut Vec<BFieldElement>,
105            memory: &HashMap<BFieldElement, BFieldElement>,
106            _: VecDeque<BFieldElement>,
107            _: VecDeque<Digest>,
108        ) -> Result<(), RustShadowError> {
109            let stack_digest = pop_encodable::<Digest>(stack)?;
110            let leaf_index = pop_encodable::<u64>(stack)?;
111            let ram_ptr = pop_encodable::<BFieldElement>(stack)?;
112
113            let stack_digest_is_left_sibling = leaf_index.is_multiple_of(2);
114            let sibling_digest = *Digest::decode_from_memory(memory, ram_ptr)
115                .map_err(|_| RustShadowError::DecodingError)?;
116            let (left_digest, right_digest) = if stack_digest_is_left_sibling {
117                (stack_digest, sibling_digest)
118            } else {
119                (sibling_digest, stack_digest)
120            };
121
122            let parent_digest = Tip5::hash_pair(left_digest, right_digest);
123            let parent_index = leaf_index / 2;
124
125            push_encodable(stack, &(ram_ptr + bfe!(Digest::LEN)));
126            push_encodable(stack, &parent_index);
127            push_encodable(stack, &parent_digest);
128
129            Ok(())
130        }
131
132        fn pseudorandom_initial_state(
133            &self,
134            seed: [u8; 32],
135            bench_case: Option<BenchmarkCase>,
136        ) -> ReadOnlyAlgorithmInitialState {
137            let mut rng = StdRng::from_seed(seed);
138            let leaf_index = match bench_case {
139                Some(BenchmarkCase::CommonCase) => 1 << 33,
140                Some(BenchmarkCase::WorstCase) => 1 << 63,
141                None => rng.random(),
142            };
143
144            self.set_up_initial_state(rng.random(), leaf_index)
145        }
146    }
147
148    #[macro_rules_attr::apply(test)]
149    fn unit() {
150        ShadowedReadOnlyAlgorithm::new(MerkleStepMemU64Index).test();
151    }
152}
153
154#[cfg(test)]
155mod benches {
156    use super::*;
157    use crate::test_prelude::*;
158
159    #[macro_rules_attr::apply(test)]
160    fn benchmark() {
161        ShadowedReadOnlyAlgorithm::new(MerkleStepMemU64Index).bench();
162    }
163}
tasm_lib/hashing/merkle_step_mem_u64_index.rs

tasm_lib/hashing/
merkle_step_mem_u64_index.rs
