Databases Reference
In-Depth Information
0
1
23
h
0
(k)
= 1
0
1
23
4
67
5
0
1
23
h
1
(k)
= 0
23
4
5
67
0
1
0
1
23
4
5
67
h
2
(k)
= 7
h
3
(k)
= 2
0
1
23
4
5
67
(a) GHT Before Insertion
(b) GHT After Insertion
Fig. 2.
Inserting element
k
into a generalized hash tree. (a) The GHT before
k
is inserted. The shaded nodes are occupied and the white nodes are empty. (b)
h
0
(
k
) = 1, but node position 1 in the root node is already occupied. So
k
must be
hashed again using
h
1
, with the goal of inserting
k
in the node that is the child
of position 1 in the root node.
h
1
(
k
) = 0, but the 0th position in the appropriate
subtree of the root is occupied, so
k
is hashed again using
h
2
. This again results in
a collision. Finally, a new leaf is added and
k
is inserted at position
h
3
(
k
)=2.
The first step in ensuring trustworthy indexing is to store the index on
WORM. The problem of creating an index on write-once media has been
studied before. For example, in
write-once B-trees
[6] (Figure 1(a)), a node
is split into two new nodes when it overflows. Two pointers are added to the
end of its parent node, superseding the earlier pointer to the old node. If the
parent node overflows, it is split as well and only the most recent pointers are
copied. When the root node splits, a new root is created. Unfortunately, the
use of WORM alone is insucient to make this or any other index trustworthy.
For example, in a write-once B-tree, an adversary can effectively modify any
record he wishes by creating a new version of the appropriate nodes, as shown
in Figure 1(b). Although every alteration of the nodes is preserved in WORM
storage, it is too expensive to examine each version of the tree on each lookup
to guard against tampering.
Traditional hash-based structures are also not secure against tampering.
For example, in dynamic hashing and its extensions (e.g., [5, 8, 2]), when
the number of records in a hash table exceeds a high water mark, a new
hash table with a larger size is allocated and all the records are rehashed and
moved into the new table. In this way, dynamic data growth can be supported
with good performance. The ability to relocate records, however, provides an
opportunity for an adversary to alter the records during the copying step. A
trie that stores records in its leaf nodes and moves records to new leaf nodes as
the trie grows will also be untrustworthy. All these approaches are vulnerable
because the search path to a particular record is not term-immutable.
To date, researchers have proposed trustworthy versions of hashing and in-
verted indexes, both of which guarantee term-immutable search paths. For ex-
ample, a
generalized hash tree
(GHT) supports exact-match lookups of records
based on attribute values [50]. One can use such an index, for example, to find
all email sent from a particular address.
