ethereum_sdk/
merkle.rs

1use sha2::{Digest, Sha256};
2use sha3::Keccak256;
3
4pub type MerkleTreeData = Vec<u8>;
5pub type MerkleTreeHash = [u8; 32];
6pub type MerkleTreeProof = Vec<MerkleTreeHash>;
7
8#[derive(Clone, PartialEq, Eq, PartialOrd, Ord, Debug)]
9pub struct MerkleTreeRoot {
10    pub hash: MerkleTreeHash,
11}
12
13pub struct MerkleTree {
14    pub root: MerkleTreeRoot,
15    pub proofs: Vec<MerkleTreeProof>,
16}
17
18impl MerkleTreeRoot {
19    pub fn new(hash: MerkleTreeHash) -> Self {
20        MerkleTreeRoot { hash }
21    }
22
23    pub fn verify(&self, data: &MerkleTreeData, proof: &MerkleTreeProof) -> bool {
24        let mut hash = keccak256_array(data);
25        for second_hash in proof {
26            let s = serde_json::to_vec(&sort_hash_pair(&hash, second_hash)).unwrap();
27            hash = keccak256_array(&s);
28        }
29        self.hash == hash
30    }
31}
32
33pub fn keccak256_array(data: &[u8]) -> MerkleTreeHash {
34    let mut hasher = Keccak256::new();
35    hasher.update(data);
36    let result = hasher.finalize();
37    let mut output = [0u8; 32];
38    output.copy_from_slice(&result);
39    output
40}
41
42pub fn sort_hash_pair(
43    first: &MerkleTreeHash,
44    second: &MerkleTreeHash,
45) -> (MerkleTreeHash, MerkleTreeHash) {
46    if first < second {
47        (first.clone(), second.clone())
48    } else {
49        (second.clone(), first.clone())
50    }
51}
52
53impl MerkleTree {
54    pub fn build(items: &Vec<MerkleTreeData>) -> Self {
55        let items_len = items.len();
56
57        let mut items = items.clone();
58
59        let mut st_sum = 0_usize;
60        let mut st = 1_usize;
61
62        while st < items.len() {
63            st_sum += st;
64
65            st <<= 1;
66        }
67
68        while items.len() < st_sum + st {
69            items.push(MerkleTreeData::new());
70        }
71
72        let mut nodes = vec![[0_u8; 32]; st_sum + st];
73
74        for i in st_sum..st_sum + st {
75            nodes[i] = keccak256_array(&items[i - st_sum]);
76        }
77
78        let mut i = st_sum.clone();
79
80        while i > 0 {
81            i -= 1;
82
83            let s = serde_json::to_vec(&sort_hash_pair(&nodes[(i << 1) + 1], &nodes[(i + 1) << 1]))
84                .unwrap();
85
86            nodes[i] = keccak256_array(&s);
87        }
88
89        let get_proof = |index: usize| -> MerkleTreeProof {
90            let mut result = MerkleTreeProof::new();
91
92            let mut v = index + st_sum;
93
94            while v > 0 {
95                let w = if v % 2 == 0 { v - 1 } else { v + 1 };
96
97                result.push(nodes[w]);
98
99                v = (v - 1) >> 1;
100            }
101
102            result
103        };
104
105        let mut proofs: Vec<MerkleTreeProof> = Vec::new();
106
107        for i in 0..items_len {
108            proofs.push(get_proof(i))
109        }
110
111        MerkleTree {
112            root: MerkleTreeRoot::new(nodes[0]),
113            proofs,
114        }
115    }
116}
117
118pub fn string_to_crypto_hash(input: &str) -> MerkleTreeHash {
119    let mut hasher = Sha256::new();
120    hasher.update(input);
121    let result = hasher.finalize();
122    let mut crypto_hash: MerkleTreeHash = [0u8; 32];
123    crypto_hash.copy_from_slice(&result);
124
125    crypto_hash
126}
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    pub fn correct_proofs() {
134        let mut items = Vec::<MerkleTreeData>::new();
135
136        for i in 0..8 {
137            items.push(vec![i]);
138        }
139
140        let merkle_tree = MerkleTree::build(&items);
141
142        assert_eq!(merkle_tree.proofs.len(), 8);
143
144        for proof in merkle_tree.proofs {
145            assert_eq!(proof.len(), 3);
146        }
147    }
148
149    #[test]
150    pub fn verify_correct_data() {
151        let mut items = Vec::<MerkleTreeData>::new();
152
153        for i in 0..4 {
154            items.push(vec![i]);
155        }
156
157        let merkle_tree = MerkleTree::build(&items);
158        println!("root - {:?}", merkle_tree.root);
159        println!("proof - {:?} ---  {:?}", merkle_tree.proofs[0], items[0]);
160
161        for i in 0..items.len() {
162            assert!(merkle_tree.root.verify(&items[i], &merkle_tree.proofs[i]));
163        }
164    }
165
166    #[test]
167    pub fn verify_incorrect_data() {
168        let mut items = Vec::<MerkleTreeData>::new();
169
170        for i in 0..4 {
171            items.push(vec![i]);
172        }
173
174        let merkle_tree = MerkleTree::build(&items);
175
176        assert!(!merkle_tree.root.verify(&items[0], &merkle_tree.proofs[2]));
177    }
178
179    #[test]
180    fn test_make_crypt_hash() {
181        let s = "abcd".to_string();
182        for x in 0..10 {
183            let stx = format!("{}:{}", x, &s);
184            let hash = string_to_crypto_hash(&stx);
185            println!("hash - 0x{}", hex::encode(hash));
186        }
187    }
188}
189
190#[test]
191fn testx() {
192    let s = "abcd";
193    let hash = keccak256_array(s.as_bytes());
194    println!("h--{:?} ", hash);
195}
ethereum_sdk/merkle.rs

ethereum_sdk/
merkle.rs
