tasm_lib/mmr/
verify_mmr_successor.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4use twenty_first::util_types::mmr::mmr_accumulator::MmrAccumulator;
5use twenty_first::util_types::mmr::mmr_successor_proof::MmrSuccessorProof;
6
7use crate::arithmetic::u64 as u64_lib;
8use crate::hashing::merkle_step_mem_u64_index::MerkleStepMemU64Index;
9use crate::hashing::merkle_step_u64_index::MerkleStepU64Index;
10use crate::mmr::leaf_index_to_mt_index_and_peak_index::MmrLeafIndexToMtIndexAndPeakIndex;
11use crate::prelude::*;
12use crate::traits::basic_snippet::Reviewer;
13use crate::traits::basic_snippet::SignOffFingerprint;
14
15/// Verify that one MMR is a successor to another.
16///
17/// Verify the successorship relation between two MMRs. A [`MmrSuccessorProof`]
18/// is necessary to demonstrate this relation, but it is not a *stack* argument
19/// because this algorithm obtains the relevant info (authentication paths) from
20/// nondeterminism. Accordingly, nondeterminism must be [initialized] correctly with
21/// the `MmrSuccessorProof`.
22///
23/// The snippet crashes if the relation does not hold, or if the proof is invalid.
24///
25/// ### Behavior
26///
27/// ```text
28/// BEFORE: _ *old_mmr *new_mmr
29/// AFTER:  _
30/// ```
31///
32/// ### Preconditions
33///
34/// None.
35///
36/// ### Postconditions
37///
38/// - the `new_mmr` is a successor of the `old_mmr`
39///
40/// [initialized]: VerifyMmrSuccessor::update_nondeterminism
41#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)]
42pub struct VerifyMmrSuccessor;
43
44impl VerifyMmrSuccessor {
45    pub(crate) const OLD_HAS_MORE_LEAFS_THAN_NEW_ERROR_ID: i128 = 150;
46    pub(crate) const INCONSISTENT_OLD_MMR_ERROR_ID: i128 = 151;
47    pub(crate) const INCONSISTENT_NEW_MMR_ERROR_ID: i128 = 152;
48    pub(crate) const DIFFERING_SHARED_PEAK_ERROR_ID: i128 = 153;
49    pub(crate) const DIFFERING_UNSHARED_PEAK_ERROR_ID: i128 = 154;
50}
51
52impl BasicSnippet for VerifyMmrSuccessor {
53    fn inputs(&self) -> Vec<(DataType, String)> {
54        ["*old_mmr", "*new_mmr"]
55            .map(|ptr_name| (DataType::VoidPointer, ptr_name.to_string()))
56            .to_vec()
57    }
58
59    fn outputs(&self) -> Vec<(DataType, String)> {
60        vec![]
61    }
62
63    fn entrypoint(&self) -> String {
64        "tasm_lib_mmr_verify_mmr_successor".to_string()
65    }
66
67    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
68        let sub_u64 = library.import(Box::new(u64_lib::sub::Sub));
69        let lt_u64 = library.import(Box::new(u64_lib::lt::Lt));
70        let popcount_u64 = library.import(Box::new(u64_lib::popcount::PopCount));
71        let trailing_zeros_u64 = library.import(Box::new(u64_lib::trailing_zeros::TrailingZeros));
72        let shl_u64 = library.import(Box::new(u64_lib::shift_left::ShiftLeft));
73        let shr_u64 = library.import(Box::new(u64_lib::shift_right::ShiftRight));
74
75        let leaf_index_to_mti_and_pki = library.import(Box::new(MmrLeafIndexToMtIndexAndPeakIndex));
76        let merkle_step_u64 = library.import(Box::new(MerkleStepU64Index));
77        let merkle_step_mem_u64 = library.import(Box::new(MerkleStepMemU64Index));
78
79        let entrypoint = self.entrypoint();
80        let clean_up_because_old_mmr_has_0_leafs =
81            format!("{entrypoint}_clean_up_because_old_mmr_has_0_leafs");
82        let assert_mmr_equality = format!("{entrypoint}_assert_mmr_equality");
83        let assert_unchanged_peaks_equality =
84            format!("{entrypoint}_assert_unchanged_peaks_equality");
85        let clean_up_because_new_leafs_dont_affect_old_peaks =
86            format!("{entrypoint}_clean_up_because_new_leafs_dont_affect_old_peaks");
87        let traverse_new_tree = format!("{entrypoint}_traverse_new_tree");
88        let traverse_new_tree_right_sibling = format!("{traverse_new_tree}_right_sibling");
89
90        triton_asm! {
91            // BEFORE: _ *old *new
92            // AFTER:  _
93            {entrypoint}:
94                /* consistent old MMR? */
95                pick 1
96                {&MmrAccumulator::destructure()}
97                    hint old_num_leafs: Pointer = stack[0]
98                    hint old_peaks: Pointer = stack[1]
99                // _ *new *old_peaks *old_num_leafs
100
101                addi 1
102                read_mem 2 hint old_num_leafs: u64 = stack[1..3]
103                pop 1
104                // _ *new *old_peaks [old_num_leafs: u64]
105
106                pick 2
107                read_mem 1 hint old_peaks_len = stack[1]
108                addi 1
109                place 1
110                // _ *new [old_num_leafs: u64] *old_peaks old_peaks_len
111
112                dup 3 dup 3
113                call {popcount_u64}
114                // _ *new [old_num_leafs: u64] *old_peaks old_peaks_len (popcount of old_num_leafs)
115
116                eq assert error_id {Self::INCONSISTENT_OLD_MMR_ERROR_ID}
117                // _ *new [old_num_leafs: u64] *old_peaks
118
119                /* consistent new MMR? */
120                pick 3
121                {&MmrAccumulator::destructure()}
122                    hint new_num_leafs: Pointer = stack[0]
123                    hint new_peaks: Pointer = stack[1]
124                // _ [old_num_leafs: u64] *old_peaks *new_peaks *new_num_leafs
125
126                addi 1
127                read_mem 2 hint new_num_leafs: u64 = stack[1..3]
128                pop 1
129                // _ [old_num_leafs: u64] *old_peaks *new_peaks [new_num_leafs: u64]
130
131                pick 2
132                read_mem 1 hint new_peaks_len = stack[1]
133                addi 1
134                place 1
135                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks new_peaks_len
136
137                dup 3 dup 3
138                call {popcount_u64}
139                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks new_peaks_len (popcount of new_num_leafs)
140
141                eq assert error_id {Self::INCONSISTENT_NEW_MMR_ERROR_ID}
142                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks
143
144                /* edge case: old MMR has 0 leafs – nothing to verify */
145                push 0
146                dup 6 dup 6
147                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks 0 [old_num_leafs: u64]
148
149                push 0 push 0 hint zero: u64 = stack[0..2]
150                {&DataType::U64.compare()}
151                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks 0 (old_num_leafs == 0)
152
153                skiz call {clean_up_because_old_mmr_has_0_leafs}
154                skiz return
155                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks
156
157                /* edge case: old and new MMRs have the same number of leafs
158                 * Check equality of peaks. Treated separately to simplify nominal case.
159                 */
160                push 0
161                dup 6 dup 6
162                dup 5 dup 5
163                {&DataType::U64.compare()}
164                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks 0 (old_num_leafs == new_num_leafs)
165
166                skiz call {assert_mmr_equality}
167                skiz return
168                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks
169
170                /* crash if num_old_leafs > num_new_leafs */
171                dup 5 dup 5
172                dup 4 dup 4
173                call {lt_u64}
174                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks (new_num_leafs < old_num_leafs)
175
176                push 0 eq
177                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks (new_num_leafs >= old_num_leafs)
178
179                assert error_id {Self::OLD_HAS_MORE_LEAFS_THAN_NEW_ERROR_ID}
180                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks
181
182                /* nominal case */
183                dup 2 dup 2
184                dup 7 dup 7
185                //  _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks [new_num_leafs: u64] [old_num_leafs: u64]
186
187                call {leaf_index_to_mti_and_pki}    hint num_unchanged_peaks = stack[0]
188                                                    hint merkle_tree_idx: u64 = stack[1..3]
189                // _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks [mt_index: u64] num_unchanged_peaks
190
191                pick 2 pick 2
192                place 8 place 8
193                // _ [mt_index: u64] [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks num_unchanged_peaks
194
195                pick 4
196                read_mem 1
197                addi 2
198                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *new_peaks num_unchanged_peaks old_num_peaks *old_peaks[0]
199
200                pick 1
201                addi -1
202                push {Digest::LEN}
203                mul
204                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *new_peaks num_unchanged_peaks *old_peaks[0] (old_num_peaks-1)*DIGEST_LENGTH
205
206                dup 1
207                add hint last_old_peak: Pointer = stack[0]
208                place 1
209                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *new_peaks num_unchanged_peaks *old_peaks[-1] *old_peaks[0]
210
211                pick 3
212                addi 1
213                pick 3
214                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *old_peaks[-1] *old_peaks[0] *new_peaks[0] num_unchanged_peaks
215
216                call {assert_unchanged_peaks_equality}
217                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *old_peaks[-1] *old_peaks[i] *new_peaks[i] 0
218
219                pick 2
220                pop 2
221                // _ [mt_index: u64] [old_num_leafs: u64] [new_num_leafs: u64] *old_peaks[-1] *new_peaks[i]
222
223                place 5
224                place 5
225                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] [old_num_leafs: u64] [new_num_leafs: u64]
226
227                dup 3 dup 3
228                call {trailing_zeros_u64} hint height_of_lowest_old_peak = stack[0]
229                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] [old_num_leafs: u64] [new_num_leafs: u64] height_of_lowest_old_peak
230
231                push 0 push 1 hint one: u64 = stack[0..2]
232                dup 2
233                call {shl_u64} hint num_leafs_in_lowest_old_peak: u64 = stack[0..2]
234                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] [old_num_leafs: u64] [new_num_leafs: u64] height_of_lowest_old_peak [num_leafs_in_lowest_old_peak: u64]
235
236                pick 6 pick 6
237                pick 6 pick 6
238                call {sub_u64}
239                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] height_of_lowest_old_peak [num_leafs_in_lowest_old_peak: u64] [num_new_leafs: u64]
240
241                call {lt_u64}
242                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] height_of_lowest_old_peak (num_new_leafs < num_leafs_in_lowest_old_peak)
243
244                push 0
245                place 1
246                skiz call {clean_up_because_new_leafs_dont_affect_old_peaks}
247                skiz return
248                // _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] height_of_lowest_old_peak
249
250                pick 4 pick 4
251                pick 2
252                // _ *old_peaks[-1] *new_peaks[i] [mt_index: u64] height_of_lowest_old_peak
253
254                call {shr_u64} hint merkle_tree_idx: u64 = stack[0..2]
255                // _ *old_peaks[-1] *new_peaks[i] [mt_index: u64]
256
257                pick 2
258                place 3
259                divine 5
260                // _ *new_peaks[i] *old_peaks[-1] [mt_index: u64] [current_node: Digest]
261
262                call {traverse_new_tree}
263                // _ *new_peaks[i] *old_peaks[j] [one: u64] [root: Digest]
264
265                pick 8
266                addi {Digest::LEN - 1}
267                read_mem {Digest::LEN}
268                pop 1
269                // _ *old_peaks[j] [one: u64] [root: Digest] [new_peak[i]: Digest]
270
271                assert_vector error_id {Self::DIFFERING_UNSHARED_PEAK_ERROR_ID}
272                pop 5
273                // _ *old_peaks[j] [one: u64]
274
275                pop 3
276                return
277
278            // BEFORE: _ [old_num_leafs: u64] *old_peaks [new_num_leafs: u64] *new_peaks 0
279            // AFTER:  _ 1
280            {clean_up_because_old_mmr_has_0_leafs}:
281                pop 5
282                pop 2
283                push 1
284                return
285
286            // BEFORE: _ [num_leafs: u64] *old_peaks [num_leafs: u64] *new_peaks 0
287            // AFTER:  _ 1
288            {assert_mmr_equality}:
289                pick 4
290                addi 1
291                // _ [num_leafs: u64] [num_leafs: u64] *new_peaks 0 *old_peaks[0]
292
293                pick 2
294                addi 1
295                // _ [num_leafs: u64] [num_leafs: u64] 0 *old_peaks[0] *new_peaks[0]
296
297                pick 4 pick 4
298                call {popcount_u64}
299                // _ [num_leafs: u64] 0 *old_peaks[0] *new_peaks[0] num_peaks
300
301                call {assert_unchanged_peaks_equality}
302                // _ [num_leafs: u64] 0 *old_peaks[n] *new_peaks[n] 0
303
304                pop 5
305                pop 1
306                push 1
307                return
308
309            // BEFORE:    _ *old_peaks[0] *new_peaks[0] n
310            // INVARIANT: _ *old_peaks[i] *new_peaks[i] (n - i)
311            // AFTER:     _ *old_peaks[n] *new_peaks[n] 0
312            {assert_unchanged_peaks_equality}:
313                dup 0
314                push 0
315                eq
316                skiz return
317                // _ *old_peaks[i] *new_peaks[i] (n - i)
318
319                pick 2
320                addi {Digest::LEN - 1}
321                read_mem {Digest::LEN}
322                addi {Digest::LEN + 1}
323                place 7
324                // _ *old_peaks[i + 1] *new_peaks[i] (n - i) [old_peak[i]: Digest]
325
326                pick 6
327                addi {Digest::LEN - 1}
328                read_mem {Digest::LEN}
329                addi {Digest::LEN + 1}
330                place 11
331                // _ *old_peaks[i + 1] *new_peaks[i + 1] (n - i) [old_peak[i]: Digest] [new_peak[i]: Digest]
332
333                assert_vector error_id {Self::DIFFERING_SHARED_PEAK_ERROR_ID}
334                pop 5
335                // _ *old_peaks[i + 1] *new_peaks[i + 1] (n - i)
336
337                addi -1
338                recurse
339
340            // BEFORE: _ [mt_index: u64] *old_peaks[-1] *new_peaks[i] height_of_lowest_old_peak 0
341            // AFTER:  _ 1
342            {clean_up_because_new_leafs_dont_affect_old_peaks}:
343                pop 5
344                pop 1
345                push 1
346                return
347
348            // INVARIANT: _ *old_peaks[j] [mt_index >> i: u64] [current_node: Digest]
349            {traverse_new_tree}:
350                dup 6 dup 6
351                push 0 push 1 hint merkle_tree_root_index: u64 = stack[0..2]
352                {&DataType::U64.compare()}
353                skiz return
354                // _ *old_peaks[j] [mt_index >> i: u64] [current_node: Digest]
355
356                push 1
357                dup 6
358                push 1
359                and
360                // _ *old_peaks[j] [mt_index >> i: u64] [current_node: Digest] 1 is_right_sibling
361
362                skiz call {traverse_new_tree_right_sibling}
363                skiz call {merkle_step_u64}
364                // _ *old_peaks[j'] [mt_index >> (i + 1): u64] [next_node: Digest]
365
366                recurse
367
368            // BEFORE: _ *old_peaks[j]   [mt_index >> i: u64]       [current_node: Digest] 1
369            // AFTER:  _ *old_peaks[j-1] [mt_index >> (i + 1): u64] [next_node: Digest]    0
370            {traverse_new_tree_right_sibling}:
371                pop 1
372                call {merkle_step_mem_u64}
373                // _ *old_peaks[j+1] [mt_index >> (i + 1): u64] [next_node: Digest]
374
375                pick 7
376                addi -10 // -(2 · Digest::LEN)
377                place 7
378                // _ *old_peaks[j-1] [mt_index >> (i + 1): u64] [next_node: Digest]
379
380                push 0
381                return
382        }
383    }
384
385    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
386        let mut sign_offs = HashMap::new();
387        sign_offs.insert(Reviewer("ferdinand"), 0xeb1e81bd042d7a0c.into());
388        sign_offs.insert(Reviewer("alan"), 0xeb1e81bd042d7a0c.into());
389        sign_offs
390    }
391}
392
393impl VerifyMmrSuccessor {
394    /// Update a nondeterminism in accordance with verifying a given [`MmrSuccessorProof`]
395    /// with this snippet.
396    pub fn update_nondeterminism(
397        nondeterminism: &mut NonDeterminism,
398        mmr_successor_proof: &MmrSuccessorProof,
399    ) {
400        let mut auth_path = mmr_successor_proof.paths.iter();
401        if let Some(&first) = auth_path.next() {
402            nondeterminism
403                .individual_tokens
404                .extend(first.reversed().values());
405            nondeterminism.digests.extend(auth_path);
406        };
407    }
408}
409
410#[cfg(test)]
411mod tests {
412    use std::collections::VecDeque;
413
414    use twenty_first::util_types::mmr::mmr_accumulator::MmrAccumulator;
415    use twenty_first::util_types::mmr::mmr_successor_proof::MmrSuccessorProof;
416
417    use super::*;
418    use crate::empty_stack;
419    use crate::test_prelude::*;
420    use crate::twenty_first::prelude::Mmr;
421
422    impl ReadOnlyAlgorithm for VerifyMmrSuccessor {
423        fn rust_shadow(
424            &self,
425            stack: &mut Vec<BFieldElement>,
426            memory: &HashMap<BFieldElement, BFieldElement>,
427            nd_tokens: VecDeque<BFieldElement>,
428            nd_digests: VecDeque<Digest>,
429        ) {
430            let new_mmr_pointer = stack.pop().unwrap();
431            let old_mmr_pointer = stack.pop().unwrap();
432
433            let new_mmr = *MmrAccumulator::decode_from_memory(memory, new_mmr_pointer).unwrap();
434            let old_mmr = *MmrAccumulator::decode_from_memory(memory, old_mmr_pointer).unwrap();
435
436            // figure out the length of the authentication path
437            let num_new_leafs = new_mmr.num_leafs() - old_mmr.num_leafs();
438            let new_dummy_leafs = vec![Digest::default(); num_new_leafs.try_into().unwrap()];
439            let dummy_proof = MmrSuccessorProof::new_from_batch_append(&old_mmr, &new_dummy_leafs);
440            let auth_path_len = dummy_proof.paths.len();
441
442            // grab first path element from nd tokens
443            let mut path = vec![];
444            if auth_path_len > 0 {
445                let first_element = (0..Digest::LEN).rev().map(|i| nd_tokens[i]).collect_vec();
446                path.push(Digest::new(first_element.try_into().unwrap()));
447            }
448
449            // grab remaining path elements from nd digests
450            if auth_path_len > 1 {
451                path.extend((0..auth_path_len - 1).map(|i| nd_digests[i]));
452            }
453
454            assert!(MmrSuccessorProof { paths: path }.verify(&old_mmr, &new_mmr));
455        }
456
457        fn pseudorandom_initial_state(
458            &self,
459            seed: [u8; 32],
460            bench_case: Option<BenchmarkCase>,
461        ) -> ReadOnlyAlgorithmInitialState {
462            let mut rng = StdRng::from_seed(seed);
463            let old_num_leafs = match bench_case {
464                Some(BenchmarkCase::CommonCase) => u32::MAX.into(),
465                Some(BenchmarkCase::WorstCase) => u64::MAX >> 2,
466                None => rng.next_u64() >> 1,
467            };
468            let old_peaks = (0..old_num_leafs.count_ones())
469                .map(|_| rng.random())
470                .collect();
471            let old = MmrAccumulator::init(old_peaks, old_num_leafs);
472
473            let num_new_leafs = match bench_case {
474                Some(BenchmarkCase::CommonCase) => 100,
475                Some(BenchmarkCase::WorstCase) => 1000,
476                None => 1 << rng.random_range(0..5),
477            };
478            let new_leafs = (0..num_new_leafs).map(|_| rng.random()).collect_vec();
479            let proof = MmrSuccessorProof::new_from_batch_append(&old, &new_leafs);
480
481            let mut new = old.clone();
482            for leaf in new_leafs {
483                new.append(leaf);
484            }
485
486            initial_state(&old, &new, &proof)
487        }
488
489        fn corner_case_initial_states(&self) -> Vec<ReadOnlyAlgorithmInitialState> {
490            let mut rng = rand::rng();
491            let mut initial_states = vec![];
492
493            for (num_old_leafs, num_inserted_leafs) in [0_u64, 1, 2, 3, 4, 8]
494                .into_iter()
495                .cartesian_product([0, 1, 2, 3, 4, 8])
496            {
497                let old_peaks = (0..num_old_leafs.count_ones())
498                    .map(|_| rng.random())
499                    .collect();
500                let old = MmrAccumulator::init(old_peaks, num_old_leafs);
501
502                let mut new = old.clone();
503                let new_leafs = (0..num_inserted_leafs).map(|_| rng.random()).collect_vec();
504                for &leaf in &new_leafs {
505                    new.append(leaf);
506                }
507                let proof = MmrSuccessorProof::new_from_batch_append(&old, &new_leafs);
508
509                initial_states.push(initial_state(&old, &new, &proof));
510            }
511
512            initial_states
513        }
514    }
515
516    fn initial_state(
517        old: &MmrAccumulator,
518        new: &MmrAccumulator,
519        proof: &MmrSuccessorProof,
520    ) -> ReadOnlyAlgorithmInitialState {
521        let Digest(seed) = Tip5::hash_pair(Tip5::hash(old), Tip5::hash(new));
522        let seed = seed
523            .into_iter()
524            .flat_map(|bfe| bfe.raw_bytes())
525            .take(32)
526            .collect_vec();
527        let mut rng = StdRng::from_seed(seed.try_into().unwrap());
528
529        let address_for_old = bfe!(rng.random_range(0_u32..1 << 30));
530        let address_for_new =
531            address_for_old + bfe!(old.encode().len()) + bfe!(rng.random_range(0_u32..1 << 28));
532
533        let mut nondeterminism = NonDeterminism::default();
534        VerifyMmrSuccessor::update_nondeterminism(&mut nondeterminism, proof);
535        encode_to_memory(&mut nondeterminism.ram, address_for_old, old);
536        encode_to_memory(&mut nondeterminism.ram, address_for_new, new);
537
538        let mut stack = empty_stack();
539        stack.push(address_for_old);
540        stack.push(address_for_new);
541
542        ReadOnlyAlgorithmInitialState {
543            stack,
544            nondeterminism,
545        }
546    }
547
548    fn failing_initial_states() -> Vec<ReadOnlyAlgorithmInitialState> {
549        let one_leaf = MmrAccumulator::new_from_leafs(vec![Digest::default()]);
550        let empty = MmrAccumulator::new_from_leafs(vec![]);
551        let bogus_proof = MmrSuccessorProof { paths: vec![] };
552        let mut initial_states = vec![initial_state(&one_leaf, &empty, &bogus_proof)];
553
554        let mut rng = StdRng::seed_from_u64(0x18c78fc35da66859);
555        for (old_num_leafs, new_num_leafs) in
556            [1_u64, 2, 3, 8].into_iter().cartesian_product([0, 1, 8])
557        {
558            let old_peaks = (0..old_num_leafs.count_ones())
559                .map(|_| rng.random())
560                .collect();
561            let old = MmrAccumulator::init(old_peaks, old_num_leafs);
562
563            let new_leafs = (0..new_num_leafs).map(|_| rng.random()).collect_vec();
564            let mut new_mmr = old.clone();
565            for &leaf in &new_leafs {
566                new_mmr.append(leaf);
567            }
568            let new = new_mmr;
569            let proof = MmrSuccessorProof::new_from_batch_append(&old, &new_leafs);
570
571            let wrong_old = MmrAccumulator::init(old.peaks(), old.num_leafs().rotate_left(1));
572            initial_states.push(initial_state(&wrong_old, &new, &proof));
573
574            let wrong_new = MmrAccumulator::init(new.peaks(), new.num_leafs().rotate_left(1));
575            initial_states.push(initial_state(&old, &wrong_new, &proof));
576
577            let mut wrong_new_peaks = new.peaks();
578            wrong_new_peaks.push(rng.random());
579            let too_many_peaks_new = MmrAccumulator::init(wrong_new_peaks, new.num_leafs());
580            initial_states.push(initial_state(&old, &too_many_peaks_new, &proof));
581
582            for peak_idx in 0..old.peaks().len() {
583                let mut wrong_old_peaks = old.peaks();
584                let Digest(ref mut digest_to_disturb) = wrong_old_peaks[peak_idx];
585                let digest_to_disturb_innards_idx = rng.random_range(0..Digest::LEN);
586                digest_to_disturb[digest_to_disturb_innards_idx].increment();
587
588                let wrong_old = MmrAccumulator::init(wrong_old_peaks, old.num_leafs());
589                initial_states.push(initial_state(&wrong_old, &new, &proof));
590            }
591
592            for proof_path_idx in 0..proof.paths.len() {
593                let mut wrong_proof = proof.clone();
594                let proof_paths = &mut wrong_proof.paths;
595                let Digest(ref mut digest_to_disturb) = proof_paths[proof_path_idx];
596                let digest_to_disturb_innards_idx = rng.random_range(0..Digest::LEN);
597                digest_to_disturb[digest_to_disturb_innards_idx].increment();
598
599                initial_states.push(initial_state(&old, &new, &wrong_proof));
600            }
601        }
602
603        // the secret input being underpopulated is no acceptable failure reason
604        for state in &mut initial_states {
605            let non_determinism = &mut state.nondeterminism;
606            non_determinism.individual_tokens.extend(bfe_array![0; 5]);
607            non_determinism.digests.extend([Digest::default(); 1000]);
608        }
609
610        initial_states
611    }
612
613    #[test]
614    fn unit() {
615        ShadowedReadOnlyAlgorithm::new(VerifyMmrSuccessor).test();
616    }
617
618    #[test]
619    fn verify_mmr_successor_negative_test() {
620        let all_error_ids = [
621            VerifyMmrSuccessor::OLD_HAS_MORE_LEAFS_THAN_NEW_ERROR_ID,
622            VerifyMmrSuccessor::INCONSISTENT_OLD_MMR_ERROR_ID,
623            VerifyMmrSuccessor::INCONSISTENT_NEW_MMR_ERROR_ID,
624            VerifyMmrSuccessor::DIFFERING_SHARED_PEAK_ERROR_ID,
625            VerifyMmrSuccessor::DIFFERING_UNSHARED_PEAK_ERROR_ID,
626        ];
627
628        for (i, init_state) in failing_initial_states().into_iter().enumerate() {
629            dbg!(i);
630            test_assertion_failure(
631                &ShadowedReadOnlyAlgorithm::new(VerifyMmrSuccessor),
632                init_state.into(),
633                &all_error_ids,
634            );
635        }
636    }
637}
638
639#[cfg(test)]
640mod bench {
641    use super::*;
642    use crate::test_prelude::*;
643
644    #[test]
645    fn benchmark() {
646        ShadowedReadOnlyAlgorithm::new(VerifyMmrSuccessor).bench();
647    }
648}
tasm_lib/mmr/verify_mmr_successor.rs

tasm_lib/mmr/
verify_mmr_successor.rs
