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/// The struct collects a proof for single leaf.
152struct ProofCollection<T> {
153	proof: Vec<T>,
154	position: u32,
155}
156
157impl<T> ProofCollection<T> {
158	fn new(position: u32) -> Self {
159		ProofCollection { proof: Default::default(), position }
160	}
161}
162
163impl<T: Copy> Visitor<T> for ProofCollection<T> {
164	fn move_up(&mut self) {
165		self.position /= 2;
166	}
167
168	fn visit(&mut self, index: u32, left: &Option<T>, right: &Option<T>) {
169		// we are at left branch - right goes to the proof.
170		if self.position == index {
171			if let Some(right) = right {
172				self.proof.push(*right);
173			}
174		}
175		// we are at right branch - left goes to the proof.
176		if self.position == index + 1 {
177			if let Some(left) = left {
178				self.proof.push(*left);
179			}
180		}
181	}
182}
183
184/// Construct a Merkle Proof for leaves given by indices.
185///
186/// The function constructs a (partial) Merkle Tree first and stores all elements required
187/// to prove requested item (leaf) given the root hash.
188///
189/// Both the Proof and the Root Hash is returned.
190///
191/// # Panic
192///
193/// The function will panic if given `leaf_index` is greater than the number of leaves.
194pub fn merkle_proof<H, I, T>(leaves: I, leaf_index: u32) -> MerkleProof<H::Out, T>
195where
196	H: Hasher,
197	H::Out: Default + Copy + AsRef<[u8]>,
198	I: IntoIterator<Item = T>,
199	I::IntoIter: ExactSizeIterator,
200	T: AsRef<[u8]>,
201{
202	let mut leaf = None;
203	let iter = leaves.into_iter().enumerate().map(|(idx, l)| {
204		let hash = <H as Hasher>::hash(l.as_ref());
205		if idx as u32 == leaf_index {
206			leaf = Some(l);
207		}
208		hash
209	});
210
211	let number_of_leaves = iter.len() as u32;
212	let mut collect_proof = ProofCollection::new(leaf_index);
213
214	let root = merkelize::<H, _, _>(iter, &mut collect_proof);
215	let leaf = leaf.expect("Requested `leaf_index` is greater than number of leaves.");
216
217	#[cfg(feature = "debug")]
218	log::debug!(
219		"[merkle_proof] Proof: {:?}",
220		collect_proof
221			.proof
222			.iter()
223			.map(|s| array_bytes::bytes2hex("", s))
224			.collect::<Vec<_>>()
225	);
226
227	MerkleProof { root, proof: collect_proof.proof, number_of_leaves, leaf_index, leaf }
228}
229
230/// Construct a Merkle Proof for leaves given by indices.
231///
232/// This is a raw version of the [`merkle_proof`] function that expects the hashes of the leaves and
233/// not the leaves itself.
234///
235/// The function constructs a (partial) Merkle Tree first and stores all elements required
236/// to prove requested item (leaf) given the root hash.
237///
238/// Both the Proof and the Root Hash is returned.
239///
240/// # Panic
241///
242/// The function will panic if given `leaf_index` is greater than the number of leaves.
243pub fn merkle_proof_raw<H, I>(leaves: I, leaf_index: u32) -> MerkleProof<H::Out, H::Out>
244where
245	H: Hasher,
246	H::Out: Default + Copy + AsRef<[u8]>,
247	I: IntoIterator<Item = H::Out>,
248	I::IntoIter: ExactSizeIterator,
249{
250	let mut leaf = None;
251	let iter = leaves.into_iter().enumerate().map(|(idx, l)| {
252		let hash = l;
253		if idx as u32 == leaf_index {
254			leaf = Some(l);
255		}
256		hash
257	});
258
259	let number_of_leaves = iter.len() as u32;
260	let mut collect_proof = ProofCollection::new(leaf_index);
261
262	let root = merkelize::<H, _, _>(iter, &mut collect_proof);
263	let leaf = leaf.expect("Requested `leaf_index` is greater than number of leaves.");
264
265	#[cfg(feature = "debug")]
266	log::debug!(
267		"[merkle_proof] Proof: {:?}",
268		collect_proof
269			.proof
270			.iter()
271			.map(|s| array_bytes::bytes2hex("", s))
272			.collect::<Vec<_>>()
273	);
274
275	MerkleProof { root, proof: collect_proof.proof, number_of_leaves, leaf_index, leaf }
276}
277
278/// Leaf node for proof verification.
279///
280/// Can be either a value that needs to be hashed first,
281/// or the hash itself.
282#[derive(Debug, PartialEq, Eq)]
283pub enum Leaf<'a, H> {
284	/// Leaf content.
285	Value(&'a [u8]),
286	/// Hash of the leaf content.
287	Hash(H),
288}
289
290impl<'a, H, T: AsRef<[u8]>> From<&'a T> for Leaf<'a, H> {
291	fn from(v: &'a T) -> Self {
292		Leaf::Value(v.as_ref())
293	}
294}
295
296/// Verify Merkle Proof correctness versus given root hash.
297///
298/// The proof is NOT expected to contain leaf hash as the first
299/// element, but only all adjacent nodes required to eventually by process of
300/// concatenating and hashing end up with given root hash.
301///
302/// The proof must not contain the root hash.
303pub fn verify_proof<'a, H, P, L>(
304	root: &'a H::Out,
305	proof: P,
306	number_of_leaves: u32,
307	leaf_index: u32,
308	leaf: L,
309) -> bool
310where
311	H: Hasher,
312	H::Out: PartialEq + AsRef<[u8]>,
313	P: IntoIterator<Item = H::Out>,
314	L: Into<Leaf<'a, H::Out>>,
315{
316	if leaf_index >= number_of_leaves {
317		return false
318	}
319
320	let leaf_hash = match leaf.into() {
321		Leaf::Value(content) => <H as Hasher>::hash(content),
322		Leaf::Hash(hash) => hash,
323	};
324
325	let hash_len = <H as Hasher>::LENGTH;
326	let mut combined = vec![0_u8; hash_len * 2];
327	let mut position = leaf_index;
328	let mut width = number_of_leaves;
329	let computed = proof.into_iter().fold(leaf_hash, |a, b| {
330		if position % 2 == 1 || position + 1 == width {
331			combined[..hash_len].copy_from_slice(&b.as_ref());
332			combined[hash_len..].copy_from_slice(&a.as_ref());
333		} else {
334			combined[..hash_len].copy_from_slice(&a.as_ref());
335			combined[hash_len..].copy_from_slice(&b.as_ref());
336		}
337		let hash = <H as Hasher>::hash(&combined);
338		#[cfg(feature = "debug")]
339		log::debug!(
340			"[verify_proof]: (a, b) {:?}, {:?} => {:?} ({:?}) hash",
341			array_bytes::bytes2hex("", a),
342			array_bytes::bytes2hex("", b),
343			array_bytes::bytes2hex("", hash),
344			array_bytes::bytes2hex("", &combined)
345		);
346		position /= 2;
347		width = ((width - 1) / 2) + 1;
348		hash
349	});
350
351	root == &computed
352}
353
354/// Processes a single row (layer) of a tree by taking pairs of elements,
355/// concatenating them, hashing and placing into resulting vector.
356///
357/// In case only one element is provided it is returned via `Ok` result, in any other case (also an
358/// empty iterator) an `Err` with the inner nodes of upper layer is returned.
359fn merkelize_row<H, V, I>(
360	mut iter: I,
361	mut next: Vec<H::Out>,
362	visitor: &mut V,
363) -> Result<H::Out, Vec<H::Out>>
364where
365	H: Hasher,
366	H::Out: AsRef<[u8]>,
367	V: Visitor<H::Out>,
368	I: Iterator<Item = H::Out>,
369{
370	#[cfg(feature = "debug")]
371	log::debug!("[merkelize_row]");
372	next.clear();
373
374	let hash_len = <H as Hasher>::LENGTH;
375	let mut index = 0;
376	let mut combined = vec![0_u8; hash_len * 2];
377	loop {
378		let a = iter.next();
379		let b = iter.next();
380		visitor.visit(index, &a, &b);
381
382		#[cfg(feature = "debug")]
383		log::debug!(
384			"  {:?}\n  {:?}",
385			a.as_ref().map(|s| array_bytes::bytes2hex("", s)),
386			b.as_ref().map(|s| array_bytes::bytes2hex("", s))
387		);
388
389		index += 2;
390		match (a, b) {
391			(Some(a), Some(b)) => {
392				combined[..hash_len].copy_from_slice(a.as_ref());
393				combined[hash_len..].copy_from_slice(b.as_ref());
394
395				next.push(<H as Hasher>::hash(&combined));
396			},
397			// Odd number of items. Promote the item to the upper layer.
398			(Some(a), None) if !next.is_empty() => {
399				next.push(a);
400			},
401			// Last item = root.
402			(Some(a), None) => return Ok(a),
403			// Finish up, no more items.
404			_ => {
405				#[cfg(feature = "debug")]
406				log::debug!(
407					"[merkelize_row] Next: {:?}",
408					next.iter().map(|s| array_bytes::bytes2hex("", s)).collect::<Vec<_>>()
409				);
410				return Err(next)
411			},
412		}
413	}
414}
415
416#[cfg(test)]
417mod tests {
418	use super::*;
419	use sp_core::H256;
420	use sp_runtime::traits::Keccak256;
421
422	#[test]
423	fn should_generate_empty_root() {
424		// given
425		let data: Vec<[u8; 1]> = Default::default();
426
427		// when
428		let out = merkle_root::<Keccak256, _>(data);
429
430		// then
431		assert_eq!(
432			array_bytes::bytes2hex("", out),
433			"0000000000000000000000000000000000000000000000000000000000000000"
434		);
435	}
436
437	#[test]
438	fn should_generate_single_root() {
439		// given
440		let data = vec![array_bytes::hex2array_unchecked::<_, 20>(
441			"E04CC55ebEE1cBCE552f250e85c57B70B2E2625b",
442		)];
443
444		// when
445		let out = merkle_root::<Keccak256, _>(data);
446
447		// then
448		assert_eq!(
449			array_bytes::bytes2hex("", out),
450			"aeb47a269393297f4b0a3c9c9cfd00c7a4195255274cf39d83dabc2fcc9ff3d7"
451		);
452	}
453
454	#[test]
455	fn should_generate_root_pow_2() {
456		// given
457		let data = vec![
458			array_bytes::hex2array_unchecked::<_, 20>("E04CC55ebEE1cBCE552f250e85c57B70B2E2625b"),
459			array_bytes::hex2array_unchecked::<_, 20>("25451A4de12dcCc2D166922fA938E900fCc4ED24"),
460		];
461
462		// when
463		let out = merkle_root::<Keccak256, _>(data);
464
465		// then
466		assert_eq!(
467			array_bytes::bytes2hex("", out),
468			"697ea2a8fe5b03468548a7a413424a6292ab44a82a6f5cc594c3fa7dda7ce402"
469		);
470	}
471
472	#[test]
473	fn should_generate_root_complex() {
474		let test = |root, data| {
475			assert_eq!(array_bytes::bytes2hex("", &merkle_root::<Keccak256, _>(data)), root);
476		};
477
478		test(
479			"aff1208e69c9e8be9b584b07ebac4e48a1ee9d15ce3afe20b77a4d29e4175aa3",
480			vec!["a", "b", "c"],
481		);
482
483		test(
484			"b8912f7269068901f231a965adfefbc10f0eedcfa61852b103efd54dac7db3d7",
485			vec!["a", "b", "a"],
486		);
487
488		test(
489			"dc8e73fe6903148ff5079baecc043983625c23b39f31537e322cd0deee09fa9c",
490			vec!["a", "b", "a", "b"],
491		);
492
493		test(
494			"fb3b3be94be9e983ba5e094c9c51a7d96a4fa2e5d8e891df00ca89ba05bb1239",
495			vec!["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"],
496		);
497	}
498
499	#[test]
500	fn should_generate_and_verify_proof_simple() {
501		// given
502		let data = vec!["a", "b", "c"];
503
504		// when
505		let proof0 = merkle_proof::<Keccak256, _, _>(data.clone(), 0);
506		assert!(verify_proof::<Keccak256, _, _>(
507			&proof0.root,
508			proof0.proof.clone(),
509			data.len() as _,
510			proof0.leaf_index,
511			&proof0.leaf,
512		));
513
514		let proof1 = merkle_proof::<Keccak256, _, _>(data.clone(), 1);
515		assert!(verify_proof::<Keccak256, _, _>(
516			&proof1.root,
517			proof1.proof,
518			data.len() as _,
519			proof1.leaf_index,
520			&proof1.leaf,
521		));
522
523		let proof2 = merkle_proof::<Keccak256, _, _>(data.clone(), 2);
524		assert!(verify_proof::<Keccak256, _, _>(
525			&proof2.root,
526			proof2.proof,
527			data.len() as _,
528			proof2.leaf_index,
529			&proof2.leaf
530		));
531
532		// then
533		assert_eq!(
534			array_bytes::bytes2hex("", &proof0.root),
535			array_bytes::bytes2hex("", &proof1.root)
536		);
537		assert_eq!(
538			array_bytes::bytes2hex("", &proof2.root),
539			array_bytes::bytes2hex("", &proof1.root)
540		);
541
542		assert!(!verify_proof::<Keccak256, _, _>(
543			&array_bytes::hex2array_unchecked(
544				"fb3b3be94be9e983ba5e094c9c51a7d96a4fa2e5d8e891df00ca89ba05bb1239"
545			)
546			.into(),
547			proof0.proof,
548			data.len() as _,
549			proof0.leaf_index,
550			&proof0.leaf
551		));
552
553		assert!(!verify_proof::<Keccak256, _, _>(
554			&proof0.root.into(),
555			vec![],
556			data.len() as _,
557			proof0.leaf_index,
558			&proof0.leaf
559		));
560	}
561
562	#[test]
563	fn should_generate_and_verify_proof_complex() {
564		// given
565		let data = vec!["a", "b", "c", "d", "e", "f", "g", "h", "i", "j"];
566
567		for l in 0..data.len() as u32 {
568			// when
569			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
570			// then
571			assert!(verify_proof::<Keccak256, _, _>(
572				&proof.root,
573				proof.proof,
574				data.len() as _,
575				proof.leaf_index,
576				&proof.leaf
577			));
578		}
579	}
580
581	#[test]
582	fn should_generate_and_verify_proof_large() {
583		// given
584		let mut data = vec![];
585		for i in 1..16 {
586			for c in 'a'..'z' {
587				if c as usize % i != 0 {
588					data.push(c.to_string());
589				}
590			}
591
592			for l in 0..data.len() as u32 {
593				// when
594				let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
595				// then
596				assert!(verify_proof::<Keccak256, _, _>(
597					&proof.root,
598					proof.proof,
599					data.len() as _,
600					proof.leaf_index,
601					&proof.leaf
602				));
603			}
604		}
605	}
606
607	#[test]
608	fn should_generate_and_verify_proof_large_tree() {
609		// given
610		let mut data = vec![];
611		for i in 0..6000 {
612			data.push(format!("{}", i));
613		}
614
615		for l in (0..data.len() as u32).step_by(13) {
616			// when
617			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
618			// then
619			assert!(verify_proof::<Keccak256, _, _>(
620				&proof.root,
621				proof.proof,
622				data.len() as _,
623				proof.leaf_index,
624				&proof.leaf
625			));
626		}
627	}
628
629	#[test]
630	#[should_panic]
631	fn should_panic_on_invalid_leaf_index() {
632		merkle_proof::<Keccak256, _, _>(vec!["a"], 5);
633	}
634
635	#[test]
636	fn should_generate_and_verify_proof_on_test_data() {
637		let addresses = vec![
638			"0x9aF1Ca5941148eB6A3e9b9C741b69738292C533f",
639			"0xDD6ca953fddA25c496165D9040F7F77f75B75002",
640			"0x60e9C47B64Bc1C7C906E891255EaEC19123E7F42",
641			"0xfa4859480Aa6D899858DE54334d2911E01C070df",
642			"0x19B9b128470584F7209eEf65B69F3624549Abe6d",
643			"0xC436aC1f261802C4494504A11fc2926C726cB83b",
644			"0xc304C8C2c12522F78aD1E28dD86b9947D7744bd0",
645			"0xDa0C2Cba6e832E55dE89cF4033affc90CC147352",
646			"0xf850Fd22c96e3501Aad4CDCBf38E4AEC95622411",
647			"0x684918D4387CEb5E7eda969042f036E226E50642",
648			"0x963F0A1bFbb6813C0AC88FcDe6ceB96EA634A595",
649			"0x39B38ad74b8bCc5CE564f7a27Ac19037A95B6099",
650			"0xC2Dec7Fdd1fef3ee95aD88EC8F3Cd5bd4065f3C7",
651			"0x9E311f05c2b6A43C2CCF16fB2209491BaBc2ec01",
652			"0x927607C30eCE4Ef274e250d0bf414d4a210b16f0",
653			"0x98882bcf85E1E2DFF780D0eB360678C1cf443266",
654			"0xFBb50191cd0662049E7C4EE32830a4Cc9B353047",
655			"0x963854fc2C358c48C3F9F0A598B9572c581B8DEF",
656			"0xF9D7Bc222cF6e3e07bF66711e6f409E51aB75292",
657			"0xF2E3fd32D063F8bBAcB9e6Ea8101C2edd899AFe6",
658			"0x407a5b9047B76E8668570120A96d580589fd1325",
659			"0xEAD9726FAFB900A07dAd24a43AE941d2eFDD6E97",
660			"0x42f5C8D9384034A9030313B51125C32a526b6ee8",
661			"0x158fD2529Bc4116570Eb7C80CC76FEf33ad5eD95",
662			"0x0A436EE2E4dEF3383Cf4546d4278326Ccc82514E",
663			"0x34229A215db8FeaC93Caf8B5B255e3c6eA51d855",
664			"0xEb3B7CF8B1840242CB98A732BA464a17D00b5dDF",
665			"0x2079692bf9ab2d6dc7D79BBDdEE71611E9aA3B72",
666			"0x46e2A67e5d450e2Cf7317779f8274a2a630f3C9B",
667			"0xA7Ece4A5390DAB18D08201aE18800375caD78aab",
668			"0x15E1c0D24D62057Bf082Cb2253dA11Ef0d469570",
669			"0xADDEF4C9b5687Eb1F7E55F2251916200A3598878",
670			"0xe0B16Fb96F936035db2b5A68EB37D470fED2f013",
671			"0x0c9A84993feaa779ae21E39F9793d09e6b69B62D",
672			"0x3bc4D5148906F70F0A7D1e2756572655fd8b7B34",
673			"0xFf4675C26903D5319795cbd3a44b109E7DDD9fDe",
674			"0xCec4450569A8945C6D2Aba0045e4339030128a92",
675			"0x85f0584B10950E421A32F471635b424063FD8405",
676			"0xb38bEe7Bdc0bC43c096e206EFdFEad63869929E3",
677			"0xc9609466274Fef19D0e58E1Ee3b321D5C141067E",
678			"0xa08EA868cF75268E7401021E9f945BAe73872ecc",
679			"0x67C9Cb1A29E964Fe87Ff669735cf7eb87f6868fE",
680			"0x1B6BEF636aFcdd6085cD4455BbcC93796A12F6E2",
681			"0x46B37b243E09540b55cF91C333188e7D5FD786dD",
682			"0x8E719E272f62Fa97da93CF9C941F5e53AA09e44a",
683			"0xa511B7E7DB9cb24AD5c89fBb6032C7a9c2EfA0a5",
684			"0x4D11FDcAeD335d839132AD450B02af974A3A66f8",
685			"0xB8cf790a5090E709B4619E1F335317114294E17E",
686			"0x7f0f57eA064A83210Cafd3a536866ffD2C5eDCB3",
687			"0xC03C848A4521356EF800e399D889e9c2A25D1f9E",
688			"0xC6b03DF05cb686D933DD31fCa5A993bF823dc4FE",
689			"0x58611696b6a8102cf95A32c25612E4cEF32b910F",
690			"0x2ed4bC7197AEF13560F6771D930Bf907772DE3CE",
691			"0x3C5E58f334306be029B0e47e119b8977B2639eb4",
692			"0x288646a1a4FeeC560B349d210263c609aDF649a6",
693			"0xb4F4981E0d027Dc2B3c86afA0D0fC03d317e83C0",
694			"0xaAE4A87F8058feDA3971f9DEd639Ec9189aA2500",
695			"0x355069DA35E598913d8736E5B8340527099960b8",
696			"0x3cf5A0F274cd243C0A186d9fCBdADad089821B93",
697			"0xca55155dCc4591538A8A0ca322a56EB0E4aD03C4",
698			"0xE824D0268366ec5C4F23652b8eD70D552B1F2b8B",
699			"0x84C3e9B25AE8a9b39FF5E331F9A597F2DCf27Ca9",
700			"0xcA0018e278751De10d26539915d9c7E7503432FE",
701			"0xf13077dE6191D6c1509ac7E088b8BE7Fe656c28b",
702			"0x7a6bcA1ec9Db506e47ac6FD86D001c2aBc59C531",
703			"0xeA7f9A2A9dd6Ba9bc93ca615C3Ddf26973146911",
704			"0x8D0d8577e16F8731d4F8712BAbFa97aF4c453458",
705			"0xB7a7855629dF104246997e9ACa0E6510df75d0ea",
706			"0x5C1009BDC70b0C8Ab2e5a53931672ab448C17c89",
707			"0x40B47D1AfefEF5eF41e0789F0285DE7b1C31631C",
708			"0x5086933d549cEcEB20652CE00973703CF10Da373",
709			"0xeb364f6FE356882F92ae9314fa96116Cf65F47d8",
710			"0xdC4D31516A416cEf533C01a92D9a04bbdb85EE67",
711			"0x9b36E086E5A274332AFd3D8509e12ca5F6af918d",
712			"0xBC26394fF36e1673aE0608ce91A53B9768aD0D76",
713			"0x81B5AB400be9e563fA476c100BE898C09966426c",
714			"0x9d93C8ae5793054D28278A5DE6d4653EC79e90FE",
715			"0x3B8E75804F71e121008991E3177fc942b6c28F50",
716			"0xC6Eb5886eB43dD473f5BB4e21e56E08dA464D9B4",
717			"0xfdf1277b71A73c813cD0e1a94B800f4B1Db66DBE",
718			"0xc2ff2cCc98971556670e287Ff0CC39DA795231ad",
719			"0x76b7E1473f0D0A87E9B4a14E2B179266802740f5",
720			"0xA7Bc965660a6EF4687CCa4F69A97563163A3C2Ef",
721			"0xB9C2b47888B9F8f7D03dC1de83F3F55E738CebD3",
722			"0xEd400162E6Dd6bD2271728FFb04176bF770De94a",
723			"0xE3E8331156700339142189B6E555DCb2c0962750",
724			"0xbf62e342Bc7706a448EdD52AE871d9C4497A53b1",
725			"0xb9d7A1A111eed75714a0AcD2dd467E872eE6B03D",
726			"0x03942919DFD0383b8c574AB8A701d89fd4bfA69D",
727			"0x0Ef4C92355D3c8c7050DFeb319790EFCcBE6fe9e",
728			"0xA6895a3cf0C60212a73B3891948ACEcF1753f25E",
729			"0x0Ed509239DB59ef3503ded3d31013C983d52803A",
730			"0xc4CE8abD123BfAFc4deFf37c7D11DeCd5c350EE4",
731			"0x4A4Bf59f7038eDcd8597004f35d7Ee24a7Bdd2d3",
732			"0x5769E8e8A2656b5ed6b6e6fa2a2bFAeaf970BB87",
733			"0xf9E15cCE181332F4F57386687c1776b66C377060",
734			"0xc98f8d4843D56a46C21171900d3eE538Cc74dbb5",
735			"0x3605965B47544Ce4302b988788B8195601AE4dEd",
736			"0xe993BDfdcAac2e65018efeE0F69A12678031c71d",
737			"0x274fDf8801385D3FAc954BCc1446Af45f5a8304c",
738			"0xBFb3f476fcD6429F4a475bA23cEFdDdd85c6b964",
739			"0x806cD16588Fe812ae740e931f95A289aFb4a4B50",
740			"0xa89488CE3bD9C25C3aF797D1bbE6CA689De79d81",
741			"0xd412f1AfAcf0Ebf3Cd324593A231Fc74CC488B12",
742			"0xd1f715b2D7951d54bc31210BbD41852D9BF98Ed1",
743			"0xf65aD707c344171F467b2ADba3d14f312219cE23",
744			"0x2971a4b242e9566dEF7bcdB7347f5E484E11919B",
745			"0x12b113D6827E07E7D426649fBd605f427da52314",
746			"0x1c6CA45171CDb9856A6C9Dba9c5F1216913C1e97",
747			"0x11cC6ee1d74963Db23294FCE1E3e0A0555779CeA",
748			"0x8Aa1C721255CDC8F895E4E4c782D86726b068667",
749			"0xA2cDC1f37510814485129aC6310b22dF04e9Bbf0",
750			"0xCf531b71d388EB3f5889F1f78E0d77f6fb109767",
751			"0xBe703e3545B2510979A0cb0C440C0Fba55c6dCB5",
752			"0x30a35886F989db39c797D8C93880180Fdd71b0c8",
753			"0x1071370D981F60c47A9Cd27ac0A61873a372cBB2",
754			"0x3515d74A11e0Cb65F0F46cB70ecf91dD1712daaa",
755			"0x50500a3c2b7b1229c6884505D00ac6Be29Aecd0C",
756			"0x9A223c2a11D4FD3585103B21B161a2B771aDA3d1",
757			"0xd7218df03AD0907e6c08E707B15d9BD14285e657",
758			"0x76CfD72eF5f93D1a44aD1F80856797fBE060c70a",
759			"0x44d093cB745944991EFF5cBa151AA6602d6f5420",
760			"0x626516DfF43bf09A71eb6fd1510E124F96ED0Cde",
761			"0x6530824632dfe099304E2DC5701cA99E6d031E08",
762			"0x57e6c423d6a7607160d6379A0c335025A14DaFC0",
763			"0x3966D4AD461Ef150E0B10163C81E79b9029E69c3",
764			"0xF608aCfd0C286E23721a3c347b2b65039f6690F1",
765			"0xbfB8FAac31A25646681936977837f7740fCd0072",
766			"0xd80aa634a623a7ED1F069a1a3A28a173061705c7",
767			"0x9122a77B36363e24e12E1E2D73F87b32926D3dF5",
768			"0x62562f0d1cD31315bCCf176049B6279B2bfc39C2",
769			"0x48aBF7A2a7119e5675059E27a7082ba7F38498b2",
770			"0xb4596983AB9A9166b29517acD634415807569e5F",
771			"0x52519D16E20BC8f5E96Da6d736963e85b2adA118",
772			"0x7663893C3dC0850EfC5391f5E5887eD723e51B83",
773			"0x5FF323a29bCC3B5b4B107e177EccEF4272959e61",
774			"0xee6e499AdDf4364D75c05D50d9344e9daA5A9AdF",
775			"0x1631b0BD31fF904aD67dD58994C6C2051CDe4E75",
776			"0xbc208e9723D44B9811C428f6A55722a26204eEF2",
777			"0xe76103a222Ee2C7Cf05B580858CEe625C4dc00E1",
778			"0xC71Bb2DBC51760f4fc2D46D84464410760971B8a",
779			"0xB4C18811e6BFe564D69E12c224FFc57351f7a7ff",
780			"0xD11DB0F5b41061A887cB7eE9c8711438844C298A",
781			"0xB931269934A3D4432c084bAAc3d0de8143199F4f",
782			"0x070037cc85C761946ec43ea2b8A2d5729908A2a1",
783			"0x2E34aa8C95Ffdbb37f14dCfBcA69291c55Ba48DE",
784			"0x052D93e8d9220787c31d6D83f87eC7dB088E998f",
785			"0x498dAC6C69b8b9ad645217050054840f1D91D029",
786			"0xE4F7D60f9d84301e1fFFd01385a585F3A11F8E89",
787			"0xEa637992f30eA06460732EDCBaCDa89355c2a107",
788			"0x4960d8Da07c27CB6Be48a79B96dD70657c57a6bF",
789			"0x7e471A003C8C9fdc8789Ded9C3dbe371d8aa0329",
790			"0xd24265Cc10eecb9e8d355CCc0dE4b11C556E74D7",
791			"0xDE59C8f7557Af779674f41CA2cA855d571018690",
792			"0x2fA8A6b3b6226d8efC9d8f6EBDc73Ca33DDcA4d8",
793			"0xe44102664c6c2024673Ff07DFe66E187Db77c65f",
794			"0x94E3f4f90a5f7CBF2cc2623e66B8583248F01022",
795			"0x0383EdBbc21D73DEd039E9C1Ff6bf56017b4CC40",
796			"0x64C3E49898B88d1E0f0d02DA23E0c00A2Cd0cA99",
797			"0xF4ccfB67b938d82B70bAb20975acFAe402E812E1",
798			"0x4f9ee5829e9852E32E7BC154D02c91D8E203e074",
799			"0xb006312eF9713463bB33D22De60444Ba95609f6B",
800			"0x7Cbe76ef69B52110DDb2e3b441C04dDb11D63248",
801			"0x70ADEEa65488F439392B869b1Df7241EF317e221",
802			"0x64C0bf8AA36Ba590477585Bc0D2BDa7970769463",
803			"0xA4cDc98593CE52d01Fe5Ca47CB3dA5320e0D7592",
804			"0xc26B34D375533fFc4c5276282Fa5D660F3d8cbcB",
805		];
806		let root: H256 = array_bytes::hex2array_unchecked(
807			"72b0acd7c302a84f1f6b6cefe0ba7194b7398afb440e1b44a9dbbe270394ca53",
808		)
809		.into();
810
811		let data = addresses
812			.into_iter()
813			.map(|address| array_bytes::hex2bytes_unchecked(&address))
814			.collect::<Vec<_>>();
815
816		for l in 0..data.len() as u32 {
817			// when
818			let proof = merkle_proof::<Keccak256, _, _>(data.clone(), l);
819			assert_eq!(array_bytes::bytes2hex("", &proof.root), array_bytes::bytes2hex("", &root));
820			assert_eq!(proof.leaf_index, l);
821			assert_eq!(&proof.leaf, &data[l as usize]);
822
823			// then
824			assert!(verify_proof::<Keccak256, _, _>(
825				&proof.root,
826				proof.proof,
827				data.len() as _,
828				proof.leaf_index,
829				&proof.leaf
830			));
831		}
832
833		let proof = merkle_proof::<Keccak256, _, _>(data.clone(), data.len() as u32 - 1);
834
835		assert_eq!(
836			proof,
837			MerkleProof {
838				root,
839				proof: vec![
840					array_bytes::hex2array_unchecked(
841						"340bcb1d49b2d82802ddbcf5b85043edb3427b65d09d7f758fbc76932ad2da2f"
842					)
843					.into(),
844					array_bytes::hex2array_unchecked(
845						"ba0580e5bd530bc93d61276df7969fb5b4ae8f1864b4a28c280249575198ff1f"
846					)
847					.into(),
848					array_bytes::hex2array_unchecked(
849						"d02609d2bbdb28aa25f58b85afec937d5a4c85d37925bce6d0cf802f9d76ba79"
850					)
851					.into(),
852					array_bytes::hex2array_unchecked(
853						"ae3f8991955ed884613b0a5f40295902eea0e0abe5858fc520b72959bc016d4e"
854					)
855					.into(),
856				],
857				number_of_leaves: data.len() as _,
858				leaf_index: data.len() as u32 - 1,
859				leaf: array_bytes::hex2array_unchecked::<_, 20>(
860					"c26B34D375533fFc4c5276282Fa5D660F3d8cbcB"
861				)
862				.to_vec(),
863			}
864		);
865	}
866}
binary_merkle_tree/lib.rs

binary_merkle_tree/
lib.rs
