fsverity_merkle/
verifier.rs

1// Copyright 2026 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::builder::MerkleTreeBuilder;
6use crate::util::FsVerityHasher;
7use crate::{FsVerityHash, Sha256Hash, Sha512Hash};
8use zx_status::Status;
9
10use zerocopy::FromBytes;
11
12/// Verifies data blocks against a pre-validated Merkle tree.
13#[derive(Debug, Clone)]
14pub struct MerkleVerifier {
15    hasher: FsVerityHasher,
16    leaf_hashes: Box<[u8]>,
17}
18
19impl MerkleVerifier {
20    /// Constructs a `MerkleVerifier` from the expected root, leaf hashes, and hasher.
21    ///
22    /// Returns `INVALID_ARGS` if the lengths are incorrect or alignment checks fail.
23    /// Returns `IO_DATA_INTEGRITY` if the leaf hashes do not match the expected root.
24    pub fn new(
25        expected_root: &[u8],
26        leaf_hashes: Box<[u8]>,
27        hasher: FsVerityHasher,
28    ) -> Result<Self, Status> {
29        match hasher {
30            FsVerityHasher::Sha256(_) => {
31                Self::validate_root::<Sha256Hash>(expected_root, &leaf_hashes, &hasher)?;
32            }
33            FsVerityHasher::Sha512(_) => {
34                Self::validate_root::<Sha512Hash>(expected_root, &leaf_hashes, &hasher)?;
35            }
36        }
37
38        Ok(Self { hasher, leaf_hashes })
39    }
40
41    fn validate_root<D: FsVerityHash>(
42        expected_root_bytes: &[u8],
43        leaf_hashes_bytes: &[u8],
44        hasher: &FsVerityHasher,
45    ) -> Result<(), Status> {
46        let expected_root: &D =
47            D::ref_from_bytes(expected_root_bytes).map_err(|_| Status::INVALID_ARGS)?;
48        let count = leaf_hashes_bytes.len() / std::mem::size_of::<D>();
49        let leaf_hashes: &[D] = <[D]>::ref_from_bytes_with_elems(leaf_hashes_bytes, count)
50            .map_err(|_| Status::INVALID_ARGS)?;
51
52        if rebuild_root(leaf_hashes, hasher) != expected_root.as_bytes() {
53            return Err(Status::IO_DATA_INTEGRITY);
54        }
55        Ok(())
56    }
57
58    /// Verifies a chunk of data against the Merkle tree.
59    ///
60    /// Returns `IO_DATA_INTEGRITY` if the data does not match the expected hash.
61    /// Returns `INVALID_ARGS` if the offset or data length is not aligned to the block size.
62    pub fn verify(&self, offset: usize, data: &[u8]) -> Result<(), Status> {
63        match &self.hasher {
64            FsVerityHasher::Sha256(_) => self.verify_impl::<Sha256Hash>(offset, data),
65            FsVerityHasher::Sha512(_) => self.verify_impl::<Sha512Hash>(offset, data),
66        }
67    }
68
69    fn verify_impl<D: FsVerityHash>(&self, offset: usize, data: &[u8]) -> Result<(), Status> {
70        let block_size = self.hasher.block_size();
71        if offset % block_size != 0 || data.len() % block_size != 0 {
72            return Err(Status::INVALID_ARGS);
73        }
74
75        let count = self.leaf_hashes.len() / std::mem::size_of::<D>();
76        let leaf_hashes: &[D] = <[D]>::ref_from_bytes_with_elems(&self.leaf_hashes[..], count)
77            .map_err(|_| Status::INVALID_ARGS)?;
78
79        let mut leaf_nodes_offset = offset;
80
81        for chunk in data.chunks(block_size) {
82            let index = leaf_nodes_offset / block_size;
83            if index >= leaf_hashes.len() {
84                return Err(Status::IO_DATA_INTEGRITY);
85            }
86
87            if self.hasher.hash_block(chunk) != leaf_hashes[index].as_bytes() {
88                return Err(Status::IO_DATA_INTEGRITY);
89            }
90
91            leaf_nodes_offset += block_size;
92        }
93
94        Ok(())
95    }
96}
97
98fn rebuild_root<D: FsVerityHash>(leaf_hashes: &[D], hasher: &FsVerityHasher) -> Vec<u8> {
99    let mut builder = MerkleTreeBuilder::<D>::new(hasher.clone());
100
101    for hash in leaf_hashes {
102        builder.push_data_hash(*hash);
103    }
104
105    builder.finish().root().to_vec()
106}
107
108#[cfg(test)]
109mod tests {
110    use super::*;
111    use crate::MerkleTree;
112    use crate::util::{FsVerityHasher, FsVerityHasherOptions};
113    use std::mem::size_of;
114    use test_case::test_case;
115
116    const TEST_BLOCK_SIZE: usize = 4096;
117
118    #[derive(Debug, Clone, Copy)]
119    enum HashType {
120        Sha256,
121        Sha512,
122    }
123
124    fn get_hasher(hash_type: HashType) -> FsVerityHasher {
125        match hash_type {
126            HashType::Sha256 => {
127                FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![], TEST_BLOCK_SIZE))
128            }
129            HashType::Sha512 => {
130                FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![], TEST_BLOCK_SIZE))
131            }
132        }
133    }
134
135    fn create_data(size: usize) -> Vec<u8> {
136        let mut data = vec![0xFFu8; size];
137        for i in 0..data.len() {
138            data[i] = (i % 255) as u8;
139        }
140        data
141    }
142
143    #[test_case(HashType::Sha256; "sha256")]
144    #[test_case(HashType::Sha512; "sha512")]
145    fn test_successfully_validate_root(hash_type: HashType) {
146        let data = create_data(2 * TEST_BLOCK_SIZE + TEST_BLOCK_SIZE / 2);
147        let hasher = get_hasher(hash_type);
148        let tree = MerkleTree::from_data(&data, hasher.clone());
149        MerkleVerifier::new(tree.root(), tree.leaf_hashes().to_vec().into_boxed_slice(), hasher)
150            .expect("build failed");
151    }
152
153    #[test_case(HashType::Sha256; "sha256")]
154    #[test_case(HashType::Sha512; "sha512")]
155    fn test_fail_to_validate_root(hash_type: HashType) {
156        let data = create_data(2 * TEST_BLOCK_SIZE + TEST_BLOCK_SIZE / 2);
157        let hasher = get_hasher(hash_type);
158        let tree = MerkleTree::from_data(&data, hasher.clone());
159
160        let mut leaf_hashes = tree.leaf_hashes().to_vec();
161        leaf_hashes[0] ^= 0xFF;
162
163        let err = MerkleVerifier::new(tree.root(), leaf_hashes.into_boxed_slice(), hasher)
164            .expect_err("build succeeded");
165        assert_eq!(err, Status::IO_DATA_INTEGRITY);
166    }
167
168    #[test_case(HashType::Sha256; "sha256")]
169    #[test_case(HashType::Sha512; "sha512")]
170    fn test_verify_empty_data(hash_type: HashType) {
171        let hasher = get_hasher(hash_type);
172        let tree = MerkleTree::from_data(&[], hasher.clone());
173        let verifier = MerkleVerifier::new(
174            tree.root(),
175            tree.leaf_hashes().to_vec().into_boxed_slice(),
176            hasher,
177        )
178        .expect("build failed");
179
180        verifier.verify(0, &[]).expect("verify failed");
181        assert_eq!(verifier.verify(1, &[]).expect_err("verify succeeded"), Status::INVALID_ARGS);
182        assert_eq!(
183            verifier.verify(0, &[0x00]).expect_err("verify succeeded"),
184            Status::INVALID_ARGS
185        );
186    }
187
188    #[test_case(HashType::Sha256; "sha256")]
189    #[test_case(HashType::Sha512; "sha512")]
190    fn test_verify_with_invalid_args(hash_type: HashType) {
191        let data = create_data(2 * TEST_BLOCK_SIZE + TEST_BLOCK_SIZE / 2);
192        let hasher = get_hasher(hash_type);
193        let tree = MerkleTree::from_data(&data, hasher.clone());
194        let verifier = MerkleVerifier::new(
195            tree.root(),
196            tree.leaf_hashes().to_vec().into_boxed_slice(),
197            hasher,
198        )
199        .expect("build failed");
200
201        assert_eq!(
202            verifier.verify(1, &data[1..TEST_BLOCK_SIZE + 1]).expect_err("verify succeeded"),
203            Status::INVALID_ARGS
204        );
205        assert_eq!(
206            verifier.verify(0, &vec![0xAB; 4 * TEST_BLOCK_SIZE]).expect_err("verify succeeded"),
207            Status::IO_DATA_INTEGRITY
208        );
209        assert_eq!(
210            verifier.verify(0, &data[0..TEST_BLOCK_SIZE - 1]).expect_err("verify succeeded"),
211            Status::INVALID_ARGS
212        );
213    }
214
215    #[test_case(HashType::Sha256; "sha256")]
216    #[test_case(HashType::Sha512; "sha512")]
217    fn test_verification(hash_type: HashType) {
218        let data = create_data(2 * TEST_BLOCK_SIZE + TEST_BLOCK_SIZE / 2);
219        let hasher = get_hasher(hash_type);
220        let tree = MerkleTree::from_data(&data, hasher.clone());
221        let verifier = MerkleVerifier::new(
222            tree.root(),
223            tree.leaf_hashes().to_vec().into_boxed_slice(),
224            hasher,
225        )
226        .expect("build failed");
227
228        verifier.verify(0, &data[0..TEST_BLOCK_SIZE]).expect("verify failed");
229        verifier
230            .verify(TEST_BLOCK_SIZE, &data[TEST_BLOCK_SIZE..2 * TEST_BLOCK_SIZE])
231            .expect("verify failed");
232        verifier.verify(0, &data[0..2 * TEST_BLOCK_SIZE]).expect("verify failed");
233
234        let mut corrupt_data = data.clone();
235        corrupt_data[0] ^= 0xFF;
236        assert_eq!(
237            verifier.verify(0, &corrupt_data[0..TEST_BLOCK_SIZE]).expect_err("verify succeeded"),
238            Status::IO_DATA_INTEGRITY
239        );
240    }
241
242    #[test_case(HashType::Sha256; "sha256")]
243    #[test_case(HashType::Sha512; "sha512")]
244    fn test_hash_type_size_validation(hash_type: HashType) {
245        let size = match hash_type {
246            HashType::Sha256 => size_of::<Sha256Hash>(),
247            HashType::Sha512 => size_of::<Sha512Hash>(),
248        };
249        let bad_slice_less = vec![0xABu8; size - 1];
250        let bad_slice_more = vec![0xABu8; size + 1];
251
252        match hash_type {
253            HashType::Sha256 => {
254                assert!(Sha256Hash::ref_from_bytes(bad_slice_less.as_slice()).is_err());
255                assert!(Sha256Hash::ref_from_bytes(bad_slice_more.as_slice()).is_err());
256            }
257            HashType::Sha512 => {
258                assert!(Sha512Hash::ref_from_bytes(bad_slice_less.as_slice()).is_err());
259                assert!(Sha512Hash::ref_from_bytes(bad_slice_more.as_slice()).is_err());
260            }
261        }
262
263        let good_slice = vec![0xABu8; size];
264        match hash_type {
265            HashType::Sha256 => {
266                let _: &Sha256Hash =
267                    Sha256Hash::ref_from_bytes(good_slice.as_slice()).expect("read_hash failed");
268            }
269            HashType::Sha512 => {
270                let _: &Sha512Hash =
271                    Sha512Hash::ref_from_bytes(good_slice.as_slice()).expect("read_hash failed");
272            }
273        }
274    }
275
276    #[test]
277    fn test_mismatched_hasher_and_root_size() {
278        let data = create_data(512);
279        let sha256_hasher = get_hasher(HashType::Sha256);
280        let sha512_hasher = get_hasher(HashType::Sha512);
281
282        // Build a SHA-256 tree
283        let tree = MerkleTree::from_data(&data, sha256_hasher);
284
285        // Try to construct a verifier using a SHA-512 hasher but with a SHA-256 root (32 bytes).
286        // This should fail with INVALID_ARGS because the root size (32) doesn't match the
287        // expected SHA-512 digest size (64).
288        assert_eq!(
289            MerkleVerifier::new(
290                tree.root(), // 32 bytes
291                tree.leaf_hashes().to_vec().into_boxed_slice(),
292                sha512_hasher, // Expects 64 bytes
293            )
294            .expect_err("build succeeded with mismatched hasher"),
295            Status::INVALID_ARGS
296        );
297    }
298
299    #[test]
300    fn test_mismatched_hasher_rebuild_fails() {
301        let data = create_data(512);
302        let sha256_hasher = get_hasher(HashType::Sha256);
303        let sha512_hasher = get_hasher(HashType::Sha512);
304
305        // Build a SHA-256 tree
306        let tree = MerkleTree::from_data(&data, sha256_hasher);
307
308        // Pass a 64-byte expected root (to pass the length check of SHA-512)
309        let fake_sha512_root = vec![0u8; 64];
310
311        // Pass SHA-256 leaf hashes, but pad them to a multiple of 64 bytes so they pass the
312        // initial length check for SHA-512. This allows us to test the actual root validation
313        // failure.
314        let mut leaf_hashes = tree.leaf_hashes().to_vec();
315        while leaf_hashes.len() % 64 != 0 {
316            leaf_hashes.push(0);
317        }
318
319        // This should fail with IO_DATA_INTEGRITY because the rebuilt root (computed using
320        // SHA-512 on the padded SHA-256 hashes) will not match the fake SHA-512 root we passed.
321        assert_eq!(
322            MerkleVerifier::new(&fake_sha512_root, leaf_hashes.into_boxed_slice(), sha512_hasher)
323                .expect_err("build succeeded"),
324            Status::IO_DATA_INTEGRITY
325        );
326    }
327}
fsverity_merkle/verifier.rs

fsverity_merkle/
verifier.rs
