fuchsia_merkle/
merkle_verifier.rs

1// Copyright 2025 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use crate::util::{hash_block, hash_block_aligned, make_hash_hasher, update_with_zeros};
6use crate::{BLOCK_SIZE, HASH_SIZE, Hash, MerkleRootBuilder};
7use storage_ptr_slice::PtrByteSlice;
8use zx_status::Status;
9
10/// Verifies data against the leaf hashes of a merkle tree.
11#[derive(Clone)]
12pub struct MerkleVerifier {
13    hashes: Box<[Hash]>,
14}
15
16impl MerkleVerifier {
17    /// Constructs a [`MerkleVerifier`] from the root and leaf hashes of a merkle tree.
18    ///
19    /// Returns `IO_DATA_INTEGRITY` if the leaf hashes are inconsistent with the root.
20    pub fn new(root: Hash, hashes: Box<[Hash]>) -> Result<Self, Status> {
21        if rebuild_root(&hashes) != root {
22            Err(Status::IO_DATA_INTEGRITY)
23        } else {
24            Ok(Self { hashes })
25        }
26    }
27
28    /// Verifies a `data` slice against the Merkle tree, assuming it corresponds to original data
29    /// starting at `offset`.
30    ///
31    /// # Requirements:
32    /// - The `offset` must be aligned to `BLOCK_SIZE`.
33    /// - The length of `data` must be a multiple of `BLOCK_SIZE`, *except* if `data` contains the
34    ///   final chunk of the original data source.
35    pub fn verify(&self, offset: usize, data: &[u8]) -> Result<(), Status> {
36        if !offset.is_multiple_of(BLOCK_SIZE) {
37            return Err(Status::INVALID_ARGS);
38        }
39        let ending = data.len().checked_add(offset).ok_or(Status::INVALID_ARGS)?;
40        if ending.div_ceil(BLOCK_SIZE) > self.hashes.len() {
41            return Err(Status::INVALID_ARGS);
42        }
43
44        for (i, chunk) in data.chunks(BLOCK_SIZE).enumerate() {
45            let hash = hash_block(chunk, offset + i * BLOCK_SIZE);
46            if self.hashes[offset / BLOCK_SIZE + i] != hash {
47                return Err(Status::IO_DATA_INTEGRITY);
48            }
49        }
50
51        Ok(())
52    }
53
54    /// Verifies aligned, zero-padded data against the Merkle tree.
55    ///
56    /// The buffer length (`data.len()`) must be a multiple of 4096 bytes.
57    /// `unaligned_len` specifies the actual valid data length within the buffer
58    /// (`0 < unaligned_len <= data.len()`).
59    /// Any buffer bytes beyond `unaligned_len` up to `data.len()` MUST be zeroed for verification
60    /// to pass.
61    ///
62    /// Note: Does not support the null blob (empty 0-length blob, `unaligned_len == 0`).
63    pub fn verify_aligned(
64        &self,
65        offset: usize,
66        data: PtrByteSlice<'_>,
67        unaligned_len: usize,
68    ) -> Result<(), Status> {
69        let len = data.len();
70        let ending = len.checked_add(offset).ok_or(Status::INVALID_ARGS)?;
71        if !offset.is_multiple_of(BLOCK_SIZE)
72            || !len.is_multiple_of(4096)
73            || unaligned_len == 0
74            || unaligned_len > len
75        {
76            return Err(Status::INVALID_ARGS);
77        }
78        if ending.div_ceil(BLOCK_SIZE) > self.hashes.len() {
79            return Err(Status::INVALID_ARGS);
80        }
81
82        for (i, block) in data.chunks(BLOCK_SIZE).enumerate() {
83            let block_buffer_len = block.len();
84            let block_unaligned_len =
85                std::cmp::min(block_buffer_len, unaligned_len.saturating_sub(i * BLOCK_SIZE));
86            let hash = hash_block_aligned(
87                offset + i * BLOCK_SIZE,
88                block,
89                block_buffer_len,
90                block_unaligned_len,
91            );
92            if self.hashes[offset / BLOCK_SIZE + i] != hash {
93                return Err(Status::IO_DATA_INTEGRITY);
94            }
95        }
96
97        Ok(())
98    }
99}
100
101impl std::fmt::Debug for MerkleVerifier {
102    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
103        // The leaf hashes are unlikely to be useful for debugging and could be megabytes of data.
104        // The root of the merkle tree uniquely identifies the blob and the hash count can quickly
105        // give a rough idea of the size of the blob.
106        let root = rebuild_root(&self.hashes);
107        f.debug_struct("MerkleVerifier")
108            .field("root", &root)
109            .field("hash_count", &self.hashes.len())
110            .finish()
111    }
112}
113
114fn rebuild_root(leaf_hashes: &[Hash]) -> Hash {
115    let mut builder = MerkleRootBuilder::default();
116    for hash in leaf_hashes {
117        builder.push_hash(*hash);
118    }
119    builder.complete(&[])
120}
121
122fn hash_hashes(
123    hashes_per_hash: usize,
124    index: usize,
125    hashes: impl ExactSizeIterator<Item = Hash>,
126) -> Hash {
127    let mut hasher = make_hash_hasher(hashes_per_hash, 1, index * hashes_per_hash * HASH_SIZE);
128    let hash_count = hashes.len();
129    for hash in hashes {
130        hasher.update(hash.as_bytes());
131    }
132    if hash_count != hashes_per_hash {
133        update_with_zeros(&mut hasher, (hashes_per_hash - hash_count) * HASH_SIZE);
134    }
135    Hash::from_array(hasher.digest())
136}
137
138/// Verifies reads against a merkle tree.
139///
140/// [`MerkleVerifier`] verifies data at a granularity of [`BLOCK_SIZE`]. Consequently, it stores one
141/// hash (of size [`HASH_SIZE`]) for each data block. This hash storage consumes memory equal to
142/// 1/256th of the original data size.
143///
144/// [`ReadSizedMerkleVerifier`] optimizes memory usage when reads are always aligned and are
145/// guaranteed to be a multiple of the [`BLOCK_SIZE`]. Instead of storing a hash for every
146/// [`BLOCK_SIZE`] blocks like [`MerkleVerifier`], it stores only one hash for each read sized
147/// chunk. For example, 128KiB aligned reads would require storing 1/16th the number of hashes.
148#[derive(Clone)]
149pub struct ReadSizedMerkleVerifier {
150    read_size: usize,
151    hashes: Box<[Hash]>,
152}
153
154impl ReadSizedMerkleVerifier {
155    /// Constructs a [`ReadSizedMerkleVerifier`] from an existing [`MerkleVerifier`] and a
156    /// `read_size`.
157    ///
158    /// Returns an error if `read_size` is not a multiple of [`BLOCK_SIZE`].
159    pub fn new(verifier: MerkleVerifier, read_size: usize) -> Result<Self, Status> {
160        if read_size == 0 || !read_size.is_multiple_of(BLOCK_SIZE) {
161            return Err(Status::INVALID_ARGS);
162        }
163        let hashes_per_hash = read_size / BLOCK_SIZE;
164        let mut level_1_hashes =
165            Vec::with_capacity(verifier.hashes.len().div_ceil(hashes_per_hash));
166        for (i, hashes) in verifier.hashes.chunks(hashes_per_hash).enumerate() {
167            level_1_hashes.push(hash_hashes(hashes_per_hash, i, hashes.iter().copied()));
168        }
169        Ok(ReadSizedMerkleVerifier { read_size, hashes: level_1_hashes.into_boxed_slice() })
170    }
171
172    /// Verifies a `data` slice against the Merkle tree, assuming it corresponds to original data
173    /// starting at `offset`.
174    ///
175    /// # Requirements:
176    /// - The `offset` must be aligned to the configured read size granularity.
177    /// - The length of `data` must be a multiple of the read size, *except* if `data` represents
178    ///   the final chunk of the original data source (in which case it can be shorter).
179    pub fn verify(&self, offset: usize, data: &[u8]) -> Result<(), Status> {
180        let end = offset.checked_add(data.len()).ok_or(Status::INVALID_ARGS)?;
181        if !offset.is_multiple_of(self.read_size) {
182            // The offset must read aligned.
183            return Err(Status::INVALID_ARGS);
184        }
185
186        let hash_start_index = offset / self.read_size;
187        let hash_end_index = end.div_ceil(self.read_size);
188
189        if !end.is_multiple_of(self.read_size) && hash_end_index != self.hashes.len() {
190            // The end is not aligned and it's not the end of the data.
191            return Err(Status::INVALID_ARGS);
192        }
193        if hash_end_index > self.hashes.len() {
194            return Err(Status::INVALID_ARGS);
195        }
196
197        let hashes_per_hash = self.read_size / BLOCK_SIZE;
198        for (i, chunk) in data.chunks(self.read_size).enumerate() {
199            let hash = hash_hashes(
200                hashes_per_hash,
201                hash_start_index + i,
202                chunk.chunks(BLOCK_SIZE).enumerate().map(|(j, chunk)| {
203                    hash_block(chunk, offset + self.read_size * i + j * BLOCK_SIZE)
204                }),
205            );
206            if hash != self.hashes[hash_start_index + i] {
207                return Err(Status::IO_DATA_INTEGRITY);
208            }
209        }
210
211        Ok(())
212    }
213
214    /// Verifies aligned, zero-padded data against the Merkle tree.
215    ///
216    /// The buffer length (`data.len()`) must be a multiple of 4096 bytes.
217    /// `unaligned_len` specifies the actual valid data length within the buffer
218    /// (`0 < unaligned_len <= data.len()`).
219    /// Any buffer bytes beyond `unaligned_len` up to `data.len()` MUST be zeroed for verification
220    /// to pass.
221    ///
222    /// Note: Does not support the null blob (empty 0-length blob, `unaligned_len == 0`).
223    pub fn verify_aligned(
224        &self,
225        offset: usize,
226        data: PtrByteSlice<'_>,
227        unaligned_len: usize,
228    ) -> Result<(), Status> {
229        let len = data.len();
230        let end = offset.checked_add(len).ok_or(Status::INVALID_ARGS)?;
231        if !offset.is_multiple_of(self.read_size)
232            || !len.is_multiple_of(4096)
233            || unaligned_len == 0
234            || unaligned_len > len
235        {
236            return Err(Status::INVALID_ARGS);
237        }
238
239        let hash_start_index = offset / self.read_size;
240        let hash_end_index = end.div_ceil(self.read_size);
241
242        if !end.is_multiple_of(self.read_size) && hash_end_index != self.hashes.len() {
243            // The end is not aligned and it's not the end of the data.
244            return Err(Status::INVALID_ARGS);
245        }
246        if hash_end_index > self.hashes.len() {
247            return Err(Status::INVALID_ARGS);
248        }
249
250        let hashes_per_hash = self.read_size / BLOCK_SIZE;
251        for (i, chunk) in data.chunks(self.read_size).enumerate() {
252            let block_base_offset = offset + i * self.read_size;
253            let hash = hash_hashes(
254                hashes_per_hash,
255                hash_start_index + i,
256                chunk.chunks(BLOCK_SIZE).enumerate().map(|(j, block)| {
257                    let block_buffer_len = block.len();
258                    let block_unaligned_len = std::cmp::min(
259                        block_buffer_len,
260                        unaligned_len.saturating_sub(i * self.read_size + j * BLOCK_SIZE),
261                    );
262                    hash_block_aligned(
263                        block_base_offset + j * BLOCK_SIZE,
264                        block,
265                        block_buffer_len,
266                        block_unaligned_len,
267                    )
268                }),
269            );
270            if hash != self.hashes[hash_start_index + i] {
271                return Err(Status::IO_DATA_INTEGRITY);
272            }
273        }
274
275        Ok(())
276    }
277}
278
279impl std::fmt::Debug for ReadSizedMerkleVerifier {
280    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
281        // The leaf hashes are unlikely to be useful for debugging and could be megabytes of data.
282        // The root of the merkle tree can't be recovered either. The read size and hash count can
283        // give a rough idea of the size of the blob.
284        f.debug_struct("ReadAlignedMerkleVerifier")
285            .field("read_size", &self.read_size)
286            .field("hash_count", &self.hashes.len())
287            .finish()
288    }
289}
290
291#[cfg(test)]
292mod tests {
293    use super::*;
294    use anyhow::{Context, Error, anyhow};
295    use assert_matches::assert_matches;
296    use test_case::test_case;
297
298    fn create_data(size: usize) -> Vec<u8> {
299        const USIZE_SIZE: usize = size_of::<usize>();
300        let mut data = vec![0xABu8; size];
301        for (i, block) in data.chunks_mut(BLOCK_SIZE).enumerate() {
302            // Place the index of the block at the start of the block to make every block unique.
303            if block.len() < USIZE_SIZE {
304                block.copy_from_slice(&i.to_le_bytes()[0..block.len()]);
305            } else {
306                block[0..USIZE_SIZE].copy_from_slice(&i.to_le_bytes());
307            }
308        }
309        data
310    }
311
312    #[test_case(0; "0")]
313    #[test_case(1; "1")]
314    #[test_case(4096; "4096")]
315    #[test_case(8191; "8191")]
316    #[test_case(8192; "8192")]
317    #[test_case(8193; "8193")]
318    #[test_case(8192 * 2 - 1; "16383")]
319    #[test_case(8192 * 2; "16384")]
320    #[test_case(8192 * 2 + 1; "16385")]
321    #[test_case(8192 * 256 - 1; "2097151")]
322    #[test_case(8192 * 256; "2097152")]
323    #[test_case(8192 * 256 + 1; "2097153")]
324    #[test_case(8192 * 256 * 2 - 1; "4194303")]
325    #[test_case(8192 * 256 * 2; "4194304")]
326    #[test_case(8192 * 256 * 2 + 1; "4194305")]
327    fn test_successfully_validate_root(size: usize) {
328        let data = create_data(size);
329        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
330
331        MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
332    }
333
334    #[test_case(8193; "8193")]
335    #[test_case(8192 * 2 - 1; "16383")]
336    #[test_case(8192 * 2; "16384")]
337    #[test_case(8192 * 2 + 1; "16385")]
338    #[test_case(8192 * 256 - 1; "2097151")]
339    #[test_case(8192 * 256; "2097152")]
340    #[test_case(8192 * 256 + 1; "2097153")]
341    #[test_case(8192 * 256 * 2 - 1; "4194303")]
342    #[test_case(8192 * 256 * 2; "4194304")]
343    #[test_case(8192 * 256 * 2 + 1; "4194305")]
344    fn test_fail_to_validate_root(size: usize) {
345        let data = create_data(size);
346        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
347
348        {
349            let mut leaf_hashes = leaf_hashes.clone().into_boxed_slice();
350            let mut first_hash: [u8; HASH_SIZE] = leaf_hashes[0].into();
351            first_hash[0] ^= 0xFF;
352            leaf_hashes[0] = Hash::from_array(first_hash);
353            MerkleVerifier::new(root, leaf_hashes).expect_err("The merkle root shouldn't match");
354        }
355
356        {
357            let mut leaf_hashes = leaf_hashes.into_boxed_slice();
358            let mut last_hash: [u8; HASH_SIZE] = (*leaf_hashes.last().unwrap()).into();
359            last_hash[31] ^= 0xFF;
360            *leaf_hashes.last_mut().unwrap() = Hash::from_array(last_hash);
361            MerkleVerifier::new(root, leaf_hashes).expect_err("The merkle root shouldn't match");
362        }
363    }
364
365    #[test]
366    fn test_verify_empty_data() {
367        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&[]);
368        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
369        verifier.verify(0, &[]).unwrap();
370        assert_matches!(verifier.verify(1, &[]), Err(Status::INVALID_ARGS));
371        assert_matches!(verifier.verify(0, &[0x00]), Err(Status::IO_DATA_INTEGRITY));
372        assert_matches!(verifier.verify(0, &[0x01]), Err(Status::IO_DATA_INTEGRITY));
373    }
374
375    #[test]
376    fn test_verify_with_invalid_args() {
377        let data = create_data(16 * 1024 + 20);
378        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
379        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
380        // Offset isn't aligned.
381        assert_matches!(verifier.verify(1, &data[1..]), Err(Status::INVALID_ARGS));
382        // Too much data.
383        assert_matches!(verifier.verify(8192, &data), Err(Status::INVALID_ARGS));
384        // Still too much data but it's within the same block as the original data it's detected
385        // with the hashes.
386        assert_matches!(verifier.verify(8192, &data[8191..]), Err(Status::IO_DATA_INTEGRITY));
387        assert_matches!(verifier.verify(8192, &data[8192..]), Ok(()));
388    }
389
390    #[test]
391    fn test_invalid_read_sizes() {
392        let data = create_data(16 * 1024 + 20);
393        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
394        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
395        assert_matches!(
396            ReadSizedMerkleVerifier::new(verifier.clone(), 0),
397            Err(Status::INVALID_ARGS)
398        );
399        assert_matches!(
400            ReadSizedMerkleVerifier::new(verifier.clone(), 1),
401            Err(Status::INVALID_ARGS)
402        );
403        assert_matches!(
404            ReadSizedMerkleVerifier::new(verifier.clone(), 8191),
405            Err(Status::INVALID_ARGS)
406        );
407        assert_matches!(
408            ReadSizedMerkleVerifier::new(verifier, 100 * 1024),
409            Err(Status::INVALID_ARGS)
410        );
411    }
412
413    #[test]
414    fn test_verify_reads_with_multiple_reads() {
415        const READ_SIZE: usize = 16 * 1024;
416        let data = create_data(READ_SIZE * 3 + 20);
417        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
418        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
419        let verifier = ReadSizedMerkleVerifier::new(verifier, READ_SIZE).unwrap();
420        verifier.verify(0, &data).unwrap();
421        verifier.verify(0, &data[0..READ_SIZE * 2]).unwrap();
422        verifier.verify(READ_SIZE, &data[READ_SIZE..READ_SIZE * 3]).unwrap();
423        verifier.verify(READ_SIZE, &data[READ_SIZE..READ_SIZE * 3 + 20]).unwrap();
424        verifier.verify(READ_SIZE * 2, &data[READ_SIZE * 2..READ_SIZE * 3 + 20]).unwrap();
425    }
426
427    #[test]
428    fn test_verify_reads_with_invalid_args() {
429        const READ_SIZE: usize = 16 * 1024;
430        let data = create_data(READ_SIZE * 3 + 20);
431        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
432        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
433        let verifier = ReadSizedMerkleVerifier::new(verifier, READ_SIZE).unwrap();
434        // Offset isn't aligned.
435        assert_matches!(verifier.verify(1, &data[1..READ_SIZE + 1]), Err(Status::INVALID_ARGS));
436        // Read past the end.
437        assert_matches!(
438            verifier.verify(READ_SIZE * 4, &data[0..READ_SIZE]),
439            Err(Status::INVALID_ARGS)
440        );
441        // Not the end of the data and the data is not a multiple of the read size.
442        assert_matches!(verifier.verify(0, &data[0..READ_SIZE - 10]), Err(Status::INVALID_ARGS));
443        // At end of the data and it's the wrong amount of data but it's within the last block so
444        // it's detected by the hashes.
445        assert_matches!(
446            verifier.verify(READ_SIZE * 3, &data[READ_SIZE * 3..READ_SIZE * 3 + 19]),
447            Err(Status::IO_DATA_INTEGRITY)
448        );
449        let mut last_block_with_an_extra_byte = data[READ_SIZE * 3..READ_SIZE * 3 + 20].to_vec();
450        last_block_with_an_extra_byte.push(0xAB);
451        assert_matches!(
452            verifier.verify(READ_SIZE * 3, &last_block_with_an_extra_byte),
453            Err(Status::IO_DATA_INTEGRITY)
454        );
455        assert_matches!(
456            verifier.verify(READ_SIZE * 3, &data[READ_SIZE * 3..READ_SIZE * 3 + 20]),
457            Ok(())
458        );
459    }
460
461    fn verify_with_first_bit_flipped(
462        verifier: &MerkleVerifier,
463        offset: usize,
464        data: &mut [u8],
465    ) -> Result<(), Error> {
466        data[0] ^= 0x01;
467        match verifier.verify(offset, data) {
468            Ok(()) => Err(anyhow!("verify_with_first_bit_flipped should have failed")),
469            Err(Status::IO_DATA_INTEGRITY) => {
470                data[0] ^= 0x01;
471                Ok(())
472            }
473            Err(e) => Err(anyhow!("unexpected error in verify_with_first_bit_flipped: {e:?}")),
474        }
475    }
476
477    fn verify_with_last_bit_flipped(
478        verifier: &MerkleVerifier,
479        offset: usize,
480        data: &mut [u8],
481    ) -> Result<(), Error> {
482        *data.last_mut().unwrap() ^= 0x80;
483        match verifier.verify(offset, data) {
484            Ok(()) => Err(anyhow!("verify_with_last_bit_flipped should have failed")),
485            Err(Status::IO_DATA_INTEGRITY) => {
486                *data.last_mut().unwrap() ^= 0x80;
487                Ok(())
488            }
489            Err(e) => Err(anyhow!("unexpected error in verify_with_last_bit_flipped: {e:?}")),
490        }
491    }
492
493    fn run_verify_tests(data: &mut [u8], verifier: MerkleVerifier) -> Result<(), Error> {
494        // Verify all of the data at once.
495        verifier.verify(0, data).context("verify all data")?;
496        verify_with_first_bit_flipped(&verifier, 0, data).context("verify all data")?;
497        verify_with_last_bit_flipped(&verifier, 0, data).context("verify all data")?;
498
499        // Verify 1 block at a time.
500        for (i, block) in data.chunks_mut(BLOCK_SIZE).enumerate() {
501            let offset = i * BLOCK_SIZE;
502            let context = || format!("verify 1 block at a time: offset={offset}");
503            verifier.verify(offset, block).with_context(context)?;
504            verify_with_first_bit_flipped(&verifier, offset, block).with_context(context)?;
505            verify_with_last_bit_flipped(&verifier, offset, block).with_context(context)?;
506        }
507
508        // Verify 4 blocks at a time.
509        const BLOCK_COUNT: usize = 4;
510        for (i, block) in data.chunks_mut(BLOCK_SIZE * BLOCK_COUNT).enumerate() {
511            let offset = i * BLOCK_SIZE * BLOCK_COUNT;
512            let context = || format!("verify {BLOCK_COUNT} blocks at a time: offset={offset}");
513            verifier.verify(offset, block).with_context(context)?;
514            verify_with_first_bit_flipped(&verifier, offset, block).with_context(context)?;
515            verify_with_last_bit_flipped(&verifier, offset, block).with_context(context)?;
516        }
517        Ok(())
518    }
519
520    fn verify_reads_with_first_bit_flipped(
521        verifier: &ReadSizedMerkleVerifier,
522        offset: usize,
523        data: &mut [u8],
524    ) -> Result<(), Error> {
525        data[0] ^= 0x01;
526        match verifier.verify(offset, data) {
527            Ok(()) => Err(anyhow!("verify_reads_with_first_bit_flipped should have failed")),
528            Err(Status::IO_DATA_INTEGRITY) => {
529                data[0] ^= 0x01;
530                Ok(())
531            }
532            Err(e) => {
533                Err(anyhow!("unexpected error in verify_reads_with_first_bit_flipped: {e:?}"))
534            }
535        }
536    }
537
538    fn verify_reads_with_last_bit_flipped(
539        verifier: &ReadSizedMerkleVerifier,
540        offset: usize,
541        data: &mut [u8],
542    ) -> Result<(), Error> {
543        *data.last_mut().unwrap() ^= 0x80;
544        match verifier.verify(offset, data) {
545            Ok(()) => Err(anyhow!("verify_reads_with_last_bit_flipped should have failed")),
546            Err(Status::IO_DATA_INTEGRITY) => {
547                *data.last_mut().unwrap() ^= 0x80;
548                Ok(())
549            }
550            Err(e) => Err(anyhow!("unexpected error in verify_reads_with_last_bit_flipped: {e:?}")),
551        }
552    }
553
554    fn run_read_sized_verify_tests(
555        data: &mut [u8],
556        verifier: MerkleVerifier,
557        read_size: usize,
558    ) -> Result<(), Error> {
559        let verifier = ReadSizedMerkleVerifier::new(verifier, read_size)
560            .context("Failed to create read aligned verifier")?;
561
562        for (i, chunk) in data.chunks_mut(read_size).enumerate() {
563            let offset = i * read_size;
564            let context = || format!("verify read: offset={offset}");
565            verifier.verify(offset, chunk).with_context(context)?;
566            verify_reads_with_first_bit_flipped(&verifier, offset, chunk).with_context(context)?;
567            verify_reads_with_last_bit_flipped(&verifier, offset, chunk).with_context(context)?;
568        }
569        Ok(())
570    }
571
572    fn verify_test(data: &mut [u8]) -> Result<(), Error> {
573        let hashes = Vec::with_capacity(data.len().div_ceil(BLOCK_SIZE));
574        let (root, hashes) = MerkleRootBuilder::new(hashes).complete(data);
575        let verifier = MerkleVerifier::new(root, hashes.into_boxed_slice())
576            .with_context(|| format!("create verifier: data-size={}", data.len()))?;
577        run_verify_tests(data, verifier.clone())
578            .with_context(|| format!("verify data-size={}", data.len()))?;
579        for read_size in [8 * 1024, 32 * 1024, 96 * 1024, 128 * 1024, 216 * 1024] {
580            run_read_sized_verify_tests(data, verifier.clone(), read_size).with_context(|| {
581                format!("verify read read-size={} data-size={}", read_size, data.len())
582            })?;
583        }
584        Ok(())
585    }
586
587    #[test_case(1; "1")]
588    #[test_case(4096; "4096")]
589    #[test_case(8192 - 1; "8191")]
590    #[test_case(8192; "8192")]
591    #[test_case(8192 + 1; "8193")]
592    #[test_case(8192 * 2 - 1; "16383")]
593    #[test_case(8192 * 2; "16384")]
594    #[test_case(8192 * 2 + 1; "16385")]
595    #[test_case(8192 * 256 - 1; "2097151")]
596    #[test_case(8192 * 256; "2097152")]
597    #[test_case(8192 * 256 + 1; "2097153")]
598    fn test_verification(size: usize) {
599        verify_test(&mut create_data(size)).unwrap();
600    }
601
602    #[test]
603    fn test_verify_aligned() {
604        for size in [1, 100, 4096, 4097, 8192, 16384, 65536, 131072] {
605            let data = create_data(size);
606            let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
607            let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
608            let read_sized_verifier =
609                ReadSizedMerkleVerifier::new(verifier.clone(), 128 * 1024).unwrap();
610
611            let buffer_len = size.next_multiple_of(4096);
612            let mut buf = vec![0u8; buffer_len];
613            buf[..size].copy_from_slice(&data);
614
615            // Test MerkleVerifier::verify_aligned
616            verifier
617                .verify_aligned(0, PtrByteSlice::from(&buf[..]), size)
618                .expect("verify_aligned failed");
619
620            // Test ReadSizedMerkleVerifier::verify_aligned
621            read_sized_verifier
622                .verify_aligned(0, PtrByteSlice::from(&buf[..]), size)
623                .expect("read_sized_verifier.verify_aligned failed");
624
625            // Test sub-chunk verification with non-zero offsets.
626            for chunk_offset in (0..size).step_by(8192) {
627                let chunk_unaligned_len = std::cmp::min(8192, size - chunk_offset);
628                let chunk_buffer_len = chunk_unaligned_len.next_multiple_of(4096);
629                let chunk_slice = &buf[chunk_offset..chunk_offset + chunk_buffer_len];
630                verifier
631                    .verify_aligned(
632                        chunk_offset,
633                        PtrByteSlice::from(chunk_slice),
634                        chunk_unaligned_len,
635                    )
636                    .expect("verify_aligned failed for non-zero offset sub-chunk");
637            }
638
639            // Test corruption detection
640            let mut corrupt_buf = buf.clone();
641            corrupt_buf[0] ^= 0x01;
642            assert_matches!(
643                verifier.verify_aligned(0, PtrByteSlice::from(&corrupt_buf[..]), size),
644                Err(Status::IO_DATA_INTEGRITY)
645            );
646            assert_matches!(
647                read_sized_verifier.verify_aligned(0, PtrByteSlice::from(&corrupt_buf[..]), size),
648                Err(Status::IO_DATA_INTEGRITY)
649            );
650
651            // Test corruption detection at non-zero offset
652            if size > 8192 {
653                let mut corrupt_nonzero_buf = buf.clone();
654                corrupt_nonzero_buf[8192] ^= 0x01;
655                let chunk_unaligned_len = std::cmp::min(8192, size - 8192);
656                let chunk_buffer_len = chunk_unaligned_len.next_multiple_of(4096);
657                assert_matches!(
658                    verifier.verify_aligned(
659                        8192,
660                        PtrByteSlice::from(&corrupt_nonzero_buf[8192..8192 + chunk_buffer_len]),
661                        chunk_unaligned_len
662                    ),
663                    Err(Status::IO_DATA_INTEGRITY)
664                );
665            }
666
667            // Test unzeroed tail padding detection (if size < buffer_len)
668            if size < buffer_len {
669                let mut unzeroed_tail_buf = buf.clone();
670                unzeroed_tail_buf[size] = 0xAA;
671                assert_matches!(
672                    verifier.verify_aligned(0, PtrByteSlice::from(&unzeroed_tail_buf[..]), size),
673                    Err(Status::IO_DATA_INTEGRITY)
674                );
675                assert_matches!(
676                    read_sized_verifier.verify_aligned(
677                        0,
678                        PtrByteSlice::from(&unzeroed_tail_buf[..]),
679                        size
680                    ),
681                    Err(Status::IO_DATA_INTEGRITY)
682                );
683            }
684        }
685
686        // Test non-4096-aligned buffer length returns INVALID_ARGS
687        let data = create_data(100);
688        let (root, leaf_hashes) = MerkleRootBuilder::new(Vec::new()).complete(&data);
689        let verifier = MerkleVerifier::new(root, leaf_hashes.into_boxed_slice()).unwrap();
690        let unaligned_buf = [0u8; 100];
691        assert_matches!(
692            verifier.verify_aligned(0, PtrByteSlice::from(&unaligned_buf[..]), 100),
693            Err(Status::INVALID_ARGS)
694        );
695    }
696
697    #[test]
698    #[ignore]
699    fn test_very_large_verification() {
700        const MAX_BUF: usize = 256 * 1024 * 1024 + 8192;
701        let parallelism = std::thread::available_parallelism().unwrap().get();
702        std::thread::scope(|scope| {
703            for thread in 0..parallelism {
704                scope.spawn(move || {
705                    let mut data = create_data(MAX_BUF + 1);
706                    for size in ((8192 * (thread + 1))..MAX_BUF).step_by(8192 * parallelism) {
707                        verify_test(&mut data[0..size - 1]).unwrap();
708                        verify_test(&mut data[0..size]).unwrap();
709                        verify_test(&mut data[0..size + 1]).unwrap();
710                    }
711                });
712            }
713        });
714    }
715}
fuchsia_merkle/merkle_verifier.rs

fuchsia_merkle/
merkle_verifier.rs
