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

fsverity_merkle/
tree.rs
