TELK
OMNIKA
T
elecommunication,
Computing,
Electr
onics
and
Contr
ol
V
ol.
18,
No.
4,
August
2020,
pp.
2224
2234
ISSN:
1693-6930,
accredited
First
Grade
by
K
emenristekdikti,
No:
21/E/KPT/2018
DOI:
10.12928/TELK
OMNIKA.v18i4.15701
r
2224
F
air
and
trustw
orth
y:
Lock-fr
ee
enhanced
tendermint
blockchain
algorithm
Basem
Assiri,
W
azir
Zada
Khan
Department
of
CS
and
IS,
Jazan
Uni
v
ersity
,
Jazan,
Saudi
Arabia
Article
Inf
o
Article
history:
Recei
v
ed
January
30,
2020
Re
vised
April
13,
2020
Accepted
April
29,
2020
K
eyw
ords:
Blockchain
protocol
Consensus
protocols
Correctness
Cryptocurrenc
y
F
airness
Lock-free
Smart
contracts
ABSTRA
CT
Blockchain
T
echnology
is
e
xclusi
v
ely
used
to
mak
e
online
transactions
secure
by
maintaining
a
distrib
uted
and
decentralized
ledger
of
records
across
multiple
com-
puters.
T
endermint
is
a
general-purpose
blockchain
engine
that
is
composed
of
tw
o
parts;
T
endermint
Core
and
the
blockchain
application
interf
ace.
The
application
in-
terf
ace
mak
es
T
endermint
suitable
for
a
wide
range
of
applications.
In
this
paper
,
we
analyze
and
impro
v
e
Practical
Byzantine
F
ault
T
olerant
(PBFT),
a
consensus-based
T
endermint
blockchain
algorithm.
In
order
to
a
v
oid
ne
g
ati
v
e
issues
of
locks,
we
first
propose
a
lock-fr
ee
algorithm
for
blockchain
in
which
the
proposal
and
v
oting
phases
are
concurrent
whereas
the
commit
phase
is
sequential.
This
consideration
in
the
al-
gorithm
allo
ws
parall
elism.
Secondly
,
a
ne
w
methodology
is
used
to
decide
the
size
of
the
v
oter
set
which
is
a
subs
et
of
blockchain
nodes,
further
in
v
estig
ating
the
block
sensiti
vity
and
trustw
orthiness
of
nodes.
Thirdly
,
to
f
airly
select
the
v
oter
set
nodes,
we
emplo
y
the
random
w
alk
algorithm.
F
ourthl
y
,
we
imply
the
w
ait-freedom
property
by
using
a
timeout
due
to
which
all
blocks
are
e
v
entually
committed
or
aborted.
In
addition,
we
ha
v
e
discussed
v
oting
conflicts
and
consensuses
issues
that
are
used
as
a
correctness
property
,
and
pro
vide
some
supporti
v
e
techniques.
This
is
an
open
access
article
under
the
CC
BY
-SA
license
.
Corresponding
A
uthor:
W
azir
Zada
Khan,
Department
of
CS
and
IS,
Jazan
Uni
v
ersity
,
Main
Uni
v
ersity
Campus,
Jazan,
45142,
Saudi
Arabia.
Email:
w
azirzadakhan@jazanu.edu.sa
1.
INTR
ODUCTION
Blockchain
technology
,
also
called
Distrib
uted
Ledger
technology
is
capable
of
achie
ving
and
main-
taining
data
inte
grity
in
distrib
uted
systems,
so
the
interest
in
this
technology
has
been
increased.
The
term
blockchain
w
as
started
in
the
90’
s
as
v
ariant
of
distrib
uted
database
in
which
e
v
ent
or
information
w
as
stored.
After
the
global
financial
meltdo
wn
in
September
2008,
the
term
”Bitcoin”
w
as
first
introduced
by
Satoshi
Nakamoto
[1].
Being
the
first
application
as
a
pure
peer
to
peer
electronic
payment
concept
that
w
as
initially
proposed
to
a
v
oid
the
incurred
cost
caused
by
online
payments.
Duri
ng
the
period
of
September
2014-2015
[2],
bitcoin
has
e
xperienced
an
e
xponential
gro
wth
with
o
v
er
4
million
users,
which
has
t
ransformed
it
into
one
of
the
most
po
werful
computing
netw
orks
in
e
xistence.
After
the
success
of
Bitcoin,
blockchain
has
been
applied
in
man
y
applications
including
smart
cities
[3],
content
deli
v
ery
netw
orks
[4],
access
control
systems
[5],
smart
grid
po
wered
systems,
Internet
of
Things
(IoT)
and
Industrial
IoT
(IIoT)
[6,
7].
User
transactions
can
be
recorded
in
a
decentralized
f
ashion
rather
than
centralized
digital
ledger
ap-
J
ournal
homepage:
http://journal.uad.ac.id/inde
x.php/TELK
OMNIKA
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
r
2225
proaches.
A
blockchain
a
v
oids
the
alteration
of
all
subsequent
blocks
or
collusion
of
all
nodes
in
the
netw
ork
by
maintaining
a
distrib
uted
and
decentralized
ledger
of
records
across
multiple
computers[8].
The
transac-
tions
and
some
details
(such
as
sender
,
recei
v
er
,
amount
of
mone
y
,
and
hash
number)
are
grouped
into
datasets
referred
to
as
”blocks”
[9].
The
blockchain
users
are
called
”miners
”
who
record
and
share
the
data
blocks
o
v
er
the
whole
blockchain
netw
ork.
Ev
ery
node
has
a
cop
y
of
the
ledger
and
all
node
are
connected
for
communi-
cations.
The
nodes
communicate
to
maintain
the
copies
of
the
ledger
and
to
synchronize
processes.
Through
inte
gration
of
edge
computing
and
blockchain
technology
,
high
throughput
and
ef
ficienc
y
of
transaction
pro-
cessing
can
be
achie
v
ed
while
maintaining
data
security
and
inte
grity
[10].
The
operation
and
w
orking
of
blockchain
is
as
follo
ws:
A
ne
w
transaction
record
is
created
when
a
blockchain
user
performs
a
transaction
which
is
then
transferred
to
neighboring
peer
users
in
the
blockchain
netw
ork.
Prior
to
adding
blocks
to
the
public
ledger
,
v
erification
of
transactions
is
done
by
the
neighboring
peer
users
who
used
to
perform
mining
by
utilizing
consensus
algorithms.
These
distrib
uted
consensus
protocols
are
used
to
ensure
that
the
ne
wly
added
transactions
are
not
altered
or
not
f
ak
e.
F
or
the
v
alidation
of
the
block,
the
nodes
in
the
peer
to
peer
netw
ork
solv
e
a
crypto-puzzle
called
Proof-of-w
ork
(PoW)
by
using
computational
re-
sources
at
their
disposal
[11].
Since
this
approach
is
considered
to
be
an
ener
gy
inef
ficient
consensus
approach,
in
order
to
a
v
oid
depletion
of
computat
ional
resources,
v
arious
consensus
mechanisms
are
proposed
including
proof-of-stak
e
(PoS),
proof
of
acti
vity
,
proof
of
space,
v
ariant
s
of
Byzantine
f
ault-tolerant
algorithms
(BFT).
The
proof-of-stak
e
(PoS)
consensus
pr
o
t
ocol
is
an
interestingly
attracti
v
e
one
because
it
does
not
cost
com-
puting
po
wer
and
pro
vides
increased
protection
from
a
malicious
attack
on
the
netw
ork.
In
PoS
mechanism,
there
is
pre-distrib
ution
of
stak
es
at
the
be
ginning
of
the
process.
The
entities
that
ha
v
e
stak
es
in
the
system
are
allo
wed
to
tak
e
block-inclusion
decisions,
irrespecti
v
e
of
blockchain’
s
length
or
history
of
the
public
ledger
.
Dif
fering
in
the
consensus
mechanism,
recently
man
y
v
ariants
of
blockchain
protocols
are
proposed
[12,
13].
Comparing
to
the
other
e
xisting
blockchain
protocols,
the
T
endermint
blockchain
has
unique
charac-
teristics
including
cross
chain
transactions
system
along
with
in-chain
transactions.
A
ne
w
set
of
v
alidators
is
selected
dynamically
for
each
ne
w
block.
Recently
man
y
studies
ha
v
e
analyzed
the
correctness
and
f
airness
of
T
endermint
bloc
k
c
hain
protocol
[14].
Identifying
man
y
b
ugs
in
the
code
of
original
T
endermint
protocol,
this
study
has
proposed
fix
es
for
these
errors
and
for
achie
ving
correctness
and
f
airness,
man
y
enhancements
are
also
proposed.
Another
recent
study
[15]
has
also
analyzed
the
original
T
endermint
protocol
and
highlighted
v
arious
challenges
caused
by
adv
ersary
and
system
model
.
In
this
paper
,
we
ha
v
e
also
re
vie
wed
the
contrib
ution
in
[16]
and
after
f
u
r
ther
in
v
estig
ation,
we
propose
an
enhancement,
discussing
the
design
and
the
T
endermint
blockchain
protocol
in
more
detail
s.
W
e
ha
v
e
made
the
follo
wing
enhancements
in
the
original
T
endermint
blockchain
protocol:
•
The
proposal
and
v
oter
phases
are
considered
concurrent
while
the
commit
phase
is
considered
sequen-
tial.
•
The
v
oters
set
is
a
subset
of
blockchain
nodes.
A
ne
w
methodology
is
used
to
decide
the
size
of
this
subset,
in
v
estig
ating
the
block
sensiti
vity
and
nodes
trustw
orthiness.
•
F
or
the
selection
of
v
oters
set
nodes,
the
random
w
alk
algorithm
is
emplo
yed.
•
The
w
ait-freedom
property
is
maintained
by
using
a
timeout
on
the
v
oting
phase.
Thus,
all
blocks
are
e
v
entually
committed
or
aborted,
which
means
no
one
stays
in
the
e
x
ecution
fore
v
er
and
no
one
w
aits
fore
v
er
to
e
x
ecute.
•
The
reasons
for
v
oting
conflicts
and
the
weakness
of
consensuses
when
it
is
used
as
a
correctness
property
are
in
v
estig
ated
using
R
ound
2
of
the
algorithm.
•
Finally
,
Detection
of
Byzantine
and
f
ailure
nodes
in
the
blockchain
is
sho
wn.
The
remainder
of
this
paper
is
or
g
anized
as
follo
ws:
section
2
discuss
the
related
w
ork.
Section
3
defines
the
System
Model.
Section
4
discusses
the
proposed
modified
algorithm.
Sections
5
discusses
the
v
arious
concepts.
Finally
,
section
6
concludes
the
paper
.
2.
RELA
TED
W
ORK
The
T
endermint
is
a
PBFT
consensus-based
blockchian
protocol
[12–14].
Recently
,
fe
w
research
stud-
ies
ha
v
e
identified
some
issues
and
proposed
enhancements
in
original
T
endermint
blockchian
protocol
[14–16].
Y
.
Amoussou-Guenou
et
al.
[14]
ha
v
e
studied
the
correctness
and
f
airness
of
T
endermint
blockchain
protocol.
The
y
ha
v
e
identified
issues
and
man
y
b
ugs
in
original
protocol.
T
o
achie
v
e
the
correct-
ness
and
f
airness,
the
y
ha
v
e
proposed
enhancement
by
fixing
the
identified
issues
and
b
ugs.
In
[15]
the
original
F
air
and
trustworthy:
Loc
k-fr
ee
enhanced
tendermint
bloc
kc
hain
...
(Basem
Assiri)
Evaluation Warning : The document was created with Spire.PDF for Python.
2226
r
ISSN:
1693-6930
T
endermint
protocol
is
analyzed.
The
authors
ha
v
e
highlighted
v
arious
challenges
caused
by
adv
ersary
and
system
model.
Our
proposed
enhanced
T
endermint
algorithm
is
dif
ferent
from
the
original
T
endermint
[12,
13]
and
its
enhance
v
ariants
[14,
15],
in
the
follo
wing
w
ays;
First,
as
compared
to
the
e
xisting
T
endermint
algorithms
that
are
lock
based,
our
algorithm
is
lock-free.
Although,
the
T
endermint
algori
thm
and
its
v
ariants
use
timeout
to
ma
intain
the
correctness.
Ho
we
v
er
,
it
does
not
pro
vide
progressi
v
eness
such
that
in
case
of
transaction
f
ailure
while
holding
the
lock,
it
results
in
an
issue
with
maintaining
the
progressi
v
eness
and
the
correctness
of
blockchain.
Secondly
,
we
ha
v
e
used
the
w
ait-freedom
property
for
e
v
entually
commit
or
abort
without
staying
in
the
e
x
ecution
fore
v
er
or
w
ait
for
e
x
ecution
for
the
non-deterministic
time
period.
On
the
other
hand,
the
T
endermint
algorithm
and
its
v
ariants
use
timeout
to
maintain
the
correctness.
W
e
ha
v
e
proposed
no
v
el
methods
for
the
selection
of
the
size
of
v
alidator’
s
subsets
and
selection
of
v
alidators
in
order
to
achie
v
e
f
airness.
W
e
ha
v
e
also
considered
the
trustw
orthiness
of
nodes
and
sensiti
vity
of
data.
W
e
ha
v
e
also
emplo
yed
a
random
w
alk
for
the
selection
of
v
alidators
whereas,
the
original
T
endermint
and
its
enhanced
v
ariants
select
the
v
alidators
deterministically
which
results
in
unf
air
re
w
ard
distrib
ution
of
the
v
alidators.
3.
SYSTEM
MODEL
This
section
defines
the
fundamentals
of
our
blockchain
system
model.
The
blockchain
[1,
17,
18]
consists
of
a
set
of
nodes
(processors)
of
size
n
,
called
P
,
where
P
=
f
P
1
;
:::;
P
n
g
;
and
P
i
is
an
y
processor
belongs
to
P
and
i
is
an
inte
ger
such
that
0
<
i
<
n
.
The
blockchain
contains
a
distrib
uted
ledger
L
,
and
each
node
shares
copies
of
memory
objects
and
L
.
F
or
e
xampl
e,
for
a
bank
blockchain,
the
memory
objec
ts
represent
the
bank
accounts,
while
the
operations
on
the
bank
account
recorded
in
L
.
The
operations
on
the
memory
obje
cts
are
either
read
or
write.
The
read
operation
returns
the
data
of
the
memory
object,
while
the
write
operation
updates
the
data
of
memory
object.
A
transaction
is
a
sequence
of
read
and/or
write
operations
that
e
x
ecute
in
isolation
and
at
the
end,
the
transaction
commits
if
it
is
correct,
otherwise,
it
aborts
[19].
F
or
e
xample,
if
a
bank
account
x
has
an
amount
of
mone
y
e
qu
a
ls
to
100$
,
and
a
transaction
withdra
ws
10$
,
then
the
ne
w
v
alue
of
x
is
90$
,
this
transact
ion
is
correct
and
commits;
ho
we
v
er
if
the
result
of
x
is
50$
,
then
the
transaction
aborts.
A
block
B
consists
of
one
or
more
transaction
and
B
commits
when
all
transactions
in
B
commits.
On
the
other
hand,
B
aborts
if
at
least
one
transaction
aborts.
Upon
the
creation
of
B
,
it
gets
the
inde
x
of
proposer
as
an
identifier
,
namely
B
i
.
It
also
gets
a
unique
timestamp
called
ts
and
it
k
eeps
in
mind
the
situation
of
L
;
especially
the
order
of
the
last
committed
block
in
L
,
called
Lb
ts
.
Actually
,
e
v
ery
committed
B
represents
a
page
in
L
.
The
aborted
blocks
do
not
sho
w
up
in
L
,
b
ut
for
correctness
purpose,
we
consider
their
ts
.
Ha
ving
a
blockchain
of
4
nodes,
Figure
1
sho
ws
L
of
tw
o
committed
blocks
(in
the
form
of
B
i:ts
).
The
blocks
are
B
2
:
0
and
B
4
:
2
.
The
first
block
in
L
is
proposed
by
nodes
inde
x
ed
as
2,
and
its
ts
is
0.
The
node
2
also
proposes
another
block
with
ts
=
1
b
ut
it
is
aborted,
so
it
is
not
recorded
in
L
.
The
second
block
in
L
is
proposed
by
node
4,
with
ts
=
2.
This
means
L
has
blocks
with
the
timestamps
of
0
and
2,
b
ut
it
skips
the
block
of
ts
=
1
(because
it
is
aborted).
The
blocks
are
chained
in
L
using
hashing,
such
that
each
block
has
the
hash
of
the
pre
vious
one.
Thus,
L
is
unchangeable.
The
nodes
communicate
with
each
other
through
messages
e
xchange
o
v
er
a
netw
ork.
The
blockchain
allo
ws
broadcasting
messages
in
paral
lel
and
a
timeout
is
used
to
limit
the
delays.
The
timeout
is
specified
according
to
systems
specifi
cations.
Since
P
might
include
a
lar
ge
number
of
processors,
and
to
reduce
the
cost
of
v
oting
processes,
we
ha
v
e
a
subset
of
v
alidators
(v
oters),
called
V
,
where
V
P
.
The
size
of
V
(or
a
number
of
v
alidators)
v
aries
from
system
to
another
based
on
the
l
e
v
el
of
data
sensiti
vity
and
nodes
trustw
orthiness.
The
blockchain
may
include
some
netw
ork
issue,
f
ailure
nodes
or
Byzantine
ones.
A
Byzantine
node
is
the
one
that
misleads
the
system
or
e
v
en
lies
intentionally
[20,
21].
Netw
ork
issue,
f
ailure
nodes
or
no
sho
w
v
otes
are
considered
as
ne
g
ati
v
e
v
otes.
The
decision
on
block
B
is
tak
en
through
consensus,
which
finds
the
decision
of
the
majority
.
The
majority
could
be
an
y
percentage
between
51%
and
99%,
and
that
is
decided
based
on
the
system
sensiti
vity
[22,
23].
This
helps
to
reduce
the
influence
of
Byzantine
nodes.
In
our
algorithm,
we
test
node
twice
to
in
v
estig
ate
if
it
is
a
Byzantine
or
not,
and
to
tak
e
decision
such
as
e
xcluding
it.
In
our
algorithm,
we
use
v
oters
set
[]
to
represent
V
.
The
node
P
i
broadcasts
a
proposal
of
B
i
with
a
unique
ts
.
The
nodes
in
V
compute
the
transactions
of
B
i
and
v
ote
to
commit
or
abort
B
i
.
Then,
the
y
broadcast
the
v
otes
in
the
form
of
0
or
1.
The
recei
v
ed
v
otes
are
stored
in
v
otes[].
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
18,
No.
4,
August
2020
:
2224
–
2234
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
r
2227
Figure
1.
The
Ledger
L
Including
the
Committed
Block
B
2
:
0
and
B
4
:
2
Only
,
While
the
T
imestamps
of
the
Blocks
are
0
and
2.
The
T
imestamp
1
is
a
Unique
T
imestamp
for
an
Aborted
T
ransaction
B
2
:
1
.
4.
PR
OPOSED
ALGORITHM
In
the
be
ginning,
blockchain
algorithm
consists
of
three
phases
(as
sho
wn
in
Algorithm
1),
which
are:
(i)
proposal
phase;
(ii)
v
oting
phase;
(iii)
commit
phase.
First,
for
the
proposal
phase,
an
y
node
P
i
can
propose
and
create
a
block
B
i
at
an
y
moment.
No
w
,
it
sets
a
timeout
for
this
proposal
to
complete
within.
Since
some
blockchains
ha
v
e
a
lar
ge
number
of
nodes,
it
is
v
ery
costly
to
include
all
of
them
in
the
v
otes.
Ho
we
v
er
,
based
on
data
sensiti
vity
and
system
trustw
orthiness,
P
i
decides
the
siz
e
of
ho
w
man
y
nodes
should
v
ote
through
a
function
called
siz
e
v
oter
s
set
()
(that
will
be
e
xplained
in
details
later).
Then,
P
i
calls
v
oter
s
set
()
to
decides
which
nodes
are
going
to
v
ote
using
a
random-walk
algorithm
(that
will
be
e
xplained
in
details
later).
After
that,
P
i
finishes
proposing
phase
by
broadcasting
B
i
,
L
,
Lb
ts
and
ts
to
all
nodes
in
the
v
oter
s
set
[]
.
Since
the
proposal
phase
can
be
e
x
ecuted
by
more
than
one
node
in
parallel,
P
i
uses
a
unique
inte
ger
number
(
ts
)
to
sho
w
the
position
of
B
i
in
L
if
B
i
commits;
otherwise,
when
B
i
aborts
we
skip
its
ts
.
The
selection
of
a
unique
number
ts
can
be
e
x
ecuted
in
a
decentralized
manner
through
man
y
algorithms
such
as
Counting
Netw
ork
[24,
25].
This
step
ends
the
proposing
phase.
Second,
at
the
be
ginning
of
the
v
oting
phase,
e
v
er
y
node
in
v
oter
s
set
[]
v
alidates
B
i
and
v
otes
using
a
function
called
v
ote
()
.
In
v
ote
()
,
the
node
records
1
if
B
i
is
v
alid
or
0
if
it
is
not.
Actually
,
we
create
an
ar
r
a
y
v
otes
[]
in
corresponding
to
v
oter
s
set
[]
.
Ne
xt,
we
w
ait
for
some
ti
me
until
all
nodes
in
v
oter
s
set
[]
v
ote
or
the
timeout
finishes.
After
that,
if
timeout
finishes
while
some
v
otes
are
still
missing,
then
consider
all
missing
v
otes
as
v
otes
ag
ainst
B
i
using
a
function
called
no
show
v
otes
()
.
Indeed,
for
those
missing
v
otes,
we
record
0
in
v
otes
[]
.
T
o
end
the
v
ote
phase,
P
i
calls
mj
v
ote
O
k
()
,
checks
the
v
otes
of
the
majority
,
and
broadcasts
commit
or
abort
message.
Third,
the
commit
phase
is
the
critical
section
of
our
algorithm,
where
we
should
maintain
the
ts
0
s
of
committed
blocks
in
L
.
It
is
clear
that
using
timeout
all
blocks
are
e
v
entually
committed
or
aborted.
F
or
aborted
ones
we
do
nothing.
Ho
we
v
er
,
for
committed
ones,
all
nodes
must
connect
them
to
L
in
the
same
order;
otherwise,
nodes
w
ould
ha
v
e
dif
ferent
ledgers.
In
the
commit
phase,
if
B
i:ts
comes
directly
after
Lb
ts
in
L
,
then
B
i
commits.
F
or
e
xample,
if
the
ts
of
the
last
bl
ock
in
the
ledger
Lb
ts
=
5
,
and
B
i:ts
=
6
,
it
commits.
On
the
other
hand,
if
there
is
a
g
ap
between
B
i:ts
and
Lb
ts
,
then
B
i
has
to
w
ait
for
all
blocks
in-between
to
either
commit
or
abort,
then
B
i
commits.
F
or
e
xample,
if
the
ts
of
the
last
block
in
the
ledger
Lb
ts
=
5
,
and
B
i:ts
=
8
,
then
B
i
w
aits
for
commit
and
abort
broadcasted
messages
that
tells
about
the
blocks
of
timestamps
6
and
7.
Actually
,
if
it
recei
v
es
an
abort
messages
for
an
y
of
them;
it
does
nothing;
while
recei
ving
a
commit
message
for
an
y
of
them
means
it
has
to
connect
it
to
L
before
B
i
.
F
air
and
trustworthy:
Loc
k-fr
ee
enhanced
tendermint
bloc
kc
hain
...
(Basem
Assiri)
Evaluation Warning : The document was created with Spire.PDF for Python.
2228
r
ISSN:
1693-6930
As
mentioned
before,
the
consensus
decision
means
some
nodes
may
v
ote
ag
ainst
the
majority
.
This
happens
because
of
man
y
reasons,
such
as
(i)
nodes
ha
v
e
computation
and
processing
issue;
(ii)
being
a
Byzan-
tine
node
and
lay
intentionally;
(iii)
ha
ving
an
issue
with
memory
consistenc
y
[26].
F
or
e
xample,
ha
ving
a
memory
block
x
,
that
equals
to
50,
when
a
proposed
transaction
adds
100
to
x
,
it
becomes
150.
Since
blockchain
is
decentralized,
there
is
a
cop
y
of
x
in
all
nodes.
If
there
is
an
issue
of
updating
x
in
some
parts
of
the
system,
then
some
nodes
may
ha
v
e
x
6
=
50
(memory
is
not
consistent),
and
by
adding
100
to
x
,
the
result
w
ould
not
be
150,
so
it
v
otes
ag
ainst
the
transaction.
In
some
cases,
some
nodes
do
not
v
ote.
This
happens
because
of
man
y
reasons,
such
as
nodes
are
being
in
f
ailure;
or
ha
ving
communication
and
netw
ork
issues.
Our
algorithm
introduces
R
ound
2
(as
sho
wn
in
Algorithm
2),
to
in
v
estig
ate
these
issues.
This
helps
the
system
to
be
a
w
are
of
each
node
in
the
blockchain,
find
netw
ork
issue,
impro
v
e
the
consensus
ratio,
and
impro
v
e
the
system
trustw
orthiness.
In
the
be
ginning,
the
proposer
node
P
i
creates
a
ne
w
v
oters
set
v
oter
s
set
2[]
includes
all
nodes
that
v
oted
ag
ainst
in
R
ound
1
.
P
i
selects
one
node
P
j
from
those
nodes
that
v
oted
with
the
majority
in
R
ound
1
(
P
j
could
be
P
i
).
Then,
P
j
broadcasts
copies
of
memory
blocks
that
are
accessed
by
B
i
(called
B
i
.
access
set)
to
v
oter
s
set
2[]
.
After
that,
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
18,
No.
4,
August
2020
:
2224
–
2234
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
r
2229
nodes
in
v
oter
s
set
2[]
,
updates
their
memory
,
re-v
alidates
B
i
and
v
otes
ag
ain;
If
P
i
belongs
to
v
oter
s
set
2[]
,
it
does
the
same
thing.
It
w
aits
for
some
time
to
get
the
v
otes.
When
the
timeout
finishes,
there
are
three
possibilities:
(i)
some
nodes
v
ote
(with
a
majority
of
R
ound
1
)
correctly
,
which
means
the
y
had
a
memory
consistenc
y
issue
and
by
updating
their
memories
the
y
get
the
same
results
of
the
majority;
(ii)
some
nodes
do
not
v
ote,
which
means
the
y
ha
v
e
a
f
ailure
or
communication
and
netw
ork
issue
(
no
show
v
otes
f
ail
ed
())
;
(iii)
If
nodes
still
v
oting
ag
ainst
the
majority
of
R
ound
1
,
then
the
y
are
Byzantine.
4.1.
Corr
ectness
pr
oof
Our
algorithm
is
a
lock-free
algorithm
where
nodes
are
able
to
propose
and
v
ote
in
parallel.
Ho
we
v
er
,
block
committing
has
to
modify
the
ledger
,
so
it
should
be
serialized
and
ordered
according
to
timestamps.
In
the
correctness
analysis,
we
sho
w
that
our
algorithm
satisfies
the
Linearizability
which
is
a
correctness
property
that
v
alidates
concurrent
e
x
ecution.
In
linearizability
,
all
blocks
are
ordered
in
a
w
ay
that
matches
a
correct
sequential
e
x
ecution
[27,
28].
Let
H
be
a
parallel
e
x
ecution
history
of
all
blocks.
No
w
let
S
be
a
sequential
history
,
which
sho
ws
a
serialization
of
the
blocks
in
H
based
on
their
timestamps.
Indeed,
for
an
y
tw
o
blocks
B
i
and
B
j
,
if
i
<
j
,
then
B
i
<
s
B
j
.
Note
that
the
timestamp
for
e
v
ery
block
is
unique.
Lemma
4..1.
S
pr
eserves
the
r
eal
time
or
der
of
H
.
Pr
oof.
According
to
Algorithm
1,
for
a
block
B
i
the
timestamp
i
is
a
unique
one,
since
it
is
obtained
through
the
Counting
Netw
orks.
If
B
i
<
H
B
j
then,
i
<
j
.
Since
S
orders
blocks
in
the
timestamp
order
,
then
we
also
ha
v
e
that
B
i
<
S
B
j
,
as
needed.
Lemma
4..2.
Our
algorithm
is
wait-fr
ee
.
Pr
oof.
It
is
tri
vial
to
pro
v
e
that
our
algorithm
is
w
ait-free,
as
according
to
the
propose
phase
in
Algorithm
1,
e
v
ery
block
B
i
has
a
timeout
.
Clearly
when
the
time
equals
to
T
,
B
i
must
finish.
After
that,
the
v
oting
phase
continues
until
all
v
otes
arri
v
e,
or
the
timeout
finishes
(means
the
time
reaches
T
).
In
such
case,
the
missing
v
otes
are
considered
as
ne
g
ati
v
e
v
otes.
Then,
we
check
the
majority
of
v
otes
to
commit
or
abort.
Therefore,
e
v
ery
block
e
v
entually
finishes
within
a
specific
timeout;
and
the
ne
xt
block
e
v
entually
e
x
ecutes.
Lemma
4..3.
The
bloc
ks
in
H
ar
e
or
der
ed
based
on
their
timestamps.
Pr
oof.
Let
a
block
B
i
has
a
timestamp
ts
=
i
,
and
the
timestamp
of
the
last
block
in
the
ledger
Lb
ts
=
x
.
where
i
>
x
.
i.
If
B
i
passes
proposing
and
v
oting
phases
successful
ly
,
and
it
is
about
to
commit.
If
i
x
=
1
(which
means
i
is
ordered
directly
after
x
),
then
B
i
commits
and
connected
to
the
ledger
ne
xt
to
B
x
.
ii.
If
B
i
passes
proposing
and
v
oting
phases
suc
cessfully
,
and
it
is
about
to
commit.
If
i
x
6
=
1
,
which
means
there
is
at
least
one
block
with
a
timestamp
between
x
and
i
,
such
that
f
B
x
+1
;
:::;
B
i
1
g
(where
we
could
ha
v
e
B
x
+1
=
B
i
1
)
.
F
or
simplicity
let
say
there
is
only
one
block
B
j
between
B
x
and
B
i
,
where
x
<
j
<
i
.
Then
B
i
w
aits
until
either
B
j
aborts
(recei
ving
abort
messages);
or
B
j
commits
and
becomes
the
last
block
in
the
ledger
(
Lb
ts
=
j
).
Thus,
B
i
commits
since
i
j
=
1
.
Seeking
a
contradiction,
assume
that
B
i
commits
before
B
j
finishes
(commits/abort).
Then
based
on
the
commit
phase
in
Algorithm1;
either
i
x
=
1
,
which
is
impossible
since
x
<
j
<
i
;
or
B
i
recei
v
es
abort
messages
of
B
j
,
which
is
also
impossible
since
the
B
j
abortion
massage
means
that
B
j
already
finishes,
contradiction
.
In
general
case,
B
i
w
aits
until
either
some/all
of
blocks
f
B
x
+1
;
:::;
B
i
1
g
abort
or
commit.
Actually
,
B
i
kno
ws
aborted
blocks
by
recei
ving
abort
messages;
and
kno
ws
committed
blocks
by
follo
wing
the
changes
of
Lb
ts
.
Therefore
the
ledger
preserv
es
the
timestamp
order
.
iii.
If
B
i
f
ails
in
proposing
or
v
oting
phases,
Then
either
the
majority
v
ote
to
abort
it,
and
the
abortion
massages
get
sent;
otherwise
the
timeout
finishes
and
the
missing
v
otes
are
considered
as
ne
g
ati
v
e
ones,
so
it
also
seems
lik
e
the
majority
v
ote
to
abort
i
t.
Actually
,
in
both
cases
the
aborted
block
B
i
can
be
ordered
easily
in
the
right
position
in
H
,
since
it
does
not
modify
the
ledger
or
an
y
local
memory
.
Therefore,
in
all
cases
H
preserv
es
the
order
of
S
,
considering
all
blocks
in
H
,
and
from
Lemmas
4..1,
4..2
and
4..3,
we
obtain
the
follo
wing
theorem.
Theor
em
4..4.
Any
e
xecution
history
H
using
our
algorithm
is
linearizable
(corr
ect)
as
it
r
espects
the
times-
tamps
or
der
that
appear
s
in
S
.
F
air
and
trustworthy:
Loc
k-fr
ee
enhanced
tendermint
bloc
kc
hain
...
(Basem
Assiri)
Evaluation Warning : The document was created with Spire.PDF for Python.
2230
r
ISSN:
1693-6930
4.2.
Selection
of
the
v
alidator’
s
gr
oup
size
(v
ariable
set
of
v
alidators)
The
selection
of
v
alidators
(v
oters/
miners)
in
the
consensus
process
is
a
v
ery
important
part.
After
the
51%
miner’
s
v
alidation,
the
ne
w
blocks
can
be
added
to
the
chain.
Normally
in
the
block
v
erification
process,
all
miners
participate
in
the
consensus
process.
Selecting
all
miners
is
a
costly
process
in
terms
of
processing
and
ener
gy
.
But
sometimes
depending
upon
the
sensiti
vity
of
data
and
trustw
orthiness
of
miners,
it
is
possible
to
select
a
subset
of
miners
out
of
all
the
set
of
miners.
W
e
ha
v
e
proposed
a
ne
w
mechanism
for
the
selection
of
v
al-
idators.
The
subset
of
v
alidators
is
selected
based
on
the
sensiti
vity
of
data
and
the
trustw
orthiness
of
v
alidators.
If
the
data
is
highly
sensiti
v
e
and
trustw
orthiness
le
v
el
of
the
system
is
lo
w
then
we
need
high
numbers
of
v
al-
idators.
On
the
other
hand,
if
the
data
sensiti
vity
requirements
are
lo
w
and
the
trustw
orthiness
high
t
hen
we
need
a
relati
v
ely
small
number
of
v
alidators.
The
follo
wing
matrix
e
xplains
(T
able
1)
the
relationship
between
the
three
actors
(Data
sensiti
vity
(di),
trustw
orthiness
(ti)
and
v
alidators
(vi))
for
the
maximum
size
of
the
subset
of
v
alidators.
T
able
1.
Relationship
between
data
sensiti
vity
,
trustw
orthiness
and
the
size
of
the
subset
of
v
alidators
Data
sensiti
vity
(di)
T
rustw
orthiness
(ti)
V
alidators
(vi)
High
High
50%
High
Lo
w
75%
Lo
w
High
25%
Lo
w
Lo
w
50%
4.3.
Selection
of
v
alidators
In
the
blockchain,
a
ne
w
block
is
appended
to
the
chain
after
the
agreement
of
v
alidators.
After
we
discuss
the
size
of
v
al
idators
set,
no
w
we
focus
one
the
v
alidator
selection.
The
selection
of
v
alidators
v
aries
according
to
types
of
blockchains.
F
or
e
xample,
in
T
endermint
blockchain
protocol,
the
subset
of
v
alidators
is
selected
deterministically
using
the
current
history
of
blockchain.
The
subset
of
v
alidators
only
changes
when
ne
w
blocks
are
added
to
the
chain.
In
this
paper
,
we
ha
v
e
proposed
a
no
v
el
v
alidator
selection
mechanism.
In
the
proposed
mechanism,
we
ha
v
e
emplo
yed
a
random
w
alk
for
the
selection
of
v
alidators.
When
a
ne
w
block
B
is
proposed
by
a
proposer
,
it
will
select
a
subset
of
v
alidators
through
a
random
w
alk.
The
proposed
selection
mechanism
has
fe
w
unique
features,
i.e.,
the
subset
of
v
alidators
are
selected
non-deterministically
and
randomly
.
F
or
e
v
ery
ne
w
proposed
block,
a
ne
w
subset
of
v
alidators
will
be
selected.
The
length
of
the
random
w
alk
will
be
equal
to
the
size
of
the
subset
of
the
v
alidator
(e
xplained
in
the
pre
vious
section).
The
proposer
node
will
select
a
v
alidator
ra
nd
om
ly
from
a
set
of
v
alidator
and
forw
ard
the
ne
wly
created
block
to
the
selected
v
alidator
.
The
selected
v
alidator
will
select
another
v
alidator
from
the
list
and
forw
ard
the
ne
w
block
recei
v
ed
from
the
proposer
node.
The
v
alidator
selection
process
will
continue
until
the
required
numbers
of
v
alidators
ha
v
e
not
being
selected
(selected
v
alidators
=
=
vi).
Due
to
the
pure
nature
of
the
random
w
alk,
we
can
restrict
the
random
w
alk
to
not
the
selected
the
already
passed
v
alidators
(i.e.,
we
will
e
xclude
them
from
the
group
of
v
alidators
once
selected).
Figure
2
sho
ws
the
selection
mechanism
of
v
alidators
using
random
w
alk.
5.
DISCUSSION
5.1.
T
ransaction’
s
v
alidation
Clearly
,
in
blockchain
there
are
tw
o
le
v
els
of
v
alidation
and
correctness
check,
which
are
the
v
al-
idation
of
trans
actions
and
the
v
alidation
of
blocks
(of
transactions).
This
section
focus
es
on
transactions
v
alidation.
In
f
act,
when
an
y
node
creates
a
ne
w
transaction,
nodes
(miners)
pick
ed
it
up
to
check
the
cor
-
rectness
of
the
transaction,
v
alidity
,
le
g
ality
and
its
output
[27,
28].
F
or
e
xample,
a
bank
account
x
belongs
to
user
1
,
and
x
contains
100$
.
No
w
user
1
withdra
ws
10$
form
x
,
so
the
v
alue
of
x
becomes
90$
.
This
is
a
v
alid
and
le
g
al
transaction.
After
that,
let
user
1
withdra
ws
100$
,
then
this
is
in
v
alid
transaction
since
x
does
not
ha
v
e
suf
ficient
fund
to
e
x
ecut
e
the
transaction.
Also,
if
x
contains
90$
and
user
1
withdra
ws
20$
,
b
ut
for
some
reasons
x
becomes
50$
,
then
it
is
in
v
alid
transaction.
This
w
ay
,
nodes
chec
k
the
v
al
idity
of
transactions.
If
the
transaction
is
v
alid
(correct),
it
is
stored
in
the
node’
s
block,
otherwise
it
is
ignored.
The
node
continues
the
transactions’
v
alidation
process
and
place
them
in
its
o
wn
block
until
it
reaches
the
block
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
18,
No.
4,
August
2020
:
2224
–
2234
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
r
2231
capacity
,
then
it
proposes
the
block
to
the
v
alidators
for
another
v
alidation
process.
Moreo
v
er
,
it
is
impor
-
tant
to
notes
that
all
nodes
w
ork
in
isolation,
so
each
one
b
uild
its
o
wn
block
re
g
ardless
the
others.
This
allo
ws
dif
ferent
nodes
to
v
alidate
the
same
transaction,
so
one
transaction
may
appear
in
more
than
one
block.
Figure
2.
Selection
mechanism
of
v
alidators
using
random
w
alk
5.2.
Block’
s
v
alidation
This
section
focuses
on
the
block
v
alidation
process.
Upon
the
creation
of
a
ne
w
block
of
transac
tions,
the
block
should
hash
it
o
wn
content
(transactions)
and
produce
a
fix
ed
size
hash
number
,
with
spec
ific
criteria.
This
guarantees
that
no
one
w
ould
change
the
cont
ent
of
the
block,
as
an
y
change
to
the
block
will
change
the
hash
number
.
Blockchain
uses
PoW
to
produce
the
hash
number
,
where
the
proposer
node
should
solv
e
a
mathematical
crypto-puzzle
[11]
(it
can
use
dif
ferent
techniques
such
as
PoS).
The
hash
of
the
last
block
in
the
ledger
must
be
attached
as
well.
The
proposer
node
also
includes
its
digital
signature
to
confirm
that
the
ne
w
block
is
proposed
by
an
authentic
and
authorized
node.
When
node
proposes
a
block
to
the
v
alidators,
the
v
alidators
check
the
block
and
v
ote
to
add
it
to
the
ledger
(using
consensus).
Actually
the
v
alidators
v
alidate
four
items
as
follo
ws:
•
V
alidators
v
alidate
the
signature
of
the
proposer
node
to
v
erify
that
the
block
is
created
by
a
le
gitimate
node.
•
V
alidators
v
alidate
the
PoW
to
v
erify
that
it
matches
the
system
cri
teria
and
it
matches
the
content
of
the
block
(which
means
the
content
of
the
block
has
not
been
changed).
•
V
alidators
v
alidate
the
hash
of
the
pre
vious
block
to
fix
the
order
of
the
block
in
the
ledger
.
•
V
alidators
v
alidate
the
content
of
the
block
to
pre
v
ent
the
conflicts
and
ille
g
al
transactions.
No
w
,
blockchain
uses
consensus
to
v
alidate
the
content
of
the
block
to
pre
v
ent
the
conflicts
and
i
lle
g
al
transactions.
The
consensus
decision
influences
the
order
of
the
blocks
that
are
added
to
the
ledger
.
Figure
3
(a)
sho
ws
the
status
of
memories
for
four
bank
accounts
before
the
block
v
alidation
and
e
x
ecution.
Figure
3
(b)
sho
ws
three
blocks
where
e
v
ery
block
has
tw
o
transactions.
In
Block1,
T
x
1
withdra
ws
10$
from
acc
1
,
so
it
becomes
90$
.
Then,
T
x
2
withdra
ws
100$
from
acc
2
,
so
acc
2
=
100$
.
In
Block2,
T
x
3
withdra
ws
50$
from
acc
3
,
so
acc
3
=
450$
.
Then,
T
x
4
deposits
100$
to
acc
4
,
so
acc
4
=
110$
.
Block3,
also
has
T
x
1
and
T
x
5
where
it
deposits
30$
to
acc
4
,
so
acc
4
=
40$
.
Thus,
Block3
conflicts
with
Block1
and
Block2.
Indeed
Block1
and
Block3
both
include
T
x
1
,
which
means
if
we
allo
ws
to
both
of
them
to
commit,
then
T
x
1
will
e
x
ecute
twice
and
double
the
withdra
w
operations
on
acc
1
,
which
is
not
acceptabl
e.
Moreo
v
er
,
Block3
conflicts
with
Block2
since
T
x
4
and
T
x
5
both
of
them
e
x
ecutes
operations
on
acc
4
,
and
both
of
them
are
not
a
w
are
of
each
other
.
If
both
of
them
commit,
then
the
amount
of
acc
4
will
be
either
110$
or
40$
(according
to
the
committing
order),
where
the
right
v
alue
is
the
accumulati
v
e
of
both
which
is
140$
.
Thus
,
if
by
consensus,
Block1
and
Block2
commit
first
(the
y
can
commit
in
an
y
order
as
there
is
no
dependenc
y
between
them),
Block3
must
be
aborted.
On
the
other
hand,
if
by
consensus,
Block3
commits
first,
then
F
air
and
trustworthy:
Loc
k-fr
ee
enhanced
tendermint
bloc
kc
hain
...
(Basem
Assiri)
Evaluation Warning : The document was created with Spire.PDF for Python.
2232
r
ISSN:
1693-6930
Block1
and
Block2
must
be
aborted.
The
follo
wing
section
focuses
on
ho
w
to
order
blocks
in
the
ledger
.
Figure
3.
(a)
Sho
ws
the
status
of
four
bank
accounts;
(b)
Sho
ws
three
blocks
where
e
v
ery
block
includes
tw
o
transactions
5.3.
Corr
ectness
In
thi
s
paper
,
we
focus
on
the
correctness
of
blocks
rather
than
ar
guing
about
the
correctness
of
trans-
actions
themselv
es.
The
correctness
of
transactions
is
check
ed
by
miners
before
the
y
propose
the
blocks.
T
o
v
alidate
the
transactions,
nodes
may
use
an
y
appro
v
ed
correctness
prosperity
such
as
opacity
or
Linearizability
[27,
28].
Indeed,
man
y
researchers
restrict
the
parallelism
of
blockchain
to
guarantee
correctness
[13,
14].
Some
algorithms
use
locks
to
serialize
blocks
e
x
ecution
or
pipel
ining
them.
This
increases
the
e
x
ecution
time
and
may
result
in
some
lock’
s
issues
such
as
deadlock
and
starv
ation.
Ho
we
v
er
,
our
algorithm
is
a
lock-free
algorithm
where
nodes
are
able
to
propose
and
v
ot
e
in
parallel.
In
f
act,
proposing
and
v
oting
run
in
temporary
memory
and
do
not
require
maintaining
the
ledger
.
On
the
other
hand,
the
critical
section
of
our
algorithm
is
when
nodes
modify
the
ledger
,
which
is
the
moment
of
commit.
W
e
propose
a
timestamped
based
algorithm
where
e
v
ery
block
has
a
unique
timestamp
ts
[29].
This
ts
tells
wither
the
block
should
commit
or
w
ait.
Ac-
tually
,
blocks
can
be
aborted
directly
(based
on
consensus),
since
the
aborted
blocks
do
not
update
the
ledger
.
Committed
blocks
must
maintain
the
ledger
with
respect
to
their
ts
,
so
e
v
ery
block
has
to
w
ait
for
al
l
blocks
of
timestamps
smaller
than
its
o
wn.
5.4.
Consensus
The
v
alidation
of
blocks
is
conducted
via
consensus.
Actually
,
the
consensus
is
considered
as
a
weak
correctness
prosperity
,
it
is
indeed
a
f
ault
tolerance
property
[20,
21,
30].
This
means
consensus
is
able
to
w
ork
with
some
f
aulty
results
(v
otes).
F
or
e
xample,
the
block
can
commit
e
v
en
with
about
%49
ne
g
ati
v
e
v
otes.
T
o
the
best
of
our
kno
wledge,
blockchain
algorithms
do
not
consider
the
weaknes
s
of
consensus
itself.
F
or
e
xample,
with
some
financial
operations,
the
decision
has
to
be
black
or
white
from
all
v
alidators,
while
the
consensus
allo
ws
for
some
gray
area.
In
our
algori
thm,
we
introduce
some
techniques
to
support
the
consensus
decision.
First,
we
select
the
number
of
v
alidators
based
on
the
sensiti
vity
of
the
data.
Second,
we
decide
the
consensus
percentage
based
on
both
data
sensit
i
vity
and
trustw
orthiness.
F
or
e
xample,
with
our
criteria,
for
some
critical
matters,
the
consensus
may
reach
99%,
or
abort.
Third,
we
e
v
aluate
the
trustw
orthiness
of
the
nodes
based
on
their
history
of
v
otes.
R
ound
2
in
our
algorithm
in
v
estig
ates
the
reasons
for
ha
ving
v
oting
conflicts.
W
e
in
v
estig
ate
the
data
consistenc
y
and
we
gi
v
e
another
chance
for
the
f
aulty
v
alidators
to
adjust
themselv
es.
This
impro
v
es
the
data
cons
istenc
y
in
the
blockchain
and
increases
the
ratio
of
consensus
as
some
nodes
may
be
able
to
v
ote
correctly
(with
the
majority)
in
the
second
round.
Ho
we
v
er
,
for
those
nodes
that
do
TELK
OMNIKA
T
elecommun
Comput
El
Control,
V
ol.
18,
No.
4,
August
2020
:
2224
–
2234
Evaluation Warning : The document was created with Spire.PDF for Python.
TELK
OMNIKA
T
elecommun
Comput
El
Control
r
2233
not
v
ote
because
of
f
ailure
or
netw
ork
issue.
It
is
important
to
tak
e
some
decisions
to
fix
the
issues
or
mark
them
to
be
a
v
oided
later
on.
Moreo
v
er
,
the
y
should
be
treated
ne
g
ati
v
ely
in
the
re
w
ards
distrib
utions.
F
or
Byzantine
nodes
that
insist
to
mislead
the
consensus,
it
is
important
to
classify
them
under
the
class
of
lo
w
trustw
orth
y
nodes;
which
decreases
their
chance
to
be
s
elected
in
the
v
oters
set
and
consequently
decreases
their
re
w
ards.
Otherwise,
blockchain
supposes
to
e
xclude
them.
All
mention
steps
are
supporti
v
e
techniques
to
enhance
the
consensus
decision
as
a
correctness
property
.
5.5.
W
ait-fr
eedom
Let
us
start
with
a
proposed
scenario,
when
one
block
B
3
with
ts
=
3
,
about
to
commit
b
ut
w
aits
for
another
block
B
2
with
ts
=
2
.
Ho
we
v
er
,
B
2
passes
the
proposal
phase
and
w
aits
for
v
alidators
to
decide
to
weather
it
commits
or
not.
If
at
least
one
v
alidator
has
an
issue
and
does
not
respond,
then
B
2
,
B
3
,
and
all
the
follo
wing
blocks
w
ould
w
ait
for
non-deterministic
time
to
commit.
T
o
solv
e
such
a
problem
our
algorithm
maintains
the
w
ait-freedom
property
.
W
ait-freed
means
that
all
blocks
are
able
to
complete
within
a
finite
number
of
steps
(time)
[31].
Indeed,
we
implement
the
w
ait-freedom
property
using
timeout;
it
starts
directly
after
block
creation
and
finishes
within
a
deterministic
time.
If
it
finishes
before
the
block
completes,
it
ignores
the
pending
v
otes
and
considers
them
as
ne
g
ati
v
es.
Then
tak
es
the
decision
of
the
majority
to
commit
or
abort.
This
w
ay
blocks
can
still
commit
e
v
en
after
the
timeout
decision.
F
or
e
xample,
when
the
v
oters
set
contains
10
nodes,
8
of
them
v
ote
to
commit
the
block,
1
node
v
otes
to
abort
and
1
node
delays
the
v
ote;
then
we
consider
the
v
ote
of
the
one
with
delay
as
a
ne
g
ati
v
e
v
ote,
which
mak
es
the
ratio
8
to
2;
so
it
commits.
Thus,
all
blocks
are
e
v
entually
commit
ted
or
aborted,
which
means
no
one
stays
in
the
e
x
ecution
fore
v
er
and
no
o
ne
w
ait
for
non-deterministic
time
to
e
x
ecute.
6.
CONCLUSION
Blockchain
technology
ha
s
the
potential
to
transform
the
digitization
of
industries
for
more
ef
ficien-
cies.
In
this
paper
we
analyzed
the
T
endermint
blockchain
protocol
and
proposed
v
arious
enhancements
to
impro
v
e
correctness,
f
airness,
parallelism,
performance,
progressi
v
eness
and
trustw
orthiness.
REFERENCES
[1]
S.
Nakamoto
and
A.
Bitcoin,
“
A
peer
-to-peer
electronic
cash
system,
”
Bitcoin.–URL:
https://bitcoin.
or
g/bitcoin.
pdf
,
2008.
[2]
R.
Cohen,
“Global
bitcoin
computing
po
wer
no
w
256
times
f
aster
than
top
500
supercomputers,
com-
bined,
”
F
orbes,
No
vember
,
2013.
[3]
S.
Hakak,
W
.
Z.
Khan,
G.
A.
Gil
k
a
r
,
M.
Imran,
and
N.
Guizani,
“Securing
smart
ci
ties
through
blockchain
technology:
Architecture,
requirements,
and
challenges,
”
IEEE
Network
,
v
ol.
34,
no.
1,
pp.
8–14,
2020.
[4]
N.
Herbaut
and
N.
Ne
gru,
“
A
model
for
collaborati
v
e
blockchain-based
video
deli
v
ery
relying
on
ad-
v
anced
netw
ork
services
chains,
”
IEEE
Communications
Ma
gazine
,
v
ol.
55,
no.
9,
pp.
70–76,
2017.
[5]
Q.
L
yu,
Y
.
Qi,
X.
Zhang,
H.
Liu,
Q.
W
ang,
and
N.
Zheng,
“Sbac:
A
secure
blockchain-based
access
control
frame
w
ork
for
information-centric
netw
orking,
”
J
ournal
of
Network
and
Computer
Applications
,
v
ol.
149,
p.
102444,
2020.
[6]
Z.
Zheng,
S.
Xie,
H.-N.
Dai,
W
.
Chen,
X.
Chen,
J.
W
eng,
and
M.
Imran,
“
An
o
v
ervie
w
on
smart
contracts:
Challenges,
adv
ances
and
platforms,
”
Futur
e
Gener
ation
Computer
Systems
,
v
ol.
105,
pp.
475–491,
2020.
[7]
W
.
Khan,
M.
Rehman,
H.
Zangoti,
M.
Afzal,
N.
Armi,
and
K.
Salah,
“Industrial
internet
of
things:
Recent
adv
ances,
enabling
technologies
and
open
challenges,
”
Computer
s
&
Electrical
Engineering
,
v
ol.
81,
p.
106522,
2020.
[8]
S.
Gao,
G.
Piao,
J.
Zhu,
X.
Ma,
and
J.
Ma,
“T
rustaccess:
A
trustw
orth
y
secure
cipherte
xt-polic
y
and
attrib
ute
hiding
access
control
scheme
based
on
blockchain,
”
IEEE
T
r
ansactions
on
V
ehicular
T
ec
hnolo
gy
,
2020.
[9]
S.
Moin,
A.
Karim,
Z.
Safdar
,
K.
Safdar
,
E.
Ahmed,
and
M.
Imran,
“Securing
iots
in
distrib
uted
blockchain:
Analysi
s,
requirements
and
open
issues,
”
Futur
e
Gener
ation
Computer
Systems
,
v
ol.
100,
pp.
325–343,
2019.
[10]
W
.
Z.
Khan,
E.
Ahmed,
S.
Hakak,
I.
Y
aqoob,
and
A.
Ahmed,
“Edge
computing:
A
surv
e
y
,
”
Futur
e
Gener
ation
Computer
Systems
,
v
ol.
97,
pp.
219–235,
2019.
F
air
and
trustworthy:
Loc
k-fr
ee
enhanced
tendermint
bloc
kc
hain
...
(Basem
Assiri)
Evaluation Warning : The document was created with Spire.PDF for Python.