Databases Reference
In-Depth Information
s
tree
=
S
(h
root
)
h
root
=
H
(h
12
|
h
34
)
h
12
=
H
(h
1
|
h
2
)
h
34
=
H
(h
3
|
h
4
)
h
1
=
H
(r
1
)
h
2
=
H
(r
2
)h
3
=
H
(r
3
)
h
4
=
H
(r
4
)
r
1
r
2
r
3
r
4
Fig. 1.
Example of a Merkle hash tree.
multiplications,
t
hashing operations, and one modular exponentiation (thus,
the computational gain is that
t
1 modular exponentiations are replaced by
modular multiplications). Note that aggregating signatures is possible only
for some digital signature schemes.
−
2.4 The Merkle Hash Tree.
The straightforward solution for verifying a set of
n
values is to generate
n
digital signatures, one for each value. An improvement on this straightforward
solution is the Merkle hash tree (see Figure 1), first proposed by [26]. It
solves the simplest form of the query authentication problem for point queries
and datasets that can fit in main memory. The Merkle hash tree is a binary
tree, where each leaf contains the hash of a data value, and each internal
node contains the hash of the concatenation of its two children. Verification
of data values is based on the fact that the hash value of the root of the
tree is authentically published (authenticity can be established by a digital
signature). To prove the authenticity of any data value, all the prover has
to do is to provide the verifier, in addition to the data value itself, with the
values stored in the siblings of the path that leads from the root of the tree to
that value. The verifier, by iteratively computing all the appropriate hashes
up the tree, at the end can simply check if the hash she has computed for the
root matches the authentically published value. The security of the Merkle
hash tree is based on the collision-resistance of the hash function used: it is
computationally infeasible for a malicious prover to fake a data value, since
this would require finding a hash collision somewhere in the tree (because
the root remains the same and the leaf is different—hence, there must be
a collision somewhere in between). Thus, the authenticity of any one of
n
data values can be proven at the cost of providing and computing log
2
n
hash
values, which is generally much cheaper than storing and verifying one digital
signature per data value. Furthermore, the relative position (leaf number)
of any of the data values within the tree is authenticated along with the
value itself. Finally, in [27] this idea is extended to dynamic environments,
by dynamizing the binary search tree using 2-3 trees. Thus, insertions and
deletions can be handled eciently by the Merkle hash tree.
