sp_domains/
merkle_tree.rs1#[cfg(not(feature = "std"))]
2extern crate alloc;
3
4use crate::OperatorPublicKey;
5#[cfg(not(feature = "std"))]
6use alloc::vec::Vec;
7use blake2::digest::FixedOutput;
8use blake2::{Blake2b, Digest};
9use parity_scale_codec::{Decode, Encode};
10use rs_merkle::Hasher;
11use scale_info::TypeInfo;
12use sp_runtime::traits::{BlakeTwo256, Hash};
13
14pub type MerkleTree = rs_merkle::MerkleTree<Blake2b256Algorithm>;
16
17pub type MerkleProof = rs_merkle::MerkleProof<Blake2b256Algorithm>;
19
20#[derive(Debug, Decode, Encode, TypeInfo, PartialEq, Eq, Clone, Default)]
22pub struct Witness {
23 pub leaf_index: u32,
25 pub proof: Vec<u8>,
27 pub number_of_leaves: u32,
29}
30
31#[derive(Clone)]
32pub struct Blake2b256Algorithm;
33
34impl Default for Blake2b256Algorithm {
35 #[inline]
36 fn default() -> Self {
37 Self
38 }
39}
40
41impl Hasher for Blake2b256Algorithm {
42 type Hash = [u8; 32];
43
44 fn hash(data: &[u8]) -> Self::Hash {
45 let mut hasher = Blake2b::new();
46 hasher.update(data);
47 hasher.finalize_fixed().into()
48 }
49}
50
51pub fn authorities_merkle_tree<StakeWeight: Encode>(
53 authorities: &[(OperatorPublicKey, StakeWeight)],
54) -> MerkleTree {
55 let leaves = authorities
56 .iter()
57 .map(|x| BlakeTwo256::hash_of(&x.encode()).to_fixed_bytes())
58 .collect::<Vec<_>>();
59 MerkleTree::from_leaves(&leaves)
60}
61
62#[cfg(test)]
63mod tests {
64 use super::MerkleTree;
65
66 #[test]
67 fn test_merkle_tree() {
68 let leaves = [[1u8; 32], [2u8; 32], [3u8; 32], [4u8; 32], [5u8; 32]];
69
70 let merkle_tree = MerkleTree::from_leaves(&leaves);
71
72 let indices_to_prove = (0..leaves.len()).collect::<Vec<_>>();
73 let leaves_to_prove = leaves
74 .get(0..leaves.len())
75 .expect("can't get leaves to prove");
76
77 let proof = merkle_tree.proof(&indices_to_prove);
78 let root = merkle_tree.root().expect("couldn't get the merkle root");
79
80 assert!(proof.verify(root, &indices_to_prove, leaves_to_prove, leaves.len()));
81 }
82}