IOHK | Cardano whiteboard with Prof. Aggelos Kiayias, Chief Scientist



all right welcome so i'm achilles
korea's chief scientist at i/o sk and
terry cyber security and privacy here at
the university of ellebra so today the
topic of our discussion is going to be
proof of stake protocols and more widely
blockchain protocols how do you design
them how do you prove them secure so to
get us started I'd like to do a little
bit about cryptographic design in
general like how does it cryptography
think when they go about designing a
security protocol like a blockchain
protocol so let's get to that so first
we have an objective and that objective
would be something that we would like to
do so that could be for example
designing a ledger like a blocking
protocol tries to solve or could be
something else like a component like
digital signature so given that
objective and now an owl can to describe
a bit later how it's possible to specify
that objective specifically we have two
other things we have to determine like
next thing is the resources that are
available to the parties that are going
to be running the protocol or to the
parties that are going to be using an
algorithm to meet the objective and
together with the resources we have to
design and describe a threat model
now these two they come hand-in-hand so
the resources would be things that when
we write our algorithm the parties that
are using the algorithm are going to
have them available and the third model
would describe what the adversary is
allowed and what is not allowed to do in
order to come up with a good threat
model we would have to think exactly
what is going to happen when our
algorithm is going to be deployed in the
real world and we would like the threat
model to completely capture what is
going to be happening now given these
two then comes an algorithm or the
protocol so the algorithm or the
protocol will be code or a specification
for code that uses the resources
available and meets the objective given
the threat model now this is what we
hope that is going to work now what we
would like is actually to prove formally
that this is the case now typically this
will also involve some other assumptions
and these assumptions could be things
that we do believe they are true about
the world for instance a common
assumption that is used in cryptography
is that certain computational problems
like the well-known discrete logarithm
problem is a difficult problem to solve
so this would be the assumptions let's
say mathematical frequently in nature
that we're going to assume when we argue
that our protocol or algorithm meets the
objective and finally given all that we
will have a proof
and that security proof is going to
establish that the algorithm meets the
objective given the resources in the
threat model that we have specified
under the assumptions that we have
described so this is the general logic
that we use in modern cryptography to
argue that protocols are secure we
design them following this logic and
designing of the protocols is actually
following a feedback between those so
sometimes we have to revisit the
resources that are available sometimes
we have to revisit the threat model then
we have to fine-tune the algorithm look
at the proof and then again because
frequently things won't be exactly in
the way that they are appropriate for a
security proof to emerge the final
objective is that this would be solid
and then once we have this the algorithm
in the protocol will be specified and
implement it now going a step further we
have from the algorithm protocol we have
a specification emerging and then given
that specification we have the
so this gives a greater picture so let's
see how this can be put in practice we
can see how we can apply this logic to
the design of a distributed ledger so
what is the objective in the case of a
is something that let's call it
distributed ledger
we need some more space to describe now
what a ledger is
we should not think of a ledger as
something tight necessarily to the
blocks in protocol itself this is an
important point to keep in mind the
blocks in protocol will come as a
solution to the ledger problem so to
have a ledger we need two things
persistence and liveness these are the
two basic properties these two
properties they do refer to a log of
transactions resistance is a type of
safety property it basically says that
the view of the log of transactions is
stable if you ask any node that is
implementing the ledger will give you
the same version of the log and that
also should hold true over a period of
time so if you ask today what is the log
the log that you will find tomorrow will
be an extension of the log that you
heard yesterday so this is captured by
persistence and it's possible to define
this in a mathematically precise fashion
resistance is not enough what we also
need is that the ledger the log of
transactions is populated by
transactions which are admitted by those
that use the log so liveness basically
says that new transactions are added a
regular frequency and at minimum there
is an upper bound after which a
transaction which is sent to the nodes
that are implementing the ledger will be
included in the log so these are the two
cornerstone properties
of what is the objective of a
distributed ledger so now let's go and
see how we can implement that so we have
to talk about resources and we have to
talk about the threat model let's talk
about resources first so the resources
available would be first that parties
have private memory and they have the
ability to sample random strings these
are important resources for the design
the protocol and in many cases and these
are typical I should say in crypto
graphic design so it's typical in crypto
graphic design that we think that a
computer system which move might call it
a party for simplicity in the context of
a protocol it has its own memory that
only itself can access it and he has the
ability to sample randomness and that
randomness it's only its own it's not
shared with other parties now this
sampling of randomness should also be
private in the sense that an attacker
from outside should not be able to
subvert the randomness of a party so
this is the first important resource
so another resource should be access to
a network that is relatively
synchronized let's call it like this so
basically this says that when a party
wants to send a message access to the
network is facilitated and in a
relatively synchronous fashion that
message is going to reach the other
all right and this next would describe
now the threat model now in a threat
model we would like to specify what the
adversary is capable of doing so the
adversary should control a number of
parties now we have to put a bound on
how many parties the adversary should
control and now depending on the setting
we will adjust this bound so that it
fits the type of design we would like to
make for instance in the proof-of-work
setting let's say as in Bitcoin the
bound on the number of passes the other
side controls is that it should restrict
the other side to be the minority of the
total hashing power which is available
to the network in the case of a proof of
stake protocol in contrast we would like
the bound to restrict the adversary to
the minority of the stake that is
recorded in the ledger so this also
provides the threat model now with that
let's see what would be
the solution let's make a contrast
between the two proof of work proof of
stake in a proof of work setting what we
have is that the part is they're going
to be communicating with each other
solving proof of work and exchanging
blocks that will record whatever they
won't include in the ledger so what's
happening is that in a proof of work
based solution for a letter like that of
Bitcoin you have a Genesis block which
then is extended by parties as they find
proof of work each of these blocks is a
proof of work and inside here you have a
number of transactions in the proof of
State case something similar is
happening you have a game
a sequence of blocks it's one of them
has transactions but what you have
inside producing its block requires a
proof of stake let's see the difference
between the two producing a proof of
work requires parties to solve a
moderately hard cryptographic equation
more inequality
specifically in the case of Bitcoin so
you can think of the whole protocol
operating as an election at any given
moment one of the parties is elected to
produce the next block and the next
block is going to be produced
basically at random it's a random
sampling by those that are attempting to
produce the block in proof of stake what
happens is a similar type of operation
in a proof of stake setting the next
block is elected by is produced by one
of the stake holders at random based on
the stake that is recorded in the
blockchain so what we have in both cases
is an election
that points to the next eligible party
to issue a block the nature though that
election is different in the case of
proof of work and let's make it now more
specific Bitcoin what we have is that
the election is based on solving this
moderately hard problem specified by the
Bitcoin client let's make it more
specific for proof of stake in the case
of Kerberos what we have is that the
election is based on a cryptographic
protocol that creates randomness and
stores it in the blockchain in both
cases though the high-level logic is
similar there is this election process
that will enable one of the parties to
issue an X block so this is the central
idea that typifies how these blocks and
protocols work something it's
interesting to point out is a different
assumption that happens with respect to
the Genesis block so both protocols have
as a requirement to provide parties a
Genesis block that they can use as a
point of reference of what is the
what is the correct blockchain in that
point of reference in the case of
Bitcoin specifies just the initial block
and that's initial block plus a setting
the difficulty level
so the difficulty level is stored in the
genesis of Bitcoin and here we have an
initial stakeholder distribution so in
both cases there is going to be an
assumption about the Genesis block so
the Genesis block should know something
about the status of the world when the
blockchain is initiated in the case of
Bitcoin you should hit the right level
of difficulty that reflects how many
parties will be producing blocks when
the blocks and starts and similarly the
knees as they called distribution should
be a distribution that has been preset
and coded into the Genesis block of the
proof of state protocol in both cases
the assumption would be that there must
be an honest majority honest majority of
stakeholders here honest majority of
hashing power here so this is how the
protocols now compare now let's look at
how do we prove that these protocols are
secure and under what assumptions and
what arguments the two protocols might
be argued to be secure so let's come now
to the proof of security how do we argue
that block same protocols are secure and
again I'm gonna make a contrast between
a proof of war protocol like Bitcoin and
a proof of stake protocol like Ouroboros
so in the case of Bitcoin the logic
basically is as follows what you have in
the protocol operation is that multiple
block chains
coexist the reason for that is that
parties first of all naturally Fork they
are not synchronized they're not
coordinated they don't do the dune run
the sparkle in a coordinated fashion so
you can have many Forks that are
naturally emerging so the same situation
will be happening in a proof of stake
setting I should say so the two
protocols kind of have the same logic in
terms of resolving these Forks the
parties do follow the longest chain now
the definition of longest is slightly
different between the two but let's say
in simple terms the proof of work based
blockchain will follow the chain that
has the biggest amount of difficulty or
if you want the most amount of blocks
if difficulty is fixed for a certain
part of the execution and here you will
have followed the blocks in with the
most amount of stake again the most
amount of blocks so a similar rule in
both cases but let's see how this is
going to be reflected in the security
arguments now what happens in proof of
work is that because solving a block is
a moderately hard problem there is going
to be these moments here is such a
moment where a block is produced
uniquely by a single honest party so in
the analysis of the Bitcoin blockchain
protocol this has been called a uniquely
successful round
so basically it's a period of time where
just the single owners party was
successful now something very
interesting happens with those rounds
which are uniquely successful and they
if you look at the protocol execution
what is happening is that if such a
round happens the block that is produced
by the honest party will be adopted by
all other honest parties unless and only
unless the adversary acts and issues
another block that confuses the honest
parties and splits them so the
cornerstone of the analysis of the proof
of work based Bitcoin protocol marking
Bitcoin this side again is that the rate
of uniquely successful rounds should be
bigger than the rate of blocks produced
by the adversary in if that is ensured
then you can so that the adversary will
not be able to maintain what is known as
a fork so this is something that will
enable us to prove persistence so
we'll be implied by this inability of
the adversary to maintain a long fork
now lawn fork here is relevant and is
because it's important to think of a
fork over a period of time
small forks will occur but eventually
over a sufficiently long period a number
of such uniquely successful round will
or cure that will overcome the number of
blocks that are produced by the
adversary and because the adversary has
too much it's and all of them it's one
of them then he will be unable to and
thus the fork will collapse so this is
the central security argument that we
used in the backbone paper to establish
that the Bitcoin blocks in protocol is
secure now this proof logic is tempting
for someone to use it in the proof of
stake setting now unfortunately what
I'll show you now is that this is not
the main problem in the proof of stake
setting which you have a similar
situation like that can be illustrated
with a following example so imagine you
have a fork that somehow starts from
here and there are let's say honest
parties being acting here here you have
an adversary who is elected to produce
the next block in the case of rural
boroughs but also similar in other
protocols what is going to happen is
the adversary by being elected to issue
the next block he is capable of adding
this block in more than one potential
block chains so he is getting somehow
the ability to use the fact that he is
elected more than once
and these spoils the counting argument
that make that security proof go through
this is also consistent with our
understanding that proof of stake
protocols they are more difficult to
argue security for and is correlated
with problems that the blocks and
community has identified like nothing at
stake it basically means that it costs
really nothing for the adversary to
produce blocks in multiple possible
histories of the protocol and that's
exactly the point that spawns the
security argument here but now the
question is that is that the end is it
just fundamentally impossible to argue
that a simple protocol like Ouroboros is
capable to be proven secure and the
answer is no we can actually produce a
block of security we just have to work a
little bit harder so let's see a little
bit what is going to make visible the
security proof in the case of a proof of
State protocol like Ouroboros alright so
let's take a kind of deeper dive and see
how a robust execution looks like let's
take an execution segment
segment of an execution in the Ouroboros
protocol so what's happening is that
multiple we can start from this block
and there is a potential like multiple
blocks may coexist and multiple change
so some of these blocks are produced by
the adversary so here is the adversary
that has produced this blocks now there
is no the adversary is in control of
these blocks is that he was elected at
that moment and as you see he used the
liberty he has to issue multiple blocks
for the same position so this is how the
protocol execution looks like at that
particular moment you can imagine that
you are the next party to act in the
protocol so here we have a good guy now
he comes to do this part and executes
the next step in the protocol so the
last honest block that was produced was
here and here we have the adversary who
is together with that chain which was
produced by another honest party his
also has at his disposal other block
chains that it can serve to that party
in the security analysis of Ouroboros we
assume that the adversary is in full
control of the network and it can order
messages the way that he prefers thus if
he is capable of adding more blocks to
that block saying here
it will be feasible for the adversary to
serve that blockchain to that party so
for instance imagine that it's possible
for the adversary to add three more
blocks here now that chain becomes more
preferable for that party because the
adversary can arrange for that
blockchain to be served first and that
party is using the simple longest chain
rule in order to produce the next block
so in that particular case the adversary
has the ability to serve that block
chain to that party and the next block
that is going to be produced is going to
be here on the other hand the adversary
could have selected to serve that blocks
and first again he's in control of the
network so this situation is not a very
desirable situation for Ouroboros the
fact of the matter is that the adversary
has full control of what locks in to
serve to the party and what we are
experiencing here is a fork now we would
like to argue that this undesirable
situation happens with very small
probability so the adversary really
cannot count on it so the way that we're
going to argue for this is to try to
understand what are the fundamental
features of that structure as they
emerge in a protocol execution so each
one of these threads that you see here
we call them x so here is a time one and
here is time - okay so here we have the
situation with two times that the
adversary can exploit to confuse the
honest party that is activated
the protocol so this is the setting that
we would like to avoid and here is the
one that we hope it happens most of the
time so most of the time what we hope in
the protocol that is happening is that
the protocol execution starting from
here has a single long time and
furthermore any other disjoint times
that exist are too short for the
adversary to be able to reach the
leading one so basically this is an
execution segment that provides the
opportunity for the honest part is to
adopt using the longest sane rule that
block and in consequence that chain so
this is a good situation and we would
like to show that this happens almost
all the time
now in order to be able to argue that
what is going to happen is that we have
to understand the dynamics of this
execution segment and how they are
translated into this set of times so
what do we observe is that it's possible
to define a certain quantity which we're
going to call reach that is going to
specify for any execution segment how
far ahead for each time the adversary
can go with respect to the last block
that was issued by an honest party so in
this case that's the last block that was
issued by an honest party and perhaps
the adversary can have one more block
here so the reach of that time is going
to be one whereas here the reach of
these other times is negative so reach
negative and positive so what do you
observe when we look at an execution
segment is that the maximum reach will
always be greater equals zero there is
one block that is the leading one that
is by an honest party and perhaps the
adversary can put some blocks on top of
it because she has some slots here he
has some opportunities to produce blocks
ahead of that and other times will be
hopefully now what we would like the
picture to be is always like that with
all other times having a reach to be
negative the second biggest reach we're
gonna call it the margin so that's the
second largest reach so if the margin is
negative we know we are safe because all
these other times are too much behind
and they cannot reach the leading one
whereas if the margin is greater equals
zero then it's possible for one of the
times to reach that block and then we
have a problem execution like the one
that we've seen before the adversary can
fork the next honest party and deliver
to the party any chain that it wishes so
now we would like to show that the
margin which is the second largest reach
is always going to be negative with
overwhelming probability so how are we
going to do that so in our arsenal of
analysis we will put a probabilistic
argument which relates to random walks
random walks is an area of probability
which has a lot of applications
in blocks and protocols the most simple
random walk is the one that is called
one-dimensional random walk and those of
you that are familiar with analysis of
blocks and protocols or even the white
paper of Nakamoto you can appreciate how
that relates to basic analysis of the
Bitcoin blockchain so a random walk has
in a one dimension starts from a certain
point let's say zero and then flipping a
coin it either moves forward or backward
let's say that coin has a probability of
coming up heads which is some number P
which is less or equal 1/2 and here is
the coin going forward now with
probability 1 minus P we go backwards
so that's a picture of a one-dimensional
random walk questions that are relevant
for random walk are the following
suppose you start at position zero and
we can ask for a certain choice of P
what is the probability that you will
find yourself at another position what
is possible to show for a
one-dimensional random walk is the
following it's possible to divide the
region in three segments let's call the
middle volatile this one hot and this
one called
and then you're gonna take a number of
steps and after you take a number of
steps we will examine what region you
are then you're going to take a few more
steps and we're going to examine again
the region we are now it's possible to
make an argument and say that if the
probability is strictly less than 1/2
then what happens as you observe is that
the random walk will have a tendency to
go left in the cold territory and that
is indeed the case we can prove that
after a sequence of steps you're gonna
find yourself in a cold territory and
once you find yourself in the cold
territory it would be very unlikely that
you will be able to return back to
volatile or hot what actually is going
to happen is that after a number of
sequences of steps you're going to find
yourself in this territory and
eventually escape to the left that's
because the random walk has a bias to
the left the nice thing about this is
that it describes a number of phenomena
in the analysis of the Bitcoin blocks in
protocol for instance the fact that in
we'll fall behind of the main honest
chain and his probabilistic behavior can
be modeled by this random work which is
biased to the left the cold setting is
basically the setting where the system
is stable because the adversary has
found himself behind this is one
dimensional random walk unfortunately
such a random walk which can be useful
when you think about Bitcoin cannot be
useful in the analysis of Ouroboros it's
too simple to capture exactly the
phenomenon that's the probabilistic
behavior of the protocol exhibits
instead what is interesting is that the
protocol is described well by a two
dimensional random walk which I'll give
you a short glimpse of so the two
quantities that are relevant in this
two-dimensional random walk is margin
and reach or to be precise the maximum
reach that a certain execution segment
has remember the maximum reach is going
to be the reach of the time which is
most ahead and the margin is going to be
the second time which we would like to
be of negative reach so what we would
like in this two-dimensional random walk
is to show that the margin is going to
escape towards minus infinity so as in
the case of Bitcoin we wanted the chance
of the adversary to bring back his same
comparable to the honest parties we
wanted that to escape towards minus
in the single dimension here we would
like the margin to go to this minus
infinity in that direction because
remember margin is what the adversary
needs to reach the owners parties that
are producing blocks at the head of the
chain unfortunately the relationship
between these two parameters is more
complex than a simple composition of two
one-dimensional walks and what's
happening actually is that the work is a
little bit like that when you are in
that domain you flip again a coin
following this behavior which as you see
is a one-dimensional type of behavior
and given that reach is always positive
what happens when you are in that
position is that you just go down so
like this but now what's happening once
you go up should give you myself just a
little bit more space to show you
exactly the phenomenon of this random
walk so once you go up you have again
the random walk
climbing up like this and as you see so
far this is pretty much a simple
one-dimensional behavior but once you
reach that point what's happening is
that the random walk gets attracted to
zero so it doesn't follow the same
upward path as before and you can see
why this complicates the analysis what
we would like is that the margin goes
towards negative values minus infinity
but what happens actually in the
protocol is that it is possible for an
attacker running against the protocol
to use this X dimension which is reach
to compensate for margin and maintain it
at zero the question is that is this
effect sufficient to prevent this whole
random walk from escaping to minus
infinity and the answer is that no it's
still possible to do an analysis similar
to the one analysis I showed you for the
simple one-dimensional random walk and
that analysis basically also involves
defining regions over the two
dimensional space which roughly look
like that and repeating the same
argument so what's happening is that
here is going to be hot here is volatile
and here is cold and it turns out that
by setting this the areas of these
regions suitably what we can show is
that the same escape to infinity
behavior which is favorable for the
honest parties is going to happen in the
same way that in the two in the one
dimensional case and this shows how is
it possible to get a similar type of
analysis for persistence where basically
establishes the fact that honest parties
converse to a single chain i'll beat
with a more complex argument so this
presentation was aimed to give you a
glimpse of how security analysis of
blocks and protocols is performed I
showed you a contrast between Bitcoin
and Ouroboros inspired from the security
arguments that we know for both these
protocols and I contrasted both of them
so that you can see both the similarity
as well as the difference between the
two protocols in terms of the security
arguments that we use to establish that
are secure
the situation that comes out from all
this discussion is the fact that yes we
can prove both protocols being secure
and their different assumptions this
does not affect other aspects of the
protocols that are of critical
importance such as the performance of
the protocol or the energy footprint
that this protocol has what we know is
that both protocols are secure albiet as
you know a proof of stake protocol is
much more efficient protocol in terms of
energy consumption compared to proof of
war protocol so but that econ itself
would be the subject of another
discussion thank you very much for
attending this presentation