merkle_root/
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 sha2::{Digest, Sha256};
6use std::mem::{size_of, size_of_val};
7#[cfg(feature = "xxhash")]
8use xxhash_rust::xxh3::xxh3_64;
9
10use crate::{Hash, HashAlgorithm, BLOCK_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
25pub(crate) fn hash_size(algorithm: HashAlgorithm) -> usize {
26    match algorithm {
27        HashAlgorithm::SHA256 => 32,
28        #[cfg(feature = "xxhash")]
29        HashAlgorithm::XXHash64 => 8,
30    }
31}
32
33pub(crate) fn hashes_per_block(algorithm: HashAlgorithm) -> usize {
34    BLOCK_SIZE / hash_size(algorithm)
35}
36
37pub(crate) fn hash(data: &[u8], algorithm: HashAlgorithm) -> Vec<u8> {
38    match algorithm {
39        HashAlgorithm::SHA256 => Sha256::digest(data).to_vec(),
40        #[cfg(feature = "xxhash")]
41        HashAlgorithm::XXHash64 => xxh3_64(data).to_le_bytes().to_vec(),
42    }
43}
44
45/// Compute the merkle hash of a block of data.
46///
47/// A merkle hash is the hash of a block of data with a small header built from the length
48/// of the data, the level of the tree (0 for data blocks), and the offset into the level. The
49/// block will be zero filled if its len is less than [`BLOCK_SIZE`], except for when the first
50/// data block is completely empty.
51///
52/// # Panics
53///
54/// Panics if `block.len()` exceeds [`BLOCK_SIZE`] or if `offset` is not aligned to [`BLOCK_SIZE`]
55pub fn hash_block(block: &[u8], offset: usize, algorithm: HashAlgorithm) -> Hash {
56    assert!(block.len() <= BLOCK_SIZE);
57    assert!(offset % BLOCK_SIZE == 0);
58
59    let mut to_hash = Vec::<u8>::new();
60    to_hash.extend_from_slice(&make_identity(block.len(), 0, offset));
61    to_hash.extend_from_slice(block);
62    // Zero fill block up to BLOCK_SIZE. As a special case, if the first data block is completely
63    // empty, it is not zero filled.
64    if block.len() != BLOCK_SIZE && !(block.is_empty() && offset == 0) {
65        to_hash.extend_from_slice(&vec![0; BLOCK_SIZE - block.len()]);
66    }
67
68    hash(&to_hash, algorithm)
69}
70
71/// Compute the merkle hash of a block of hashes.
72///
73/// Both `hash_block` and `hash_hashes` will zero fill incomplete buffers, but unlike `hash_block`,
74/// which includes the actual buffer size in the hash, `hash_hashes` always uses a size of
75/// [`BLOCK_SIZE`] when computing the hash. Therefore, the following inputs are equivalent:
76/// ```ignore
77/// let data_hash = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b"
78///     .parse()
79///     .unwrap();
80/// let zero_hash = "0000000000000000000000000000000000000000000000000000000000000000"
81///     .parse()
82///     .unwrap();
83/// let hash_of_single_hash = merkle_root::hash_hashes(&vec![data_hash], 0, 0);
84/// let hash_of_single_hash_and_zero_hash =
85///     merkle_root::hash_hashes(&vec![data_hash, zero_hash], 0, 0);
86/// assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
87/// ```
88///
89/// # Panics
90///
91/// Panics if any of the following conditions are met:
92/// - `hashes.len()` is 0
93/// - `hashes.len() > HASHES_PER_BLOCK`
94/// - `level` is 0
95/// - `offset` is not aligned to [`BLOCK_SIZE`]
96pub fn hash_hashes(hashes: &[Hash], level: usize, offset: usize, algorithm: HashAlgorithm) -> Hash {
97    assert_ne!(hashes.len(), 0);
98    assert!(hashes.len() <= hashes_per_block(algorithm));
99    assert!(level > 0);
100    assert!(offset % BLOCK_SIZE == 0);
101
102    let mut to_hash = Vec::<u8>::new();
103    to_hash.extend_from_slice(&make_identity(BLOCK_SIZE, level, offset));
104    for hash in hashes.iter() {
105        to_hash.extend_from_slice(hash);
106    }
107    for _ in 0..(hashes_per_block(algorithm) - hashes.len()) {
108        // Repeat zero hash to fill the block (of size) HASH_SIZE.
109        to_hash.extend_from_slice(&vec![0; hash_size(algorithm)]);
110    }
111
112    hash(&to_hash, algorithm)
113}
114
115#[cfg(test)]
116mod tests {
117    use super::*;
118
119    pub const HASH: HashAlgorithm = HashAlgorithm::SHA256;
120
121    #[test]
122    fn test_hash_block_empty() {
123        let block = [];
124        let hash = hash_block(&block[..], 0, HASH);
125        let expected = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b";
126        assert_eq!(expected, &hex::encode(hash));
127    }
128
129    #[test]
130    fn test_hash_block_single() {
131        let block = vec![0xFF; 8192];
132        let hash = hash_block(&block[..], 0, HASH);
133        let expected = "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737";
134        assert_eq!(expected, &hex::encode(hash));
135    }
136
137    #[test]
138    fn test_hash_hashes_full_block() {
139        let mut leafs = Vec::new();
140        {
141            let block = vec![0xFF; BLOCK_SIZE];
142            for i in 0..hashes_per_block(HASH) {
143                leafs.push(hash_block(&block, i * BLOCK_SIZE, HASH));
144            }
145        }
146        let root = hash_hashes(&leafs, 1, 0, HASH);
147        let expected = "1e6e9c870e2fade25b1b0288ac7c216f6fae31c1599c0c57fb7030c15d385a8d";
148        assert_eq!(expected, &hex::encode(root));
149    }
150
151    #[test]
152    fn test_hash_hashes_zero_pad_same_length() {
153        let data_hash = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b";
154        let zero_hash = "0000000000000000000000000000000000000000000000000000000000000000";
155        let hash_of_single_hash = hash_hashes(&[hex::decode(data_hash).unwrap()], 1, 0, HASH);
156        let hash_of_single_hash_and_zero_hash = hash_hashes(
157            &[
158                hex::decode(data_hash).unwrap(),
159                hex::decode(zero_hash).unwrap(),
160            ],
161            1,
162            0,
163            HASH,
164        );
165        assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash);
166    }
167}
merkle_root/util.rs

merkle_root/
util.rs
