decds_lib/
chunk.rs

1use crate::{chunkset::ChunkSet, consts::DECDS_BINCODE_CONFIG, errors::DecdsError, merkle_tree::MerkleTree};
2use serde::{Deserialize, Serialize};
3
4/// Represents a fixed-size (1MB = 2^20 bytes) data chunk within a chunkset in erasure-coded form.
5/// It contains metadata about its origin and the RLNC erasure-coded data.
6#[derive(Clone, Serialize, Deserialize, Debug, PartialEq)]
7pub(crate) struct Chunk {
8    chunkset_id: usize,
9    chunk_id: usize,
10    erasure_coded_data: Vec<u8>,
11}
12
13impl Chunk {
14    pub const BYTE_LENGTH: usize = 1usize << 20;
15
16    /// Creates a new `Chunk` instance.
17    ///
18    /// # Arguments
19    ///
20    /// * `chunkset_id` - The ID of the chunkset this chunk belongs to.
21    /// * `chunk_id` - The global ID of this chunk.
22    /// * `erasure_coded_data` - The RLNC erasure-coded data payload of the chunk.
23    ///
24    /// # Returns
25    ///
26    /// Returns a new `Chunk` instance.
27    pub fn new(chunkset_id: usize, chunk_id: usize, erasure_coded_data: Vec<u8>) -> Self {
28        Chunk {
29            chunkset_id,
30            chunk_id,
31            erasure_coded_data,
32        }
33    }
34
35    /// Computes the BLAKE3 digest of the byte serialized representation of this chunk.
36    ///
37    /// # Returns
38    ///
39    /// A `blake3::Hash` representing the digest of the chunk.
40    pub fn digest(&self) -> blake3::Hash {
41        blake3::Hasher::new()
42            .update(&self.chunkset_id.to_le_bytes())
43            .update(&self.chunk_id.to_le_bytes())
44            .update(&self.erasure_coded_data)
45            .finalize()
46    }
47}
48
49/// Represents a `Chunk` augmented with a Merkle proof of its inclusion in the original blob.
50/// This structure is used for verifiable data retrieval and reconstruction.
51#[derive(Clone, Serialize, Deserialize, Debug, PartialEq)]
52pub struct ProofCarryingChunk {
53    chunk: Chunk,
54    proof: Vec<blake3::Hash>,
55}
56
57impl ProofCarryingChunk {
58    /// Creates a new `ProofCarryingChunk` instance.
59    ///
60    /// # Arguments
61    ///
62    /// * `chunk` - The underlying `Chunk` data.
63    /// * `proof` - A `Vec<blake3::Hash>` representing the Merkle inclusion proof for this chunk within its chunkset.
64    ///
65    /// # Assumes
66    ///
67    /// That `proof.len()` equals to `ChunkSet::PROOF_SIZE`.
68    pub(crate) fn new(chunk: Chunk, proof: Vec<blake3::Hash>) -> Self {
69        Self { chunk, proof }
70    }
71
72    /// Validates the inclusion of this chunk in the overall blob using the provided blob root commitment.
73    ///
74    /// This method verifies the Merkle proof against the blob's root commitment,
75    /// assuming the proof contains the necessary sibling nodes to ascend to the blob root.
76    ///
77    /// Meaning `Self::append_proof_to_blob_root()` needs to be called after `Self::new()` to extend
78    /// the Merkle inclusion proof to the blob root level - only then one can validate inclusion of this
79    /// chunk in the blob.
80    ///
81    /// # Arguments
82    ///
83    /// * `blob_commitment` - The `blake3::Hash` of the root of the Merkle tree for the entire blob.
84    ///
85    /// # Returns
86    ///
87    /// Returns `true` if the chunk's inclusion proof in the blob is valid, `false` otherwise.
88    pub fn validate_inclusion_in_blob(&self, blob_commitment: blake3::Hash) -> bool {
89        MerkleTree::verify_proof(self.get_global_chunk_id(), self.chunk.digest(), &self.proof, blob_commitment)
90    }
91
92    /// Validates the inclusion of this chunk within its specific chunkset using the provided chunkset root commitment.
93    ///
94    /// This method checks the Merkle proof against the chunkset's root commitment.
95    ///
96    /// # Arguments
97    ///
98    /// * `chunkset_commitment` - The `blake3::Hash` of the root of the Merkle tree for the chunkset this chunk belongs to.
99    ///
100    /// # Returns
101    ///
102    /// Returns `true` if the chunk's inclusion proof in its chunkset is valid, `false` otherwise.
103    pub fn validate_inclusion_in_chunkset(&self, chunkset_commitment: blake3::Hash) -> bool {
104        MerkleTree::verify_proof(
105            self.get_local_chunk_id(),
106            self.chunk.digest(),
107            &self.proof[..ChunkSet::PROOF_SIZE],
108            chunkset_commitment,
109        )
110    }
111
112    /// Returns the ID of the chunkset this chunk belongs to.
113    pub fn get_chunkset_id(&self) -> usize {
114        self.chunk.chunkset_id
115    }
116
117    /// Returns the global ID of the chunk.
118    pub fn get_global_chunk_id(&self) -> usize {
119        self.chunk.chunk_id
120    }
121
122    /// Returns the local ID of the chunk.
123    pub fn get_local_chunk_id(&self) -> usize {
124        self.chunk.chunk_id % ChunkSet::NUM_ERASURE_CODED_CHUNKS
125    }
126
127    /// Returns a reference to the erasure-coded data contained within the chunk.
128    pub fn get_erasure_coded_data(&self) -> &[u8] {
129        self.chunk.erasure_coded_data.as_ref()
130    }
131
132    /// Appends additional Merkle proof hashes to the existing proof, proving blob-level inclusion.
133    ///
134    /// This is used to extend a chunkset-level proof to a blob-level proof. You are supposed to call this
135    /// function after `Self::new` is used to contruct a new proof-carrying chunk, which originally holds a
136    /// proof of inclusion in the corresponding chunkset.
137    ///
138    /// # Arguments
139    ///
140    /// * `blob_proof` - A slice of `blake3::Hash` representing the proof to append.
141    pub fn append_proof_to_blob_root(&mut self, blob_proof: &[blake3::Hash]) {
142        self.proof.extend_from_slice(blob_proof);
143    }
144
145    /// Serializes the `ProofCarryingChunk` into a vector of bytes using `bincode`.
146    ///
147    /// # Returns
148    ///
149    /// Returns a `Result` which is:
150    /// - `Ok(Vec<u8>)` containing the serialized bytes if successful.
151    /// - `Err(DecdsError::ProofCarryingChunkSerializationFailed)` if serialization fails.
152    pub fn to_bytes(&self) -> Result<Vec<u8>, DecdsError> {
153        bincode::serde::encode_to_vec(self, DECDS_BINCODE_CONFIG).map_err(|err| DecdsError::ProofCarryingChunkSerializationFailed(err.to_string()))
154    }
155
156    /// Deserializes a `ProofCarryingChunk` from a byte slice using `bincode`.
157    ///
158    /// # Arguments
159    ///
160    /// * `bytes` - The byte slice from which to deserialize the chunk.
161    ///
162    /// # Returns
163    ///
164    /// Returns a `Result` which is:
165    /// - `Ok((Self, usize))` containing the deserialized `ProofCarryingChunk` and the number of bytes read if successful.
166    /// - `Err(DecdsError::ProofCarryingChunkDeserializationFailed)` if deserialization fails.
167    pub fn from_bytes(bytes: &[u8]) -> Result<(Self, usize), DecdsError> {
168        bincode::serde::decode_from_slice::<ProofCarryingChunk, bincode::config::Configuration>(bytes, DECDS_BINCODE_CONFIG)
169            .map_err(|err| DecdsError::ProofCarryingChunkDeserializationFailed(err.to_string()))
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176    use blake3;
177    use rand::Rng;
178
179    #[test]
180    fn test_chunk_digest() {
181        let chunkset_id = 1;
182        let chunk_id = 5;
183        let erasure_coded_data = vec![1, 2, 3, 4, 5];
184
185        let chunk = Chunk::new(chunkset_id, chunk_id, erasure_coded_data.clone());
186        let computed_digest = chunk.digest();
187
188        // Manually compute the expected digest
189        let expected_digest = blake3::Hasher::new()
190            .update(&chunkset_id.to_le_bytes())
191            .update(&chunk_id.to_le_bytes())
192            .update(&erasure_coded_data)
193            .finalize();
194
195        assert_eq!(computed_digest, expected_digest);
196
197        // Test with different data to ensure digest changes
198        let chunk2 = Chunk::new(chunkset_id, chunk_id, vec![6, 7, 8]);
199        assert_ne!(chunk2.digest(), expected_digest);
200    }
201
202    #[test]
203    fn test_proof_carrying_chunk_serialization_deserialization() {
204        let mut rng = rand::rng();
205
206        let chunkset_id = 0;
207        let chunk_id = 5;
208        let erasure_coded_data: Vec<u8> = (0..Chunk::BYTE_LENGTH).map(|_| rng.random()).collect();
209
210        // Generate a proof with a length consistent with ChunkSet::PROOF_SIZE
211        let proof_data = (0..ChunkSet::PROOF_SIZE)
212            .map(|_| {
213                let random_bytes: [u8; 32] = rng.random();
214                blake3::Hash::from_bytes(random_bytes)
215            })
216            .collect::<Vec<blake3::Hash>>();
217
218        let original_chunk = Chunk::new(chunkset_id, chunk_id, erasure_coded_data);
219        let original_pcc = ProofCarryingChunk::new(original_chunk.clone(), proof_data.clone());
220
221        // Test serialization
222        let serialized_pcc_bytes = original_pcc.to_bytes().expect("Serialization failed");
223
224        // Test deserialization
225        let (deserialized_pcc, bytes_read) = ProofCarryingChunk::from_bytes(&serialized_pcc_bytes).expect("Deserialization failed");
226
227        assert_eq!(original_pcc, deserialized_pcc);
228        assert_eq!(serialized_pcc_bytes.len(), bytes_read);
229
230        // Test deserialization with lesser bytes
231        assert!(ProofCarryingChunk::from_bytes(&serialized_pcc_bytes[..(serialized_pcc_bytes.len() / 2)]).is_err());
232    }
233}
decds_lib/chunk.rs

decds_lib/
chunk.rs
