zkSummit:Ouroboros Samasika: A Proof-of-Stake Consensus Protocol for Succinct Blockchains V. Rao

Transcript

uh so my name is manri um thank you everybody for um being patient with all this uh technical issues um uh I work on the qua protocol um and I'm presenting orora samasa which uh is a proof of State consensus protocol for sexing block chains and this is Joint work with the entire team but uh mainly in collaboration with Isaac and Ian so before we uh dive into the consensus protocol uh let's quickly Recall why a sucing blockchain is important uh as we all know the original goal with which Bitcoin was designed was

uh decentralization where uh all parties should be able to access uh uh should be able to take part in the blockchain protocol and verify blockchain but that is not the case anymore as more and more transactions are getting record under the blockchain making the blockchain grow bigger and bigger as a result uh only a shrinking set of Highly powerful parties are able to uh participate in the blockchain protocol thereby strongly backpedaling on the goal of decentralization um now um so clearly to have decentralization even at

scale uh we need to have blockchains um we need blockchains to remain small at all times and sucing blockchains offer just this uh so what is a suing blockchain a suing blockchain we Define it to be a blockchain um which can be verified in uh time polinomial in the security parameter so independent of the total number of transactions um so now having uh talked about and uh motivated uh suxing blockchains note that the core underlying tool of a succinct of of any blockchain protocol is its consensus protocol uh which specifies how people should come to

agreement on what should be entered into the blockchain next but now the problem at hand is that we cannot use uh the existing consensus protocols why because um either uh they do not provide the security guarantees we need or they are not compatible with the suxing blockchain setting so for security we of course require that uh there is no Reliance on um Central uh entity trusted entity and we also want that the modeling is as close to real life scenarios as possible but unfortunately some protocols uh require that require that there is a trusted entity who helps newly joining parties

with an ADV wise on what the recent uh chain is uh that's part for decentralization um of course and the some of protocols require that there is some common knowledge on what the participation level is at is um at all times um and some of the protocols um are not compatible with the suxing blockchain setting because they require you to hold on to the entire um uh history of uh blockchain so that that's not going to work with the suing blockchain setting because of these shortcomings of the existing protocols we uh design a new uh proof of State consensus protocol

for suxing blockchains called aoro samasa and uh you do not need excuse me you do not need any trusted entity to provide any sort of advice for uh any sort of help to newly joining parties uh a newly join joining party can just boot stack from Genesis from the Genesis block and um there is no restriction on parties on when they can join and leave uh the protocol and the pro our protocol is uh is proven secure in the Universal composability model which means that uh you can plug our protocol into a bigger system and still uh expect the same security

guarantees from mint as you would do in the Standalone setting so these are the proper of our protocol now let's dive into our protocol right so let's begin with how the modeling uh is the our protocol is set in the following uh setting we divide time into these uh periods called uh time periods called slots and each slot can either be filled with a block or it can be empty uh depending on whether there was a slot leader uh selected for the slot or not and of course a party WI a slot with probability proportional to its stake um so that is the modeling and

uh and the core um aspect of the the the the core aspect of any consensus protocol is its chain selection rules uh which specify Whenever there is a fork there are multiple chains to choose from which chain should you choose and uh we have two chain selection roles uh the first chain selection rule is just the simple uh longest chain rule like in Bitcoin where you choose the uh chain with the highest block highest number of blocks while this uh by itself works for uh proof of work setting of Bitcoin uh

this rule alone won't work for the proof of St for proof of stake systems why because uh proof of stake systems uh suffer from this vulnerability called cost Costless simulation uh because of which an adversary can um an adversary with nothing at stake can uh try different reruns of its execution uh to see what is favorable uh whereas in the case of uh a proof of work setting you will need to spend as much more resources to do another rerun um so because of this vulnerability uh an adversary can pose the so-called long range attack uh

wherein um an adversary would have forked the Tain long back in history and then uh over time slowly uh by by using various advisal techniques like grinding um she would manipulate um the slot leader distribution and in in such a way that eventually the total number of blocks in the dishonest chain is higher than the uh number of blocks in the honest change so clearly in this case the longest change will will not work right um so the uh ororo Genesis protocol which is our starting point uh the way this

protocol deals with this issue is that it says do not look at the whole chain do not compare the block the total number of blocks in the whole chain but just look at a few slots following the fork where the adversary wouldn't have had the chance to skew distributions yet so you just look at that period and compare the uh uh number of blocks in that period and pick the chain with higher number of blocks in that period um but note that what this rule means is that you will need to hold on to the entire chain history uh why because we may learn about uh Fork long after it

has occurred so you do not so you cannot be sure what part what information in history will be useful in future so you'll need to hold on to the entire chain history and um if you think about it this shouldn't be surprising why because um when you need to uh tell apart two things that are similar you need a lot of information about each of them to be able to tell them apart um but this requirement of holding on to the entire chain history will not work for suing blockchain settings so we designed this new uh chain selection rule uh where we maintain this um

um M maintain this window window that we call a uh move there's this moving window that we call a Min density window uh so here is how it works uh there is a window and it keeps moving with time and uh at any given point in time you just need to hold on to one single value uh and what is that value that what that value basically is the minimum of all the total number of blocks in any um number of blocks in any window we have seen so you you look at all the windows you have seen you you you take the number of

blocks in all the windows and all you maintain is just the minimum of what you have seen and uh you can of course do that by taking uh Min of the previous uh Min density value and the current total number of BLX so you maintain just that value and that is the idea um so why should this work why why does this uh suffice and to um squash all the necessary information in a sucing yet use yet useful manner um so here is a quick high level uh intuition on why this should work um so

um consider this uh Fork um um the h intuition is is is that um in the honest block because we are making this assumption that there is honest majority um um there it has to be that every block has consistently uh High number of every window has consistently High number of blocks and in the dis in the dishonest chain uh in the part where the adversary uh still hasn't had a chance to skew the distribution there is initially some low number of blocks and this in and this uh will affect the Min

and value forever because we are taking a Min of all the uh window uh block densities um so this is a very high level in uh intuition the proof of security uh involves um some amount of bookkeep bookkeeping and CA uh case analysis and um and uh uh and finally we'll need to prove all the uh core properties of a uh secure transaction Ledger namely um um the chain quality um chain growth um and so on so but what I'm going to do right now is just having given the high level

intuition let's see just at a high level what the proof structure will look like uh so that if you're uh interested in going through the uh paper it'll at least give you an anchor um to read that should help in reading the paper so how does the uh proof work um we let let's first quickly recall what is it that we want to prove we want to prove that the Min that that the honest chain will get chosen which means that the Minden value for the honest chain has to be greater than the Minden value for the dishonest chain um and we prove this in two steps

we first uh establish a lower bound uh for the honest lower Bound for the number of blocks in any window in the honest chain call it tlb and in the next step we prove some uh uper bound on the number of we we choose a specific uh specific window and we say that in this window there is an upper upper bound on the uh number of blocks in the dishonest chain um and call that tub and it turns out that tlb is higher than tub and thereby proving what we want um now how exactly do we uh achieve each of these steps so Step One is

relatively uh very simple uh we just use use a simple coroller of the auma hting inequality which is a generalization of the turn turnoff Bond uh turn of bound as we know is just for Bernal uh in independent Bernal uh variables but um Azuma hofing inequality um can be applied for any uh independent bounded independent random variables um so that's for step one for step two um we do it again in two steps uh we first identify a specific point in time in the uh dishonest chain and say that

uh there so here is what we prove we spec we point we specifically pinpoint uh a Time on the dishonest and say that after this time there cannot be an honest block because an honest party will ref ref to part participate in it and then what we do is we consider uh in in the next step what we do is we consider a window that that follows almost IM immediately after this point in time and uh we will be we will be proving an upper bound on the number of blocks for this window so we'll be taking into advantage two things one is that there is no honest participation in it so there is only dishonest participation in

this and uh the advis wouldn't have had the chance to uh manipulate the slotted distribution yet so uh there is only dishonest State contribution in this part and we will be able to place an upper Bound Again uh based on a different coroller of theuma hting inequality so this is the high level structure of the proof um so uh I don't know how we doing with time but uh uh I can say a little bit more about the proof but uh this is almost all uh almost all I wanted to say did you see that there's some questions in the chat maybe you want to take

okay or actually I could maybe we could read them out to you so that you don't have to look at them oh that's fine uh easier Dara I saw you had one do you want to ask yours yeah um so um you're assuming that um the onest chain has um basically a high block rate within any given window what happens if something goes wrong with the chain and that assumption isn't met yeah basically we force that assumption we we we say that the we say that people can uh join and leave the protocol but any given point in time the active stake uh we put the

lower bound on the active stake in our assumption okay yeah did that make sense D um I'm I'm not sure I completely understand um oh sorry maybe I misunderstood your question let's see um so so um suppose that there's um some fault some for example some bug in the code that's CA it's a temporary problem with the blockchain um how how would the protocol recover from that right um uh so so we we we are thinking of that to

be a more um system approach than within the protocol where there is some kind of a voting on what the um uh what the participation level is um but uh if this assumption cannot be met then the protocol uh by itself won't be able to do anything right I guess you could always make a choice in the software and check the chain that you actually wanted to continue from we had a similar problem on the zcash test net yeah where um the we didn't have enough mining power on the test net um and basically someone

manipulated the difficulty algorithm so that they had lots of hash power and then they with through it suddenly um and the chain just completely stalled um to restart it from yeah yeah and you can imagine such problems to occur uh in the initial part of the main where people are still joining the network right yeah yeah very very nice can can you go into more detail on um the proof uhhuh um so um let's see let me expand more on this

substep a which is the part that uh I didn't cover much uh in the talk so um so we use various uh so here here let me step back and before talking about substep a let me step back and talk a little bit more about the uh uh high level part of the proof uh so what uh what what we do is that um we say that if there is no long assume that there is no long range fork for very long time and then uh consider the first time there is a long range Fork we Pro that that until there is a uh as long as there is no longrange Fork

everything works like um everything can be proven secure just the way oror prow did um because oror prow doesn't uh cater to the long range attacks and all all the modeling is very much almost simar almost similar to PR so having done that then what we do is that in the proof um so this this structure part of the structure is similar to oros Genesis and then the exact way we execute the remaining part of the proof is uh different in our case um Genesis also falls back on um prow I mean and now um we are at a point where there is a

long range Fork some honest party discovers a long range Fork what what is it that we want to prove we want to prove that this honest party um will apply this new chain selection rule we have um this honest party will continue to hold on to uh it Tain but um um so this that is what we want to prove uh what why is proving this sufficient it is sufficient for two things we we need to consider two things right one is uh from the view of an honest party who is active and one is from the view of a newly joining party from the view of a new from the view of a non party who has been there we would want that dishonest party doesn't switch over to the

dishonest chain um and uh that's uh that's one thing we want to ensure and the other thing we want to ensure is that is that a new newly joining party will choose the honesty uh um [Music] so we we can we model uh a newly joining party the choice of a newly joining party from we treat it in a in in in a weird way we we say that there exists this virtual honest party who doesn't have any stake and who has been online for a very long time and there is this chain that this honest party has and we we we consider that as the honest chain we want that chain to

be chosen by the newly joining party right uh so there is this virtual party and we want that for this virtual party this virtual party will not switch over to the uh newly uh switch over to the dishonest thing so that's what Pro I said many things but let me summarize um to to pinpoint what the core aspect is so um we real the the first thing we do is that we say that until there is a um until the point there is a a long range Fork everything happens like prow once there is a long range Fork what we do is we consider this virtual honest party and all we need to prove is that this

virtual honest party doesn't switch over to the uh dishonest chain um uh when it applies this new chain selection role so that is what we want to prove now going forward in the proof um so we just do these steps the steps that I just described are the things that we do now uh we saw a little bit about step one step two um but let me say a a little bit more about step one and uh uh this about this uh inequality so um we we just need to uh count the total number of honest uh slot

wins uh in um any given time period and then we we just play so that is the that is the uh random variable uh um we take into consideration and then we apply this inequality on that and and we will be able to get this uh step one and substep B um excuse me and now um how do we do this uh substep a so uh we are talking about the part where there is this dishonest chain and we want to place a an upper bound on the number of blocks in the window um we what what we are trying to say is

we want we want to place we want to pinpoint a time uh after which there is no honest participation that is substep a to recall and the way we do it is um uh we say that okay so uh there are multiple cases um uh let me see uh can can can you guys see my uh Mouse yes we can see okay okay um so let's see uh let me see what is the first case uh it makes sense to talk first um okay so so what we do is that um we

say that okay we rely on this property called chain growth property and what this chain growth property does is that it gives us some Assurance on the total number of blocks right it it it again is the result of this uh it again is the result of this bound we place on the number of blocks right CH because of this property of chain growth there there is enough number of blocks um we have in this part right this is the honest chain and we can say that there are a lot of blocks here and uh uh so that is one thing to bookkeep that there are a lot of blocks here there are a lot of blocks here and then we say that um

after a time about a window length after a time about a window length consider the first time there is an honest block right so we we we we uh look at that block and the first time there is an honest block we um we note that down and then we say that uh um and then we go into the Dison block and uh consider this Peri in time which is as long as almost the uh window and then we say that consider the case that this uh that the number of blocks here is greater than the number of blocks here right consider the case

that so here is what we are going to do case one number of blocks here is greater than the number of blocks here in that case um if there is a honest block here we'll arrive into a contradiction uh how do we arve into contradiction so there is a there is an honest block here there is an honest block here and there are a lot of uh blocks here this immediately gives contradiction on this other prop property which is the chain prefix property which says that you know you cannot when there is a a fork and uh um when there is a fork you and you you cannot have honest block here and here um

uh and a lot of uh blocks before um why because the the prowess already gave some kind of a guarantee that honest blocks cannot have disagreement for that long right that so that's the high level idea of chain growth property uh so that so that we prove that's case number one and case number two if this is long if this part uh has a lot of blocks in the dishonest chain then um again um um if there is a block if there is an honest block here um there is a there is a technical caveat I um which needs to be considered you

cannot just write away apply the um let me see oh yeah um um just recalling if there no actually let me try to construct the argument here so if there is a block if there is an honest block here and this has higher number of blocks then the number of this has higher number of blocks then there is again a chain uh prefix uh violation why because uh the chain prefix violation is by a parameter that is again higher than the um higher than the the the amount of growth we have had in the honest chain which which by aor PR it happens with very low

probability um so that's a high level structure of the proof I don't know how uh how coherent that was with the so I hate to do this but I'm gonna have to kind of wrap this up uh it does look like the platform is working again and I think we're gonna try to get back on there and what I'm gonna do is I'm actually G to take this video and actually probably put it on the uh crowdcast at a later time so what I'm noticing is there's like there's probably going to be quite a few people they've just told me like a lot of the Europeans just went to sleep or they're going to sleep soon so they're probably going to watch a lot of this tomorrow so