fuchsia_merkle/
util.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 mundane::hash::{Digest, Hasher, Sha256};
6use std::mem::{size_of, size_of_val};
7
8use crate::{Hash, BLOCK_SIZE, HASH_SIZE};
9
10pub(crate) const HASHES_PER_BLOCK: usize = BLOCK_SIZE / HASH_SIZE;
11
12type BlockIdentity = [u8; size_of::<u64>() + size_of::<u32>()];
13
14/// Generate the bytes representing a block's identity.
15fn make_identity(length: usize, level: usize, offset: usize) -> BlockIdentity {
16    let offset_or_level = (offset as u64 | level as u64).to_le_bytes();
17    let length = (length as u32).to_le_bytes();
18    let mut ret: BlockIdentity = [0; size_of::<BlockIdentity>()];
19    let (ret_offset_or_level, ret_length) = ret.split_at_mut(size_of_val(&offset_or_level));
20    ret_offset_or_level.copy_from_slice(&offset_or_level);
21    ret_length.copy_from_slice(&length);
22    ret
23}
24
25/// Compute the merkle hash of a block of data.
26///
27/// A merkle hash is the SHA-256 hash of a block of data with a small header built from the length
28/// of the data, the level of the tree (0 for data blocks), and the offset into the level. The
29/// block will be zero filled if its len is less than [`BLOCK_SIZE`], except for when the first
30/// data block is completely empty.
31///
32/// # Panics
33///
34/// Panics if `block.len()` exceeds [`BLOCK_SIZE`] or if `offset` is not aligned to [`BLOCK_SIZE`]
35pub fn hash_block(block: &[u8], offset: usize) -> Hash {
36    assert!(block.len() <= BLOCK_SIZE);
37    assert!(offset % BLOCK_SIZE == 0);
38
39    let mut hasher = Sha256::default();
40    hasher.update(&make_identity(block.len(), 0, offset));
41    hasher.update(block);
42    // Zero fill block up to BLOCK_SIZE. As a special case, if the first data block is completely
43    // empty, it is not zero filled.
44    if block.len() != BLOCK_SIZE && !(block.is_empty() && offset == 0) {
45        hasher.update(&vec![0; BLOCK_SIZE - block.len()]);
46    }
47
48    Hash::from(hasher.finish().bytes())
49}
50
51/// Compute the merkle hash of a block of hashes.
52///
53/// Both `hash_block` and `hash_hashes` will zero fill incomplete buffers, but unlike `hash_block`,
54/// which includes the actual buffer size in the hash, `hash_hashes` always uses a size of
55/// [`BLOCK_SIZE`] when computing the hash. Therefore, the following inputs are equivalent:
56/// ```ignore
57/// let data_hash = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b"
58///     .parse()
59///     .unwrap();
60/// let zero_hash = "0000000000000000000000000000000000000000000000000000000000000000"
61///     .parse()
62///     .unwrap();
63/// let hash_of_single_hash = fuchsia_merkle::hash_hashes(&vec![data_hash], 0, 0);
64/// let hash_of_single_hash_and_zero_hash =
65///     fuchsia_merkle::hash_hashes(&vec![data_hash, zero_hash], 0, 0);
66/// assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
67/// ```
68///
69/// # Panics
70///
71/// Panics if any of the following conditions are met:
72/// - `hashes.len()` is 0
73/// - `hashes.len() > HASHES_PER_BLOCK`
74/// - `level` is 0
75/// - `offset` is not aligned to [`BLOCK_SIZE`]
76pub(crate) fn hash_hashes(hashes: &[Hash], level: usize, offset: usize) -> Hash {
77    assert_ne!(hashes.len(), 0);
78    assert!(hashes.len() <= HASHES_PER_BLOCK);
79    assert!(level > 0);
80    assert!(offset % BLOCK_SIZE == 0);
81
82    let mut hasher = Sha256::default();
83    hasher.update(&make_identity(BLOCK_SIZE, level, offset));
84    for hash in hashes.iter() {
85        hasher.update(hash.as_bytes());
86    }
87    for _ in 0..(HASHES_PER_BLOCK - hashes.len()) {
88        hasher.update(&[0; HASH_SIZE]);
89    }
90
91    Hash::from(hasher.finish().bytes())
92}
93
94/// Initializes the crypto library used for hashing. This is only necessary if using `hash_block`
95/// directly.
96pub fn crypto_library_init() {
97    unsafe { CRYPTO_library_init() }
98}
99
100extern "C" {
101    #[allow(dead_code)]
102    fn CRYPTO_library_init();
103}
104
105#[cfg(test)]
106mod tests {
107    use super::*;
108
109    #[test]
110    fn test_hash_block_empty() {
111        let block = [];
112        let hash = hash_block(&block[..], 0);
113        let expected =
114            "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b".parse().unwrap();
115        assert_eq!(hash, expected);
116    }
117
118    #[test]
119    fn test_hash_block_single() {
120        let block = vec![0xFF; 8192];
121        let hash = hash_block(&block[..], 0);
122        let expected =
123            "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737".parse().unwrap();
124        assert_eq!(hash, expected);
125    }
126
127    #[test]
128    fn test_hash_hashes_full_block() {
129        let mut leafs = Vec::new();
130        {
131            let block = vec![0xFF; BLOCK_SIZE];
132            for i in 0..HASHES_PER_BLOCK {
133                leafs.push(hash_block(&block, i * BLOCK_SIZE));
134            }
135        }
136        let root = hash_hashes(&leafs, 1, 0);
137        let expected =
138            "1e6e9c870e2fade25b1b0288ac7c216f6fae31c1599c0c57fb7030c15d385a8d".parse().unwrap();
139        assert_eq!(root, expected);
140    }
141
142    #[test]
143    fn test_hash_hashes_zero_pad_same_length() {
144        let data_hash =
145            "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b".parse().unwrap();
146        let zero_hash =
147            "0000000000000000000000000000000000000000000000000000000000000000".parse().unwrap();
148        let hash_of_single_hash = hash_hashes(&[data_hash], 1, 0);
149        let hash_of_single_hash_and_zero_hash = hash_hashes(&[data_hash, zero_hash], 1, 0);
150        assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
151    }
152}
fuchsia_merkle/util.rs

fuchsia_merkle/
util.rs
