cuprate_pruning/
lib.rs

1//! # Pruning Mechanism for Monero
2//!
3//! This crate provides an implementation of the pruning mechanism used in Monero.
4//! The main data structure, `PruningSeed`, encapsulates the logic for creating and manipulating pruning seeds,
5//! which determine the set of blocks to be pruned from the blockchain.
6//!
7//! `PruningSeed` also contains a method for checking if a pruning seed is valid for Monero rules (must only be
8//! split into 8 parts):
9//!
10//! ```rust
11//! use cuprate_pruning::PruningSeed;
12//!
13//! let seed: u32 = 386; // the seed you want to check is valid
14//! match PruningSeed::decompress_p2p_rules(seed) {
15//!     Ok(seed) => seed, // seed is valid
16//!     Err(e) => panic!("seed is invalid")
17//! };
18//! ```
19//!
20
21use std::cmp::Ordering;
22
23use cuprate_constants::block::MAX_BLOCK_HEIGHT_USIZE;
24
25use thiserror::Error;
26
27/// The default log stripes for Monero pruning.
28pub const CRYPTONOTE_PRUNING_LOG_STRIPES: u32 = 3;
29/// The amount of blocks that peers keep before another stripe starts storing blocks.
30pub const CRYPTONOTE_PRUNING_STRIPE_SIZE: usize = 4096;
31/// The amount of blocks from the top of the chain that should not be pruned.
32pub const CRYPTONOTE_PRUNING_TIP_BLOCKS: usize = 5500;
33
34const PRUNING_SEED_LOG_STRIPES_SHIFT: u32 = 7;
35const PRUNING_SEED_STRIPE_SHIFT: u32 = 0;
36const PRUNING_SEED_LOG_STRIPES_MASK: u32 = 0x7;
37const PRUNING_SEED_STRIPE_MASK: u32 = 127;
38
39#[derive(Debug, Error)]
40pub enum PruningError {
41    #[error("log_stripes is out of range")]
42    LogStripesOutOfRange,
43    #[error("Stripe is out of range")]
44    StripeOutOfRange,
45    #[error("The block height is greater than `MAX_BLOCK_HEIGHT_USIZE`")]
46    BlockHeightTooLarge,
47    #[error("The blockchain height is greater than `MAX_BLOCK_HEIGHT_USIZE`")]
48    BlockChainHeightTooLarge,
49    #[error("The calculated height is smaller than the block height entered")]
50    CalculatedHeightSmallerThanEnteredBlock,
51    #[error("The entered seed has incorrect log stripes")]
52    SeedDoesNotHaveCorrectLogStripes,
53}
54
55/// A valid pruning seed for a Monero node.
56///
57/// A pruning seed tells nodes which blocks they should keep and which they should prune.
58#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
59#[cfg_attr(
60    feature = "borsh",
61    derive(borsh::BorshSerialize, borsh::BorshDeserialize)
62)]
63pub enum PruningSeed {
64    /// A peer with this seed is not pruned.
65    NotPruned,
66    /// A peer with this seed is pruned.
67    Pruned(DecompressedPruningSeed),
68}
69
70impl PruningSeed {
71    /// Creates a new [`PruningSeed::Pruned`] seed.
72    ///
73    /// See: [`DecompressedPruningSeed::new`]
74    pub fn new_pruned(stripe: u32, log_stripes: u32) -> Result<Self, PruningError> {
75        Ok(Self::Pruned(DecompressedPruningSeed::new(
76            stripe,
77            log_stripes,
78        )?))
79    }
80
81    /// Attempts to decompress a raw pruning seed.
82    ///
83    /// An error means the pruning seed was invalid.
84    pub fn decompress(seed: u32) -> Result<Self, PruningError> {
85        Ok(DecompressedPruningSeed::decompress(seed)?.map_or(Self::NotPruned, Self::Pruned))
86    }
87
88    /// Decompresses the seed, performing the same checks as [`PruningSeed::decompress`] and some more according to
89    /// Monero's p2p networks rules.
90    ///
91    /// The only added check currently is that `log_stripes` == 3.
92    pub fn decompress_p2p_rules(seed: u32) -> Result<Self, PruningError> {
93        let seed = Self::decompress(seed)?;
94
95        if let Some(log_stripes) = seed.get_log_stripes() {
96            if log_stripes != CRYPTONOTE_PRUNING_LOG_STRIPES {
97                return Err(PruningError::LogStripesOutOfRange);
98            }
99        }
100
101        Ok(seed)
102    }
103
104    /// Compresses this pruning seed to a u32.
105    pub const fn compress(&self) -> u32 {
106        match self {
107            Self::NotPruned => 0,
108            Self::Pruned(seed) => seed.compress(),
109        }
110    }
111
112    /// Returns the `log_stripes` for this seed, if this seed is pruned otherwise [`None`] is returned.
113    pub const fn get_log_stripes(&self) -> Option<u32> {
114        match self {
115            Self::NotPruned => None,
116            Self::Pruned(seed) => Some(seed.log_stripes),
117        }
118    }
119
120    /// Returns the `stripe` for this seed, if this seed is pruned otherwise [`None`] is returned.
121    pub const fn get_stripe(&self) -> Option<u32> {
122        match self {
123            Self::NotPruned => None,
124            Self::Pruned(seed) => Some(seed.stripe),
125        }
126    }
127
128    /// Returns `true` if a peer with this pruning seed should have a non-pruned version of a block.
129    pub const fn has_full_block(&self, height: usize, blockchain_height: usize) -> bool {
130        match self {
131            Self::NotPruned => true,
132            Self::Pruned(seed) => seed.has_full_block(height, blockchain_height),
133        }
134    }
135
136    /// Gets the next pruned block for a given `block_height` and `blockchain_height`
137    ///
138    /// Each seed will store, in a cyclic manner, a portion of blocks while discarding
139    /// the ones that are out of your stripe. This function is finding the next height
140    /// for which a specific seed will start pruning blocks.
141    ///
142    /// This will return Ok(None) if the seed does no pruning or if there is no pruned block
143    /// after this one.
144    ///
145    /// ### Errors
146    ///
147    /// This function will return an Error if the inputted `block_height` or
148    /// `blockchain_height` is greater than [`MAX_BLOCK_HEIGHT_USIZE`].
149    ///
150    /// This function will also error if `block_height` > `blockchain_height`
151    pub fn get_next_pruned_block(
152        &self,
153        block_height: usize,
154        blockchain_height: usize,
155    ) -> Result<Option<usize>, PruningError> {
156        Ok(match self {
157            Self::NotPruned => None,
158            Self::Pruned(seed) => seed.get_next_pruned_block(block_height, blockchain_height)?,
159        })
160    }
161
162    /// Gets the next unpruned block for a given `block_height` and `blockchain_height`
163    ///
164    /// Each seed will store, in a cyclic manner, a portion of blocks while discarding
165    /// the ones that are out of your stripe. This function is finding the next height
166    /// for which a specific seed will start storing blocks.
167    ///
168    /// ### Errors
169    ///
170    /// This function will return an Error if the inputted `block_height` or
171    /// `blockchain_height` is greater than [`MAX_BLOCK_HEIGHT_USIZE`].
172    ///
173    /// This function will also error if `block_height` > `blockchain_height`
174    ///
175    pub fn get_next_unpruned_block(
176        &self,
177        block_height: usize,
178        blockchain_height: usize,
179    ) -> Result<usize, PruningError> {
180        Ok(match self {
181            Self::NotPruned => block_height,
182            Self::Pruned(seed) => seed.get_next_unpruned_block(block_height, blockchain_height)?,
183        })
184    }
185}
186
187impl PartialOrd<Self> for PruningSeed {
188    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
189        Some(self.cmp(other))
190    }
191}
192
193impl Ord for PruningSeed {
194    fn cmp(&self, other: &Self) -> Ordering {
195        match (self, other) {
196            // Make sure pruning seeds storing more blocks are greater.
197            (Self::NotPruned, Self::NotPruned) => Ordering::Equal,
198            (Self::NotPruned, Self::Pruned(_)) => Ordering::Greater,
199            (Self::Pruned(_), Self::NotPruned) => Ordering::Less,
200
201            (Self::Pruned(seed1), Self::Pruned(seed2)) => seed1.cmp(seed2),
202        }
203    }
204}
205
206/// This represents a valid Monero pruning seed.
207///
208/// It does allow representations of pruning seeds that Monero's P2P network would not allow, i.e.
209/// it does not restrict the seed to only have a `log_stripes` of 8.
210#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)]
211#[cfg_attr(
212    feature = "borsh",
213    derive(borsh::BorshSerialize, borsh::BorshDeserialize)
214)]
215pub struct DecompressedPruningSeed {
216    /// The amount of portions the blockchain is split into.
217    log_stripes: u32,
218    /// The specific portion this peer keeps.
219    ///
220    /// *MUST* be between `1..=2^log_stripes`
221    stripe: u32,
222}
223
224impl PartialOrd<Self> for DecompressedPruningSeed {
225    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
226        Some(self.cmp(other))
227    }
228}
229
230impl Ord for DecompressedPruningSeed {
231    fn cmp(&self, other: &Self) -> Ordering {
232        // Compare the `log_stripes` first so peers which store more blocks are greater than peers
233        // storing less.
234        #[expect(clippy::wildcard_enum_match_arm)]
235        match self.log_stripes.cmp(&other.log_stripes) {
236            Ordering::Equal => self.stripe.cmp(&other.stripe),
237            ord => ord,
238        }
239    }
240}
241
242impl DecompressedPruningSeed {
243    /// Creates a new pruning seed from a `stripe` and `log_stripes`
244    ///
245    /// ### What is a `stripe`
246    ///
247    /// A stripe is the part of the blockchain this peer will keep.
248    ///  
249    /// Monero, when pruning, will split the blockchain into multiple
250    /// "stripes", that amount is currently 8 and each pruned peer
251    /// will keep one of those 8 stripes.
252    ///
253    /// ### What is `log_stripes`
254    ///
255    /// `log_stripes` is log2 of the amount of stripes used.
256    ///
257    ///  For Monero, currently, that amount is 8 so `log_stripes` will
258    ///  be 3.
259    ///
260    /// ---------------------------------------------------------------
261    ///
262    /// *note this function allows you to make invalid seeds, this is done
263    /// to allow the specifics of pruning to change in the future. To make
264    /// a valid seed you currently MUST pass in a number 1 to 8 for `stripe`
265    /// and 3 for `log_stripes`.*
266    ///
267    pub const fn new(stripe: u32, log_stripes: u32) -> Result<Self, PruningError> {
268        if log_stripes > PRUNING_SEED_LOG_STRIPES_MASK {
269            Err(PruningError::LogStripesOutOfRange)
270        } else if !(stripe > 0 && stripe <= (1 << log_stripes)) {
271            Err(PruningError::StripeOutOfRange)
272        } else {
273            Ok(Self {
274                log_stripes,
275                stripe,
276            })
277        }
278    }
279
280    /// Attempts to decompress a raw pruning seed.
281    ///
282    /// Will return Ok(None) if the pruning seed means no pruning.
283    ///
284    /// An error means the pruning seed was invalid.
285    pub const fn decompress(seed: u32) -> Result<Option<Self>, PruningError> {
286        if seed == 0 {
287            // No pruning.
288            return Ok(None);
289        }
290
291        let log_stripes = (seed >> PRUNING_SEED_LOG_STRIPES_SHIFT) & PRUNING_SEED_LOG_STRIPES_MASK;
292        let stripe = 1 + ((seed >> PRUNING_SEED_STRIPE_SHIFT) & PRUNING_SEED_STRIPE_MASK);
293
294        if stripe > (1 << log_stripes) {
295            return Err(PruningError::StripeOutOfRange);
296        }
297
298        Ok(Some(Self {
299            log_stripes,
300            stripe,
301        }))
302    }
303
304    /// Compresses the pruning seed into a u32.
305    pub const fn compress(&self) -> u32 {
306        (self.log_stripes << PRUNING_SEED_LOG_STRIPES_SHIFT)
307            | ((self.stripe - 1) << PRUNING_SEED_STRIPE_SHIFT)
308    }
309
310    /// Returns `true` if a peer with this pruning seed should have a non-pruned version of a block.
311    pub const fn has_full_block(&self, height: usize, blockchain_height: usize) -> bool {
312        match get_block_pruning_stripe(height, blockchain_height, self.log_stripes) {
313            Some(block_stripe) => self.stripe == block_stripe,
314            None => true,
315        }
316    }
317
318    /// Gets the next unpruned block for a given `block_height` and `blockchain_height`
319    ///
320    /// Each seed will store, in a cyclic manner, a portion of blocks while discarding
321    /// the ones that are out of your stripe. This function is finding the next height
322    /// for which a specific seed will start storing blocks.
323    ///
324    /// ### Errors
325    ///
326    /// This function will return an Error if the inputted `block_height` or
327    /// `blockchain_height` is greater than [`MAX_BLOCK_HEIGHT_USIZE`].
328    ///
329    /// This function will also error if `block_height` > `blockchain_height`
330    ///
331    pub const fn get_next_unpruned_block(
332        &self,
333        block_height: usize,
334        blockchain_height: usize,
335    ) -> Result<usize, PruningError> {
336        if block_height > MAX_BLOCK_HEIGHT_USIZE || block_height > blockchain_height {
337            return Err(PruningError::BlockHeightTooLarge);
338        }
339
340        if blockchain_height > MAX_BLOCK_HEIGHT_USIZE {
341            return Err(PruningError::BlockChainHeightTooLarge);
342        }
343
344        if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
345            // If we are within `CRYPTONOTE_PRUNING_TIP_BLOCKS` of the chain we should
346            // not prune blocks.
347            return Ok(block_height);
348        }
349
350        let block_pruning_stripe = get_block_pruning_stripe(block_height, blockchain_height, self.log_stripes)
351                .expect("We just checked if `block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height`");
352        if self.stripe == block_pruning_stripe {
353            // if we have the same stripe as a block that means we keep the block so
354            // the entered block is the next un-pruned one.
355            return Ok(block_height);
356        }
357
358        // cycles: how many times each seed has stored blocks so when all seeds have
359        // stored blocks thats 1 cycle
360        let cycles = (block_height / CRYPTONOTE_PRUNING_STRIPE_SIZE) >> self.log_stripes;
361        // if our seed is before the blocks seed in a cycle that means we have already past our
362        // seed this cycle and need to start the next
363        let cycles_start = cycles
364            + if self.stripe > block_pruning_stripe {
365                0
366            } else {
367                1
368            };
369
370        // amt_of_cycles * blocks in a cycle + how many blocks through a cycles until the seed starts storing blocks
371        let calculated_height = cycles_start * (CRYPTONOTE_PRUNING_STRIPE_SIZE << self.log_stripes)
372            + (self.stripe as usize - 1) * CRYPTONOTE_PRUNING_STRIPE_SIZE;
373
374        if calculated_height + CRYPTONOTE_PRUNING_TIP_BLOCKS > blockchain_height {
375            // if our calculated height is greater than the amount of tip blocks then the start of the tip blocks will be the next un-pruned
376            Ok(blockchain_height.saturating_sub(CRYPTONOTE_PRUNING_TIP_BLOCKS))
377        } else if calculated_height < block_height {
378            Err(PruningError::CalculatedHeightSmallerThanEnteredBlock)
379        } else {
380            Ok(calculated_height)
381        }
382    }
383
384    /// Gets the next pruned block for a given `block_height` and `blockchain_height`
385    ///
386    /// Each seed will store, in a cyclic manner, a portion of blocks while discarding
387    /// the ones that are out of your stripe. This function is finding the next height
388    /// for which a specific seed will start pruning blocks.
389    ///
390    /// ### Errors
391    ///
392    /// This function will return an Error if the inputted `block_height` or
393    /// `blockchain_height` is greater than [`MAX_BLOCK_HEIGHT_USIZE`].
394    ///
395    /// This function will also error if `block_height` > `blockchain_height`
396    ///
397    pub fn get_next_pruned_block(
398        &self,
399        block_height: usize,
400        blockchain_height: usize,
401    ) -> Result<Option<usize>, PruningError> {
402        if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
403            // If we are within `CRYPTONOTE_PRUNING_TIP_BLOCKS` of the chain we should
404            // not prune blocks.
405            return Ok(None);
406        }
407
408        let block_pruning_stripe = get_block_pruning_stripe(block_height, blockchain_height, self.log_stripes)
409            .expect("We just checked if `block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height`");
410        if self.stripe != block_pruning_stripe {
411            // if our stripe != the blocks stripe that means we prune that block
412            return Ok(Some(block_height));
413        }
414
415        // We can get the end of our "non-pruning" cycle by getting the next stripe's first un-pruned block height.
416        // So we calculate the next un-pruned block for the next stripe and return it as our next pruned block
417        let next_stripe = 1 + (self.stripe & ((1 << self.log_stripes) - 1));
418        let seed = Self::new(next_stripe, self.log_stripes)
419            .expect("We just made sure this stripe is in range for this log_stripe");
420
421        let calculated_height = seed.get_next_unpruned_block(block_height, blockchain_height)?;
422
423        if calculated_height + CRYPTONOTE_PRUNING_TIP_BLOCKS > blockchain_height {
424            // If the calculated height is in tip blocks then there is no next block to prune
425            Ok(None)
426        } else {
427            Ok(Some(calculated_height))
428        }
429    }
430}
431
432const fn get_block_pruning_stripe(
433    block_height: usize,
434    blockchain_height: usize,
435    log_stripe: u32,
436) -> Option<u32> {
437    if block_height + CRYPTONOTE_PRUNING_TIP_BLOCKS >= blockchain_height {
438        None
439    } else {
440        #[expect(
441            clippy::cast_possible_truncation,
442            clippy::cast_sign_loss,
443            reason = "it's trivial to prove it's ok to us `as` here"
444        )]
445        Some(
446            (((block_height / CRYPTONOTE_PRUNING_STRIPE_SIZE) & ((1 << log_stripe) as usize - 1))
447                + 1) as u32,
448        )
449    }
450}
451
452#[cfg(test)]
453mod tests {
454    use super::*;
455
456    fn make_all_pruning_seeds() -> Vec<PruningSeed> {
457        let possible_stripes = 1..=(1 << CRYPTONOTE_PRUNING_LOG_STRIPES);
458        possible_stripes
459            .map(|stripe| PruningSeed::new_pruned(stripe, CRYPTONOTE_PRUNING_LOG_STRIPES).unwrap())
460            .collect()
461    }
462
463    #[test]
464    fn from_u32_for_pruning_seed() {
465        let good_seeds = 384..=391;
466        for seed in good_seeds {
467            assert!(PruningSeed::decompress(seed).is_ok());
468        }
469        let bad_seeds = [383, 392];
470        for seed in bad_seeds {
471            assert!(PruningSeed::decompress(seed).is_err());
472        }
473    }
474
475    #[test]
476    fn make_invalid_pruning_seeds() {
477        let invalid_stripes = [0, (1 << CRYPTONOTE_PRUNING_LOG_STRIPES) + 1];
478
479        for stripe in invalid_stripes {
480            assert!(PruningSeed::new_pruned(stripe, CRYPTONOTE_PRUNING_LOG_STRIPES).is_err());
481        }
482    }
483
484    #[test]
485    fn get_pruning_log_stripe() {
486        let all_valid_seeds = make_all_pruning_seeds();
487        for seed in &all_valid_seeds {
488            assert_eq!(seed.get_log_stripes().unwrap(), 3);
489        }
490    }
491
492    #[test]
493    fn get_pruning_stripe() {
494        let all_valid_seeds = make_all_pruning_seeds();
495        #[expect(clippy::cast_possible_truncation)]
496        for (i, seed) in all_valid_seeds.iter().enumerate() {
497            assert_eq!(seed.get_stripe().unwrap(), i as u32 + 1);
498        }
499    }
500
501    #[test]
502    fn blocks_pruning_stripe() {
503        let blockchain_height = 76437863;
504
505        for i in 0_u32..8 {
506            assert_eq!(
507                get_block_pruning_stripe(
508                    (i * 4096) as usize,
509                    blockchain_height,
510                    CRYPTONOTE_PRUNING_LOG_STRIPES
511                )
512                .unwrap(),
513                i + 1
514            );
515        }
516
517        for i in 0_u32..8 {
518            assert_eq!(
519                get_block_pruning_stripe(
520                    32768 + (i * 4096) as usize,
521                    blockchain_height,
522                    CRYPTONOTE_PRUNING_LOG_STRIPES
523                )
524                .unwrap(),
525                i + 1
526            );
527        }
528
529        for i in 1_u32..8 {
530            assert_eq!(
531                get_block_pruning_stripe(
532                    32767 + (i * 4096) as usize,
533                    blockchain_height,
534                    CRYPTONOTE_PRUNING_LOG_STRIPES
535                )
536                .unwrap(),
537                i
538            );
539        }
540
541        // Block shouldn't be pruned
542        assert!(get_block_pruning_stripe(
543            blockchain_height - 5500,
544            blockchain_height,
545            CRYPTONOTE_PRUNING_LOG_STRIPES
546        )
547        .is_none());
548    }
549
550    #[test]
551    fn next_unpruned_block() {
552        let all_valid_seeds = make_all_pruning_seeds();
553        let blockchain_height = 76437863;
554
555        for (i, seed) in all_valid_seeds.iter().enumerate() {
556            assert_eq!(
557                seed.get_next_unpruned_block(0, blockchain_height).unwrap(),
558                i * 4096
559            );
560        }
561
562        for (i, seed) in all_valid_seeds.iter().enumerate() {
563            assert_eq!(
564                seed.get_next_unpruned_block((i + 1) * 4096, blockchain_height)
565                    .unwrap(),
566                i * 4096 + 32768
567            );
568        }
569
570        for (i, seed) in all_valid_seeds.iter().enumerate() {
571            assert_eq!(
572                seed.get_next_unpruned_block((i + 8) * 4096, blockchain_height)
573                    .unwrap(),
574                i * 4096 + 32768
575            );
576        }
577
578        for seed in &all_valid_seeds {
579            assert_eq!(
580                seed.get_next_unpruned_block(76437863 - 1, blockchain_height)
581                    .unwrap(),
582                76437863 - 1
583            );
584        }
585
586        let zero_seed = PruningSeed::NotPruned;
587
588        assert_eq!(
589            zero_seed.get_next_unpruned_block(33443, 5565445).unwrap(),
590            33443
591        );
592
593        let seed = PruningSeed::decompress(384).unwrap();
594
595        // the next unpruned block is the first tip block
596        assert_eq!(seed.get_next_unpruned_block(5000, 11000).unwrap(), 5500);
597    }
598
599    #[test]
600    fn next_pruned_block() {
601        let all_valid_seeds = make_all_pruning_seeds();
602        let blockchain_height = 76437863;
603
604        for seed in all_valid_seeds.iter().skip(1) {
605            assert_eq!(
606                seed.get_next_pruned_block(0, blockchain_height)
607                    .unwrap()
608                    .unwrap(),
609                0
610            );
611        }
612
613        for (i, seed) in all_valid_seeds.iter().enumerate() {
614            assert_eq!(
615                seed.get_next_pruned_block((i + 1) * 4096, blockchain_height)
616                    .unwrap()
617                    .unwrap(),
618                (i + 1) * 4096
619            );
620        }
621
622        for (i, seed) in all_valid_seeds.iter().enumerate() {
623            assert_eq!(
624                seed.get_next_pruned_block((i + 8) * 4096, blockchain_height)
625                    .unwrap()
626                    .unwrap(),
627                (i + 9) * 4096
628            );
629        }
630
631        for seed in &all_valid_seeds {
632            assert_eq!(
633                seed.get_next_pruned_block(76437863 - 1, blockchain_height)
634                    .unwrap(),
635                None
636            );
637        }
638
639        let zero_seed = PruningSeed::NotPruned;
640
641        assert_eq!(
642            zero_seed.get_next_pruned_block(33443, 5565445).unwrap(),
643            None
644        );
645
646        let seed = PruningSeed::decompress(384).unwrap();
647
648        // there is no next pruned block
649        assert_eq!(seed.get_next_pruned_block(5000, 10000).unwrap(), None);
650    }
651}