Distributed randomness using weighted VRFs with Benny Pinkas | a16z crypto research talks

Transcript

so it's my pleasure to introduce Benny pinkas today uh Benny is a researcher at abos lab if you notice they're our neighbors I think down one floor Benny is also uh a professor of computer science at barand University Benny has many uh Works in NPC space he worked in NPC probably even before some of you have been born so he he really stood at the origin of the field um it's my feeling is that Benny has worked on every interesting um Direction and NPC research and kind of left his uh contribution there uh Benny also uh worked for various companies including Google VMware hit buckard so he really stands at the intersection of theory and

practice and today he's going to uh tell us about very exciting protocol that Abus has developed Ved um fully designed I think and brought into production in up slabs thank you Lea uh so I'm going to talk today about uh this the randomness using grated vrf this is a protocol that we designed and implemented in upos laabs and you can actually use it on the Aptos blockchain uh today uh this is Joint work with Sur Das who's here and with alen tomescu and Daniel Shang from Aptos laabs so before describing the protocol I'll uh give a few you know give introduction about the Aptos blockchain so Aptos is a

layer one blockchain it publishes a block of transactions every about 1 second and you get transaction finality in less than a second so this is up to Spa wallet I transferred some tokens and it was finished in 0.93 seconds so uh this is the uh amount of latency you have on the network so everything we do has to be you know fast enough to to work uh with this latency upos is a proof of stake Network the about 100 or more than 100 validated notes all over the world and they achieve consensus on any block of transactions every second what happens that uh each token owner can decide to stake his or her tokens

any validator and then the validators vote to achieve consensus and uh the consensus assumes that corrupt validators control less than one third of the stake just an example me as a as a as a as a user this is a a screen copy of my petol wallet and here I decided to State 12 tokens using uh one validator and you can do it using your phone like in in a you know in a matter of minutes and if I decide to stake with this validator not with the other then the weight of that validator the stake that it has increases okay and then our whole decision about the consensus and about the security of the randomness should be depend on people deciding to stake their tokens like this this is a map of the

validators you can see that they're all over the world this is for March I think the 129 validators all over the place and the total amount of tokens that we stake is about 884 million at that time right now it's it's different it changes every two hours so as of March there were about 880 million token Stak the stake distribution and also the identity of validators might change every 2 hours and it and it does change and the stake distribution is kind of diff it's it's not uniform at that time 14 validators had between 15 and 20 million uh tokens take with them and a lot of validators had around 1 million tokens St with them

because 1 million is the minimum amount of tokens that you can you can stake so there's like a a long tail of validators with is small weight and some has some have much higher rate so before going into our talk I just dis I'll give you some example of things happening on upos and why have why we have to be like very efficient and we cannot afford to slow the network down this actually happened exactly uh a month ago in last March and I'll read this to you there's like a tweet saying look what's happening on atos the uh uh TPS in last 48 hours transactions per second increased to something like 2,000 3,000 TPS which is quite high and that's another uh tweet

from DJ news saying Aptos has about 100 million transactions per day much over Sana okay so this is quite amazing and what was the reason for this so the reason was like a simple game where you had to click on the cat to make it smile and the more you clicked I mean each click is a transaction on chain okay so that all the valat has achieve consensus about it and the more the more you click the more uh uh chance you have of being rewarded okay this counter says this in three days had 323 million clicks okay I I'm responsible for about a 100 of these clicks because was kind of fun and this

is you know 60,000 uh people participated okay so this is like you know it's like a funny game why is it interesting okay so the interesting thing is that you know this game okay funny game caused a lot of traffic on chain so this amount of traffic like 100 million transactions per day is about the same traffic that uh Visa process per day okay and the network was able to process it without any uh any problem so this was done to demonstrate the performance of the network and this is a a tweet from Sasha spigelman from our uh a research uh group saying look the fact that we were able to do this without any spikes without any problems with the network is

amazing because no one else has done it but what's even more amazing is this counter here that says you know the total number of clicks because this counter was updated in parallel by all these 60,000 people playing and somehow uh the network should be able should have been able to do this parallel processing of many accounts in parallel uh uh uh updating the same variable so we do it with something called aggregator which supports parallel processing very efficiently so the the program to write this smart contract was very simple okay but the technology to support this especially this uh uh joint counter is is very complicated okay and this is what we want to do like build a

complicated uh uh uh infrastructure that enables developers to write simple programs that will make use of it okay this is like this is like the the task that we have to do okay so enough with the games and let's go to to Randomness so what's the motivation for using Randomness on chain so one motivation these games which are a serious business so games like back gamon they required you know to throw Dice and even uh like arcade games when you fight all kinds of you know enemies the the players want to know that the enemies actually uh play randomly According to some distribution are not kind of

tricking there but trying to cheat them that's actually even important for these games and other games of chance uh Dungeons and and Dragons Etc they need Randomness and the players really care about the quality of the randomness there's randomized nft meeting where you should get the random NF and some nfts are much more valuable than others so they want to verify that they get you know no random results air drops transaction ordering to limit me opportunities that's very important and there are also some cryptographic applications like uh uh selecting leaders for consensus so also zero knowledge proofs and let me show you something about Zer knowledge proofs one simple Zer knowledge proof is based on

Sigma protocols where the Prov sends a commitment gets a challenge and then sends back a response and there's the Fiat Shamir aristic where instead of getting a challenge from the verifier the approver can compute it non interactively by Computing some hash of its initial message here as the uh as the challenge and most proof systems use this sistic in order to be non- interactive and this hash function should be based on the commitment but also on on all the content of know what instan is being run here Etc so this is a very simple theistic and apparently it's very easy to get it wrong I mean there is you know a paper showing about weak

implementation of Fiat Shamir the compan is making a living of finding uh uh weaknesses in Fiat Shamir implementations and the main problem is that when you compute the hash function you don't compute it over all the inputs you you forget some of them and this is extremely extremely common so using onchain Randomness what the P can do uh he can post the commitment on chain and then use the randomness generated on that on that block as it challenge so it doesn't need interaction from the verifier it can do it all by itself by posting committing to its value on chain and then using uh the random post use generated on that block as its challenge

then submitting the last answer now another thing that it enables is that the prover is not not being able to grind and find you know which uh to look know to do a boot Force attack looking for a uh a convenient challenge because the challenge is computed on chain independently of the prover and this enables to use uh shorter challenges so in case of proofs where the length of the proof depends on the length of the challenge this can make the proof much more much shorter okay and we have examples about this that we I won't go into details here so for that previous application but then when you want to prove zero knowledge what are you going to assume to prove zero knowledge in this sort of so let me

repeat the question so the question what ask whether how can I prove zero knowledge here okay so where I see you basically have here an oracle okay that gives you a challenge uh the Oracle is out of the reach of the of the verifier and we can in the proofs we can program it to give whatever CH whatever value we want it just instead of instead of the challenge being received from like in a verifier here is being generated by you know by or by an oracle it's a real random Oracle a real random Oracle random yeah yeah there might be an issue with ver verifiability of that

Oracle because it's going to be a verifiable Oracle but we can discuss this later so what we want to achieve is a verifiable random function or vrf where the output must be unpredictable uh or more accurately indistinguishable from random and we also want it to be verifiable meaning that meaning that anyone can verify that the output is correct okay it was committed to like at an earlier stage and thus no one can bias the output now I won't go into the definition uh in more detail than this this is basically the properties that we want to achieve yeah does the eventual solution use random oracles the eventual solution okay the question was whether the uh

eventure solution uses random Oracle yes it does use a random Oracle for the proof uh yeah so it does use it yeah so the proof is in the random or model suppose you want to achieve you know get Randomness in a blockchain so you want fresh Randomness for every block and the question is what is the good time to get this randomness so we have blocks and each block should get a random value associated with it and the question is when to compute it so one option is to compute the value just before the block begins and then commit to the transaction that block but this might be too soon because a sophisticated adversary might learn the Randomness at this point and immediately change what is committing to the block and if

there's some value associated with it no people will do that another option is to reveal the output just slightly after the block is ends okay but this uh might be too late because it slows down you know the time when we can uh process the transactions and the right thing is to reveal the output immediately after we commit the the block okay and this is what we want to achieve and actually I'm I'm going all the way to the end currently we achieve this within 30 milliseconds so 30 milliseconds after the transactions are committed we give the the output so this doesn't slow anything yeah so R here is the

randomness that the transactions inside bi can use potentially exactly so the question was uh what is this Randomness for so basically here we commit to transactions the transactions are going to call a function that gives them random values and the question is know suppose I'm playing back game so it gives me the value of the dice and the question is when is this value generated so here it's too early because then I can decide how to to play based on the value of the dice here is too late because I have to wait too much so here it's within the block like 30 milliseconds after I commit to to my move after all the transactions are committed including my move so it's 30 milliseconds of compute no no extra Network messages are needed it it it

covers everything I mean 30 30 milliseconds is it also covers the N then has to be a function of where your servers are because if one of them is in Australia then okay so I maybe should have shouldn't have said 30 milliseconds right here but that's the that's the amount of uh uh latency we currently have on on our Network in an optimistic case which happens most of the times if not all of the times okay somehow inter leave into the consensus I can give more details afterwards now another way of achieving Rand getting Randomness on chain is using external oracles like chain link Supra or or Dand these are services that give you random values so basically each time you're asking for value you can call the Oracle and get

back a random answer so the question is why not use them one issue is security and availability I mean they might they know the random value before us so maybe they're going to cheat it but these companies are not going to cheat us but we uh depend on them for availability like if they fail then we fail and we don't want this to happen another issue which is even uh more critical is usability these companies would not like we have a block every second and then maybe in the future future is going to be every some fraction of a second and they run at a different uh different time intervals so this means that the output from the Oracle will not be ready for this specific block we'll have to wait a little bit for that so this means

that whatever transaction that tries to get the value from the Oracle will be a twostep process where I commit to my move based on the value that the orle will publish in the future might might happen in half a second and when this values publish I'm going to start I can use it but in terms of programming this is very complicated I mean I now I have to do like a two-step commit or twostep uh access to Randomness and for programmers to use this it's quite complicated why is that different I mean you're committing to the block and then using the randus anyway so so the commitment to the block is done by the validators for the transactions are going to be run on that block here you as a programmer who's

writing a smart contract a distributed app you have to use some interface that says I'm committing here and this is going to be uh run in the future when we get a Randomness I'm no you and I we throw a dice based on the result that will be given for us from Dand in the future we have to specify in which time it will be will happen that will be after the current time that we don't know what it is when we write the program so it seems more complicated and there's an issue of cost I mean they should charge some money because they're running a service okay so that's also an issue so the desired experience is that our blockchain validators agree

on the set of transactions to be run on a on a block they order them immediately afterwards we get the randomness for this block we get like one value from which we can Generate random values for each transaction in that block and then we're running the transactions of of that block the API should be very easy and also everyone should be able to verify the output so about the API this is the API basically these are functions using this function you get a certain number of bytes you can get values in a certain length in certain range Etc so it's just like any programming language the the users the programmers they don't know what's happening at the back end they don't have to commit to your future time you just call random that's it every time you call the function within

this in the same smart codk you get a new Fresh random value so in terms of programmers that should be as easy as we can get now after talking about the motivation let's talk about the construction so as I said we want a verifiable random function which is unpredictable and verifiable we can verify it and the trust guarantee will be that as long as less than a sum threshold which we said to be 50% of the stake does not cheat then you cannot predict the output of the function or or bias set so the way we're going to implement it is using a threshold vrf riable random function every two hours every EP every two hours there's a new EPO at that time the stake distribution ution changes at that time the validators run a distributed key

generation protocol or dkg where they do Secret sharing of a new uh uh secret for this vrf based on the new stake distribution for if I if I have say uh 1% of the stake at a certain EPO and 1.1% of the stake in the next EPO I might get more shares in the next EP compared to this one and uh each Val received shares of the new key based on its on its weight and the key is generated in a distributed way then every block which is about every 1 second the validators together to compute the vrf and it's secure as long as less than 50% of the validat is cude and typically the way you compute a vrf a verifiable random function is by

Computing a VF a verifi un verifiable unpredictable function and then applying haash function to the output so the VF is verifiable and we don't claim it to be distinguishable for random is just unpredictable and then we apply to it a random has function model as a random Oracle and basically VF is equivalent to Unique signature because a signature is also something which is unpredictable and you can verify it so a unique signature just like a VF this is what we want to implement wa why does it have to be unique though because U the question was why does the signature has to be unique and the issue is that we want like just a single output as the certain block so there the VF say would be the

signature on the block number now if you're using a randomiz signature like say Al Gamal then you can have multiple signatures for the same block number so the same so multiple possible VF outputs for that block number if the VF is the terministic then you only have a you know one possible my complaint is that a VF is shouldn't be equivalent to Unique signature then so this is what I bote the VF is equivalent to Unique signature I'm saying just the verifiable property doesn't mean it has to unique the issue so the question was because then you can buy it if I have three possibilities and I can choose which one is better for me so to to to verify verify give unpredictability means you don't have any Bel so I'm just okay I'm saying this

for the you know for the recording the question was what what why does an unpredictable function has to be unique it also has to be verifiable and actually it's my blame for not defining what I want here but one property you want is that for each input there's only one possible output therefore the signature has to be unique okay so the desired structure we want is that every EPO 2 hours we do distributed key Generation by all of them then each validator gets a new share based on the new stake distribution and then every block every one second they compute the vrf output One technical issue is that this is the current stake distribution in very small fonts that changes all the time and then if certain validator has

you know 10 million 10, 512,000 tokens we're not going to give it this number of shares because then we have going to have too many shares so we somehow have to round this so the way we do it we set a certain uh unit say of tokens that is equivalent to one share say it's going to be like 1 million uh tokens uh one share and then for each validator we divide it stake by that by that unit and we round up we round other up or down round round to the closest integer so this might give you some rounding errors so what can happen a validator suppose it should get like say 10 three uh shares but we round down so it's only

going to get 10 shares so each validator might lose or gain up to 1 half shares so a committee of M validators might lose or gain up to M over two shares which is which depends on the the number of members of that committee not not on the total number of shares and this effect is limited and can be analyzed and we did analyze it so I won't go into this in more detail and we use something between 500 and 1,000 shares right now and the more shares we're going to use the more accurate it's going to be so the construction is going to use by linear pairings here's a reminder about pairings we have two groups G and G hat and a Target group GT as an a symmetric pairing is a function taking element from G and from

G hat mapping it to the Target group GT with the property that the PA pairing of G to the power of A and G hat to the power of B is equal to the pairing of G and G hat raised to the power of a * B so basically the exponents we can play with them and and and move them and we get the multiplication of the two exponents and the security will be based of our construction based on the bilinear D Helman assumption which says that if you have g g to the a g to the power of b g to the power of C in one group and the same exponents in the second group it's still hard to compute the pairing of G and G hat to the power of a * B * C it's easy to compare to compute it to the power of a * B say but

not to the power of all three exponents and this is a known and used assumption so first some approaches which do not directly work so for the dkg the obvious thing is to use felman's uh vsss Veri a secret sharing which will work like this uh each player each validator will generate a polom s of degree T it will broad broadcast the G to the power of the coefficients of this polinomial and then we'll secretly send to each participant the value of the polinomial at that participant's ID a p at location J and then each participant can verify using the polinomial and the exponent that actually it received the right

value if you've seen this for the first time it's probably hard to follow if you've seen it you know 10 times in the past then then you know what what I'm talking about here and each participant verifies that this is the case and if this this verication doesn't work then a participant fires a complaint and he can prove that the dealer cheated cheated him okay that's the important thing here and at the end of the fa this phase this sharing was done by every part by every validator so I received a share from each validator I summ them and this is a share of the sum of the all of the pols so this is is how you know as the first approach for doing it but there are several problems the first is that

each participant the dealer has to broadcast the exponent of this this polinomial the degree is as the threshold say like you know 500 so each validator has to broadcast a lot of information and broadcast is expensive I mean it's easy to write here the world broadcast but actually implementing it is exp is is expensive and even harder problem is filing a complaint if a participant think that the dealer sent it a wrong value it has to file a complaint then everyone has to check the complaint and decide who whom to blame this is the interactive process which slows everything down and you have to wait till you see if everyone filed the complaint or didn't file a complaint this is is is complicated especially

also to implement it it's complicated yeah you could do interaction of a previous blocks right you could say um in order to get the the uh results for BL block t+3 I'm starting the protocol in Block T then I'll broadcast this t+1 I'll get complaints in T plus2 and then in t+3 I'm finished okay so you said that you can do it in different blocks so this is done uh once every EPO when the EPO changes so every two hours the stake distribution changes and then we only know about the uh stake distribution in the new EPO shortly before it begins like a few you know seconds minutes before that and also the big thing here the main difficulty is implementing this it has to be you know

reliable and you have to wait for the worst case it's it's it's a lot of heic so doing this interactive uh uh secret sharing is not good how does the VF typically work usually we use it use BLS signatures so if it wasn't a threshold case then the private key would have been X the public key G to the X and the signature the VF output will be age of the hash of the message ra to the power of X and we can verify it using a pairing because the pairing of age of M tox together with G is like just the pairing of the public key G to the x uh with the hash of the message so that's what you do if there's no threshold access structure in a threshold access structure uh each participant would

publish would broadcast age of the message raised to the power of its own share and then they can do interpolation in the exponent and and get age of M to the power of the secret and the problem here is that you have to send a message for each share and you're going to have say up to a th000 shares so this is a lot of items to broadcast and this slows things down and you have to check each one of them so this slows things down we want to do it more efficiently especially this happens like in every block every second so what do we do so for the distributed key generation for dkg we use very fiber secret sharing but there are two properties we require of it one is that it's publicly verifiable meaning that anyone can verify that the dealer operated correctly so dealer

should encrypt each share to a different recipient others cannot decrypt all the shares they should be able to verify that the encryption is indeed correct okay so this is the publicly verifiable VSS PVSS another property we want is that the PVSS is aggregatable meaning that you can take different PVSS transcripts for many dealers aggregate them to a single transcript of about the same length sharing the sum of the secrets so we take many PVSS transcript and aggregate them to one of the same length this will improve efficiency efficiency which I'll show in a minute the problem here is that the only aggregatable PVSS that we know due to G canet Al uh it shares group elements rather than field

elements so the secret that we're going to share is going to be a value of say G to the a rather than a field element a and this complicates the VF that we're uh uh uh using it would have been much easier to work with sharing a field element why use aggregatable PVSS that causes causes all these problems the common implementation for dkg would work like this each validator is doing a PVSS and broadcast the PVSS that it's doing every validator can add validator okay and also it's important to read ordered broadcast where there is there is order for all the PVSS transcripts but were verified that we uh broadcast every validator can look at

the ordered broadcast here look for the first PVSS transcripts that came from validators whose total weight total stake is above the threshold sum them up and get this as as the result of that as its own secret share so this is what is usually being done what we could have done but this would require each PVSS to be broadcast and an order that broadcast something I can easily write here but it's quite heavy it requires quite heavy computation communication because all these F validators have to agree about what is being broadcast and about the order okay and this is actually quite long each transcript is okay is as long as the number of shares say like 800 the

130 validators uh you have to publish at least two elements each one of them is an element of a of a of a group I have your calculate I think it's something like more than six megabytes and doing an ordered Brad of 6 megabytes is is quite uh uh quite heavy instead we're using an aggregatable PVSS so we do something like this each validator sends using peer-to-peer messages uh each PVSS transcript to all other validator now a cheating validator might send different transcripts to different validators but it does doesn't matter so each one sends transcripts to

different validators one designated validator say the first one Waits until it gets valid PVSS transcripts from validators whose weight is more than the threshold and then it Aggregates them to a single PVSS transcript and and broadcast it so we only broadcast a single PVSS transcript rather than 130 and this is much much shorter so this is the way we we implement this and this is why we need an aggregatable PVSS so H how can you tell that it has I mean obviously the person who brought can tell that it has weight more than W but how does how do I verify that okay so there is a okay so the question was how can we tell that we got messages from

validators of weight more than the threshold W so there's public information saying what is the weight of each validator and this information here these messages here are are signed so okay the person who sends the final message says uh this is the combination and it was constructed from player 4 19264 but now again if I need to validate that and someone equivocated to me and sent me a different one for player 17 I would get I wouldn't be able to check that what's going to happen is that this validator aggregated transcripts for a certain number of validators and he what he publishes is I got this from these validators you can

check that the combined weight is more more than the threshold and the aggregatable PVSS has the property that you convert verify that what I published The Single transcript is some of transcripts signed by these validators so everyone can verify that what I publish here was signed by this set of validators this guy could have chosen any subset here as long as the threshold the rate is more than the threshold a validator here might have sent a different PVSS to this validator or that validator it doesn't matter as long as less than the threshold number of validators are are trying to colluding together is there a single designated aggregator who is doing that or is everybody okay

so the question was whether there's a single designated aggregator doing that or not I'm not sure about the implementation I think that in each uh in each D EPO there's another validator who's who should be doing that but uh uh I'm not clear about that because we also have to do something if he doesn't send a message in time yes I'm bit confused by your answer what I be asked I can I can get intuitively that if there's someone who's cheating then we can detect that but you're saying that as long as we have above the threshold I have guaranteed output delivery as well I'm not saying about it's not okay the the the question was about guaranteed output delivery it's that's not necessarily the the case here

we uh I want to okay I assume that more than more than threshold of the validators send correct PVSS send correct PVSS shares say to this validator okay so uh he Aggregates them to a single message and um uh even though we had a choice of deciding which transcripts here to to aggregate together he doesn't enable it to bias because it doesn't know what's inside these transcripts I mean the both random values he can choose to combine different vandom values it doesn't matter now guaranteed output deliver I think you get it because this this

validator I mean we assume it's working properly if it cheats then we'll go to the second validator I mean one of them I so here I'm not sure how it's being implemented but let me okay maybe s here will know so everybody sends to everybody else then everybody locally Aggregates but posting We Do Round Rob in because the blockchain is uh leader base the first leader is supposed to post the pbss transcript if it doesn't then we go to the second leader and and then that's up yeah okay so so is the you know also both both cryptography and consensus guy so you said that these guys uh so he knows so they said that this guy are trying to post these things around Robin we start with this guy and if doesn't

proba we go to the second guy ET so just summing it up every EPO change we do multiple PVSS we aggregate them in broadcast only a single PS transcript and then every block every second each Val sends a share uh to compute the VF output and the nice thing is that each validator and have to show you how to do it sends a constant size share regardless of its own rate so before going into the construction talk about performance of cryptographic operations in general when you do cryptographic pairing operations a pairing is takes more time than Computing exponentiation and Computing exponentiation takes more time than the average time of computing an

exponentiation inside the MTI expon iation which multiplies a lot of exponentiations and actually uh if you replace n say 200 pairings with a single multi exponentiation of 200 values you can gain two orders of magnitude you can gain a lot okay so we want to do a multi exponentiation instead of many pairings another thing which is even more important is that communication is often more important than computation because computation you can paralyze and then do it faster using many CES and communication is harder to paralyze so communication is often the batttle neck so the VF will be as follows we have a secret key a and the VF will be the pairing of a public

generator age and the hash of the message ra to the power of the secret key so why does it look secure so age of the message ra to the a is is known to be sud ROM function and basically what we comp compute here basically comput a ing of a sud random output together with a constant age so basically we computed terministic function of a sandom function so this is why we at least it seems to be unpredictable okay so this is what we want to compute and we can also Define the VF as the pairing of H to the a the public generator R to the power of the secret key with the hash of the message this is how we're going to comput it and in a threshold setting no

one will know the secret key a or H to the a validator say validator one we know uh H to the power of A1 H to the power of A2 Etc as as as many as you know with as many shares that it has so that these AIS are values of a polinomial that shares the secret a so each uh validator will have these many as many secret you know secret key shares as its own rate so first key generation so the setup we agree on groups and generate at in the two groups and we also know what are the weights of the different validators this is public information based on staking okay this looks scary but let me let me go with

you through through this okay so to generate the key uh we know that the total rate says W so we generate a Shamir secret sharing of the threshold out of w shares okay just generate a polinomial each validator will have a secret secret shares secret keys in public Keys uh say validator of weight 20 is going to get you know 20 shares uh the secret key will be age to the power of each shares where age are elements in the first group a is generator of the first group and the public key will be Gat to the power of its shares where Gat is the generator of the second group so validator with a certain weight will get as many shares

as its weight and the secret Shares are values of you know these values of the polinomial in the exponent in the first now the validator now arguments his key what is this process so this is a secret key H to the power of the shares okay now he picks a random RI a secret that only he is going to know okay and he's going to keep it as a secret that only he will know and what he publishes is H to the power of r i and also each of the shares he got to the power of R so basically he publishes his private shares each of them raised to the same power of this random r that he chose and this is based on know Dy Helman

assumptions this doesn't give information about the shares now we want to verify that the information that the validator published here is indeed correct so this can be done using a pairing so basically what we check he published AG to the power of R where H is the generator we know the public key of that validator which is g to the power of the share and he also published here what should be H to the power of the shares times r i so using a pairing this should be these two pairing should be the same so is this the reason you're not just doing plain BLS because here you only need one pairing to verify them all but isn't that also with plain BLS why the the next the main reason we don't use PLS is

to in the next slide we'll show how the validator only sends a single value in order to compute the function regardless of its rate that's one reason we not going to use BLS and another reason we unfortunately cannot use BLS is that for the dkg we can only distribute a secret which is uh a group element say AG to the power of the secret and not so this I think is the the main reason we cannot use BLS because other things would have been nicer with BLS but basically here the the validator publishes his secret shares rais to the power of a secret R uh and here you can verify that's correct wait is that happening once this happens yeah this happens when at at

when the EPO begins after once every two hours when we do the once every two hours first the validator we do this Shir Shamir secret sharing which is a dkg where each validator shares a secret and then we sum them together and then each validator augments his secret key by raising it to the power of this R and publishes it so basically you don't know my secret key you know you know that I raised all the items of my secret key to the certain power of RI and I also commit to RI by publishing H to the poweri but both of these steps are completely unrelated to the validators like uh secret key for consensus it's unrelated

to the secret key yeah it's a different key than the key used for consensus completely it's this is key only for this survey youf both of those have to be broadcast and again they're both they're one is relate one has to happen after the other right so I thought you wanted to one round but am I correct that that's two rounds or can you do both of those at the same time these are two rounds I mean the first first is the the uh Fiat Shamir okay and the second is this thing uh and then the second thing is augmenting augmenting your your secret key I think that two rounds is is not so much of a problem as the interaction that was needed for pets and secret sharing like the main thing in Peters the main problem was that you know I I publish I send you something

and then you complain then we have to start others have to decide which one of us is is correct and which one is cheating and this way I publish this everyone can verify whether I'm correct or not using this equation here now every second we want to compute an output of the VF and to do this the only thing I have to do regardless of my uh uh input is if you want to compute the VF of an input on on a value M so regardless of my weight I compute age of M and raise it to the power of 1 / r i one over my secret okay so this is regardless of my of my weight you should verify that this signature share that I publish for computing the function on M

is indeed correct at a ra to power of 1/ r i but this is easy because before when I augmented my key I published H to the power of RI and if you do a pairing between H to the power of RI and age of M the power of 1 over r i then the r i is uh uh cancel each other and this is just equal to the pairing age and age of M so you can verify that I published the right function share now we want to cute the final output of the function So This Is How We Do It Let's Go it step by step so we have a certain uh subset of validators that contributed shares for the final contribution the first thing we do we verify that they contributed the right shares okay so we basically check this

for each one of them that they contributed the correct share this is one pairing per validator now now we want to do the interpolation so we take the augmented public key of validator which is this private key multiplied by these RIS and we PA this age of the share times r i we P pair this with age of hash of the message to the power of 1 over r i so when we do this pairing what we have is this R these r i cancel out and we get a pairing of H with the hash of the message raised to the power of the value of the polinomial so the trick here is this pairing cancels out this uh r i and we

get you know what we need ra to the power of the polinomial with these things we can do interpolation the exponent and compute the output of the function okay so that's that's the the main trick we're using here and the nice thing is that this share that he has to send is only one share per validator I don't get it though why why do you need that like why do you need a BL this by one over R given that everybody already has a you know you've already shared a so why can't you just do a reconstruction of e of H comma H to the m to the a so that EG that e term is essentially the everybody just broadcast shares of that that to their exponent so

the question was why why should why why should we do this so the the reason is that I'll be able to send a single validator will be able to send a single share regardless of its weight I mean another option would have been for the validator to send h of M raised to the power of its weight somehow unclear because we don't have the AIS themselves but this way he just sends a single value uh and this kind of cancel cancels out with all with all its augmented uh Keys okay so to sum up setup cost depends on the total number of shares which is like let's say 800 the validator cost per value ation is constant which is great verifying uh each validated contribution is a single

pairing but this means that if you get contributions for a certain number of validators we have to do a validation a pairing per per each one of them which is a bit costly another thing we cannot verify the final output what we verify here is not the final output but but the derivation process if you want to verify the output you have to go through the derivation process or if you get the signature of the of the blockchain of enough large enough thresold of validators that they all verify this then you know that this is correct security is based on the bilinear dman Assumption and just I'll go through this like in you know 10 seconds those who know have done these things 10 times it will look familiar

otherwise it won't look familiar so basically you want to be able to compute the pairing of G and G hat to the power of ABC so what you do you say en code uh the generator age will be G to the power of B the public B will be G to the power of a and when you answer questions about the output of the hash function of different messages M uh you just one of them you answer G to the power of c and you have to hope that this is the uh uh uh query uh for the uh uh input on which the you know adversary will be able to cheat and if the is able to cheat then you get as the output the

pairing of uh age and the public key rais to the power of c and this is what you get here basically uh and this is not the tricky part the tricky part is proving the security of the dkg that's and this is I'm not going to go into this so we are the pink ones the gray ones are BLS had we done this with BLS with as many shares as you know total number of shares so the evaluation time per part is much smaller enough our case it's constant uh the xaxis is the number of shares you're going to use and you see that in BLS it grows in our case it's constant verification time in our case is constant and the share size and what we have to uh uh broadcast is also

constant where it's not that nice is the derivation time of the final output which is larger in our uh construction because we have to do a pairing per participant however the total runtime of our construction is is faster because these things verifying each share okay in BLS you have to do it per share in our case you do it only per participant and these in you do a lot in our case you do much fewer so the total overhead of our construction is is is better because because of these items in which we benefit and the end to endend evaluation so this is in the paper for 112

validators the DK G say with 800 shares takes about 20 seconds every 2 hours and the onchain latency for computing the output is 160 milliseconds with all kinds of optimizations the code in production takes 30 milliseconds which is amazing uh it's really nice and let me just sum up so what we showed is a Randomness beacon in the weighted second setting we have a weighted VF with constant size shares we have new aggregate PVSS and dkg which I didn't go into uh this is a full system running on on the blockchain you know everyone can use it and security assuming the bilinear dman Assumption and there also

some open problems the dkg is still virtualization based meaning that if your weight is 20 you're going to get 20 shares it would have been nicer to give you if your weight is 20 give you just one share okay uh but this might have uh imply uh weighted secret sharing with constant side shares which is a hard problem the secret key that we have is a group element and not the field element and it would been really really good to use field elements here the other things we want to to uh achieve and which we cannot do with group elements and also improving the aggregation and and uh verification cost you know would always be be great that's it the uh the dkg running once every two hours so wouldn't

it like wouldn't it make more sense to spend have a I think with a more expensive dkg you you could get rid of the problem of having the group sharing the group element and you could maybe do other things that tradeoff didn't seem worthwhile so the question was about implementing a more complicated dkg uh because it's only one every two hours so I think the way I understand it like the main difficulty is the uh uh implementation cost like the engineering cost because should be know very reliable you know code that will not break in production now doing something which is uh uh non interactive it's it's

rather simple I mean you broadcast it you check when you start doing interactivity in blaming and and and comparing Etc it's it's much more much more complicated I think that one may if I understood correctly if I have to choose between the aggregatable which saves in uh uh uh the the the property of aggregating which saves on communication and the property of uh this being non interactive compared to interactive uh this being non interactive is much more important and the main maybe the main resource is engineering time which is the most scarce at the end you said it would be nice to get just one share the virtualization so first of all it doesn't seem to be a problem in terms of efficiency this virtualization

so how how crucial is it just a theoretical question or is it something that really would improve the and the other question is did you guys look at that um Chinese remainder theorem based approach and what would be the problem with that okay so the so about uh the question whether uh virtualization is a problem it would right now it takes about 20 seconds or okay but suppose you want to use 3,000 shells for better accuracy it will take much more and we would like to go that way uh also you don't know about the uh the stake distribution for the next Epoch uh until almost the end of that EPO and by the

way we do the dkg in the towards the end of the last Epoch and not at the beginning of the new EPO because otherwise if we were doing it only in the new EPO we would have have to wait say for 20 seconds in which Randomness was not available and uh uh we don't want this to to happen so this is kind of on the borderline about using the CRT based uh secret sharing that's it's really nice uh I mean I I was I looked at it a little bit I'm going to look at it more uh it's like a new protocol for doing uh it's actually not new it's not new okay so it's a new analysis new variant of an all the protocol of doing Secret sharing based on the Chinese made

theum uh one issue there is that uh secret sharing is not not interesting what's interesting is doing Secret sharing in the exponent to compute functions and that scheme was working over the integers and we need to do it like in in in you know in the field like in the exponent you couldn't I don't know if you could do the publicly I don't know if you could do the pbss but they were doing some sort of DK they were doing some sort and I'm so actually I'm not sure I mean I looked at it only for a couple of days and then not not more than that but that would be interesting I misunderstood something in your slides I thought the secret was a little AJ but you said that there's a it's a group element yeah I kind of so the secret okay so I kind of uh I took

the liberty maybe of being too playing with this so uh you know the secret you can look at it as as either being a or H to the power of a what we in our case no no one knows a I mean no one can recover a we just only know AJ yeah H to the power of a isn't little a a field element and isn't it a secret it just happens that in your system H to the a is what's uh so you can think of a as a secret but no one will get AJ a subscript J as a secret share because what you can get as a secret sh a share of a secret is only H to the power of AJ not AJ itself so the

secret you can think of it either as a or H to the power of a but no one knows the ajs the values of the Pol omals only them you know being used as an exponent and that is because of the PV asss property that's because of the P the aggregatable PVSS property that's the only way we can do it and the second syntactic question I had was so in your final protocol what happens is uh all of the transactions in Block I get ordered so that's a consensus message yeah and then after that everybody sends the um their share h of M to the 1 over RI and after that uh everybody knows what the value is and then you can execute the

transactions so you said the transactions are ordered and then after that you send sending your shares and and after that the transaction so it's not really after that I think in the optimistic case it's not really after that but maybe together think does okay and this is Falls or in the border line then can someone Rush the like can't you rush the like if if you send them together the set of actions is unordered at this point so someone can Rush right or no so you're afraid again I I I think so you're afraid about rushing and being a knowing the secret key the secret the out the randomness output before the transactions is ordered so that cannot be the case but we have to look at it

offline why why is weighted secret why do we need weighted because so each validator has a different weight in our setting some has like some have weight 20 and about one FD of the validators have weight one and we don't want validators to send as many like for each VF interaction we don't want to to send as many shares as the weight because that's going to take it's going to be too complicated I mean too too uh too slow uh are you looking into extending this to time lock encryption um time lock encryption where you would encrypt a certain time and once the Bon value becomes available at that time you can decrypt so if I understand and the question can we use

this VF also as a decryption key to decrypt things so that's actually a great uh you know a great goal uh there are two issues I mean both of them can be solved one is that here we do a new secret sharing every EPO every two hours so if I want to encrypt something to say next day to next day I have to know what's going to happen so that so in that case we'll have to somehow keep a secret over more than one Epic but that that's that's possible just have to reshare the previous secret secret it's possible uh the other issue is that to do a decryption we can definitely do a decryption uh by the validat is Computing at decryption however we don't want them to

do no for each contract that wants to deip something we don't want the validators to work for that contract now they spend say 30 milliseconds doing Computing a v VF that everyone can use we don't want them to spend you know 30 milliseconds for every contract that needs to decp something because validators need to validate they don't need to spend time Computing this or you have to pay a lot of gas for that ideally what we would like the validators in each uh block uh to do like constant amount of work that will equip all messages equ equp it to that block one way to to do it is using ibe uh but to do ibe we need uh we don't know how to do it using uh uh a secret

which is a group element we need a secet which is a field element uh maybe there's another way using group elements or maybe we should move to uh uh working with uh field elements [Applause]