corevm_engine/
util.rs

1use alloc::collections::VecDeque;
2use codec::{Encode, Output};
3use jam_types::Hash;
4
5pub fn hash_encoded<E: Encode>(x: E) -> Hash {
6	let mut hasher = Blake2bHasher::new();
7	x.encode_to(&mut hasher);
8	hasher.into_hash()
9}
10
11pub fn hash_raw(data: &[u8]) -> Hash {
12	let mut hasher = Blake2bHasher::new();
13	hasher.update(data);
14	hasher.into_hash()
15}
16
17/// Compute the hash of the concatenation of byte slices.
18pub fn hash_raw_concat<I, T>(items: I) -> Hash
19where
20	I: IntoIterator<Item = T>,
21	T: AsRef<[u8]>,
22{
23	let mut hasher = Blake2bHasher::new();
24	for item in items.into_iter() {
25		hasher.update(item.as_ref());
26	}
27	hasher.into_hash()
28}
29
30struct Blake2bHasher {
31	state: blake2b_simd::State,
32}
33
34impl Blake2bHasher {
35	fn new() -> Self {
36		let state = blake2b_simd::Params::new().hash_length(32).to_state();
37		Self { state }
38	}
39
40	fn update(&mut self, data: &[u8]) {
41		self.state.update(data);
42	}
43
44	fn into_hash(self) -> Hash {
45		self.state.finalize().as_bytes().try_into().expect("Hash length set to 32")
46	}
47}
48
49impl Output for Blake2bHasher {
50	fn write(&mut self, bytes: &[u8]) {
51		self.update(bytes);
52	}
53}
54
55pub struct HexDisplay<'a>(pub &'a [u8]);
56
57impl core::fmt::Display for HexDisplay<'_> {
58	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
59		for b in self.0 {
60			write!(f, "{:02x}", b)?;
61		}
62		Ok(())
63	}
64}
65
66/// Compute Merkle tree root of the pre-hashed items.
67pub fn merkle_tree_root_prehashed<I>(hashes: I) -> Hash
68where
69	I: IntoIterator<Item = Hash>,
70{
71	let iter = hashes.into_iter();
72	let capacity = {
73		let (min_len, max_len) = iter.size_hint();
74		max_len.unwrap_or(min_len).next_multiple_of(2)
75	};
76	let mut queue = VecDeque::with_capacity(capacity);
77	for hash in iter {
78		queue.push_back(hash);
79	}
80	merkle_tree_root_impl(queue)
81}
82
83fn merkle_tree_root_impl(mut queue: VecDeque<Hash>) -> Hash {
84	while queue.len() > 1 {
85		if queue.len() % 2 != 0 {
86			// Pad with zero hash.
87			queue.push_back(Default::default());
88		}
89		let n = queue.len() / 2;
90		for _ in 0..n {
91			let h1 = queue.pop_front().expect("We extract exactly queue.len() elements");
92			let h2 = queue.pop_front().expect("We extract exactly queue.len() elements");
93			queue.push_back(merkle_node_hash(&h1, &h2));
94		}
95	}
96	queue.pop_front().unwrap_or_default()
97}
98
99fn merkle_node_hash(left: &[u8], right: &[u8]) -> Hash {
100	hash_raw_concat([b"node", left, right])
101}
102
103pub fn merkle_leaf_hash(leaf: &[u8]) -> Hash {
104	hash_raw_concat([b"leaf", leaf])
105}
106
107#[cfg(test)]
108mod tests {
109	use super::*;
110
111	/// Compute Merkle tree root of the items.
112	fn merkle_tree_root<I, T>(items: I) -> Hash
113	where
114		I: IntoIterator<Item = T>,
115		T: AsRef<[u8]>,
116	{
117		merkle_tree_root_prehashed(items.into_iter().map(|item| merkle_leaf_hash(item.as_ref())))
118	}
119
120	#[test]
121	fn merkle_tree_root_works() {
122		// 0 elements.
123		assert_eq!(Hash::default(), merkle_tree_root([[0_u8; 100]; 0].iter()));
124		// 1 element.
125		let data1 = [0_u8, 1, 2, 3];
126		assert_eq!(merkle_leaf_hash(&data1[..]), merkle_tree_root([data1].iter()));
127		// 2 elements.
128		let data2 = [4_u8, 5, 6, 7];
129		assert_eq!(
130			merkle_node_hash(&merkle_leaf_hash(&data1[..]), &merkle_leaf_hash(&data2[..])),
131			merkle_tree_root([data1, data2].iter())
132		);
133		// 3 elements.
134		let data3 = [8_u8, 9, 10, 11];
135		assert_eq!(
136			merkle_node_hash(
137				&merkle_node_hash(&merkle_leaf_hash(&data1[..]), &merkle_leaf_hash(&data2[..])),
138				&merkle_node_hash(&merkle_leaf_hash(&data3[..]), &Hash::default())
139			),
140			merkle_tree_root([data1, data2, data3].iter())
141		);
142	}
143}
corevm_engine/util.rs

corevm_engine/
util.rs
