tasm_lib/hashing/
merkle_step_u64_index.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::prelude::*;
6use crate::traits::basic_snippet::Reviewer;
7use crate::traits::basic_snippet::SignOffFingerprint;
8
9/// Like instruction `merkle_step`, but for index of type `u64` instead of the
10/// native `u32`.
11///
12/// ### Behavior
13///
14/// ```text
15/// BEFORE: _ [merkle_tree_node_index: u64] [node: Digest]
16/// AFTER:  _ [merkle_tree_parent_node_index: u64] [parent_node: Digest]
17/// ```
18///
19/// ### Preconditions
20///
21/// - all input arguments are properly [`BFieldCodec`] encoded
22///
23/// ### Postconditions
24///
25/// - all output is properly [`BFieldCodec`] encoded
26#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
27pub struct MerkleStepU64Index;
28
29impl MerkleStepU64Index {
30    /// Make a Merkle tree index of type `u64` consistent after having performed a
31    /// Triton-VM-native `merkle_step` instruction.
32    ///
33    /// ```text
34    /// BEFORE: _ mt_index_hi       (mt_index_lo / 2) [node: Digest]
35    /// AFTER:  _ (mt_index / 2)_hi (mt_index / 2)_lo [node: Digest]
36    /// ```
37    pub(super) fn make_u64_index_consistent() -> Vec<LabelledInstruction> {
38        triton_asm! {
39            push 2      // _ mt_index_hi (mt_index_lo / 2) [digest; 5] 2
40            pick 7      // _ (mt_index_lo / 2) [digest; 5] 2 mt_index_hi
41            div_mod     // _ (mt_index_lo / 2) [digest; 5] (mt_index_hi / 2) (mt_index_hi % 2)
42                        // _ (mt_index_lo / 2) [digest; 5] (mt_index / 2)_hi (mt_index_hi % 2)
43            push {1u32 << 31}
44            hint two_pow_31: u32 = stack[0]
45            mul         // _ (mt_index_lo / 2) [digest; 5] (mt_index / 2)_hi carry
46            hint carry: u32 = stack[0]
47            pick 7      // _ [digest; 5] (mt_index / 2)_hi carry (mt_index_lo / 2)
48            add         // _ [digest; 5] (mt_index / 2)_hi (mt_index / 2)_lo
49            place 6     // _ (mt_index / 2)_lo [digest; 5] (mt_index / 2)_hi
50            place 6     // _ (mt_index / 2)_hi (mt_index / 2)_lo [digest; 5]
51        }
52    }
53}
54
55impl BasicSnippet for MerkleStepU64Index {
56    fn inputs(&self) -> Vec<(DataType, String)> {
57        vec![
58            (DataType::U64, "merkle tree node index".to_owned()),
59            (DataType::Digest, "node".to_owned()),
60        ]
61    }
62
63    fn outputs(&self) -> Vec<(DataType, String)> {
64        vec![
65            (DataType::U64, "merkle tree parent node index".to_owned()),
66            (DataType::Digest, "parent node".to_owned()),
67        ]
68    }
69
70    fn entrypoint(&self) -> String {
71        "tasmlib_hashing_merkle_step_u64_index".to_owned()
72    }
73
74    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
75        triton_asm!(
76            {self.entrypoint()}:
77                merkle_step
78                // _ mt_index_hi (mt_index_lo / 2) [parent_node: Digest]
79
80                {&Self::make_u64_index_consistent()}
81                // _ (mt_index / 2)_hi (mt_index / 2)_lo [parent_node: Digest]
82
83                return
84        )
85    }
86
87    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
88        let mut sign_offs = HashMap::new();
89        sign_offs.insert(Reviewer("ferdinand"), 0xe123f6c5f6456a8d.into());
90        sign_offs
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use std::collections::VecDeque;
97
98    use super::*;
99    use crate::test_prelude::*;
100
101    impl MerkleStepU64Index {
102        fn set_up_initial_state(&self, leaf_index: u64) -> ReadOnlyAlgorithmInitialState {
103            let mut stack = self.init_stack_for_isolated_run();
104            push_encodable(&mut stack, &leaf_index);
105            push_encodable(&mut stack, &rand::random::<Digest>());
106
107            ReadOnlyAlgorithmInitialState {
108                stack,
109                nondeterminism: NonDeterminism::default().with_digests(vec![rand::random()]),
110            }
111        }
112    }
113
114    impl ReadOnlyAlgorithm for MerkleStepU64Index {
115        fn rust_shadow(
116            &self,
117            stack: &mut Vec<BFieldElement>,
118            _: &HashMap<BFieldElement, BFieldElement>,
119            _: VecDeque<BFieldElement>,
120            nd_digests: VecDeque<Digest>,
121        ) {
122            let stack_digest = pop_encodable::<Digest>(stack);
123            let leaf_index = pop_encodable::<u64>(stack);
124
125            let stack_digest_is_left_sibling = leaf_index % 2 == 0;
126            let (left_digest, right_digest) = if stack_digest_is_left_sibling {
127                (stack_digest, nd_digests[0])
128            } else {
129                (nd_digests[0], stack_digest)
130            };
131
132            let parent_digest = Tip5::hash_pair(left_digest, right_digest);
133            let parent_index = leaf_index / 2;
134
135            push_encodable(stack, &parent_index);
136            push_encodable(stack, &parent_digest);
137        }
138
139        fn pseudorandom_initial_state(
140            &self,
141            seed: [u8; 32],
142            bench_case: Option<BenchmarkCase>,
143        ) -> ReadOnlyAlgorithmInitialState {
144            let leaf_index = match bench_case {
145                Some(BenchmarkCase::CommonCase) => 1 << 33,
146                Some(BenchmarkCase::WorstCase) => 1 << 63,
147                None => StdRng::from_seed(seed).random(),
148            };
149
150            self.set_up_initial_state(leaf_index)
151        }
152    }
153
154    #[test]
155    fn rust_shadow() {
156        ShadowedReadOnlyAlgorithm::new(MerkleStepU64Index).test();
157    }
158
159    #[test]
160    fn unit_test() {
161        fn assert_expected_behavior(mt_index: u64, expected_parent_index: u64) {
162            let initial_state = MerkleStepU64Index.set_up_initial_state(mt_index);
163            let final_state = crate::test_helpers::tasm_final_state(
164                &ShadowedReadOnlyAlgorithm::new(MerkleStepU64Index),
165                &initial_state.stack,
166                &[],
167                initial_state.nondeterminism,
168                &None,
169            );
170
171            let mut final_stack = final_state.op_stack.stack;
172            let _ = pop_encodable::<Digest>(&mut final_stack);
173            let calculated_parent_index = pop_encodable::<u64>(&mut final_stack);
174
175            assert_eq!(expected_parent_index, calculated_parent_index);
176            assert_eq!(mt_index / 2, calculated_parent_index);
177        }
178
179        assert_expected_behavior(0, 0);
180        assert_expected_behavior(1, 0);
181        assert_expected_behavior(2, 1);
182        assert_expected_behavior(3, 1);
183        assert_expected_behavior(4, 2);
184        assert_expected_behavior(1 << 32, 1 << 31);
185        assert_expected_behavior(1 << 33, 1 << 32);
186        assert_expected_behavior(1 << 34, 1 << 33);
187        assert_expected_behavior(0b101 << 32, 0b101 << 31);
188        assert_expected_behavior(u64::MAX, (1 << 63) - 1);
189    }
190}
191
192#[cfg(test)]
193mod benches {
194    use super::*;
195    use crate::test_prelude::*;
196
197    #[test]
198    fn benchmark() {
199        ShadowedReadOnlyAlgorithm::new(MerkleStepU64Index).bench();
200    }
201}
tasm_lib/hashing/merkle_step_u64_index.rs

tasm_lib/hashing/
merkle_step_u64_index.rs
