I'm going to talk about the Pala
consensus protocol this is giant work
with the hilbert chandra file pass so in
chinese pili pala is the sound of
thunder
it also means fast furious and
streamlined okay so I will begin by
explaining the problem I'm trying to
solve right so in all these
cryptocurrency systems the car
abstraction is called state machine
replication also referred to as
blockchain or consensus so in the rest
of the talk these terms are used
interchangeably and we have a set of
decentralized nodes and these nodes are
trying to reach agreement and
ever-growing linearly or the lakh of
transactions okay there are two
important security properties that we
care about namely consistency and
liveness consistency says that all of
the honest nodes must agree on the same
lock so it could be your log is a little
faster than mine because network has
delay but nonetheless at the end of the
day we have to all agree life this says
that whenever I want to buy coffee the
transaction will appear in all of the
honest nodes locks very quickly it's not
like I want to wait forever for my
coffee
okay now initially the problem may seem
somewhat boring right so what's so
exciting about building a linearly audit
log well indeed if all of these nodes
were honest and they correctly followed
the protocol the problem would have been
trivial but what's challenging about it
is when some of these nodes can be
corrupt and these corrupt nodes can
behave arbitrarily and deviate
arbitrarily from the protocol and even
in such add adversarial conditions we
want to make sure that the remaining
honest nodes must nonetheless satisfy
these security properties so in the rest
of the talk we are always going to
assume that less than one third of the
nodes are corrupt okay so I will tell
you a very simple consensus protocol
that satisfies these two properties
consistency and lightness and to begin
with I will first explain somewhat of a
strawman scheme a protocol that's very
natural
it works by single round of voting and
this is
actually Sounders fast path consensus
protocol the previous version if you are
not familiar with the Sounders protocol
it doesn't matter because entire talk is
going to be self-contained okay so let's
start with this very simple voting place
protocol and before I talk about the
protocol I will very quickly explain the
block format we are going to assume
throughout the talk right so in the talk
we are going to assume every block
contains the parent hash basically it's
a cryptographic digest of the entire
prefix of the chain it has an epoch
number so we are going to assume every
epoch is one second and whenever honest
node sent a message the message is going
to get delivered in let's say a quarter
of the second so in one epic you can
have four round trips for simplicity in
this talk I'm just going to assume the
synchronous model basically every honest
message will get delivered very quickly
but at the end of the talk I will
mention it's actually very easy to
extend the approach to partial
asynchronous setting to okay so now of
course the block is going to contain the
transactions you want to confirm okay to
make it more fun this is the scenario we
are going to work with Vitalik acts as
the proposer and everyone else is a
voter right so some of these notes can
be corrupt like in this case low key is
corrupt and the proposer can also be
corrupt so here's how a very natural
protocol would work step number one the
proposer makes a proposal and the
proposal contains a block and the block
is tagged with the epoch number
indicating the current epoch okay now
when the voters receive the proposal
they are going to vote on the proposal
right and in this case
Vitalik proposed an orange block so if
you are honest you are going to vote
exactly the proposal you have received
so everyone almost everyone casts an
orange vote except for Loki right Loki
is corrupt
and instead of voting honestly he voted
for you know two blue blocks okay so now
we have voted what do we do next
we basically wait we wait until we
collect enough votes on the same block
and when there are enough votes on the
same block we have high enough
confidence then we can confirm that
block so what is enough in this talk I'm
going to assume votes from 2/3 the
committee is considered enough and in
fact if we have 2/3 votes we are going
to cut that a notarization okay so a
very important thing to remember about
this protocol is that all of the honest
notes are going to vote to uniquely in
every epoch this means that in every
epoch I'm going to wait until I hear the
first proposal from the proposer I'm
going to vote on that proposal and only
that proposal I'm not going to vote on
anything else
so this invariant is very important for
consistency and in fact given this
invariant I can give you a very simple
consistency proof ok so imagine
let's fix an epoch ok so imagine for
this epoch the blue block obtained
notarization and the orange block
obtained notarization - and what I want
to prove is that the blue block must be
the same as the orange block and
remember as I said in the beginning we
are going to assume less than when
certain notes are corrupt okay so how
does the proof work if you look at the
blue set and orange set and remember
there are only n nodes in total right so
it must be the case that the
intersection contains at at least one
third and nodes and now because the
adversary controls less than one third
this means there must be an honest node
in this intersection ok now remember
what I said about honest nodes right
they are going to vote uniquely and if
this honest guy in the intersection
voted for both the blue and the orange
there is only one explanation right
basically the blue block
be the same as orange okay so this
establishes the fact that with this very
simple protocol for every epoch only one
black can't get notarization okay and
another thing to note is that this
consistency proof doesn't rely on the
proposer being honest the only thing it
relies on is the fact that honest notes
vote uniquely okay so with this in mind
let's take a step back and think about
this very simple protocol right as I
said we are going to assume two-thirds
of the nodes are honest and online and
when the proposer is honest life is all
good we have both consistency and
liveness consistency I've just proved to
you life this is all so simple because
if the proposer is honesty is going to
propose the same thing to everyone and
because two-thirds of the nodes are
honest soon enough you are going to
collect enough votes and you make
progress so when the proposer is corrupt
what happens in this case we still have
consistency because as I argued the
consistency proof doesn't rely on
proposer being honest right but we don't
have liveness because the proposer can't
just crash and fail to propose anything
or maybe he can propose different things
to different people and everyone will
end up voting on a different block and
no block will gain notarization in this
case so ok so now if you look at this
picture we have three out of the four
properties and the only thing we need to
fix is the liveness issue when the
proposer is corrupt and if we can fix
that we can get the four consensus
protocol okay before I talk about Paulo
I want to quickly mention the approach
that's used by the previous version of
the standard protocol right in the
previous version of the time the
protocol the idea is that we have the
fast path and the slow chain the slow
chain is basically think of it as
aetherium as Bitcoin but it can also be
a proof of stake slow chain right so on
the first path we run this voting based
protocol like I just explained but when
the proposal crashes and the fast path
doesn't have liveness we will fall back
to the slow chain and we use the slow
chain to resolve the problem and to
really
the next proposer and now you can reboot
strap the fast path okay so this is a
very simple and powerful idea when
drawback is that if you use this
approach to fall back to the slow chain
to fix the the proposer then the
proposal switch is going to take about
ten minutes if let's say we use a
theorem as a slow chain and that's
rather slow and one implication of this
is that if we want to have an if we want
the proposer to be like decentralized on
the fast path it's kind of impossible
because every time we switch the
proposer it's going to cause
interruption for ten minutes and that's
not going to be okay okay so what we
want is the mechanism to allow us to
rotate the proposer on the fast path in
the seamless manner and that's what I'm
going to talk about I'm going to talk
about the Pala protocol paula is
thunders new fast path consensus
protocol it's actually a full-fledged
consensus it gives you about consistency
and liveness
and and in fact you can't just like run
Paula in a standalone fashion even
without the slow chain and one question
you might want to ask is you know since
now Paula itself is a full-fledged
consensus protocol do we still need a
slow chain right and the answer is you
know it still makes sense to have a slow
chain because the slow Qing is a multi
centralized packing you can have
decentralized monitoring of the fast
path through the slow chain and whenever
you know under these extraordinary
circumstances let's say maybe the entire
committee can be corrupt in these cases
you can still use the slow Qin to
recover
okay so again if you are not familiar
with Sanders current approach it doesn't
matter because the protocol I'm going to
explain as I said is self-contained and
the full-fledged consensus protocol in
itself okay
so since we are going to talk about
proposal rotation the most challenging
case is if every block can allow a new
proposal and that's what we are going to
stick to in this talk we are going to
assume a very simple around robbing
and in epic I note I is the proposer so
if we can solve this extreme case then
the other cases are simpler like for
instance you can have a stability
favoring policy where you only switch
the proposer when the current one
doesn't work ok but this is what we are
going to stick to in this talk ok so
let's kind of quickly recap the fast
path the one round voting protocol we
mentioned right and let's try to work
the proposal rotation into this protocol
so as I said the protocol goes by epochs
in every epoch we are going to do the
following very natural if I'm the
proposer of this epoch I will take my
freshest notarize chain and I will
propose the next block extending the
freshest notarize chain so very natural
when people receive the proposal they
are going to vote as I explained earlier
everyone votes uniquely in each epoch
but I'm also going to assume that when
people vote on the block they are going
to check that the parent chain has been
notarized because if the block extends
from an invalid parent you shouldn't
vote on that block ok so the protocol
goes by proposed vote proposed vote very
simple of course it doesn't quite work
yet and what I'm going to do next is to
kind of describe the problems with this
protocol and introduce two very simple
fixes to this very simple protocol ok
and then the resulting protocol would be
actually provably correct ok well the
nice thing is that this very simple
protocol already works in ideal world
when everyone is honest right if
everyone is honest we should what you
should expect is that you know as the
epochs go by these blocks get notarized
one by one and nothing will be skipped
and things are all good but when some of
these people can be corrupt so by the
way I forgot to mention and I'm just
going to assume like the committee
itself will act as the proposer I'm not
going to distinguish the
and the proposer anymore okay because
the proposer is like you know by
rotation okay now when some of these
notes are corrupt then you'll run into
these somewhat tricky problems and I
will use this as a running example to
illustrate the problems and to introduce
the two simple fixes okay so let's look
at this scenario right so imagine this
is a notarized chain that I see during
the protocol what are the problems here
one problem is that the block number two
is being skipped there is no block
number two and another problem is that
the fifth block is extending from three
and not extending from four right so
this actually creates a fork what I
really want to talk about is the second
problem but let me just very quickly
explain the first one right so how can
plug to be skipped
so if proposer two is corrupt let's say
he just crashes and he didn't make any
proposal I mean of course no epic two
block will get notarized right so what
we don't want is for a single bad guy to
kill liveness and we can do this if we
just basically were just going to allow
skipping in a notarized chain the epic
numbers don't have to be consecutive you
can skip okay
but this skipping behavior kind of
introduces the second problem which is I
would I want to focus on right in this
case you may ask why does the block
number five extend from three and not
from four okay so let's think about it
well very natural explanation is that
perhaps the proposer five is corrupt
although he sees block four notarized he
tries to you know undo block four by
extending from a previous block okay and
that's not going to be okay and in fact
you know in the extreme case if I'm
malicious I can extend from a very very
ancient block
from the past and that's that's not
going to be okay right
so the fix is actually very natural and
this was the protocol we had earlier and
I'm just going to add an additional
route to the voting to say whenever I
vote for a block I will make sure that
the parent chain is fresh enough right
if this proposed block is extending from
something way way way back in the past
I'm going to refuse to vote on it so
technically we have to specify what it
means to be fresh enough and the most
natural strawman kind of idea is to say
I will compare the parent block with the
freshest notarized chain I've seen so
far and I want that the parent block be
at least as fresh so this almost works
but not quite so because one thing is
that the proposal was made let's say
half a second ago right and if I'm
comparing the proposal with my current
freshest notarized chain that's kind of
unfair to the proposal because a lot can
have happened during that half second
right I could have seen new notarized
blocks during that half second so what
the protocol actually does is to have a
slightly relaxed condition instead of
comparing with the present myself I'm
going to compare the parent block with
myself but a second ago so the second is
like a parameter it actually captures
attention between consistency and
lightness and the actual proof to show
that this parameter works is a you know
just it needs a little bit more work and
but for the talk I'm going to ask you to
take my word for it if you set this to
be one second it'll all work okay so
that's the first fix and we are almost
there
we just need one additional minor fix
okay and I'm going to use exactly the
same scenario same question to motivate
the second fix so remember what we asked
is why does the block number 5 extend
from
and not four and earlier we said you
know perhaps the proposer five is
correct now I'm going to ask you to
erase everything from your your mind
forget about everything I explained and
let's start from scratch here's another
possible explanation it actually could
be the case that proposed a five is
honest and it is proposal for who is
corrupt and this scenario can also
happen when proposal for is the bad guy
and how can it happen here's the
concrete attack so let's say Loki is our
proposal for he proposes two blocks in
epic for the blue block to the blue guys
and the red block to the red guys now we
have six and people on the committee so
you need like four votes to have a
notarization right in this case if you
collect all of the honest notes votes
it's not enough to make a notarize issue
for either the blue or the red block
because we have three for blue and two
for red but remember that the corrupt
guy also has a vote now if the corrupt
guy votes for blue he can have an
authorization for the blue block and the
bad thing here is that the corrupt guy
is the only guy who knows an
authorization for blue and no one else
has seen an authorization for blue yet
right so now he can play it to his
advantage in particular he can time the
release he can let's say release the
last vote to a subset of the notes first
so some of the people will see
notarization for this block first before
others see it okay so concretely okay so
this is the only guy who knows an
authorization for the blue block so
concretely he's going to exploit this
advantage in the following way so at
some instant the bad guy chooses one
victim in this case spider-man and it's
going to tell spider-man an
authorization for the the fourth block
okay
at the same instant everyone else hasn't
seen another ization 4/4 yet they've
only seen notarization for the prefix up
to three so now what's going to happen
is that these guys are going to vote for
the block 5 and because the you know the
fifth proposer is honest and he hasn't
seen notarization 4/4 yet so he's going
to build this block from 3 and then this
block can take notarization in this very
instant okay so what is problematic
about the scenario the problem here is
that suppose and at the instant when
spider-man sees notarization 4/4 if he
hastily confirms plot for that he's in
trouble because at the end of the time
he'll live to discover that in fact this
other fork survived to the end of time
and 4 is abandoned right so he risks
inconsistency with the rest of the notes
at the end of time okay so what do we do
now well the moral of the story is that
like perhaps I shouldn't confirm a block
the moment I cease an authorization form
for me to confirm the block not only do
I want to see an authorization for the
block I also want to note that many
other people have seen an authorization
for the block - so I want like a higher
degree of confidence okay so now to
implement this idea the question we have
to answer is how do I know that many
other people have seen the notarization
right I know when I see the notarization
but how can I tell that you guys have
seen the notarization - in fact we can't
do this also very simply so imagine we
have two consecutive blocks in this case
3 & 4 and I've seen both of them
notarized so remember the honest notes
are only going to vote for block 4 if
they have seen notarization for 3 right
I'm
see the notarization for the parent
before I vote for the block so this
means by voting for four I'm also
attesting to the fact that I've seen
notarization for three in epic form so
whenever I see this pattern two
consecutive blocks get both getting
authorized I can draw the conclusion
that many honest people must have seen
an authorization for three in their epic
form not only have they seen the
notarization they see it very fast
the seating I pick four so this is very
nice because for any future block many
since many people have seen notarization
for three very quickly they're going to
insist on the prefix ending as three be
included in any future chain and that's
how the block is going to stick around
and not be lost right so for instance I
put five for any future epic if anyone
makes a proposal this proposal must
include the prefix ending as three
otherwise people are just going to
refuse to vote on it right remember
people check that the parent block must
be fresh enough when they cast the vote
okay so essentially this motivates the
second very simple fix and all we need
to do is to add the following
modification to finalization right so
remember in Bitcoin whenever we see a
chain we don't output we don't confirm
the whole chain we chop off the trailing
six blocks the trailing six blocks are
not stable yet and here it's a little
bit similar except that we don't chop up
six blocks right whenever I see a
notarized chain and let's say the
notarized chain and at a streak of
consecutively notarized blocks so
basically everything except the last
block is by now so if any time I see a
notarized chain ending at a streak of
consecutively notarized blocks I only
have to chop off the last one and then
the prefix is notarized
but the prefix is final
okay so that's basically it and just to
quickly recap the protocol is very
simple you go by proposed vote proposed
vote and you you need to check a couple
of things when you vote and then this
very simple proposed vote based protocol
combined with finalization rule actually
gives you approval a correct consensus
protocol I'm not going to go through the
proof and to quickly conclude in this
talk I talked about a synchronous
protocol that tolerates one-third
corruptions right for Santa's new fast
pad consensus it's not too difficult to
extend this protocol to the paschal
asynchronous setting and as I said the
protocol is extremely simple it's like
almost the most natural protocol
combined with the you know a carefully
thought-out
finalization rule and what's cool about
this protocol is every block requires
only a single round of voting to confirm
okay so let me just quickly conclude and
try out our test net and also sander is
currently hiring and we have all sorts
of positions including executive level
positions like CMO and CRO and contact
me if you are interested thanks
you