fuchsia_merkle/tree.rs
1// Copyright 2018 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::{Hash, BLOCK_SIZE};
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 8K block of data, allowing it to identify which 8K blocks of
13/// data are corrupt. A `MerkleTree` also allows individual 8K blocks of data to be verified
14/// without 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 8K 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///
26/// Each level consists of a hash for each 8K block of hashes from the previous level (or, for
27/// level 0, each 8K block of data). When computing a hash, the 8K block is prepended with a block
28/// identity.
29///
30/// A block identity is the binary OR of the starting byte index of the block within
31/// the current level and the current level index, followed by the length of the block. For level
32/// 0, the length of the block is 8K, except for the last block, which may be less than 8K. All
33/// other levels use a block length of 8K.
34#[derive(Clone, Eq, PartialEq, Ord, PartialOrd, Hash, Debug)]
35pub struct MerkleTree {
36 levels: Vec<Vec<Hash>>,
37}
38
39impl MerkleTree {
40 /// Creates a `MerkleTree` from a well-formed tree of hashes.
41 ///
42 /// A tree of hashes is well-formed iff:
43 /// - The length of the last level is 1.
44 /// - The length of every hash level is the length of the prior hash level divided by
45 /// `HASHES_PER_BLOCK`, rounded up to the nearest integer.
46 pub fn from_levels(levels: Vec<Vec<Hash>>) -> MerkleTree {
47 MerkleTree { levels }
48 }
49
50 /// The root hash of the merkle tree.
51 pub fn root(&self) -> Hash {
52 self.levels[self.levels.len() - 1][0]
53 }
54
55 /// Creates a `MerkleTree` from all of the bytes of a `Read`er.
56 ///
57 /// # Examples
58 /// ```
59 /// # use fuchsia_merkle::MerkleTree;
60 /// let data_to_hash = [0xffu8; 8192];
61 /// let tree = MerkleTree::from_reader(&data_to_hash[..]).unwrap();
62 /// assert_eq!(
63 /// tree.root(),
64 /// "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737".parse().unwrap()
65 /// );
66 /// ```
67 pub fn from_reader(mut reader: impl std::io::Read) -> Result<MerkleTree, io::Error> {
68 let mut builder = crate::builder::MerkleTreeBuilder::new();
69 let mut buf = [0u8; BLOCK_SIZE];
70 loop {
71 let size = reader.read(&mut buf)?;
72 if size == 0 {
73 break;
74 }
75 builder.write(&buf[0..size]);
76 }
77 Ok(builder.finish())
78 }
79}
80
81impl AsRef<[Vec<Hash>]> for MerkleTree {
82 fn as_ref(&self) -> &[Vec<Hash>] {
83 &self.levels[..]
84 }
85}
86
87#[cfg(test)]
88mod tests {
89 use super::*;
90 use crate::util::{hash_block, hash_hashes, HASHES_PER_BLOCK};
91
92 impl MerkleTree {
93 /// Given the index of a block of data, lookup its hash.
94 fn leaf_hash(&self, block: usize) -> Hash {
95 self.levels[0][block]
96 }
97 }
98
99 #[test]
100 fn test_single_full_hash_block() {
101 let mut leafs = Vec::new();
102 {
103 let block = vec![0xFF; BLOCK_SIZE];
104 for i in 0..HASHES_PER_BLOCK {
105 leafs.push(hash_block(&block, i * BLOCK_SIZE));
106 }
107 }
108 let root = hash_hashes(&leafs, 1, 0);
109
110 let tree = MerkleTree::from_levels(vec![leafs.clone(), vec![root]]);
111
112 assert_eq!(tree.root(), root);
113 for (i, leaf) in leafs.iter().enumerate().take(HASHES_PER_BLOCK) {
114 assert_eq!(&tree.leaf_hash(i), leaf);
115 }
116 }
117
118 #[test]
119 fn test_from_reader_empty() {
120 let data_to_hash = [0x00u8; 0];
121 let tree = MerkleTree::from_reader(&data_to_hash[..]).unwrap();
122 let expected: Hash =
123 "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b".parse().unwrap();
124 assert_eq!(tree.root(), expected);
125 }
126
127 #[test]
128 fn test_from_reader_oneblock() {
129 let data_to_hash = [0xffu8; 8192];
130 let tree = MerkleTree::from_reader(&data_to_hash[..]).unwrap();
131 let expected: Hash =
132 "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737".parse().unwrap();
133 assert_eq!(tree.root(), expected);
134 }
135
136 #[test]
137 fn test_from_reader_unaligned() {
138 let size = 2_109_440usize;
139 let mut the_bytes = Vec::with_capacity(size);
140 the_bytes.extend(std::iter::repeat_n(0xff, size));
141 let tree = MerkleTree::from_reader(&the_bytes[..]).unwrap();
142 let expected: Hash =
143 "7577266aa98ce587922fdc668c186e27f3c742fb1b732737153b70ae46973e43".parse().unwrap();
144 assert_eq!(tree.root(), expected);
145 }
146
147 #[test]
148 fn test_from_reader_error_propagation() {
149 const CUSTOM_ERROR_MESSAGE: &str = "merkle tree custom error message";
150 struct ReaderSuccessThenError {
151 been_called: bool,
152 }
153
154 impl std::io::Read for ReaderSuccessThenError {
155 fn read(&mut self, buf: &mut [u8]) -> std::io::Result<usize> {
156 if !self.been_called {
157 self.been_called = true;
158 buf[0] = 0;
159 Ok(1)
160 } else {
161 Err(io::Error::other(CUSTOM_ERROR_MESSAGE))
162 }
163 }
164 }
165
166 let reader = ReaderSuccessThenError { been_called: false };
167 let result = MerkleTree::from_reader(reader);
168 assert_eq!(result.unwrap_err().to_string(), CUSTOM_ERROR_MESSAGE);
169 }
170}