snowbridge_beacon_primitives/
merkle_proof.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: 2023 Snowfork <hello@snowfork.com>
3use sp_core::H256;
4use sp_io::hashing::sha2_256;
5
6/// Specified by <https://github.com/ethereum/consensus-specs/blob/fe9c1a8cbf0c2da8a4f349efdcd77dd7ac8445c4/specs/phase0/beacon-chain.md?plain=1#L742>
7/// with improvements from <https://github.com/ethereum/consensus-specs/blob/dev/ssz/merkle-proofs.md>
8pub fn verify_merkle_branch(
9	leaf: H256,
10	branch: &[H256],
11	index: usize,
12	depth: usize,
13	root: H256,
14) -> bool {
15	// verify the proof length
16	if branch.len() != depth {
17		return false
18	}
19	// verify the computed merkle root
20	root == compute_merkle_root(leaf, branch, index)
21}
22
23fn compute_merkle_root(leaf: H256, proof: &[H256], index: usize) -> H256 {
24	let mut value: [u8; 32] = leaf.into();
25	for (i, node) in proof.iter().enumerate() {
26		let mut data = [0u8; 64];
27		if generalized_index_bit(index, i) {
28			// right node
29			data[0..32].copy_from_slice(node.as_bytes());
30			data[32..64].copy_from_slice(&value);
31			value = sha2_256(&data);
32		} else {
33			// left node
34			data[0..32].copy_from_slice(&value);
35			data[32..64].copy_from_slice(node.as_bytes());
36			value = sha2_256(&data);
37		}
38	}
39	value.into()
40}
41
42/// Spec: <https://github.com/ethereum/consensus-specs/blob/fe9c1a8cbf0c2da8a4f349efdcd77dd7ac8445c4/ssz/merkle-proofs.md#get_generalized_index_bit>
43fn generalized_index_bit(index: usize, position: usize) -> bool {
44	index & (1 << position) > 0
45}
46
47/// Spec: <https://github.com/ethereum/consensus-specs/blob/fe9c1a8cbf0c2da8a4f349efdcd77dd7ac8445c4/specs/altair/light-client/sync-protocol.md#get_subtree_index>
48pub const fn subtree_index(generalized_index: usize) -> usize {
49	generalized_index % (1 << generalized_index_length(generalized_index))
50}
51
52/// Spec: <https://github.com/ethereum/consensus-specs/blob/fe9c1a8cbf0c2da8a4f349efdcd77dd7ac8445c4/ssz/merkle-proofs.md#get_generalized_index_length>
53pub const fn generalized_index_length(generalized_index: usize) -> usize {
54	match generalized_index.checked_ilog2() {
55		Some(v) => v as usize,
56		None => panic!("checked statically; qed"),
57	}
58}
snowbridge_beacon_primitives/merkle_proof.rs

snowbridge_beacon_primitives/
merkle_proof.rs
