subspace_core_primitives/
segments.rs

1//! Segments-related data structures.
2
3#[cfg(not(feature = "std"))]
4extern crate alloc;
5
6use crate::BlockNumber;
7use crate::hashes::{Blake3Hash, blake3_hash};
8use crate::pieces::{FlatPieces, Piece, PieceIndex, RawRecord};
9#[cfg(not(feature = "std"))]
10use alloc::boxed::Box;
11use core::array::TryFromSliceError;
12use core::fmt;
13use core::iter::Step;
14use core::num::NonZeroU64;
15use derive_more::{
16    Add, AddAssign, Deref, DerefMut, Display, Div, DivAssign, From, Into, Mul, MulAssign, Sub,
17    SubAssign,
18};
19use parity_scale_codec::{Decode, DecodeWithMemTracking, Encode, MaxEncodedLen};
20use scale_info::TypeInfo;
21#[cfg(feature = "serde")]
22use serde::{Deserialize, Serialize};
23#[cfg(feature = "serde")]
24use serde::{Deserializer, Serializer};
25#[cfg(feature = "serde")]
26use serde_big_array::BigArray;
27
28/// Segment index type.
29#[derive(
30    Debug,
31    Display,
32    Default,
33    Copy,
34    Clone,
35    Ord,
36    PartialOrd,
37    Eq,
38    PartialEq,
39    Hash,
40    From,
41    Into,
42    Encode,
43    Decode,
44    Add,
45    AddAssign,
46    Sub,
47    SubAssign,
48    Mul,
49    MulAssign,
50    Div,
51    DivAssign,
52    TypeInfo,
53    MaxEncodedLen,
54    DecodeWithMemTracking,
55)]
56#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
57#[repr(transparent)]
58pub struct SegmentIndex(u64);
59
60impl Step for SegmentIndex {
61    #[inline]
62    fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
63        u64::steps_between(&start.0, &end.0)
64    }
65
66    #[inline]
67    fn forward_checked(start: Self, count: usize) -> Option<Self> {
68        u64::forward_checked(start.0, count).map(Self)
69    }
70
71    #[inline]
72    fn forward_overflowing(start: Self, count: usize) -> (Self, bool) {
73        let (n, overflowing) = u64::forward_overflowing(start.0, count);
74        (Self(n), overflowing)
75    }
76
77    #[inline]
78    fn backward_checked(start: Self, count: usize) -> Option<Self> {
79        u64::backward_checked(start.0, count).map(Self)
80    }
81
82    #[inline]
83    fn backward_overflowing(start: Self, count: usize) -> (Self, bool) {
84        let (n, overflowing) = u64::backward_overflowing(start.0, count);
85        (Self(n), overflowing)
86    }
87}
88
89impl SegmentIndex {
90    /// Segment index 0.
91    pub const ZERO: SegmentIndex = SegmentIndex(0);
92    /// Segment index 1.
93    pub const ONE: SegmentIndex = SegmentIndex(1);
94
95    /// Create new instance
96    #[inline]
97    pub const fn new(n: u64) -> Self {
98        Self(n)
99    }
100
101    /// Get the first piece index in this segment.
102    #[inline]
103    pub const fn first_piece_index(&self) -> PieceIndex {
104        PieceIndex::new(self.0 * ArchivedHistorySegment::NUM_PIECES as u64)
105    }
106
107    /// Get the last piece index in this segment.
108    #[inline]
109    pub const fn last_piece_index(&self) -> PieceIndex {
110        PieceIndex::new((self.0 + 1) * ArchivedHistorySegment::NUM_PIECES as u64 - 1)
111    }
112
113    /// List of piece indexes that belong to this segment.
114    pub fn segment_piece_indexes(&self) -> [PieceIndex; ArchivedHistorySegment::NUM_PIECES] {
115        let mut piece_indices = [PieceIndex::ZERO; ArchivedHistorySegment::NUM_PIECES];
116        (self.first_piece_index()..=self.last_piece_index())
117            .zip(&mut piece_indices)
118            .for_each(|(input, output)| {
119                *output = input;
120            });
121
122        piece_indices
123    }
124
125    /// List of piece indexes that belong to this segment with source pieces first.
126    pub fn segment_piece_indexes_source_first(
127        &self,
128    ) -> [PieceIndex; ArchivedHistorySegment::NUM_PIECES] {
129        let mut source_first_piece_indices = [PieceIndex::ZERO; ArchivedHistorySegment::NUM_PIECES];
130
131        let piece_indices = self.segment_piece_indexes();
132        piece_indices
133            .into_iter()
134            .step_by(2)
135            .chain(piece_indices.into_iter().skip(1).step_by(2))
136            .zip(&mut source_first_piece_indices)
137            .for_each(|(input, output)| {
138                *output = input;
139            });
140
141        source_first_piece_indices
142    }
143
144    /// Checked integer subtraction. Computes `self - rhs`, returning `None` if underflow occurred.
145    #[inline]
146    pub const fn checked_sub(self, rhs: Self) -> Option<Self> {
147        // TODO: when Option::map becomes const, use it here
148        match self.0.checked_sub(rhs.0) {
149            Some(segment_index) => Some(Self(segment_index)),
150            None => None,
151        }
152    }
153
154    /// Saturating integer subtraction. Computes `self - rhs`, returning zero if underflow
155    /// occurred.
156    #[inline]
157    pub const fn saturating_sub(self, rhs: Self) -> Self {
158        Self(self.0.saturating_sub(rhs.0))
159    }
160}
161
162/// Segment commitment contained within segment header.
163#[derive(
164    Copy,
165    Clone,
166    Eq,
167    PartialEq,
168    Hash,
169    Deref,
170    DerefMut,
171    From,
172    Into,
173    Encode,
174    Decode,
175    TypeInfo,
176    MaxEncodedLen,
177    DecodeWithMemTracking,
178)]
179#[repr(transparent)]
180pub struct SegmentCommitment([u8; SegmentCommitment::SIZE]);
181
182impl fmt::Debug for SegmentCommitment {
183    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
184        write!(f, "{}", hex::encode(self.0))
185    }
186}
187
188#[cfg(feature = "serde")]
189#[derive(Serialize, Deserialize)]
190#[serde(transparent)]
191struct SegmentCommitmentBinary(#[serde(with = "BigArray")] [u8; SegmentCommitment::SIZE]);
192
193#[cfg(feature = "serde")]
194#[derive(Serialize, Deserialize)]
195#[serde(transparent)]
196struct SegmentCommitmentHex(#[serde(with = "hex")] [u8; SegmentCommitment::SIZE]);
197
198#[cfg(feature = "serde")]
199impl Serialize for SegmentCommitment {
200    #[inline]
201    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
202    where
203        S: Serializer,
204    {
205        if serializer.is_human_readable() {
206            SegmentCommitmentHex(self.0).serialize(serializer)
207        } else {
208            SegmentCommitmentBinary(self.0).serialize(serializer)
209        }
210    }
211}
212
213#[cfg(feature = "serde")]
214impl<'de> Deserialize<'de> for SegmentCommitment {
215    #[inline]
216    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
217    where
218        D: Deserializer<'de>,
219    {
220        Ok(Self(if deserializer.is_human_readable() {
221            SegmentCommitmentHex::deserialize(deserializer)?.0
222        } else {
223            SegmentCommitmentBinary::deserialize(deserializer)?.0
224        }))
225    }
226}
227
228impl Default for SegmentCommitment {
229    #[inline]
230    fn default() -> Self {
231        Self([0; Self::SIZE])
232    }
233}
234
235impl TryFrom<&[u8]> for SegmentCommitment {
236    type Error = TryFromSliceError;
237
238    #[inline]
239    fn try_from(slice: &[u8]) -> Result<Self, Self::Error> {
240        <[u8; Self::SIZE]>::try_from(slice).map(Self)
241    }
242}
243
244impl AsRef<[u8]> for SegmentCommitment {
245    #[inline]
246    fn as_ref(&self) -> &[u8] {
247        &self.0
248    }
249}
250
251impl AsMut<[u8]> for SegmentCommitment {
252    #[inline]
253    fn as_mut(&mut self) -> &mut [u8] {
254        &mut self.0
255    }
256}
257
258impl SegmentCommitment {
259    /// Size of segment commitment in bytes.
260    pub const SIZE: usize = 48;
261}
262
263/// Size of blockchain history in segments.
264#[derive(
265    Debug,
266    Display,
267    Copy,
268    Clone,
269    Ord,
270    PartialOrd,
271    Eq,
272    PartialEq,
273    Hash,
274    From,
275    Into,
276    Deref,
277    DerefMut,
278    Encode,
279    Decode,
280    TypeInfo,
281    MaxEncodedLen,
282    DecodeWithMemTracking,
283)]
284#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
285#[repr(transparent)]
286pub struct HistorySize(NonZeroU64);
287
288impl From<SegmentIndex> for HistorySize {
289    #[inline]
290    fn from(value: SegmentIndex) -> Self {
291        Self(NonZeroU64::new(value.0 + 1).expect("Not zero; qed"))
292    }
293}
294
295impl HistorySize {
296    /// History size of one
297    pub const ONE: Self = Self(NonZeroU64::new(1).expect("Not zero; qed"));
298
299    /// Create new instance.
300    pub const fn new(value: NonZeroU64) -> Self {
301        Self(value)
302    }
303
304    /// Size of blockchain history in pieces.
305    pub const fn in_pieces(&self) -> NonZeroU64 {
306        self.0.saturating_mul(
307            NonZeroU64::new(ArchivedHistorySegment::NUM_PIECES as u64).expect("Not zero; qed"),
308        )
309    }
310
311    /// Segment index that corresponds to this history size.
312    pub fn segment_index(&self) -> SegmentIndex {
313        SegmentIndex::from(self.0.get() - 1)
314    }
315
316    /// History size at which expiration check for sector happens.
317    ///
318    /// Returns `None` on overflow.
319    pub fn sector_expiration_check(&self, min_sector_lifetime: Self) -> Option<Self> {
320        self.0.checked_add(min_sector_lifetime.0.get()).map(Self)
321    }
322}
323
324/// Progress of an archived block.
325#[derive(
326    Debug,
327    Copy,
328    Clone,
329    PartialEq,
330    Eq,
331    Ord,
332    PartialOrd,
333    Hash,
334    Encode,
335    Decode,
336    TypeInfo,
337    DecodeWithMemTracking,
338)]
339#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
340#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
341pub enum ArchivedBlockProgress {
342    /// The block has been fully archived.
343    Complete,
344
345    /// Number of partially archived bytes of a block.
346    Partial(u32),
347}
348
349impl Default for ArchivedBlockProgress {
350    /// We assume a block can always fit into the segment initially, but it is definitely possible
351    /// to be transitioned into the partial state after some overflow checking.
352    #[inline]
353    fn default() -> Self {
354        Self::Complete
355    }
356}
357
358impl ArchivedBlockProgress {
359    /// Return the number of partially archived bytes if the progress is not complete.
360    pub fn partial(&self) -> Option<u32> {
361        match self {
362            Self::Complete => None,
363            Self::Partial(number) => Some(*number),
364        }
365    }
366
367    /// Sets new number of partially archived bytes.
368    pub fn set_partial(&mut self, new_partial: u32) {
369        *self = Self::Partial(new_partial);
370    }
371}
372
373/// Last archived block
374#[derive(
375    Debug,
376    Copy,
377    Clone,
378    PartialEq,
379    Eq,
380    Ord,
381    PartialOrd,
382    Hash,
383    Encode,
384    Decode,
385    TypeInfo,
386    DecodeWithMemTracking,
387)]
388#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
389#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
390pub struct LastArchivedBlock {
391    /// Block number
392    pub number: BlockNumber,
393    /// Progress of an archived block.
394    pub archived_progress: ArchivedBlockProgress,
395}
396
397impl LastArchivedBlock {
398    /// Returns the number of partially archived bytes for a block.
399    pub fn partial_archived(&self) -> Option<u32> {
400        self.archived_progress.partial()
401    }
402
403    /// Sets new number of partially archived bytes.
404    pub fn set_partial_archived(&mut self, new_partial: u32) {
405        self.archived_progress.set_partial(new_partial);
406    }
407
408    /// Sets the archived state of this block to [`ArchivedBlockProgress::Complete`].
409    pub fn set_complete(&mut self) {
410        self.archived_progress = ArchivedBlockProgress::Complete;
411    }
412}
413
414/// Segment header for a specific segment.
415///
416/// Each segment will have corresponding [`SegmentHeader`] included as the first item in the next
417/// segment. Each `SegmentHeader` includes hash of the previous one and all together form a chain of
418/// segment headers that is used for quick and efficient verification that some [`Piece`]
419/// corresponds to the actual archival history of the blockchain.
420#[derive(
421    Debug, Copy, Clone, PartialEq, Eq, Encode, Decode, TypeInfo, Hash, DecodeWithMemTracking,
422)]
423#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
424#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
425pub enum SegmentHeader {
426    /// V0 of the segment header data structure
427    #[codec(index = 0)]
428    #[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
429    V0 {
430        /// Segment index
431        segment_index: SegmentIndex,
432        /// Root of commitments of all records in a segment.
433        segment_commitment: SegmentCommitment,
434        /// Hash of the segment header of the previous segment
435        prev_segment_header_hash: Blake3Hash,
436        /// Last archived block
437        last_archived_block: LastArchivedBlock,
438    },
439}
440
441impl SegmentHeader {
442    /// Hash of the whole segment header
443    pub fn hash(&self) -> Blake3Hash {
444        blake3_hash(&self.encode())
445    }
446
447    /// Segment index
448    pub fn segment_index(&self) -> SegmentIndex {
449        match self {
450            Self::V0 { segment_index, .. } => *segment_index,
451        }
452    }
453
454    /// Segment commitment of the records in a segment.
455    pub fn segment_commitment(&self) -> SegmentCommitment {
456        match self {
457            Self::V0 {
458                segment_commitment, ..
459            } => *segment_commitment,
460        }
461    }
462
463    /// Hash of the segment header of the previous segment
464    pub fn prev_segment_header_hash(&self) -> Blake3Hash {
465        match self {
466            Self::V0 {
467                prev_segment_header_hash,
468                ..
469            } => *prev_segment_header_hash,
470        }
471    }
472
473    /// Last archived block
474    pub fn last_archived_block(&self) -> LastArchivedBlock {
475        match self {
476            Self::V0 {
477                last_archived_block,
478                ..
479            } => *last_archived_block,
480        }
481    }
482}
483
484/// Recorded history segment before archiving is applied.
485///
486/// NOTE: This is a stack-allocated data structure and can cause stack overflow!
487#[derive(Copy, Clone, Eq, PartialEq, Deref, DerefMut)]
488#[repr(transparent)]
489pub struct RecordedHistorySegment([RawRecord; Self::NUM_RAW_RECORDS]);
490
491impl fmt::Debug for RecordedHistorySegment {
492    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
493        f.debug_struct("RecordedHistorySegment")
494            .finish_non_exhaustive()
495    }
496}
497
498impl Default for RecordedHistorySegment {
499    #[inline]
500    fn default() -> Self {
501        Self([RawRecord::default(); Self::NUM_RAW_RECORDS])
502    }
503}
504
505impl AsRef<[u8]> for RecordedHistorySegment {
506    #[inline]
507    fn as_ref(&self) -> &[u8] {
508        RawRecord::slice_to_repr(&self.0)
509            .as_flattened()
510            .as_flattened()
511    }
512}
513
514impl AsMut<[u8]> for RecordedHistorySegment {
515    #[inline]
516    fn as_mut(&mut self) -> &mut [u8] {
517        RawRecord::slice_mut_to_repr(&mut self.0)
518            .as_flattened_mut()
519            .as_flattened_mut()
520    }
521}
522
523impl RecordedHistorySegment {
524    /// Number of raw records in one segment of recorded history.
525    pub const NUM_RAW_RECORDS: usize = 128;
526    /// Erasure coding rate for records during archiving process.
527    pub const ERASURE_CODING_RATE: (usize, usize) = (1, 2);
528    /// Size of recorded history segment in bytes.
529    ///
530    /// It includes half of the records (just source records) that will later be erasure coded and
531    /// together with corresponding commitments and witnesses will result in
532    /// [`ArchivedHistorySegment::NUM_PIECES`] [`Piece`]s of archival history.
533    pub const SIZE: usize = RawRecord::SIZE * Self::NUM_RAW_RECORDS;
534
535    /// Create boxed value without hitting stack overflow
536    #[inline]
537    pub fn new_boxed() -> Box<Self> {
538        // TODO: Should have been just `::new()`, but https://github.com/rust-lang/rust/issues/53827
539        // SAFETY: Data structure filled with zeroes is a valid invariant
540        unsafe { Box::<Self>::new_zeroed().assume_init() }
541    }
542}
543
544/// Archived history segment after archiving is applied.
545#[derive(Debug, Clone, Eq, PartialEq, Deref, DerefMut)]
546#[repr(transparent)]
547pub struct ArchivedHistorySegment(FlatPieces);
548
549impl Default for ArchivedHistorySegment {
550    #[inline]
551    fn default() -> Self {
552        Self(FlatPieces::new(Self::NUM_PIECES))
553    }
554}
555
556impl ArchivedHistorySegment {
557    /// Number of pieces in one segment of archived history.
558    pub const NUM_PIECES: usize = RecordedHistorySegment::NUM_RAW_RECORDS
559        * RecordedHistorySegment::ERASURE_CODING_RATE.1
560        / RecordedHistorySegment::ERASURE_CODING_RATE.0;
561    /// Size of archived history segment in bytes.
562    ///
563    /// It includes erasure coded [`crate::pieces::PieceArray`]s (both source and parity) that are
564    /// composed of [`crate::pieces::Record`]s together with corresponding commitments and
565    /// witnesses.
566    pub const SIZE: usize = Piece::SIZE * Self::NUM_PIECES;
567
568    /// Ensure archived history segment contains cheaply cloneable shared data.
569    ///
570    /// Internally archived history segment uses CoW mechanism and can store either mutable owned
571    /// data or data that is cheap to clone, calling this method will ensure further clones and
572    /// returned pieces will not result in additional memory allocations.
573    pub fn to_shared(self) -> Self {
574        Self(self.0.to_shared())
575    }
576}
subspace_core_primitives/segments.rs

subspace_core_primitives/
segments.rs
