snarkvm_ledger_puzzle/
lib.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16#![forbid(unsafe_code)]
17#![allow(clippy::too_many_arguments)]
18#![warn(clippy::cast_possible_truncation)]
19
20extern crate snarkvm_console as console;
21
22mod partial_solution;
23pub use partial_solution::*;
24
25mod solution;
26pub use solution::*;
27
28mod solution_id;
29pub use solution_id::*;
30
31mod solutions;
32pub use solutions::*;
33
34use console::{
35    account::Address,
36    algorithms::Sha3_256,
37    collections::kary_merkle_tree::KaryMerkleTree,
38    prelude::{
39        FromBits,
40        Network,
41        Result,
42        anyhow,
43        bail,
44        cfg_into_iter,
45        cfg_iter,
46        cfg_keys,
47        cfg_values,
48        ensure,
49        has_duplicates,
50    },
51    types::U64,
52};
53
54use aleo_std::prelude::*;
55use core::num::NonZeroUsize;
56use indexmap::IndexMap;
57#[cfg(feature = "locktick")]
58use locktick::parking_lot::RwLock;
59use lru::LruCache;
60#[cfg(not(feature = "locktick"))]
61use parking_lot::RwLock;
62use rand::SeedableRng;
63use rand_chacha::ChaChaRng;
64use std::sync::Arc;
65
66#[cfg(not(feature = "serial"))]
67use rayon::prelude::*;
68
69/// The arity of the Merkle tree.
70const ARITY: u8 = 8;
71/// The size of the cache.
72const CACHE_SIZE: usize = 1 << 10;
73
74/// The Merkle tree for the puzzle.
75type MerkleTree = KaryMerkleTree<Sha3_256, Sha3_256, 9, { ARITY }>;
76
77/// The puzzle trait.
78pub trait PuzzleTrait<N: Network>: Send + Sync {
79    /// Initializes a new instance of the puzzle.
80    fn new() -> Self
81    where
82        Self: Sized;
83
84    /// Returns the leaves for the puzzle, given the epoch hash and seeded RNG.
85    fn to_leaves(&self, epoch_hash: N::BlockHash, rng: &mut ChaChaRng) -> Result<Vec<Vec<bool>>>;
86
87    /// Returns the batches of leaves for the puzzle, given the epoch hash and seeded RNGs.
88    fn to_all_leaves(&self, epoch_hash: N::BlockHash, rngs: Vec<ChaChaRng>) -> Result<Vec<Vec<Vec<bool>>>>;
89}
90
91#[derive(Clone)]
92pub struct Puzzle<N: Network> {
93    /// The core puzzle.
94    inner: Arc<dyn PuzzleTrait<N>>,
95    /// The LRU cache of solution IDs to proof targets.
96    proof_target_cache: Arc<RwLock<LruCache<SolutionID<N>, u64>>>,
97}
98
99impl<N: Network> Puzzle<N> {
100    /// Initializes a new puzzle instance.
101    pub fn new<P: PuzzleTrait<N> + 'static>() -> Self {
102        Self {
103            inner: Arc::new(P::new()),
104            proof_target_cache: Arc::new(RwLock::new(LruCache::new(NonZeroUsize::new(CACHE_SIZE).unwrap()))),
105        }
106    }
107
108    /// Returns the Merkle leaves for the puzzle, given the solution.
109    pub fn get_leaves(&self, solution: &PartialSolution<N>) -> Result<Vec<Vec<bool>>> {
110        // Initialize a seeded random number generator.
111        let mut rng = ChaChaRng::seed_from_u64(*solution.id());
112        // Output the leaves.
113        self.inner.to_leaves(solution.epoch_hash(), &mut rng)
114    }
115
116    /// Returns each of the Merkle leaves for the puzzle, given the solutions.
117    pub fn get_all_leaves(&self, solutions: &PuzzleSolutions<N>) -> Result<Vec<Vec<Vec<bool>>>> {
118        // Ensure all of the solutions are for the same epoch.
119        ensure!(
120            cfg_values!(solutions).all(|solution| solution.epoch_hash() == solutions[0].epoch_hash()),
121            "The solutions are for different epochs"
122        );
123        // Construct the RNGs.
124        let rngs = cfg_keys!(solutions).map(|solution_id| ChaChaRng::seed_from_u64(**solution_id)).collect::<Vec<_>>();
125        // Output the leaves.
126        self.inner.to_all_leaves(solutions[0].epoch_hash(), rngs)
127    }
128
129    /// Returns the proof target given the solution.
130    pub fn get_proof_target(&self, solution: &Solution<N>) -> Result<u64> {
131        // Calculate the proof target.
132        let proof_target = self.get_proof_target_unchecked(solution)?;
133        // Ensure the proof target matches the expected proof target.
134        ensure!(solution.target() == proof_target, "The proof target does not match the expected proof target");
135        // Return the proof target.
136        Ok(proof_target)
137    }
138
139    /// Returns the proof target given the solution.
140    ///
141    /// Note: This method does **not** check the proof target against the expected proof target.
142    pub fn get_proof_target_unchecked(&self, solution: &Solution<N>) -> Result<u64> {
143        // Calculate the proof target.
144        self.get_proof_target_from_partial_solution(solution.partial_solution())
145    }
146
147    /// Returns the proof target given the partial solution.
148    pub fn get_proof_target_from_partial_solution(&self, partial_solution: &PartialSolution<N>) -> Result<u64> {
149        // If the proof target is in the cache, then return it.
150        if let Some(proof_target) = self.proof_target_cache.write().get(&partial_solution.id()) {
151            return Ok(*proof_target);
152        }
153
154        // Construct the leaves of the Merkle tree.
155        let leaves = self.get_leaves(partial_solution)?;
156        // Get the proof target.
157        let proof_target = Self::leaves_to_proof_target(&leaves)?;
158
159        // Insert the proof target into the cache.
160        self.proof_target_cache.write().put(partial_solution.id(), proof_target);
161        // Return the proof target.
162        Ok(proof_target)
163    }
164
165    /// Returns the proof targets given the solutions.
166    pub fn get_proof_targets(&self, solutions: &PuzzleSolutions<N>) -> Result<Vec<u64>> {
167        // Initialize the list of proof targets.
168        let mut targets = vec![0u64; solutions.len()];
169
170        // Initialize a list of solutions that need to be computed for the proof target.
171        let mut to_compute = Vec::new();
172        // Iterate over the solutions.
173        for (i, (id, solution)) in solutions.iter().enumerate() {
174            // Check if the proof target is in the cache.
175            match self.proof_target_cache.write().get(id) {
176                // If the proof target is in the cache, then store it.
177                Some(proof_target) => {
178                    // Ensure that the proof target matches the expected proof target.
179                    ensure!(
180                        solution.target() == *proof_target,
181                        "The proof target does not match the cached proof target"
182                    );
183                    targets[i] = *proof_target
184                }
185                // Otherwise, add it to the list of solutions that need to be computed.
186                None => to_compute.push((i, id, *solution)),
187            }
188        }
189
190        if !to_compute.is_empty() {
191            // Construct the solutions object for those that need to be computed.
192            let solutions_subset = PuzzleSolutions::new(to_compute.iter().map(|(_, _, solution)| *solution).collect())?;
193            // Construct the leaves of the Merkle tree.
194            let leaves = self.get_all_leaves(&solutions_subset)?;
195            // Construct the Merkle roots and truncate them to a u64.
196            let targets_subset = cfg_iter!(leaves)
197                .zip(cfg_iter!(solutions_subset))
198                .map(|(leaves, (solution_id, solution))| {
199                    // Get the proof target.
200                    let proof_target = Self::leaves_to_proof_target(leaves)?;
201                    // Ensure that the proof target matches the expected proof target.
202                    ensure!(
203                        solution.target() == proof_target,
204                        "The proof target does not match the computed proof target"
205                    );
206                    // Insert the proof target into the cache.
207                    self.proof_target_cache.write().put(*solution_id, proof_target);
208                    // Return the proof target.
209                    Ok((solution_id, proof_target))
210                })
211                .collect::<Result<IndexMap<_, _>>>()?;
212
213            // Recombine the proof targets.
214            for (i, id, _) in &to_compute {
215                targets[*i] = targets_subset[id];
216            }
217        }
218
219        // Return the proof targets.
220        Ok(targets)
221    }
222
223    /// Returns the combined proof target of the solutions.
224    pub fn get_combined_proof_target(&self, solutions: &PuzzleSolutions<N>) -> Result<u128> {
225        self.get_proof_targets(solutions)?.into_iter().try_fold(0u128, |combined, proof_target| {
226            combined.checked_add(proof_target as u128).ok_or_else(|| anyhow!("Combined proof target overflowed"))
227        })
228    }
229
230    /// Returns a solution to the puzzle.
231    pub fn prove(
232        &self,
233        epoch_hash: N::BlockHash,
234        address: Address<N>,
235        counter: u64,
236        minimum_proof_target: Option<u64>,
237    ) -> Result<Solution<N>> {
238        // Construct the partial solution.
239        let partial_solution = PartialSolution::new(epoch_hash, address, counter)?;
240        // Compute the proof target.
241        let proof_target = self.get_proof_target_from_partial_solution(&partial_solution)?;
242        // Check that the minimum proof target is met.
243        if let Some(minimum_proof_target) = minimum_proof_target {
244            if proof_target < minimum_proof_target {
245                bail!("Solution was below the minimum proof target ({proof_target} < {minimum_proof_target})")
246            }
247        }
248
249        // Construct the solution.
250        Ok(Solution::new(partial_solution, proof_target))
251    }
252
253    /// Returns `Ok(())` if the solution is valid.
254    pub fn check_solution(
255        &self,
256        solution: &Solution<N>,
257        expected_epoch_hash: N::BlockHash,
258        expected_proof_target: u64,
259    ) -> Result<()> {
260        // Ensure the epoch hash matches.
261        if solution.epoch_hash() != expected_epoch_hash {
262            bail!(
263                "Solution does not match the expected epoch hash (found '{}', expected '{expected_epoch_hash}')",
264                solution.epoch_hash()
265            )
266        }
267        // Ensure the solution is greater than or equal to the expected proof target.
268        let proof_target = self.get_proof_target(solution)?;
269        if proof_target < expected_proof_target {
270            bail!("Solution does not meet the proof target requirement ({proof_target} < {expected_proof_target})")
271        }
272        Ok(())
273    }
274
275    /// ATTENTION: This function will update the target if the solution target is different from the calculated one.
276    /// Returns `Ok(())` if the solution is valid.
277    pub fn check_solution_mut(
278        &self,
279        solution: &mut Solution<N>,
280        expected_epoch_hash: N::BlockHash,
281        expected_proof_target: u64,
282    ) -> Result<()> {
283        // Ensure the epoch hash matches.
284        if solution.epoch_hash() != expected_epoch_hash {
285            bail!(
286                "Solution does not match the expected epoch hash (found '{}', expected '{expected_epoch_hash}')",
287                solution.epoch_hash()
288            )
289        }
290        // Calculate the proof target of the solution.
291        let proof_target = self.get_proof_target_unchecked(solution)?;
292
293        // Set the target with the newly calculated proof target value.
294        solution.target = proof_target;
295
296        // Ensure the solution is greater than or equal to the expected proof target.
297        if proof_target < expected_proof_target {
298            bail!("Solution does not meet the proof target requirement ({proof_target} < {expected_proof_target})")
299        }
300        Ok(())
301    }
302
303    /// Returns `Ok(())` if the solutions are valid.
304    pub fn check_solutions(
305        &self,
306        solutions: &PuzzleSolutions<N>,
307        expected_epoch_hash: N::BlockHash,
308        expected_proof_target: u64,
309    ) -> Result<()> {
310        let timer = timer!("Puzzle::verify");
311
312        // Ensure the solutions are not empty.
313        ensure!(!solutions.is_empty(), "The solutions are empty");
314        // Ensure the number of solutions does not exceed `MAX_SOLUTIONS`.
315        if solutions.len() > N::MAX_SOLUTIONS {
316            bail!("Exceed the maximum number of solutions ({} > {})", solutions.len(), N::MAX_SOLUTIONS)
317        }
318        // Ensure the solution IDs are unique.
319        if has_duplicates(solutions.solution_ids()) {
320            bail!("The solutions contain duplicate solution IDs");
321        }
322        lap!(timer, "Perform initial checks");
323
324        // Ensure the epoch hash matches.
325        cfg_iter!(solutions).try_for_each(|(solution_id, solution)| {
326            if solution.epoch_hash() != expected_epoch_hash {
327                bail!("Solution '{solution_id}' did not match the expected epoch hash (found '{}', expected '{expected_epoch_hash}')", solution.epoch_hash())
328            }
329            Ok(())
330        })?;
331        lap!(timer, "Verify each epoch hash matches");
332
333        // Ensure the solutions meet the proof target requirement.
334        cfg_into_iter!(self.get_proof_targets(solutions)?).enumerate().try_for_each(|(i, proof_target)| {
335            if proof_target < expected_proof_target {
336                bail!(
337                    "Solution '{:?}' did not meet the proof target requirement ({proof_target} < {expected_proof_target})",
338                    solutions.get_index(i).map(|(id, _)| id)
339                )
340            }
341            Ok(())
342        })?;
343        finish!(timer, "Verify each solution");
344        Ok(())
345    }
346
347    /// A helper function that takes leaves of a Merkle tree and returns the proof target.
348    fn leaves_to_proof_target(leaves: &[Vec<bool>]) -> Result<u64> {
349        // Construct the Merkle tree.
350        let merkle_tree = MerkleTree::new(&Sha3_256::default(), &Sha3_256::default(), leaves)?;
351        // Retrieve the Merkle tree root.
352        let root = merkle_tree.root();
353        // Truncate to a u64.
354        match *U64::<N>::from_bits_be(&root[0..64])? {
355            0 => Ok(u64::MAX),
356            value => Ok(u64::MAX / value),
357        }
358    }
359}
360
361#[cfg(test)]
362mod tests {
363    use super::*;
364    use console::{
365        account::{Address, PrivateKey},
366        network::Network,
367        prelude::{FromBytes, TestRng, ToBits as TBits, ToBytes, Uniform},
368        types::Field,
369    };
370
371    use anyhow::Result;
372    use core::marker::PhantomData;
373    use rand::{CryptoRng, Rng, RngCore, SeedableRng};
374    use rand_chacha::ChaChaRng;
375
376    type CurrentNetwork = console::network::MainnetV0;
377
378    const ITERATIONS: u64 = 100;
379
380    pub struct SimplePuzzle<N: Network>(PhantomData<N>);
381
382    impl<N: Network> PuzzleTrait<N> for SimplePuzzle<N> {
383        /// Initializes a new instance of the puzzle.
384        fn new() -> Self {
385            Self(PhantomData)
386        }
387
388        /// Returns the leaves for the puzzle, given the epoch hash and seeded RNG.
389        fn to_leaves(&self, epoch_hash: N::BlockHash, rng: &mut ChaChaRng) -> Result<Vec<Vec<bool>>> {
390            // Sample a random number of leaves.
391            let num_leaves = self.num_leaves(epoch_hash)?;
392            // Sample random field elements for each of the leaves, and convert them to bits.
393            let leaves = (0..num_leaves).map(|_| Field::<N>::rand(rng).to_bits_le()).collect::<Vec<_>>();
394            // Return the leaves.
395            Ok(leaves)
396        }
397
398        /// Returns the batches of leaves for the puzzle, given the epoch hash and seeded RNGs.
399        fn to_all_leaves(&self, epoch_hash: N::BlockHash, rngs: Vec<ChaChaRng>) -> Result<Vec<Vec<Vec<bool>>>> {
400            // Sample a random number of leaves.
401            let num_leaves = self.num_leaves(epoch_hash)?;
402            // Initialize the list of leaves.
403            let mut leaves = Vec::with_capacity(rngs.len());
404            // Construct the epoch inputs.
405            for mut rng in rngs {
406                // Sample random field elements for each of the leaves, and convert them to bits.
407                leaves.push((0..num_leaves).map(|_| Field::<N>::rand(&mut rng).to_bits_le()).collect::<Vec<_>>());
408            }
409            // Return the leaves.
410            Ok(leaves)
411        }
412    }
413
414    impl<N: Network> SimplePuzzle<N> {
415        /// Returns the number of leaves given the epoch hash.
416        pub fn num_leaves(&self, epoch_hash: N::BlockHash) -> Result<usize> {
417            const MIN_NUMBER_OF_LEAVES: usize = 100;
418            const MAX_NUMBER_OF_LEAVES: usize = 200;
419
420            // Prepare the seed.
421            let seed = u64::from_bytes_le(&epoch_hash.to_bytes_le()?[0..8])?;
422            // Seed a random number generator from the epoch hash.
423            let mut epoch_rng = ChaChaRng::seed_from_u64(seed);
424            // Sample a random number of leaves.
425            Ok(epoch_rng.gen_range(MIN_NUMBER_OF_LEAVES..MAX_NUMBER_OF_LEAVES))
426        }
427    }
428
429    /// Samples a new puzzle.
430    fn sample_puzzle() -> Puzzle<CurrentNetwork> {
431        Puzzle::<CurrentNetwork>::new::<SimplePuzzle<CurrentNetwork>>()
432    }
433
434    #[test]
435    fn test_puzzle() {
436        let mut rng = TestRng::default();
437
438        // Initialize a new puzzle.
439        let puzzle = sample_puzzle();
440
441        // Initialize an epoch hash.
442        let epoch_hash = rng.r#gen();
443
444        for batch_size in 1..=CurrentNetwork::MAX_SOLUTIONS {
445            // Initialize the solutions.
446            let solutions = (0..batch_size)
447                .map(|_| puzzle.prove(epoch_hash, rng.r#gen(), rng.r#gen(), None).unwrap())
448                .collect::<Vec<_>>();
449            let solutions = PuzzleSolutions::new(solutions).unwrap();
450
451            // Ensure the solutions are valid.
452            assert!(puzzle.check_solutions(&solutions, epoch_hash, 0u64).is_ok());
453
454            // Ensure the solutions are invalid.
455            let bad_epoch_hash = rng.r#gen();
456            assert!(puzzle.check_solutions(&solutions, bad_epoch_hash, 0u64).is_err());
457        }
458    }
459
460    #[test]
461    fn test_prove_with_minimum_proof_target() {
462        let mut rng = TestRng::default();
463
464        // Initialize a new puzzle.
465        let puzzle = sample_puzzle();
466
467        // Initialize an epoch hash.
468        let epoch_hash = rng.r#gen();
469
470        for _ in 0..ITERATIONS {
471            let private_key = PrivateKey::<CurrentNetwork>::new(&mut rng).unwrap();
472            let address = Address::try_from(private_key).unwrap();
473            let counter = u64::rand(&mut rng);
474
475            let solution = puzzle.prove(epoch_hash, address, counter, None).unwrap();
476            let proof_target = puzzle.get_proof_target(&solution).unwrap();
477
478            // Assert that the operation will pass if the minimum target is low enough.
479            assert!(puzzle.prove(epoch_hash, address, counter, Some(proof_target)).is_ok());
480
481            // Assert that the operation will fail if the minimum target is too high.
482            assert!(puzzle.prove(epoch_hash, address, counter, Some(proof_target.saturating_add(1))).is_err());
483
484            let solutions = PuzzleSolutions::new(vec![solution]).unwrap();
485
486            // Ensure the solution is valid.
487            assert!(puzzle.check_solutions(&solutions, epoch_hash, proof_target).is_ok());
488
489            // Ensure the solution is invalid.
490            assert!(puzzle.check_solutions(&solutions, epoch_hash, proof_target.saturating_add(1)).is_err());
491        }
492    }
493
494    #[test]
495    fn test_prove_with_no_minimum_proof_target() {
496        let mut rng = rand::thread_rng();
497
498        // Initialize a new puzzle.
499        let puzzle = sample_puzzle();
500
501        // Initialize an epoch hash.
502        let epoch_hash = rng.r#gen();
503
504        // Generate inputs.
505        let private_key = PrivateKey::<CurrentNetwork>::new(&mut rng).unwrap();
506        let address = Address::try_from(private_key).unwrap();
507
508        // Generate a solution.
509        let solution = puzzle.prove(epoch_hash, address, rng.r#gen(), None).unwrap();
510        assert!(puzzle.check_solution(&solution, epoch_hash, 0u64).is_ok());
511
512        let solutions = PuzzleSolutions::new(vec![solution]).unwrap();
513        assert!(puzzle.check_solutions(&solutions, epoch_hash, 0u64).is_ok());
514    }
515
516    #[test]
517    fn test_check_solution_with_incorrect_target_fails() {
518        let mut rng = rand::thread_rng();
519
520        // Initialize a new puzzle.
521        let puzzle = sample_puzzle();
522
523        // Initialize an epoch hash.
524        let epoch_hash = rng.r#gen();
525
526        // Generate inputs.
527        let private_key = PrivateKey::<CurrentNetwork>::new(&mut rng).unwrap();
528        let address = Address::try_from(private_key).unwrap();
529
530        // Generate a solution.
531        let solution = puzzle.prove(epoch_hash, address, rng.r#gen(), None).unwrap();
532
533        // Generate a solution with an incorrect target.
534        let incorrect_solution = Solution::new(*solution.partial_solution(), solution.target().saturating_add(1));
535
536        // Ensure the incorrect solution is invalid.
537        assert!(puzzle.check_solution(&incorrect_solution, epoch_hash, 0u64).is_err());
538
539        // Ensure the invalid solution is invalid on a fresh puzzle instance.
540        let new_puzzle = sample_puzzle();
541        assert!(new_puzzle.check_solution(&incorrect_solution, epoch_hash, 0u64).is_err());
542
543        // Ensure the incorrect solutions are invalid.
544        let incorrect_solutions = PuzzleSolutions::new(vec![incorrect_solution]).unwrap();
545        assert!(puzzle.check_solutions(&incorrect_solutions, epoch_hash, 0u64).is_err());
546
547        // Ensure the incorrect solutions are invalid on a fresh puzzle instance.
548        let new_puzzle = sample_puzzle();
549        assert!(new_puzzle.check_solutions(&incorrect_solutions, epoch_hash, 0u64).is_err());
550    }
551
552    #[test]
553    fn test_check_solutions_with_incorrect_target_fails() {
554        let mut rng = TestRng::default();
555
556        // Initialize a new puzzle.
557        let puzzle = sample_puzzle();
558
559        // Initialize an epoch hash.
560        let epoch_hash = rng.r#gen();
561
562        for batch_size in 1..=CurrentNetwork::MAX_SOLUTIONS {
563            // Initialize the incorrect solutions.
564            let incorrect_solutions = (0..batch_size)
565                .map(|_| {
566                    let solution = puzzle.prove(epoch_hash, rng.r#gen(), rng.r#gen(), None).unwrap();
567                    Solution::new(*solution.partial_solution(), solution.target().saturating_add(1))
568                })
569                .collect::<Vec<_>>();
570            let incorrect_solutions = PuzzleSolutions::new(incorrect_solutions).unwrap();
571
572            // Ensure the incorrect solutions are invalid.
573            assert!(puzzle.check_solutions(&incorrect_solutions, epoch_hash, 0u64).is_err());
574
575            // Ensure the incorrect solutions are invalid on a fresh puzzle instance.
576            let new_puzzle = sample_puzzle();
577            assert!(new_puzzle.check_solutions(&incorrect_solutions, epoch_hash, 0u64).is_err());
578        }
579    }
580
581    #[test]
582    fn test_check_solutions_with_duplicate_nonces() {
583        let mut rng = TestRng::default();
584
585        // Initialize a new puzzle.
586        let puzzle = sample_puzzle();
587
588        // Initialize an epoch hash.
589        let epoch_hash = rng.r#gen();
590        // Initialize an address.
591        let address = rng.r#gen();
592        // Initialize a counter.
593        let counter = rng.r#gen();
594
595        for batch_size in 1..=CurrentNetwork::MAX_SOLUTIONS {
596            // Initialize the solutions.
597            let solutions =
598                (0..batch_size).map(|_| puzzle.prove(epoch_hash, address, counter, None).unwrap()).collect::<Vec<_>>();
599            // Ensure the solutions are invalid, if the batch size is greater than 1.
600            let solutions = match batch_size {
601                1 => PuzzleSolutions::new(solutions).unwrap(),
602                _ => {
603                    assert!(PuzzleSolutions::new(solutions).is_err());
604                    continue;
605                }
606            };
607            match batch_size {
608                1 => assert!(puzzle.check_solutions(&solutions, epoch_hash, 0u64).is_ok()),
609                _ => unreachable!("There are duplicates that should not reach this point in the test"),
610            }
611        }
612    }
613
614    #[test]
615    fn test_get_proof_targets_without_cache() {
616        let mut rng = TestRng::default();
617
618        // Initialize an epoch hash.
619        let epoch_hash = rng.r#gen();
620
621        for batch_size in 1..=CurrentNetwork::MAX_SOLUTIONS {
622            // Initialize a new puzzle.
623            let puzzle = sample_puzzle();
624            // Initialize the solutions.
625            let solutions = (0..batch_size)
626                .map(|_| puzzle.prove(epoch_hash, rng.r#gen(), rng.r#gen(), None).unwrap())
627                .collect::<Vec<_>>();
628            let solutions = PuzzleSolutions::new(solutions).unwrap();
629
630            // Reinitialize the puzzle to *clear the cache*.
631            let puzzle = sample_puzzle();
632
633            // Compute the proof targets.
634            let proof_targets = puzzle.get_proof_targets(&solutions).unwrap();
635
636            // Ensure the proof targets are correct.
637            for ((_, solution), proof_target) in solutions.iter().zip(proof_targets) {
638                assert_eq!(puzzle.get_proof_target(solution).unwrap(), proof_target);
639            }
640        }
641    }
642
643    #[test]
644    fn test_get_proof_targets_with_partial_cache() {
645        let mut rng = TestRng::default();
646
647        // Initialize an epoch hash.
648        let epoch_hash = rng.r#gen();
649
650        for batch_size in 1..=CurrentNetwork::MAX_SOLUTIONS {
651            // Initialize a new puzzle.
652            let puzzle = sample_puzzle();
653            // Initialize the solutions.
654            let solutions = (0..batch_size)
655                .map(|_| puzzle.prove(epoch_hash, rng.r#gen(), rng.r#gen(), None).unwrap())
656                .collect::<Vec<_>>();
657            let solutions = PuzzleSolutions::new(solutions).unwrap();
658
659            // Reinitialize the puzzle to *clear the cache*.
660            let puzzle = sample_puzzle();
661
662            // Partially fill the cache.
663            for solution in solutions.values() {
664                // Flip a coin.
665                if rng.r#gen::<bool>() {
666                    // This operation will fill the cache.
667                    puzzle.get_proof_target(solution).unwrap();
668                }
669            }
670
671            // Compute the proof targets.
672            let proof_targets = puzzle.get_proof_targets(&solutions).unwrap();
673
674            // Ensure the proof targets are correct.
675            for ((_, solution), proof_target) in solutions.iter().zip(proof_targets) {
676                assert_eq!(puzzle.get_proof_target(solution).unwrap(), proof_target);
677            }
678        }
679    }
680
681    /// Use `cargo test profiler --features timer` to run this test.
682    #[ignore]
683    #[test]
684    fn test_profiler() -> Result<()> {
685        fn sample_address_and_counter(rng: &mut (impl CryptoRng + RngCore)) -> (Address<CurrentNetwork>, u64) {
686            let private_key = PrivateKey::new(rng).unwrap();
687            let address = Address::try_from(private_key).unwrap();
688            let counter = rng.next_u64();
689            (address, counter)
690        }
691
692        let mut rng = rand::thread_rng();
693
694        // Initialize a new puzzle.
695        let puzzle = sample_puzzle();
696
697        // Initialize an epoch hash.
698        let epoch_hash = rng.r#gen();
699
700        for batch_size in [1, 2, <CurrentNetwork as Network>::MAX_SOLUTIONS] {
701            // Generate the solutions.
702            let solutions = (0..batch_size)
703                .map(|_| {
704                    let (address, counter) = sample_address_and_counter(&mut rng);
705                    puzzle.prove(epoch_hash, address, counter, None).unwrap()
706                })
707                .collect::<Vec<_>>();
708            // Construct the solutions.
709            let solutions = PuzzleSolutions::new(solutions).unwrap();
710            // Verify the solutions.
711            puzzle.check_solutions(&solutions, epoch_hash, 0u64).unwrap();
712        }
713
714        bail!("\n\nRemember to #[ignore] this test!\n\n")
715    }
716}
snarkvm_ledger_puzzle/lib.rs

snarkvm_ledger_puzzle/
lib.rs
