Building Secure Distributed Computing Systems for Blockchains, Over Blockchains with Aniket Kate

Transcript

Welcome everyone to today's A16Z research crypto seminar. Um very pleased to introduce today Anaket Kate who's a professor at Purdue. Um and he's worked broadly in lots of areas related to the blockchain space, applied cryptography, security, game theory, consensus. So welcome. The floor is yours. So >> thank you. Uh hi everybody. My name is Anit Kate. I really thank Tim and A6G crypto for this invitation to meet the team and the interns and I look forward to interact more uh through you for the next three days. So uh I gave uh going to talk about an I idea which is general and can be related to several of your work but I thought it can be looked into a nice umbrella term what we can call as

building secure distributed computing protocols or systems for blockchain and over blockchain and I'll explain what I meant by that as we make progress. So probably some of several of you already know me and we got chance to talk otherwise I work on uh secure distributed computing in general. I use this term I actually stole this term from Christian Kasha uh which I find use up. So my work is with is is with cryptography and distributed computing. So the secure distributed computing is term that we use. I work on some of the uh SMR or state machine replication protocols and blockchains also some MPC stuff. I have a interesting discussion uh regarding what can we do with the MPC in general. uh I was I won't be able to

talk about that today much but I highlighted that in case something that is interesting to you I'll be happy to discuss more uh earlier I work work quite a lot on anonymous communication came as a as a heritage from my adviser so I work quite a lot on anonymity and meta privacy and uh recently I started to venture into uh bringing game theory and cryptography together and there are some interesting results which at the same time are challenging and happy to discuss them as well with you uh if there are some things that we look into.

But now let's get into the topic of the discussion today and to explain the idea I'm going to talk a really real world practical problem uh closely related to blockchain which is a distributed oracle agreement or as we can as blockchain oracle problem and let me quickly explain the problem first. So the whole idea is that there are off-chain resources which have uh data and uh blockchain systems are closed system in some sense that they cannot collect this data uh by themselves and that's the reason they have to be provided that data okay and uh they cannot connect to this entity outside and that's the reason we required uh we need to solve this problem to to bring somebody in between uh who can provide this data and

that's where this blockchain oracle networks uh come into the picture who are supposed to collect this information and submit that to blockchain. The way to look at this is however it's an abstraction. Conceptually it can happen that there is a overlap between the blockchain oracle nodes and blockchain node itself. But for our discussion just assume it's a a separate abstraction distributed system abstraction that has to be uh resolved there. Okay. So that's what the Oracle problem is. Let's try to understand that bit more. So the typical idea as the core thing is there could be multiple sources for the same data and uh it may be required that in such a space we collect information from multiple data sources and each of those

Oracle network nodes makes up their own opinion uh which can be by which can be generated by computing mean or whatsoever and they have a input that they want to give to the solving this Oracle problem. Okay. So that's the abstraction. So uh we with this abstraction we throw away the data sources completely we don't need to keep them in understanding we'll assume that somehow each of these node have made an opinion about the value that problem itself can be look at you contact majority of them as long as most of them give you correct answer you average out mean all these things work out but not so interesting we'll just assume that each of these oracle node have problem but then what problem we going to solve the first thing to consider is that what model are we working on right and uh I

guess So we'll see that um at least in my most of my work that that I look into I try to build those solutions assuming that network is not synchronous and so we work with the asynchrony so that the messages are always delivered between two honest parties it may take some time but they are they are eventually delivered and uh uh we can't define that bound uh but uh but there is a reliability associated with that and as well as partial synchrony where we actually assume that there exist a special event called GST or global synchronization time and after that event the messages are regularly delivered for a known value of delta okay uh most of the discussion that

we'll be doing today I'll be working asynchrony but uh sometime maybe partial synchrony can become relevant uh when I'll talk about it but u so basically uh this model I find to be we want low latency really fast system with high throughput and in that case I find Building building typically think with asynchrony to be better than going for bounded synchrony as a uh just as a thought process but uh happy to discuss that later. All right. So now in this or uh in this system uh how does this uh distributed blockchain oracle problem looks like. So in such a system it will be more that we have a we need a protocol among nodes uh and each of each of those node will have input vi. Okay.

And what we want to make sure that a termination that all the correct observer eventually decide on value. We want to make sure that that there there is some kind of a termination there. Agreement that the output value for all the correct observer is the same. And uh very interestingly we should have minmax validity which means that the out output value coincide in the range of the honest input. So if if you take the all all the honest correct input and if you put that in a range then uh the output the final output should lie between the min and max of that. Okay. So uh in a way this problem if you see uh uh we know that when we in partial synchrony or in asynchrony required 67% uh uh honest parties in general and it is very

similar to bisentan agreement uh problem not exactly binary I mean one could think in that way but uh the most closest problem is convex agreement because this minmax can be looked at more like a convex range and as you can see if you can go to multiple dimension and still it remains in that sense right so it's a a convex agreement problem >> so we to think of the vi as being numbers. >> Yeah. So for my for my for this talk we can assume vi number but the problem can be extended to vi to have uh other other meaningful things associated with that.

But uh we will require somehow comparison uh kind of operation to make it work out. But uh uh in but there may exist indeed a domains where uh it could be more complex than that and maybe we still haven't thought about a correct definition because the minmax validity can become difficult to define. What does it mean by that? Yeah. But for our talk just assumes it's a numbers. So uh what's a what's a a typical approach to solve this problem? Uh uh because we say it's similar to the convex uh convex agreement or BA agreement. uh what what's the the firstand approach to solve this problem?

The first hand approach could be you take these information sources you build basically uh we have existing protocols for Bisantine agreement or convex agreement problems and we solve those problems themselves and we publish a value onto the blockchain. Okay, just submit the value to that looks like a very straightforward approach, right? And uh the the interesting thing here is that uh maybe it can be nice thought that can uh that I can put in uh this space is that so if you look at the blockchain itself it's a uh it's a it's it's a distributed system by itself and it solves the consensus problem. So but if you look at this figure it kind of

looks like I'm solving the consensus problem twice. I'm solving that first for this BA agreement and then onto the blockchain. And I really uh the question that we asked is that really necessary and that's where could be a good starting point uh for to looking into that. Uh let me go in bit more detail here. So uh yeah as we say blockchain they are state machine replication. I guess uh in this room probably I don't need to go into the properties into detail. uh but I'll just quickly mention that means uh transactions are ordered and or inputs are orders and we make sure that they are uh this order can be consistently viewed by all the parties they may not see that in uh in

simultaneously but if I see a order uh then I know that you must have seen a prefix of that or maybe my what I see is also prefix of your and eventually we all going to see all transaction eventually okay so that's the informal guarantee. Uh we also want uh some kind of a lioness that if a transaction is submitted then eventually get added to this blockchain and uh so if we have we have such a blockchain available and the question that we ask that can we just use that to solve my problem of doing uh oracle agreement okay and uh and I'm just starting with a very simple protocol to just show that actually it is uh it is easily possible. So what I'm doing here is that I'm just building a

very simple four node network. Okay. And one of them can be Bentine and uh each each node have their own opinion, their own VI value. They simply just take their value and submit that uh to a blockchain smart contract or SMR and uh what we because we work in a all these flows are asynchronous. So we cannot wait for all n input. So we should make opinion after getting information from N minus F. In my case uh 4 minus 1 that is three messages. So you collect this information you compute a median and you say that's my output and so among let's say in my example there are three of them and two

transaction two and three include inputs from the honest parties node two and three. So when you compute the median uh you know that it is in honest range input okay when we compute three values median. So uh so what why is this better right the first thing is I'm not solving the consensus problem outside okay the this is purely asynchronous protocol and uh what do you mean by solving consensus problem uh so this is just at least why my way of looking at it that because I'm in asynchronous world or I'm non-synchronous world I have to overcome the FLP impossibility like impossibility that we cannot have consensus even when there's a single node that can crash and I have to solve

If when I do the solve the consensus uh problem outside I overcome the FLP to solve this BA problem and then I solve again somehow my blockchain must be solving that again but here in this pro this flows are completely asynchronous and uh property that achieve is that uh I'm using basically SM I'm using SMR to solve the BA problem okay at the very conceptual level that's what uh it turns out but there are more benefit that I'll try to bring up but that's the core simple idea in this space. So uh there is no need to solve the consensus problem before touching the blockchain and u the advantage of that is we don't need to make partial synchronous assumption or timeout or we need common

coin if you're working asynchrony to solve the problem. The flows are completely asynchronous as I already mentioned. So uh that's the advantage uh that we we observe over here and uh that can be uh that can certainly provide the property that we look for right but uh but the thing the problem on this uh space is that uh now I I want to become greedy right so uh the disadvantage here is that uh if I have end parties I will have to try to submit all end messages to the blockchain okay and uh gen one of the one of the important thing that may be necessary as any blockchain system may want. They do not uh they want to reduce the number of traffic and the

data that goes to the blockchain. So this complexity of publishing on blockchain I want to avoid that. Okay, that's a that's a very natural thing to go for right. So uh what can we do in that case is that let's say we we can work on that mechanism by uh this we pick a subset of node which we call as aggregator node uh conceptually uh this aggregator node we only rely there on livveness. So let's say I pick only uh t plus so if my t is the number of bad parties in my system this threshold will be t + one but we can use some statistical error and even further reduce this number of aggre aggregate nodes but let's say it just uh as long

as one of the aggregator node is live uh my system can make progress okay so what I'm collecting is rather than everybody just publishing their out uh their input directly to the chain I can they all can send their inputs to the aggregator nodes Okay. Uh aggregator node just computes then median and say that okay here's the median here is how it is computed from all these inputs the uh okay I'm assuming that the inputs are assigned and send that information again back to for approval to the same uh same oracle nodes. Okay, this is that okay I see that it's coming from a right set of inputs and that median is correctly computed and I take those inputs and basically I they all say that we approve

this inputs and they sign the median value saying that this median value I agree that it's signed with the correct set of inputs and uh they only they don't need to send the data again the entire data and the sign medians are now collected by these nodes and once that happen now only requirement they have is that these aggregator nodes collect take this information uh if it is threshold sign then they combine it if it is multi- signature whatever all these things work and that's the final output that create and they submit that output to the blockchain so now rather than all the nodes nodes connecting to the blockchain I reduce that problem to just a threshold a small number of aggregator nodes submitting that to blockchain and uh eventually I I'll say that this is a

bare minimum requirement because you will have to have at least there should be at least one node live for your system to submit any thing to the chain. So in that s it's a bare minimum requirement in this particular space that we can build with and again very importantly these all these flows are purely asynchronous so that uh we we don't we are making we are not making any assumption regarding partial synchrony or we require any common coin to solve these problems. Okay. So uh that's the u that's the key idea here. Now uh let's look at what happened in this space. So so we we know how to solve the problem. Yeah.

>> So going back to the previous slide um so you had like multiple rounds right? So, so the oracle sent to the aggregators and then the aggregators have to send something back to the oracle and then is there a way to shave off that round using let's say some sort of snark or something where you say oh in the first round itself the oracles would sign off on something and the aggregators just say okay here's a proof that I included whatever I got and uh this is the computed median >> yeah so uh let me repeat the question is that can we use some cryptography technique like snag or some zk proof towards reducing the I think reducing number of rounds could be hard. Uh one more aspect here is because is all to one one to all to one kind of a structure that gives us communication uh

efficiency but it could be possible to do that. uh uh uh I'm trying to think but maybe maybe one round could be saved but uh we are not used to using any ZQ or whatever because here uh only thing required is threshold signing from cryptography but uh >> yeah I guess >> maybe one round could be saved here and there >> but you're saying it's not worth the >> it may work in some scenario because at least the oracle thing everybody want really fast Oracle so uh this reason is good for to reduce to make whether you have better throughput but uh sometime it may be worth saving that one round.

Yeah. Uh >> I I think also even with snarks you still have to do a round to compare things. Say like the the lead >> the smart contract could maybe do that. >> Oh okay. >> There's not that many aggregators let's say. >> Yeah. So and here any basically both of them can have two different valid inputs but we say it doesn't matter whichever appears first is the our output. That's the uh that can be very simple way to look at it right because order will decide what to which which are among them to pick uh I yeah now that we are topic I kept it things simple uh this signing part however I'm sending it to Oracle node but because data is signed we don't need this Oracle nodes to

actually do it can be any committee I'll see it can be any only any honest majority committee can just sign that but that's just a side note uh but okay uh for simplicity I keep this again same Oracle node but they don't have to be the same node uh but then coming to the problem uh is that if you look at this so let's let's call it SMR assisted Dora or Oracle agreement interesting thing to observe is here is that because of this minmax validity condition we still required two3 honest majority okay the way to look at this two-3 honest majority it's a separate I'm using uh state machine replication as a oracle so this has nothing to do with the what's the complex what's the

requirement in terms of the number of bad parties in this oracle it's a separate thing uh so in this sorry in this SMR this bound talks about this oracle network that is still required or super honest majority okay uh it's I mean you'll soon see that it's very interesting because you see come on isn't are you working in non-synchronous system so you are always in uh 3F+1 and basically my talk will be sure that no there exist many instances where we might be able to even break that bound. So no FLP impossibility and top of that maybe we'll be able to also improve the uh improve uh the fall tolerance of the system through this way. And for that I'm just going to start with the another interesting assumption let's say. So

let's say I make an assumption that uh inputs that are coming from honest parties will be all in a kind of a close to each other what we can call as a coherent coherent cluster which which I mean that all the input values from a coherent clusters are are in distance delta with each other okay let's say that's the assumption we are making that they are in almost in the same thing okay uh in that case then I can have uh more like an approximate mean max validity where I can make sure that uh so initially I said my input my output will be in the range of ons minimum and ons max now I'm going to replace that my output will be in the ons uh h ons mean uh minimum minus delta or h ons max plus

delta and if you I do that I can solve the problem uh that oracle problem only for n greater than 2f basically simple honest majority okay uh to emphasize why this is interesting is that let's say I take away access to the blockchain or SMR problem and even if I have such a assumption available on my input that they are from a coming from a coherent cluster I will still require 3F plus one because it's just like again a typical solving the consensus problem which we are solving by blockchain right so that that so another advantage I find about thinking about the problem such a way is that it allows me to uh somehow

uh overcome the boundaries with respect to uh uh with respect to fault tolerance itself which otherwise we cannot solve. >> I'm trying to figure out how to what extent the claim is that like the usual approach wouldn't work versus there's really a fundamental impossibility result. So >> so like if you took delta equals zero so if you really needed between the min and the max yeah there is an impossibility result saying that n greater than 3f is necessary. Yeah, I think it should it should be easy to prove uh even from the slide. I mean some somehow it's so so here uh I think at I must have written down somewhere a proof but it was very natural to if if we uh so if we do not know such delta then it will be n greater than 3f. Uh the the way to look

at uh I mean because I'm in a synchronous world right? So I have to make progress after getting n minus f messages and among n minus f I want to make sure that uh honest inputs are in majority. So that's the reason this uh n minus f should be at least two uh greater than 2f. Yeah, the second the second step I'd say is intuition, not so much a proof. But >> yeah, yeah, yeah, but I've written down it uh to uh it follow the standard why BA required 3F plus one kind of a proof >> and then so that argument doesn't work on the right because >> because now I introduce this uh uh uh the range and I say all the input honest

inputs are in a range. So in that case you would still so what would you do if you had the cluster where that was sort of >> majority Byzantine output. >> Yeah. So uh >> so you have to make a decision with n minus f again you're saying right? >> Yeah I have to still make decision with n min >> and you might have minority honest right? >> Yeah. >> Okay. >> But uh even when you have minority honest but I know that all the inputs that are honest will be coming from this session. So yeah that should be clear uh here. So let's say uh again I'm just working three examples. So node three is slow. We don't get it's honest but slow.

I only get a input from the bisentine node which is in the delta range from the second value. So m_sub_2 and m1 will be in a range of each other. So that's reason whatever uh whatever value I compute will be in uh uh >> oh I thought it was honest inputs or delta apart. Yeah it's >> if Yeah. So if dishonest input on other hand is not in the range then I'm going to discard that and wait for the third one. >> I see >> because when I look at the input from honest party and dishonest party said oh they are not in delta range from each other. So I can wait for one more round because it's assumption on the system.

>> I see. So you you can then identify one of the people is okay. >> Yeah. Yeah. >> Okay. Okay. Okay. >> Yeah. uh but on the other hand if we do not have SMR available we can't get that and then we again go back to 3F plus one word yeah >> yeah so it's almost like a very weak form of accountability where you know there are bad guys you just don't know exactly which ones they are right >> yeah okay yeah also very interesting I guess we did not go into the accountability it's very it can be very interesting to think about accountability for oracles and I think it's a very good problem uh because the value at stake there is also equally uh we have seen examples in practice where uh some input wrong input from Oracle resulted in significant losses. Right?

So introducing accountability can be interesting as well. Uh because here if in this example they will realize that M2 and M3 are in the range while this M1 is too far and now we can be in principle hold that uh node one accountable eventually. >> I mean maybe intuition for delta equals 0 is that uh you have a promise either all the honest have zero or they all have one. >> Yeah. So now you can solve that with 2F plus one because basically if you get a mix >> then you know you can wait for f plus one of one of them. Yeah. So that's kind of your algorithm.

>> Yeah. >> So yeah. Yeah. I mean you in fact I started with delta x is equal to zero simple example. I realized that they're just too good to be true. And uh we also checked the data that's coming from exjes and we found that in I should have a slide about that. Okay. Yeah. So it's it's old slide. uh so I don't know what's exactly that's happening in this space uh but what we realize that we look at the uh in data data that we collect from the exchanges and uh this agreement distance is all percentage and we found that most of the time inputs that are coming from they are are close to each other so we can uh pick the clusters can get formed even when you have a a diff this is percentage number so if the value is 100% that most of the

inputs are typically when most input from if you consider take from these different exchanges they are in close range of each other. Okay. uh uh I mean interesting like how you pick delta uh uh by the we I mean I not going through talk again but it can indeed happen that the values are not in range and then we required a fall back in such mechanism but fallback can be built on top of that it's just that uh in a purely theoretical sense an adversary can slow down my message and always go to the fall back with 3F +1 but for our discussion just to make sure that the problem is interesting assume that the data is known and we fix it. Uh but even if it not fixed, we can build fallback

but that's a uh that fallback will be trigger when indeed values are not in range or if adversary just slow down everything because it's more like a still a synchronous protocol but you have to just decide that hey we are we are not making any progress let's fall back. >> What what are the units on the x-axis? >> So x-axis talk about agreement uh distance. So how much let's say uh I take a exchange pair and I look at the current value and let's see if that's 100% how much was the difference between two uh add two couple of uh let's say I'll take exchange one and exchange two and how much was the difference between them >> right but so the units that's so that's percent >> yeah percentage yeah that's a for

simplicity I >> 6% not not 60%. No. Yeah. Yeah. Yeah. Okay. >> Yeah. Sorry. You're right. Actually, I want to change that. I forgot to add that part. But yeah, it's not significant. Yeah. >> But even beyond, I mean, if you look at some real world data, it can be even smaller than I mean if let's say we are taking weather information from multiple sources, we expect honest sources to be very close to each other, right? So, uh yeah, now that was just uh that was a one of the easier thing I realized it can be nice to explain. So uh what I want to spend rest of the time say that actually this 15 honest honest majority protocols are common in the blockchain environment again in the asynchronous

and partial synchronous setting in general and maybe this is the right time to uh talk about the uh uh the clause in my title right it's uh this I'm talking when we're building protocol uh for blockchain and with blockchain means that I uh when I talk all the scheme I'm talking about my my final outcome or output is appearing on blockchain and I'm and because of that I want to also use this blockchain environment itself towards solving this particular problem and uh if that's not the assumption if output output is for to be used outside blockchain system maybe some of the technique that I presenting can become less interesting uh but at least for

that setting which is uh for blockchain with blockchain uh this this provides an approach approach which certainly should have benefit rather than solving the problem completely outside and just publishing the result on blockchain. Okay. So that's the uh generalizing idea but there's so one more uh interesting way to look at this problem you see that okay so you try to solve this with only honest measure why it's interesting because a we are increasing the uh fall tolerance which is good but uh I find practically another direction of looking that interesting where I might be able to solve the problem with fewer nodes. So let's say I have a system which has super majority but to solve my problem I only need to work

with the uh with only honest majority assumption. I might sample among those among those systems for for some for some statistical error and then uh the advantage is that because I'm sampling for such a a small committee for statistical error I am solving my problem efficiently and I can actually improve throughput of the system because uh now I can create multiple such committees and each of my committee will solve a separate problem or multiple instance of diff uh uh same problem and because of that I improve my throughput.

So I find in fact that to be another angle to look at uh why going for honest majority is helpful in some of the system. Right? So the way I see that is uh the terms is that let's say this whole thing is what we can call as a a tribe of super honest majority and when I when I can create multiple clans or committees among them which has this only honest majority and for example just to give example let's say I have n is equal to 500 nodes for statistically 2 is to minus 40 uh I could create uh easily four or five clients or committee out of that so uh I'm solving the problem uh with a throughput gain of four times easily because of that this

approach just as an example uh I can include okay so I'm just using clan uh tribe as a entire structure and clan is individual committee just for the uh simplicity of understanding so uh as I already promised uh indeed this approach has uh advantages uh in multiple environment I claim that right so uh my talk will be now looking to some of the interesting examples right so what so what will the overall approach. So we assume that what blockchain offers is a mechanism uh which is executed and drive for super honest majority and it only thing it provides is provides a way to have integrity or ordering into the system. I'll not try to use that for anything else more than that. Mostly I

think I'll remain uh true to that uh assumption. U yeah at least in the example that I'm showing today uh because there are just so many nice example that somewhere I might be using that for more okay no data need to flow through this process and then I'm trying to look at different examples and see how it functions right so we already look at the first example of the Oracle problem right uh but uh very interesting example is if you look at the reliable broadcast or data delivery or aid problems right so in fact there's a paper uh with yokim which uh the AFT 2020 paper where you are doing where you show the spread spread of spectrum in terms of this semi aid problem right uh that's example of the

reliable broadcaster data delivery where again we can conceptually solve the problem of just delivering data in only an uh honest majority system we do not required uh 3 F+1 so a typical derable broadcast requires super honest majority but if we are trying to do what with the help of blockchain uh we don't require that assumption. We can solve the problem only for uh only for majority. Okay. Uh yeah. So so another example I do not include it here is that blockchain execution problem. Uh if I want to uh if you look at that means I am already done executing. So most of the uh recent or

what I can call as a third generation blockchains they differentiate data dissemination ordering and execution. And if you look at the execution problem once the ordering is done we can solve that only with honest majority again purely asynchronously okay because ordering is already done and uh the parties are supposed to just execute and as long as majority of they say this is the outcome we know that that's what will be the outcome. So execution is also one pro one more problem in this space. So just so understand so there there is always a twothirds >> honest assumption for the blockchain validators right and it's just there's this separate group that's it's only the honest majority right >> yeah so thanks a lot for asking that

question because I wanted to mention I forgot so the question is that do you always require honest super majority assumption for blockchain so one uh again it's my thinking also involved right I would have given answer one year ago yes but the way to look the way I rightly look at that is It's up to the blockchain where we executing this. So if it is a blockchain, it gives me as long as my uh ordering guarantee and it gives me my eventual termination. Anyhow, I leave that problem to be solved by blockchain. As long as it give me ordering and eventual termination, I'll just use everything beyond that uh as it is. So in that sense if we have some blockchains for which we have

proven security with uh synchrony for honest majority uh the because all these flows are purely asynchronous it doesn't matter for that but uh but u for some some some advantage to really come to the floor it will be really good to have super honest majority so yeah for the rest of my talk uh okay I'm doing good okay I'll be focusing on uh the DKG and threshold crypto and multi-party computation to just give intuition there uh and and there are some interesting uh open problems that I also try to spend time on that okay so uh now uh I'm slightly shifting the gear I'm going from distributed computing to more like cryptography protocols generally if you look at threshold cryptography multi-party computation uh many commonly

uh we work in here with honest majority and there are properties like robustness uh uh guaranteed output delivery fairness there is a concept called security about which are very common properties in this particular space. So not all the protocol there exist solutions in asynchronous space. Uh but most of them typically they make assumption uh that the network is uh synchronous that means pointto-point links are secure and uh and they're synchronous and they they say that B once we give that we can build what is known as broadcast channel. I'll go into detail exact what do you mean by broadcast channel in case somebody is looking what does that provide. So it's a B broadcast channel bulletin ch

bulletin assumption and uh once you do that you build protocol on top of that that's a very common approach that consider we already discussed that so uh can we really consider in uh internet to be synchronism is to build broadcast channel is a very interesting question and he this is the probably the most controversial side uh that indeed I do get uh some um some questions certainly uh from cryptographer uh crypto photography audience is that at least uh the way I think about it unless the latency per round is not in minutes or few minutes uh in general uh then internet cannot be considered to be synchronous if you have a high

throughput system where you want to make sure that you don't wait really long then we should not really consider network to be synchronous is uh is what I'm going to claim uh where my discussion will be based on uh just again to complete the story there do exist uh some synchronous protocol that that are built and libraries are available for them and if all the nodes are honest in your protocol and they behave honest during the execution uh the protocol may finish even when the network is not synchronous because they'll just collect all the messages and it will finish but it's very uh the moment some nodes go wrong you will at least uh lose liness and uh in some application uh loss of livveness in uh

in a subprotocol may result into a loss of safety in the higher protocol. Okay. uh just to give concrete example for that let's say I'm building uh some let's say a beacon protocol or uh random beacon protocol or I'm building some kind of a randomness generation protocol uh then if an adversary do not like a particular random value they can just not do not participate in uh that generation that random value and because of there there's a lack of livveness but uh be that will reduce bias to the output generated and can result into correspondingly safety failures. So uh there could be more example in fact uh I'm in search for more such concrete example uh but that's reason I generally

do not find making synchrony assumption to be uh that accurate unless my protocol can be really slow and I'm not worried about finishing it fast. Okay. Uh yeah happy to discuss if somebody uh about that if you have a question or concern right now this broadcast channel I mentioned uh for sure there exist a really concrete definition for that and it is known as bisentine broadcasts and uh these uh properties I got from one of it paper in general so where they look at this with bounded synchrony what properties we want uh regarding so the idea there is there is a distinguished broadcaster uh uh who submits a value to be broadcasted and what we want to make sure that uh

that all all the honest parties they agree on some value which is exactly the same. So m is equal to m prime if broadcaster is honest then all honest parties commit the broadcaster value and the protocol terminates. That's a typical uh this exactly is what we can define the formal definition for broadcast channel or bulletin board which is sufficient for most protocols. uh uh there. So uh the interesting thing is that the moment we go beyond bounded synchrony we just can't achieve this really strong definition and we have to go to weaker definition which is in partial synchrony where where there's a very interesting property that if the broadcaster is honest and GST global synchronization time is zero then only replicas will commit to broadcaster

value otherwise we cannot give guarantee. it drastically significantly reduces. Okay, I think this is also uh very uh interesting comparison between I think synchrony and partial synchrony. uh the definition drastically change because this problem single producer or source here right in many of our SMR or even BA multiple parties give input and that's the reason we can deal with it better but here there is just a single proposer and it just disappears what are we going to do is a uh problem and that's the reason there is a drastic difference and uh the protocols uh that are built uh in cryptography uh the this definition the partial synchron definition uh is not s sufficient for

them to uh uh suffic is not sufficient for their in fact in that case they some of the honest parties can also be considered as being wrong or crashed or been malicious and the protocol will at least will livveness will be broken and sometime even safety can be broken now let's look at the the general problem we look at uh so if you look at secret sharing or a verifiable secret sharing DKG MPC MPC is the most generic form of these. So that's the reason I'm starting my discussion for that. So if you go for MPC beyond synchrony beyond bounded synchrony then again we required super honest majority protocols at least.

Okay, for some thinking it can also become for uh even like we required 4F plus one and uh but along with that there are interesting challenges that come up like increased complexity because of dealing with network asynchrony and common coins you required uh in such a setting or dealing with timeout or view change and responsiveness partial synchrony we have become good at that we have built all these nice distributed computing protocol but still it will be good if we can avoid this problem if you're solving MPC problem for blockchain with blockchain right our theme. So uh some of the existing MPC protocol or blockchain have been proposed but if you look at the definition clearly they kind of assume that uh uh blockchains are broadcast channel and that I find to

be a a very challenging uh assumption for our discussion but more importantly so let's say uh I mean coming to against uh the question that team asked right uh what about underlying blockchain is built assuming bounded synchrony right where security and everything is based on boundary the security I'm still going to say that state machine replication or blockchain really should not represent this broadcast channel uh for one more reason is that uh there is one very unique thing uh possibly unique thing for blockchain is that even when we have in synchrony uh there could be motivation for the nodes or proposers so that my transaction doesn't reach the blockchain in time because of front running lots of other transaction came

or congestion in general so uh when my transaction get added it will be get added into some block but there is no guarantee that I I submit a transaction and my transaction will be getting added in a predefined time delta unless that delta is maybe a a day or something like that okay so uh that's the reason I find it very difficult to take any blockchain today and say that we can use that to build bise broadcast or broadcast channel because uh all honest parties commit and termit we just can't uh go for that property in this like how long do we is always becomes the challenge in this particular space. I mean this become challenging because we can't differentiate between a broadcaster who submitted the transaction and it's not

getting added to the blockchain versus the broadcast who just did not submit transaction and just waiting. Okay. Right. So uh that's SMRs are not broadcast channel as I think uh the difference I already explained here. So we have to have a fixed delta. Many of these protocol use this assumption that uh you save me something in time delta otherwise you crash or you're all right with the input right we use both of these definition if you look at the synchronous SMSRS and blockchain based primitive and that can be quite challenging in general while here we only have eventual G protocol my message will be added eventually I don't know when right so uh that's we we can assume that the SMRs are not exactly broadcast

channels and but still now uh is there a way out and that's where The interesting uh thing we can observe that can we still have blockchain assisted MPC protocol design where now we don't use them as a broadcast channel but we use them still as a state machine replication or atomic broadcast okay uh in general and answer is yeah we we see that there are interesting uh possibilities here and as well as impossibilities and that's what I'll try to explain. So if you take the verifiable secret sharing primitive I assume uh everybody's aware of that but very quickly verifiable secret sharing mean there is a a dealer who want to secret share a particular value and dealer itself can be malicious so we want to sh make sure that even when

dealer is malicious any subset of uh sufficient number of parties can decrypt the exact same uh secret that may be what dealer is mind or whatsoever but you take any T+1 party they're going to uh uh reconstruct the exact same s is the requirement for verifiable secret sharing. If you use VSSs with broadcast channel uh that require we we we have lots of protocol for 51% honest parties. Okay. Uh very interestingly we can even have unconditional hiding property okay so my uh so similar to commitment if I have unconditional hiding but computationally binding or correctness property then we can do it. If I want both unconditional hiding and binding

then we have to go for 3F +1. But uh that's that's completely completely unconditional protocol. So we can skip that for now. Okay. On other hand the moment we go from uh broadcast channel to asynchrony uh the requirement shoots up and now we required 67% on its properties and there are very interesting protocol that has uh that are possible. We can solve this with uh pattern commitment hash functions all these things are in general sufficient in this space. Okay. Even statistical vsss is possible for 3F+1 whereas is unconditional but statistical. But if you want perfect where we don't even make the statistical thing then it becomes 4F + 1 for the completion. Okay.

But now I'm good to show let's see I want to build such VSSs again using my uh my blockchain as station state state machine replication or ABC uh can I really do that and let me give a really simple example to uh to how to do that. So uh let's see uh there there's a concept which is already existing. It came with the name publicly verifiable secret sharing but one can also call them as a non-interactive VSSs. Okay. Uh so you can build publicly verifiable secret sharing by interactions but non-interactive is maybe more uh exact concept. So what can a a verifiable secret sharing uh dealer can do is that take is take it secret generate the

shares from that S1 to SN encrypt individual shares for their uh their individual uh recipient okay for their own public keys generate a zero knowledge proof that the all shares are are correct so that when you take any t plus one of them that they will be generating exact same secret okay so you can have a nic for that and just submit that transaction to blockchain. Okay. And uh these protocols when they build into the theory they assume this is a broadcast channel but here even when we replace that with broadcast this broadcast channel by just SMR that is sufficient.

Okay. Uh you'll see hang on actually why you are think this looks like too big of problem. VSS is a completely asynchronous primitive we don't need to overcome the FLP boundary. uh so indeed I can replace in this example the state machine replication or SMR by access giving access to just a reliable broadcast uh primitive but it helps me in my rest of the talk so that's is believe me that I'm using SMR basically I can just take this such a vector and reliable broadcast that to all the parties and that will be sufficient and we can still just solve the problem for n greater than 2F okay uh >> so sorry the point is this this approach to vsss doesn't need the doesn't need to bound on um you know termination from

the primitive is that the point >> yeah because >> the blockchain's fine even if it only gives you eventual >> delivery but that's sort of fine in this case >> that's fine uh so vss is a completely asynchronous primitive right so that is then we don't need to overcome it's not a consensus problem yet >> yeah and then the the ordering is is good enough basically >> yeah anything any ordering is sufficient uh very interestingly uh is that this only offers computational hiding property because we are using encryptions. Okay. And uh I mean there's the intuition again uh I'm just let me just put it that as a conjecture because unless I have a proof completely written down I don't want to claim that as a complete result and I'm going to claim that we can't solve this problem if you

have if you require unconditional hiding property. So by under conditional hiding just so that we get it uh it's a it's a weird assumption uh for a practitioner but theoretically it's fine. to assume that all the participant they have secure point-to-point links with each other okay they are given to you and now you can have a protocol which is unconditionally hiding so what happen with unconditional hiding so if I use pison commitment uh it's unconditionally hiding so if I have secure channel and pison commitment I can do create a protocol in concept uh in concept which has unconditionally hiding right uh hope I guess I I couldn't go into the detail but hope that basic idea was But I'm going to claim that uh this you even

when you have access to free RBC as a or as a black box or if I give access to SMR uh free access I cannot solve this problem of uh if I want to have unconditional hiding property it's exclusively possible because I add encryption okay I'll be happy to go in detail but yeah >> there's this classical U and I think 89 >> Ben or Robin MPC right that basically show that if you have a broadcast channel >> you can get statistical security. >> Yeah. Uh but this is not a broadcast channel right?

>> I'm just saying that like >> Yeah, you can do VSSs uh with statistical security assuming a broadcast channel, right? This is like >> Yeah. >> 1980. >> Yes. Yes. Yes. But uh that's the reason the difference between broadcast channel and uh when it is not broadcast channel will become clear there. So indeed with broadcast channel uh with statistical or as well as unconditional hiding or computational binding using commitment pattern commitment we can achieve MPC for 2T + 1 uh but I guess that's where the interesting distinction come in picture. So I'll give more example to make it clear. Yeah but yeah there's a uh you are right there. So uh yeah in this paper we actually just to summarize so the weakening of the primitive from the broadcast channel the SMR flips the

security from statistical the the hiding property from >> is that right? >> Yeah. So uh also statistical is one angle. So to be say more precisely it's like unconditional hiding become impossible. >> That's that's your conjecture. Yeah. >> Yeah. So in here that what used to be unconditional is now just computational. >> Completely computational because I have to exclusively use encryptions also. Yeah. Okay. So uh yeah just to just to be uh clear I guess as we see VSSs or DK uh MPC in general with broadcast channel we can do 51% on even statistical we can go there. Uh on other hand if we are in asynchronous VSSs again 67% required. uh but if you want to do RBC or SMR

resisted VSSs we can achieve it but unconditional uh unconditional hiding uh doesn't seem achievable okay I was I don't want it unless I write proof who am I to just claim it but uh I think I should have something just it's work in progress but uh uh I mean I found out a nice result how to relate that to where I even go beyond uh uh baantine fail if I just have this crash fail top plus semi-honest I can see a result and pro possibly some impossibilities for OT can be related to that but it's still work in progress so I do not want to just uh claim something uh before okay now I start building on top of that and let me spend uh very

quickly so I want to now do DKG or distributed key generation so uh if you haven't seen that uh distributed key generations means now no uh we want to have a secret sharing of a secret that nobody knows Okay. Uh that secret nobody knows but everybody has a share. uh the only really good way to we we know how to do that is uh run multiple verifiable secret sharing and combine those sharings is a very approach we and I want to really say that uh when we that's reason proving impossibilities and other is very difficult for DKG because maybe there is some very awesome way where we don't need to go by a VSSs route but still that's approach that we

know and now here this a this problem required consensus solving And that's the reason I no longer has S uh RBC present over here. Here I'll assume that okay everybody just generate those D VSSs vectors and publish them onto the chain. Okay. Again u as long as I have input from one honest party to the system uh that is sufficient and uh we have a uh ordering property that blockchain gives me. So because of that I can collect any f plus first f plus one of the input it will contain one honest input and that is sufficient for me to just generate dk in all the parties will also pick the exact same f plus one so the problem is solved in

that space okay so again just everybody send the pvs vector you collect them and uh we achieve the dkg here >> so sorry so so for DKG you're saying you think you must use an or so broadcast is not enough >> uh I'm not using anywhere broadcast RBC is not enough because you have to overcome the FLP somewhere right you have to solve the agreement >> agreement it's agreement I see it's it's an agreement problem got it got it >> yeah so uh you have so just to complete the thought that uh indeed for DKG along with solving uh broadcast we will also record access access to uh ACS or coin somewhere yeah uh that reminded me there is a very nice result by uh from a

damstra team like if you consider from distributed computing per what are the necessary primitive for over and the interesting thing be if you have consistent broadcast and coins then you can build everything else but coin can allow you to overcome the consensus uh or FLP and consistent broadcast and they can be allow you to solve the problem in general but here uh just to solve the uh uh overcome the FLP for consensus we use SMR and not broadcast >> I see but you could you broadcast in a weak point that would be okay yeah that's certainly possible but again my the the theme is is that this must have solved this problem for me so why shall I solve it yeah that's a way to see >> and also one more thing will happen that

solving the weak coin itself will probably still require 3F plus1 >> nobody but I guess my point is if you get a blackbox RBC >> and a blackbox coin >> you can build everything right that's kind okay it's like uh those things need 3F plus one both of them >> um but if you kind of abstract them away and say I get them for free then everything else is 2F plus1 >> yeah in in asynchrony which is kind of nice. >> So uh just to mention again uh yes but if you look at the BA problem the original BA problem unless I make uh this range assumption even if you give access to broadcast B broadcast uh free broadcast and coin BA with no no assumption on honest inputs will be still 3F plus one that will be quite

interesting. I I was surprised but yeah uh >> why binary agreement >> uh uh no no uh the with the minmax validity the problem I mentioned in the beginning okay so let's say convex convex agreement maybe can be simplest uh thing if I if I give access to coin and RBC >> oh it's that's a validity problem okay I can >> yeah you're right >> it just to indeed it's happening because of this stronger validity that we need. Yeah.

Okay. So, uh moving on I guess. Yeah. So, uh basically same thing for the distributed key generation. Uh we can solve the problem. Uh we have a a very interesting result again here. If you look at the complexity, it will be n square data going to blockchain. Too bad, right? For our blockchain. So, we have a result how to build such a system only for 2T + 1. But uh the data that goes to blockchain is only O of N. O of N is necessary because we want to have uh all the individual public key shares for parties to be present on blockchain.

But basic scheme require O of N square. Uh it is possible to reduce that to O of N by adding more rounds in between purely asynchronous but it is possible. Okay. Uh happy to discuss in one-on-one conversation that's relevant. Okay. So uh yeah but we don't need to stop there right we looked at if once we got DKG then we can use threshold BLS signatures or unique signature and achieve random function so that can be built there but when we go for threshold ECDSA or some other signature we require MPC in general uh then we need to solve the MPC problem now and this is this is this in fact find uh where I think there are lot of interesting things that could be possible right so so far I only know one solution uh how that can be achieved So

it's a very famous paper called CDN multi-party computation in Eurocrypt 2001 where they use uh threshold linearly homophic encryption uh set up like algamal encryption or pal encryption or class group encryption something using that we know how to do MPC and that approach again very uh that approach can allow us to solve the problem okay so uh I'll not go through the cryptography screen completely it's here uh but it's a it's not that difficult scheme scheme and I'll be uh you'll find out that once we look at the slides or we can discuss that later. But the key thing why does this scheme work is that uh many times in pro uh in the systems uh which are based on broadcast

channel we use this assumption that if you don't tell me anything you are bad party or if you don't say anything then you must be happy and this protocol is one such example where original scheme was define assume broadcast channel but it doesn't make those assumption and because of that we can solve the problem only with honest majority uh I do not know still like is Is there a scheme based in more like OT space uh obvious transfer space or something where something like that happen and I find that to be quite interesting >> as you said this one property of this thing is that it's computationally hiding >> and so that that may give you a hint why this is the only in some sense >> no but there could be more schemes where we could have something like just if we have we use OT or garble circuit

>> circuit is completely hiding >> yeah garble circuit is just uh encryptions right so in that sense I can >> okay but if you're doing uh guarantee output delivery then you have to secret share that thing and then it becomes not yeah >> yeah yeah so but but I'm saying that uh this scheme uh it's computationally expensive that's the reason I don't like it uh that's reason it's a very interesting thing can we build uh MPC for use on blockchain with blockchain uh maybe it will require some encryption so public key component but maybe interesting uh thing could be possible to look into that >> okay so we can take it offline but like this the advantage of this thing is Actually it's very uh yosso friendly so it's good for like subsampling committees.

>> Yes. Yeah. >> So uh that might be a good combination. >> Okay. One of the crypto people in Yoso did work on this scheme only topics. Indeed. Indeed. That's that's certainly advantage. Okay. Uh because you bring the yoso into discussion right. So the interesting comparison. So this this is in a way weaker and stronger than old yosu framework because >> you should give a little context there of what you're talking about when you say yoso. What do you mean? >> Okay. Yeah. So you also for those who know you only speak one it's a very uh interesting framework that got built into the cryptographic literature where they assume that we work in a system where every party just sending their messages once and then they disappear and but they uh original USO assume that

you have access to a broadcast channel. So uh you have a really good network but uh really uh weak assumption or uh your parties can just crash or can become malicious really fast. that's the world they work in and such a world uh then how to do MPC in general is the problem uh there and uh indeed such schemes can be useful uh there uh it the setting uh comparing now that with the setting that I'm talking about here my net parties are not changing I'm just working with the same set of parties and uh on other hand my all the links are asynchronous okay there is a recent paper where they go for asynchronous here so it will be

interesting I haven't studied read that into detail but I am aware of them being present. Yeah. Okay. So, uh in general I think I already made it clear but let me just spend couple of times. So if you want to solve all these secret sharing problem again we can solve with only 51% adversary. Uh assuming we have access to SMR channel. Uh we the key idea is we use encryptions. Then I added but now I know that encryption is a core primitive there not uh so much other things. If you're on unconditional hiding, we have to go to 67% in general which is very interesting. Okay. And uh there there interesting uh things that can be proven in this particular environment and uh some of them there are good intuition that are built but I guess uh again it

will be still interesting to really concretize that or prove that something is wrong. That will be quite interesting as well but I find it difficult in general. All right. So what are the takeaway for my talk? I know I'm slightly already running ahead of time but so the thing is if you want to build secure distributed computing protocols for blockchain with blockchain we don't need to solve the consensus problem twice let's just leave that to the blockchain why it's a nice way because blockchain is going to solve it whether we solve whether we solve it outside or not right so I can build a complete my protocol asynchronously but I'm submitting on a blockchain which is making synchrony assumption then kind of I'm uh my efforts are wasted I could have solved the more efficiently and uh although my my protocol which is sol

which uses blockchain as Oracle access is not taking advantage of what blockchains can provide me right so that's the key theme in here uh we looked at the uh the blockchain oracle problem and we say that indeed can be solved completely asynchronously and possibly with better fall tolerance for valid when the uh for making a weakness with the validity in general and then we looked at the so the threshold cryptography in MPC for blockchain and how can we solve this problem again completely asynchronously but with a with better fault tolerance if when we are up for computation hiding but proving otherwise will be quite interesting so uh that's it I guess I come uh come to the end of my talk and thanks a lot for fascinating questions

>> can I model this uh Oracle access to an SMR channel by simply I have a trusted party we all have asynchronous links to that trusted party party >> it can perform any computation at once for us but I may not hear back from that party due to asynchrony like would that be an equivalent model? >> Yeah, I should confirm that because uh trusted party can simplify something. So that's the reason >> I see your point. Yeah, it's not like >> but uh maybe but I'll think more about it because I know some setting where uh if we have semi-honest parties uh I was able to achieve more uh at least for MPC.

Uh >> so but that trusted party doesn't know our inputs or anything. Say like we also care about privacy from that trusted party or some >> something. Yeah. I don't know >> possibly. Uh >> I'm trying to like clean away the blockchain part of it like I want to like a clean theoretical model for what's going on here. Yeah. Yeah. >> So then uh I mean in that case we can just take the trusted party who does only two thing. it will eventually add something to the block and it is partial uh it's going to order that uh then it is equivalent but moment that trusted party can do little bit more uh maybe maybe it might be able to solve something that otherwise can't be solved.

Yeah. Because uh just to give uh concrete example for that there is a very interesting model where if this trusted party uh can be semi-honest but it will never collude with the users then we are able to solve MPC even for dishonest majority purely asynchronously. So it do become bit weird uh once you do that. Thanks. Thank you.