Information Technology Reference
In-Depth Information
15:
if
e
(
sig
sk
(
H
(
f
(
S
))),
g
) ≠
e
(
H
(
γ
k
),
v
)
then
16:
return
FALSE
17:
else if
ρ
k
−
ζ
k
≠
i
then
18:
return
FALSE
19:
else
20:
return
TRUE
21:
end if
3.4.3 Skip List Verification
First, we describe the algorithm
PathGen
(
i
) [10] to generate a verification path
for block
i
. The verification path is the reverse search path; for example, let
v
k
,
v
k
−1
, … ,
v
1
be the search path for block
i
, then
v
1
,
v
2
, … ,
v
k
is the verification
path for block
i
. For each node
v
j
,
j
= 1, … ,
k
, Boolean
d
(
v
j
) and values
q
(
v
j
) and
g
(
v
j
) are defined as follows, where
r
(
null
) is set to 0:
=
()
rgt
j
=
1
or j
>
1
nd v
rgt v
()
=
j
−
1
j
dv
j
wn v
()
dwnj
>
1
andv
=
d
j
−
1
(
)
()
rrgt v
j
=
>
()
=
1
j
1
j
1
nd lv
0
j
()
=
qv
(
)
j
()
()
>
()
=
rdwn v
j
>
1,
llv
0
andd vrgt
j
j
j
(
)
()
>
()
>
(()
=
dwn
rrgt v
j
1
,
lv
0
andd v
j
j
j
(
( )
=
()
>
()
=
()
frgt v
j
1
j
xv
j
1
nd lv
0
j
j
()
=
gv
(
)
j
>
()
>
()
=
fdwn v
j
1
,
l v
0
and dv
rgt
j
j
j
(
)
()
>
()
>
()
=
frgt v
j
1
,
lv
0
an
dd v wn
j
j
The
PathGen
(
i
) algorithm returns the sequence Π(
i
) = (
A
(
v
1
), … ,
A
(
v
k
)) where
A
(
v
) = (
d
(
v
),
l
(
v
),
q
(
v
),
g
(
v
)) for the block
i
with signature
x
(
i
). Table 3.2 shows
the sequence Π(
v
6
) as the sample verification path. Due to the properties of
the skip list, data in the verification path have an expected size
O
(log
n
) with
high probability.
To verify the skip list, the verifier requests the signature generated by the
client by signing the start node of the skip list and the path table Π for any
random block. Then, the verifier runs the skip list verification algorithm
Search WWH ::
Custom Search