Information Technology Reference
In-Depth Information
To reach the
if
ith bottom node, we start from
v
=
S
, where
S
is the start node
while (
if
(ith bottom node is not reached):
{
if
if
∈
[
low
(
w
),
high
(
w
)]
v
=
w
is set //the right pointer is followed
else
v
=
z
is set //the down pointer is followed
}
For each node
v
of the rank-based authenticated skip list, a label
f
(
v
) is
defined as follows:
0
if
v
=
null
(
)
(
)
(
)
() ()
()
()
()
>
()
=
hlvrvfdwnv
,
,
,
frgt v
if
f
lv
0
fv
(
)
(
)
() () () ()
()
=
hlvrvxvfrgtv
,
,
,
if
lv
0
The next two algorithms have been described [10], but we present them
here for completeness.
Algorithm 1 Path Generation:
PathGen
(
if
)
→
{
x
(
v
if
),
Π
}
1: Let
v
1
, ...,
v
k
be the verification path for block
if
2:
return
signature
x
(
v
if
) of block
if
and the table
Π
= (
A
(
v
1
), ...,
A
(
v
k
)) corresponding to block
if
Algorithm 2 Skip List Verification:
verify
(
Π
, x
(
v
if
)
, sig
sk
(
H
(
f
(
S
))))
→
{
TRUE, FALSE
}
1: Let
Π
= (
A
1
, ...,
A
k
),
2: where
A
j
= (
d
j
,
if
j
,
q
j
,
g
j
),1 ≤
j
≤
k
3:
λ
1
= 0;
ρ
1
= 1 +
q
1
;
δ
1
=
d
1
;
ζ
1
= 0;
4:
γ
1
=
h
(
λ
1
,
ρ
1
,
x
(
v
if
),
g
1
);
5:
for
j
= 2, ...,
k
do
6:
λ
j
=
if
j
;
ρ
j
=
ρ
j
− 1
+
q
j
;
δ
j
=
d
j
;
7:
if
δ
j
= = rgt
then
8:
γ
j
=
h
(
λ
j
,
ρ
j
,
g
j
,
γ
j
− 1
);
9:
ζ
j
=
ζ
j
− 1
;
10:
else if
δ
j
= = dwn
then
11:
γ
j
=
h
(
λ
j
,
ρ
j
,
γ
j
− 1
,
g
j
);
12:
ζ
j
=
ζ
j
− 1
+
q
j
;
13
end if
14:
end for
Search WWH ::
Custom Search