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

binary_merkle_tree/
lib.rs
