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