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

ab_core_primitives/
pieces.rs
