drive_proof_verifier/block_proof/
merkle.rs1use super::BlockProofError;
5use sha2::{Digest, Sha256};
6
7const LEAF_PREFIX: [u8; 1] = [0];
8const INNER_PREFIX: [u8; 1] = [1];
9const HASH_SIZE: usize = 32;
10
11fn leaf_hash(leaf: &[u8]) -> [u8; 32] {
12 Sha256::new()
13 .chain_update(LEAF_PREFIX)
14 .chain_update(leaf)
15 .finalize()
16 .into()
17}
18
19fn inner_hash(left: &[u8], right: &[u8]) -> [u8; 32] {
20 Sha256::new()
21 .chain_update(INNER_PREFIX)
22 .chain_update(left)
23 .chain_update(right)
24 .finalize()
25 .into()
26}
27
28fn split_point(length: usize) -> usize {
30 1 << (usize::BITS - 1 - (length - 1).leading_zeros())
31}
32
33pub fn merkle_root<T: AsRef<[u8]>>(leaves: &[T]) -> [u8; 32] {
35 match leaves {
36 [] => Sha256::digest([]).into(),
37 [leaf] => leaf_hash(leaf.as_ref()),
38 _ => {
39 let (left, right) = leaves.split_at(split_point(leaves.len()));
40 inner_hash(&merkle_root(left), &merkle_root(right))
41 }
42 }
43}
44
45#[derive(Debug)]
48pub struct MerkleTree {
49 pub root: [u8; 32],
51 pub paths: Vec<Vec<Vec<u8>>>,
53}
54
55impl MerkleTree {
56 pub fn new<T: AsRef<[u8]>>(leaves: &[T], selected: &[usize]) -> Self {
59 Self::build(leaves, 0, selected)
60 }
61
62 fn build<T: AsRef<[u8]>>(leaves: &[T], first: usize, selected: &[usize]) -> Self {
63 if selected.is_empty() {
64 return Self {
65 root: merkle_root(leaves),
66 paths: Vec::new(),
67 };
68 }
69 if leaves.len() < 2 {
70 return Self {
71 root: merkle_root(leaves),
72 paths: vec![Vec::new(); selected.len()],
73 };
74 }
75
76 let split = split_point(leaves.len());
77 let (left_leaves, right_leaves) = leaves.split_at(split);
78 let (left_selected, right_selected) =
79 selected.split_at(selected.partition_point(|&position| position < first + split));
80 let left = Self::build(left_leaves, first, left_selected);
81 let right = Self::build(right_leaves, first + split, right_selected);
82
83 let root = inner_hash(&left.root, &right.root);
84 let paths = left
85 .paths
86 .into_iter()
87 .map(|mut path| {
88 path.push(right.root.to_vec());
89 path
90 })
91 .chain(right.paths.into_iter().map(|mut path| {
92 path.push(left.root.to_vec());
93 path
94 }))
95 .collect();
96 Self { root, paths }
97 }
98}
99
100pub fn root_from_path(
107 index: u32,
108 total: u32,
109 leaf: &[u8],
110 path: &[Vec<u8>],
111) -> Result<[u8; 32], BlockProofError> {
112 if index >= total {
113 return Err(BlockProofError::IndexOutOfRange { index, total });
114 }
115
116 let (mut position, mut size) = (index as usize, total as usize);
118 let mut leaf_is_on_the_left = Vec::new();
119 while size > 1 {
120 let split = split_point(size);
121 if position < split {
122 leaf_is_on_the_left.push(true);
123 size = split;
124 } else {
125 leaf_is_on_the_left.push(false);
126 position -= split;
127 size -= split;
128 }
129 }
130 let malformed = path.len() != leaf_is_on_the_left.len()
131 || path.iter().any(|sibling| sibling.len() != HASH_SIZE);
132 if malformed {
133 return Err(BlockProofError::MalformedPath { index, total });
134 }
135
136 let root = path.iter().zip(leaf_is_on_the_left.iter().rev()).fold(
138 leaf_hash(leaf),
139 |hash, (sibling, &on_the_left)| {
140 if on_the_left {
141 inner_hash(&hash, sibling)
142 } else {
143 inner_hash(sibling, &hash)
144 }
145 },
146 );
147 Ok(root)
148}
149
150#[cfg(test)]
151mod tests {
152 use super::*;
153
154 const TENDERDASH_ROOT: &str =
156 "0b007fb915eb9b2a146f54b1c86ec53b664f8e455b7660b0b6ee13edc0d921c0";
157 const TENDERDASH_PATHS: [&[&str]; 7] = [
158 &[
159 "3145c409f259b7c53e32036090ff76751025a2498ba9823ef718cac50b4e616f",
160 "bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
161 "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
162 ],
163 &[
164 "305df59f9590c3c9ac63d2b2743c388e3792449078cebf7fb3dbe6471643b2b7",
165 "bd45ff28796704d88bdac51b1df553fda59837b616d6d1cb2114dbc3b087ff69",
166 "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
167 ],
168 &[
169 "f76836325aec5699d8d71f8e42e9d47c5c29b08059ba296384f7ca40ad3a40ae",
170 "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
171 "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
172 ],
173 &[
174 "fca89f57c9f8c8eb4047a7ff9d333acf9e0f3384b20b255bceab0f216dcca267",
175 "60a53eed0de87a90c8e59427c59c46253c33a76a09502a51801300927b7e6bdc",
176 "8eae6bd3b3a07f1f75ee72a531629e6eb31e42e62f760e47de52a53c3641ef23",
177 ],
178 &[
179 "8f1593cb92f429d9340b9bbc1f0bb122adf8026c42a4a42142e2168931727236",
180 "676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d",
181 "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
182 ],
183 &[
184 "ea9fc1a1b6e191b460d0d6306e3e870c173f39330f13cda1b70cfc72bdc398ba",
185 "676f3782f5b3a5fb4370ed49572cedc523f4a66322269c85f2af0509d17b0a4d",
186 "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
187 ],
188 &[
189 "985bb5d36b927800876871da925a7e82abe83a9ddba5882920a007a55ea2b376",
190 "bdd1c5ff55b19cb6b0e7c761bf9a6ccaa27fbbfc07b74f1fabb6e911a0bd2ab3",
191 ],
192 ];
193
194 fn tenderdash_leaves() -> Vec<Vec<u8>> {
195 (0..7)
196 .map(|index| format!("leaf-{index}").into_bytes())
197 .collect()
198 }
199
200 fn numbered_leaves(total: usize) -> Vec<Vec<u8>> {
201 (0..total)
202 .map(|index| index.to_be_bytes().to_vec())
203 .collect()
204 }
205
206 fn hex_path(path: &[Vec<u8>]) -> Vec<String> {
207 path.iter().map(hex::encode).collect()
208 }
209
210 #[test]
211 fn should_build_the_same_tree_as_tenderdash() {
212 let leaves = tenderdash_leaves();
213
214 let tree = MerkleTree::new(&leaves, &(0..leaves.len()).collect::<Vec<_>>());
215
216 assert_eq!(hex::encode(tree.root), TENDERDASH_ROOT);
217 for (path, expected) in tree.paths.iter().zip(TENDERDASH_PATHS) {
218 assert_eq!(hex_path(path), expected);
219 }
220 }
221
222 #[test]
223 fn should_follow_the_paths_tenderdash_builds_to_its_root() {
224 let leaves = tenderdash_leaves();
225
226 for (index, (leaf, path)) in leaves.iter().zip(TENDERDASH_PATHS).enumerate() {
227 let path = path
228 .iter()
229 .map(|hash| hex::decode(hash).unwrap())
230 .collect::<Vec<_>>();
231
232 let root = root_from_path(index as u32, 7, leaf, &path).unwrap();
233
234 assert_eq!(hex::encode(root), TENDERDASH_ROOT, "leaf {index}");
235 }
236 }
237
238 #[test]
239 fn should_hash_edge_trees_like_rfc_6962() {
240 assert_eq!(
241 hex::encode(merkle_root::<Vec<u8>>(&[])),
242 "e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855"
243 );
244 assert_eq!(
245 hex::encode(merkle_root(&[Vec::new()])),
246 "6e340b9cffb37a989ca544e6bb780a2c78901d3fb33738768511a30617afa01d"
247 );
248 assert_eq!(
249 hex::encode(merkle_root(&[b"L123456".to_vec()])),
250 "395aa064aa4c29f7010acfe3f25db9485bbd4b91897b6ad7ad547639252b4d56"
251 );
252 assert_eq!(
253 hex::encode(inner_hash(b"N123", b"N456")),
254 "aa217fe888e47007fa15edab33c2b492a722cb106c64667fc2b044444de66bbb"
255 );
256 }
257
258 #[test]
259 fn should_compute_the_same_root_without_building_paths() {
260 for total in 0..=33usize {
261 let leaves = numbered_leaves(total);
262 let all = (0..total).collect::<Vec<_>>();
263
264 assert_eq!(merkle_root(&leaves), MerkleTree::new(&leaves, &all).root);
265 }
266 }
267
268 #[test]
269 fn should_build_only_the_selected_paths() {
270 let leaves = tenderdash_leaves();
271
272 for selected in [vec![], vec![0], vec![6], vec![1, 4], vec![2, 3, 5]] {
273 let tree = MerkleTree::new(&leaves, &selected);
274
275 assert_eq!(hex::encode(tree.root), TENDERDASH_ROOT);
276 assert_eq!(tree.paths.len(), selected.len());
277 for (path, position) in tree.paths.iter().zip(&selected) {
278 assert_eq!(hex_path(path), TENDERDASH_PATHS[*position]);
279 }
280 }
281 }
282
283 #[test]
284 fn should_give_every_leaf_a_path_to_the_root() {
285 for total in 1..=33usize {
286 let leaves = numbered_leaves(total);
287 let tree = MerkleTree::new(&leaves, &(0..total).collect::<Vec<_>>());
288
289 for (index, leaf) in leaves.iter().enumerate() {
290 let root =
291 root_from_path(index as u32, total as u32, leaf, &tree.paths[index]).unwrap();
292 assert_eq!(root, tree.root, "leaf {index} of {total}");
293 }
294 }
295 }
296
297 #[test]
298 fn should_not_reach_the_root_from_another_position() {
299 for total in 2..=33usize {
300 let leaves = numbered_leaves(total);
301 let tree = MerkleTree::new(&leaves, &(0..total).collect::<Vec<_>>());
302
303 for (index, leaf) in leaves.iter().enumerate() {
304 for claimed in (0..total).filter(|&claimed| claimed != index) {
305 let root =
306 root_from_path(claimed as u32, total as u32, leaf, &tree.paths[index]);
307 assert_ne!(root.ok(), Some(tree.root), "leaf {index} as {claimed}");
308 }
309 }
310 }
311 }
312
313 #[test]
314 fn should_not_reach_the_root_from_another_leaf() {
315 let leaves = tenderdash_leaves();
316 let tree = MerkleTree::new(&leaves, &[3]);
317
318 let root = root_from_path(3, 7, b"leaf-4", &tree.paths[0]).unwrap();
319
320 assert_ne!(root, tree.root);
321 }
322
323 #[test]
324 fn should_refuse_a_position_outside_the_tree() {
325 assert_eq!(
326 root_from_path(7, 7, b"leaf", &[]),
327 Err(BlockProofError::IndexOutOfRange { index: 7, total: 7 })
328 );
329 assert_eq!(
330 root_from_path(0, 0, b"leaf", &[]),
331 Err(BlockProofError::IndexOutOfRange { index: 0, total: 0 })
332 );
333 }
334
335 #[test]
336 fn should_refuse_a_path_of_the_wrong_shape() {
337 let leaves = tenderdash_leaves();
338 let tree = MerkleTree::new(&leaves, &[2]);
339 let path = &tree.paths[0];
340 let malformed = Err(BlockProofError::MalformedPath { index: 2, total: 7 });
341
342 assert_eq!(root_from_path(2, 7, b"leaf-2", &path[1..]), malformed);
344 let mut longer = path.clone();
345 longer.push(vec![0; 32]);
346 assert_eq!(root_from_path(2, 7, b"leaf-2", &longer), malformed);
347 let mut truncated = path.clone();
348 truncated[0].pop();
349 assert_eq!(root_from_path(2, 7, b"leaf-2", &truncated), malformed);
350
351 assert_eq!(
353 root_from_path(0, 1, b"leaf", &[vec![0; 32]]),
354 Err(BlockProofError::MalformedPath { index: 0, total: 1 })
355 );
356 assert_eq!(root_from_path(0, 1, b"leaf", &[]), Ok(leaf_hash(b"leaf")));
357 }
358}