Candidate:
Chunyu
Mao
Title:
Scaling
Permissioned
Blockchains
via
Sharding
Date:
December
8,
2022
Time:
3:00
PM
Place:
REMOTE
ATTENDANCE
Supervisor(s):
Golab,
Wojciech
Abstract:
This
thesis
scales
permissioned
blockchains
via
sharding
techniques.
Traditional
distributed
systems,
such
as
those
used
in
banking
and
real
estate,
require
a
trusted
third
party
to
operate
and
maintain
them,
which
is
highly
dependent
on
the
reliability
of
the
operator.
Since
Bitcoin
was
introduced
by
Nakamoto
in
2008,
blockchain
technology
has
been
considered
as
a
promising
solution
to
the
trust
issue
raised
by
the
traditional
centralized
approach.
Blockchain
is
now
used
by
most
cryptocurrencies
and
has
meaningful
applications
in
other
areas,
such
as
logistics
and
supply
chain
management.
However,
scalability
remains
a
major
limitation.
Various
techniques
are
being
investigated
to
tackle
the
scalability
issue.
Sharding
is
an
intuitive
approach
to
improve
the
scalability
of
blockchain
systems.
First
of
all,
two
techniques
are
examined
for
interleaving
the
shards
of
permissioned
blockchains,
which
are
referred
to
as
strong
temporal
coupling
and
weak
temporal
coupling.
The
analysis
and
experiment
results
show
that
strong
coupling
loses
performance
when
different
shards
grow
unevenly,
but
outperforms
weak
coupling
in
a
wide-area
environment
due
to
its
inherent
efficiency.
Weak
coupling,
in
contrast,
deals
naturally
with
load
imbalance
across
shards
and
in
fact
tolerates
shard
failures
without
any
additional
effort,
but
loses
performance
when
running
on
a
high-latency
network
due
to
the
additional
coordination
performed.
Second,
we
propose
Antipaxos,
a
leaderless
consensus
protocol
that
reaches
agreement
on
multiple
proposals
with
a
fast
path
solution
in
the
failure-free
case,
and
falls
back
on
a
slow
path
to
handle
other
cases.
A
new
agreement
problem,
termed
as
$k$-\emph{Interactive
Consistency}
is
formalized
first.
Then,
two
algorithms
to
solve
this
problem
are
proposed
under
the
crash
failure
model
and
Byzantine
failure
model,
respectively.
We
prove
the
safety
and
liveness
of
the
proposed
algorithms,
and
present
an
experimental
evaluation
of
their
performance
in
the
Amazon
cloud.
Both
the
crash-tolerant
and
Byzantine-tolerant
designs
reach
agreement
on
$n$
batches
of
proposals
with
$\Theta(n^2)$
messages.
This
leads
to
the
linear
complexity
of
each
batch
in
one
consensus
cycle,
rather
than
a
single
batch
of
proposals
per
cycle
in
conventional
solutions.
The
experiments
show
that
our
algorithms
achieve
not
only
lower
execution
latency
but
also
higher
peak
throughput
in
the
failure-free
case
when
deployed
in
a
geo-distributed
environment.
Lastly,
we
introduce
a
full
sharding
protocol,
Geochain,
for
permissioned
blockchains.
The
transaction
latency
is
minimized
by
clustering
participants
using
their
geographical
properties,
locality.
In
addition,
the
locality
is
also
being
used
to
decide
the
transaction
placement
which
results
in
a
low
ratio
of
cross-shard
transactions
for
applications,
such
as
everyday
banking,
retail
payments,
and
electric
vehicle
charging.
We
also
propose
a
client-driven
efficient
mechanism
to
handle
cross-shard
transactions
and
present
an
analysis.
This
enables
clients
to
manage
their
assets
across
different
shards
directly.
A
prototype
is
implemented
on
top
of
Hyperlegder
Fabric
v2.3
and
evaluated
on
Amazon
EC2.
The
experiments
show
that
our
protocol
doubles
the
peak
throughput,
even
with
a
high
ratio
of
cross-shard
transactions,
while
minimizing
the
transaction
latency.
Thursday, December 8, 2022 3:00 pm
-
3:00 pm
EST (GMT -05:00)