Databases Reference
In-Depth Information
33
33
21
23
33
39
43
47
51
63
21
23
33
39
43
47
51
63
Insert 45
Insert 45
33
33
47
33
33
47
21
23
33
39
43
47
51
63
39
43
45
47
51
63
21
23
33
39
43
47
51
63
39
43
45
47
63
(a) Write-Once B-Tree
(b) Tampered Write-Once B-Tree
Fig. 1.
An example of a write-once B-tree insert operation. (a) Inserting 45 requires
a node split. Two new leaf nodes (shaded) are created and pointers to the new nodes
are placed at the parent node. The parent node now has two pointers associated
with 33. During querying, the latest pointer associated with a value is traversed. (b)
Write-once B-trees are not trustworthy. The adversary can omit entries (e.g., value
51) during the copy operation.
Another trick to increase throughput during periods of high load is to tem-
porarily replace expensive SCPU signature operations (e.g., 1024-bit signa-
tures) with less expensive
short-term secure
variants (e.g., 512-bit signatures)
[41]. The system can strengthen these weaker constructs when the load slack-
ens, but within their security lifetime (e.g., before enough time has passed for
an adversary to break the 512-bit signature scheme). This adaptivity helps
the system amortize signature costs over time so that it gracefully handles
high-load document insertion bursts.
6 Trustworthy Indexing
Indexing ensures that a target record can be quickly extracted from terabytes
of data. In our discussion, we will assume that each record is assigned an
integer identifier as it arrives at the storage server, and that identifiers are
given out in increasing order. Any indexing approach for trustworthy records
retention must have the following properties:
•
The index itself must be trustworthy. As explained below, in practice this
means that the search path to an index entry must be immutable for the
lifetime of the record that it indexes.
•
To keep the trusted computing base small, the indexing code should reside
outside the storage server.
•
To ensure that a record
R
is entered and retained in the appropriate in-
dexes
before
Mallory regrets its existence, the insertion and indexing of
R
must be performed atomically.
•
All traces of
R
must be removed from the index when
R
is deleted.
