merkletree-rs/src/lib.rs
src/lib.rsRaw
1#[macro_use]
2extern crate arrayref;
3extern crate hex;
4extern crate rustc_hex;
5extern crate tiny_keccak;
6
7use rustc_hex::ToHex;
8
9pub mod constants;
10pub mod db;
11pub mod node;
12pub mod utils;
13
14type Result<T> = std::result::Result<T, String>;
15
16pub struct TestValue {
17 pub bytes: Vec<u8>,
18 pub index_length: u32,
19}
20pub trait Value {
21 fn bytes(&self) -> &Vec<u8>;
22 fn index_length(&self) -> u32;
23 fn hi(&self) -> [u8; 32];
24 fn ht(&self) -> [u8; 32];
25}
26impl Value for TestValue {
27 fn bytes(&self) -> &Vec<u8> {
28 &self.bytes
29 }
30 fn index_length(&self) -> u32 {
31 self.index_length
32 }
33 fn hi(&self) -> [u8; 32] {
34 utils::hash_vec(
35 self.bytes()
36 .to_vec()
37 .split_at(self.index_length() as usize)
38 .0
39 .to_vec(),
40 )
41 }
42 fn ht(&self) -> [u8; 32] {
43 utils::hash_vec(self.bytes().to_vec())
44 }
45}
46
47pub struct MerkleTree<'a> {
48 root: [u8; 32],
49 num_levels: u32,
50 sto: &'a mut db::Db,
51 root_node_key: [u8;32],
52}
53impl<'a> MerkleTree<'a> {
54 pub fn new(database: &'a mut db::Db, num_levels: u32) -> MerkleTree<'a> {
55 let rnk: [u8; 32] = utils::hash_vec("root".as_bytes().to_vec());
56 let (_, _, root_vec) = database.get(&rnk);
57 let mut root: [u8; 32] = [0;32];
58 root.copy_from_slice(&root_vec); // root will be [0;32] if not found (EMPTYNODEVALUE)
59
60 MerkleTree {
61 root: root,
62 num_levels,
63 sto: database,
64 root_node_key: rnk,
65 }
66 }
67 pub fn get_root(&mut self) -> [u8; 32] {
68 self.root
69 }
70 pub fn get_num_levels(&mut self) -> u32 {
71 self.num_levels
72 }
73
74 pub fn add(&mut self, v: &TestValue) -> Result<()> {
75 // add the leaf that we are adding
76 self.sto.insert(
77 v.ht(),
78 constants::TYPENODEVALUE,
79 v.index_length(),
80 v.bytes().to_vec(),
81 );
82
83 let hi = v.hi();
84 let path = utils::get_path(self.num_levels, hi);
85 let mut siblings: Vec<[u8; 32]> = Vec::new();
86
87 let mut node_hash = self.root;
88
89 for i in (0..=self.num_levels - 2).rev() {
90 // get node
91 let (t, il, node_bytes) = self.sto.get(&node_hash);
92 if t == constants::TYPENODEFINAL {
93 let hi_child =
94 utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
95 let path_child = utils::get_path(self.num_levels, hi_child);
96 let pos_diff = utils::compare_paths(&path_child, &path);
97 if pos_diff == -1 {
98 return Err("node already exists".to_owned());
99 }
100 let final_node_1_hash = utils::calc_hash_from_leaf_and_level(
101 pos_diff as u32,
102 &path_child,
103 utils::hash_vec(node_bytes.to_vec()),
104 );
105 self.sto.insert(
106 final_node_1_hash,
107 constants::TYPENODEFINAL,
108 il,
109 node_bytes.to_vec(),
110 );
111 let final_node_2_hash =
112 utils::calc_hash_from_leaf_and_level(pos_diff as u32, &path, v.ht());
113 self.sto.insert(
114 final_node_2_hash,
115 constants::TYPENODEFINAL,
116 v.index_length(),
117 v.bytes().to_vec(),
118 );
119
120 // parent node
121 let parent_node: node::TreeNode;
122 if path[pos_diff as usize] {
123 parent_node = node::TreeNode {
124 child_l: final_node_1_hash,
125 child_r: final_node_2_hash,
126 }
127 } else {
128 parent_node = node::TreeNode {
129 child_l: final_node_2_hash,
130 child_r: final_node_1_hash,
131 }
132 }
133 let empties = utils::get_empties_between_i_and_pos(i, pos_diff as u32 + 1);
134 for empty in &empties {
135 siblings.push(*empty);
136 }
137
138 let path_from_pos_diff = utils::cut_path(&path, (pos_diff + 1) as usize);
139
140 self.root = self.replace_leaf(
141 path_from_pos_diff,
142 &siblings,
143 parent_node.ht(),
144 constants::TYPENODENORMAL,
145 0,
146 parent_node.bytes().to_vec(),
147 );
148 self.sto
149 .insert(self.root_node_key, constants::TYPENODEROOT, 0, self.root.to_vec());
150 return Ok(());
151 }
152
153 let node = node::parse_node_bytes(node_bytes);
154
155 let sibling: [u8; 32];
156 if !path[i as usize] {
157 node_hash = node.child_l;
158 sibling = node.child_r;
159 } else {
160 sibling = node.child_l;
161 node_hash = node.child_r;
162 }
163 siblings.push(*array_ref!(sibling, 0, 32));
164 if node_hash == constants::EMPTYNODEVALUE {
165 if i == self.num_levels - 2
166 && siblings[siblings.len() - 1] == constants::EMPTYNODEVALUE
167 {
168 let final_node_hash =
169 utils::calc_hash_from_leaf_and_level(i + 1, &path, v.ht());
170 self.sto.insert(
171 final_node_hash,
172 constants::TYPENODEFINAL,
173 v.index_length(),
174 v.bytes().to_vec(),
175 );
176 self.root = final_node_hash;
177 self.sto
178 .insert(self.root_node_key, constants::TYPENODEROOT, 0, self.root.to_vec());
179 return Ok(());
180 }
181 let final_node_hash = utils::calc_hash_from_leaf_and_level(i, &path, v.ht());
182 let path_from_i = utils::cut_path(&path, i as usize);
183 self.root = self.replace_leaf(
184 path_from_i,
185 &siblings,
186 final_node_hash,
187 constants::TYPENODEFINAL,
188 v.index_length(),
189 v.bytes().to_vec(),
190 );
191 self.sto
192 .insert(self.root_node_key, constants::TYPENODEROOT, 0, self.root.to_vec());
193 return Ok(());
194 }
195 }
196 self.root = self.replace_leaf(
197 path,
198 &siblings,
199 v.ht(),
200 constants::TYPENODEVALUE,
201 v.index_length(),
202 v.bytes().to_vec(),
203 );
204 self.sto
205 .insert(self.root_node_key, constants::TYPENODEROOT, 0, self.root.to_vec());
206 return Ok(());
207 }
208
209 pub fn replace_leaf(
210 &mut self,
211 path: Vec<bool>,
212 siblings: &Vec<[u8; 32]>,
213 leaf_hash: [u8; 32],
214 node_type: u8,
215 index_length: u32,
216 leaf_value: Vec<u8>,
217 ) -> [u8; 32] {
218 self.sto
219 .insert(leaf_hash, node_type, index_length, leaf_value);
220 let mut curr_node = leaf_hash;
221
222 for i in 0..siblings.len() {
223 if !path[i as usize] {
224 let node = node::TreeNode {
225 child_l: curr_node,
226 child_r: siblings[siblings.len() - 1 - i],
227 };
228 self.sto
229 .insert(node.ht(), constants::TYPENODENORMAL, 0, node.bytes());
230 curr_node = node.ht();
231 } else {
232 let node = node::TreeNode {
233 child_l: siblings[siblings.len() - 1 - i],
234 child_r: curr_node,
235 };
236 self.sto
237 .insert(node.ht(), constants::TYPENODENORMAL, 0, node.bytes());
238 curr_node = node.ht();
239 }
240 }
241 curr_node
242 }
243
244 pub fn get_value_in_pos(&mut self, hi: [u8; 32]) -> Vec<u8> {
245 let path = utils::get_path(self.num_levels, hi);
246 let mut node_hash = self.root;
247 for i in (0..=self.num_levels - 2).rev() {
248 let (t, il, node_bytes) = self.sto.get(&node_hash);
249 if t == constants::TYPENODEFINAL {
250 let hi_node = utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
251 let path_node = utils::get_path(self.num_levels, hi_node);
252 let pos_diff = utils::compare_paths(&path_node, &path);
253 if pos_diff != -1 {
254 return constants::EMPTYNODEVALUE.to_vec();
255 }
256 return node_bytes;
257 }
258 let node = node::parse_node_bytes(node_bytes);
259 if !path[i as usize] {
260 node_hash = node.child_l;
261 } else {
262 node_hash = node.child_r;
263 }
264 }
265 let (_t, _il, node_bytes) = self.sto.get(&node_hash);
266 node_bytes
267 }
268
269 pub fn generate_proof(&mut self, hi: [u8; 32]) -> Vec<u8> {
270 let mut mp: Vec<u8> = Vec::new();
271
272 let mut empties: [u8; 32] = [0; 32];
273 let path = utils::get_path(self.num_levels, hi);
274
275 let mut siblings: Vec<[u8; 32]> = Vec::new();
276 let mut node_hash = self.root;
277
278 for i in 0..self.num_levels {
279 let (t, il, node_bytes) = self.sto.get(&node_hash);
280 if t == constants::TYPENODEFINAL {
281 let real_value_in_pos = self.get_value_in_pos(hi);
282 if real_value_in_pos == constants::EMPTYNODEVALUE {
283 let leaf_hi =
284 utils::hash_vec(node_bytes.to_vec().split_at(il as usize).0.to_vec());
285 let path_child = utils::get_path(self.num_levels, leaf_hi);
286 let pos_diff = utils::compare_paths(&path_child, &path);
287 if pos_diff as u32 == self.num_levels {
288 return mp;
289 }
290 if pos_diff as u32 != self.num_levels - 1 - i {
291 let sibling = utils::calc_hash_from_leaf_and_level(
292 pos_diff as u32,
293 &path_child,
294 utils::hash_vec(node_bytes.to_vec()),
295 );
296 let mut new_siblings: Vec<[u8; 32]> = Vec::new();
297 new_siblings.push(sibling);
298 new_siblings.extend(siblings);
299 siblings = new_siblings;
300 // set empties bit
301 let bit_pos = self.num_levels - 2 - pos_diff as u32;
302 empties[(empties.len() as isize + (bit_pos as isize / 8 - 1) as isize)
303 as usize] |= 1 << (bit_pos % 8);
304 }
305 }
306 break;
307 }
308 let node = node::parse_node_bytes(node_bytes);
309 let sibling: [u8; 32];
310 if !path[self.num_levels as usize - i as usize - 2] {
311 node_hash = node.child_l;
312 sibling = node.child_r;
313 } else {
314 sibling = node.child_l;
315 node_hash = node.child_r;
316 }
317 if sibling != constants::EMPTYNODEVALUE {
318 // set empties bit
319 empties[(empties.len() as isize + (i as isize / 8 - 1) as isize) as usize] |=
320 1 << (i % 8);
321 let mut new_siblings: Vec<[u8; 32]> = Vec::new();
322 new_siblings.push(sibling);
323 new_siblings.extend(siblings);
324 siblings = new_siblings;
325 }
326 }
327 mp.append(&mut empties[..].to_vec());
328 for s in siblings {
329 mp.append(&mut s.to_vec());
330 }
331 mp
332 }
333
334 pub fn print_level(&mut self, parent: [u8; 32], mut lvl: u32, max_level: u32) {
335 let mut line: String = "".to_string();
336 for _ in 0..lvl {
337 line += &format!(" ");
338 }
339 line += &format!("lvl {}", lvl);
340 line += &format!(" - '{}' = ", parent.to_hex());
341 let (t, _, node_bytes) = self.sto.get(&parent);
342 let mut node = node::TreeNode {
343 child_l: constants::EMPTYNODEVALUE,
344 child_r: constants::EMPTYNODEVALUE,
345 };
346 if t == constants::TYPENODENORMAL {
347 node = node::parse_node_bytes(node_bytes);
348 line += &format!("'{}' - '{}'", node.child_l.to_hex(), node.child_r.to_hex());
349 } else if t == constants::TYPENODEVALUE {
350 //
351 } else if t == constants::TYPENODEFINAL {
352 let hash_node_bytes = utils::hash_vec(node_bytes);
353 line += &format!("[final] final tree node: {} \n", hash_node_bytes.to_hex());
354 let (_, _, leaf_node_bytes) = self.sto.get(&hash_node_bytes);
355 for _ in 0..lvl {
356 line += " ";
357 }
358 let leaf_node_string = String::from_utf8_lossy(&leaf_node_bytes);
359 line += &format!("leaf value: {}", leaf_node_string);
360 } else {
361 line += "[EMPTY Branch]"
362 }
363 println!("{}", line);
364 lvl += 1;
365 if node.child_r.len() > 0
366 && lvl < max_level
367 && t != constants::TYPENODEEMPTY
368 && t != constants::TYPENODEFINAL
369 {
370 self.print_level(node.child_l, lvl, max_level);
371 self.print_level(node.child_r, lvl, max_level);
372 }
373 }
374 pub fn print_full_tree(&mut self) {
375 let root = self.root.clone();
376 let num_levels = self.num_levels.clone();
377 self.print_level(root, 0, num_levels - 1);
378 println!("root {:?}", &self.root.to_hex());
379 }
380 pub fn print_levels_tree(&mut self, max_level: u32) {
381 let root = self.root.clone();
382 let num_levels = self.num_levels.clone();
383 self.print_level(root, 0, num_levels - 1 - max_level);
384 println!("root {:?}", self.root.to_hex());
385 }
386}
387
388pub fn verify_proof(
389 root: [u8; 32],
390 mp: &Vec<u8>,
391 hi: [u8; 32],
392 ht: [u8; 32],
393 num_levels: u32,
394) -> bool {
395 let empties: Vec<u8>;
396 empties = mp.split_at(32).0.to_vec();
397
398 let mut siblings: Vec<[u8; 32]> = Vec::new();
399 for i in (empties.len()..mp.len()).step_by(constants::EMPTYNODEVALUE.len()) {
400 let mut sibling: [u8; 32] = [0; 32];
401 sibling.copy_from_slice(&mp[i..i + constants::EMPTYNODEVALUE.len()]);
402 siblings.push(sibling);
403 }
404
405 let path = utils::get_path(num_levels, hi);
406 let mut node_hash = ht;
407 let mut sibling_used_pos = 0;
408
409 for i in (0..=num_levels - 2).rev() {
410 let sibling: [u8; 32];
411 if (empties[empties.len() - i as usize / 8 - 1] & (1 << (i % 8))) > 0 {
412 sibling = siblings[sibling_used_pos];
413 sibling_used_pos += 1;
414 } else {
415 sibling = constants::EMPTYNODEVALUE;
416 }
417
418 let n: node::TreeNode;
419 if path[num_levels as usize - i as usize - 2] {
420 n = node::TreeNode {
421 child_l: sibling,
422 child_r: node_hash,
423 }
424 } else {
425 n = node::TreeNode {
426 child_l: node_hash,
427 child_r: sibling,
428 }
429 }
430 if node_hash == constants::EMPTYNODEVALUE && sibling == constants::EMPTYNODEVALUE {
431 node_hash = constants::EMPTYNODEVALUE;
432 } else {
433 node_hash = n.ht();
434 }
435 }
436 if node_hash == root {
437 return true;
438 }
439 false
440}
441
442#[cfg(test)]
443mod tests {
444 use super::*;
445 use rustc_hex::ToHex;
446
447 #[test]
448 fn test_hash_vec() {
449 let a: Vec<u8> = From::from("test".to_string());
450 let h = utils::hash_vec(a);
451 assert_eq!(
452 "9c22ff5f21f0b81b113e63f7db6da94fedef11b2119b4088b89664fb9a3cb658",
453 h.to_hex()
454 );
455 }
456
457 #[test]
458 fn test_new_mt() {
459 let mut sto = db::Db::new("test".to_string(), true);
460 let mt = MerkleTree::new(&mut sto, 140);
461 assert_eq!(140, mt.num_levels);
462 assert_eq!(
463 "0000000000000000000000000000000000000000000000000000000000000000",
464 mt.root.to_hex()
465 );
466 let (_t, _il, b) = mt.sto.get(&[0; 32]);
467 assert_eq!(mt.root.to_vec(), b);
468 }
469
470 #[test]
471 fn test_tree_node() {
472 let n = node::TreeNode {
473 child_l: [1; 32],
474 child_r: [2; 32],
475 };
476 assert_eq!("01010101010101010101010101010101010101010101010101010101010101010202020202020202020202020202020202020202020202020202020202020202",
477 n.bytes().to_hex());
478 assert_eq!(
479 "346d8c96a2454213fcc0daff3c96ad0398148181b9fa6488f7ae2c0af5b20aa0",
480 n.ht().to_hex()
481 );
482 }
483
484 #[test]
485 fn test_add() {
486 let mut sto = db::Db::new("test".to_string(), true);
487 let mut mt = MerkleTree::new(&mut sto, 140);
488 assert_eq!(
489 "0000000000000000000000000000000000000000000000000000000000000000",
490 mt.root.to_hex()
491 );
492 let val = TestValue {
493 bytes: vec![1, 2, 3, 4, 5],
494 index_length: 3,
495 };
496 mt.add(&val).unwrap();
497 let (_t, _il, b) = mt.sto.get(&val.ht());
498 assert_eq!(*val.bytes(), b);
499 assert_eq!(
500 "a0e72cc948119fcb71b413cf5ada12b2b825d5133299b20a6d9325ffc3e2fbf1",
501 mt.root.to_hex()
502 );
503 }
504
505 #[test]
506 fn test_add_2() {
507 let mut sto = db::Db::new("test".to_string(), true);
508 let mut mt = MerkleTree::new(&mut sto, 140);
509 let val = TestValue {
510 bytes: "this is a test leaf".as_bytes().to_vec(),
511 index_length: 15,
512 };
513 assert_eq!(
514 "0000000000000000000000000000000000000000000000000000000000000000",
515 mt.root.to_hex()
516 );
517 mt.add(&val).unwrap();
518 let (_t, _il, b) = mt.sto.get(&val.ht());
519 assert_eq!(*val.bytes(), b);
520 assert_eq!(
521 "b4fdf8a653198f0e179ccb3af7e4fc09d76247f479d6cfc95cd92d6fda589f27",
522 mt.root.to_hex()
523 );
524 let val2 = TestValue {
525 bytes: "this is a second test leaf".as_bytes().to_vec(),
526 index_length: 15,
527 };
528 mt.add(&val2).unwrap();
529 let (_t, _il, b) = mt.sto.get(&val2.ht());
530 assert_eq!(*val2.bytes(), b);
531 assert_eq!(
532 "8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82",
533 mt.root.to_hex()
534 );
535 }
536
537 #[test]
538 fn test_generate_proof_and_verify_proof() {
539 let mut sto = db::Db::new("test".to_string(), true);
540 let mut mt = MerkleTree::new(&mut sto, 140);
541 let val = TestValue {
542 bytes: "this is a test leaf".as_bytes().to_vec(),
543 index_length: 15,
544 };
545 assert_eq!(
546 "0000000000000000000000000000000000000000000000000000000000000000",
547 mt.root.to_hex()
548 );
549 mt.add(&val).unwrap();
550 let (_t, _il, b) = mt.sto.get(&val.ht());
551 assert_eq!(*val.bytes(), b);
552 assert_eq!(
553 "b4fdf8a653198f0e179ccb3af7e4fc09d76247f479d6cfc95cd92d6fda589f27",
554 mt.root.to_hex()
555 );
556 let val2 = TestValue {
557 bytes: "this is a second test leaf".as_bytes().to_vec(),
558 index_length: 15,
559 };
560 mt.add(&val2).unwrap();
561 let (_t, _il, b) = mt.sto.get(&val2.ht());
562 assert_eq!(*val2.bytes(), b);
563 assert_eq!(
564 "8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82",
565 mt.root.to_hex()
566 );
567
568 let mp = mt.generate_proof(val2.hi());
569 assert_eq!("0000000000000000000000000000000000000000000000000000000000000001fd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", mp.to_hex());
570
571 // verify
572 let v = verify_proof(mt.root, &mp, val2.hi(), val2.ht(), mt.num_levels);
573 assert_eq!(true, v);
574 }
575
576 #[test]
577 fn test_generate_proof_empty_leaf_and_verify_proof() {
578 let mut sto = db::Db::new("test".to_string(), true);
579 let mut mt = MerkleTree::new(&mut sto, 140);
580 let val = TestValue {
581 bytes: "this is a test leaf".as_bytes().to_vec(),
582 index_length: 15,
583 };
584 mt.add(&val).unwrap();
585 let val2 = TestValue {
586 bytes: "this is a second test leaf".as_bytes().to_vec(),
587 index_length: 15,
588 };
589 mt.add(&val2).unwrap();
590 assert_eq!(
591 "8ac95e9c8a6fbd40bb21de7895ee35f9c8f30ca029dbb0972c02344f49462e82",
592 mt.root.to_hex()
593 );
594
595 // proof of empty leaf
596 let val3 = TestValue {
597 bytes: "this is a third test leaf".as_bytes().to_vec(),
598 index_length: 15,
599 };
600 let mp = mt.generate_proof(val3.hi());
601 assert_eq!("000000000000000000000000000000000000000000000000000000000000000389741fa23da77c259781ad8f4331a5a7d793eef1db7e5200ddfc8e5f5ca7ce2bfd8e1a60cdb23c0c7b2cf8462c99fafd905054dccb0ed75e7c8a7d6806749b6b", mp.to_hex());
602
603 // verify that is a proof of an empty leaf (constants::EMPTYNODEVALUE)
604 let v = verify_proof(
605 mt.root,
606 &mp,
607 val3.hi(),
608 constants::EMPTYNODEVALUE,
609 mt.num_levels,
610 );
611 assert_eq!(true, v);
612 }
613
614 #[test]
615 fn test_harcoded_proofs_of_existing_leaf() {
616 // check proof of value in leaf
617 let mut root: [u8; 32] = [0; 32];
618 root.copy_from_slice(
619 &hex::decode("7d7c5e8f4b3bf434f3d9d223359c4415e2764dd38de2e025fbf986e976a7ed3d")
620 .unwrap(),
621 );
622 let mp = hex::decode("0000000000000000000000000000000000000000000000000000000000000002d45aada6eec346222eaa6b5d3a9260e08c9b62fcf63c72bc05df284de07e6a52").unwrap();
623 let mut hi: [u8; 32] = [0; 32];
624 hi.copy_from_slice(
625 &hex::decode("786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878")
626 .unwrap(),
627 );
628 let mut ht: [u8; 32] = [0; 32];
629 ht.copy_from_slice(
630 &hex::decode("786677808ba77bdd9090a969f1ef2cbd1ac5aecd9e654f340500159219106878")
631 .unwrap(),
632 );
633 let v = verify_proof(root, &mp, hi, ht, 140);
634 assert_eq!(true, v);
635 }
636
637 #[test]
638 fn test_harcoded_proofs_of_empty_leaf() {
639 // check proof of value in leaf
640 let mut root: [u8; 32] = [0; 32];
641 root.copy_from_slice(
642 &hex::decode("8f021d00c39dcd768974ddfe0d21f5d13f7215bea28db1f1cb29842b111332e7")
643 .unwrap(),
644 );
645 let mp = hex::decode("0000000000000000000000000000000000000000000000000000000000000004bf8e980d2ed328ae97f65c30c25520aeb53ff837579e392ea1464934c7c1feb9").unwrap();
646 let mut hi: [u8; 32] = [0; 32];
647 hi.copy_from_slice(
648 &hex::decode("a69792a4cff51f40b7a1f7ae596c6ded4aba241646a47538898f17f2a8dff647")
649 .unwrap(),
650 );
651 let v = verify_proof(root, &mp, hi, constants::EMPTYNODEVALUE, 140);
652 assert_eq!(true, v);
653 }
654
655 #[test]
656 fn test_add_leafs_different_order() {
657 let mut sto1 = db::Db::new("test".to_string(), true);
658 let mut mt1 = MerkleTree::new(&mut sto1, 140);
659 mt1.add(&TestValue {
660 bytes: "0 this is a test leaf".as_bytes().to_vec(),
661 index_length: 15,
662 })
663 .unwrap();
664 mt1.add(&TestValue {
665 bytes: "1 this is a test leaf".as_bytes().to_vec(),
666 index_length: 15,
667 })
668 .unwrap();
669 mt1.add(&TestValue {
670 bytes: "2 this is a test leaf".as_bytes().to_vec(),
671 index_length: 15,
672 })
673 .unwrap();
674 mt1.add(&TestValue {
675 bytes: "3 this is a test leaf".as_bytes().to_vec(),
676 index_length: 15,
677 })
678 .unwrap();
679 mt1.add(&TestValue {
680 bytes: "4 this is a test leaf".as_bytes().to_vec(),
681 index_length: 15,
682 })
683 .unwrap();
684 mt1.add(&TestValue {
685 bytes: "5 this is a test leaf".as_bytes().to_vec(),
686 index_length: 15,
687 })
688 .unwrap();
689 // mt1.print_full_tree();
690
691 let mut sto2 = db::Db::new("test".to_string(), true);
692 let mut mt2 = MerkleTree::new(&mut sto2, 140);
693 mt2.add(&TestValue {
694 bytes: "2 this is a test leaf".as_bytes().to_vec(),
695 index_length: 15,
696 })
697 .unwrap();
698 mt2.add(&TestValue {
699 bytes: "1 this is a test leaf".as_bytes().to_vec(),
700 index_length: 15,
701 })
702 .unwrap();
703 mt2.add(&TestValue {
704 bytes: "0 this is a test leaf".as_bytes().to_vec(),
705 index_length: 15,
706 })
707 .unwrap();
708 mt2.add(&TestValue {
709 bytes: "5 this is a test leaf".as_bytes().to_vec(),
710 index_length: 15,
711 })
712 .unwrap();
713 mt2.add(&TestValue {
714 bytes: "3 this is a test leaf".as_bytes().to_vec(),
715 index_length: 15,
716 })
717 .unwrap();
718 mt2.add(&TestValue {
719 bytes: "4 this is a test leaf".as_bytes().to_vec(),
720 index_length: 15,
721 })
722 .unwrap();
723 // mt2.print_full_tree();
724
725 assert_eq!(mt1.root, mt2.root);
726 assert_eq!(
727 &mt1.root.to_hex(),
728 "264397f84da141b3134dcde1d7540d27a2bf0d787bbe8365d9ad5c9c18d3c621"
729 );
730 }
731
732 #[test]
733 fn test_add_1000_leafs() {
734 let mut sto = db::Db::new("test".to_string(), true);
735 let mut mt = MerkleTree::new(&mut sto, 140);
736 for i in 0..1000 {
737 mt.add(&TestValue {
738 bytes: (i.to_string() + " this is a test leaf").as_bytes().to_vec(),
739 index_length: 15,
740 })
741 .unwrap();
742 }
743 assert_eq!(
744 mt.root.to_hex(),
745 "6e2da580b2920cd78ed8d4e4bf41e209dfc99ef28bc19560042f0ac803e0d6f7"
746 );
747 }
748
749 #[test]
750 fn test_get_root_in_db() {
751 let mut sto = db::Db::new("test".to_string(), true);
752 let mut mt = MerkleTree::new(&mut sto, 140);
753 for i in 0..10 {
754 mt.add(&TestValue {
755 bytes: (i.to_string() + " this is a test leaf").as_bytes().to_vec(),
756 index_length: 15,
757 })
758 .unwrap();
759 }
760 assert_eq!(
761 mt.root.to_hex(),
762 "9418fd35bae19de4ab033efaf7cc624adf6a42827e39029d8da13288e9c3170d"
763 );
764 let mt2 = MerkleTree::new(&mut sto, 140);
765 assert_eq!(
766 mt2.root.to_hex(),
767 "9418fd35bae19de4ab033efaf7cc624adf6a42827e39029d8da13288e9c3170d"
768 );
769 }
770}