Databases Reference
In-Depth Information
Authentication cost:
Assuming that
ρ
0
is the total number of query results contained in the left
boundary leaf node of the query sub-tree,
σ
0
on the right boundary leaf node,
and
ρ
i
,σ
i
the total number of entries of the left and right boundary nodes on
level
i,
1
d
q
, that point towards leaves that contain query results (see
Figure 4), the size of the
≤
i
≤
VO
is:
m
=
(2
f
m
−
|VO|
ρ
0
−
σ
0
)
|
h
|
+
N
R
·|
r
|
+
|
s
|
+
(
d
m
−
d
q
)
·
(
f
m
−
1)
|
h
|
+
d
q
−
2
(2
f
m
−
ρ
i
−
σ
i
)
|
h
|
+
i
=1
(
f
m
−
ρ
d
q
−
1
−
σ
d
q
−
1
)
|
h
|
.
(11)
This cost does not include the extra boundary information needed by the
client in order to group hashes correctly, but this overhead is very small (one
byte per node in the
) especially when compared with the hash value size.
Consequently, the verification cost on the client is:
VO
d
q
−
1
m
v
f
i
m
·C
H
f
m
|h|
+
C
=
N
R
·C
H
|r|
+
i
=0
(
d
m
−
d
q
)
·C
H
f
m
|h|
+
C
V
|h|
.
(12)
Given that the computation cost of hashing versus signing is orders of
magnitude smaller, the initial construction cost of the MB-tree is expected
to be orders of magnitude less expensive than that of the ASB-tree. Given
that the size of hash values is much smaller than that of signatures and that
the fanout of the MB-tree will be smaller than that of the ASB-tree, it is not
easy to quantify the exact difference in the storage cost of these techniques,
but it is expected that the structures will have comparable storage cost, with
the MB-tree being smaller. The
construction cost of the MB-tree will be
much smaller than that of the ASB-tree, since the ASB-tree requires many
I/Os for retrieving signatures, and also some expensive modular multiplica-
tions. The MB-tree will have smaller verification cost as well since: 1. Hashing
operations are orders of magnitude cheaper than modular multiplications, 2.
The ASB-tree requires
N
R
modular multiplications for verification. The only
drawback of the MB-tree is the large
VO
VO
size, which increases the client/server
communication cost. Notice that the
VO
size of the MB-tree is bounded by
f
m
·
log
f
m
N
D
. Since generally
f
m
log
f
m
N
D
,the
VO
size is essentially
determined by
f
m
, resulting in large sizes.
