| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| use bytes::BufMut; |
| use mundane::hash::{Digest, Hasher, Sha256}; |
| use std::io::Cursor; |
| use std::mem::size_of; |
| |
| use crate::hash::Hash; |
| use crate::BLOCK_SIZE; |
| |
| pub(crate) const HASH_SIZE: usize = 32; |
| pub(crate) const HASHES_PER_BLOCK: usize = BLOCK_SIZE / HASH_SIZE; |
| |
| type BlockIdentity = [u8; size_of::<u64>() + size_of::<u32>()]; |
| |
| /// Generate the bytes representing a block's identity. |
| fn make_identity(length: usize, level: usize, offset: usize) -> BlockIdentity { |
| let mut identity = [0; size_of::<BlockIdentity>()]; |
| let mut cursor = Cursor::new(&mut identity); |
| cursor.put_u64_le(offset as u64 | level as u64); |
| cursor.put_u32_le(length as u32); |
| identity |
| } |
| |
| /// Compute the merkle hash of a block of data. |
| /// |
| /// A merkle hash is the SHA-256 hash of a block of data with a small header built from the length |
| /// of the data, the level of the tree (0 for data blocks), and the offset into the level. The |
| /// block will be zero filled if its len is less than [`BLOCK_SIZE`], except for when the first |
| /// data block is completely empty. |
| /// |
| /// # Panics |
| /// |
| /// Panics if `block.len()` exceeds [`BLOCK_SIZE`] or if `offset` is not aligned to [`BLOCK_SIZE`] |
| pub(crate) fn hash_block(block: &[u8], offset: usize) -> Hash { |
| assert!(block.len() <= BLOCK_SIZE); |
| assert!(offset % BLOCK_SIZE == 0); |
| |
| let mut hasher = Sha256::default(); |
| hasher.update(&make_identity(block.len(), 0, offset)); |
| hasher.update(block); |
| // Zero fill block up to BLOCK_SIZE. As a special case, if the first data block is completely |
| // empty, it is not zero filled. |
| if block.len() != BLOCK_SIZE && !(block.len() == 0 && offset == 0) { |
| hasher.update(&vec![0; BLOCK_SIZE - block.len()]); |
| } |
| |
| Hash::from(hasher.finish().bytes()) |
| } |
| |
| /// Compute the merkle hash of a block of hashes. |
| /// |
| /// Both `hash_block` and `hash_hashes` will zero fill incomplete buffers, but unlike `hash_block`, |
| /// which includes the actual buffer size in the hash, `hash_hashes` always uses a size of |
| /// [`BLOCK_SIZE`] when computing the hash. Therefore, the following inputs are equivalent: |
| /// ```ignore |
| /// let data_hash = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b" |
| /// .parse() |
| /// .unwrap(); |
| /// let zero_hash = "0000000000000000000000000000000000000000000000000000000000000000" |
| /// .parse() |
| /// .unwrap(); |
| /// let hash_of_single_hash = fuchsia_merkle::hash_hashes(&vec![data_hash], 0, 0); |
| /// let hash_of_single_hash_and_zero_hash = |
| /// fuchsia_merkle::hash_hashes(&vec![data_hash, zero_hash], 0, 0); |
| /// assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash); |
| /// ``` |
| /// |
| /// # Panics |
| /// |
| /// Panics if any of the following conditions are met: |
| /// - `hashes.len()` is 0 |
| /// - `hashes.len() > HASHES_PER_BLOCK` |
| /// - `level` is 0 |
| /// - `offset` is not aligned to [`BLOCK_SIZE`] |
| pub(crate) fn hash_hashes(hashes: &[Hash], level: usize, offset: usize) -> Hash { |
| assert_ne!(hashes.len(), 0); |
| assert!(hashes.len() <= HASHES_PER_BLOCK); |
| assert!(level > 0); |
| assert!(offset % BLOCK_SIZE == 0); |
| |
| let mut hasher = Sha256::default(); |
| hasher.update(&make_identity(BLOCK_SIZE, level, offset)); |
| for ref hash in hashes.iter() { |
| hasher.update(hash.as_bytes()); |
| } |
| for _ in 0..(HASHES_PER_BLOCK - hashes.len()) { |
| hasher.update(&[0; HASH_SIZE]); |
| } |
| |
| Hash::from(hasher.finish().bytes()) |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use super::*; |
| |
| #[test] |
| fn test_hash_block_empty() { |
| let block = vec![]; |
| let hash = hash_block(&block[..], 0); |
| let expected = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b" |
| .parse() |
| .unwrap(); |
| assert_eq!(hash, expected); |
| } |
| |
| #[test] |
| fn test_hash_block_single() { |
| let block = vec![0xFF; 8192]; |
| let hash = hash_block(&block[..], 0); |
| let expected = "68d131bc271f9c192d4f6dcd8fe61bef90004856da19d0f2f514a7f4098b0737" |
| .parse() |
| .unwrap(); |
| assert_eq!(hash, expected); |
| } |
| |
| #[test] |
| fn test_hash_hashes_full_block() { |
| let mut leafs = Vec::new(); |
| { |
| let block = vec![0xFF; BLOCK_SIZE]; |
| for i in 0..HASHES_PER_BLOCK { |
| leafs.push(hash_block(&block, i * BLOCK_SIZE)); |
| } |
| } |
| let root = hash_hashes(&leafs, 1, 0); |
| let expected = "1e6e9c870e2fade25b1b0288ac7c216f6fae31c1599c0c57fb7030c15d385a8d" |
| .parse() |
| .unwrap(); |
| assert_eq!(root, expected); |
| } |
| |
| #[test] |
| fn test_hash_hashes_zero_pad_same_length() { |
| let data_hash = "15ec7bf0b50732b49f8228e07d24365338f9e3ab994b00af08e5a3bffe55fd8b" |
| .parse() |
| .unwrap(); |
| let zero_hash = "0000000000000000000000000000000000000000000000000000000000000000" |
| .parse() |
| .unwrap(); |
| let hash_of_single_hash = hash_hashes(&vec![data_hash], 1, 0); |
| let hash_of_single_hash_and_zero_hash = hash_hashes(&vec![data_hash, zero_hash], 1, 0); |
| assert_eq!(hash_of_single_hash, hash_of_single_hash_and_zero_hash); |
| } |
| } |