MiniCast: Minimizing the communication complexity of reliable broadcast with Victor Shoup

Transcript

welcome everyone to today's a16z crypto research seminar very happy to introduce Victor shup professor ameritus at NYU uh and these days also um working at offchain Labs um Victor's well known for lots of different results in cryptography over many years but he's actually been working uh suon consensus lately and that's what he's going to tell us about today so Victor thanks for the introduction thanks for inviting me to hang out here for a couple of days so um yesterday uh chrisan gave a nice overview of a lot of consensus problems kind of flying above the mountaintops I'm going to be like working out in the backyard in the tool shed on some little tiny things uh and show you around uh some things I've been looking at lately so um I'm going to be talking about reliable

broadcast uh just quick survey how many people here know bra's broadcast so pry oh okay so uh it's this will be a self-contained talk uh but I'll maybe go a little bit faster through some of the brocka broadcast stuff so so reliable broadcast is kind of a very special case of consensus um and it's used in consensus protocols such as uh the dag based consensus protocols it's a it's a component there as well as others and I'll talk more about that later so what's the problem so we have n parties uh P1 through PN they're connected by I'll just assume authenticated channels I won't really be using any other cryptography today and so they're connected by point-to-point

channels and communication is asynchronous so there's no notion of time there's no upper bound on how long it will take messages to be delivered from one party to another and really we'll be assuming here that the adversary totally controls the network when a message is delivered uh and even if it's ever delivered um but he can't alter the contents of the messages that's where the authentication comes in in this setting the best so we have some number of uh corrupt parties at most T can be corrupt and we'll assume that's strictly less than n over3 um and that's the best you can uh hope to do in this space uh one of the parties is going to be a designated sender so we're just going to be looking at one run of the protocol where there's

one designated sender he's trying to send a message to P1 through PN right so if the sender was a good honest party he could just send his message to everybody and we would be done but at the sender is corrupt he might choose to send uh one message to some parties another message to other parties and maybe not send any message at all to some other parties so we want to kind of force a corrupt sender to uh send the same message to everybody and uh of course a corrupt sender could just be sleeping the whole time and do absolutely nothing so in which case we have to be a little bit careful how we Define things right so maybe no message gets delivered to anybody but if any message does get

delivered to some parties then all parties should get the same message so there's a correctness property that says that all honest parties that output a message should output the same message and if s is honest that message should be the one that s wanted to send and not some other message and then there's kind of a liveness or completeness property uh which says the following if on the one hand if the sender is maybe corrupt but if any honest party ends up outputting a message or if the sender is honest and actually runs the protocol then eventually all honest parties output a message that's the completeness property and eventually is a technical term there's no notion of time so what

one way to think about it and I have arguments with chrisan knows very well I have arguments with people not with chrisan but we've had arguments with various people about how you define any of this stuff um in all of these protocols there's going to be like a finite number of messages that are ever transmitted and uh ually just means that if there's no other messages that have been protocol messages that have not yet been delivered then at that point in time uh all honest parties should have output a message if that's what they were supposed to do um so that's what eventually means this is your lecture on braa broadcast if you've never had one before I told you I'm going to be working out in the tool shed looking at little wrenches and and whatnot so we'll start with braa a classic protocol so uh

I I'll kind of go through some details because they they kind of matter so um so here's my sender he's going to send um a message to all parties so he disperse his message so this is what he supposed to do right now every party I guess including the sender is also involved here is acting as a receiver so here's the logic for the receiver um they're just going to go through a a loop forever waiting for different conditions to happen so the first condition that will trigger uh some action will be well if that party uh receives this dis first message that the sender sent up here right and if he hasn't done if he hasn't done anything before so this variable is still false um then he's going to well he's going to

remember that he's gone through this step before and then he's going to Echo what he received to all other parties so the sender sends a message to each party each party then Echoes it to every other party and and they're only going to Echo a message once never more than once okay then so that's step one step two is if I as a party receive uh the same Echo message from n minus t distinct parties I'm going to vote for that message and by and sometimes this is called a ready message but here I'm calling it a vote so I'm going to record that I voted and then I'm going to set I'm going to Echo the message all over again to all the other parties uh this

time labeled as a vote and that's what I do so that's actually there's two ways that you that we're going to vote for a message here one way is if I I see like n minus t uh Echoes of the message I'm going to vote for it now why the N minus t for those in this don't work in this asynchronous space it's kind of like there might be T crashed parties right so and there are n parties altogether so I can't afford to wait for more than n minus t party so in these protocols you see all the time wait for wait for n minus t of this wait for n minus t of that so um that's why you see those so there's two different ways that you can vote for a message in braa one is you saw a whole lot of Echoes the other one

is that you didn't see them but you're going to jump on the bandwagon anyway because you saw t+1 parties voting for that message and and this is a a nice uh little device that ensures that um that ensures the completeness property really that's why it's there then finally if you receive n minus t distinct vote messages you're going to deliver this as your output so that's the whole protocol question comment the last n minus t could be two 2 plus one uh I haven't thought yeah yeah yeah or it could be this crazy thing with lots of floors and ceilings in it that you tend to write in your paper that I I don't do that you don't do that anymore no I never do you did I your papers you had I have bigger

than n plus T over two n plus T yeah with a ceiling or a floor or something no strictly bigger than n plus t two gets rid of the ceilings in the floors I don't have to separate you guys okay so so if I had a a little bit longer to talk I would like walk through all these I want to I want to like walk through very quickly like how you would analyze this thing and I want to just focus in on one property um and then I'll think I'll skip over the rest so let's call this the many Echoes property so if some honest party ever votes for a message n then some honest party must have received at least n minus t Echoes of M but remember you can vote in two different ways jumping on the bandwagon or so if you so if if you voted because

you saw n minus t Echoes then yes we're done right but so otherwise you argue that well the first party who voted for M must have not been jumping on the bandwagon because one of those t+1 honest part parties must have been honest and so there must have been some point in time where some honest party voted by seeing many Echoes and so that's what guarantees the many Echoes property and then from there so so that's one uh property then from there you can argue unique votes so no two honest parties ever vote for different messages and here you just wave the magic wand of Quorum intersection to say well you can't have like many Echoes for two different uh messages so um and then and then there's the other then there's

the completeness properties which I think I'll kind of skip over not to go too deep into the weeds here there's a completeness property which is and then there's validity property which says that if the sender is honest then then eventually all parties will will output the sender's message so that's that okay so let's talk about um message and communication complexity so let's define terms the message complexity is just the total number of messages sent from all honest parties to any party you add them all up and uh you can see for brcka there's N squared messages everybody sends a message to everybody so there's N squared messages okay that's fine communication complexity so the typical way you Define communication

complexity is you look at each party and ask how many bits did they transmit to all other parties and then you sum that up over all honest parties and that will give you the communication complexity but I'll come back to talking about like what's the right way to Define communication complexity a little later so for braa you can see that everybody Echoes the message to everybody else so it's n s times the message length so that's pretty easy to see can we do better yes so Christian looked at this problem and noticed that uh we can use eraser codes which I'll be talking about a little bit later to get the uh communication complexity down to message SI Big O of message size times number of parties plus some here that doesn't

depend on the message size and this is optimal in some sense uh in the sense that well you know the message has to be delivered to everybody so if you look at like download message complexity every honest party is going to have to download the message from somewhere so those bits must have come from somewhere so the overall message complexity is going to have to be n times the the message size uh just to get the message out to everybody so that was um uh so that's so that's a nice result uh and then there have been some improvements oh by the way so here Lambda in this expression is going to be the uh hash output length uh of some hash function so 256 bits and there's

this log end term here which comes from uh Merkel trees uh which I guess everybody knows about Merkel trees I was told that that's a safe a safe bet okay so that was back in 2005 some nice progress uh and then also sitting in the audience here is surov who's did some more work on this and he focused in on this term here and said do we really need this login term and he said no we don't so we got rid of this login term which for so you can say when when is this important it's important in applications where uh m is around the same size as n uh so in that regime this gives you an improvement Abraham and

asherov also looked at this problem and noticed that well it's the same result but what's different is this is statistical security so this Lambda here is for serov's result is again the output of a hash function output length of a hash function here I'm I'm kind of paraphrasing Abraham and asherov a little bit uh I think this Lambda is is just a statistical security parameter um they have there's different ways of stating the result but I think this is a fair way of stating it so they they don't need any cryptography I said we don't need cryptography besides authenticated channels but here I just snuck in a hash function uh here they get rid of any cryptography again uh if if that's what you want to do in this

work I'm going to be thinking about what is this uh bigo constant here on the M * n term because if I have like really huge messages like many megabytes and my network is smallish say a few dozen up to a 100ish nodes in the network I mean the only thing that's going to matter is in terms of communication complexity is the const is this is this term here so not not to be critical but I mean this you know worrying about this term is important in some applications but not in others so in the application where this message might be very big and certainly like in certain blockchain projects where you know you've got several megabytes of transactions being

disseminated by a a leader uh these types of techniques uh for for getting uh like at my last G definity I try to convince them to Implement some of this stuff and and they were complaining about this this factor of three that you get off the bat just by using eraser codes so if you look at all of these works if you look into the constructions you're going to get a cost of at least three times the message size times the network size plus some lower order terms for the rest of this talk I'm going to just be talking about how to lower this constant so hopefully you'll find that entertaining and interesting but that's all I'm going to be doing so I said I was going to be messing around in my my my tool shed in the backyard here so

that's all I'm going to do so my colleague Thomas loer at who's still at definity raised this question which is interesting because I I I I I I mentioned this problem to somebody else recently and they they assumed that this three was just like some some Universal constant that nobody had ever even thought of like like is this the right like yeah so so Tomas got a result and got the three down to a two and then we joined forces and we got it down to 1.5 okay so yeah so it's a pretty modest uh goal here so that's what I'm going to talk about but if you haven't seen like how these eraser codes work and everything hopefully you'll you might learn something useful so let's talk about the

ratio codes is there any lower bound bigger than one um well no we so so that's like one of the open questions is to get a lower bound on this so we think the lower bound is 1.5 and Tomas has a result but in a very limited model so it's not really sat it's it's it's puts too many constraints on the protocol uh so so under some not very realistic constraints you can prove a 1.5 lower bound and we kind of feel in our bones that's the answer but I it's a nice problem so that's actually if I can get any of you to work on this and solve it that would be really cool um so let's talk about eraser codes um they're nice to know about anyway so I'll walk through the whole kind of how you how

you do all of this and then how you get the improvements so we're going to start out with the 3x uh results um so what is an eraser code so if I have a this this is an N minus 2T out of n eratio code means that I'm going to take my message M and code it as a vector of n fragments and the property is that the second parameter here is the kind of the the Reconstruction threshold so any in this case any n minus 2T fragments can be combined to to reconstruct M right and you can do this using readed Solomon which is just a fancy name for uh polinomial interpolation right so um so this can all be done how big are is each fragment well you're you know you're

basically taking the message size and dividing it by the Reconstruction threshold that'll be like the degree of your polinomial so just taking your message and chopping it up into coefficients of a polinomial and this is basically how many coefficients you have and so this will be I'm assuming here that t is say around n over3 so in this case um uh fragments will be of size you know m / by n times this factor of three which is where the whole three comes from in this business so the idea now we can kind of Bolt this idea onto braa very easily and there's a number of different ways of doing this I'll show you one that's anyway kind of interesting so the idea is this so the sender s starts by encoding M as this Vector of fragments and then he builds a

Merkel tree uh whose leaves are the fragments and let's say R is the root we're going to run braa basically with with the root in place of the message so the root is nice and small so we can do this but we do but we make a few adjustments so here are the adjustments we make in the the first flow of the protocol is this disperse phase but in so we're going to disperse the root of the Merkel tree but we're also going to the sender is also going to um send to each party Pi his fragment fi along with uh the Merkel proof or the path to so he can validate that this is really the opening of this Vector commitment at the E position right so he's GNA so he's going to like uh piggyback uh uh these

fragments in the first flow of braa each Pi is going to Echo in in the Echo he's going to Echo the root of the Merkel tree and he's also going to Echo his fragment along with its its uh proof well he's only going to do this if if the Merkel proof is consistent with the the root that he received as a part of the disperse the votes are going to work the same way as before at the last stage where we output right we're going to collect n minus t votes and then output a message so what we're going to do is the following so if I so if each party is going to when it receives the the N minus t votes what is a party going to do the first thing they're going to do is wait for n minus 2T fragments that

match the Merkel route why is this going to work well remember by the many Echo property if anybody well if we've gotten to this stage like somebody has voted for this for this Merkel route right which means that there were n minus there there were um some party received n minus t uh Echo among them there must have been n minus 2T Echoes that actually came from honest parties and what are those honest parties going to do they're also going to be echoing their fragments so there's got to be so so if I get to this stage where I've received n minus t votes for sure the N minus 2T honest parties have echoed uh fragments that that are consistent with

the the Merkel tree so I so I can afford to wait for them I'm guaranteed that they will arrive eventually I have a question yes so here it seems the broadcaster is sending the fragments once and then parties are sending it back again so no matter how efficient coding we use let's say we have a coding scheme somehow which is doesn't do any blow up then we're anyway sending the message twice right first the broadcaster is sending once okay let me come back to that okay okay I'll come back to that in the next slide um so now so I've gotten my n minus 2T fragments and they're consistent with the merco root I'm going to run the decoding algorithm to get some message let's call it m Prime I'm

going to re-encode M Prime into fragments all over again so so I can compute all the fragments associated with M Prime and then I'm going to recompute a Merkel tree with all of these fragments and I'm going to test if what I get is consistent with uh the the the Merkel rout that was was output here because why am I doing this so why why is this done what this is done is really I'll I came up with a very fancy name for this because it doesn't seem to have a name I'll call this this is kind of a postf facto guard against inconsistent fragments so why am I calling this that all through this protocol nobody has done any consistency checking whatsoever to make sure when they receive an echo a fragment who knows if this is really a fragment of some readed Solomon code

word it may or may not be it's just some thing I got and I'm echoing it right who's to say if if the sender is corrupt he might actually just you know uh commit to a vector of random strings that are not that don't that don't for a that don't form a code word and so what are you supposed to do when that happens right uh well what you do is you just treat the sender at this point in the protocol you'll detect that he did that and you will basically treat his message as being garbage and ignore it and the nice property is that if you choose to do that so will everybody else so either all parties will see that this this Vector that was committed to was actually a commitment to a code word or it wasn't and we're all we'll all agree

on that whether it was or it wasn't uh so so so um um this so this wasn't in your original paper I don't think this this kind of postao guard there there somebody must have verified something nevertheless you verified something somewhere along the line but in fact you verif there were extra so it wasn't so this particular way of doing things is a little bit simpler and and has has fewer rounds and and a little bit constant lower complexity um and this idea of kind of this postf facto guard I mean such a I think it's a cute idea but and and it's appeared like I've seen it in like three different papers one's sod's BC which I don't know too much about and then there's this Dumbo mvba paper and disperse Ledger this is the

first place I ran across it was this disperse Ledger but after the fact I noticed that actually it appears in a couple of different places it's kind of a nice little trick it's not like you know going to change the world but it's it's a nice trick to know about because there are applications where um you need more maybe you need to like send out fragments along with proofs that these fragments really do uh are consistent with a code word right so but but for this particular application you don't need that at all it's perfectly okay if you just like detect that these were bogus fragments like at the end you don't have to like go out of your way to do any extra checking which is nice because then it lets us use kind of whatever uh efficient um uh eraser coding scheme we want we don't need an

eraser coding scheme we don't need to use kzg commitments we don't need to do anything fancy just any any Vector commitment and any eraser code will do so is this practical well so now I'm going to answer s's question about communication complexity what is it so each party is going to Echo well he's going to so when he does the echoing there's going to be n fragments sent to each party right this is what each party does right he's going to send n fragments out over the network each of these are of this size so it's going to be three times the message length that's what each receiver does during the echo the sender is going to transmit also an additional uh 3M bits so if we're measuring communication complexity is

just the sum of all bits transmitted this this just adds in once right the center just does this once every other party does this this many times so you get n times this plus one of these so it's kind of balanced even though the sender is like sending twice as many bits as everybody else so it's kind of annoying there's another trick which um I haven't seen it before but I've used it in a couple of places which is kind of nice what you can do is instead of using an N an N minus 2T out of n code you can just chop just subtract one from the both parameters and so basically there's going to be n minus one fragments instead of n the sender is going to transmit to all the other n minus one

parties their fragments out of this uh code and then he's just going to stop and then his his his his role is over he's not going to Echo anything he's not going to do anything so he's he's transmitted once and and and and and Rec and reconstructing the the message out of these fragments is a job for the other n minus one parties you get for small n you get slightly less optimal overall communication complexity but for a large end there's no real difference and and then you get perfect balance every party is echoing yeah Ahad many people want to treat the sender as an outside client you can do that too yeah then then uh then I guess matters then you still end then then it's still yeah yeah which is fine okay um yeah and the applications I have in mind like for

Atomic broad leader-based Atomic broadcast protocols the sender will typically be one one of the end parties transaction come from the client no transactions come from the client but blocks come from the leader so okay so let me go through an example because sometimes I think that people think of these eraser codes as some exotic expensive Beast that you would never use in practice right and I wondered that myself so so I was wondering like is this is this all just you know kind of Science Fiction that you would never Implement so so I did some micro benchmarking I didn't like Implement a real system or anything like that um but okay so here's my example I had I set n equal to 100 and t equal 33 and a message size of 4 megabytes so uh

something reasonably big for purposes of putting this all together in a minute I'll I'll assume a one gab bit per second now Network so that's the upload and download speed onto the network so these were all done with my MacBook down here there's a a nice library on GitHub uh which is a it's an eraser coding Library written in Rust you have to look through the document this it's it's a nice culmination of a lot of theory and practice so there are some papers written over the last 10 years that really kind of push the envelope on terms of the theory of eraser coding a little bit I mean it's still you know all polinomial ation and whatnot but they have special tricks special types of ffts over special domains um but all

of this was just like on paper and then thanks to you know the beauty of uh of of GitHub and and and and this kind of sharing free there's been several iterations of libraries people have taken like a first implementation and then written a second implementation this one this one is U well it's simd so it's it's written carefully to exploit uh AVX instructions on a x86 machine and the neon instruction on on on my MacBook and it's it's it's really impressive so um so the time to encode a 4 megabyte block using these parameters is like three milliseconds uh time to decode a little bit more uh 13 milliseconds pretty good

but let's but these numbers only mean something in relation to other numbers like like is this expensive well I don't know is it expensive relative to the cost of transmitting and downloading the data my answer is no not not at all right so uh there's also a lot of hashing going on here we have to do all this uh hashing for the uh for the Merkel trees time to hash everything you need is for both sender and receiver is going to be uh six milliseconds again just using my laptop here and then uh let's look at data transmission time so here I'm assuming this kind of like pretty conservative 1 gabit per second Network so the time for a party to transmit uh 12 megabytes right it's three times the message size right my message size here is 4 megabytes

everything gets blown up by this factor of three so if I did my arithmetic correctly this turns into 96 millisecond so you can see that you know the the time you spend doing all this hashing and coding and decoding is not very much compared to the time you spend just uploading and downloading data off the network so it's it's faster than the network so it's fine there there's no reason not to do any of this here's where I get a little bit maybe controversial like how would you do this otherwise like I I know projects that are out there they don't use any of this eraser coding stuff they don't they just send it all out like this is what we did at definity when I was there you've got a you've got a a block proposer who's just going to send the same four

megabyte block to everybody I'm not an I'm I'm a theoretical computer scientist I guess but I know enough and I've talked to enough people to figure out there is no magic way to do this really on a standard you know internet setup you're just going to literally send the same message to everybody a 100 times and there's no like magic to avoid that there are alternatives so but if you do this right just over point-to-point networks you open 100 TSL connections and you send the same damn thing 100 times right uh and it's going to take you you know over three seconds to do that just to upload the data onto your network so so yeah it's already you know a win uh let me just say one more thing before I take a question on this controversial Point uh which is um you could do other things like uh Gossip

protocols and whatnot which um those those create other problems though I mean first of all it's the the latency is going to be quite a bit higher because it has to go through several rounds to reach everybody and then you also have security issues like how many people are you gossiping to and what's the probability of hitting corrupt only corrupt corrupt subset of parties when you when you gossip so question did that include proving time and you didn't proving there's no proofs hashing there's only hashing just Merkel proofs just Merkel yeah yeah thought said there was also some proof that you'd encoded the file correctly no no those were just Merkel proofs it's all oral proofs huh it's all morle proofs and I went out of my way to say that if you weren't paying attention young man I went out of my way

to say that we don't need any proofs of consistency other than just a postao Merkle proof check at the end as opposed to doing like kzg commitments and doing and doing uh you know some kind of uh proof that I've evaluated a polinomial at a point or something right that's that's kind of the dunk sharding uh Vision right which is using these kind of proofs of yeah yeah that's what that's why I wanted to like shake you up a little bit and so you don't for some applications you just don't need anything like that which opens up a lot of opportunities because then you can use you know read Solomon simd codes instead of some some super slow uh kzg type stuff um yeah question uh another comment to the compar the last item

there the three seconds right mhm our predecessors Castro and Lov they used the hardware multicast IP multicast UDP for for for this stuff but nobody really uses this right absolutely not so yeah or you're on a land or something I guess because because they thought it's too yeah and this was restricted to a obviously yeah so anyway so that's so right so I haven't gotten any new results yet I just uh giving you the the background uh yeah first step so actually so I'm going to so Tomas had his paper where we reduce three to two I'll show you that and then I'll show you how to reduce two to 1.5 it's just kind of fun and it's it's all simple I hope you

think like this is really simple I had a feeling giving this talk that you all just kind of laugh at me because it's all just kind of simple so here's loker's idea and again I think I think the most interesting thing here is just asking the question the answers are not that difficult but the fact that nobody even asked this question is kind of weird um so why are we using n minus two why why we have a reconstruction threshold of n minus 2T so roughly n over three why why not use n minus t we have n minus t onest parties you would think that we could somehow use all of them right so we're not really using them cuz if you use so if you do this then you need you know n minus t fragments to recover M so you need more

fragments so it's harder to make sure that you really get them all but if you can do that then the nice thing is the fragments are half the size as they were before one and a half instead of three so how do you actually do this well here's tomas's idea for getting this down to two I'm going to present it in a simplified way that has a bit more the number of rounds is is a bit too high uh but it's easier to convey the basic idea um it's one or two extra rounds of communication here so to simplify things we're just going to like as before the center is going to form a Merkel tree with the roots with the leaves being fragments but now with a code with these parameters and then we're just going to in the simplified version of the

protocol we're just going to reliably broadcast the root of the Merkel tree and then only when we've finished that we'll proceed to The Next Step we're also going to disseminate the fragments to each piece I but but each party is going to because we're trying to be a little bit stingy on communication complexity each Pi is just going to hold that in his pocket until this this braa broadcast is finished and we're sure that we we all agree on what the root of this Merkel tree is because I could get a fragment associated with a different Merkel tree and if I broadcast that I just kind of wasted some bandwidth uh so I'm going to be careful uh not to not to broadcast my my my fragment until I know I've got a fragment associated with the the right Merkel tree so then only after

I deliver I know what R is and I deliver it then I Echo it if it matches right if it's if it's consistent with that now when P receives valid so now again p is going to each party is going to receive valid fragments of n minus t parties is going to go do the same thing as before so now I'm going to carefully name these parties right so I've I've got a set of n minus t parties let's call them you know P subj for some subset J of parties as before Pi is going to reconstruct m in all the fragments and and apply the the my postao consistency guard he's going to Output M but just but now he's going to help his comrades out he's computed all the fragments right for everybody uh he received n minus t but

now he's got n fragments and he's going to carefully just send his fragments back to the parties from whom he didn't receive a fragment that's the whole idea for this thing there's more so I won't disappoint you there's more a party who received kind of this backup fragment he what he might have not received anything from the sender or he might have received a fragment for like the wrong rout if the sender was sending out was equivocating on the on the Merkel tree route so he's going to wait around and then finally if he gets either a fragment from the sender that's the right one or a backup fragment from one of his colleagues then he will Echo this this this this thing so this guarantees that all honest parties will eventually Echo their fragment remember we for completeness we

want it to be the case that if any party outputs the message than all parties do so I've received n minus fragments and output the message but there's no guarantee that anybody else is going to receive these n minus t uh uh fragments unless I help them out so I'm going to make sure that all the honest so if I output something I'll make sure that all honest parties eventually get their fragment which they can then echo which will make sure that all n minus t honest parties are eventually echoing their fragment and so every honest party will eventually collect n minus t fragments and eventually output M um um so that's my argument here all honest parties eventually Echo their fragment so all honest parties out with M what are the bits sent for each receiver well in the Echo everybody sends one fragment to to

n parties so this is the size of a fragment sending it to n parties as part of the echo so that's uh 1 and A2 time M for the backups you see we're cleverly only sending uh backups to 1/3 of the parties basically because only to parties from which we didn't receive a fragment in the first place so when you add it all up you get 2 m yes The Wonder of grade school arithmetic yes so that's that's that um but that's clearly not the end of the story this is too simple so we have to do something more complicated to get to 1.5 you see there's a lot of waste here obviously there's there's room for improvement because I'm sending my backup to everybody I'm sending a I'm sending backups to a lot of parties and in fact

if I'm missing my if I don't have a fragment to Echo I'm receiving backups from many parties right so there's a lot of wasted there there's a lot of repeated stuff being echoed around so can we be more uh stingy on on what we send around so here's how we go from two to 1.5 again a bit simplified we're going to again use uh the same eraser code with the same with the same parameters each fragment will have size now I'm going to be a little bit careful here so each fragment will have size three halfes m/n and uh in this part of the presentation you might start to worry about what happens when m is not really big uh so there's always a no matter how big or small m is you can be

sure that the if you use say just a standard read Solomon code of some time the it's going to be this plus some login term is going to be the the size um then we're going to use another eraser code with parameters that we used for the naive braa to encode fragments into mini fragments so each mini fragment then you just divide every you divide by n and multiply by three you get the size of a fragment and we still have this log n term so you might complain well this is all going to be meaningless if m is not very big and that's true but but anyway it's all going to be absorbed into the into the N squ login term that we're not anyway worried about anyway so in practice you

would probably want to not use the scheme except for a very large M but but I'll show you an example it's not that bad either in practice so at a high level we're going to use braa just like before to broadcast the root of a Merkel tree now it's actually a two level Merkel tree I won't go into all the details on here but we're basically taking a message encoding the fragments I can draw a little picture here I encode it into n fragments and then each of these fragments is going to be encoded into a mini fragment and now that's my twole and then these guys here are going to be the leaves of a of a Merkel tree and I'm going to I'm going to pass around I'm going to Des seminate the root of this

Merkel tree here um I'm only going to send fragments to parties at least the the sender is going to send fragments uh so for parties to verify their fragment what they're going to have to do is encode the fragment into mini fragments and and then check that against this this Merkel tree so there's a little bit of extra hashing going on but it's it's all okay so here's like a simplified version of the whole protocol the sender is going to use braa to broadcast the root of our Merkel tree he's going to disseminate fragments proofs to each party then only after R is delivered each party is going to do the following he's going to okay after R is delivered each party is going to Echo its its fragment and and the proof of its fragment then as before he's going to

wait until he receives n minus t fragments from other parties now we just have to make sure that everybody else is going to get n minus t fragments as well be and I'm going to do a little bit of waiting here so Pi is going to reconstruct M and all the fragments and apply the consistency guard as usual then he's going to send a backup mini fragment so I've got all the fragments and I'm going to encode each fragment in the mini fragments and then I'm going to send to each other party the fragment it's the mini fragment it needs for me to get its fragment that it's hopefully waiting for so instead of sending a fragment back I'm just sending a mini

fragment which is where you cut down that that extra one half term um so if right so if if if I'm sending a a mini fragment to all parties then any party who is not holding a fragment can collect uh um n minus 2T um he'll be sure to um Again by the just by the many Echo property here um right if I if I receive fragments from these parties I know that then we're sure that n minus 2T parties are are sending backup min fragments each party PJ will Echo its fragment when it collects those mini fragments if it hasn't already okay and then so that's what these how these mini

fragments are used but notice I haven't like um actually output a message yet so before I do that I need a little bit of extra synchronization and in this case you can get by pretty cheaply just I've done all this stuff I've got my n minus t fragments I've reconstructed the message I've sent backup mini fragments and I'm not quite ready to Output the message yet I'm going to send a ready message to everybody and then I'm going to wait for n minus t ready messages uh from everybody else and only then do I output the message and what does that buy you now I've output my message so it better be the case that I can argue that everybody will eventually output their message right to to maintain completeness so if I get to

this point where I've received n minus t ready messages that means that out of these n minus 2T honest parties have done the same thing they've reconstructed M and send backup fragments to everybody right so that means um that means that all honest parties will eventually receive these n minus 2T mini fragments if they need them which will allow them to reconstruct their fragment and then Echo their fragment so all honest parties will eventually reconstruct M and also send their ready messages eventually all honest parties will output M all honest parties will eventually send ready messages so that makes n minus t so we're not going to get stuck yes so that's the whole thing bits sent per receiver so the same we have for the echoing we have the same as before and

then for the backups well these are all mini fragments now so they're like an order of magnitude smaller so it's really like not there it's a lower order term that we're not going to worry about the next I have up is uh some comments about a few things round complexity there's definitely like something extra there there's this there's this extra round of waiting to make sure that I don't stick my neck out too far uh ahead of other parties right there's this this step of um it seemed like a small thing but it's really there and it's hard to get rid of like I really have to make sure that not only have I gotten to this stage but n that n minus 2T honest parties have gotten to the same stage as me before I'm ready to

commit to delivering this message so why was it that came up here and not in the previous protocol um because um I was sending out whole fragments here I have to make sure that that there are n minus because I alone can fix it I alone am sending fragments to everybody who could possibly be missing a fragment um so I'm sure that everybody who needs a fragment will will get it here I'm not so sure because I'm only sending one piece of a fragment and I got to make sure that a bunch of other people are sending pieces of this fragment if you're careful about this so braa kind of in the optimistic path where the Senter is honest has three

rounds of communication here we get it four that's the best way you can figure out how to do you can get it down to three rounds on kind of an optimistic variant where you the the problem arises where if you have a where again the idea is you're going to send out your fragment before you really sure that it's safe to send it out because you haven't like uh agreed on the on the Merkel route yet if you do that you could have a you you the the communication complexity might be a little bit higher uh but that'll only happen because have a corrupt kind of equivocating sender um so that'll cause some extra communication at at the cost of a round in the worst case but you know he'll be caught I mean especially if you attach signatures to things you can implicate

the sender as a as a equivocating sender and maybe there are economic incentives to prevent that going back to my little example same parameters as before there's a lot more hashing and a lot more coding going on so you might worry that I I was worried that this is going to be like kind of silly so frag so in this setting with a 4 megabyte size and this many uh parties like each fragment is like 60 kilobytes many fragments are still like almost 2 kilobytes so not like too tiny to to to make it like impractical to be sending these all around for in terms of eraser en coding like you have to encode a message into fragments interesting so before this took three milliseconds it turns out for reasons I don't fully understand when you when you change the when you increase the Reconstruction threshold

but keep end the same it's actually faster to do the encoding and decoding I believe it they maybe using systematic code so if it's a systematic code then for sure yeah yeah and it is a systematic code so maybe okay it's not surprising okay so uh and then you have to encode the sender anyway is going to have to encode all the fragments in mini fragments uh that takes 3.9 milliseconds so all all in all you do spend a bit more time um time to decode the messages from fragments uh again uh the decoding is also faster this was using a I think a random set of fragments so I'm not cheating by using uh just a systematic code uh I I think even like I'm using all the

non uh all the the the par the parody check uh ones yeah I think there's a there's a switch you can set in this code uh and then you have to decode a frag then if you need to you don't always have to do this but if you're missing a fragment you'll have to decode fragments for Min fragments that's that's very quick hashing time also increases there's a lot more hashing because you have this Double Tree of yeah so's a lot of hashing it jumps up to 12 from 6 data transmission time obviously Falls in half and again there's like and with these numbers I worked out like exactly there there's these lower order terms but they're really like not there they're like within a few percentage a couple of percentage points of the of the astics uh at this thing open question is 1.5 optimal I don't know

like I said there's some partial results it would be really cool to see some some results I want to close with an application I've met I've kind of talked about this a little bit uh like some applications reliable broadcast you have everybody broadcasting all at once and then you gather together these broadcasts somehow and for these balanced communication isn't so important because everybody's working symmetrically right but for like if you take pbft what are some examples of this pbft hot stuff they all kind of conveniently actually just ignore the problem of how you actually disseminate these blocks they assume there's some some way to do it but they don't actually talk about how to do it uh but if you actually do try to do it it

becomes actually a bottleneck uh because every you have this leader who's trying to push out megabytes of stuff to 100 parties and his he gets he gets bottlenecked by his Network bandwidth this is a phenomenon that okay so is anybody here like a hot stuff cheerleader I don't know so I I get I get a little bit like freaked out sometimes by like how there's all these papers in the literature that are like hyperfocused on reducing the communication complexity from n squ to linear when that's not even like the bottleneck in the system the bottleneck in the system is disseminating these large blocks to everybody the rest of it just doesn't really matter unless you have like 10,000 nodes in your system or something like that and people have noticed this over the years there's a there's a nice uh paper uh honey badger

some of you have seen this they also do experiments and they say well here's hot stuff and here's our super slow honey badger that works in the asynchronous model and it's actually gets much better throughput because the bottleneck at the leader there's another less well-known paper by some folks who used to work at IBM in Zurich I think Mir bft they made the same observation and came up with a completely other way of like dealing with this problem um also the whole dag stuff if you read their papers it's all predicated on the fact that oh there's a bottleneck at the leader so we have to get rid of the leader and and there's a lot of nice reason I I like this work and it's great but the the argument that because there's a bottleneck at the leader you have to get rid of the leader

seems a little bit Mis guided what you can do is just remove the bottleneck from the leader but keep the leader in place so we don't need to abandon leader-based protocols what you can do is use a reliable broadcast with balanced communication to relieve the bottleneck at the leader so this way everybody's the leader is just disseminating fragments out to parties and then they're helping because of balanced communication everybody will get the block from the leader now I I mentioned like for our particular protocol there's like four rounds to disseminate to to to run this protocol but if you're careful and clever you can maybe you know shoe you know bolt this uh reliable broadcast protocol into an existing bft protocol in such a way that you actually don't increase the

optimistic latency and so that's so as a as a to closing with a Shameless plug for another paper which I was thinking about presenting here but I'm not um there's a beautiful not my work the beautiful paper is simplex which is from it's a it's a nice um pbft like protocol works in the partially synchronous model like pbft um and it's such a beautiful simple protocol I don't really know why you would ever learn or teach another protocol in this space I mean in in this a in the partially synchronous leader-based protocol it's such a beautiful simple protocol um and then in this follow-up paper that I did I I sing the Praises of of this protocol and in addition to that I I kind of tweak it a

bit and show like um so they don't they're not really worried too much about communication complexity more like latency and I show that you can bolt on uh different flavors of reliable broadcast with balanced communication so that actually you can get um um you you you don't have to increase the latency their their protocol has optimal latency um on a couple of different metrics and you can bolt on more efficient balanced uh broadcast protocol without increasing the latency whatsoever which is really nice and to get all the benefits of of uh of this so then so I did some my my experiments in the space are like run running micro benchmarks and doing back of the envelope calculations to see that like if like nothing else is like really weird then this should like predict the

the the behavior of the system so somewhat optimistically if the leader is honest uh and and this is for a version of this with a stable leader that runs for a while you can get you know 80 megabytes per second throughput which in this space it seems like people take like a half a like a um um yeah so so so this this is this is this is quite good um and uh and then you can get and the latencies are pretty are pretty good too so that's my claim is that uh you don't necessarily have to we don't have to give up all together on leader-based protocols there's advantage in this advantages the nice thing about leader-based protocols is when the leader is honest you can really you know hit the gas pedal and go really fast and

then but the problem is once the leader is is broken it can take you know maybe a couple of seconds to recover and and and switch to a new leader which the dag based bft protocols don't have that problem and of course you have problems with the leader who might be censoring or not fairly scheduling transactions so those are there are trade-offs there final questions complaints so it seems that um you're using two-dimensional re Solon code where you first get a row and then but you get one point you also get a column and then you're disseminating the column so somehow I see similarities there yeah yeah could you yeah I don't know if there's yeah I didn't really

think of it that way but you could I don't know all this VSS with by pols have this structure you you have this you take this whole long message convert it into a matrix give one row one column and then try to help others reconstruct one column that's true it has a similar flavor um and I yeah and maybe there's a way of thinking about it along those lines but I think like this is going to be better cuz I think if you're really working with these B varied polinomial you're going to be stuck uh in the slow lane doing all kinds of finite field arithmetic uh as opposed to using like uh unless they like really good B variate uh uh I I'll I I want to think of them as simple blackbox codes not too

much as uh like they they'll probably still work with smaller fields and then yeah I'm just saying the implementation's out there for like really uh fast uh yeah and and maybe there's a nice way of thinking about that way that leads to some other results and another yeah probably not very important but you can although you have n Square login uh Lambda you can do it n Square so you're saying you get rid of the login like you do in in these other settings that's a good question I I actually don't know I thought about that a little bit okay uh I mean I made sure I understood your techniques and uh and there's something going on there that I don't see how to Sol you can call it an open problem if you like uh uh maybe there's something

you can do there uh I'm not too worried about it because for for like the parameter examples I showed you that that that that second order term is like you can't even see it in the in the final numbers so um so I'm not sure yeah I have uh a question or a comment on the reliable broadcast I think the reliable broadcast the braa broadcast tool itself right yes cuz it does a lot of the work to make sure that everybody actually uh receives the message what can be called totality right you if you output the message I'm eventually outputting the message as well and I think most practical systems they just rely on the fact that they are going to do another round in the future and in this other round in the future I will going I am

going to realize that I may have missed something from the previous round like I have missed the previous reliable broadcast you're going to ask other people delivery and then I'm going to ask other people for what they what they have delivered what I might have missed and so this is not going to come in this is the Practical optimization this right so this is like so I've had these discussions with surov and other people like why are these people doing this why why do they hate on ER raal code so much like and they they insist on doing well because you're right so you could just ask for it right but but okay so two things one is isn't this like opening you up to a Doss attack what you could if n over3 parties are corrupt you could have these these n over3 parties asking

everybody for their block all the time and then what are you going to how you going to well there is yet another exception mechanism to block them out and kick them out of the protocol right how do you know okay so you have to come up with because they have asked too many times okay I guess you could do something that or I thought so there's but I think there's maybe a nice uh if you're not worried about so first of all that doesn't solve the balanced communication problem either so that's no no no that for this ra codes are still good right so they're good for that but even if you're not worried about balance like you're in the the dag writer kind of protocol where anyway you don't worry about balance um you still think I still think there are variations on this protocol where instead of like

uh being pulled for missing uh blocks just pull for missing I can ask for fragments right I can cuz because the problem with this polling is too I ask I have to ask like several parties for a block because I don't know who's going to respond and they're all going to respond and so that's also very wasteful right I could instead like ask everybody for a fragment and they could send me a fragment and then this I don't know if anybody's proposed this in a practical system like you could have like a pull mechanism like what you're talking about for missing blocks but then but based it on eratio codes as well yeah if I'm missing a block I can just ask everybody for a fragment and they'll give might be doing what this called this um they're doing this right the the the bit torrent torren right they're

doing this right there that happens all the time yeah it happens all the time okay but I I also think that you can actually get by you can use this fragment and mini fragment business too to even like cut down the Conant a little bit more if you want as a technical command my initial suggestion to use 2 t plus one in the last round for running with n much bigger than 3F or 3T this could be done right we can have Nal 1,000 and we tolerate only 10 yeah uh n equals tal 10 in this case we this optimization will not work right this you have to go to n minus t to 990 here nevertheless probably but isn't it better to use n minus t to get better to get better better better ER to better eral code parameters you would right okay it's opening up another another

dimension another dimension yeah few people told me that the right now many industry uses consistent broadcast simply send the message collects signatures yeah and they don't they didn't want to do any coding because of this three 3x blow up maybe one but they also but that's what I claim though too I think it's still right I I agree that you can do that you can use consistent broadcast but then use coding to to for the for for the backup pulling for the pulling the backups wouldn't that be better my impr people just want to have a backup they never want to use it if there is something bad they'll start phoning around and then say Oh there's yeah but but it could be that at some time they actually calculate the whole cost right and then there's a story from a r coded

storage like in cloud storage like Amazon S3 and friends right they were initially like replicating stuff like we were doing this eras code a thing that you cited even on say we should do raas coding right and guess what 5 years later Microsoft research wrote oh they're doing aasal code now and all of those like papers right because of the cost like they had to spend they had to buy fewer discs for for the for the cloud storage for object storage right all right thanks again thank you