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 inputs(&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 outputs(&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"), 0xd1c95ceda7a3fa88.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        ) {
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 % 2 == 0;
114            let sibling_digest = *Digest::decode_from_memory(memory, ram_ptr).unwrap();
115            let (left_digest, right_digest) = if stack_digest_is_left_sibling {
116                (stack_digest, sibling_digest)
117            } else {
118                (sibling_digest, stack_digest)
119            };
120
121            let parent_digest = Tip5::hash_pair(left_digest, right_digest);
122            let parent_index = leaf_index / 2;
123
124            push_encodable(stack, &(ram_ptr + bfe!(Digest::LEN)));
125            push_encodable(stack, &parent_index);
126            push_encodable(stack, &parent_digest);
127        }
128
129        fn pseudorandom_initial_state(
130            &self,
131            seed: [u8; 32],
132            bench_case: Option<BenchmarkCase>,
133        ) -> ReadOnlyAlgorithmInitialState {
134            let mut rng = StdRng::from_seed(seed);
135            let leaf_index = match bench_case {
136                Some(BenchmarkCase::CommonCase) => 1 << 33,
137                Some(BenchmarkCase::WorstCase) => 1 << 63,
138                None => rng.random(),
139            };
140
141            self.set_up_initial_state(rng.random(), leaf_index)
142        }
143    }
144
145    #[test]
146    fn unit() {
147        ShadowedReadOnlyAlgorithm::new(MerkleStepMemU64Index).test();
148    }
149}
150
151#[cfg(test)]
152mod benches {
153    use super::*;
154    use crate::test_prelude::*;
155
156    #[test]
157    fn benchmark() {
158        ShadowedReadOnlyAlgorithm::new(MerkleStepMemU64Index).bench();
159    }
160}
tasm_lib/hashing/merkle_step_mem_u64_index.rs

tasm_lib/hashing/
merkle_step_mem_u64_index.rs
