fsverity_merkle/
tree.rs

1// Copyright 2023 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 std::io;
9
10/// A `MerkleTree` contains levels of hashes that can be used to verify the integrity of data.
11///
12/// While a single hash could be used to integrity check some data, if the data (or hash) is
13/// corrupt, a single hash can not determine what part of the data is corrupt. A `MerkleTree`,
14/// however, contains a hash for every block of data, allowing it to identify which blocks of
15/// data are corrupt. A `MerkleTree` also allows individual blocks of data to be verified without
16/// having to verify the rest of the data.
17///
18/// Furthermore, a `MerkleTree` contains multiple levels of hashes, where each level
19/// contains hashes of blocks of hashes of the lower level. The top level always contains a
20/// single hash, the merkle root. This tree of hashes allows a `MerkleTree` to determine which of
21/// its own hashes are corrupt, if any.
22///
23/// # Structure Details
24///
25/// A merkle tree contains levels. A level is a row of the tree, starting at 0 and counting upward.
26/// Level 0 represents the leaves of the tree which contain hashes of chunks of the input stream.
27/// Each level consists of a hash for each block of hashes from the previous level (or, for
28/// level 0, each block of data).
29///
30/// While building a `MerkleTree`, callers pass in an `FsverityHasher` which hashes based on a
31/// particular algorithm and contains the necessary parameters to compute the merkle tree. The
32/// `block size` is determined by the filesystem and the `salt` by the FsverityMetadata struct
33/// stored in fxfs. When computing a hash, if `salt`.len() > 0, the block of data (or hashes) is
34/// prepended by the `salt`.
35///
36/// For level 0, the length of the block is `block size`, except for the last block, which may be
37/// less than `block size`. All other levels use a block length of `block size`.
38#[derive(Clone, Eq, PartialEq, Debug)]
39pub struct MerkleTree {
40    levels: Vec<Box<[u8]>>,
41    hasher: FsVerityHasher,
42}
43
44impl MerkleTree {
45    /// Creates a `MerkleTree` from data.
46    pub fn from_data(data: &[u8], hasher: FsVerityHasher) -> Self {
47        match hasher {
48            FsVerityHasher::Sha256(_) => Self::from_data_impl::<Sha256Hash>(data, hasher),
49            FsVerityHasher::Sha512(_) => Self::from_data_impl::<Sha512Hash>(data, hasher),
50        }
51    }
52
53    fn from_data_impl<D: FsVerityHash>(data: &[u8], hasher: FsVerityHasher) -> Self {
54        let mut builder = MerkleTreeBuilder::<D>::new(hasher);
55        builder.write(data);
56        builder.finish()
57    }
58
59    // Creates a `MerkleTree` from a well-formed tree of hashes.
60    //
61    // This is used by `MerkleTreeBuilder` to construct the tree.
62    //
63    // A tree of hashes is well-formed iff:
64    // - The length of the last level is 1.
65    // - The length of every hash level is the length of the prior hash level divided by
66    //   hashes_per_block (`block size` / `digest length`), rounded up to the nearest
67    //   integer.
68    pub(crate) fn from_levels(levels: Vec<Box<[u8]>>, hasher: FsVerityHasher) -> MerkleTree {
69        MerkleTree { levels, hasher }
70    }
71
72    /// The root hash of the merkle tree.
73    pub fn root(&self) -> &[u8] {
74        &self.levels[self.levels.len() - 1][..]
75    }
76
77    /// Returns the levels of the tree as flat byte slices, from leaves (level 0) to root.
78    pub fn levels(&self) -> &[Box<[u8]>] {
79        &self.levels[..]
80    }
81
82    /// Returns the raw bytes of the leaf hashes (level 0 of the tree).
83    pub fn leaf_hashes(&self) -> &[u8] {
84        &self.levels[0][..]
85    }
86
87    /// Creates a `MerkleTree` from all of the bytes of a `Read`er.
88    pub fn from_reader(
89        reader: impl std::io::Read,
90        hasher: FsVerityHasher,
91    ) -> Result<MerkleTree, io::Error> {
92        match hasher {
93            FsVerityHasher::Sha256(_) => Self::from_reader_impl::<Sha256Hash>(reader, hasher),
94            FsVerityHasher::Sha512(_) => Self::from_reader_impl::<Sha512Hash>(reader, hasher),
95        }
96    }
97
98    fn from_reader_impl<D: FsVerityHash>(
99        mut reader: impl std::io::Read,
100        hasher: FsVerityHasher,
101    ) -> Result<MerkleTree, io::Error> {
102        let block_size = hasher.block_size() as usize;
103        let mut builder = MerkleTreeBuilder::<D>::new(hasher);
104        let mut buf = vec![0u8; block_size];
105        loop {
106            let size = reader.read(&mut buf)?;
107            if size == 0 {
108                break;
109            }
110            builder.write(&buf[0..size]);
111        }
112        Ok(builder.finish())
113    }
114}
115
116#[cfg(test)]
117mod tests {
118    use super::*;
119    use crate::FsVerityHasherOptions;
120    use hex::FromHex;
121
122    impl MerkleTree {
123        /// Given the index of a block of data, lookup its hash.
124        fn leaf_hash(&self, block: usize) -> &[u8] {
125            let hash_size = self.hasher.hash_size();
126            let start = block * hash_size;
127            &self.levels[0][start..start + hash_size]
128        }
129    }
130
131    #[test]
132    fn test_single_full_hash_block_sha256() {
133        let hasher = FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
134        let hashes_per_block = hasher.block_size() / hasher.hash_size();
135        let mut leafs = Vec::new();
136        let mut expected_leafs = Vec::new();
137        {
138            let block = vec![0xFF; hasher.block_size()];
139            for _i in 0..hashes_per_block {
140                leafs.push(hasher.hash_block(&block));
141                expected_leafs.push(hasher.hash_block(&block));
142            }
143        }
144        let root = hasher.hash_hashes(&leafs);
145
146        // Convert Vec<Vec<u8>> to flat Box<[u8]> for the test
147        let flat_leafs = leafs.concat().into_boxed_slice();
148        let flat_root = root.clone().into_boxed_slice();
149
150        let tree: MerkleTree = MerkleTree::from_levels(vec![flat_leafs, flat_root], hasher.clone());
151        assert_eq!(tree.root(), root);
152        for (i, leaf) in expected_leafs.iter().enumerate().take(hashes_per_block) {
153            assert_eq!(tree.leaf_hash(i), leaf);
154        }
155    }
156
157    #[test]
158    fn test_single_full_hash_block_sha512() {
159        let hasher = FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096));
160        let hashes_per_block = hasher.block_size() / hasher.hash_size();
161        let mut leafs = Vec::new();
162        let mut expected_leafs = Vec::new();
163        {
164            let block = vec![0xFF; hasher.block_size()];
165            for _i in 0..hashes_per_block {
166                leafs.push(hasher.hash_block(&block));
167                expected_leafs.push(hasher.hash_block(&block));
168            }
169        }
170        let root = hasher.hash_hashes(&leafs);
171
172        // Convert Vec<Vec<u8>> to flat Box<[u8]> for the test
173        let flat_leafs = leafs.concat().into_boxed_slice();
174        let flat_root = root.clone().into_boxed_slice();
175
176        let tree: MerkleTree = MerkleTree::from_levels(vec![flat_leafs, flat_root], hasher.clone());
177        assert_eq!(tree.root(), root);
178        for (i, leaf) in expected_leafs.iter().enumerate().take(hashes_per_block) {
179            assert_eq!(tree.leaf_hash(i), leaf);
180        }
181    }
182
183    #[test]
184    fn test_from_reader_empty_sha256() {
185        let data_to_hash = [0x00u8; 0];
186        let tree = MerkleTree::from_reader(
187            &data_to_hash[..],
188            FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)),
189        )
190        .unwrap();
191        let expected: [u8; 32] =
192            FromHex::from_hex("0000000000000000000000000000000000000000000000000000000000000000")
193                .unwrap();
194        assert_eq!(tree.root(), expected);
195    }
196
197    #[test]
198    fn test_from_reader_empty_sha512() {
199        let data_to_hash = [0x00u8; 0];
200        let tree = MerkleTree::from_reader(
201            &data_to_hash[..],
202            FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)),
203        )
204        .unwrap();
205        let expected: [u8; 64] = FromHex::from_hex("00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000").unwrap();
206        assert_eq!(tree.root(), expected);
207    }
208
209    #[test]
210    fn test_from_reader_oneblock_sha256() {
211        let data_to_hash = [0xffu8; 8192];
212        let tree = MerkleTree::from_reader(
213            &data_to_hash[..],
214            FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)),
215        )
216        .unwrap();
217        let expected: [u8; 32] =
218            FromHex::from_hex("e9c09b505561b9509f93b5c7990ed41427f708480c56306453d505e94076d600")
219                .unwrap();
220        assert_eq!(tree.root(), expected);
221    }
222
223    #[test]
224    fn test_from_reader_oneblock_sha512() {
225        let data_to_hash = [0xffu8; 8192];
226        let tree = MerkleTree::from_reader(
227            &data_to_hash[..],
228            FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 4096)),
229        )
230        .unwrap();
231        let expected: [u8; 64] = FromHex::from_hex("22750472f522bf68a1fe2a66ee1ac57759b322c634d931097b3751e3cd9fe9dd2d8f551631922bf8f675e4b5e3a38e6db11c7df0e5053e80ffbac2c2d7a0105b").unwrap();
232        assert_eq!(tree.root(), expected);
233    }
234
235    #[test]
236    fn test_from_reader_unaligned_sha256() {
237        let size = 2_109_440usize;
238        let mut the_bytes = Vec::with_capacity(size);
239        the_bytes.extend(std::iter::repeat(0xff).take(size));
240        let tree = MerkleTree::from_reader(
241            &the_bytes[..],
242            FsVerityHasher::Sha256(FsVerityHasherOptions::new(vec![0xFF; 8], 8192)),
243        )
244        .unwrap();
245        let expected: [u8; 32] =
246            FromHex::from_hex("fc21b1fbf53a4175470a7328085b5a03b2c87771cda6f1a4dbd1d1d5ce8babd5")
247                .unwrap();
248        assert_eq!(tree.root(), expected);
249    }
250
251    #[test]
252    fn test_from_reader_unaligned_sha512() {
253        let size = 2_109_440usize;
254        let mut the_bytes = Vec::with_capacity(size);
255        the_bytes.extend(std::iter::repeat(0xff).take(size));
256        let tree = MerkleTree::from_reader(
257            &the_bytes[..],
258            FsVerityHasher::Sha512(FsVerityHasherOptions::new(vec![0xFF; 8], 8192)),
259        )
260        .unwrap();
261        let expected: [u8; 64] = FromHex::from_hex("e0b048b63e814157443f42ccef9093482cee056f6afea5b9e26b772effa5077a8bac34ee8f7a877bf219e0f45a999154b0600a319c4bd7d0c9b59f8d17ce0f75").unwrap();
262        assert_eq!(tree.root(), expected);
263    }
264}
fsverity_merkle/tree.rs

fsverity_merkle/
tree.rs
