binary_merkle_tree/
lib.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18#![cfg_attr(not(feature = "std"), no_std)]
19#![warn(missing_docs)]
20
21//! This crate implements a simple binary Merkle Tree utilities required for inter-op with Ethereum
22//! bridge & Solidity contract.
23//!
24//! The implementation is optimised for usage within Substrate Runtime and supports no-std
25//! compilation targets.
26//!
27//! Merkle Tree is constructed from arbitrary-length leaves, that are initially hashed using the
28//! same hasher as the inner nodes.
29//! Inner nodes are created by concatenating child hashes and hashing again. The implementation
30//! does not perform any sorting of the input data (leaves) nor when inner nodes are created.
31//!
32//! If the number of leaves is not even, last leaf (hash of) is promoted to the upper layer.
33#[cfg(not(feature = "std"))]
34extern crate alloc;
35#[cfg(not(feature = "std"))]
36use alloc::vec;
37#[cfg(not(feature = "std"))]
38use alloc::vec::Vec;
39
40use codec::{Decode, Encode};
41use hash_db::Hasher;
42
43/// Construct a root hash of a Binary Merkle Tree created from given leaves.
44///
45/// See crate-level docs for details about Merkle Tree construction.
46///
47/// In case an empty list of leaves is passed the function returns a 0-filled hash.
48pub fn merkle_root<H, I>(leaves: I) -> H::Out
49where
50	H: Hasher,
51	H::Out: Default + AsRef<[u8]>,
52	I: IntoIterator,
53	I::Item: AsRef<[u8]>,
54{
55	let iter = leaves.into_iter().map(|l| <H as Hasher>::hash(l.as_ref()));
56	merkelize::<H, _, _>(iter, &mut ()).into()
57}
58
59/// Construct a root hash of a Binary Merkle Tree created from given leaves.
60///
61/// This is a raw version of the [`merkle_root`] function that expects the hashes of the leaves and
62/// not the leaves itself.
63///
64/// See crate-level docs for details about Merkle Tree construction.
65///
66/// In case an empty list of leaves is passed the function returns a 0-filled hash.
67pub fn merkle_root_raw<H, I>(leaves: I) -> H::Out
68where
69	H: Hasher,
70	H::Out: Default + AsRef<[u8]>,
71	I: IntoIterator<Item = H::Out>,
72{
73	merkelize::<H, _, _>(leaves.into_iter(), &mut ()).into()
74}
75
76fn merkelize<H, V, I>(leaves: I, visitor: &mut V) -> H::Out
77where
78	H: Hasher,
79	H::Out: Default + AsRef<[u8]>,
80	V: Visitor<H::Out>,
81	I: Iterator<Item = H::Out>,
82{
83	let upper = Vec::with_capacity((leaves.size_hint().1.unwrap_or(0).saturating_add(1)) / 2);
84	let mut next = match merkelize_row::<H, _, _>(leaves, upper, visitor) {
85		Ok(root) => return root,
86		Err(next) if next.is_empty() => return H::Out::default(),
87		Err(next) => next,
88	};
89
90	let mut upper = Vec::with_capacity((next.len().saturating_add(1)) / 2);
91	loop {
92		visitor.move_up();
93
94		match merkelize_row::<H, _, _>(next.drain(..), upper, visitor) {
95			Ok(root) => return root,
96			Err(t) => {
97				// swap collections to avoid allocations
98				upper = next;
99				next = t;
100			},
101		};
102	}
103}
104
105/// A generated merkle proof.
106///
107/// The structure contains all necessary data to later on verify the proof and the leaf itself.
108#[derive(Debug, PartialEq, Eq, Encode, Decode)]
109pub struct MerkleProof<H, L> {
110	/// Root hash of generated merkle tree.
111	pub root: H,
112	/// Proof items (does not contain the leaf hash, nor the root obviously).
113	///
114	/// This vec contains all inner node hashes necessary to reconstruct the root hash given the
115	/// leaf hash.
116	pub proof: Vec<H>,
117	/// Number of leaves in the original tree.
118	///
119	/// This is needed to detect a case where we have an odd number of leaves that "get promoted"
120	/// to upper layers.
121	pub number_of_leaves: u32,
122	/// Index of the leaf the proof is for (0-based).
123	pub leaf_index: u32,
124	/// Leaf content.
125	pub leaf: L,
126}
127
128/// A trait of object inspecting merkle root creation.
129///
130/// It can be passed to [`merkelize_row`] or [`merkelize`] functions and will be notified
131/// about tree traversal.
132trait Visitor<T> {
133	/// We are moving one level up in the tree.
134	fn move_up(&mut self);
135
136	/// We are creating an inner node from given `left` and `right` nodes.
137	///
138	/// Note that in case of last odd node in the row `right` might be empty.
139	/// The method will also visit the `root` hash (level 0).
140	///
141	/// The `index` is an index of `left` item.
142	fn visit(&mut self, index: u32, left: &Option<T>, right: &Option<T>);
143}
144
145/// No-op implementation of the visitor.
146impl<T> Visitor<T> for () {
147	fn move_up(&mut self) {}
148	fn visit(&mut self, _index: u32, _left: &Option<T>, _right: &Option<T>) {}
149}
150
151/// Maximum number of nodes in a single-leaf proof, i.e. `ceil(log2(number_of_leaves))`.
152fn proof_capacity(number_of_leaves: u32) -> usize {
153	// `checked_ilog2` is `None` for 0, so empty and single-leaf trees map to a capacity of 0.
154	number_of_leaves
155		.saturating_sub(1)
156		.checked_ilog2()
157		.map_or(0, |log| log as usize + 1)
158}
159
160/// The struct collects a proof for single leaf.
161struct ProofCollection<T> {
162	proof: Vec<T>,
163	position: u32,
164}
165
166impl<T> ProofCollection<T> {
167	fn new(position: u32, number_of_leaves: u32) -> Self {
168		// Size the proof up front so collecting it does not reallocate.
169		ProofCollection { proof: Vec::with_capacity(proof_capacity(number_of_leaves)), position }
170	}
171}
172
173impl<T: Copy> Visitor<T> for ProofCollection<T> {
174	fn move_up(&mut self) {
175		self.position /= 2;
176	}
177
178	fn visit(&mut self, index: u32, left: &Option<T>, right: &Option<T>) {
179		// we are at left branch - right goes to the proof.
180		if self.position == index {
181			if let Some(right) = right {
182				self.proof.push(*right);
183			}
184		}
185		// we are at right branch - left goes to the proof.
186		if self.position == index + 1 {
187			if let Some(left) = left {
188				self.proof.push(*left);
189			}
190		}
191	}
192}
193
194/// Construct a Merkle Proof for leaves given by indices.
195///
196/// The function constructs a (partial) Merkle Tree first and stores all elements required
197/// to prove requested item (leaf) given the root hash.
198///
199/// Both the Proof and the Root Hash is returned.
200///
201/// # Panic
202///
203/// The function will panic if given `leaf_index` is greater than the number of leaves.
204pub fn merkle_proof<H, I, T>(leaves: I, leaf_index: u32) -> MerkleProof<H::Out, T>
205where
206	H: Hasher,
207	H::Out: Default + Copy + AsRef<[u8]>,
208	I: IntoIterator<Item = T>,
209	I::IntoIter: ExactSizeIterator,
210	T: AsRef<[u8]>,
211{
212	let mut leaf = None;
213	let iter = leaves.into_iter().enumerate().map(|(idx, l)| {
214		let hash = <H as Hasher>::hash(l.as_ref());
215		if idx as u32 == leaf_index {
216			leaf = Some(l);
217		}
218		hash
219	});
220
221	let number_of_leaves = iter.len() as u32;
222	let mut collect_proof = ProofCollection::new(leaf_index, number_of_leaves);
223
224	let root = merkelize::<H, _, _>(iter, &mut collect_proof);
225	let leaf = leaf.expect("Requested `leaf_index` is greater than number of leaves.");
226
227	#[cfg(feature = "debug")]
228	log::debug!(
229		"[merkle_proof] Proof: {:?}",
230		collect_proof
231			.proof
232			.iter()
233			.map(|s| array_bytes::bytes2hex("", s))
234			.collect::<Vec<_>>()
235	);
236
237	MerkleProof { root, proof: collect_proof.proof, number_of_leaves, leaf_index, leaf }
238}
239
240/// Construct a Merkle Proof for leaves given by indices.
241///
242/// This is a raw version of the [`merkle_proof`] function that expects the hashes of the leaves and
243/// not the leaves itself.
244///
245/// The function constructs a (partial) Merkle Tree first and stores all elements required
246/// to prove requested item (leaf) given the root hash.
247///
248/// Both the Proof and the Root Hash is returned.
249///
250/// # Panic
251///
252/// The function will panic if given `leaf_index` is greater than the number of leaves.
253pub fn merkle_proof_raw<H, I>(leaves: I, leaf_index: u32) -> MerkleProof<H::Out, H::Out>
254where
255	H: Hasher,
256	H::Out: Default + Copy + AsRef<[u8]>,
257	I: IntoIterator<Item = H::Out>,
258	I::IntoIter: ExactSizeIterator,
259{
260	let mut leaf = None;
261	let iter = leaves.into_iter().enumerate().map(|(idx, l)| {
262		let hash = l;
263		if idx as u32 == leaf_index {
264			leaf = Some(l);
265		}
266		hash
267	});
268
269	let number_of_leaves = iter.len() as u32;
270	let mut collect_proof = ProofCollection::new(leaf_index, number_of_leaves);
271
272	let root = merkelize::<H, _, _>(iter, &mut collect_proof);
273	let leaf = leaf.expect("Requested `leaf_index` is greater than number of leaves.");
274
275	#[cfg(feature = "debug")]
276	log::debug!(
277		"[merkle_proof] Proof: {:?}",
278		collect_proof
279			.proof
280			.iter()
281			.map(|s| array_bytes::bytes2hex("", s))
282			.collect::<Vec<_>>()
283	);
284
285	MerkleProof { root, proof: collect_proof.proof, number_of_leaves, leaf_index, leaf }
286}
287
288/// Leaf node for proof verification.
289///
290/// Can be either a value that needs to be hashed first,
291/// or the hash itself.
292#[derive(Debug, PartialEq, Eq)]
293pub enum Leaf<'a, H> {
294	/// Leaf content.
295	Value(&'a [u8]),
296	/// Hash of the leaf content.
297	Hash(H),
298}
299
300impl<'a, H, T: AsRef<[u8]>> From<&'a T> for Leaf<'a, H> {
301	fn from(v: &'a T) -> Self {
302		Leaf::Value(v.as_ref())
303	}
304}
305
306/// Verify Merkle Proof correctness versus given root hash.
307///
308/// The proof is NOT expected to contain leaf hash as the first
309/// element, but only all adjacent nodes required to eventually by process of
310/// concatenating and hashing end up with given root hash.
311///
312/// The proof must not contain the root hash.
313pub fn verify_proof<'a, H, P, L>(
314	root: &'a H::Out,
315	proof: P,
316	number_of_leaves: u32,
317	leaf_index: u32,
318	leaf: L,
319) -> bool
320where
321	H: Hasher,
322	H::Out: PartialEq + AsRef<[u8]>,
323	P: IntoIterator<Item = H::Out>,
324	L: Into<Leaf<'a, H::Out>>,
325{
326	if leaf_index >= number_of_leaves {
327		return false;
328	}
329
330	let leaf_hash = match leaf.into() {
331		Leaf::Value(content) => <H as Hasher>::hash(content),
332		Leaf::Hash(hash) => hash,
333	};
334
335	let hash_len = <H as Hasher>::LENGTH;
336	let mut combined = vec![0_u8; hash_len * 2];
337	let mut position = leaf_index;
338	let mut width = number_of_leaves;
339	let computed = proof.into_iter().fold(leaf_hash, |a, b| {
340		if position % 2 == 1 || position + 1 == width {
341			combined[..hash_len].copy_from_slice(&b.as_ref());
342			combined[hash_len..].copy_from_slice(&a.as_ref());
343		} else {
344			combined[..hash_len].copy_from_slice(&a.as_ref());
345			combined[hash_len..].copy_from_slice(&b.as_ref());
346		}
347		let hash = <H as Hasher>::hash(&combined);
348		#[cfg(feature = "debug")]
349		log::debug!(
350			"[verify_proof]: (a, b) {:?}, {:?} => {:?} ({:?}) hash",
351			array_bytes::bytes2hex("", a),
352			array_bytes::bytes2hex("", b),
353			array_bytes::bytes2hex("", hash),
354			array_bytes::bytes2hex("", &combined)
355		);
356		position /= 2;
357		width = ((width - 1) / 2) + 1;
358		hash
359	});
360
361	root == &computed
362}
363
364/// Processes a single row (layer) of a tree by taking pairs of elements,
365/// concatenating them, hashing and placing into resulting vector.
366///
367/// In case only one element is provided it is returned via `Ok` result, in any other case (also an
368/// empty iterator) an `Err` with the inner nodes of upper layer is returned.
369fn merkelize_row<H, V, I>(
370	mut iter: I,
371	mut next: Vec<H::Out>,
372	visitor: &mut V,
373) -> Result<H::Out, Vec<H::Out>>
374where
375	H: Hasher,
376	H::Out: AsRef<[u8]>,
377	V: Visitor<H::Out>,
378	I: Iterator<Item = H::Out>,
379{
380	#[cfg(feature = "debug")]
381	log::debug!("[merkelize_row]");
382	next.clear();
383
384	let hash_len = <H as Hasher>::LENGTH;
385	let mut index = 0;
386	let mut combined = vec![0_u8; hash_len * 2];
387	loop {
388		let a = iter.next();
389		let b = iter.next();
390		visitor.visit(index, &a, &b);
391
392		#[cfg(feature = "debug")]
393		log::debug!(
394			"  {:?}\n  {:?}",
395			a.as_ref().map(|s| array_bytes::bytes2hex("", s)),
396			b.as_ref().map(|s| array_bytes::bytes2hex("", s))
397		);
398
399		index += 2;
400		match (a, b) {
401			(Some(a), Some(b)) => {
402				combined[..hash_len].copy_from_slice(a.as_ref());
403				combined[hash_len..].copy_from_slice(b.as_ref());
404
405				next.push(<H as Hasher>::hash(&combined));
406			},
407			// Odd number of items. Promote the item to the upper layer.
408			(Some(a), None) if !next.is_empty() => {
409				next.push(a);
410			},
411			// Last item = root.
412			(Some(a), None) => return Ok(a),
413			// Finish up, no more items.
414			_ => {
415				#[cfg(feature = "debug")]
416				log::debug!(
417					"[merkelize_row] Next: {:?}",
418					next.iter().map(|s| array_bytes::bytes2hex("", s)).collect::<Vec<_>>()
419				);
420				return Err(next);
421			},
422		}
423	}
424}
425
426#[cfg(test)]
427mod tests {
428	use super::*;
429	use sp_core::H256;
430	use sp_runtime::traits::Keccak256;
431
432	#[test]
433	fn should_generate_empty_root() {
434		// given
435		let data: Vec<[u8; 1]> = Default::default();
436
437		// when
438		let out = merkle_root::<Keccak256, _>(data);
439
440		// then
441		assert_eq!(
442			array_bytes::bytes2hex("", out),
443			"0000000000000000000000000000000000000000000000000000000000000000"
444		);
445	}
446
447	#[test]
448	fn should_generate_single_root() {
449		// given
450		let data = vec![array_bytes::hex2array_unchecked::<_, 20>(
451			"E04CC55ebEE1cBCE552f250e85c57B70B2E2625b",
452		)];
453
454		// when
455		let out = merkle_root::<Keccak256, _>(data);
456
457		// then
458		assert_eq!(
459			array_bytes::bytes2hex("", out),
460			"aeb47a269393297f4b0a3c9c9cfd00c7a4195255274cf39d83dabc2fcc9ff3d7"
461		);
462	}
463
464	#[test]
465	fn should_generate_root_pow_2() {
466		// given
467		let data = vec![
468			array_bytes::hex2array_unchecked::<_, 20>("E04CC55ebEE1cBCE552f250e85c57B70B2E2625b"),
469			array_bytes::hex2array_unchecked::<_, 20>("25451A4de12dcCc2D166922fA938E900fCc4ED24"),
470		];
471
472		// when
473		let out = merkle_root::<Keccak256, _>(data);
474
475		// then
476		assert_eq!(
477			array_bytes::bytes2hex("", out),
478			"697ea2a8fe5b03468548a7a413424a6292ab44a82a6f5cc594c3fa7dda7ce402"
479		);
480	}
481
482	#[test]
483	fn should_generate_root_complex() {
484		let test = |root, data| {
485			assert_eq!(array_bytes::bytes2hex("", &merkle_root::<Keccak256, _>(data)), root);
486		};
487
488		test(
489			"aff1208e69c9e8be9b584b07ebac4e48a1ee9d15ce3afe20b77a4d29e4175aa3",
490			vec!["a", "b", "c"],
491		);
492
493		test(
494			"b8912f7269068901f231a965adfefbc10f0eedcfa61852b103efd54dac7db3d7",
495			vec!["a", "b", "a"],
496		);
497
498		test(
499			"dc8e73fe6903148ff5079baecc043983625c23b39f31537e322cd0deee09fa9c",
500			vec!["a", "b", "a", "b"],
501		);
502
503		test(
504			"fb3b3be94be9e983ba5e094c9c51a7d96a4fa2e5d8e891df00ca89ba05bb1239",
505			vec!["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"],
506		);
507	}
508
509	#[test]
510	fn should_generate_and_verify_proof_simple() {
511		// given
512		let data = vec!["a", "b", "c"];
513
514		// when
515		let proof0 = merkle_proof::<Keccak256, _, _>(data.clone(), 0);
516		assert!(verify_proof::<Keccak256, _, _>(
517			&proof0.root,
518			proof0.proof.clone(),
519			data.len() as _,
520			proof0.leaf_index,
521			&proof0.leaf,
522		));
523
524		let proof1 = merkle_proof::<Keccak256, _, _>(data.clone(), 1);
525		assert!(verify_proof::<Keccak256, _, _>(
526			&proof1.root,
527			proof1.proof,
528			data.len() as _,
529			proof1.leaf_index,
530			&proof1.leaf,
531		));
532
533		let proof2 = merkle_proof::<Keccak256, _, _>(data.clone(), 2);
534		assert!(verify_proof::<Keccak256, _, _>(
535			&proof2.root,
536			proof2.proof,
537			data.len() as _,
538			proof2.leaf_index,
539			&proof2.leaf
540		));
541
542		// then
543		assert_eq!(
544			array_bytes::bytes2hex("", &proof0.root),
545			array_bytes::bytes2hex("", &proof1.root)
546		);
547		assert_eq!(
548			array_bytes::bytes2hex("", &proof2.root),
549			array_bytes::bytes2hex("", &proof1.root)
550		);
551
552		assert!(!verify_proof::<Keccak256, _, _>(
553			&array_bytes::hex2array_unchecked(
554				"fb3b3be94be9e983ba5e094c9c51a7d96a4fa2e5d8e891df00ca89ba05bb1239"
555			)
556			.into(),
557			proof0.proof,
558			data.len() as _,
559			proof0.leaf_index,
560			&proof0.leaf
561		));
562
563		assert!(!verify_proof::<Keccak256, _, _>(
564			&proof0.root.into(),
565			vec![],
566			data.len() as _,
567			proof0.leaf_index,
568			&proof0.leaf
569		));
570	}
571
572	#[test]
573	fn should_generate_and_verify_proof_complex() {
574		// given
575		let data = vec!["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"];
576
577		for l in 0..data.len() as u32 {
578			// when
579			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
580			// then
581			assert!(verify_proof::<Keccak256, _, _>(
582				&proof.root,
583				proof.proof,
584				data.len() as _,
585				proof.leaf_index,
586				&proof.leaf
587			));
588		}
589	}
590
591	#[test]
592	fn should_generate_and_verify_proof_large() {
593		// given
594		let mut data = vec![];
595		for i in 1..16 {
596			for c in 'a'..'z' {
597				if !(c as usize).is_multiple_of(i) {
598					data.push(c.to_string());
599				}
600			}
601
602			for l in 0..data.len() as u32 {
603				// when
604				let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
605				// then
606				assert!(verify_proof::<Keccak256, _, _>(
607					&proof.root,
608					proof.proof,
609					data.len() as _,
610					proof.leaf_index,
611					&proof.leaf
612				));
613			}
614		}
615	}
616
617	#[test]
618	fn should_generate_and_verify_proof_large_tree() {
619		// given
620		let mut data = vec![];
621		for i in 0..6000 {
622			data.push(format!("{}", i));
623		}
624
625		for l in (0..data.len() as u32).step_by(13) {
626			// when
627			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
628			// then
629			assert!(verify_proof::<Keccak256, _, _>(
630				&proof.root,
631				proof.proof,
632				data.len() as _,
633				proof.leaf_index,
634				&proof.leaf
635			));
636		}
637	}
638
639	#[test]
640	#[should_panic]
641	fn should_panic_on_invalid_leaf_index() {
642		merkle_proof::<Keccak256, _, _>(vec!["a"], 5);
643	}
644
645	#[test]
646	fn should_generate_and_verify_proof_on_test_data() {
647		let addresses = vec![
648			"0x9aF1Ca5941148eB6A3e9b9C741b69738292C533f",
649			"0xDD6ca953fddA25c496165D9040F7F77f75B75002",
650			"0x60e9C47B64Bc1C7C906E891255EaEC19123E7F42",
651			"0xfa4859480Aa6D899858DE54334d2911E01C070df",
652			"0x19B9b128470584F7209eEf65B69F3624549Abe6d",
653			"0xC436aC1f261802C4494504A11fc2926C726cB83b",
654			"0xc304C8C2c12522F78aD1E28dD86b9947D7744bd0",
655			"0xDa0C2Cba6e832E55dE89cF4033affc90CC147352",
656			"0xf850Fd22c96e3501Aad4CDCBf38E4AEC95622411",
657			"0x684918D4387CEb5E7eda969042f036E226E50642",
658			"0x963F0A1bFbb6813C0AC88FcDe6ceB96EA634A595",
659			"0x39B38ad74b8bCc5CE564f7a27Ac19037A95B6099",
660			"0xC2Dec7Fdd1fef3ee95aD88EC8F3Cd5bd4065f3C7",
661			"0x9E311f05c2b6A43C2CCF16fB2209491BaBc2ec01",
662			"0x927607C30eCE4Ef274e250d0bf414d4a210b16f0",
663			"0x98882bcf85E1E2DFF780D0eB360678C1cf443266",
664			"0xFBb50191cd0662049E7C4EE32830a4Cc9B353047",
665			"0x963854fc2C358c48C3F9F0A598B9572c581B8DEF",
666			"0xF9D7Bc222cF6e3e07bF66711e6f409E51aB75292",
667			"0xF2E3fd32D063F8bBAcB9e6Ea8101C2edd899AFe6",
668			"0x407a5b9047B76E8668570120A96d580589fd1325",
669			"0xEAD9726FAFB900A07dAd24a43AE941d2eFDD6E97",
670			"0x42f5C8D9384034A9030313B51125C32a526b6ee8",
671			"0x158fD2529Bc4116570Eb7C80CC76FEf33ad5eD95",
672			"0x0A436EE2E4dEF3383Cf4546d4278326Ccc82514E",
673			"0x34229A215db8FeaC93Caf8B5B255e3c6eA51d855",
674			"0xEb3B7CF8B1840242CB98A732BA464a17D00b5dDF",
675			"0x2079692bf9ab2d6dc7D79BBDdEE71611E9aA3B72",
676			"0x46e2A67e5d450e2Cf7317779f8274a2a630f3C9B",
677			"0xA7Ece4A5390DAB18D08201aE18800375caD78aab",
678			"0x15E1c0D24D62057Bf082Cb2253dA11Ef0d469570",
679			"0xADDEF4C9b5687Eb1F7E55F2251916200A3598878",
680			"0xe0B16Fb96F936035db2b5A68EB37D470fED2f013",
681			"0x0c9A84993feaa779ae21E39F9793d09e6b69B62D",
682			"0x3bc4D5148906F70F0A7D1e2756572655fd8b7B34",
683			"0xFf4675C26903D5319795cbd3a44b109E7DDD9fDe",
684			"0xCec4450569A8945C6D2Aba0045e4339030128a92",
685			"0x85f0584B10950E421A32F471635b424063FD8405",
686			"0xb38bEe7Bdc0bC43c096e206EFdFEad63869929E3",
687			"0xc9609466274Fef19D0e58E1Ee3b321D5C141067E",
688			"0xa08EA868cF75268E7401021E9f945BAe73872ecc",
689			"0x67C9Cb1A29E964Fe87Ff669735cf7eb87f6868fE",
690			"0x1B6BEF636aFcdd6085cD4455BbcC93796A12F6E2",
691			"0x46B37b243E09540b55cF91C333188e7D5FD786dD",
692			"0x8E719E272f62Fa97da93CF9C941F5e53AA09e44a",
693			"0xa511B7E7DB9cb24AD5c89fBb6032C7a9c2EfA0a5",
694			"0x4D11FDcAeD335d839132AD450B02af974A3A66f8",
695			"0xB8cf790a5090E709B4619E1F335317114294E17E",
696			"0x7f0f57eA064A83210Cafd3a536866ffD2C5eDCB3",
697			"0xC03C848A4521356EF800e399D889e9c2A25D1f9E",
698			"0xC6b03DF05cb686D933DD31fCa5A993bF823dc4FE",
699			"0x58611696b6a8102cf95A32c25612E4cEF32b910F",
700			"0x2ed4bC7197AEF13560F6771D930Bf907772DE3CE",
701			"0x3C5E58f334306be029B0e47e119b8977B2639eb4",
702			"0x288646a1a4FeeC560B349d210263c609aDF649a6",
703			"0xb4F4981E0d027Dc2B3c86afA0D0fC03d317e83C0",
704			"0xaAE4A87F8058feDA3971f9DEd639Ec9189aA2500",
705			"0x355069DA35E598913d8736E5B8340527099960b8",
706			"0x3cf5A0F274cd243C0A186d9fCBdADad089821B93",
707			"0xca55155dCc4591538A8A0ca322a56EB0E4aD03C4",
708			"0xE824D0268366ec5C4F23652b8eD70D552B1F2b8B",
709			"0x84C3e9B25AE8a9b39FF5E331F9A597F2DCf27Ca9",
710			"0xcA0018e278751De10d26539915d9c7E7503432FE",
711			"0xf13077dE6191D6c1509ac7E088b8BE7Fe656c28b",
712			"0x7a6bcA1ec9Db506e47ac6FD86D001c2aBc59C531",
713			"0xeA7f9A2A9dd6Ba9bc93ca615C3Ddf26973146911",
714			"0x8D0d8577e16F8731d4F8712BAbFa97aF4c453458",
715			"0xB7a7855629dF104246997e9ACa0E6510df75d0ea",
716			"0x5C1009BDC70b0C8Ab2e5a53931672ab448C17c89",
717			"0x40B47D1AfefEF5eF41e0789F0285DE7b1C31631C",
718			"0x5086933d549cEcEB20652CE00973703CF10Da373",
719			"0xeb364f6FE356882F92ae9314fa96116Cf65F47d8",
720			"0xdC4D31516A416cEf533C01a92D9a04bbdb85EE67",
721			"0x9b36E086E5A274332AFd3D8509e12ca5F6af918d",
722			"0xBC26394fF36e1673aE0608ce91A53B9768aD0D76",
723			"0x81B5AB400be9e563fA476c100BE898C09966426c",
724			"0x9d93C8ae5793054D28278A5DE6d4653EC79e90FE",
725			"0x3B8E75804F71e121008991E3177fc942b6c28F50",
726			"0xC6Eb5886eB43dD473f5BB4e21e56E08dA464D9B4",
727			"0xfdf1277b71A73c813cD0e1a94B800f4B1Db66DBE",
728			"0xc2ff2cCc98971556670e287Ff0CC39DA795231ad",
729			"0x76b7E1473f0D0A87E9B4a14E2B179266802740f5",
730			"0xA7Bc965660a6EF4687CCa4F69A97563163A3C2Ef",
731			"0xB9C2b47888B9F8f7D03dC1de83F3F55E738CebD3",
732			"0xEd400162E6Dd6bD2271728FFb04176bF770De94a",
733			"0xE3E8331156700339142189B6E555DCb2c0962750",
734			"0xbf62e342Bc7706a448EdD52AE871d9C4497A53b1",
735			"0xb9d7A1A111eed75714a0AcD2dd467E872eE6B03D",
736			"0x03942919DFD0383b8c574AB8A701d89fd4bfA69D",
737			"0x0Ef4C92355D3c8c7050DFeb319790EFCcBE6fe9e",
738			"0xA6895a3cf0C60212a73B3891948ACEcF1753f25E",
739			"0x0Ed509239DB59ef3503ded3d31013C983d52803A",
740			"0xc4CE8abD123BfAFc4deFf37c7D11DeCd5c350EE4",
741			"0x4A4Bf59f7038eDcd8597004f35d7Ee24a7Bdd2d3",
742			"0x5769E8e8A2656b5ed6b6e6fa2a2bFAeaf970BB87",
743			"0xf9E15cCE181332F4F57386687c1776b66C377060",
744			"0xc98f8d4843D56a46C21171900d3eE538Cc74dbb5",
745			"0x3605965B47544Ce4302b988788B8195601AE4dEd",
746			"0xe993BDfdcAac2e65018efeE0F69A12678031c71d",
747			"0x274fDf8801385D3FAc954BCc1446Af45f5a8304c",
748			"0xBFb3f476fcD6429F4a475bA23cEFdDdd85c6b964",
749			"0x806cD16588Fe812ae740e931f95A289aFb4a4B50",
750			"0xa89488CE3bD9C25C3aF797D1bbE6CA689De79d81",
751			"0xd412f1AfAcf0Ebf3Cd324593A231Fc74CC488B12",
752			"0xd1f715b2D7951d54bc31210BbD41852D9BF98Ed1",
753			"0xf65aD707c344171F467b2ADba3d14f312219cE23",
754			"0x2971a4b242e9566dEF7bcdB7347f5E484E11919B",
755			"0x12b113D6827E07E7D426649fBd605f427da52314",
756			"0x1c6CA45171CDb9856A6C9Dba9c5F1216913C1e97",
757			"0x11cC6ee1d74963Db23294FCE1E3e0A0555779CeA",
758			"0x8Aa1C721255CDC8F895E4E4c782D86726b068667",
759			"0xA2cDC1f37510814485129aC6310b22dF04e9Bbf0",
760			"0xCf531b71d388EB3f5889F1f78E0d77f6fb109767",
761			"0xBe703e3545B2510979A0cb0C440C0Fba55c6dCB5",
762			"0x30a35886F989db39c797D8C93880180Fdd71b0c8",
763			"0x1071370D981F60c47A9Cd27ac0A61873a372cBB2",
764			"0x3515d74A11e0Cb65F0F46cB70ecf91dD1712daaa",
765			"0x50500a3c2b7b1229c6884505D00ac6Be29Aecd0C",
766			"0x9A223c2a11D4FD3585103B21B161a2B771aDA3d1",
767			"0xd7218df03AD0907e6c08E707B15d9BD14285e657",
768			"0x76CfD72eF5f93D1a44aD1F80856797fBE060c70a",
769			"0x44d093cB745944991EFF5cBa151AA6602d6f5420",
770			"0x626516DfF43bf09A71eb6fd1510E124F96ED0Cde",
771			"0x6530824632dfe099304E2DC5701cA99E6d031E08",
772			"0x57e6c423d6a7607160d6379A0c335025A14DaFC0",
773			"0x3966D4AD461Ef150E0B10163C81E79b9029E69c3",
774			"0xF608aCfd0C286E23721a3c347b2b65039f6690F1",
775			"0xbfB8FAac31A25646681936977837f7740fCd0072",
776			"0xd80aa634a623a7ED1F069a1a3A28a173061705c7",
777			"0x9122a77B36363e24e12E1E2D73F87b32926D3dF5",
778			"0x62562f0d1cD31315bCCf176049B6279B2bfc39C2",
779			"0x48aBF7A2a7119e5675059E27a7082ba7F38498b2",
780			"0xb4596983AB9A9166b29517acD634415807569e5F",
781			"0x52519D16E20BC8f5E96Da6d736963e85b2adA118",
782			"0x7663893C3dC0850EfC5391f5E5887eD723e51B83",
783			"0x5FF323a29bCC3B5b4B107e177EccEF4272959e61",
784			"0xee6e499AdDf4364D75c05D50d9344e9daA5A9AdF",
785			"0x1631b0BD31fF904aD67dD58994C6C2051CDe4E75",
786			"0xbc208e9723D44B9811C428f6A55722a26204eEF2",
787			"0xe76103a222Ee2C7Cf05B580858CEe625C4dc00E1",
788			"0xC71Bb2DBC51760f4fc2D46D84464410760971B8a",
789			"0xB4C18811e6BFe564D69E12c224FFc57351f7a7ff",
790			"0xD11DB0F5b41061A887cB7eE9c8711438844C298A",
791			"0xB931269934A3D4432c084bAAc3d0de8143199F4f",
792			"0x070037cc85C761946ec43ea2b8A2d5729908A2a1",
793			"0x2E34aa8C95Ffdbb37f14dCfBcA69291c55Ba48DE",
794			"0x052D93e8d9220787c31d6D83f87eC7dB088E998f",
795			"0x498dAC6C69b8b9ad645217050054840f1D91D029",
796			"0xE4F7D60f9d84301e1fFFd01385a585F3A11F8E89",
797			"0xEa637992f30eA06460732EDCBaCDa89355c2a107",
798			"0x4960d8Da07c27CB6Be48a79B96dD70657c57a6bF",
799			"0x7e471A003C8C9fdc8789Ded9C3dbe371d8aa0329",
800			"0xd24265Cc10eecb9e8d355CCc0dE4b11C556E74D7",
801			"0xDE59C8f7557Af779674f41CA2cA855d571018690",
802			"0x2fA8A6b3b6226d8efC9d8f6EBDc73Ca33DDcA4d8",
803			"0xe44102664c6c2024673Ff07DFe66E187Db77c65f",
804			"0x94E3f4f90a5f7CBF2cc2623e66B8583248F01022",
805			"0x0383EdBbc21D73DEd039E9C1Ff6bf56017b4CC40",
806			"0x64C3E49898B88d1E0f0d02DA23E0c00A2Cd0cA99",
807			"0xF4ccfB67b938d82B70bAb20975acFAe402E812E1",
808			"0x4f9ee5829e9852E32E7BC154D02c91D8E203e074",
809			"0xb006312eF9713463bB33D22De60444Ba95609f6B",
810			"0x7Cbe76ef69B52110DDb2e3b441C04dDb11D63248",
811			"0x70ADEEa65488F439392B869b1Df7241EF317e221",
812			"0x64C0bf8AA36Ba590477585Bc0D2BDa7970769463",
813			"0xA4cDc98593CE52d01Fe5Ca47CB3dA5320e0D7592",
814			"0xc26B34D375533fFc4c5276282Fa5D660F3d8cbcB",
815		];
816		let root: H256 = array_bytes::hex2array_unchecked(
817			"72b0acd7c302a84f1f6b6cefe0ba7194b7398afb440e1b44a9dbbe270394ca53",
818		)
819		.into();
820
821		let data = addresses
822			.into_iter()
823			.map(|address| array_bytes::hex2bytes_unchecked(&address))
824			.collect::<Vec<_>>();
825
826		for l in 0..data.len() as u32 {
827			// when
828			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
829			assert_eq!(array_bytes::bytes2hex("", &proof.root), array_bytes::bytes2hex("", &root));
830			assert_eq!(proof.leaf_index, l);
831			assert_eq!(&proof.leaf, &data[l as usize]);
832
833			// then
834			assert!(verify_proof::<Keccak256, _, _>(
835				&proof.root,
836				proof.proof,
837				data.len() as _,
838				proof.leaf_index,
839				&proof.leaf
840			));
841		}
842
843		let proof = merkle_proof::<Keccak256, _, _>(data.clone(), data.len() as u32 - 1);
844
845		assert_eq!(
846			proof,
847			MerkleProof {
848				root,
849				proof: vec![
850					array_bytes::hex2array_unchecked(
851						"340bcb1d49b2d82802ddbcf5b85043edb3427b65d09d7f758fbc76932ad2da2f"
852					)
853					.into(),
854					array_bytes::hex2array_unchecked(
855						"ba0580e5bd530bc93d61276df7969fb5b4ae8f1864b4a28c280249575198ff1f"
856					)
857					.into(),
858					array_bytes::hex2array_unchecked(
859						"d02609d2bbdb28aa25f58b85afec937d5a4c85d37925bce6d0cf802f9d76ba79"
860					)
861					.into(),
862					array_bytes::hex2array_unchecked(
863						"ae3f8991955ed884613b0a5f40295902eea0e0abe5858fc520b72959bc016d4e"
864					)
865					.into(),
866				],
867				number_of_leaves: data.len() as _,
868				leaf_index: data.len() as u32 - 1,
869				leaf: array_bytes::hex2array_unchecked::<_, 20>(
870					"c26B34D375533fFc4c5276282Fa5D660F3d8cbcB"
871				)
872				.to_vec(),
873			}
874		);
875	}
876
877	#[test]
878	fn proof_capacity_matches_ceil_log2() {
879		// (number_of_leaves, expected `ceil(log2(n))`).
880		let cases = [
881			(0, 0),
882			(1, 0),
883			(2, 1),
884			(3, 2),
885			(4, 2),
886			(5, 3),
887			(7, 3),
888			(8, 3),
889			(9, 4),
890			(1 << 20, 20),
891			(u32::MAX, 32),
892		];
893		for (n, expected) in cases {
894			assert_eq!(proof_capacity(n), expected, "n={n}");
895		}
896	}
897
898	#[test]
899	fn proof_length_never_exceeds_tree_height() {
900		// A proof must never exceed `proof_capacity`. Cover sizes either side of a power of
901		// two (128), where an odd node gets promoted instead of adding a proof element.
902		for n in 1u32..=130 {
903			let data: Vec<H256> = (0..n).map(|i| H256::repeat_byte(i as u8)).collect();
904			let max = proof_capacity(n);
905			for leaf_index in 0..n {
906				let proof = merkle_proof::<Keccak256, _, _>(data.clone(), leaf_index);
907				assert!(
908					proof.proof.len() <= max,
909					"n={n}, leaf={leaf_index}: proof len {} exceeds height {max}",
910					proof.proof.len(),
911				);
912			}
913		}
914	}
915}
binary_merkle_tree/lib.rs

binary_merkle_tree/
lib.rs
