Proof-of-Stake Protocol Design | Cryptography Seminar | IOHK Research

[00:00:00][Music] Professor Ivan dumo and Professor yasper bu nsen and I'm finishing my PhD now in the end of the year beginning next year and I'm also working uh part-time with iohk and Mario on all this cryptocurrencies protocols so first today the goal was to present to you this uh proof of stake protocol that we've developed and the security definitions that we developed and to show you more or less how our construction works so first of all if I'm speaking too fast or if you don't understand something please interrupt me it's no problem uh please uh raise a hand and ask me questions I don't mind if we stop in the middle of the presentation to answer questions think it's better than to leave it to the end now first of all before we start talking about the proof of stake protocol itself I'd like to know how familiar you are with some Concepts and then maybe tell you a little bit about these Concepts before we use them in the protocol so how many of you are familiar with commitments nice uh verifiable secret sharing nice coin tosin yeah and uh guaranteed output delivery for protocols that's a more uh weird concept but let's start reviewing this concept from the beginning so first I'll start with commitments and how you use it how you use this primitive to build something called coin tossing it was introduced in the early 80s by Manuel bloom in a paper that is actually called coin tossing over the telephone that's a funny actually a fun paper to read the way he writes is interesting so what is a commitment it's a protocol between two parties a sender and uh receiver and it allows the sender to commit to some information what does it mean the sender becomes bound to this data that it's sending so the protocols have two phases in general first the commit phase here the sender has a message as input message M and he wants to tell the receiver some hint about that message without revealing the message at first but in such a way that later he can prove to the receiver that that was the message he was talking about so let's imagine it like a box a closed Black Box where you put the message that's my ugly drawing of a black box with a lock let's say he puts the message inside this lock inside this locked box you can't really see the message it's a dark box the message is hidden in there and he sends the box to the receiver now the receiver has the locked box he can't really do anything with this locked box he doesn't know what's inside because it doesn't have the key and he can't modify really what's inside because it's a locked box now later in an opening phase the sender will send him the key to the lock box now he can actually open this lock box and get the message so what guarantees what security guarantees we have here here first in the commit phase when the receiver gets the lock box we have something we call hiding which means that the receiver doesn't know what the message m is he can't learn any information about message M now in the opening phase when the receiver uses the key to open the box and get the message we have another property called binding what does this mean it means that the receiver can be sure with high probability that the message M that he got out of the box is the same message M that was inside the box in the commit phase so he can be sure that the sender didn't change the message in some way if you can think that he had the Box on his side so the Senter couldn't really change anything now you might be thinking how do you actually build this from assumptions from cryptographic building blocks I'll just show you an outline a really quick outline of a very easy way to build this kind of primitive let's say you have a public key crypto system that's is shared by the sender receiver they know they have a key generation algorithm and an encryption algorithm this algorithm gives you a public key and a secret key right when he gets a security parameter now the encryption algorithm will get Randomness and a message and give you a cipher text C now how can you build a simple commitment of course it it can't be any public key crypto system but most of the ones you know like elgamal based on ddh uh and a modification of RSA can be used to do this kind of construction what you do here in the commit phase the sender encrypts the message under a certain Randomness that he samples he stores the randomness and the message let's say save Randomness and message on his side on his ad and he sends to the receiver the cipher text now it's an it's a public crypto system so here it's hiding the receiver doesn't know the secret key let's say that there's um I forgot the parameter here let's say that this public key was sampled randomly by the sender and the receiver simply doesn't know the secret key so he cannot extract the message and it's hiding all right now in the opening phace the sender will send the randomness the message and the public key now the receiver can compute the same operation let's put Prime here just to say it could be something different the receiver will compute the encryption under PK Prime R Prime of message M Prime and this will give him C Prime now he will check if C Prime is equal to C this see here now you can observe that if the sender is honest and he sent the same Randomness and same message and same public he that he used in the commitment phase then C Prime which is basically Computing the same operation as in the commitment is going to be equal to C which is the commitment that the receiver got in the commit commitment phase so that's a simple way if that's something I believe you're familiar with all public key crypto systems that's a simple way to build it now you have several constructions based more or less on this Paradigm of encrypting something sending the encryption and later trying to recompute the encryption and checking that you get the same Cipher text for one of the very famous uh results is by toin pson in 91 it's a famous commitment scheme that was only mentioned in a footnote in a paper about secret sharing that he wrote alone in for crypto 91 but that's a that's based on the ddh Assumption the same you use use for alal encryption and for many other public crypto systems such as kmer sh and so on easy to construct it works basically like this where the encryption is alal and uh you can build this kind of protocols in many different ways with many different kinds of security with composition or just Standalone it's a very rich there's a very rich literature on how to build this so I can tell you I hope you believe me that we know how to construct this uh from many past results that's something we understand well so I'm going to use this in the POS protocol in a blackbox way just going to say I have a commitment and uh I use it let's believe it works and we can construct this in many different ways so it's nice yes proof of State yeah PS is proof of State just so how I eras later so let's just establish some notation here I told you we have two phases commitment and opening I just want to tell you how I'm going to write commitment and opening in an easier way than writing all the boxes or public encryption so if the sender is sending a commitment if the sender is sending that information to the receiver such as the cipher taex in that toy construction I will say he's doing commitment R Rand where R is Randomness message I'll say this gives you a atomic thing C it could be group elements if you do it with Al M could be uh a big Vector field elements depending on how you construct it but I'll just call this generically a commitment and this is the box that I showed before so if I give you the C it's like I'm giving you I'm putting the message inside the box and giving you the box now receiver gets this when I'm opening I'll will say that I send open r m to the receiver and this is sending the key this is like sending the key to the box now the receiver can use this information C and the information open with the message to check that this message was indeed the one inside the box he will use the open information as the key to open the box and check that the message is is the one that the sender claims so here we have hiding when I give you the c i you know that you can't learn anything about the message and here we have The Binding when I give you the opening information you can be sure that you got the right message or you can detect that the sender was in fact cheating and he didn't give you the right message I'll use this notation because it's easier than uh writing the whole protocol or stuff just saying commit and open now what do I want to tell you about coin tossing so why do we call this this funny thing because it's literally coin tossing this protocol allows you to get a coin toss it over and get a random result when the coin Falls so how do you do this there's a very simple protocol there are many ways of doing this some very complicated but I'm going to show you a very simple construction based on commitments in a black box way for this construction I will only assume that you have a working commitment scheme and this construction was also shown by Manuel Bloom on his paper coin tossing over the telephone so this is all Bloom 81 or 82 I might be wrong it's a very old paper but the the both the notion of commitments and the coin tosing protocol were shown in the same paper now how do you do coint tossing let's say you have Alice and Bob Alis starts by getting Randomness R okay that's a b let's say not Randomness s she gets this this is a random Vector I'll just say I'm sampling this randomly from a binary Vector of size Lambda it's just a random binary string let's say something like that then Lis will sent to B a commitment to S now Bob has this commitment this box containing this random string s it's hiding so Bob knows nothing about s what Bob does now is to send back to Ellice some oh oops some new Randomness S Prime of the same size sampled randomly from the space of all uh binary strings of the same length as the original s Bob just send this in the clear no encryption no commitment he just sends this Vector S Prime now Alice opens the commitment so from here Bob gets he retriev he retrieves s now what happened here Alice has S Prime Alice has s that she sampled herself Ellis has S Prime because Bob sent S Prime to Ellis and now Alice opens her commitment so Bob also gets s that L is generated and they both have S Prime and S what do they do they exort s exor s Prime and let's say they get from this a s hat we know that the S hat that Bob gets is equal to the S hat that Ellis gets because it's the same operation sxor S Prime right now why is this secure and why can we be sure that s hat is in fact random even if one of the parties is corrupted even if one of the parties is trying to cheat so here Alice sends this commitment to Bob containing s so Bob doesn't get any information about s he doesn't know anything about s because the commitment is hiding now he's going to sample another random string knowing nothing about the original s and he's going to send it back to Alice now let's say how could they cheat here if Bob knew if Bob knew the original as from Alis in the beginning he could choose a an arbitrary string random string a such that and then choose a s Prime such that S Prime xor s is equal to a and then he would force the result to be equal to a but to do that he must know s and he doesn't know anything about s because it wasn't a commitment now what could Alice do she could do the same in this last step here if if it wasn't for the commitment Alice would know S Prime and then she could again choose an arbitrary string a and select a s that is different from the one that that was in the commitment but the commitment is binding so we know that if Alice tries to cheat and say and a different s in the opening then Bob is going to detect the cheating and he can simply abort the protocol and not care about the result because he knows it's going to be cheating now up to here do you guys understand that we can get random strings through this protocol and uh please if you have any doubts please ask me uh uh this is going to be important uh later so we can do that using commitments in a blackbox way so up to here everything is blackbox I don't care about how this commitment is constructed it just has to be hiding and biing so we can use any of the many constructions of commitments to build this protocol you can see it's a kind of simple protocol it only has three rounds and and uh it it works it gives you the random strings now let's think of a different situation we are thinking here about an adversary a malicious user that cheats but that always completes the protocol so here I'm saying that Alice will send both the commitment and the opening and that Bob will always send this string s but imagine that Ellis is a bit smarter and that she wants to outsmart Bob let's say she wants to learn as hats but not tell Bob let's say there's a prize whoever gets this hat gets some money and Ellice wants the money and she doesn't want to share it with Bob so she wants to learn as hat and then tell Bob bye-bye I know as hat I don't want to talk to you anymore so Alice if she's malicious with abort she can abort the protocol stop the execution right here when she receives S Prime she can just go away and stop running the protocol now what happens she knows both S Prime and S she can compute s hat but Bob Bob is just hanging there if he doesn't get the the opening he doesn't know s so so he cannot compute the final output so here we don't know if we have an adversary that's smart like that we don't know if we are ever going to get the output we might never get the output from from uh the message from Alice then we never get the output here so what do we do there's a whole line of research into trying to understand how we can do this better so first I can tell you it's impossible to do it perfectly in in three rounds I can tell you you can you can never do this and get a completely uniform string in three rounds if you're willing to do more rounds you can get Epsilon close to uniform for any adversary in any kind of asynchronous network then if you're willing to do many rounds that's a no result by uh cleave in 83 he showed that you cannot get fairness what do I call fairness fairness here is that all the parties get their outputs in the same way that nobody can cheat get the output but not give the output to the other one he showed that if we want to compute an exor we can't do this fairly with any protocol and then uh we need more rounds than three there are there are results now that show that if you have many rounds you can get as good as you want Randomness but still we are going to talk about a protocol that's going to run on a blockchain and it needs to run fast because we need the transactions to get in the blockchain fast so I don't want to do many rounds because if I start doing many rounds then um then what guarantee do I have that the that the protocol is going to run fast enough for the blockchain to advance so I want a protocol that is still three or four rounds but that has what I called guaranteed output delivery or God that's what people actually write in the papers I want guaranteed output delivery which means I want to guarantee from the protocol that I will get an output I want to know that everybody will get an output and I want to prove that that by the end of the protocol everybody gets the output now let's see what's happening here we have only two parties okay so if one of the parties is corrupted we have a corrupted majority we have 50% of everybody in the protocol corrupted the result I told you about that says that it's impossible to do this with guaranteed output delivery and fairness it's only valid if you have this majority of corrupted people now how do we circumvent the the impossibility results we know in this in all this cryptocurrency and blockchain protocols that we assume Hest majority and in this cases of cryptocurrencies we don't have only Ellis and Bob we have many people participating in the protocol so we and we assume that more than half of these people are honest that's something we have to assume uh I can also tell you that if we don't assume that more than half of the people are honest we cannot achieve consensus I guess you've been uh discussing consensus protocols uh for Bitcoin and I mean I mean consensus by this Byzantine agreement protocol that lets everybody agree on a value even if you have an adversary in the middle shouting different values there's a result that for synchronous networks what do I mean by synchronous networks I'll talk a bit more about that later I mean that it's a network that where I also have a guarantee that when I send you a message you get the message so synchronous Network would be the let's say the mail system you put a letter on one side the letter gets out on the other side on a finite amount of time now let's say I put the letter around a dog's neck and I kick the dog on the street and the dog runs around I don't know if the dog is ever going to arrive at the destination that would be a asynchronous network in a asynchronous network the adversary is all powerful the adversary can drop messages the adversary can delay the delivery of M messages and then we have different uh lower bounds here for synchronous networks we know that if we have heal plus one no okay that's that was a bad choice heal of The Players let's say we have n people participating in the protocol in synchronous networks if we have half of the people plus one that are honest this is what I call honest majority we know that we can achieve consensus and it's nice that we also know that we can do this with guaranteed output delivery we can do coin tossing with guaranteed output delivery now in asynchronous networks the case gets much more complicated there's a proof that it's impossible to do any consensus unless you have 2/3 plus one of honest parties it gets much more complicated and uh maybe if we have another discussion another day I can show you a very nice proof of this that takes only actually five minutes and it's only by by drawing it's appr proed by Nancy Lynch it's a very nice neat proof you can show that even if you have all crypto in the world if you assume anything if you assume IND distinguishability obfuscation you cannot do this it's an information theoretical proof it's impossible but well we're working on cryptocurrencies and most protocols they always assume honest majority so let's use this Assumption of honest majority to make it easier to circumvent this impossibility results and get what we want to build so just so you know I'm I'm going to start working now with the assumption that we have honest majority otherwise it's much much more difficult to construct any of these things and you end up in the situations where you need many rounds a lot of communication and you don't even know if the protocol is going to finish the question of how how do you deal with uh asynchronous cryptographic protocols when you try to write proofs by simulation what happens was only answer this year in crypto we didn't know what happened with asynchronous networks for most crypto protocols because uh there's also a proof that the the you can't say after how many rounds the protocol is going to end the only thing you can say is that after let's say our rounds there's a probability Epsilon close to one that the protocol ends but it's a probabilistic termination argument you don't I can even tell you the protocol is going to take five six or a million rounds so we didn't even know how to deal with this in theory how to write proofs about these things now some guys came up with a compiler that turns these things into uh it wraps it in UC functionalities that deal with the probabalistic termination super complicated huge paper and so we we stick to the to the easy case that's what everybody's doing if you've been looking at the other papers like the the paper by gai kayas and leonardos on the Bitcoin backbone protocol and uh other papers like zero cash or the hog paper they are all dealing with the synchronous model just so you know I'm not cheating too much because everybody is we we're still beginning to understand how this protocols work so we start from the easy case synchronous messages Standalone protocol we're not pro I'm not going to prove anything about composition I actually know how to prove that this protocol is universally composable but we didn't write that yet so I I think I think my proof is correct but we need to write it down first and uh and check the nice thing is that the protocol is basically blackbox so using some black magic in how to define time in the UC model for synchronizing messages and using other other you see uh building blocks like you see commitments and so on I think I can actually prove it composes but today let's talk about Standalone just one one copy of the protocol being executed without any interaction with other protocols and that's also the setting that the gkl paper on the Bitcoin backbone and all these other papers uh apart from Hawk Hawk is proven composable actually but all these other papers they are assuming that we have a standalone setting with synchronous networks the first paper that tells us anything about asynchronous networks is by ABI shalat and Rafael pass and one of their students it's on nint now I think it got accepted into CCS but they show that the Bitcoin ah cool but that's the first paper that actually manages to show that the Bitcoin protocol under certain conditions can work on asynchronous networks but it's a the the actual technique that they use to prove that is not in the paper they they have a they have a better idea they had a very nice idea on how to begin with the Bitcoin protocol and bootstrap a protocol for consensus for asynchronous networks that need certain precomputed information they can do this pre-computing using the Bitcoin protocol and then and then they jump for this other protocol that's from the 80s and uh then they can prove that they can prove that everything works but on that paper they just write the theorems that it works they give a they give complicated arguments but I saw presentation where they show uh the actual technique that's going to be in a upcoming paper so they do the it's complicated so we stay for now synchronous Standalone model now I can show you I told you that we can do this with guaranteed output delivery but I'm just telling you you don't have to believe me so I can show you a very simple transformation that we can use to turn not this protocol because it only has two parties let's say we put Charlie we put a third party here then I can show you how we can turn this into a protocol with guaranteed output delivery in a very simple uh transformation that transformation is going to use something called verifiable secret sharing and I can explain you really quickly what this spr allows us to do I'm not going to show you how to construct it because it takes a lot of time but I'm going to show you in a very high level what we can do with verifiable secret sharing and how we can use it uh if we have to take a break I don't mind uh no I'm okay but if you guys if you guys are tired we can uhbe just sure I I'll I'll keep a ER raising and then uh yeah I'll prepare the I'll prepare the next screen let's say good oh should we start okay no it's all right I don't know good so we can restart talking about verifiable secret sharing it's a huge name so I'll just say vs s now just with a little bit of background what is secret sharing itself without the verifiable so secret sharing was introduced by adish Shamir 79 on this paper how to share secrets one of the most silent papers given by Humanities people they they they find this paper on Google once I looked on a Google Scholar of for the citations of this paper and citations to other more modern papers on secret sharing there's a bunch of people in Humanities that study stuff like the sociology of Secrets the anthropology of Secrets then they cite the crypto papers because they don't really read the paper they just see a paper that says secret and they cite it in their uh in their references it's funny but the actual idea of this paper was to tell you what do you do if you have a secret s and you have a bunch of people just going to call them A B C D the secret is very important so you don't trust anyone to know the secret you don't give the secret to one person it's like uh nuclear weapons activation you need several Keys you need two people with two different keys to turn the keys to launch uh nuclear missile same thing let's say you have a secret that activates a bomb that destroys a lot of stuff you don't trust one person so you want to give to a b c and d little bits of information of the secret such that alone these little bits of information don't mean anything but together they can be used to reconstruct the secret so we're going to call these bits of information shares as a share b share C and share D now what I'm just going to write down in terms of generic algorithms I'm going to say I have an algorithm share that takes in some Randomness I'll even omit the randomness because in our constructions we just sample we don't need need to set specific Randomness we just assume it has internal random coins the share algorithm takes in a secret and outputs several shares in our case I'm calling them A B C D then once you have those shares the shares the guarantee here is that you define I'm defining here a very specific ific kind of secret sharing a t out of n secret sharing what does it mean if I have t + one shares I can get the secret if I have the shares or less than less than T I cannot get the secret so how do I reference getting the secret I'm going to say I have a reconstruct algorithm that takes in several shares we actually change this because this gets hard to reason about I'll say we have shares S1 to SN just because I need to tell you the number of shares you have now this gets shares SI this just an index one to s i t + 1 what I mean here is that you can get any t+ one shares out of the end shares any of them are okay I don't need it spe specific ones and that will give you the original secret now as I told you this is a very special kind of secret sharing I'm talking about which is threshold secret sharing that's what Shamir introduced what does this kind of secret sharing allows you to do it allows you to give you many shares pieces of information about the secret to several people and they can only reconstruct it if a large number of them comes together if more than three of them come together to reconstruct the secret if it's less than T they get zero information about the secret they don't know anything now these days we know that we can actually do this such that you can only reconstruct if you get very specific shares we call this an access structure it's a mathematical object object that defines which specific shares you need to be able to reconstruct the secret I could for example build a scheme that can only that where the secret only gets reconstructed if I get share one share five share 17 and Share three with arbitrary numbers here I could Define such a scheme and we know how to build it we know how to build this for any access structure which is what tells you how when you can reconstruct but for our case we only need the simple T out of n you might be thinking how do you actually build this to build the more complicated uh t t outut ofan where uh any sub any subset with t+1 shares reconstructs things you need a bit more involved construction which looks like a r Solomon code if you're familiar with that kind of uh coding Theory stuff and today we know that all these secret sharing schemes are very tightly connected to code to codes to error correcting codes and coding Theory but I don't want to get in the details of this because uh those constructions are complicated you have to define a right kind of Rich Solomon code or generalizations of that with motivar binomials to actually build this I just want to show you a very simple example or how you can do what would be a n Out of n where you set t equal to n where it can only reconstruct if everybody comes together I'll show you here so we start with s we want to get share s a right we say the share S A is equal to s+ R where R is some random string now we say that chair SB is equal to let me put here R RB where B is a random string we say that share s c is equal to S + RC where C where RC is a random string now finally we have share SD share SD is equal to all let's just so it makes sense I I'm going to say I'm working on a binary field here and these are actually exors now SD is going to be the exor of all the random NES no did I make a I might have made a mistake because these things depend on the number of no did I make the mistake oh no I didn't make the mistake mistake it's the right number when you write these things for many parties it's the so let's see what happens these are the shares these are my sharing algorithm it samples this R A RB RC compiled shares ABC just by xoring the randomness with the secret then the final shares just exort of all these random strings they are the same size of course now how do we reconstruct we simply exort s SB s c and SD and we know it's going to be equal to S why you exor sa a and SB s exor s goes away you have R A exor RB now we exort r a exor r b with SC c s comes back now we have S exort R A exort RB exort RC finally you exort SD and then R A RB and R C go away and you're left with s that's a very simple additive secret sharing scheme where you need all the shares to reconstruct but please believe me that you can actually build this for any access structure specifically for this case any T out of n thresold access structure there's a the paper it's actually one of the shortest papers I've ever seen in my life the original secret sharing paper it's two pages long you can read it really quickly if you know a little bit about re Solomon codes you read it in 15 minutes because it's a very short paper but still very deep result actually so if you're interested you can take a look at that it's a actually quick to understand when you read the paper Shamir writes much better than I can explain you so it's a you can find information there now what what is the problem here with this notion that I've been constructing of secret sharing what if the guy who's Computing the share algorithm here is malicious what if the adversary is Computing the shares and then the adversary gives us let's say we're all here and I'm giving you shares and I'm a bad guy I could give you shares such that if uh Mario me and T say get together we get one secret then I get I do something else I get give different chairs such that if uh isida and yeah Manda and me get together then we get a completely different message or I give you chairs such that if I give you one so and yosa Har okay so I want to learn your names too and you inom good I just want to try to remember if I give one har and yoshida's uh shares then they get nothing when they try to reconstruct they get error they find an error and they can't reconstruct so it could be a bad guy doing that and there's nothing preventing me from doing that with Shamir secret sharing based on read Solomon cols or with this secret sharing I could give you specific s SBS C such that when you exort them they something bad happens you get an error you get some value that doesn't make sense so in order to deal with these situations people came up with verifiable secret sharing and a little bit of motivation why did people even think of this situation where you have a bad guy giving out bad chaires one of the original applications that people had in mind when they were looking into these problems was uh secure multi party computation where you have a lot of people who have inputs and they want to compute an output a program on the inputs and get an output without revealing the inputs that's secure multiparty computation and in the late 90s people for looking into what you could do can you make this secure when you have uh a third of the parties corrupted can you make it secure when you have less than half can you make it secure when you have more than half so the answer was if you have a Hest majority meaning that situation where half of the parties plus one are honest you can do this secure multiparty computation and in a 9 Rabin not Michael Rabin but his daughter uh T Ren and Beno introduced the protocol for doing this MPC with honest majority where almost half of the people can be corrupted and to do that they introduce verifiable secret sharing as a tool and develop started developing the theory so what does it allow you to do it it gives you an extra algorithm here that's so there are different ways of defining it I just want uh simple definition that we can use in the protocol has this very fine algorith know let me Define in a different way I don't want to talk about the verification directly what this what you can do here is that you extend the reconstruct algorithm let me write here now instead of only adding t + one values you say that the reconstruct algorithm gets all values but then you think that doesn't make sense why does it get all values then it's not t out of n then it's N Out of n no here some of these values can be empty I could have let's say S1 S2 S3 blah blah blah and I could when I'm reconstructing now this is an interactive procedure the different parties talk to each other to reconstruct they can simply set let's say S2 was a bad share you set it to per empty you don't consider it let's say you got some crap here random random trash you just put here the random trash but as long as you have t+ one Shares are correct they're correct you can still reconstruct and the parties can talk to each other they can come together and talk to each other such that if you have t+ one honest parties talking and you get that if you have more than half of honest parties you just set the T to be uh half then they can always get the guarantee here is that you always get S even if you have an empty share a share with random stuff even if you have is adversarial shares that's the guarantee of verifiable secret sharing and well in some schemes if you cannot get S you won't be fooled you won't get a value that you think is s no you get error you will detect that's a weak verifiable secret sharing you will detect there's an error and you abort but this guarantees that the adversary cannot cheat on you and make you believe you have the right Secrets without really having the right secret ah yes yes that that's a always if you have oh you have doesn't matter yeah you need you give an inputs but the let's say we are in a case where we are only t plus one people getting together we put in our inputs in you don't know but theut or not you use it anyway you use it anyway and the algorithm the protocol takes care in the in if you think of Shamir secret sharing the Reconstruction is very simple you do it locally once you get the shares you run some interpolation like read Solomon like in Solomon decoding and you get the share in verifiable secret sharing this reconstruct it's not necessarily local anymore it might require communication between the parties getting together apart from just sending the the just sending the secret you might need to send some extra verification information I don't want to get into the details because when to actually Define this in all the details I would take some hours but you have of the message exch oh yeah yeah yeah we can say this we can say reconstruction is going to take this many messages exactly we can we can say that and it's not many messages it's usually two rounds three rounds for reconstruction because you need to do what you do inside this reconstructor here that I'm showing as a black box is at least t+ one people come together the they exchange their shares and extra information let's just let me just call it extra information for the other shares you don't care you input empty shares or random stuff and the protocol makes everything happen you use the extra information to check that the shares are correct and correct them if if they're not so if I am a party and after I don't know how many number of message if I don't sh I can just send space yeah if you have t+1 parties you get your message and you know it's I mean when I try to fill the fields there ah yeah after some all the all the communication I don't one the just yeah you leave it empty or input a random string it depends on the actual construction but you can have I'm just saying you get all of them because you you input something but if you don't have the actual share you just put some random stuff and the algorithm will take care of uh how this gets handled how can you construct this it's a bit more complicated then you need to generalize read Solomon codes and have a and and then in read Solomon codes you have a univariate polinomial a polinomial on X of a lower degree in this case you need a pol polinomial on X and Y multivariate polinomial with higher degree that allows you to to get this extra information that you will use to check the shares I'm not going to tell you how to construct this because it's it takes it takes a while the nice thing is we know how to construct this in many different ways we can construct this based in a we have blackbox constructions of verifiable secret sharing from regular secret sharing from what from the easy regular secret sharing I told you before we have a specific constructions based on uh on specific algebraic structures uh we have constructions based on cods directly from CT we have many constructions and it can be done efficiently I just want you to believe me on this uh I can point you out to papers about this if you want to read the constructions but it can be done if efficiently and uh in in a small number of rounds even the Reconstruction even though you need communication it can be done efficiently and it has what but the takeaway message here is that with this verifiable secret sharing if you achieve the threshold you get the right Secrets the guy who shares the secret cannot cheat on you he the worst that can happen if he cheats is that you detect and aort protocol in some constructions but you know that when you get a secret that was the right Secrets now I told you all about this secret sharing things and how this verifiable property means that you get the right secret now how do we use this to build protocols where we can get the output even if a guy drops out the guy stops uh working on the protocol or uh even if there's an adversary actively corrupting a party and doesn't send you the message you need so how do we start with this this is also a technique that started with a rabing and and and Beno in that paper how to use vsss for this kind of stuff uh let me show you it's pretty simple for our case at least it gets complicated when you actually want to do this transformation for big protocols it's complicated but for the coin tosing it's okay let's say we have Ellis Bob and Charlie and they want to do coin tossing you remember we had that template for coin tossing from Bloom that's basically easy to extend to any number of parties how you do that now you say that L is commits to sa no I'm going to use this for let me use a different letter um um V VA Charlie commits to [Music] VC and now Bob sends them both [Music] VB and then they open the commitments so it's just the protocol I showed you before between Ellis and Bob Comm me to to VA huh yeah are the me those are the messages just random strings then uh that if you look at just this it's just like the other protocol L is commit to a random value VA then Bob sends her another random value VB now she opens the commitment to VA it's just a lot more arrrows because we have more people and and we have to send double messages to everyone open so they doing commitment pairwise yeah pairwise they're committing pairwise here you could do it differently you could actually broadcast one commitment but I don't let's keep it uh simple then uh it's basically the protocol between Ellis and Boba showed it before commit to random string send random string in plain text open other random string exor everything did you get the idea of replicating the protocol that you do this protocol but between everyone commit to random string open random string send random string and clear so if you have the idea that that's how the protocol is going to run I don't even want to talk about the commitments or the messages in the protocol I want to talk about what you do before the protocol starts with the inputs with the VA VB and VC to get guaranteed output delivery that's a generic transformation idea originated in uh Rabin and Beno and now we can people actually proved that this idea can be extended to any any complicated protocol it's a nice paper by Yehuda Lind and I think and some other guys in Israel from 2006 you can use the same technique so what do you do Ellice let's say Alice is going to use her VA Bob's goingon to use his VB and Charlie's going to use his VC correct so what Ellis does before the protocol starts with the commitments Alis is going to share VA is going to send to Bob let's call it v b v Bob a a share of va to Bob and to Charlie V Charlie a Charlie is going to do the same it's going to share VC and send v l is C2 Lis V Bob C2 Bob now we actually don't need to do this but I'll also say that Bob shares VB just to make it symmetric B shares VB and send to L is V Lis B to Charlie V Charlie B what happens now now everybody has a share of the other players inputs so now Bob has a share of Alice's input and Charlie has a share of alysis input so they can come together and reconstruct the the yeah Shar breakie yeah in this case this I'm showing the three-party case yeah so this this can be extended to any number of parties you could have any number of people doing the sharing then you simply split your input into shares for everybody else now if if we have honest majority if we know that half plus one of all parties are honest we know that they cannot retrieve the input before the protocol starts because let's say here that we have honest majority it means that at most one of those guys is corrupted so if at most one of them is corrupted he cannot go to another guy and say hey are you corrupted too let's get together puts of the other guy and cheat on him you can't because you're assuming that you have honest majority so at most one is corrupted so let's say let's say that Charlie is a bad guy he doesn't like Alis and Bob and by after we do this sharing we do the commitments and openings for the for the random values and Charlie never opens his VC he gets VA he gets VB from the openings he computes the outputs then he goes away says bye I don't I don't like you I'm not I'm not giving you the opening to VC now what can Ellis and Bob do Alice has VC Bob has V bobc they have two shares of Charlie's input they can come together send the shares to each other vac vbc they can reconstruct Charlie's input and they will get the same output so problem solved we get guaranteed output delivery if any if if we have honest Ma majority and the bad guys the dishonest minority the less than half people that are corrupted try to cheat on us by not giving us their input their their their last messages or by by giving us a wrong message we can always use the shares that we had of the the bad people's inputs to reconstruct their inputs and run the protocols in our heads let's say if we have the input we just we and we saw all the protocol happening we can just use that input and have a virtual machine running our head with that input as the bad guy and run the protocol again and we get the input because we verifiably secret share the input in the beginning now why do we need oh that was the microphone why do we need verifiable secret sharing because let's say I'm a bad guy I'm Charlie and I'm planning to cheat I start the pro knowing I am going to cheat on Bob and Ellis I want the output and I don't want them to have the output he could just share this maliciously he could give Alice and Bob invalid shairs of his input and say that well this is the valid share then disappear when they try to reconstruct they don't get anything so you need verifiable secret sharing so that you are sure that even if Charlie is a bad guy you can still retrieve his input if he tries to cheat on you so that's the that's why we need all this verifiable secret Chari Machinery then we can transform basically any secure protocol into a protocol with guaranteed output delivery why do why do we need guaranteed output delivery in this coin tossing protocol because inside the proof of stake protocol we are going to use this coin tossing with guaranteed output delivery as the main piece for keeping the protocol running during the protocol we will need Randomness this Randomness can't be known in advance so I can't even this Randomness needs to be renewed I need new unknown Randomness after every period in the protocol I'm going to show you later I can't just tell you ah look at electromagnetic radiation and learn Randomness I need to get this Randomness from somewhere and I need to be sure that no adversary can trick you into accepting any Randomness that the adversary knows because then he can steal your money and uh what an adversary could do he could be a bad guy like Charlie start the protocol the commitment with the commitments never open his commitment get Randomness use his knowledge of Randomness and the fact that you didn't learn anything to steal your money so we need to have guaranteed output delivery to make sure that everybody gets uniform Randomness since we are working on a on a majority situation then we're good we use this technique T style and then uh the problem solved if you want to also if you want to read more about how this uh produ this vsss works and this transformation works I can point you to the papers where they discussed that it's a in in this case we're using just a very specific case of this for coin tossing because that's what we need for the protocol so this was what I wanted to introduce first because after you understand the coin tossing with guaranteed output delivery and you understand that you can build this from commitments and verifiable secret sharing then the protocol is much easier to explain then we just use this as a black box so let me just put here a simple diagram showing what I want you to remember from all these if if you have to remember something basically what I want to say Here Is that ah okay no problem ah the Tes in the audio does it work oh good so I just want to finish this first half with an outline of all these things I told you about and how they connect to each other to get to the final black box that we're going to use inside the protocol so we started with commitments then we talked about verifiable secret sharing as I mentioned to you you can build this in a black box way from Secret sharing itself the easy kind that doesn't have any guarantees this alone in implies coin tossing with that three move protocol I showed you commit to random value send random value open random value this is imply coin tossing but still no guaranteed output delivery now we combined both of these things that was a bad error uh to get guaranteed output delivery for coin tossing and this is what we're going to use in the protocol in the protocol we're going to we're going to be doing all the the time saying we're going to all the time say something like call coin tossing with guaranteed output delivery let's imagine this big black box is going to be there in the sky somewhere it's God after all then we we're going to we're going to be able to call this and get uniform Randomness for everyone and just because I didn't want to tell you this exists and believe me you know that this can be constructed in a black Black Box way from well not really yeah it is blackbox in the end it just V assess the inputs from coin tossing that can be inter turn constructed from commitments plus verifiable secret sharing that can be inter constructed from Secret sharing now commitments themselves can be constructed from a huge number of things can tell you from some important things or is a OT but public key encryption ah oblivious transfer sorry I I work with this so much that I forgot to explain what obious transfer is it's a another primitive we can talk about this another day but just want to say that you can construct this from so many things and even sudo random generators what I want to say here is that these things can be constructed very efficiently so you can even construct this with the S random generator uh if you're in in the Standalone model there's a beautiful result by Mono in 91 that shows how to construct this in a very very efficient way so just want you to know that this can be constructed efficiently so this is the uh takeaway message for this first half we can do God coin TOS in combining these things and I hope you understood a little bit of how these different building blocks work and then uh we use them to build a final protocol just using this as a source of Randomness thank you guess we can break for lunch yeah I'll live this year uh this it's okay okay so now that we've already talked about how we're going to obtain Randomness for this protocol to work then I want to tell you a little bit about why we want to consider this mechanism called proof of stake why it's good how it is different from what people were doing in Bitcoin already and in other cryptocurrencies so first of all let me just acknowledge people that were involved in this work this was a collaboration with the ailos kayas who's a professor in the University of Edinburgh and the University of Athens he's the K in that gkl paper of the Bitcoin backbone protocol and uh Alexander Russell and uh Roman nikov and uh Nan ago student with a complicated Greek name um but that's a that's a project that we've been working on for the past two months or so and right now we have a final protocol and proof that we believe to be correct and uh I want to show you where we are at now and what are the next steps into turning this into a functional practical cryptocurrency consensus protocol so first of all you know that Bitcoin uses a consensus protocol based on this mechanism called proof of work or p as I'm abbreviating here so we need this in order to get distributed consensus that has some incentive for people to devote energy and computational work to in return for money you know when you mine on bitcoin you get a base coin transaction that gives you new coins that you get as a reward for Mining and finding a block now what happens with Bitcoin that is a bit annoying first of all there's a clear distinction between coin holders and miners if you want to mine it doesn't matter if you actually use the system to perform transactions with your own resources Financial Resources you just have to have computational resources the people who actually have lots of money invested in the system of course the miners invest money in Hardware but they don't necessarily have to have lots of Bitcoin or of the actual currency I mean the people who actually have lots of coins in the system don't have much control unless they also invest a lot in computational resources there's a problem that you know that by Design the rewards you get for mining in Bitcoin are decreasing every number of years the amount of coins that you get back if you find a block gets divided by two it's HED it happened is year already and what is the problem once this amount of money you get for mining gets really low then the incentive for people to buy very expensive hardware and actually do the mining will also go really low so how do you keep the system working how do you keep people uh wanting how do you make people want to actually invest resources in mining if they are not going to get that much in return so this is a problem and that's something that happens by Design in Bitcoin the one of the biggest problems the control of the Bitcoin network of the Bitcoin system is extremely centralized in the hands of very few very powerful miners the people who have have most of the mining equipment they can actually decide what happens with the system because they control how many blocks are being found by per second and and they control what goes in the trans in the blocks that they are generating and uh we know by now that a handful of people control almost half of all the computational power or even more than that most of them are in China that's a statistical semi statistical data most of the mining power comes from China and there are around five mining pools that control basically half of the whole whole computational power of the system so decentralization is bad the whole idea of having Bitcoin of having blockchains and cryptocurrencies is achieving decentralization and not being uh forign to trust in one Authority or let's say a group oligarchy of five authorities I mean there miners with all the power so we have this clear problems that are affecting the Bitcoin environment already in a practical scale the problem of diminishing rewards is really serious because if you think 10 years from now really why what what will be the incentive for somebody to spend millions of dollars buying equipment if he's not going to get the same kind of money in return where's the where are the profits so why will people keep mining Bitcoin what happens with the network then and uh it's scary that just a few people control the network basically and they can decide what happens do do we want to trust just a few people no we it's not nice we want through decentralization we want real incentive for people to mine or do whatever the system requires to stay active so then the notion of proof of stake showed up and I want to compare both Notions so you see how Bitcoin with proof of work and how a currency based on proof of stake compared to each other first of all what do we mean by proof of stake in a proof of stake mechanism the amount of money you have in the system is what determines how much control you have on the system the more money you have the more blocks you should be able to generate in proof of work the amount of computers you have determines how much control you have on the system the more hash functions you can compute per second the higher your probability of generating a block now the in the POS style system the more you have the more you control the more you having money in the system but you can think of it as a stake in a in a gambling game you have a lot of money which gives you a lot of control over the system if you do bad things if you try to cheat if you try to attack the system people will lose trust start selling their coins your stake your large amount of money in the system will decrease in value so the incentive to run the protocol honestly is basically that you're going to lose your money if you use your control in a bad way now let's see some points here that's what I was saying in proof of work this is an actual minor he owns a big mining pool and those those shelves are full of boards with ASX with integrated circuits designed specifically to compute many hash functions a second and he he actually said once in an interview that he wants to control Bitcoin he said that I want my mining pool to control half of all the hashing power he didn't succeed by himself but as I told you you have this five mining tools or so that do control half of the hashing power so here in a proof of work situation more computational resources equal more control the more of these boards you have the higher the probability you generate a block so you get more control this is a bad thing but there are also good things I don't want to tell you that proof of work is bad uh it's completely bad we know it works in practice it's running Bitcoin is running people the incentive structure works people are actually spending money on buying this ASX to mine Bitcoin because they get something in return at least until the rewards get he so much that they don't really get much in return we have a security analysis so that's nice ni we can prove that this works that this is secure according to uh reasonable security definition so we have provable security for this it's good we know it works we know it is secure it's not just a heuristic argument one huge problem resource waste this is just a huge waste of electrical energy running all these zics all those little boards it spends a huge amount of money there's actually an anecdote of uh miners in a specific city in the US where they had a spe there was a special deal with the electric company that they sold really cheap energy then a lot of miners moved there and started running their equipment there and uh in the end the electric company raised the prices because they were just depleting all electric resources I've also heard that some of the miners in China try to stay located close to power plants so so they can get good deals and because they need a lot of energy and what is this energy used for for nothing your Computing hash functions on random inputs they're good for nothing you're not achieving anything it's not any calculation that can be used for any other purpose rather than generating a block only one none of these outputs will be used all the billions of other outputs will be thrown away and the energy is just lost I mean these days with all the the worry we have about the environment and energy waste this is a really big problem and at some point we can't just keep growing mining power and hashing power like that because we have serious energy limitations now POS it's a different situation the more you have to lose if the system fails the more control you have that's the idea if you have more money in the system more coins you get a higher probability of generating a block but if you have more money and you do something bad the system crashes you lose that money so you got to really think if you want to do something bad you want to follow the protocol so your money keeps its value now what I'm going to show is this is a situation before our work then I'm going to show you how we solve this problems until now this was a nice idea it had been proposed first in forums by practitioners but there was basically no real understanding about this or people us using this in practice there are several coins that implemented proof of proof of Stak style mechanisms but they aren't as widespread as Bitcoin and other altcoins they were smaller experiments they didn't really grow even worse security the previous schemes based on POS had no proper security analysis basically because we didn't even know how to define security for the systems well enough to prove that they are secure as cryptographers I know you were aware that you need a security definition before you can say anything meaningful about a protocol or a cryptographic scheme so until now we didn't even know how to define security much less prove it secure all the protocols that were proposed were euristic and for many of them there were already practical attacks so the situation there was terrible and that's something that we're going to address one really good thing last waste here you don't have to waste a lot of energy to generate more blocks you just have to buy more coins that's the thing now a bit about what happened until now in terms of posos based cryptocurrencies there are some as I told you like next blackcoin pcoin and nocoin that implemented some flavor of proof of stake let me tell you a little bit about some details of some of these implementations and how they implemented the POS mechanism and why it was a problem in peercoin you have a situation like this the ash computer is basically the same as in Bitcoin you compute a hash of the previous block Uh current time and your current outputs your current state of the blockchain and it has to be is smaller than a Target D just like in Bitcoin but then the new the new thing that implements the POS here comes in the second terms the there's a Target that's fixed let's say it's small but the the more coins you have the more this right hand side of the equation grows because you're multiplying the Target by your number of coins and you also have this time way of your coins which means the the longer you have possessed the coin let's say your input transactions that gave you those coins are 10 years old they have more weight then you get a bigger value here than somebody who just got some coins a minute ago so basically it makes it easier to find a new block to find a hash whose output is smaller than the right hand side of the equation if you have more coins and in this case if your if your coins have been in your possession for a long time now what is the problem with this approach first this situation where in the letting the time that you have possessed a coin influence the probability with which you find a block opens up the system to some attacks one of the tax is pretty simple intuitively speaking you can get a coin or a few coins not much leave them there for a very long time wait for a moment where people who are transacting a lot of coins really fast and not keeping their own coins are generating blocks and then you use your larger time we even though you have less coins even though your number of coins is smaller you use your very large time we to get a block faster than those people who are actually doing more transactions than you they have more money flowing but they transact a lot then you get to generate blocks with a higher probability and you can do double spending and so on and there are other other problems like bribing you can collude several people with several coins can easily collude here to to to aggregate their number of coins and time weight so they get a higher probability of jointly generating a block and they can use that to do a text so there's several of this problems later they've proposed getting rid of this time way parameter at least but still just doing this approach here doesn't really let you prove security of the scheme it's uh it's very hard to actually prove that that first of all even if everybody's honest that the probability the the probability that you get a to get to generate a block is actually related to the number of coins you have and how the how exactly this relation works it's hard to show that so other proposals showed up nocoin got that approach and from the start got rid of the time we now the only thing that nocoin uses is the number of coins that you have they also introduced faster block generation but then we have another problem as we know from empirical studies and also from the analysis in the gkl 15 paper the network delay affects how much security you can actually get if you generate more blocks and the delay stays the same there's a higher probability that somebody can cheat in the protocol so this might introduce some problems this introduces more rewards in nocoin and it has a mechanism for punishing people who try to do malicious forks and double spending if somebody gets detected doing this they lose a certain amount of money but still no formal analysis just an empirical protocol and empirical implementation ristics now in those schemes where do the coins come from it's a bit complicated right because if you add block rewards if you say if you generate a block you get a big reward like it happens in Bitcoin what will happen is that the Richer will get richer because the Richer users with more money generate more blocks and then they would just get more money because they generated the blocks and in the end only very few very rich users will be generating blocks we will end up with centralization so there are some mechanisms proposed apart from the standard take transaction fees and the transaction fees are are your source of reward there's some ideas these guys in NCoin and pcoin they they had this idea of adding a reward for Block generation that is proportional to the number of coins you already have times the number of days you've been idle the number of days you haven't generated a block so let's say if I generated a block um a year ago 365 year days ago I get the full reward number of coins plus a coefficient that shows how much percent of your coins you get as a reward but if I generate a block every day I only get 1 365 over 365 of the reward so if I'm generating many blocks over a whole year you can see that I'll get the same number of coins as reward as a person who generates only one block in the whole year because here it's proportional to the number of vital days so the idea here is that everybody over a year makes the same amount of money in rewards independently of how much money they already have they want to eliminate the Richer getting richer problem with this approach in peercoin this percent here is 1% they just give uh they just give 1% of the number of coins you have now in nocoin they have a diminishing reward system where this starts with 100% of your coins and as you earn more money and as you use the system longer it declines slowly to 6% the idea behind this is that they want to keep the incentive high enough so that people buy coins in the system and keep the system working now still those models are purely euristic uh protocols as you can see from the previous equations they are a simplistic in way implementation of proof of stake you simply multiply the target value by the number of your of coins you have and you hope I mean intuitively theistically yeah the probability that you generate a block grows with the number of coins it's easy to see that but still showing the exact relation how this probability actually relates to the number of coins it's not so easy it's not so easy to show that you get that you get selected with uniform probability according to the number of coins you you have it's not that easy so we have these problems now something came up that that works interestingly it's a paper that still mostly eristic but they try to formally prove that some attacks are impossible against their system and they introduce some interesting ideas first of all they have a randomized selection of miners the people who get to choose the get to generate a block are selected by extracting Randomness out of the blockchain using an extractor and using this Randomness to run a procedure called follow the satosi which I'm going to explain in detail later that this procedure when this algorithm if you give it uniform Randomness it will select the stakeholders with uniform probability proportional to the amount of coins they have this procedure does work it's really easy to see that it does select the [Music] the stakeholders that will generate each block with uh with with a probability that is directly proportional to the number of coins but for that you need the randomness what they propose here use this extractor what is complicated is well you can use an extractor sure if you want to give an asymptotic argument you just say you let the blockchain grow enough and when it's long enough you know that the extractor is going to extract real Randomness you assume the Min enthropy is high enough but if we're talking about actually implementing this with concrete parameters then you have to ask yourself when is the blockchain long enough when there's enough min tropy in the blockchain to guarantee that when you apply the extractor you actually get uniform Randomness it's hard to for many for most extractors that fit the requirements for this kind of application it's very hard to compute concrete parameters so we were left with this problem but it still they introduced this very interesting idea of how to actually select the minus randomly with the proper probability they have a formal analysis they say they don't have a security definition that they prove that they use to prove their system secure but they least several attacks and then they Pro that given certain assumptions for example that you have an extractor uh those attacks don't work against the system but still no formal model they try to estimate concrete parameters for the uh not for the extractor but for this randomized selection of miners they implement this follow the satosi scheme and they see how fast you can run this how well it scales by the way the paper here is by bentov at all it's not published as far as I know yet but it's on the archives it also has the scheme also has a nice way to punish malicious Forks you can take people's money away if you see they're cheating which is a good way to incentivize people to not cheat to be honest now the initial distribution of money is unclear they don't really set a specific way to distribute the initial coins what I can tell you is one way that people have been doing this uh in in Practical schemes is by doing a IPO initial public offer you pre-mine a bunch of coins and you tell people well I have this bunch of coins do you want to buy some of them before the blockchain starts running before the beginning of time for the blockchain you distribute the initial provision of coins between different users and then you run a blockchain they also propose using an initial proof of work scheme to distribute the money but it's not really clear and for certain attacks they require the users to create a web of trust between themselves I mean they have to trust each other or trust a central service in some way that that puts some watermarks in the blockchain that say behind here nothing will ever change again or that confirm that certain blocks were generated in the certain way you have extra trust relations which are in the end extra assumptions that we want to avoid now given all situation what are the problems that we want to address here first of all formalize POS formalize what it means to have a secure POS scheme and uh actually construct one that we can prove secure and this one we solve another very interesting problem that seems very difficult to solve giv an actual game theoretic security analysis showing uh if we can with some protocol I don't know if ours but maybe another protocol reach an equilibrium if everybody plays honestly it's complicated because the protocols are very complicated the incentive structure is complicated then if you try to look at it from a game theoretic point of view then the utility functions you have to Define are very complicated and it's we still we haven't even looked into that there are people looking into apply doing game theoretic analysis on cryptocurrencies but here we're just going to do a standard nonrational crypto Proof come up with better protocols addressing attacks to current protocols getting better parameters is strong security guarantees yeah we came up with a new protocol that is immune to the attacks that have been shown to now that has nice parameters we're still working on estimating the concrete parameters but everything shows that they will be very reasonable and will provide for a fast protocol and we do get stronger security guarantees now I want to show you how the protocol works and I'm we're going to I'm going to show you how to construct something similar to the Bitcoin backbone protocol as defined in the gkl paper so I'm not going to show you a specific um crypto currency I'm going to show you how to build a consensus protocol that lets users agree on records They are ordered in the specific order and that are immutable after a while from that you can you you can write anything on those blocks you can write transactions for cryptocurrency you can write messages that you want to for which you want bantine agreement it it's just like that Bitcoin bit backbone protocol you use it as you like one of the very good applications is cryptocurrencies so first I want to show you the follow the satachi procedure from uh bent of all that allows us to select a user among all users with probability that is proportional to the number of coins that the user has so basically you start with a hash function that takes in a random seeds and outputs a number I that is is between bigger than zero and smaller than the total number of satoshis what is a Satoshi here it's the smallest unit the smallest monetary unit in the system in the cryptocurrency like cents so you select a number that identifies one of these satosi let's say you have a million such satosi you select a number let's say 153,000 721 and then you know this satosi let's say they that's a unique identifier for the Satoshi intuitively of course you you you have to actually create a mapping between the es in the system and this indices but it's basically easy to do so just showing the general idea you select the satosi by selecting this random number that comes from a seed that you input in this hash function or alternatively you could also just have a seed that has the same number of bits that you need to represent all satosi so let's say you have a million satoshis it could just sample a random number between zero and a million and use that number to identify your satosi then let's say you know how you selected this random satosi like that from a random seat and now you find who currently owns that Satoshi you look at the blockchain you Traverse the blockchain you find who was the last person to receive that Satoshi as a transaction output and that person person identified by their address is the winner of the follow the Satoshi so you can see here that we are selecting one of the users at random and the probability that that user gets selected is exactly equal to the number of satosi he has divided by the total number of satoshis so we get the exact distribution probability that we want the more money you have larger probability that you get selected and now this person gets selected he gets to generate the next block so it seems basically problem solved right we can select somebody who gets to generate a satosi it's publicly verifiable everybody who's verifying the blockchain can run the follow the Satoshi again assuming this random this random C is public anybody can run follow the Satoshi find who was supposed to generate that block and check that that block was actually generated by that person so since problem solved you can just apply that but how do generate the randomness that's one of the big problems how where do you get this seat from in the bent off at all paper on chains of activity they say apply a non oblivious Source the terministic extractor to the blockchain as in theory it's perfect I mean the argument works you can give it asymptotic argument you show if the blockchain grows enough you can get enough Randomness and it's all good it all works but then I as I told you how do you estimate in practice that there's enough Min enthropy in the blockchain for that it's a bit complicated so we want to get rid of that so let me just show you how using this which basically solves the problem given that you have the randomness plus standard blockchain techniques we can get a functioning blockchain based on POS before I tell you what we do about the randomness so first our protocol will be divided in Epo each EPO lasts for a number of blocks let's say that it lasts for n blocks for each Epoch we're going to have follow the Satoshi parameterized with just enough Randomness for this Epoch in each Epoch we say that we have a Genesis block even if it's a virtual Genesis Block in the beginning of the Epoch so when it's actually beginning when it's the first block of the whole blockchain when it's really the blockchain the the Genesis block for the whole blockchain then this block will be there on the blockchain and it will contain the following information user ID I'm telling I'm calling the users or stakeholders here U1 to un and the amount of money that they have Before Time began when I say before time began it's before the epoch again when it's the real Genesis block for the whole blockchain than it is before all time began in the mind of the protocol and then you have this information who has what cach and Randomness in the Genesis block for the blockchain when it started we will assume that this Randomness is indeed written inside the block but as the protocol progresses this information of which user has which money will be already stored in the blockchain you can just read the blockchain before your current Epoch and you'll find this information so we don't need to store this block anymore and then I'm going to tell you where this Randomness is going to come from for now let's assume the randomness falls from the sky and uh it's there for us it's perfect Randomness it's all good and it will be enough Randomness to run follow the satosi for each block we will defi divide the time in this protocol inside each EPO into slots okay for each slot a block can be generated or block might not be generated if the if the slot leader as we call them which are the people who get to to generate a block for that slot are offline so let's look at how this works first we have this Genesis block be it the real Genesis block for the whole blockchain or some virtual let's say Genesis block for the epoch whose information you can derive from the blockchain Now using the mapping from user to satosi that we have stored in this Genesis block and the randomness we run follow the Satoshi as I just explained in the previous slide so this will select a slot leader for each slot I'm calling them e here the slot leaders are the users that got selected by follow the Satoshi with probability equal to their number of satoshis divided by the total number of satoshis so you have a higher probability to be elected if you have more money in the system once you are elected you can generate a block you are the one who has the right to generate a block and no one else can generate a block in that slot once so once the list of users and the cash they own and the initial Randomness are set for the epoch you determine deterministically the slot leader of each slot inside that one epoch okay and during the whole EPO we will consider that the stake doesn't move that the coins don't move we'll consider that they are as they were before the EPO started so let's say slot leader E1 wasn't online he got selected that's immutable because it depends only on his information that he set in stone but he wasn't online he could not generate a block because he didn't he missed his slot so no block gets generated well it's bad for him not to be online because he gets the transaction fees if he generates the block and if he's honest it's in his own interest to keep the the system moving one good thing if you look at it is that in the beginning of the block you know when you get to generate in the beginning of the EPO sorry you know when you get to generate a block you know when you're going to be as not leader cuz you know this information so you can let's say put an alarm on your phone saying hey now I have to go generate a block it's my slot let turn let's turn on my computer inside one EPO now we run follow the Satoshi again for the third slot here and we select the slot leader this lot leader was online he saw he ran followed the satosi and he was happy yay I got selected I'm the lot leader I'm going to generate a block what does it do very similar to Bitcoin in the block is going to put the transaction information the transaction output so on the Block header with a merco tree root containing all this information yes how does does lots have fixed time let's say we say for example one slot lasts 10 minutes let's say the first slot begins at midnight at midnight 10 second slot begins at midnight 20 huh yeah physical time at midnight 20 this lot ends so of course we can have perfect clock synchronization across the whole internet but small flux uations don't really don't really affect this here we can work with a margin here okay so some what what there would be a problem for example is if let's say somebody generates a block one second before his lot ends and then another's lot starts and let's say this guy was quick he generates a block right when his his lot starts and and they send and it collides you keep the sorry you keep the the the newest you keep the newest Block it's it's a there are different rules you can do about this but the easier the easier rule to also facilitate analysis is saying well you missed your lot I received the newer block already that is valid that is by a guy who should be generating the Block in the current slot so sorry your block doesn't doesn't yeah doesn't get in well then of course you might get in a situation where you have a fork yeah then we use a basic longest chain rule then the forks are going to get extended and people are going to choose to which Fork they will extend but the rule is simple you extend the longest fork so in the end you're going to end up with a with the longest uh all the Hest people will see the longest one and follow the the the the longest one that's a that's a guarantee now what's in the the block we have the transactions transaction information a state information which is the hash of the previous the previous block basically and the signature by the slot leader that's how the slot leader proves that he was the one who generated the block that he was the one that had the right to generate the block he signs all the block information with his signing key and then everybody can verify the signature and see that okay I run follow the Satoshi with the randomness that is that is in the sky in this magic Genesis block I see that this guy E2 should be the slot leader for this slot and then I check the signature if the signature is valid and it's this block where he is the slot leader then it's a valid block and of course you also have to check the state information to see to which block is's linking because you might have this for situations where a block gets lost or where an adversary sends a block T ice for so you need to check to which block the the current block is linking so the protocol progresses like this this for each slot you run follow the Satoshi you find out who's the lucky winner who gets selected to generate the block this user generates the block mostly liking Bitcoin but adding a signature to verify that he was the one who generated so here we can see that the more money you have in the system the more blocks you get to generate with high probability right with a simple turnoff bound you can show that you you the the the blocks generat will stick to the stake distribution the the more Satoshi you have the more blocks to generate as long as we're running follow the Satoshi with uniform Randomness but still yeah how many participants so don't need to know you need to know not for the fall the Satoshi okay itself not for the selecting the random Satoshi but you need to know who owns each Satoshi in advance so we need to fix this for the proof to work we need to know for each Epoch that's that's why that's where I was getting it's a good question that's why we have this Epoch Genesis block that sets in stone who is in the system and who has each Satoshi that yeah in the you don't actually need to put that block there for the only time you actually write this down in the blockchain is in the first EPO in the Genesis block for the blockchain but in the next EPO you can just derive this information from the blockchain okay but for each EPO you will consider thep has yeah and you for each app you you will consider the state distribution of the end of the last Epoch now why do we do this thing of dividing it dividing the protocol in epochs and slots and having this fixed stake for each EPO that's equal to the last step book because we need to generate this Randomness again for every ideally let's say for every slot we would have to generate new Randomness so nobody knows in advance when there's lots are what is the problem of somebody knowing in advance the randomness is that this person will know which satosi will get selected for a slot in the future then they can go and buy buy that satosi so that's an attack then even if you don't own a lot of money there you buy the satosi that get selected so that's why when we run an Appo when we run the Father the satos inside one Epoch we consider the distribution in the previous Epoch when this Randomness wasn't known so nobody can look at the follow the satachi results and say hey I'm going to buy the satosi here and I'll be selected if you had those satosi before the randomness was known good for you you get selected if not you don't because the randomness will change for each EPO and now as I said the ideal situation would be generate new Randomness for every slot but then again we spent the first half of the day discussing how to generate randomness securely with a multi party protocol with guaranteed output delivery which we need because as you see here if I learn the randomness and you don't learn the randomness then you cannot run the fall the Satoshi and you and and I can cheat on you I'll have a better chance of generating blocks than you so we need this guaranteed output delivery when we run a protocol here to generate Randomness and this is what we're going to do to generate Randomness that's what I show here in the protocol the whole protocol with Modo EPO we will use this guaranteed output delivery coin tossin as a Randomness source and we are going to run that in parallel with the blockchain protocol so we start let's say here's the start of time this is the the blockchain Genesis block before this there was chaos there was nothing we start here and then we do write down a block with all the user IDs the money they have and Randomness that Randomness will be on the Genesis block that's something you have to trust so you can say something this Randomness is the hash of the New York Times in 1971 1 of January you can set some public Randomness but it must be on the Genesis block then we will run the protocol I showed you before with follow the Satoshi for every lot and people generating blocks and signing their blocks and in parallel we will run this Fair coin tossing protocol with guaranteed output delivery which is constructed just in the way I showed you before we use a basic coin tossing protocol based on commitments the bloom protocol plus verifiable secret sharing to obtain guaranteed output delivery all the parp all the participants of the protocol will be playing all of them will generate the messages as I showed you before how does the protocol work I send you a commitment to a value you send me your commitment to a value and everybody here in the room sends commitment to a value and then after all commitments are received we send openings that's what we discussed before right we can do it because the parties are fixed yeah the parties are fixed and what do we have here a blockchain that works as a broadcast channel so instead of I don't need to actually let's say we are all running the protocol I don't need to go around sending a commitment to each person in the room I can just chout here the commitment and let's say the shouting is the blockchain you all hear the commitment because it will be in the blockchain why is it also good to write this on the blockchain because once it's it's set in stone in the blockchain nobody you can actually call out the cheaters we haven't really looked into that but you can call out cheaters and you can uh be sure of all messages that are being sent they are there even if you're not online at a certain point and you get let's say you're offline for half of the Appo okay then you come online you send your commitment then you go offline again you come online you read people's openings you send your opening if you were offline it's no problem because the messages for the protocol all those commitments I was writing down here that they sent with arrow S one now they will just be in the blockchain and as you remember apart from the commitments we will also write down the shares of each person's sorry actually the shares we don't even need to waste space in the blockchain we can just send the shares to people locally or to of course when when the system grows a lot we can just put this in certain blocks and then uh when people misbehave we can open the we can sh we can come together with our shares get the inputs run the exorb the input say in the bloom protocol get our Randomness and that's our Randomness set in stone for follow the Satoshi so the situation we arrive at me see yeah okay I have a I have the nice arrows here situation we arrive at is this virtual Genesis block for the next Epoch that is actually determined by the previous epoch I don't really need to write down that block in the blockchain this information of which user has which money comes from the transactions they're written in the previous blogs the randomness comes for the fair fair coin tossing protocol but the messages for the Fair coin tossing protocol are in the blockchain so I don't even need to be online all the time to run the protocol and at any time if I join the system I can read these messages on the blocks and run the protocol in my head get the randomness to verify the next EPO and then we start a new Epoch same thing we run the epoch protocol with the with the F the satosi generating each block signing each block at the same time again Fair coin tossing with guaranteed output delivery then what do you obtain same thing a list of users in their state dis distribution and new Randomness and so goes a protocol now what we can prove about this we can prove that if this R it's a the actual proof is very modular first we prove that inside an Epoch inside one Epoch assuming you have Randomness that falls from the sky we actually Define a functionality that gives you a follow the satosi function you call the randomness or call the functionality it gives you a description of the F the satosi function in Randomness and you can select inside one EPO so we Pro that inside one EPO considering that you have a fixed stake for that EPO and the whole list of users and a fixed follow the Satoshi that is that uses proper Randomness we can show that the probability that an ad ad AR that doesn't have at least more than half at least half the stake cheating is decreases exponentially so formally what do we prove we prove that we can achieve the chain quality and common prefix properties of the gkl paper so common prefix basically means that after a number of blocks in this case after a whole Epoch goes by with very high probability there will be no Forks everybody will have converged to one single chain basically common prefix chain quality means that after a while also let's say after an EPO is done there will be a considerable fraction of blocks that were generated by Honest users again intuitively since we we have honest majority and we're doing follow the satosi we can show that with high probability there will be at least one honest block because we have honest majority and with and the distribution of blocks will follow the distribution of stake so we can show that and we also show uh nextra property that we need to define a chain growth that we have to show that the chain grows that even though there are some offline people some times people who don't generate blocks and so on have to show that it still grows and we can prove that now in in our scheme grand scheme of things we show that this epok alone considering perfect Randomness for fall the Satoshi and the distribution is secure then we show that we can compose this and get and glue the EPO together that we can run the protocol for for one modify the protocol for one EPO by running the the fair Quint toin with guaranteed output delivery at the same time writing the messages in the blockchain and we show that by doing that considering that we have common prefix and chain quality we need to that's why we need to prove that first for the epoch because we need to prove that by the end of the epoch everybody will agree on the messages that that were sent by the Fair coin tossing protocol right because we're putting those messages in the in the blockchain if the if the adversary can create a fork that goes over the whole EPO then he can make different people agree on different Randomness which is an attack but first we show that he can't do that for a whole Epoch which means that When We Run The Fair coin tossing using the blockchain as a broadcast channel then we can arrive at the end of the epoch with fresh uniform Randomness to seed the follow the satosi yeah he cannot the adversary cannot generate a block try to over the we prove that he can after the epoch is finished common prefix holds that's what we prove he can generate small Forks inside the the epoch but once we finish the epoch we know that what is behind here is there will be no Forks that span the whole EPO that let's say cut 10 blocks out we have many many before the the first many blocks in the epoch are are agreed upon by everybody that's what common prefix tells you and we prove that at least one of those blocks will be honest at not only one at least a constant fraction and you have a value how many blocks uh we still uh calculating that uh we because we have like we have the proof in terms of U Asm totic we can show we have an expression that shows the probability that an adversary succeeds in in in generating a fork after a number n of n blocks and we can clearly show that that expression decreases exponentially with the number of blocks but we haven't at least maybe aguilos is already looking into that but uh we didn't estimate that yet so I was wondering if you have at least minimum size ah we will certainly have a minimum size of the epoch to to have a it depends of course on the probability you want that the adversary cheats you want that he cheats with probability only 1% or probability only 0.00000000 z0000 1% but it seems from what we've looked at that this curve decreases very fast yeah the the probability that the yeah the success of the adversary decreases really fast with the number of blocks so we're confident that you don't need let's say a thousand blocks or whatever you don't need that many blocks to get a very low very low probability that the adversary succeeds but we still estimating that that's a good point that's something we need for the be able to break when you succeeds yeah you mean break the break break the yeah so that's one of the next steps that I'm going to show actually estimating the concrete parameters no but it's a good question because we want to know the concrete parameters the good thing is I showed you the protocol how this protocol works it's not very complicated you send a message to commit you send another message to open you send along in the same round to send the vsss so it's not it's not a complicated protocol it can certainly run inside an EPO so we don't have a problem like ah we're going to have to make I've heard some concern from practitioners they asked us but you're running this super complicated crypto protocol isn't it going to take forever isn't it very inefficient it's going to make an EPO very large no I showed you guys before that protocol takes two three rounds it's quick and it's very efficient the verifiable secret sharing as I told you before is based on error correcting codes it's information theoretical it's extremely efficient you can also make it based on uh on computational assumptions of course if you depending on if on the trade-off between communication and computational power we can Implement them based vsss based on on efficient things like uh elliptic curve mod applications the commitments as I also told you are extremely efficient you can Implement them BAS based on most uh public key encryption schemes on ddh or even using prg so we're good with that so we're combining very combining two very simple things is uh commitments and vsss there that are efficiently constructed so the result even though it's something that might sound strong something that guarantees that you get perfect Randomness it's not one of those very complicated asynchronous MPC protocols no it's a it's something that you run in two or three rounds and uh that doesn't require that much communication and that can be implemented efficiently in in terms of running fast in a computer or even a cell phone it's very simple operations if you think of ddh commitments you do you get uh uh group element a group based g g to the message then G to the the Rand to some Randomness that's a parameter times another Randomness that's a commitment you're doing two exponentiations and you got a commitment right there so it is something that can be very efficiently implemented that was one of the concerns i' i' I've heard before uh the factor that makes the EPO stretch a little bit more is actually being long enough to achieve common prefix because of the structure of the follow the Satoshi and this this random selection of uh slot leaders and the fact that you have to account for people who are offline and the fact that the adversary can cheat in some ways that's that's what makes the the the EPO grow a little bit because we need to achieve common prefix but the protocol itself it runs as fast as you achieve common prefix basically cuz you need to send a message wait for common prefix you have to send the commitments and wait for common prefix so you are sure that everybody's committed right otherwise you could cheat as I showed you before if you know somebody's Randomness before you send your commitment then you can choose your Randomness in a way that you determine all the you determine the final result so we need to make sure that everybody's committed and to do that we need to wait for common prefix and after that we can just open so I was wondering of many not dep on many participants because might be thee that some not all participant ah sure in that way I I see what you mean well you need to have a nbook uh no you don't have to ah I get your doubt no uh not everybody has to be chosen in a netbook if you don't have much money let's say uh if you have I don't know 0.001% of all the satoshis you might just not get selected in a Neto overall over the whole blockchain it is over the whole blockchain over many epics it should be the case that 0.001% of the slots are yours but maybe this 0.001% is so small you don't get selected inside the netbook but that's not a problem that doesn't affect the analysis of what does affect the analysis in terms of number of users is uh of course you need how many how many how many users you have how many you consider that they are corrupted and how many you consider which fraction will be offline that you can also account for is corrupt corrupted so that's what that's how it affects the analysis because you need to for the concrete parameters let's say if we have a million users and we consider that the third is corrupted then uh maybe we need we don't need that many slots to actually get uh some onus blocks to show up but if we have less users then we need more blocks to get let's say if we have less users and more corrupted people we need more blocks to to make sure none its block shows up that that's more or less how it how it effect online honest more or less but what what we're in the analysis we basically consider offline people as corrupted then you you deal with with them that way now one interesting thing that's coming up oh sure please please question if there is a very small possib CH yeah in yeah so that's something you're also working on you say in this case let's say I don't have much money so the probability I get selected is very small so I don't want to keep playing the protocol all the time because it's small so so we're working now on something called delegated proof of stake where you delegate the power of generating a block whenever you get selected to generate a block to a bigger entity let's say a the equivalent to a mining pool then you delegate your uh your your your signing power to them we're we're working on a solution based on proxy signatures that sound that seems natural for this uh problem is that good for the well it of course it it uh incentivizes a bit the centralization right but in the same way in Bitcoin at least in this case there's one clear advantage over Bitcoin in Bitcoin uh you you have no control as a person who only has uh coins you have zero control and you can't choose which mining pools get together or no or not in this situation you have uh you have the coins you have the power and uh you can choose which to which person you're going to delegate the signing power and if they start doing bad stuff you lose money so you also have an incentive to watch over the people who are centralizing this delegated uh signing power so you have incentive to actually uh check and audit these people to make sure that they're not doing bad things because then you will lose your money and you can easily just delegate no I don't want to Delegate for you anymore I'm going to delegate to another person that's that's the idea of this scheme so that small stakeholders who don't have a large enough incentive to stay online all the time can delegate it to somebody and then we have enough blocks coming up that's one of the next works that one of the Future Works that we're checking out right now I think I think we have a solution that works but of course we need to finish formalizing that I don't want to say for sure before I write down a proof but yeah they don't need to be necessarily online all the time to run the protocol yeah you have ah sure they have to come online at at some point before uh what what do you mean by I mean yeah yeah half plus one yeah yeah I see then it's bad then it's bad we inside one EPO inside one one given EPO we need to have a major we need the honest majority to be online inside one EPO yeah yeah one uh one what I mentioned that they don't need to be online all the time is that the Hest parties they don't necessarily have to be online all at the same time they can come online on one slot write down their commitments go offline again come online again when they want when they're going to generate their their block generate their block read the openings go offline again what I mean is that they don't need interactive uh interact interaction uh necessarily they can write things on the blockchain go offline if they just show up in the middle once that's if they show up to put to contribute to the Fair coin tossing protocol of course they have to show up in time CU they are the rounds right of the protocol they show up in time to contribute and if if they show up to generate their their blocks then it's fine if they never show up and they don't generate in one EP yeah most of the Hesters are offline in one EP a for the whole EPO that's a bad EP then then security doesn't hold yeah and just come up online and gets out that's fine yeah for this for the beginning of the coint tossing for this commitment phase in the opening phase let's say we have the adversary that is bad and aborts does then yeah but to do the God thing in the opening then they need to to have some direct interaction to do the the Reconstruction of the VSS then they need to interact but if you but that's one part in the end of the EPO then they need to be there to reconstruct the the shares the secrets but for most of the protocol it's interesting to see that when you just sending the commitments and uh generating blocks then it's all right you can come online put your commitment in a blockchain go offline come online generate a block but of course if you have a problem with the openings and you want the guaranteed output delivery you need the Reconstruction of the vsss that will include interaction but even then it's short interaction that's the nice thing you don't need s several rounds you don't need a lot of computation or communication it can be done in a few rounds only if that answerers please please please explan stat the ah we're considering that that we have a static adversary that corrupts parties before execution begins or yeah maybe in some can uh yeah it would be interesting to actually do an adapt show that this is adaptively secure but then it's more complicated I think it's probably possible to show that the the adversary can come in the middle of let's say the adversary comes in the middle of an Epoch and corrupts a new party then what happens we haven't studied that case yet our proof is for the case where we where the the militias and honest parties are set before the EPO begins okay yeah let me think if the corrup between EPO let me think if the proof works let me just think if the proof would work in that case it might actually it might actually work if I understand it might actually we didn't write it we the way we wrote it was considering you have uh since it was the first attempt at proving this thing secure we consider the synchronous networks and static corruption from the beginning of the protocol but I believe that we can also prove that the corruption can change between EPO but inside the Epoch our proof doesn't work no way if corruption changes it has to be stady corruption but between epochs I think it might actually be possible to modify or approve trivially to do that but I I won't say for sure because I haven't written it down so I don't want to promise but I think it's a good question and it makes sense it would be interesting to actually show that in the paper that uh between EPO you can have different corruption but inside one EPO using our techniques it doesn't work we have to to have it fixed maybe with different techniques but that's a thanks for the question it's something I hadn't actually thought about before but it makes sense and I think you can we can actually show that it works like this any questions for spe spee ah okay any more questions yeah ah yeah sorry you C you caught the detail cuz this is just this is just a screenshot of the previous slide with one with one ook that I shrinked but you are totally correct that this this is this would be the virtual the virtual Genesis block that is actually determined by the previous Epoch but these two would be this means the same got the tiny detail I thought nobody would notice the tin I just wanted to illustrate that you run the epoch protocol then you start with this Epoch Genesis for the next EPO but you're correct you I'm happy that you understood that it's a the the same good uh any more questions then I can tell you a little bit about what we're going to do next uh first determine concrete parameters what might asked it makes a lot of sense we need to do that for the implementation for example specifically epoc length that's a good one to be determined we have the proofs and the Expressions now it's more of a matter of plotting graphs and and and seeing how the functions behave to get the concrete parameters then work with the development team at iohk to to uh come up with a prototype since it's a project that we've been developing inside iohk for uh an upcoming cryptocurrency products so we want the prototype to see how it behaves and also it would be it would be good data for the paper to show that how the implementation works in practice but then there are developers that will do that I don't know how to program that well uh some other things that came up Tanaka sensei's question is a good one can we prove that this protocol works when the the corruption changes when the adversary can corrupt somebody and the then that user behaves maliciously then he's honest again the malicious again it would be certainly nice to investigate that there's not nothing like that done for any cryptocurrency protocol by now it's all considering static corruption uh also would be interesting to study the case where users join the protocol in the middle of the protocol here we're considering that the users are known in the beginning and then uh throughout the protocol they stay the same but it would be certainly cool to look into the Adaptive Cann in the prot the of no they have to wait for the next EPO next one that correct that is correct well you can do transactions if you jump in the middle of the EPO you can buy coins but that but that state will be just refreshed in the beginning of the exactly exactly so that's also point the tradeoff between longer Epoch with the tiny probability of success for the adversary to do a fork and shorter EPO where the changes in stake get reflected quicker I have a question please please please and make aaction for example might receive some yeah and so and very tin what happens if chosen for for generating the block but for the other transer the participant the joining participant it will be it will be you consider that the owner is the guy who owned it in the previous EPO it's fixed in that virtual Genesis block doesn't matter doesn't actually matter that the transaction no who currently has it in the EPO doesn't matter what matters is who had the satosi in the previous EPO and that's set in stone in the blockchain for the previous Appo that's that's the idea join yeah but this is an interesting problem the only analysis right now formal analysis that considers people joining the protocol is in the paper by Rafael Pas and abish shot and their student that they show Security in asynchronous networks then they also consider people joining the protocol even though the corruption set the corruption static they they consider an interesting funny model where you have [Music] static adversary but then the adversary can spawn its users into the protocol later he can't corrupt one that's honest but he can spawn a new corrupted one inside the protocol so the set the full set of of of of users and Corruption is known but they are not assumed to be participating in the protocol from the beginning it's something like that but still it's a it's a complicated case that's why people are still struggling with defining no our idea here was to start from the simple case Standalone uh static uh adversary and uh synchronous networks and then progress towards the synchronous networks adaptive adversary composition good thing is one of the next steps is also looking into composition if you looked at the protocol basically what you need to make the protocol tick to make the protocol run is do this guaranteed output delivery Co tossing to refresh the randomness every EPO if you control the randomness you control follow the Satoshi if I can give you an arbitrary Randomness I know exactly who will be generating blocks in the next Epoch so my intuition for proving composition here in the Universal Universal composability model if you guys are familiar with that that's a model people use to prove composition is that I I can use here the vsss is information theoretical so I can always cheat in the vsss if I'm simulating the protocol in the proof in the security proof and I can then combine this with a UC secure commitment scheme that allows me to select a specific uh Randomness and then I can cheat on the randomness in the simulation and I can set the randomness in a way that I control the who gets to generate the blocks then I can then I can simulate things per perfectly basically for the proof yeah for the proof for the proof that's the intuition but I haven't really the the the hard thing there is the technicality of UC see that in UC you don't have slots you can't just say that you're going to get messages delivered inside as lot or you have to deal with time but Hangar and some other clever guys came up with a way of modeling this and you see you have a clock functionality that makes time tick and you can so it would be a highly I think the technique itself is kind of straightforward conceptually but it's a highly technical analysis to prove that this thing is composable because you have to deal with this tiny details of time and message delivery but it's probably doable it's one of the next steps too so there's a lot of work to be done on these things and the delegation of course good if you guys don't have any more questions uh that's all I wanted to say good thank you yeah thank you very much [Applause] thanks took me some Googling for