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