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

implementation

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

ledger

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

parties

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

blockchain

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

persistence

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

feasible

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

that

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

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

behind

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

malicious

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

infinity

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

## コメント