Databases Reference
In-Depth Information
size, for constructing the
and authenticating the results, 6. The require-
ment for a public key signature scheme that supports aggregated signatures.
For the rest of the chapter, this approach is denoted as Aggregated Signatures
with
B
+
-trees (ASB-tree). The ASB-tree has been generalized to work with
multi-dimensional selection queries in [24, 31].
VO
The Merkle B-tree
Motivated by the drawbacks of the ASB-tree, we present a different approach
for building authenticated structures that is based on the general ideas of
[28] (which utilize the Merkle hash tree) applied in our case on a
B
+
-tree
structure. We term this structure the Merkle B-tree (MB-tree).
As already explained in Section 2.4, the Merkle hash tree uses a hierarchical
hashing scheme in the form of a binary tree to achieve query authentication.
Clearly, one can use a similar hashing scheme with trees of
higher fanout and
with different organization algorithms
, like the
B
+
-tree, to achieve the same
goal. An MB-tree works like a
B
+
-tree and also consists of ordinary
B
+
-tree
nodes that are extended with one hash value associated with every pointer
entry. The hash values associated with entries on leaf nodes are computed
on the database records themselves. The hash values associated with index
node entries are computed on the concatenation of the hash values of their
children. For example, an MB-tree is illustrated in Figure 3. A leaf node
entry is associated with a hash value
h
=
H
(
r
i
), while an index node entry
with
h
=
h
f
m
), where
h
1
,...,h
f
m
are the hash values of the node's
children, assuming fanout
f
m
per node. After computing all hash values, the
owner has to sign the hash of the root using its secret key
SK
.
H
(
h
1
|ยทยทยท|
...
...
k
j
p
j
h
j
=
H
(
h
1
|
...
|h
f
)
...
...
...
k
i
p
i
h
i
=
H
(
r
i
)
Fig. 3.
An MB-tree node.
VO
by initiating two top-
down
B
+
-tree like traversals, one to find the left-most and one the right-
most query result. At the leaf level, the data contained in the nodes between
the two discovered boundary leaves are returned, as in the normal
B
+
-tree.
The server also needs to include in the
To answer a range query the server builds a
the hash values of the entries
contained in each index node that is visited by the lower and upper boundary
traversals of the tree, except the hashes to the right (left) of the pointers
that are traversed during the lower (upper) boundary traversals. At the leaf
level, the server inserts only the answers to the query, along with the hash
VO
