snarkvm_ledger_puzzle/
lib.rs

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

snarkvm_ledger_puzzle/
lib.rs
