hi hi my name's Dominic once I founder
of just a research project called
affinity which seeks to advance
blockchain technology with a particular
focus on scalability in the process of
doing that we look at many different
types of distributed algorithm and in
particular many different types of
consensus algorithm and in the crypto
space we often spend a lot of time
talking about block chains and block
chain like consensus systems and think
the purpose of my talk is to introduce
another form of consensus which has been
around for longer Luna's byzantium fault
tolerant consensus which is based on
message passing so I'm going to try and
do this in 20 minutes which is kind of
challenging but I want to just give it a
give you a fear of some of the issues
involved and what these kind of
consensus protocols look like so first
of all quickly it's worth just asking
the question we already have block
chains so so why bother ways complex can
concerns as protocols and the answer is
they're useful for creating scale-out
crips alleges that's crypt alleges that
increase their transaction throughput as
more nodes join the network so you know
the objective of the research effort is
to transport the creation of sort of
limitless to centralize clouds that can
be used in the case of an open
decentralized virtual machine like
etherium to run you know gmail goober
Facebook Twitter that kind of thing
internet of things
services layer and so on and the most of
the three different kinds of
decentralized system that I'm interested
in one is the open decentralized systems
like Bitcoin and athyrium also federated
decentralized systems as of the type
that banks are currently creating for
settlement of clearing and also think
actually the centralization is a
completely new computing paradigm and
we're going to see it within the
enterprise so people are going to create
to centralize databases which highly
fault tolerant because you know that's
where the design they easy to administer
because they're symmetric every server
involved has a similar role there is no
kind of master slave arrangement like
you see in mysql databases or something
like that and once these decentralized
networks can scale multi-party
computation can be introduced to secure
the data inside them so you probably all
heard about the hacks that target in
America and the Office of Personnel
Management I think in the UK Talk Talk
has just lost a lot of customer data I
think we're going to see you know
enterprise decentralized databases where
the data is distributed across a large
number of different servers and you can
only access it by running running
authorized requests which access the
days are in a certain way you can ask
when you can run a query against the day
to say but you can't retrieve all the
data from the database so you know with
with a and a decentralized enterprise
database which is using NPC all of these
kind of hacks that you hear about would
their laundry possible so
I think the more specifically for some
lesser sister probably in the long term
I think that the scale out kind of
systems will use a number of different
kinds of consensus system in their
overall network architecture and this is
an architecture that I pursue and you
can see at the very top level them it's
got several layers you've got a master
consensus layer you got a scalable
validation there and you get a storage
layer and at the very top level it's
going to block chain like it's going to
watching it may not use proof-of-work
could use something like Casper or it
could use something else altogether but
that's only one component of the overall
network we also have this validation
layer and we have a storage layer and
these green dots these represents
traditional consensus processes that are
being run because for various reasons
it's very difficult to create strongly
consistent master chain that is if
you're very large number of nodes
imagine if you had a million nodes in a
distributed virtual machine be very
difficult to have strong consistency at
that level so if if the master chain can
reorganize itself and drive other
changes lower low down we don't want to
have weekly consistent to be you know
composing weekly consistent consensus
process is further down so you know
consensus really does have a really
important role to play in creating these
kinds of network and in this diagram
here these green dots are in fact
traditional consensus instances soon
what is the sort of xan team consensus
challenge very basically you've got a
bunch of nodes that are connected by
some kind of network here are cool man
processes so I'll try and use that non
closure and then you'll have a value
that they want to propose and they've
got to agree on this value and the
important point is that some of these
most of these nodes are correct which
means they follow the protocol but some
of them are faulty and that means they
can behave completely arbitrarily which
is what is meant by presenting so what
is Byzantium consensus so I it's the
easiest way to think about it is as a
game the correct processes run this
protocol and try and reach agreement by
sending and receiving messages meanwhile
the faulting processes which are
controlled by anniversary try to either
prevent consensus being reached or to
make correct nodes decide invalid values
that is think they've reached agreement
on something that they happen so on
these 1402 processes what can they do
their Byzantine and what that means is
they can adopt arbitrary tactics they
can just decide to crash and fail they
can corrupt data and messages they can
subtly subvert the communications
protocol and they can coordinate their
their actions so they really can do
anything at all depending on the model
that's being used the adversary can also
do things like controlling the control
the scheduling and messages right it can
impact the network he may have full
information about process States and he
can during the consensus protocol you
can corrupt correct nodes at will so
just to clarify what consensus is the
first of all consensus is agreement here
we have
network of just four nodes the green
ones are correct and the red one is
faulty and the green cracks nodes all
start off wanting to propose different
values and after consensus is run
they've all agreed on the same value XYZ
and that's I guess pretty intuitive
agreement source of validity noting in
this case means that if all the nodes
start off proposing the same value then
they decide that same value and there's
two forms of this actually there's
there's week validity which requires
that every single and process starts off
proposing the same value and the strong
validity which requires that only the
correct processes need stop to start off
proposing the same value anyway in this
diagram here all of the processes have
started started off proposing and mo and
after consensus all of the correct
processes have decided an NM o of course
the faulty process has come up with XYZ
it could be anything it's faulty it can
do what it likes can behave arbitrarily
so this is um an important one consensus
is also termination or what that means
is that the before contentious protocol
that it would eventually terminate it
can't go on forever that's a valid
consensus protocol has has to terminate
so as you probably guessed listening so
far as there are actually many different
models that these consensus
protocols are designed to work for and
so here some of the main ones first one
is network behavior
and generally speaking consensus
protocols are divided into synchronous
consensus protocols and partly
synchronous consensus protocols and
asynchronous protocols and in
synchronous protocols the network is
assumed to deliver messages within some
bounded predictable time and in
asynchronous networks there are no
timing assumptions whatsoever so and
this actually is kind of realistic for
the internet right you can get arbitrary
partitions a correct node can be deduced
right and the second one of course is
the fault type so this is a pretty
oversimplification but the pretty heaven
consensus algorithm called pack sauce
anyone it so use it was use it's used in
like Google chubby and thanks possibly
zookeeper and things like that so it's a
consensus algorithm where the only kinds
of faults that are handled a crash fault
so it can deal with processes crashing
but it can't deal with them behaving
arbitrarily and of course the wider set
of fault fault types is presenting where
processes can behave up too early so if
there's anything just to take from this
this useful it's that obviously if a
consensus protocol is byzantium fault
tolerant it's resistant to a far greater
number of faults right I would you folds
of fact and works within a synchronous
network that's better because it's not
vulnerable to you know correct process
being dido store something or that or
the network just behaving strangely
so just to talk about challenges but
more I think one of the reasons these
kind of protocols are complex is that in
fact of course the state of the network
is unknowable and it's easy to forget
that because you always see a network
diagram which shows lots of connected
nodes and some of them are correct and
some of them are faulty but it but in
actual fact nobody can know what the
state of the network is right you can
only make inferences about the current
state of the network based upon the
messages you receive and that's equally
true actually for these kind of
consensus protocols as it is from
blockchain based consensus protocols
you've got no way of knowing what be the
overall state of the network is you can
only make inferences about it based upon
the messages you receive now you can
send messages out to ask questions and
you may or may not get answers but you
can only make imprint inferences the
network is a black box another big
challenge is equivocation by faulty
nodes and again this applies to
protocols like Casper Ola this is again
as assuming a traditional consensus
protocol and equivocation simply means
that faulty nodes can send two different
versions of a message when there any men
or men ascend one so in this case
process one is is faulty and it's
telling process to that it's voting ABC
and it's telling process through that
it's voting NO and equivocation is a
surprisingly powerful tool for
anniversary to use can kredel kinds of
problems and as a result that comes from
this which is that typically to reach
consensus when you receive a message
from a process you need to echo it to
all the other processes to make sure
that that it hasn't been equivocating
and this kind of leads to quadratic
message complexity which basically means
that as the number of processes
cooperating in consensus increases the
number of messages they send increases
with the square of the number of
processes and that's the reason why
Satoshi creatives the proof of work
blockchain because it doesn't have this
problem ok has a different works in a
different way that people try and solve
puzzles and whoever solves the puzzle
gets to cast a deciding vote right and
you don't get strong consistency you get
a sort of it eventual consistency as
them as the chain gets longer and block
gets buried deeper and deeper it gets
more and more likely to be permanent so
that's the limitation of this kind of
protocols the number of messages they
have to pass increases with the the
square of the number of processes
involved and so consequently they tend
to be used within a larger protocol as
we look sat at the beginning so here's
another challenge this is network
asynchrony and this is actually probably
the most profound challenge of thing
which is there's no way of knowing if
the network can pave it in a synchronous
way why you haven't received a message
so in this case he too is expecting a
message from p1 ok and it hasn't
received a message from p1 ok so what is
p2 mother think does it continue waiting
for the message from p1 so there's a
system called ripple she probably all
aware of and they had a consensus
protocol which didn't handle a synchrony
correctly and it was adopted by another
cryptic article Stella and it was
absolutely plain from the way they
described the the protocol that I had
this issue of the synchrony that it
would just make an assumption that it
hadn't got a message because the sender
had failed ok and as a consequence they
had a day out of four so it's very easy
to just imagine what
haven't received a message the sending
us to fails therefore I'm going to
proceed with the messages i have and
assume that some some part of the
network's faulty but it can lead to
problems so of course you know an
adversary realizing that the receiver
doesn't know what to do can use this as
a tool you can decide to withhold
messages right and there is a kind of
prefer issue that comes from that so
what is the you know the maximum number
of faulty processes that these kind of
consensus protocols can handle and
there's no easy way to think about it
perhaps this is the easiest there's a
thing called the Byzantine poorer and a
Byzantium quorum is a subset of nodes so
chosen that if two different forums are
selected they will always intersect in
at least one correct node and this means
that you can chain operations together
and produce some kind of result or
inference and so we can see here there's
seven here are seven notes and these two
quorums intersect there are two forums
here of five nodes and you can see they
both intersect in one node even though
both of the quorums have selected the
two faulty nodes and anyway this area
there's a general result which is the
the the must be less than the number of
faulty nodes must be less than a third
right so less than a third of the
processes participating in the consensus
algorithm must be faulty for the thing
to be able to reach a correct result and
the issue there is that one of the one
of the issues one of them other things
were thinking about is that if we cannot
wait for all of the messages so let's
say you know they're there n processes
and the consensus protocol in this case
there are seven and we know up to two of
them can be faulty right once we've
received five messages right five
messages do we wait and see if we can
receive another two right there's evil 7
we can't write because the remaining two
messages we haven't received may be
coming from faulty nodes and the faulty
nodes may just decide not to send these
messages to make to make us wait forever
right so these kind of protocols need to
proceed when they've received two F plus
one of the messages which has another
side effect which is that of course it
may be that the F messages that we
didn't wait for in this case to two
messages we didn't wait for we're
actually from correct processes and
we've received two messages from faulty
processes in which which means that we
can only be sure f plus 1 messages from
those who have collected from correct
processes and that's why it's kind of
complex so I'm at a time so you're saved
I was going to try and walk you through
in a synchronous protocol but
i'm at a time but if anyone's the deck
ping me and have it thank you so much