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
138
|
#include "merkletree/merkle_verifier.h"
#include <stddef.h>
#include <vector>
using std::move;
using std::string;
using std::unique_ptr;
MerkleVerifier::MerkleVerifier(unique_ptr<SerialHasher> hasher)
: treehasher_(move(hasher)) {
}
MerkleVerifier::~MerkleVerifier() {
}
static inline size_t Parent(size_t leaf) {
return leaf >> 1;
}
static inline bool IsRightChild(size_t leaf) {
return leaf & 1;
}
bool MerkleVerifier::VerifyPath(size_t leaf, size_t tree_size,
const std::vector<string>& path,
const string& root, const string& data) {
string path_root = RootFromPath(leaf, tree_size, path, data);
if (path_root.empty())
return false;
return path_root == root;
}
string MerkleVerifier::RootFromPath(size_t leaf, size_t tree_size,
const std::vector<string>& path,
const string& data) {
if (leaf > tree_size || leaf == 0)
// No valid path exists.
return string();
size_t node = leaf - 1;
size_t last_node = tree_size - 1;
string node_hash = LeafHash(data);
std::vector<string>::const_iterator it = path.begin();
while (last_node) {
if (it == path.end())
// We've reached the end but we're not done yet.
return string();
if (IsRightChild(node))
node_hash = treehasher_.HashChildren(*it++, node_hash);
else if (node < last_node)
node_hash = treehasher_.HashChildren(node_hash, *it++);
// Else the sibling does not exist and the parent is a dummy copy.
// Do nothing.
node = Parent(node);
last_node = Parent(last_node);
}
// Check that we've reached the end.
if (it != path.end())
return string();
return node_hash;
}
bool MerkleVerifier::VerifyConsistency(size_t snapshot1, size_t snapshot2,
const string& root1,
const string& root2,
const std::vector<string>& proof) {
if (snapshot1 > snapshot2)
// Can't go back in time.
return false;
if (snapshot1 == snapshot2)
return root1 == root2 && proof.empty();
if (snapshot1 == 0)
// Any snapshot greater than 0 is consistent with snapshot 0.
return proof.empty();
// Now 0 < snapshot1 < snapshot2.
// Verify the roots.
size_t node = snapshot1 - 1;
size_t last_node = snapshot2 - 1;
if (proof.empty())
return false;
std::vector<string>::const_iterator it = proof.begin();
// Move up until the first mutable node.
while (IsRightChild(node)) {
node = Parent(node);
last_node = Parent(last_node);
}
string node1_hash;
string node2_hash;
if (node)
node2_hash = node1_hash = *it++;
else
// The tree at snapshot1 was balanced, nothing to verify for root1.
node2_hash = node1_hash = root1;
while (node) {
if (it == proof.end())
return false;
if (IsRightChild(node)) {
node1_hash = treehasher_.HashChildren(*it, node1_hash);
node2_hash = treehasher_.HashChildren(*it, node2_hash);
++it;
} else if (node < last_node)
// The sibling only exists in the later tree. The parent in the
// snapshot1 tree is a dummy copy.
node2_hash = treehasher_.HashChildren(node2_hash, *it++);
// Else the sibling does not exist in either tree. Do nothing.
node = Parent(node);
last_node = Parent(last_node);
}
// Verify the first root.
if (node1_hash != root1)
return false;
// Continue until the second root.
while (last_node) {
if (it == proof.end())
// We've reached the end but we're not done yet.
return false;
node2_hash = treehasher_.HashChildren(node2_hash, *it++);
last_node = Parent(last_node);
}
// Verify the second root.
return node2_hash == root2 && it == proof.end();
}
string MerkleVerifier::LeafHash(const std::string& data) {
return treehasher_.HashLeaf(data);
}
|
