-
Notifications
You must be signed in to change notification settings - Fork 50
/
partial.rs
137 lines (133 loc) · 5.28 KB
/
partial.rs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// Copyright 2019-2022 Manta Network.
// This file is part of manta-rs.
//
// manta-rs is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// manta-rs is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with manta-rs. If not, see <http://www.gnu.org/licenses/>.
//! Partial Merkle Tree Tests
use crate::{
accumulator::{Accumulator, FromItemsAndWitnesses},
merkle_tree::{
forest::{Forest, TreeArrayMerkleForest},
fork::ForkedTree,
full::{Full, FullMerkleTree},
partial::{Partial, PartialMerkleTree},
path::Path,
test::{BinaryIndex, Test},
tree::Parameters,
},
rand::{OsRng, Rand, Sample},
};
/// Tests the [`Partial`] tree generated from a set of leaves and a [`Path`] behaves
/// as expected.
#[test]
fn test_from_leaves_and_path() {
let mut rng = OsRng;
const HEIGHT: usize = 7;
type Config = Test<u64, HEIGHT>;
let parameters = Parameters::<Config>::sample(Default::default(), &mut rng);
let number_of_insertions = rng.gen_range(5..(1 << (HEIGHT - 1)));
let inner_element_index = rng.gen_range(0..number_of_insertions - 3);
println!("{number_of_insertions}, {inner_element_index}");
let mut tree = FullMerkleTree::<Config>::new(parameters);
let mut insertions = Vec::<u64>::with_capacity(number_of_insertions);
for _ in 0..number_of_insertions {
insertions.push(rng.gen());
}
for leaf in &insertions {
tree.insert(leaf);
}
let forked_tree = ForkedTree::<Config, Full<Config>>::new(tree.tree.clone(), ¶meters);
let path = tree.current_path();
let partial_tree = PartialMerkleTree::<Test<u64, HEIGHT>> {
parameters,
tree: Partial::from_leaves_and_path_unchecked(
¶meters,
insertions.clone(),
path.clone().into(),
),
};
let forked_partial_tree = ForkedTree::<Config, Partial<Config>>::from_leaves_and_path_unchecked(
¶meters,
insertions.clone(),
path.into(),
);
let root = tree.root();
let partial_root = partial_tree.root();
let forked_root = forked_tree.root();
let forked_partial_root = forked_partial_tree.root();
assert_eq!(root, partial_root, "Roots must be equal");
assert_eq!(root, forked_root, "Roots must be equal");
assert_eq!(root, forked_partial_root, "Roots must be equal");
let proof_full_inner = tree
.prove(&insertions[inner_element_index])
.expect("Failed to generate proof");
let proof_partial_inner = partial_tree
.prove(&insertions[inner_element_index])
.expect("Failed to generate proof");
assert!(
proof_full_inner.verify(¶meters, &insertions[inner_element_index], &mut ()),
"Inner proof in the full tree must be valid"
);
assert!(
!proof_partial_inner.verify(¶meters, &insertions[inner_element_index], &mut ()),
"Inner proof in the partial tree must be invalid"
);
let proof_full = tree
.prove(&insertions[number_of_insertions - 1])
.expect("Failed to generate proof");
let proof_partial = partial_tree
.prove(&insertions[number_of_insertions - 1])
.expect("Failed to generate proof");
assert!(
proof_full.verify(¶meters, &insertions[number_of_insertions - 1], &mut ()),
"Final proof in the full tree must be valid"
);
assert!(
proof_partial.verify(¶meters, &insertions[number_of_insertions - 1], &mut ()),
"Final proof in the partial tree must be valid"
);
}
/// Tests the forest consisting of [`Partial`] trees generated from a set of leaves
/// and a [`Path`]s behaves as expected.
#[test]
fn test_from_leaves_and_path_forest() {
let mut rng = OsRng;
const HEIGHT: usize = 7;
type Config = Test<u64, HEIGHT>;
let parameters = Parameters::<Config>::sample(Default::default(), &mut rng);
let mut forest =
TreeArrayMerkleForest::<Config, ForkedTree<Config, Full<Config>>, 2>::new(parameters);
let number_of_insertions = rng.gen_range(5..(1 << (HEIGHT - 1)));
let mut insertions = Vec::<u64>::with_capacity(number_of_insertions);
for _ in 0..number_of_insertions {
insertions.push(rng.gen());
}
for leaf in &insertions {
forest.insert(leaf);
}
let path_1 = Path::from(forest.forest.get(BinaryIndex::Zero).current_path());
let path_2 = Path::from(forest.forest.get(BinaryIndex::One).current_path());
let paths = vec![path_1, path_2];
let items = TreeArrayMerkleForest::<_, ForkedTree<_, Partial<Config>>, 2>::sort_items(
insertions.clone(),
);
let partial_forest =
TreeArrayMerkleForest::<_, ForkedTree<_, Partial<Config>>, 2>::from_items_and_witnesses(
¶meters,
items,
paths,
);
for leaf in &insertions {
assert_eq!(forest.output_from(leaf), partial_forest.output_from(leaf));
}
}