merkletree-rs/src/lib.rs
src/lib.rsRaw
1use std::collections::HashMap;
2
3#[macro_use]
4extern crate arrayref;
5
6extern crate tiny_keccak;
7
8extern crate rustc_hex;
9
10extern crate hex;
11
12use rustc_hex::ToHex;
13
14mod utils;
15mod node;
16
17const TYPENODEEMPTY: u8 = 0;
18const TYPENODENORMAL: u8 = 1;
19const TYPENODEFINAL: u8 = 2;
20const TYPENODEVALUE: u8 = 3;
21const EMPTYNODEVALUE: [u8;32] = [0;32];
22
23pub struct TestValue {
24 bytes: Vec<u8>,
25 index_length: u32,
26}
27pub trait Value {
28 fn bytes(&self) -> &Vec<u8>;
29 fn index_length(&self) -> u32;
30 fn hi(&self) -> [u8;32];
31 fn ht(&self) -> [u8;32];
32}
33impl Value for TestValue {
34 fn bytes(&self) -> &Vec<u8> {
35 &self.bytes
36 }
37 fn index_length(&self) -> u32 {
38 self.index_length
39 }
40 fn hi(&self) -> [u8;32] {
41 utils::hash_vec(self.bytes().to_vec().split_at(self.index_length() as usize).0.to_vec())
42 }
43 fn ht(&self) -> [u8;32] {
44 utils::hash_vec(self.bytes().to_vec())
45 }
46}
47
48#[allow(dead_code)]
49pub struct Db {
50 storage: HashMap<[u8;32], Vec<u8>>,
51}
52impl Db {
53 pub fn insert(&mut self, k: [u8; 32], t: u8, il: u32, b: Vec<u8>) {
54 let mut v: Vec<u8>;
55 v = [t].to_vec();
56 let il_bytes = il.to_le_bytes();
57 v.extend(il_bytes.to_vec()); // il_bytes are [u8;4] (4 bytes)
58 v.extend(&b);
59 self.storage.insert(k, v);
60 }
61 pub fn get(&self, k: &[u8;32]) -> (u8, u32, Vec<u8>) {
62 if k.to_vec() == EMPTYNODEVALUE.to_vec() {
63 return (0, 0, EMPTYNODEVALUE.to_vec());
64 }
65 match self.storage.get(k) {
66 Some(x) => {
67 let t = x[0];
68 let il_bytes: [u8; 4] = [x[1], x[2], x[3], x[4]];
69 let il = u32::from_le_bytes(il_bytes);
70 let b = &x[5..];
71 (t, il, b.to_vec())
72 },
73 None => (TYPENODEEMPTY, 0, EMPTYNODEVALUE.to_vec()),
74 }
75 }
76}
77
78pub fn new_db()-> Db {
79 Db {
80 storage: HashMap::new(),
81 }
82}
83
84pub struct MerkleTree {
85 #[allow(dead_code)]
86 root: [u8; 32],
87 #[allow(dead_code)]
88 num_levels: u32,
89 #[allow(dead_code)]
90 sto: Db,
91}
92
93
94pub fn new(num_levels: u32) -> MerkleTree {
95 MerkleTree {
96 root: EMPTYNODEVALUE,
97 num_levels,
98 sto: new_db(),
99 }
100}
101
102impl MerkleTree {
103 pub fn add(&mut self, v: &TestValue) {
104 #![allow(unused_variables)]
105 #[allow(dead_code)]
106
107 let leaf_node_string = String::from_utf8_lossy(&v.bytes());
108 // add the leaf that we are adding
109 self.sto.insert(v.ht(), TYPENODEVALUE, v.index_length(), v.bytes().to_vec());
110
111 let index = v.index_length() as usize;
112 let hi = v.hi();
113 let ht = v.ht();
114 let path = utils::get_path(self.num_levels, hi);
115 let mut siblings: Vec<[u8;32]> = Vec::new();
116
117
118 let mut node_hash = self.root;
119
120 for i in (0..=self.num_levels-2).rev() {
121 // get node
122 let (t, il, node_bytes) = self.sto.get(&node_hash);
123 if t == TYPENODEFINAL {
124 let hi_child = utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
125 let path_child = utils::get_path(self.num_levels, hi_child);
126 let pos_diff = utils::compare_paths(&path_child, &path);
127 if pos_diff == 999 { // TODO use a match here, and instead of 999 return something better
128 println!("node already exists");
129 println!("compare paths err");
130 return;
131 }
132 let final_node_1_hash = utils::calc_hash_from_leaf_and_level(pos_diff, &path_child, utils::hash_vec(node_bytes.to_vec()));
133 self.sto.insert(final_node_1_hash, TYPENODEFINAL, il, node_bytes.to_vec());
134 let final_node_2_hash = utils::calc_hash_from_leaf_and_level(pos_diff, &path, v.ht());
135 self.sto.insert(final_node_2_hash, TYPENODEFINAL, v.index_length(), v.bytes().to_vec());
136
137 // parent node
138 let parent_node: node::TreeNode;
139 if path[pos_diff as usize] {
140 parent_node = node::TreeNode {
141 child_l: final_node_1_hash,
142 child_r: final_node_2_hash,
143 }} else {
144 parent_node = node::TreeNode {
145 child_l: final_node_2_hash,
146 child_r: final_node_1_hash,
147 }}
148 let empties = utils::get_empties_between_i_and_pos(i, pos_diff+1);
149 for empty in &empties {
150 siblings.push(*empty);
151 }
152
153 let path_from_pos_diff = utils::cut_path(&path, (pos_diff + 1) as usize);
154
155 self.root = self.replace_leaf(path_from_pos_diff, &siblings, parent_node.ht(), TYPENODENORMAL, 0, parent_node.bytes().to_vec());
156 return;
157 }
158
159 let node = node::parse_node_bytes(node_bytes);
160
161 let sibling: [u8;32];
162 if !path[i as usize] {
163 node_hash = node.child_l;
164 sibling = node.child_r;
165 } else {
166 sibling = node.child_l;
167 node_hash = node.child_r;
168 }
169 siblings.push(*array_ref!(sibling, 0, 32));
170 if node_hash == EMPTYNODEVALUE {
171 if i==self.num_levels-2 && siblings[siblings.len()-1]==EMPTYNODEVALUE {
172 let final_node_hash = utils::calc_hash_from_leaf_and_level(i+1, &path, v.ht());
173 self.sto.insert(final_node_hash, TYPENODEFINAL, v.index_length(), v.bytes().to_vec());
174 self.root = final_node_hash;
175 return;
176 }
177 let final_node_hash = utils::calc_hash_from_leaf_and_level(i, &path, v.ht());
178 let path_from_i = utils::cut_path(&path, i as usize);
179 self.root = self.replace_leaf(path_from_i, &siblings, final_node_hash, TYPENODEFINAL, v.index_length(), v.bytes().to_vec());
180 return;
181 }
182 }
183 self.root = self.replace_leaf(path, &siblings, v.ht(), TYPENODEVALUE, v.index_length(), v.bytes().to_vec());
184 }
185
186 #[allow(dead_code)]
187 pub fn replace_leaf(&mut self, path: Vec<bool>, siblings: &Vec<[u8;32]>, leaf_hash: [u8;32], node_type: u8, index_length: u32, leaf_value: Vec<u8>) -> [u8;32] {
188 self.sto.insert(leaf_hash, node_type, index_length, leaf_value);
189 let mut curr_node = leaf_hash;
190
191 for i in 0..siblings.len() {
192 if !path[i as usize] {
193 let node = node::TreeNode {
194 child_l: curr_node,
195 child_r: siblings[siblings.len()-1-i],
196 };
197 self.sto.insert(node.ht(), TYPENODENORMAL, 0, node.bytes());
198 curr_node = node.ht();
199 } else {
200 let node = node::TreeNode {
201 child_l: siblings[siblings.len()-1-i],
202 child_r: curr_node,
203 };
204 self.sto.insert(node.ht(), TYPENODENORMAL, 0, node.bytes());
205 curr_node = node.ht();
206 }
207 }
208 curr_node
209 }
210
211 #[allow(dead_code)]
212 pub fn get_value_in_pos(&self, hi: [u8;32]) -> Vec<u8> {
213 let path = utils::get_path(self.num_levels, hi);
214 let mut node_hash = self.root;
215 for i in (0..=self.num_levels-2).rev() {
216 let (t, il, node_bytes) = self.sto.get(&node_hash);
217 if t == TYPENODEFINAL {
218 let hi_node = utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
219 let path_node = utils::get_path(self.num_levels, hi_node);
220 let pos_diff = utils::compare_paths(&path_node, &path);
221 // if pos_diff > self.num_levels {
222 if pos_diff != 999 {
223 return EMPTYNODEVALUE.to_vec();
224 }
225 return node_bytes;
226 }
227 let node = node::parse_node_bytes(node_bytes);
228 if !path[i as usize] {
229 node_hash = node.child_l;
230 } else {
231 node_hash = node.child_r;
232 }
233 }
234 let (_t, _il, node_bytes) = self.sto.get(&node_hash);
235 node_bytes
236 }
237
238 #[allow(dead_code)]
239 pub fn generate_proof(&self, hi: [u8;32]) -> Vec<u8> {
240 let mut mp: Vec<u8> = Vec::new();
241
242 let mut empties: [u8;32] = [0;32];
243 let path = utils::get_path(self.num_levels, hi);
244
245 let mut siblings: Vec<[u8;32]> = Vec::new();
246 let mut node_hash = self.root;
247
248 for i in 0..self.num_levels {
249 let (t, il, node_bytes) = self.sto.get(&node_hash);
250 if t == TYPENODEFINAL {
251 let real_value_in_pos = self.get_value_in_pos(hi);
252 if real_value_in_pos == EMPTYNODEVALUE {
253 let leaf_hi = utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
254 let path_child = utils::get_path(self.num_levels, leaf_hi);
255 let pos_diff = utils::compare_paths(&path_child, &path);
256 if pos_diff == self.num_levels { // TODO use a match here, and instead of 999 return something better
257 return mp;
258 }
259 if pos_diff != self.num_levels-1-i {
260 let sibling = utils::calc_hash_from_leaf_and_level(pos_diff, &path_child, utils::hash_vec(node_bytes.to_vec()));
261 let mut new_siblings: Vec<[u8;32]> = Vec::new();
262 new_siblings.push(sibling);
263 new_siblings.extend(siblings);
264 siblings = new_siblings;
265 // set empties bit
266 let bit_pos = self.num_levels-2-pos_diff;
267 empties[(empties.len() as isize + (bit_pos as isize/8-1) as isize) as usize] |= 1 << (bit_pos%8);
268 }
269 }
270 break
271 }
272 let node = node::parse_node_bytes(node_bytes);
273 let sibling: [u8;32];
274 if !path[self.num_levels as usize -i as usize -2] {
275 node_hash = node.child_l;
276 sibling = node.child_r;
277 } else {
278 sibling = node.child_l;
279 node_hash = node.child_r;
280 }
281 if sibling != EMPTYNODEVALUE {
282 // set empties bit
283 empties[(empties.len() as isize + (i as isize/8-1) as isize) as usize] |= 1 << (i%8);
284 let mut new_siblings: Vec<[u8;32]> = Vec::new();
285 new_siblings.push(sibling);
286 new_siblings.extend(siblings);
287 siblings = new_siblings;
288 }
289 }
290 mp.append(&mut empties[..].to_vec());
291 for s in siblings {
292 mp.append(&mut s.to_vec());
293 }
294 mp
295 }
296 #[allow(dead_code)]
297 pub fn print_level(&self, parent: [u8;32], mut lvl: u32, max_level: u32) {
298 let mut line: String = "".to_string();
299 for _ in 0..lvl {
300 line += &format!(" ");
301 }
302 line += &format!("lvl {}", lvl);
303 line += &format!(" - '{}' = ", parent.to_hex());
304 let (t, _, node_bytes) = self.sto.get(&parent);
305 let mut node = node::TreeNode {
306 child_l: EMPTYNODEVALUE,
307 child_r: EMPTYNODEVALUE,
308 };
309 if t==TYPENODENORMAL {
310 node = node::parse_node_bytes(node_bytes);
311 line += &format!("'{}' - '{}'", node.child_l.to_hex(), node.child_r.to_hex());
312 } else if t == TYPENODEVALUE {
313 //
314 } else if t == TYPENODEFINAL {
315 let hash_node_bytes = utils::hash_vec(node_bytes);
316 line += &format!("[final] final tree node: {} \n", hash_node_bytes.to_hex());
317 let (_, _, leaf_node_bytes) = self.sto.get(&hash_node_bytes);
318 for _ in 0..lvl {
319 line += " ";
320 }
321 let leaf_node_string = String::from_utf8_lossy(&leaf_node_bytes);
322 line += &format!("leaf value: {}", leaf_node_string);
323 } else {
324 line += "[EMPTY Branch]"
325 }
326 println!("{}", line);
327 lvl += 1;
328 if node.child_r.len()>0 && lvl<max_level && t != TYPENODEEMPTY && t != TYPENODEFINAL {
329 self.print_level(node.child_l, lvl, max_level);
330 self.print_level(node.child_r, lvl, max_level);
331 }
332 }
333 pub fn print_full_tree(&self) {
334 self.print_level(self.root, 0, self.num_levels - 1);
335 println!("root {:?}", self.root.to_hex());
336 }
337 pub fn print_levels_tree(&self, max_level: u32) {
338 self.print_level(self.root, 0, self.num_levels - 1 - max_level);
339 println!("root {:?}", self.root.to_hex());
340 }
341 }
342#[allow(dead_code)]
343 pub fn verify_proof(root: [u8;32], mp: Vec<u8>, hi: [u8;32], ht: [u8;32], num_levels: u32) -> bool {
344 let empties: Vec<u8>;
345 empties = mp.split_at(32).0.to_vec();
346
347 let mut siblings: Vec<[u8;32]> = Vec::new();
348 for i in (empties.len()..mp.len()).step_by(EMPTYNODEVALUE.len()) {
349 let mut sibling: [u8;32] = [0;32];
350 sibling.copy_from_slice(&mp[i..i+EMPTYNODEVALUE.len()]);
351 siblings.push(sibling);
352 }
353
354 let path = utils::get_path(num_levels, hi);
355 let mut node_hash = ht;
356 let mut sibling_used_pos = 0;
357
358 for i in (0..=num_levels-2).rev() {
359 let sibling: [u8;32];
360 if (empties[empties.len()-i as usize/8-1] & (1 << (i%8))) > 0 {
361 sibling = siblings[sibling_used_pos];
362 sibling_used_pos += 1;
363 } else {
364 sibling = EMPTYNODEVALUE;
365 }
366
367 let n: node::TreeNode;
368 if path[num_levels as usize - i as usize-2] {
369 n = node::TreeNode {
370 child_l: sibling,
371 child_r: node_hash,
372 }} else {
373 n = node::TreeNode {
374 child_l: node_hash,
375 child_r: sibling,
376 }}
377 if node_hash == EMPTYNODEVALUE && sibling == EMPTYNODEVALUE {
378 node_hash = EMPTYNODEVALUE;
379 } else {
380 node_hash = n.ht();
381 }
382 }
383 if node_hash==root {
384 return true;
385 }
386 false
387 }
388
389
390#[cfg(test)]
391 mod tests {
392 use super::*;
393 use rustc_hex::ToHex;
394
395 #[test]
396 fn test_hash_vec() {
397 let a: Vec<u8> = From::from("test");
398 let h = utils::hash_vec(a);
399 assert_eq!("9c22ff5f21f0b81b113e63f7db6da94fedef11b2119b4088b89664fb9a3cb658", h.to_hex());
400 }
401
402 #[test]
403 fn test_new_mt() {
404 let mt: MerkleTree = new(140);
405 assert_eq!(140, mt.num_levels);
406 assert_eq!("0000000000000000000000000000000000000000000000000000000000000000", mt.root.to_hex());
407 let (_t, _il, b) = mt.sto.get(&[0;32]);
408 assert_eq!(mt.root.to_vec(), b);
409 }
410
411
412 #[test]
413 fn test_tree_node() {
414 let n = node::TreeNode {
415 child_l: [1;32],
416 child_r: [2;32],
417 };
418 assert_eq!("01010101010101010101010101010101010101010101010101010101010101010202020202020202020202020202020202020202020202020202020202020202",
419 n.bytes().to_hex());
420 assert_eq!("346d8c96a2454213fcc0daff3c96ad0398148181b9fa6488f7ae2c0af5b20aa0", n.ht().to_hex());
421 }
422
423 #[test]
424 fn test_add() {
425 let mut mt: MerkleTree = new(140);
426 assert_eq!("0000000000000000000000000000000000000000000000000000000000000000", mt.root.to_hex());
427 let val = TestValue {
428 bytes: vec![1,2,3,4,5],
429 index_length: 3,
430 };
431 mt.add(&val);
432 let (_t, _il, b) = mt.sto.get(&val.ht());
433 assert_eq!(*val.bytes(), b);
434 assert_eq!("a0e72cc948119fcb71b413cf5ada12b2b825d5133299b20a6d9325ffc3e2fbf1", mt.root.to_hex());
435 }
436
437 #[test]
438 fn test_add_2() {
439 let mut mt: MerkleTree = new(140);
440 let val = TestValue {
441 bytes: "this is a test leaf".as_bytes().to_vec(),
442 index_length: 15,
443 };
444 assert_eq!("0000000000000000000000000000000000000000000000000000000000000000", mt.root.to_hex());
445 mt.add(&val);
446 let (_t, _il, b) = mt.sto.get(&val.ht());
447 assert_eq!(*val.bytes(), b);
448 assert_eq!("b4fdf8a653198f0e179ccb3af7e4fc09d76247f479d6cfc95cd92d6fda589f27", mt.root.to_hex());
449 let val2 = TestValue {
450 bytes: "this is a second test leaf".as_bytes().to_vec(),
451 index_length: 15,
452 };
453 mt.add(&val2);
454 let (_t, _il, b) = mt.sto.get(&val2.ht());
455 assert_eq!(*val2.bytes(), b);
456 assert_eq!("8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82", mt.root.to_hex());
457 }
458
459 #[test]
460 fn test_generate_proof_and_verify_proof() {
461 let mut mt: MerkleTree = new(140);
462 let val = TestValue {
463 bytes: "this is a test leaf".as_bytes().to_vec(),
464 index_length: 15,
465 };
466 assert_eq!("0000000000000000000000000000000000000000000000000000000000000000", mt.root.to_hex());
467 mt.add(&val);
468 let (_t, _il, b) = mt.sto.get(&val.ht());
469 assert_eq!(*val.bytes(), b);
470 assert_eq!("b4fdf8a653198f0e179ccb3af7e4fc09d76247f479d6cfc95cd92d6fda589f27", mt.root.to_hex());
471 let val2 = TestValue {
472 bytes: "this is a second test leaf".as_bytes().to_vec(),
473 index_length: 15,
474 };
475 mt.add(&val2);
476 let (_t, _il, b) = mt.sto.get(&val2.ht());
477 assert_eq!(*val2.bytes(), b);
478 assert_eq!("8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82", mt.root.to_hex());
479
480 let mp = mt.generate_proof(val2.hi());
481 assert_eq!("0000000000000000000000000000000000000000000000000000000000000001fd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", mp.to_hex());
482
483 // verify
484 let v = verify_proof(mt.root, mp, val2.hi(), val2.ht(), mt.num_levels);
485 assert_eq!(true, v);
486 }
487
488 #[test]
489 fn test_generate_proof_empty_leaf_and_verify_proof() {
490 let mut mt: MerkleTree = new(140);
491 let val = TestValue {
492 bytes: "this is a test leaf".as_bytes().to_vec(),
493 index_length: 15,
494 };
495 mt.add(&val);
496 let val2 = TestValue {
497 bytes: "this is a second test leaf".as_bytes().to_vec(),
498 index_length: 15,
499 };
500 mt.add(&val2);
501 assert_eq!("8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82", mt.root.to_hex());
502
503 // proof of empty leaf
504 let val3 = TestValue {
505 bytes: "this is a third test leaf".as_bytes().to_vec(),
506 index_length: 15,
507 };
508 let mp = mt.generate_proof(val3.hi());
509 assert_eq!("000000000000000000000000000000000000000000000000000000000000000389741fa23da77c259781ad8f4331a5a7d793eef1db7e5200ddfc8e5f5ca7ce2bfd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", mp.to_hex());
510
511 // verify that is a proof of an empty leaf (EMPTYNODEVALUE)
512 let v = verify_proof(mt.root, mp, val3.hi(), EMPTYNODEVALUE, mt.num_levels);
513 assert_eq!(true, v);
514 }
515
516 #[test]
517 fn test_harcoded_proofs_of_existing_leaf() {
518 // check proof of value in leaf
519 let mut root: [u8;32] = [0;32];
520 root.copy_from_slice(&hex::decode("7d7c5e8f4b3bf434f3d9d223359c4415e2764dd38de2e025fbf986e976a7ed3d").unwrap());
521 let mp = hex::decode("0000000000000000000000000000000000000000000000000000000000000002d45aada6eec346222eaa6b5d3a9260e08c9b62fcf63c72bc05df284de07e6a52").unwrap();
522 let mut hi: [u8;32] = [0;32];
523 hi.copy_from_slice(&hex::decode("786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878").unwrap());
524 let mut ht: [u8;32] = [0;32];
525 ht.copy_from_slice(&hex::decode("786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878").unwrap());
526 let v = verify_proof(root, mp, hi, ht, 140);
527 assert_eq!(true, v);
528 }
529
530 #[test]
531 fn test_harcoded_proofs_of_empty_leaf() {
532 // check proof of value in leaf
533 let mut root: [u8;32] = [0;32];
534 root.copy_from_slice(&hex::decode("8f021d00c39dcd768974ddfe0d21f5d13f7215bea28db1f1cb29842b111332e7").unwrap());
535 let mp = hex::decode("0000000000000000000000000000000000000000000000000000000000000004bf8e980d2ed328ae97f65c30c25520aeb53ff837579e392ea1464934c7c1feb9").unwrap();
536 let mut hi: [u8;32] = [0;32];
537 hi.copy_from_slice(&hex::decode("a69792a4cff51f40b7a1f7ae596c6ded4aba241646a47538898f17f2a8dff647").unwrap());
538 let v = verify_proof(root, mp, hi, EMPTYNODEVALUE, 140);
539 assert_eq!(true, v);
540 }
541
542 #[test]
543 fn test_add_leafs_different_order() {
544 let mut mt1: MerkleTree = new(140);
545 mt1.add(&TestValue {bytes: "0 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
546 mt1.add(&TestValue {bytes: "1 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
547 mt1.add(&TestValue {bytes: "2 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
548 mt1.add(&TestValue {bytes: "3 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
549 mt1.add(&TestValue {bytes: "4 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
550 mt1.add(&TestValue {bytes: "5 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
551 mt1.print_full_tree();
552
553
554 let mut mt2: MerkleTree = new(140);
555 mt2.add(&TestValue {bytes: "2 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
556 mt2.add(&TestValue {bytes: "1 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
557 mt2.add(&TestValue {bytes: "0 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
558 mt2.add(&TestValue {bytes: "5 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
559 mt2.add(&TestValue {bytes: "3 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
560 mt2.add(&TestValue {bytes: "4 this is a test leaf".as_bytes().to_vec(), index_length: 15,});
561 mt2.print_full_tree();
562
563 assert_eq!(mt1.root, mt2.root);
564 assert_eq!(mt1.root.to_hex(), "264397f84da141b3134dcde1d7540d27a2bf0d787bbe8365d9ad5c9c18d3c621");
565 }
566
567 #[test]
568 fn test_add_1000_leafs() {
569 let mut mt: MerkleTree = new(140);
570 for i in 0..1000 {
571 mt.add(&TestValue {bytes: (i.to_string()+" this is a test leaf").as_bytes().to_vec(), index_length: 15,});
572 }
573 assert_eq!(mt.root.to_hex(), "6e2da580b2920cd78ed8d4e4bf41e209dfc99ef28bc19560042f0ac803e0d6f7");
574 }
575 }