ab_core_primitives/
pieces.rs

1//! Pieces-related data structures.
2
3#[cfg(feature = "alloc")]
4mod cow_bytes;
5#[cfg(feature = "alloc")]
6mod flat_pieces;
7#[cfg(feature = "alloc")]
8mod piece;
9
10#[cfg(feature = "alloc")]
11pub use crate::pieces::flat_pieces::FlatPieces;
12#[cfg(feature = "alloc")]
13pub use crate::pieces::piece::Piece;
14use crate::segments::{
15    LocalSegmentIndex, RecordedHistorySegment, SegmentIndex, SegmentPosition, SegmentRoot,
16    SuperSegmentIndex, SuperSegmentRoot,
17};
18use crate::shard::ShardIndex;
19#[cfg(feature = "serde")]
20use ::serde::{Deserialize, Deserializer, Serialize, Serializer};
21use ab_io_type::trivial_type::TrivialType;
22use ab_io_type::unaligned::Unaligned;
23use ab_merkle_tree::balanced::BalancedMerkleTree;
24#[cfg(feature = "alloc")]
25use alloc::boxed::Box;
26#[cfg(feature = "alloc")]
27use alloc::vec::Vec;
28use array_reshape::{Flatten, Unflatten};
29use blake3::OUT_LEN;
30use core::array::TryFromSliceError;
31use core::hash::Hash;
32use core::iter::Step;
33#[cfg(feature = "alloc")]
34use core::mem::MaybeUninit;
35#[cfg(feature = "alloc")]
36use core::slice;
37use core::{fmt, mem};
38use derive_more::{
39    Add, AddAssign, AsMut, AsRef, Deref, DerefMut, Display, Div, DivAssign, From, Into, Mul,
40    MulAssign, Sub, SubAssign,
41};
42#[cfg(feature = "scale-codec")]
43use parity_scale_codec::{Decode, Encode, MaxEncodedLen};
44#[cfg(feature = "serde")]
45use serde_big_array::BigArray;
46use transparent_wrapper::TransparentWrapper;
47
48/// Piece index
49#[derive(
50    Debug,
51    Display,
52    Default,
53    Copy,
54    Clone,
55    Ord,
56    PartialOrd,
57    Eq,
58    PartialEq,
59    Hash,
60    Add,
61    AddAssign,
62    Sub,
63    SubAssign,
64    Mul,
65    MulAssign,
66    Div,
67    DivAssign,
68)]
69#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
70#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
71#[repr(C)]
72pub struct PieceIndex(u64);
73
74impl Step for PieceIndex {
75    #[inline]
76    fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
77        u64::steps_between(&start.0, &end.0)
78    }
79
80    #[inline]
81    fn forward_checked(start: Self, count: usize) -> Option<Self> {
82        u64::forward_checked(start.0, count).map(Self)
83    }
84
85    #[inline(always)]
86    fn forward_overflowing(start: Self, count: usize) -> (Self, bool) {
87        let (n, overflowing) = u64::forward_overflowing(start.0, count);
88        (Self(n), overflowing)
89    }
90
91    #[inline]
92    fn backward_checked(start: Self, count: usize) -> Option<Self> {
93        u64::backward_checked(start.0, count).map(Self)
94    }
95
96    #[inline(always)]
97    fn backward_overflowing(start: Self, count: usize) -> (Self, bool) {
98        let (n, overflowing) = u64::backward_overflowing(start.0, count);
99        (Self(n), overflowing)
100    }
101}
102
103const impl From<u64> for PieceIndex {
104    #[inline(always)]
105    fn from(value: u64) -> Self {
106        Self(value)
107    }
108}
109
110const impl From<PieceIndex> for u64 {
111    #[inline(always)]
112    fn from(value: PieceIndex) -> Self {
113        value.0
114    }
115}
116
117impl PieceIndex {
118    /// Size in bytes.
119    pub const SIZE: usize = size_of::<u64>();
120    /// Piece index 0.
121    pub const ZERO: PieceIndex = PieceIndex(0);
122    /// Piece index 1.
123    pub const ONE: PieceIndex = PieceIndex(1);
124
125    /// Create a piece index from bytes.
126    #[inline]
127    pub const fn from_bytes(bytes: [u8; Self::SIZE]) -> Self {
128        Self(u64::from_le_bytes(bytes))
129    }
130
131    /// Convert a piece index to bytes.
132    #[inline]
133    pub const fn to_bytes(self) -> [u8; Self::SIZE] {
134        self.0.to_le_bytes()
135    }
136
137    /// Segment index piece index corresponds to
138    #[inline]
139    pub const fn segment_index(&self) -> SegmentIndex {
140        SegmentIndex::from(self.0 / RecordedHistorySegment::NUM_PIECES as u64)
141    }
142
143    /// Position of a piece in a segment
144    #[inline]
145    pub fn position(&self) -> PiecePosition {
146        PiecePosition::from((self.0 % RecordedHistorySegment::NUM_PIECES as u64) as u8)
147    }
148}
149
150const {
151    // Assert that `u8` represents `PiecePosition` perfectly
152    assert!(RecordedHistorySegment::NUM_PIECES == usize::from(u8::MAX) + 1);
153}
154
155/// Piece position in a segment
156#[derive(
157    Debug,
158    Display,
159    Default,
160    Copy,
161    Clone,
162    Ord,
163    PartialOrd,
164    Eq,
165    PartialEq,
166    Hash,
167    From,
168    Into,
169    TrivialType,
170)]
171#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
172#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
173#[repr(C)]
174pub struct PiecePosition(u8);
175
176impl Step for PiecePosition {
177    #[inline]
178    fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
179        u8::steps_between(&start.0, &end.0)
180    }
181
182    #[inline]
183    fn forward_checked(start: Self, count: usize) -> Option<Self> {
184        u8::forward_checked(start.0, count).map(Self)
185    }
186
187    #[inline(always)]
188    fn forward_overflowing(start: Self, count: usize) -> (Self, bool) {
189        let (n, overflowing) = u8::forward_overflowing(start.0, count);
190        (Self(n), overflowing)
191    }
192
193    #[inline]
194    fn backward_checked(start: Self, count: usize) -> Option<Self> {
195        u8::backward_checked(start.0, count).map(Self)
196    }
197
198    #[inline(always)]
199    fn backward_overflowing(start: Self, count: usize) -> (Self, bool) {
200        let (n, overflowing) = u8::backward_overflowing(start.0, count);
201        (Self(n), overflowing)
202    }
203}
204
205impl From<PiecePosition> for u16 {
206    #[inline]
207    fn from(original: PiecePosition) -> Self {
208        Self::from(original.0)
209    }
210}
211
212impl From<PiecePosition> for u32 {
213    #[inline]
214    fn from(original: PiecePosition) -> Self {
215        Self::from(original.0)
216    }
217}
218
219impl From<PiecePosition> for u64 {
220    #[inline]
221    fn from(original: PiecePosition) -> Self {
222        Self::from(original.0)
223    }
224}
225
226impl From<PiecePosition> for usize {
227    #[inline]
228    fn from(original: PiecePosition) -> Self {
229        usize::from(original.0)
230    }
231}
232
233/// Piece offset in a sector
234#[derive(
235    Debug,
236    Display,
237    Default,
238    Copy,
239    Clone,
240    Ord,
241    PartialOrd,
242    Eq,
243    PartialEq,
244    Hash,
245    From,
246    Into,
247    Add,
248    AddAssign,
249    Sub,
250    SubAssign,
251    Mul,
252    MulAssign,
253    Div,
254    DivAssign,
255    TrivialType,
256)]
257#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
258#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
259#[repr(C)]
260pub struct PieceOffset(u16);
261
262impl Step for PieceOffset {
263    #[inline]
264    fn steps_between(start: &Self, end: &Self) -> (usize, Option<usize>) {
265        u16::steps_between(&start.0, &end.0)
266    }
267
268    #[inline]
269    fn forward_checked(start: Self, count: usize) -> Option<Self> {
270        u16::forward_checked(start.0, count).map(Self)
271    }
272
273    #[inline(always)]
274    fn forward_overflowing(start: Self, count: usize) -> (Self, bool) {
275        let (n, overflowing) = u16::forward_overflowing(start.0, count);
276        (Self(n), overflowing)
277    }
278
279    #[inline]
280    fn backward_checked(start: Self, count: usize) -> Option<Self> {
281        u16::backward_checked(start.0, count).map(Self)
282    }
283
284    #[inline(always)]
285    fn backward_overflowing(start: Self, count: usize) -> (Self, bool) {
286        let (n, overflowing) = u16::backward_overflowing(start.0, count);
287        (Self(n), overflowing)
288    }
289}
290
291impl From<PieceOffset> for u32 {
292    #[inline]
293    fn from(original: PieceOffset) -> Self {
294        Self::from(original.0)
295    }
296}
297
298impl From<PieceOffset> for u64 {
299    #[inline]
300    fn from(original: PieceOffset) -> Self {
301        Self::from(original.0)
302    }
303}
304
305impl From<PieceOffset> for usize {
306    #[inline]
307    fn from(original: PieceOffset) -> Self {
308        usize::from(original.0)
309    }
310}
311
312impl PieceOffset {
313    /// Piece index 0
314    pub const ZERO: Self = Self(0);
315    /// Piece index 1
316    pub const ONE: Self = Self(1);
317    /// Size in bytes
318    pub const SIZE: usize = size_of::<u16>();
319
320    /// Convert piece offset to bytes
321    #[inline]
322    pub const fn to_bytes(self) -> [u8; Self::SIZE] {
323        self.0.to_le_bytes()
324    }
325}
326
327/// Chunk contained in a record
328#[derive(
329    Default,
330    Copy,
331    Clone,
332    Eq,
333    PartialEq,
334    Ord,
335    PartialOrd,
336    Hash,
337    From,
338    Into,
339    AsRef,
340    AsMut,
341    Deref,
342    DerefMut,
343    TrivialType,
344    TransparentWrapper,
345)]
346#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
347#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
348#[cfg_attr(feature = "serde", serde(transparent))]
349#[repr(C)]
350pub struct RecordChunk([u8; RecordChunk::SIZE]);
351
352impl fmt::Debug for RecordChunk {
353    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
354        for byte in self.0 {
355            write!(f, "{byte:02x}")?;
356        }
357        Ok(())
358    }
359}
360
361impl RecordChunk {
362    /// Size of the chunk in bytes
363    pub const SIZE: usize = 32;
364
365    /// Convenient conversion from slice to underlying representation for efficiency purposes
366    #[inline]
367    pub fn slice_to_repr(value: &[Self]) -> &[[u8; Self::SIZE]] {
368        Self::peel_slice(value)
369    }
370
371    /// Convenient conversion from slice of underlying representation for efficiency purposes
372    #[inline]
373    pub fn slice_from_repr(value: &[[u8; Self::SIZE]]) -> &[Self] {
374        Self::wrap_slice(value)
375    }
376
377    /// Convenient conversion from mutable slice to underlying representation for efficiency
378    /// purposes
379    #[inline]
380    pub fn slice_mut_to_repr(value: &mut [Self]) -> &mut [[u8; Self::SIZE]] {
381        Self::peel_slice_mut(value)
382    }
383
384    /// Convenient conversion from mutable slice of underlying representation for efficiency
385    /// purposes
386    #[inline]
387    pub fn slice_mut_from_repr(value: &mut [[u8; Self::SIZE]]) -> &mut [Self] {
388        Self::wrap_slice_mut(value)
389    }
390}
391
392/// Record contained within a piece.
393///
394/// NOTE: This is a stack-allocated data structure and can cause stack overflow!
395#[derive(Copy, Clone, Eq, PartialEq, Deref, DerefMut, TrivialType, TransparentWrapper)]
396#[repr(C)]
397pub struct Record([[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]);
398
399impl fmt::Debug for Record {
400    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
401        for byte in self.0.as_flattened() {
402            write!(f, "{byte:02x}")?;
403        }
404        Ok(())
405    }
406}
407
408impl AsRef<[u8]> for Record {
409    #[inline]
410    fn as_ref(&self) -> &[u8] {
411        self.0.as_flattened()
412    }
413}
414
415impl AsRef<[u8; Record::SIZE]> for Record {
416    #[inline(always)]
417    fn as_ref(&self) -> &[u8; Record::SIZE] {
418        self.as_bytes()
419    }
420}
421
422impl AsMut<[u8; Record::SIZE]> for Record {
423    #[inline(always)]
424    fn as_mut(&mut self) -> &mut [u8; Record::SIZE] {
425        // SAFETY: `Record` is a plain byte array, any bit pattern is valid for it
426        unsafe { self.as_bytes_mut() }
427    }
428}
429
430impl AsMut<[u8]> for Record {
431    #[inline]
432    fn as_mut(&mut self) -> &mut [u8] {
433        self.0.as_flattened_mut()
434    }
435}
436
437impl<'a> From<&'a Record> for &'a [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS] {
438    #[inline]
439    fn from(value: &'a Record) -> Self {
440        value.peel_ref()
441    }
442}
443
444impl<'a> From<&'a [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]> for &'a Record {
445    #[inline]
446    fn from(value: &'a [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]) -> Self {
447        Record::wrap_ref(value)
448    }
449}
450
451impl<'a> From<&'a mut Record> for &'a mut [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS] {
452    #[inline]
453    fn from(value: &'a mut Record) -> Self {
454        value.peel_mut()
455    }
456}
457
458impl<'a> From<&'a mut [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]> for &'a mut Record {
459    #[inline]
460    fn from(value: &'a mut [[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]) -> Self {
461        Record::wrap_mut(value)
462    }
463}
464
465impl Record {
466    /// Number of chunks within one record.
467    pub const NUM_CHUNKS: usize = 2usize.pow(15);
468    /// Number of s-buckets contained within one sector record.
469    ///
470    /// Essentially we chunk records and erasure code them.
471    pub const NUM_S_BUCKETS: usize = Record::NUM_CHUNKS
472        * RecordedHistorySegment::ERASURE_CODING_RATE.1
473        / RecordedHistorySegment::ERASURE_CODING_RATE.0;
474    /// Size of a segment record, it is guaranteed to be a multiple of [`RecordChunk::SIZE`]
475    pub const SIZE: usize = RecordChunk::SIZE * Record::NUM_CHUNKS;
476
477    /// Create boxed value without hitting stack overflow
478    #[inline]
479    #[cfg(feature = "alloc")]
480    pub fn new_boxed() -> Box<Self> {
481        // TODO: Should have been just `::new()`, but https://github.com/rust-lang/rust/issues/53827
482        // SAFETY: Data structure filled with zeroes is a valid invariant
483        unsafe { Box::new_zeroed().assume_init() }
484    }
485
486    /// Create vector filled with zeroed records without hitting stack overflow
487    #[inline]
488    #[cfg(feature = "alloc")]
489    pub fn new_zero_vec(length: usize) -> Vec<Self> {
490        // TODO: Should have been just `vec![Self::default(); length]`, but
491        //  https://github.com/rust-lang/rust/issues/53827
492        let mut records = Vec::with_capacity(length);
493        {
494            let slice = records.spare_capacity_mut();
495            // SAFETY: Same memory layout due to `#[repr(C)]` on `Record` and
496            // `MaybeUninit<[[T; M]; N]>` is guaranteed to have the same layout as
497            // `[[MaybeUninit<T>; M]; N]`
498            let slice = unsafe {
499                slice::from_raw_parts_mut(
500                    slice
501                        .as_mut_ptr()
502                        .cast::<[[MaybeUninit<u8>; RecordChunk::SIZE]; Record::NUM_CHUNKS]>(),
503                    length,
504                )
505            };
506            for byte in slice.as_flattened_mut().as_flattened_mut() {
507                byte.write(0);
508            }
509        }
510        // SAFETY: All values are initialized above.
511        unsafe {
512            records.set_len(records.capacity());
513        }
514
515        records
516    }
517
518    /// Convenient conversion from slice of record to underlying representation for efficiency
519    /// purposes.
520    #[inline(always)]
521    pub fn slice_to_repr(value: &[Self]) -> &[[[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]] {
522        Self::peel_slice(value)
523    }
524
525    /// Convenient conversion from slice of underlying representation to record for efficiency
526    /// purposes.
527    #[inline(always)]
528    pub fn slice_from_repr(value: &[[[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]]) -> &[Self] {
529        Self::wrap_slice(value)
530    }
531
532    /// Convenient conversion from mutable slice of record to underlying representation for
533    /// efficiency purposes.
534    #[inline(always)]
535    pub fn slice_mut_to_repr(
536        value: &mut [Self],
537    ) -> &mut [[[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]] {
538        Self::peel_slice_mut(value)
539    }
540
541    /// Convenient conversion from mutable slice of underlying representation to record for
542    /// efficiency purposes.
543    #[inline(always)]
544    pub fn slice_mut_from_repr(
545        value: &mut [[[u8; RecordChunk::SIZE]; Record::NUM_CHUNKS]],
546    ) -> &mut [Self] {
547        Self::wrap_slice_mut(value)
548    }
549
550    /// Derive source chunks root on-demand
551    #[inline(always)]
552    pub fn source_chunks_root(&self) -> RecordChunksRoot {
553        RecordChunksRoot(BalancedMerkleTree::compute_root_only(self))
554    }
555}
556
557/// Root of the record contained within a piece.
558///
559/// This is a Merkle Tree root of the roots of source and parity record chunks.
560#[derive(
561    Copy, Clone, Eq, PartialEq, Hash, Deref, DerefMut, From, Into, TrivialType, TransparentWrapper,
562)]
563#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
564#[repr(C)]
565pub struct RecordRoot([u8; RecordRoot::SIZE]);
566
567impl fmt::Debug for RecordRoot {
568    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
569        for byte in self.0 {
570            write!(f, "{byte:02x}")?;
571        }
572        Ok(())
573    }
574}
575
576#[cfg(feature = "serde")]
577#[derive(Serialize, Deserialize)]
578#[serde(transparent)]
579struct RecordRootBinary(#[serde(with = "BigArray")] [u8; RecordRoot::SIZE]);
580
581#[cfg(feature = "serde")]
582#[derive(Serialize, Deserialize)]
583#[serde(transparent)]
584struct RecordRootHex(#[serde(with = "hex")] [u8; RecordRoot::SIZE]);
585
586#[cfg(feature = "serde")]
587impl Serialize for RecordRoot {
588    #[inline]
589    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
590    where
591        S: Serializer,
592    {
593        if serializer.is_human_readable() {
594            RecordRootHex(self.0).serialize(serializer)
595        } else {
596            RecordRootBinary(self.0).serialize(serializer)
597        }
598    }
599}
600
601#[cfg(feature = "serde")]
602impl<'de> Deserialize<'de> for RecordRoot {
603    #[inline]
604    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
605    where
606        D: Deserializer<'de>,
607    {
608        Ok(Self(if deserializer.is_human_readable() {
609            RecordRootHex::deserialize(deserializer)?.0
610        } else {
611            RecordRootBinary::deserialize(deserializer)?.0
612        }))
613    }
614}
615
616impl Default for RecordRoot {
617    #[inline]
618    fn default() -> Self {
619        Self([0; _])
620    }
621}
622
623impl TryFrom<&[u8]> for RecordRoot {
624    type Error = TryFromSliceError;
625
626    #[inline]
627    fn try_from(slice: &[u8]) -> Result<Self, Self::Error> {
628        <[u8; Self::SIZE]>::try_from(slice).map(Self)
629    }
630}
631
632impl AsRef<[u8]> for RecordRoot {
633    #[inline]
634    fn as_ref(&self) -> &[u8] {
635        &self.0
636    }
637}
638
639impl AsMut<[u8]> for RecordRoot {
640    #[inline]
641    fn as_mut(&mut self) -> &mut [u8] {
642        &mut self.0
643    }
644}
645
646impl<'a> From<&'a RecordRoot> for &'a [u8; RecordRoot::SIZE] {
647    #[inline]
648    fn from(value: &'a RecordRoot) -> Self {
649        value.peel_ref()
650    }
651}
652
653impl<'a> From<&'a [u8; RecordRoot::SIZE]> for &'a RecordRoot {
654    #[inline]
655    fn from(value: &'a [u8; RecordRoot::SIZE]) -> Self {
656        RecordRoot::wrap_ref(value)
657    }
658}
659
660impl<'a> From<&'a mut RecordRoot> for &'a mut [u8; RecordRoot::SIZE] {
661    #[inline]
662    fn from(value: &'a mut RecordRoot) -> Self {
663        value.peel_mut()
664    }
665}
666
667impl<'a> From<&'a mut [u8; RecordRoot::SIZE]> for &'a mut RecordRoot {
668    #[inline]
669    fn from(value: &'a mut [u8; RecordRoot::SIZE]) -> Self {
670        RecordRoot::wrap_mut(value)
671    }
672}
673
674impl RecordRoot {
675    /// Size of record root in bytes.
676    pub const SIZE: usize = 32;
677
678    /// Validate record root hash produced by the archiver
679    pub fn is_valid(
680        &self,
681        segment_root: &SegmentRoot,
682        record_proof: &RecordProof,
683        position: PiecePosition,
684    ) -> bool {
685        BalancedMerkleTree::<{ RecordedHistorySegment::NUM_PIECES }>::verify(
686            segment_root,
687            record_proof,
688            usize::from(position),
689            self.0,
690        )
691    }
692}
693
694/// Root of source or parity record chunks
695#[derive(
696    Copy, Clone, Eq, PartialEq, Hash, Deref, DerefMut, From, Into, TrivialType, TransparentWrapper,
697)]
698#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
699#[repr(C)]
700pub struct RecordChunksRoot([u8; RecordChunksRoot::SIZE]);
701
702impl fmt::Debug for RecordChunksRoot {
703    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
704        for byte in self.0 {
705            write!(f, "{byte:02x}")?;
706        }
707        Ok(())
708    }
709}
710
711#[cfg(feature = "serde")]
712#[derive(Serialize, Deserialize)]
713#[serde(transparent)]
714struct RecordChunksRootBinary(#[serde(with = "BigArray")] [u8; RecordChunksRoot::SIZE]);
715
716#[cfg(feature = "serde")]
717#[derive(Serialize, Deserialize)]
718#[serde(transparent)]
719struct RecordChunksRootHex(#[serde(with = "hex")] [u8; RecordChunksRoot::SIZE]);
720
721#[cfg(feature = "serde")]
722impl Serialize for RecordChunksRoot {
723    #[inline]
724    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
725    where
726        S: Serializer,
727    {
728        if serializer.is_human_readable() {
729            RecordChunksRootHex(self.0).serialize(serializer)
730        } else {
731            RecordChunksRootBinary(self.0).serialize(serializer)
732        }
733    }
734}
735
736#[cfg(feature = "serde")]
737impl<'de> Deserialize<'de> for RecordChunksRoot {
738    #[inline]
739    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
740    where
741        D: Deserializer<'de>,
742    {
743        Ok(Self(if deserializer.is_human_readable() {
744            RecordChunksRootHex::deserialize(deserializer)?.0
745        } else {
746            RecordChunksRootBinary::deserialize(deserializer)?.0
747        }))
748    }
749}
750
751impl Default for RecordChunksRoot {
752    #[inline]
753    fn default() -> Self {
754        Self([0; _])
755    }
756}
757
758impl TryFrom<&[u8]> for RecordChunksRoot {
759    type Error = TryFromSliceError;
760
761    #[inline]
762    fn try_from(slice: &[u8]) -> Result<Self, Self::Error> {
763        <[u8; Self::SIZE]>::try_from(slice).map(Self)
764    }
765}
766
767impl AsRef<[u8]> for RecordChunksRoot {
768    #[inline]
769    fn as_ref(&self) -> &[u8] {
770        &self.0
771    }
772}
773
774impl AsMut<[u8]> for RecordChunksRoot {
775    #[inline]
776    fn as_mut(&mut self) -> &mut [u8] {
777        &mut self.0
778    }
779}
780
781impl<'a> From<&'a RecordChunksRoot> for &'a [u8; RecordChunksRoot::SIZE] {
782    #[inline]
783    fn from(value: &'a RecordChunksRoot) -> Self {
784        value.peel_ref()
785    }
786}
787
788impl<'a> From<&'a [u8; RecordChunksRoot::SIZE]> for &'a RecordChunksRoot {
789    #[inline]
790    fn from(value: &'a [u8; RecordChunksRoot::SIZE]) -> Self {
791        RecordChunksRoot::wrap_ref(value)
792    }
793}
794
795impl<'a> From<&'a mut RecordChunksRoot> for &'a mut [u8; RecordChunksRoot::SIZE] {
796    #[inline]
797    fn from(value: &'a mut RecordChunksRoot) -> Self {
798        value.peel_mut()
799    }
800}
801
802impl<'a> From<&'a mut [u8; RecordChunksRoot::SIZE]> for &'a mut RecordChunksRoot {
803    #[inline]
804    fn from(value: &'a mut [u8; RecordChunksRoot::SIZE]) -> Self {
805        RecordChunksRoot::wrap_mut(value)
806    }
807}
808
809impl RecordChunksRoot {
810    /// Size of record chunks root in bytes.
811    pub const SIZE: usize = 32;
812}
813
814/// Proof that the record (root) belongs to a segment
815#[derive(
816    Copy, Clone, Eq, PartialEq, Hash, Deref, DerefMut, From, Into, TrivialType, TransparentWrapper,
817)]
818#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
819#[repr(C)]
820pub struct RecordProof([[u8; OUT_LEN]; RecordProof::NUM_HASHES]);
821
822impl fmt::Debug for RecordProof {
823    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
824        write!(f, "[")?;
825        for hash in self.0 {
826            for byte in hash {
827                write!(f, "{byte:02x}")?;
828            }
829            write!(f, ", ")?;
830        }
831        write!(f, "]")?;
832        Ok(())
833    }
834}
835
836#[cfg(feature = "serde")]
837#[derive(Serialize, Deserialize)]
838#[serde(transparent)]
839struct RecordProofBinary([[u8; OUT_LEN]; RecordProof::NUM_HASHES]);
840
841#[cfg(feature = "serde")]
842#[derive(Serialize, Deserialize, TransparentWrapper)]
843#[serde(transparent)]
844#[repr(transparent)]
845struct RecordProofHexHash(#[serde(with = "hex")] [u8; OUT_LEN]);
846
847#[cfg(feature = "serde")]
848#[derive(Serialize, Deserialize)]
849#[serde(transparent)]
850struct RecordProofHex([RecordProofHexHash; RecordProof::NUM_HASHES]);
851
852#[cfg(feature = "serde")]
853impl Serialize for RecordProof {
854    #[inline]
855    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
856    where
857        S: Serializer,
858    {
859        if serializer.is_human_readable() {
860            RecordProofHex(<[RecordProofHexHash; Self::NUM_HASHES]>::wrap(self.0))
861                .serialize(serializer)
862        } else {
863            RecordProofBinary(self.0).serialize(serializer)
864        }
865    }
866}
867
868#[cfg(feature = "serde")]
869impl<'de> Deserialize<'de> for RecordProof {
870    #[inline]
871    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
872    where
873        D: Deserializer<'de>,
874    {
875        Ok(Self(if deserializer.is_human_readable() {
876            RecordProofHex::deserialize(deserializer)?.0.peel()
877        } else {
878            RecordProofBinary::deserialize(deserializer)?.0
879        }))
880    }
881}
882
883impl Default for RecordProof {
884    #[inline]
885    fn default() -> Self {
886        Self([[0; OUT_LEN]; _])
887    }
888}
889
890impl AsRef<[u8]> for RecordProof {
891    #[inline]
892    fn as_ref(&self) -> &[u8] {
893        self.0.as_flattened()
894    }
895}
896
897impl AsMut<[u8]> for RecordProof {
898    #[inline]
899    fn as_mut(&mut self) -> &mut [u8] {
900        self.0.as_flattened_mut()
901    }
902}
903
904impl<'a> From<&'a RecordProof> for &'a [u8; RecordProof::SIZE] {
905    #[inline]
906    fn from(value: &'a RecordProof) -> Self {
907        value.peel_ref().flatten_ref()
908    }
909}
910
911impl<'a> From<&'a [u8; RecordProof::SIZE]> for &'a RecordProof {
912    #[inline]
913    fn from(value: &'a [u8; RecordProof::SIZE]) -> Self {
914        RecordProof::wrap_ref(value.unflatten_ref())
915    }
916}
917
918impl<'a> From<&'a mut RecordProof> for &'a mut [u8; RecordProof::SIZE] {
919    #[inline]
920    fn from(value: &'a mut RecordProof) -> Self {
921        value.peel_mut().flatten_mut()
922    }
923}
924
925impl<'a> From<&'a mut [u8; RecordProof::SIZE]> for &'a mut RecordProof {
926    #[inline]
927    fn from(value: &'a mut [u8; RecordProof::SIZE]) -> Self {
928        RecordProof::wrap_mut(value.unflatten_mut())
929    }
930}
931
932impl RecordProof {
933    /// Size of record proof in bytes
934    pub const SIZE: usize = OUT_LEN * Self::NUM_HASHES;
935    const NUM_HASHES: usize = RecordedHistorySegment::NUM_PIECES.ilog2() as usize;
936}
937
938/// Proof that the segment belongs to a super segment
939#[derive(
940    Copy, Clone, Eq, PartialEq, Hash, Deref, DerefMut, From, Into, TrivialType, TransparentWrapper,
941)]
942#[cfg_attr(feature = "scale-codec", derive(Encode, Decode, MaxEncodedLen))]
943#[repr(C)]
944pub struct SegmentProof([[u8; OUT_LEN]; SegmentProof::NUM_HASHES]);
945
946impl fmt::Debug for SegmentProof {
947    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
948        write!(f, "[")?;
949        for hash in self.0 {
950            for byte in hash {
951                write!(f, "{byte:02x}")?;
952            }
953            write!(f, ", ")?;
954        }
955        write!(f, "]")?;
956        Ok(())
957    }
958}
959
960#[cfg(feature = "serde")]
961#[derive(Serialize, Deserialize)]
962#[serde(transparent)]
963struct SegmentProofBinary([[u8; OUT_LEN]; SegmentProof::NUM_HASHES]);
964
965#[cfg(feature = "serde")]
966#[derive(Serialize, Deserialize, TransparentWrapper)]
967#[serde(transparent)]
968#[repr(transparent)]
969struct SegmentProofHexHash(#[serde(with = "hex")] [u8; OUT_LEN]);
970
971#[cfg(feature = "serde")]
972#[derive(Serialize, Deserialize)]
973#[serde(transparent)]
974struct SegmentProofHex([SegmentProofHexHash; SegmentProof::NUM_HASHES]);
975
976#[cfg(feature = "serde")]
977impl Serialize for SegmentProof {
978    #[inline]
979    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
980    where
981        S: Serializer,
982    {
983        if serializer.is_human_readable() {
984            SegmentProofHex(<[SegmentProofHexHash; Self::NUM_HASHES]>::wrap(self.0))
985                .serialize(serializer)
986        } else {
987            SegmentProofBinary(self.0).serialize(serializer)
988        }
989    }
990}
991
992#[cfg(feature = "serde")]
993impl<'de> Deserialize<'de> for SegmentProof {
994    #[inline]
995    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
996    where
997        D: Deserializer<'de>,
998    {
999        Ok(Self(if deserializer.is_human_readable() {
1000            SegmentProofHex::deserialize(deserializer)?.0.peel()
1001        } else {
1002            SegmentProofBinary::deserialize(deserializer)?.0
1003        }))
1004    }
1005}
1006
1007impl Default for SegmentProof {
1008    #[inline]
1009    fn default() -> Self {
1010        Self([[0; OUT_LEN]; _])
1011    }
1012}
1013
1014impl AsRef<[u8]> for SegmentProof {
1015    #[inline]
1016    fn as_ref(&self) -> &[u8] {
1017        self.0.as_flattened()
1018    }
1019}
1020
1021impl AsMut<[u8]> for SegmentProof {
1022    #[inline]
1023    fn as_mut(&mut self) -> &mut [u8] {
1024        self.0.as_flattened_mut()
1025    }
1026}
1027
1028impl<'a> From<&'a SegmentProof> for &'a [u8; SegmentProof::SIZE] {
1029    #[inline]
1030    fn from(value: &'a SegmentProof) -> Self {
1031        value.peel_ref().flatten_ref()
1032    }
1033}
1034
1035impl<'a> From<&'a [u8; SegmentProof::SIZE]> for &'a SegmentProof {
1036    #[inline]
1037    fn from(value: &'a [u8; SegmentProof::SIZE]) -> Self {
1038        SegmentProof::wrap_ref(value.unflatten_ref())
1039    }
1040}
1041
1042impl<'a> From<&'a mut SegmentProof> for &'a mut [u8; SegmentProof::SIZE] {
1043    #[inline]
1044    fn from(value: &'a mut SegmentProof) -> Self {
1045        value.peel_mut().flatten_mut()
1046    }
1047}
1048
1049impl<'a> From<&'a mut [u8; SegmentProof::SIZE]> for &'a mut SegmentProof {
1050    #[inline]
1051    fn from(value: &'a mut [u8; SegmentProof::SIZE]) -> Self {
1052        SegmentProof::wrap_mut(value.unflatten_mut())
1053    }
1054}
1055
1056impl SegmentProof {
1057    /// Size of segment proof in bytes
1058    pub const SIZE: usize = OUT_LEN * Self::NUM_HASHES;
1059    const NUM_HASHES: usize = SuperSegmentRoot::MAX_SEGMENTS.next_power_of_two().ilog2() as usize;
1060}
1061
1062/// Header for a piece of archival history.
1063///
1064/// Primarily contains information needed for piece verification.
1065#[derive(Debug, Default, Copy, Clone, Eq, PartialEq, TrivialType)]
1066#[cfg_attr(feature = "scale-codec", derive(Encode, Decode))]
1067#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
1068#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
1069#[repr(C)]
1070pub struct PieceHeader {
1071    /// Shard index
1072    pub shard_index: Unaligned<ShardIndex>,
1073    /// Local segment index
1074    pub local_segment_index: Unaligned<LocalSegmentIndex>,
1075    /// Super segment index
1076    pub super_segment_index: Unaligned<SuperSegmentIndex>,
1077    /// Position of the segment in the super segment
1078    pub segment_position: Unaligned<SegmentPosition>,
1079    /// Segment root
1080    pub segment_root: SegmentRoot,
1081    /// Segment proof
1082    pub segment_proof: SegmentProof,
1083    /// Root of parity record chunks.
1084    ///
1085    /// Technically redundant, but helps to avoid repeating erasure coding during verification.
1086    pub parity_chunks_root: RecordChunksRoot,
1087    /// Proof that the record (root) belongs to a segment
1088    pub record_proof: RecordProof,
1089}
1090
1091const {
1092    // Must have minimal alignment for various conversions to/from bytes
1093    assert!(align_of::<PieceHeader>() == 1);
1094}
1095
1096/// A piece of archival history.
1097///
1098/// This version is allocated on the stack, for a heap-allocated piece that can be moved around
1099/// efficiently, see [`Piece`].
1100///
1101/// Internally, a piece contains a record, supplementary record chunk root, and a proof proving this
1102/// piece belongs to can be used to verify that a piece belongs to the actual archival history of
1103/// the blockchain.
1104#[derive(Debug, Copy, Clone, Eq, PartialEq, TrivialType)]
1105#[repr(C)]
1106pub struct InnerPiece {
1107    /// Piece header
1108    pub header: PieceHeader,
1109    /// Record contained within a piece
1110    pub record: Record,
1111}
1112
1113const {
1114    // Must have minimal alignment for various conversions to/from bytes
1115    assert!(align_of::<InnerPiece>() == 1);
1116}
1117
1118impl InnerPiece {
1119    /// Size of a piece (in bytes)
1120    pub const SIZE: usize = size_of::<Self>();
1121
1122    /// Create boxed value without hitting stack overflow
1123    #[inline]
1124    #[cfg(feature = "alloc")]
1125    pub fn new_boxed() -> Box<Self> {
1126        // TODO: Should have been just `::new()`, but https://github.com/rust-lang/rust/issues/53827
1127        // SAFETY: Data structure filled with zeroes is a valid invariant
1128        unsafe { Box::<Self>::new_zeroed().assume_init() }
1129    }
1130
1131    /// Check whether the piece is valid against the matching super segment root
1132    pub fn is_valid(
1133        &self,
1134        super_segment_root: &SuperSegmentRoot,
1135        num_segments: u32,
1136        position: PiecePosition,
1137    ) -> bool {
1138        if !self.header.segment_root.is_valid(
1139            self.header.shard_index.as_inner(),
1140            self.header.local_segment_index.as_inner(),
1141            self.header.segment_position.as_inner(),
1142            &self.header.segment_proof,
1143            num_segments,
1144            super_segment_root,
1145        ) {
1146            return false;
1147        }
1148        self.record_root().is_valid(
1149            &self.header.segment_root,
1150            &self.header.record_proof,
1151            position,
1152        )
1153    }
1154
1155    /// Root of the record contained within a piece.
1156    ///
1157    /// It is re-derived on every call of this function.
1158    #[inline]
1159    pub fn record_root(&self) -> RecordRoot {
1160        let record_merkle_tree_root = BalancedMerkleTree::compute_root_only(&[
1161            *self.record.source_chunks_root(),
1162            *self.header.parity_chunks_root,
1163        ]);
1164
1165        RecordRoot::from(record_merkle_tree_root)
1166    }
1167
1168    /// Convenient conversion from slice of pieces to underlying representation for efficiency
1169    /// purposes.
1170    #[inline]
1171    pub fn slice_to_repr(value: &[Self]) -> &[[u8; Self::SIZE]] {
1172        // SAFETY: `InnerPiece` is `#[repr(C)]` with alignment of 1 (checked above), it consists of
1173        // integers and byte arrays only, so it has no padding and any bit pattern is valid
1174        unsafe { mem::transmute(value) }
1175    }
1176
1177    /// Convenient conversion from slice of underlying representation to pieces for efficiency
1178    /// purposes.
1179    #[inline]
1180    pub fn slice_from_repr(value: &[[u8; Self::SIZE]]) -> &[Self] {
1181        // SAFETY: `InnerPiece` is `#[repr(C)]` with alignment of 1 (checked above), it consists of
1182        // integers and byte arrays only, so it has no padding and any bit pattern is valid
1183        unsafe { mem::transmute(value) }
1184    }
1185
1186    /// Convenient conversion from mutable slice of pieces to underlying representation for
1187    /// efficiency purposes.
1188    #[inline]
1189    pub fn slice_mut_to_repr(value: &mut [Self]) -> &mut [[u8; Self::SIZE]] {
1190        // SAFETY: `InnerPiece` is `#[repr(C)]` with alignment of 1 (checked above), it consists of
1191        // integers and byte arrays only, so it has no padding and any bit pattern is valid
1192        unsafe { mem::transmute(value) }
1193    }
1194
1195    /// Convenient conversion from mutable slice of underlying representation to pieces for
1196    /// efficiency purposes.
1197    #[inline]
1198    pub fn slice_mut_from_repr(value: &mut [[u8; Self::SIZE]]) -> &mut [Self] {
1199        // SAFETY: `InnerPiece` is `#[repr(C)]` with alignment of 1 (checked above), it consists of
1200        // integers and byte arrays only, so it has no padding and any bit pattern is valid
1201        unsafe { mem::transmute(value) }
1202    }
1203}
ab_core_primitives/pieces.rs

ab_core_primitives/
pieces.rs
