leanConsensus Call #3: leanNetworking

Transcript

Okay. Hello and welcome to Beam call number three. Uh this call will be dedicated to the peer-to-peer networking layer and we have many many speakers uh today, eight speakers. So let's get started uh as quickly as possible. Uh what I'm going to do is share a set of slides uh uh with a few social updates to get us started. Okay, so social updates. Uh the first thing that I wanted to mention is that uh we are going to have a beam day in can uh on June 29th. So that's one day before the start of ECC. Uh we have a

space. There's uh you know limited capacity. So if you'd like to join, please DM one of the coordinators. We have a Luma page. Um and uh yeah we're giving a preference to uh the devs and and researchers but you know anyone is is welcome to join uh if we if we if we have space also a few useful links and QR codes that I wanted to share from from last time as well. And then another event that I wanted to highlight is the very first EF proofs call which will happen on April 25th at 2 p.m. UTC.

Eve proofs has a lot of synergies with uh the beam chain uh because of the uh the accelerationism of of of ZKVMs that's kind of happening in parallel to all of the the R&D that we're doing uh with the beam chain and there's a te uh a telegram group that you're welcome to join um if you if you'd like to to join these calls and and and the discussion in general. So here is the uh a copy of the slide from from last time around the the tentative call schedule for 2025. We've had call number one with social updates uh and basically calls two to six will be high level research updates on on

some of the key topics and today uh peer-to-peer networking is the the key topic and then towards the uh second half of the year in Q3 and Q4 we will have specking calls uh where we will first start with the subspecs uh and then put everything uh together in a in a holistic feature complete uh beam spec. So, uh this is the list of uh today's presenters. There's uh going to be eight eight of them and uh uh we're going to be extending the call from 1 hour to an hour and a half uh to to to fit everyone and these are some of the these are the topics that are going to be uh discussed. So first of all we're

going to start with Emil who's basically giving a talk which is a continuation of beam call number two the previous beam call on on some of his work around shorter proofs uh and then we'll kick uh the the peer-to-peer networking uh discussion with first a talk on by me on permissionless aggregation and then we're going to have four talks that are basically looking at potential improvements to the the the gossip layer uh age will talk about uh generalized gossip sub uh pop will talk about gossip subop 2.0 know Camille about the grid topology and Lee on on set reconciliation and then we'll close off with two quick updates on

implementations of of lip P2P in in two new languages one is in C and one is in Zigg by Mahair and and and uh the final uh social update that I wanted to give is that the Foundation is building a a networking muscle uh a networking team uh internally we've had POP uh at the FM foundation for for a while now and uh just a few days maybe a few weeks ago Marco came in and we have a third person who will be joining us uh this month uh a very you know early contributor to to LIP P2P um and hopefully uh this this team will will be able to to to help

accelerate the the the beam chain networking as well. And yeah, without further ado, what I want to do is uh start with Emil's first presentation, which again is uh a continuation of last week's call. Um here are his uh contact details uh and you can find some of his work uh on on on GitHub. Emil, if you are uh on the call, feel free to uh share your your screen and get started. Yes. Thank you. One sec. Okay. Can you see my screen?

Yes. Okay. Thank you. Hello everyone. So I'm going to um present a technical note on how to achieve hashbased snarks with short proofs which is particularly interesting for building postquantum aggregate signatures. uh to do this we can use the weird polinomial commitment scheme PCS for short as a replacement for fry. This gives us smaller proofs. Uh you can think of a we proof from between 100 to 200 kilobytes and also there is a fact that we can be used either as univariate or

multilinear which will be useful as you will see. uh so I think there are many three ways of leveraging we in the context of the air arithmetization. First we can use we as a direct replacement for fry committing to each univariate columns as well as the univariate question polomial. This would this would automatically uh give us shorter proofs and it's simple. As a possibility, we can um use the we's multilinear commitment capability by encoding all the

univariate columns into a single big multilinear polomial using the first variables as selectors. uh as well as using W um in its univariate mode to commit to the quotient polinomial and we would get a proof uh which is roughly two weird openings. But we can do even better. We can get rid of the gian polinomial. uh indeed if we commit to the whole air table as a big uh multilinear polomial using lanch basis we can um use super spastan sun check it's a paper um to

prove the validity of all the air constraints without committing to any additional um polinomial different than the air table itself and in the end we can get a snark a hash b hashbased snark whose proof is basically dominated by only one wheel opening so you can think of one to 200 kilobytes which is approximately 10 times better than pron that's the conclusion thank you amazing thank you so much uh Emil uh and from my perspective uh kind of the the story here is that um a month ago Emil

just appeared out of nowhere on my on radar and uh you know in just a few weeks he's been implementing postquantum signature aggregation with you know best-in-class proof sizes but also best-in-class um complexity of the codebase. So it's only you know roughly 6,000 lines of code for the the prover and the verify combined and uh yeah looking forward to to working more closely with with with Emil. Thank you so much uh for the for the short presentation Emil. Okay, let me go back to my slides and continue with the uh start of the the the peer-to-peer networking content. Um, so the following is, you

know, a a strawman. It's a proposal. You should think of it as the the the beginning of the discussion, not the not the end of the discussion. So one of my key goals is for the pitpin networking layer to be potato friendly. And what do I mean by a potato? I mean a computing device which is very very weak. Uh it could be a phone, it could be a Raspberry Pi or it could be a watch. And in some sense this is what makes the the problem difficult uh that it uh that it's potato uh friendly. But uh on the other hand, you know, I'd like the the peer-to-peer networking to be, you know, simple and pragmatic. And there's a few ideas here to to simplify our lives. Uh and I will

go through them uh one by one. So the first idea is to uh reuse lip p. Um so we we've done a lot of work with the beacon chain uh to build a robust set of libraries written in many different languages. And so at first approximation, what I'm suggesting we do is that we just reuse all of the work that or most of the work that has been done already at the peer-to-peer networking layer. And that includes discovery v5 and uh gossip sub. And one of the pieces of good news is that um data availability sampling is kind of pushing the limits uh of gossip sub uh which is kind of um leading to some more

R&D and and innovation at those layers uh and maybe the the the beam chain can make use of these improvements as well. So there's some nice synergies there. Okay, simplification number two uh which might sound like strange is actually to stick with pre-quantum security for the networking layer. So at the networking layer, you have some channels that are authenticated uh using pre-quantum keys. And my suggestion is actually to stick with those pre-quantum keys up until the point where we actually do have an an active uh quantum attacker. And the reason is that these keys are ephemeral.

Uh so they don't live long, they're very low value, and the whole system is offchain. So because it's not enshrined in consensus, it's something that we can upgrade relatively. uh easily without having to do a hard fork. So uh basically my suggestion is that the the parts that are enshrined the validator keys those need to be you know very robust early in advance because it takes a very long time for to do hard forks but also for the validators to upgrade their setup. On the other hand the peer-to-peer networking uh libraries can can stay pre-quantum uh for much much longer. Okay. Simplification number three is that um I'd like to make this pragmatic assumption that not all of the

nodes are potatoes. Uh that some uh small subset for example 1/8 of the of the nodes are actually like reasonably powerful computers. And my definition of reasonably powerful computer is, you know, something like a MacBook. Um, a a a a laptop which has a a relatively beefy CPU and potentially a CP uh sorry, a CPU and potentially a GPU to to to help as well. And um one of the things that I'm not assuming is that there's any actor that has like a really powerful internet connection. So all of these actors on home internet connections the vast majority are potatoes but a a small

subset are actually like slightly more powerful and these slightly more powerful entities would be the ones that uh would be doing the heavy lifting the the aggregation. So unlike with BLS where any you know even potatoes can do aggregation unfortunately with uh postquantum signatures the machinery is is more expensive and and it's likely that uh we we won't have Raspberry Pies and smart watches be powerful enough. Um so it's kind of a requirement that there's at least one actor which is not a potato. But my my assumption is basically that there's at least 1/8 of the nodes. And the the way that I would go

about it is that the clients would run some sort of a dummy benchmark um at runtime for example when they open the client um or on a regular basis and they just try and aggregate proof. So for example they take signatures they they take a thousand signatures and they measure how much time it takes to aggregate those thousand signatures and if the time is small enough then you know that that that node is kind of automatically enrolled and and listed as as an aggregator. Uh so it would be a a default on parameter and if you want to opt out then you you need to specify in the flag that I'd like to opt out uh to

be an aggregator even if uh I'm not a potato. Okay. Simplification number four is that with the aggregation technology that we have for postquantum signatures we actually have more power than BLS. So we have the ability to do recursive aggregation uh which is something that is fundamentally limited with w with with pls and this allows us to do three things. One is this optimization which I call local greedy aggregation. So the idea of greedy aggregation is that if there is a window of time where you receive uh signatures, you don't have to wait until the very end of the window to start the aggregation process. What you

can do is kind of partly through the window just aggregate whatever signatures you've received um and then uh as you receive more signatures well you just append to what you've already aggregated and so that allows us to uh to minimize latency. Another interesting thing is that recursive aggregation allows for collaborative aggregation. So right now we have these designated aggregators with BLS and you can think of them as silos right like all of the work that they're doing of for in the context of aggregation is you know uh local to them and they're not sharing any work with anyone else. And then what we're doing

is we're taking these aggregate signatures and concatenating them uh in the uh in in in the in the beacon blocks. Whereas with recursive aggregation, you you can have one person do a bunch of aggregation and then anyone else can per permissionlessly kind of contribute uh to uh to the aggregation. And then another nice property here is basically a follow on on collaborative aggregation which is that if you have an aggregator who is censoring a minority of a of a testers well anyone can just take their work and add on the the the minority that's being censored. Okay. And then simplification

number five. This is not really a simplification at the peer-to-peer networking layer. is more a simplification for the whole beam uh beam chain. Um whereby instead of having this this this complicated way of sampling the the active validators, we just have a cap on active validators and we just take the the the validators that are the largest that within within this this cap. But in my opinion, in order for um the strategy kind of to to be very attractive in in in in in the long term, we want to have a very very high cap. And so my you know tentative goal here would be to have a million active validators uh per slot.

So what I think we can potentially do is have a proof of concept in 2025 with uh only 8,000 active validators and the aggregation all within one slot. But we should be thinking about the long term. And the good news is that um I believe there's there's an opportunity to grow relatively fast to this to this 1 million uh active validator goal basically thanks to to Neielson's law. So Neielson's law says that every two years roughly speaking uh internet connections will double in bandwidth.

And the reason why I have a square here is that the design that I'm suggesting has this property of quadratic scaling. Meaning that every time internet connections improve by a factor of two will actually we have an opportunity to increase the number of active validators by uh a factor of four. And so over a period of roughly six years, you know, from Genesis uh onwards, we could potentially, you know, get to to to a million validators if we 4x every two years. Uh and if we start at Genesis with, for example, 32,000 validators. Okay. So what exactly uh is the high level uh design that I'm

suggesting? Well, in some sense it's very very similar to what we have uh today. So today what we do is that we uh take our testers and we split them up into um disjoint uh subnets. So if we have 8,000 validators, what we could do for example is put a thousand validators in in each subnet and have eight of them. Subnet one to subnet 8. And um the attesters would be sending the leaf signatures into into those subnets and then you'd basically have uh a a a signature gossip u that we have

today uh in in in each subnet. Now from here onwards this is where things change a little bit. So basically what I'm suggesting is that we um this uh this notion of the local aggregator. So of those 1,024 testers, some subset of them, let's say roughly 1/8 um so roughly 128 of them would be powerful enough to contribute as aggregators and instead of being designated to be aggregators, they can just permissionlessly just help out. Uh and so what they would be doing is that they they would be observing the signatures that they receive at the

gossip layer and and aggregating them on on and on on the computer to form local aggregates. So this would kind of be uh phase one in a in a in a level one in a two-level aggregation. And then once we have the the the local aggregates that are within these small small committees of a thousand testers, we would have this global aggregate. So again, we would have some number of aggregators who would um help out because they're powerful enough to take the aggregates, for example, one aggregate that the best aggregate per subnet and then aggregate

the aggregates recursively to generate uh these global these global aggregates. And ultimately what do we want? We want one of these aggregates to be proposed by the next L1 proposer. So what the uh the proposer for that slot will do is that they'll connect to this uh global topic for the global aggregates. they'll pick uh the aggregate that has you know the most weight um the most uh number of ones uh in in in the in the bit field and ultimately propose that.

Now, happy to to to take questions here, but al also happy to just continue on um and and basically zoom in a little bit to what's happening uh within within one of these subnets. Now, there there's there's a lot of of design space as to what exactly can happen within those subnets, but one of the ideas that I'd like to to suggest is that we have this bitfield first approach. So because we're dealing with fairly large objects each each postquantum signature is 3 kilobytes and each aggregate is like you know over 100 kilobytes let's say uh 128 kilobytes like these are are things that we we we we don't want to be uh

redundantly and needlessly downloading and uploading. And so the the the bit field first approach basically says that every node will basic will advertise to all of their peers what signatures they have as a bit field and which what is the best aggregate that they have also as as a bit field. And these bitfields are are tiny right they're uh 1 kilobits which is 128 bytes. So like tiny tiny messages that that get shared between between the peers and then if uh a peer wants to get signatures download signatures from another peer basically there's this this

message which says I want signatures and the the the bit field will specify the signatures that that that they want. Um, so if if this pier already has a bunch of signatures, then the corresponding bitfield will be zero because they don't want to to download them needlessly. Uh, and so this other pier would just return uh the list of signatures. So these these are are heavy signatures, 3 kilobytes each. Um, but they're only downloaded if specifically requested from from another pier. And then you can have the exact same logic for the aggregates. So uh again uh you would only uh request u an an aggregate uh if uh if you specifically wanted it as

opposed to being you know it's more of a pull pull than than a push uh me mechanism. Okay, happy to pause here. Uh I do have a final slide uh on the updated uh mind map, but just wanted to uh open it up for for questions real briefly. Um on this particular slide Justin uh where you have one like the proposer pick one signature out of the many

signatures in the end. Does this allow uh griefing attacks like you know someone an aggregator having a bunch of validators on the side hiding them from the other people and then pumping up their aggregate signature to be highest weight. You know what I mean? We explored this in the horn post quite a bit and it felt like when in the end you choose the best out of many there might be attacks that are possible. Great question. So one of what I described here is basically this this very simple algorithm which is that each of the global aggregators they take the

best uh signature from each subnet and then they aggregate and then you know you call it a day. But really what we want to be doing is something a little bit more sophisticated than that. Um in particular the global aggregators can learn among themselves. So what a global aggregator can do is basically pick the best that they've seen here and add on anything that that they have which is not in in in the in the best from the other global aggregators. And so this goes back to this to this notion of censorship which I think is what you're you're referring to here. So you could have uh a global aggregate which is the best in the sense that it's heaviest but

it's kind of censoring a minority. Well, as soon as uh you know you have a censoring entity who's publishing the the best well that can be kind of boosted uh to include the the the censored uh attestations as well. So that's a kind of a nice outcome of uh of the recursive aggregation. Okay, Kev is asking why 1 million validators and not half a million or 2 million just because a million is kind of a a round number.

Um and roughly speaking it would give us the same minimum uh amount of E that we have uh today like 32 E. Um and the reason is that you know we have roughly 128 million EH. Um if we have a a million validators that's 128 E uh per per validator if you have the least amount of of consolidation in the worst case you know I think more likely than not we're going to be capping the amount of st to half. So that's already half to 64 E per validator. And you know, more likely than not, more than half of the stake uh will will not be controlled by an an attacker that's trying to spread

all of their E. So this is where you get the the same 32 if uh minimum in order to be a tester. Okay, I'll take one more question if someone uh wants to to unmute. Uh otherwise I'll just read out one of the the questions. Okay, I'll read out one of the questions. Um okay, Casey says, "Regarding Neielson's law, bandwidth scales but latency is roughly invariant." Yes, I agree with that. Doesn't that matter for

how we model this? Um I don't think it matters that much. Um and the reason is that [Music] uh you know there's roughly the same number of hops uh that that are involved. Uh I mean you could argue that as you have more and more attesters here uh then the the number of hops will will grow a little bit. But if you have for example a a mesh top topology where you're connected to you know 64 random peers well the depth of that that mesh of that graph is is going to is only going to grow

logarithmically. So you know maybe there's one extra hop if we if we you know multiply the number of testers by by 64. Um but it's it that one hop is going to only add minimal latency. And then there's there's some designs out there um you know for example Camille has this suggestion to have a grid topology where the number of hops is always two um and so in in these designs um the the latency doesn't doesn't increase at all actually um I mean the number of connections will increase but maybe the number of active TCP connections or UDP connections can

can can grow uh with with Mo's law neielson's law as well just for the sake of time um I'm going to uh move to the next uh speaker but I do want to just shout out uh the mind map so the idea of the mind map is that um every beam call uh I add one little block in the mind map and ultimately we're going to fill the whole slide and so in what I've done so far is that I've updated the postquantum cryptography mind map with uh some you know exciting papers and I've also added the networking mind map.

So the straw man basically is to reuse infrastructure we have discovery v5 uh gossip subub and the two- layer aggregation that we have and you know there's some alternatives that are going to be discussed uh in the next uh presentations and there's some uh implementations that are also happening in in parallel to accelerate some of the some of the R&D. Okay. Uh, and with that I'm going to stop sharing and opening it up to the next speaker. Um, next speaker is H on generalized gossip sub. H, the

the floor is yours. Um, can anyone say this? Yep. Okay, cool. Thanks. Um, yeah, so my name is Adrian. Um, I work on the consensus layer for those of you that don't know me. Uh, it's a bit late for me, so sorry if I'm a little bit incoherent. Um, I also have a little bit to say u, so I might skip over things just for the interest of time inside my time slot. Um, the first thing I wanted to talk about is just to take a step back and look at like essentially the design space of all peerto-peer kind

of structures that or or protocols that we could implement. And I think in in my mind there's three main principles that we uh or I guess features that we're we're looking for. Um, one is like low latency, one is high resilience and one is low bandwidth. Um, and I've been looking at different kinds of ways that we can disseminate like messages on a peer-to-peer network. Um, there's one which is uh like a lean broadcast tree. We can think of a structure where you have one pier that sends it to to two that then sends it to three and it and it um it propagates in in that manner.

That that would be kind of a protocol that is low latency, low bandwidth, but it's not very resilient. You can imagine if one of those nodes are malicious, then it subree is not going to get the message. So you have you sacrifice resilience but you get low latency and low bandwidth. Um if you look at the other side if you want something that's highly resilient and low latency you have something that's like flood sub the the message this is where each node is connected to every other node. Um you're sacrificing bandwidth here. This kind of network you know you have mass massive message amplification. So uh incredibly high bandwidth but you have high resilience and low latency if you don't care about bandwidth. If you look at the bottom you want something that has high resilience and low bandwidth. You've got something that's kind of like pure

gossip. The dotted lines is representing gossip. So essentially the nodes are just messaging that they have a message. They don't actually send the message and then anyone that wants it then requests it of them. Um in consensus land we have gossip subub and in my mind it kind of exists in between this triangle. Um it has parameters involved in it that allows you to make trade-offs between latency, resilience and bandwidth. Um and at the moment we're at the point where we're trying to optimize this protocol so that um we we move somewhere inside this protocol for for our use case. The main point that I think I'm going to try and make in the in the 8 minutes here is that uh we were starting to make trade-offs between each of these three properties. Um and we're doing it specifically for some application. The

gossip sub specification means that if we if we make one particular trade-off, it applies to everything. It applies to all applications. So if we want to make a trade-off for latency versus bandwidth or resilience versus bandwidth for the peer dash topic, it necessarily applies not only to the peer dash topic, but to the block topic. So if we sacrifice latency, we're sacrificing it on the block topic as well. Um it also then applies to every other network that uses gossip sub like filecoin um or IPFS. Um so any change that we make is going to necessarily affect everything else. And uh the the point that I want to try and make is to try and not make that happen like that we can we can target specific applications. Okay. Uh the other thing that I wanted to talk about which is not

really relevant to this talk is privacy. Um privacy has been a long-standing thing. So we've known since since we've implemented gossip sub in the consensus layer that we don't really have privacy. We have pseudo anonymity. Um people kind of think that the validators are anonymous but it's not very hard to deanonymize them. Um and because of that a lot of our research and development let's let's say it's limited because if we propose something that breaks this anonymity it's usually shut down as a community. Um, so my argument here is that gossip, we currently don't have privacy. And so if we were to think of a world like the being chain, if we were going to re-engineer an entire new networking stack, is privacy something that we need? We currently don't have it. And if we were to think of uh a world where we just entirely sacrif

sacrifice it and we say that the validator set we just like people register their IPs against their validator index and we know exactly who we're trying to send messages to. we can build uh like network structures that are more like a broadcast rate. If we know exactly who we're trying to send to um and we're maximally transparent about that, we can kind of build something that's significantly easier to simulate and we can really easily make trade-offs between the latency, bandwidth, and resilience. Um and I think this is potentially an avenue that it's worth exploring if the community is willing to sacrifice privacy. So, it's something I'd be curious to look at. I'm just raising it's not really relevant to this talk but I'm just throwing it out there.

Okay. So this particular talk is specifically for gossip sub what we have at the moment and to do like kind of minimal improvements to gossip sub to to uh to to make one of these trade-offs for our use cases. Um so the way that I see gossip sub at the moment is it's essentially a set of rules that defines how the nodes communicate. And there's different kinds of optimization strategies that gossip sub as it stands allows you to do. Um you can choose essentially how many nodes you directly connect to. These are the the solid lines that I've kind of drawn here. You you directly send messages. It's called the mesh in gossip subub. Um you have you have these configuration abilities that allows you to choose the size of these things. Um you can choose like how many how many do we actually gossip to?

How do we actually form the mesh or the topology? Is it more like how does the broadcast tree look? Uh how often do we gossip and who do we gossip to? Um, these are all kinds of uh configuration parameters that each node on the network can make themselves and they can still be perfectly compatible. Um, and I want to try and make the point that each of each of these configuration settings essentially is a trade-off in that original triangle that I was trying to make. Um, and these kinds of networks are very hard to simulate real world networks. Um, which is something I've learned over the over the years. I go to the next slide.

Oh, I'm drawing. Okay, I'm back. Okay. Um, so I want to give some example strategies. One is episub, something that I I worked on a couple of years ago. Um, the idea in this is that the mesh, which is the solid lines, is dynamic. It adjusts over time. The way that it does that is essentially you have your local view of the network, your local peers. Statistically, you look at which ones are sending you messages quickly um and which ones are sending them uh duplicates or slow and you try and adjust your mesh to be the most efficient as you can to try and get statistically a very efficient broadcast tree uh in a in a global global view. Um so the idea is to try and build like this uh efficient broadcast tree based

on statistics on on how often you see messages. Um the end result of this is that uh when I did finish this, we didn't actually have really good simulation infrastructures and I wasn't convinced that it's strictly good in every possible network. Um so Filecoin, IPFS, if we were to actually put this into the specifications, uh I wasn't I wasn't convinced that it always works. There were some cases you could set some configuration parameters where where it would be worse. Um and ideally we want something that would could automatically configure itself. Another example is gossip subv2 which there's going to be a talk on directly after this so I'm not going to go into it but as a very high level um it has like a a random dynamic mesh so uh the idea is to create a parameter a parameter which represents

like a coin toss or a probability of whether you gossip or not. So when you send a message whether it's going to be a solid line or a dotted line. So the idea is to parameterize gossip sub versus uh directly sending and this is a trade-off between latency and bandwidth which is an idea proposed for for pas. Um in the interest of time I'll skip this but it's very hard to simulate real world networks. So if you see simulations treat them with caution. So what I think the problem is is that because it's hard to simulate these things. It's hard to know what we should specify and put inside the specification. something that that might look good. Um, if we specify it, it it it is hard to unspecify, I guess. Um, the optimizations and trade-offs are often network specific. So, something

that we're looking at to optimize inside Ethereum might not work for Filecoin or IPFS or or something else. So, this was one of the main reasons uh I didn't push really hard for episub. Um, optimizations currently will apply to all topics. So if we try and find a trade-off that works really really good for the pas topic, uh it might not necessarily work really well for the block topic. So if we want to trade latency for bandwidth in pas um we might not want to trade latency for bandwidth in the block topic for example. Um if we spec one of the trade-offs uh into the gossip sub specifications, it can potentially limit our design choices in the future. So if we go down one path uh maybe we could find that another path works better in another application and

it would be hard to to then do that. So an idea that uh I'm suggesting is something that just a quick name is generalized gossip sub but the idea is um we still specify the messages that that uh that the nodes interact with. Um we call like essentially the core specification but we modularize uh all of the trade-offs essentially that we can make. And these modules, we call them strategies. They can apply per topic and at per time. Uh the modules are optional at the spec level. So each network, Ethereum or anyone else can specify, add or remove their own ones and it only directly applies to them. Uh the other points aren't aren't that important. Uh so the general idea

there's a number of benefits for this but if they apply per topic it it allows you for things to things like we can come up with a trade-off that works really works well for pas for example um and we can apply it only to the pas topic we can have a different strategy that works for the block topic and we can apply it to the block topic. we can have something that works uh when nodes are bandwidth constrainted. Um and if you find that your node is like uh is severely bandwidth constrainted, you can switch to a different strategy that might might be better suited that's for for bandwidth constraint nodes. So it allows you to essentially modularize this thing.

Um I think I'm over time, but these are the number of reasons I think this might be good. I'm happy to answer any questions or if anyone wants if anyone's interested to to uh hit me up. Yeah, I'll leave it there. Thanks. Thanks, H. Really enjoyed that talk. Any questions for Adrian? Uh, yeah. Go ahead, Kev. I think you muted yourself. Um, sorry. Um, can you hear me properly? Yes. Yeah. Um, I guess if it's hard to simulate, does that mean that most changes that get added to the networking stack are just tested in

production? Uh, partially. Um, so we we we test on test nets. The test net's network is different to mainet. Um, we we even when we test on test net, we can't control all the nodes on the network. So some of the problems that we we run into is that mo like we've got different versions of different nodes across across different networks. So I don't know of a way of not to test it in production because there's no real way to simulate mainet. So yes in a sense I mean we can get a good idea with simulations but it's not the end story. I can give you examples but I'm not sure if that's

useful. One question I have is have you started uh specking uh specking the generalized gossip server? Yeah. So in my mind you Yeah. So I I wrote a proposed specification but it doesn't really change the specification. There's no real engineering effort. Um it's it's mainly an engineering refactor. you can just refactor gossip stuff as it is so that you modularize the changes that we we might want to make. Um so it allows you to uh just add and replace different different potential trade-offs. So the

idea with this is uh so yeah there does there does exist a specification I put it here um specification in inverted commas it's not polished and it's not finished this just shows the idea um my idea is to implement it inside Russ lip it's as the first step to allow us to do a lot more simulations and testing because we have more we have these modules let's say that we can adjust and simulate and see which which works Thanks again, Adrian. Uh, next up we have uh Pop, who will be talking about Gossip Sub 2.0. Pop, the floor is yours. Adrian, if

you want to stop sharing. Um, thank you. Uh, okay. Let me share the screen. Uh, uh, okay. Uh, uh, can you see the slide?

Yes. Uh, okay. Uh uh okay uh let let's talk about the current version of positive stuff first right uh maybe like some some of you don't don't don't know yet uh when when you you have PR right you you have two kind of peelings uh the first one is like uh the the mesh peeling like like like the so line here and another one is like the the the non- mesh peeling right the the the light line here yeah so there are two kind of peeling Uh and in the current version uh when you publish the message right like uh when when when you publish the message you you you send the message like to the

mesh pier uh and and when you receive the message you also forward the message like to to to your mesh pier as well. uh in in this uh slide uh you will see the uh yeah the solite is a mesh pier right so so the message will be sent from the mesh pier so if the if the dy of the mesh pier is like uh eight so you you will receive like allow eight copy of the message right and that is bad because because uh you don't need like eight copies like you just you just want only like one copy and and and that is enough Right. So we will waste bandwidth for this and and that is problem that we

are going to to solve in the next version. Uh yeah in the current version there is also something called like gossiping. So uh uh sometime some sometime you will receive something called I have uh from the non-mesh PS and when you when you get I have right you you will check uh uh that I have control message like come with the message ID so you will check like uh if you haven't already seen the the message with that message ID and if you have not seen it yet you just uh send I want out right and then you will get like the message back.

So this is this for the uh uh this this this serve as like a shortcut like first of all if if if you if you if you don't get the the the message from the mpia like uh at the heartbeat right uh you will get the I have and like it's like a shortcut that okay maybe like maybe you are too far away from the publisher uh yeah that's that's it Uh yeah. So how we solve the the the the duplicate right? So instead of like when you receive the when you receive the message instead of sending the message right right away to your MP right you

you just send like something called I announce uh so so I announce is like a lot shorter than the message right so so uh it shouldn't like consume too much bandwidth and uh after that you will send like the the the ID control message but but uh it's it's very important that you you you will send like only one I need. Uh right. Uh yeah. Uh because because uh after you you send I need like the the the will send the message back and because you send only one I need and uh so you will get only like one message back right. So uh by doing this you will

get like uh only one copy of the message, right? And uh you you you can you can also see that uh I will send like I need to the to the first pier that send me the I announce first right uh because uh that is a the the fastest way. Uh yeah but but uh there is a problem in in this design because because when when you send I need right uh your PR may not send the message back right and and and if you send I need only like to one pier right and like and like that that P doesn't send you the message back like you will you will never get the message right and that is a problem and so we need to have like uh something called a time out so if I if I

send I need and after the the time out like let's say one second I don't get the message back I will send I need like to the second pier that send me the I right okay that makes sense uh yeah and and uh yeah and and you have you have you you have to config the time out like very carefully because because if you if you set like like the time out like too high uh it may delay like receiving the message right because because if if I send one I need and like and like more than one p like don't leave pi to me like at all I I I will wait I waste like a lot of time uh yeah that is a custo v2 that is idea

so uh you can see that if if if the time out like doesn't occur at all so everyone will be guaranteed that you will receive like only one copy right because because you you you will send only like one I need and and you you will already receive the the the the message like in time. So so the time out has to be config in a way that uh every onet like can can like follow. So it like you can you cannot set the time out to to be something like 100 millisecond right because that is like too low and like when uh for if you are in like in in Europe right and like you ping someone in Australia it will take up allow like 300 millisecond already. uh

question. Yeah, I I guess like in order to remove the the the timeout, um one thing that could potentially be done is to use eraser coding, right? So let's say you have three peers that have each done the I announce. Uh you erasia code your message and then you have each pair send like roughly onethird of the chunks. Um and or maybe they they send a little bit more so that if one of them just doesn't send that their part then uh then you'll still get be able to reconstruct the full message. So you you solve this this timeout issue.

Uh yeah yeah yeah. Uh initially uh uh for is is working on the lendom linear network coding right. So, so, so, so there there is like uh an ongoing English like uh on on on that stuff, but but but yeah, it's like it's is it's more complicated, but but but it uh yeah, we have to consider like which one to use later. Yeah. Uh yes. And uh instead of uh sending only I announce like we we we also you you you can config the parameter like to like uh

like how often you will send like I I I announce and like how often you will send like the the message right away. So so instead of send sending one of the uh uh one of them you just like u you can just like mix them. for spoke uh uh clearly in the spec uh in in the spec in the PR uh uh you will toss a coin like before before forwarding the message you will toss a coil like with with some probability like if uh let's say uh uh you will send I announce like with this property and and uh and uh otherwise you will send like the message right away. So you you will send I announce like with property they the

announce overd and and you will you will send a message like with the property like one man is that yes and we did a simulation uh you can see that uh when when when you do this right you you you will waste like uh one loud time right because because uh when when you send I announce Right? You have to wait for the I need before sending the message right away. Right. Uh uh that is that that that seem bad but but it's not that bad because uh yeah yeah from the simulation I will

show later like why it's not bad but but but you have to know that you will waste like one round tip right for for for the forwarding if you just send a message right away right you will not like waste one round tip. Yeah. Uh so uh we did a simulation for that. Uh this is uh uh we we have like three scenario. The first scenario is like uh the D announce is like zero. It mean that I will never send I announce like at all.

I I will send only like the message right and this uh and this one is like D is equal to to 8 and D announce is eight. This it mean that I will always sense like the I announce like and and and this one I will I will set the the announce seven and D is equal to 8. So it's like uh I will send I announce like with like 708 probability, right? And I like I will send like the message like with one over eight probability. And uh for this one I I I I I try to to to mimic the the the uh for a scenario. So each message is

like 178 kilobyte. And and you can see here that uh the gap is about the the propagation time like the time of the node. is a is a CDF and each line correspond to uh each number of messages like you can see that uh the the C4 message here is like uh has uh the worst level of time right and uh you can see here here that uh for for the number of message right uh uh this this line uh this line the the B line here is 32 two messages, right? And and it's exactly

the same pace as like 64 messages here for the the the now seven and eight, right? So so I assume that we can like double the the B cost from the summation list out, right? But but but but in the lab we have to do like more lorous testing. But but this is this u the family result that that we can like get some intuition first. Yeah. Uh and this is what this is the number of duplicates.

Uh you can see here that okay uh if the announce is zero right and and like D is eight. So on average you will get like uh like eight duplicate right and okay on average which you get like seven duplicate so this is like the number here is like large and for the the announce the announce seven and eight the number is like a lot lower so it's like uh yeah it's it's close to zero but but but you still get like duplicate because like sometime the time uh sometime the time out occur Sometime you will get the the message like form I have I want instead of like I announce I I need right because I didn't remove the

the I have I I have I want mechanism yet. Yeah. And this is a it's for the small messages and and uh it's uh yeah you can see that the the perform performance is like worse because because you will send like more control messages and and if the message is like too small this one is like each message is like 1 kiloby instead of like one uh 128. So you you can see that the format is like worse. And the last one is like the uh uh we also simulate the the malicious scenario. It's like uh the uh we simulate with uh variable

percentage of nodes that that that are malicious and malicious note mean like uh you will not live high to like I need at all. You just let the time out like happen and this is like the results like yeah and yeah I'm I'm a bit over time so maybe like I will go like yeah faster. You can see that you you can see this result is out in the illicit approach and yeah the f the further improvement is like uh if the time out occur right so because because we set the time out to to allow our honest node to to follow so if the time out occur so it mean that uh it's likely that that pier is like malicious so maybe we should d score

them and yeah and also we have an idea of like choke unchoke so so currently uh the the sender will decide like whether to send Ionos or not, right? So, but but but it it probably make make more sense like to to allow the listener to to decide instead of the sender, right? Like Yeah. So, it's like if if if I if I if if I want you to send I announce I will just send you like a short message and like you are supposed to send me like I announce otherwise you will send me like the message right away. This uh support that that you can like read for more detail. Thank you.

Thank you, Pop. Uh, any questions for Pop? And one question I have is what do you think of generalized gossip sub? Uh, yeah. Uh I think uh the the sub uh first up uh I have look at it but uh I yeah it's like that that that that there is a a bit config it's like in in as far as I understand in general you uh it's not easy to to like introduce like

new control message messages but but but in gossip we do uh we we can still implement it like with general generalized gossip stuff but but but I I have to change like the control message but but it's it's completely uh compatible. Yeah, I would have a question if if I may. Yeah. Yeah. 30. So, you know, I'm I'm doing something similar with uh with with the pushpull and then I'm using I have messages for saying that I have it to announce that I have it. And and I'm using I want to say that I need it. And I'm just curious to understand if if

your messages have something special in the semantics and in the handling that because it kind of works for me. But I can imagine I'm like you optimized it better or or you you differentiated in the in the logic. But I I didn't needed new messages. I could just use the the the I have and I want in the same sense as you are using the um the Iron and the I need. Yeah. Actually actually uh uh when we wrote the spec uh we we we found like many distinction between like I announce and I have because because I have like uh add only the heartbeat right and

And there are changing that but yeah so I'm changing out sending out I have messages not just on the heartbeat but uh but but the message itself the the the messaging primitive is is is the same. I mean it it it might make sense to to have it different. I just didn't need it in in the logic to to differentiate. Uh yeah you uh yeah but you have to to share the logic of I have right it's like yeah it's it can be done like with I have but but you just have to share the logic of I have I have right so it's like yeah I also don't know which one is the better to to have another message or not I just I was just curious if if some

some difference it can we can discuss that off offline as well actually actually because because we have time out, right? And and and I I send only like only one I need. So So I think we should send like I need only to like the task worthy pier because because if that that pier doesn't leave high like to me like I will waste like a lot of time, right? So so uh I think the the mesh pier like are more trustworthy. So, so, so that is another distinction that okay I would like to send the the the I need to the matchpia instead instead of

like sending like to to do some lendom like non-me pop in the interest of time I'll uh cut the discussion here um but yeah we'd love to continue the discussion offline we have two more uh longish presentations uh one from Camille on the grid topology and then one only on set reconciliation. Camille, the the floor is yours for the grid topology. Great. Thanks. Uh hopefully you can see the slides. Yes. Um yeah, great. Uh yeah, today I want to discuss like how we can apply grid topology. Yeah, basically for the problem that Justin described earlier.

Um sec. So yeah, just listed some assumptions that we consider when we were thinking about that. Um so say like we have around 16k validators. Um and say like each validator generates a snark or sorry not snark a signature of size 1.5 kilobytes and in addition to validators we have uh untrusted aggregators that generate snarks to prove that signatures are valid. Uh actually that the thing that I didn't consider u I think what's different to what Justin described is well we imagine that we have like we could have unlimited number of these aggregators and it's very hard to kind of differentiate who of them are malicious and who of them are really doing what they should do. Um but yeah

and the last assumption I think it also what's different from what we have currently in um Ethereum validators land is that well validators uh they their addresses are known and they essentially could be matched with their signing public key. So that means basically that they should publish their address. So previously yeah it was briefly mentioned that the question about the privacy whether we should have it or not for addresses. So um yeah for good top apology I think we we should publish the validators addresses uh but yeah here I try to kind of convince and explain what kind of advantages we can gain from that. Um and my presentation is really like two parts. First is um kind of um

uh just describing what grid topology is and second is one of the option how we can integrate it into the signature aggregation scheme. Okay. Um so yeah and our goal is to kind of uh create as fast as possible to sort of all signatures. Um so yeah first uh the grid um so the grid is really simple topology kind of the step zero to kind of start distribution pattern for grid topology is to every validator to come up with the same grid view. Um uh for that purpose they can use some common source of randomness maybe something like rando and then uh can if they have the same source of randomness and the same set of validators that they observe then they

kind of can create this two dimensional grid latis and they kind of can can know the coordinates of each validator in this latis and then the rules for distribution are very simple. Basically each validator maintains uh only connections with their column neighbors and their row neighbors. Um column neighbors I mean all validators that positions in the same column then row neighbors in the same row and distribution pattern um can look something like that. So um basically when uh some validator creates a signature it distributed to all of its um row neighbors and column neighbors and then uh when column row neighbors receive the signature they propagated

further in orthogonal direction. So that means when for example column neighbor received the signature it propagated to all of its row neighbors and the same for row neighbor when they it received the signature it propagates to all of its column neighbors. And that means that essentially just in two hopes after step two we already in optimistic scenario we should have all validators receive the signature uh from yeah the originating validator. Uh but we also have like third step um to distribute I have messages to all. So basically whenever validator receives the signature it also broadcasts I have message to all of its row and column neighbors. That is needed to prevent clips attacks. So that when someone receives I have message but it didn't

yet receive a signature it can basically request the signature from I have sender and also these I have messages they are very helpful kind of to reduce number of duplicates. Um yeah the the the most amount of duplicates each pier can get for the same message is two because well they just have two options how to get this me message. But if for example they uh already sent I have message uh to someone u who is supposed to send this message to this validator then well uh we have no duplicates basically. Um yeah, if you look carefully, there are a lot of these I have messages that basically produced for each signature, but they really lightweight. Uh it's

just some meta information about maybe pure ID and round. Um so yeah, I hope it's not like large problem. So the benefits um that grid topology bring is that uh yeah, first and the most important is that distance between any two arbitrary validators is at most two hopes. If we compare for um if we compare that with gossip sub we basically observe that well for the same number of peers like 16k peers and with fan out factor six we have average distance of approximately five um hops and uh then the next advantage is that well each signature generates basically linear number of total signature messages in validators network. Um if we

just use the gossip sub then uh in the worst case we would have like uh n * k signature messages um before actually well of course we can apply something like I don't want or uh other optimizations but they because of undeterministic nature of gossip sub uh yeah as we previously described it's very hard to simulate and can come up with the optimal parameters for these I don't want parameters um and yeah in addition to this linear number of signature messages which are heavy We also have n time n to the^ 33 of I have messages. Uh but yeah as I said they're very light so but and they need it for eclipse attack preventions basically. And um yeah u last advantage is the basically duplicates handling

because we each peer as it described previously could just receive the same message from at most uh two other peers. That means well there there are not really a lot of duplicates could happen in the network which is why we have we don't have like a lot of messages per each signature um and uh I'm saying at most but because we have I have messages yeah sometimes just get one u original message and no duplicates at all there are other benefits that not listed here that's like something for example well because of deterministic nature peers know who they exactly need to talk to so they don't need to perform um costly TLS handshakes to new peers every time or um yeah because of deterministic nature

it's much easier to simulate these networks kind of try to play with malicious actors and see what the effect they have on signature distribution. So yeah and and and from here we kind of go to the second part where I'm trying to kind of is just to come up with some example of how we can apply this. Um so uh yeah because in my assumptions we kind of assume that uh well a aggregators they do not have any stake and there might be unlimited number of them and we have no means to kind of check u if they are I don't know malicious or not. Um therefore we can consider them untrusted and they we consider that they can really join or

leave the network and because of that uh it's very hard to join them to grid lattes but if this requirement is not the case and well we can basically rely them yeah joining them to grid with the validators would be great actually. Um but yeah if it's not the case um yeah then uh yeah we should come up with something else and um yeah just u some other challenges that we can have with grid topologies that well we cannot put all validators into a single grid for um signature messages distribution because that would mean that well if we calculate amount of messages basically that means all validators should receive all signatures from all all other peers then um if we assume like three seconds to distribute

signatures uh then um and 1.5 kilobyte signature and 16k validators then incoming bandwidth requirement would be like something like 128 megabits per second. So that's we consider like a lot if we consider like potato validators. So uh we should reduce it and the natural way to reduce is to basically not to have a single grid but have multiple grids. So that's again some somehow similar to what we have with BLS signatures aggregations but in contrast to BLS signature aggregations where we have like known um validators who aggregate signatures here aggregators do the work and there are a lot of them uh in our uh assumptions. So basically what we do here is uh well validators are

split into grid subnets inside each grid they propagate the signatures very fast just at most two hops and uh then uh whenever validator update a signature it can also stream it to the aggregators uh subnets. Uh so basically uh we have as many aggregator subnets topic as as many validator grid subnets we have. Um each aggregator can actually subscribe to m multiple grids if they consider themselves kind of powerful enough so that they can aggregate from multiple grids. Um inside this uh aggregator's gossip subnets I think we can further accelerate them maybe use something like ibo for kind of the signature set reconciliation about which I think le will describe later. Um so yeah and then

when the this kind of the first level and then uh any aggregator when it collected enough signatures and uh produced a snark it can propagated further to the kind of final aggregators subnet and uh these validators again they kind of exchange um u they use gossip sub here. So they uh exchange um uh these grid level snarks and then um come up with the final snark which they then send to uh validators again. And actually this time I think we can put all validators into single grid because uh each valator would propagate for them it would be just enough to propagate uh a single snark to all other peers and then just ignore all other snarks assuming the first snark was uh valid.

Um so we really don't have a lot of messages going through this final grid. And I I I I think it's important to kind of all validators to receive the final snark because assuming we have something like whisk with secret slot leader election uh then we don't know exactly who would be the next proposer. So uh we basically should send snark to all validators. Um so yeah that's uh that's grid uh yeah just to conclude this we consider it's kind of like effective protocol uh for distribution among validators assuming validators know each other's addresses and so they can and they also have some common source of randomness so they can form these grids and u yeah in general I

would like kind of consider this a as a building block uh this grid topology uh this proposal is not necessarily like how exactly this things should look like but Just hopefully I was able to describe main advantages um yeah of this approach. Yeah, thanks. That's all I had. Amazing. Thank you so much Camille for this very clear presentation. Any questions for Camille? I guess one question I have is um is it correct that this grid topology has been implemented in in polka dot and like do

we have uh concrete uh numbers of the performance there? Um yes correct uh we have implemented that well we are um maintainers and supporters of C++ and we use that in our pola dot client. Uh basically in polo we use grid and if you run a polka dot validator you have in your CLI command you have like a field public address which you should put and which is then uh kind of publish to everyone and uh uh so yeah validators we in polic we have six second slots and uh the task they have is basically so whenever we have a statement that some parach chain which is kind of to uh is valid this statement should be

distributed uh to all validators as fast as possible. I think currently in Polot we have if I'm not mistaken 600 validators but the goal is to have 1,000 and we have 1,000 in Kusama which is the canary network for polka dot. Uh so yeah basically we have uh grids so for thousand validators and within six seconds uh it is good enough to kind of distribute this statement so next uh block producer has this statement to include it into the block. Um I think in beam we have requirement for 4 secondond slots uh which is why uh we have I proposed to have smaller grids so that this distribution happens even faster.

Um but yeah that's kind of what we have. Okay thank you. Uh final long presentation is from Lee on such reconation. Le the floor's yours. Um, can everyone see my screen? Yes. All right. Um, yeah, thanks a Yeah, I'll try to Yeah, I think this looks better. Um yeah and uh thanks a lot for um for having me here and I really appreciate uh Justin sending me the invite and uh

and also the organizers for organizing this series of costs. Um my name is Lei and uh I'm a co-ounder of Mega E but the work I'm going to talk about is um is from the work I did when I was a PhD student at MIT and is partially is fully funded by a by a very generous grant from the Ethereum Foundation. So I really appreciate that. Um so the goal of the talk is really to um kind of introduce a a a series of um a type of very interesting primitive um that that is called set reconciliation and I think it's would really help like pushing um pushing the performance or kind of enhancing the trade-off um of peer-to-peer protocols. I think a very

interesting a very good point was made in one of the earlier talks that with um with like designs of peer-to-peer protocols you you're basically trading off three stuff three things one is the resiliency basically how reliable can you get your messages to um your peers to to kind of throughout the network second what's the latency basically what's the time it takes to propagate the messages and third which is the which is the amount of bandwidth consumed in the process so um I my point is that step reconciliation could be a tool that can uh improve the trade-offs like for for the same amount of uh resiliency and for the same amount of uh latency you're going to tolerate you'll probably be able to um achieve a much lower bandwidth consumption. So that's

kind of trying to set the stage. Um so I will give one motivating example which I think uh most of the people on this call are already aware aware of which is when you uh gossip messages in a peer-to-peer protocol um you risk um sending redundant messages. So I I'm making a very simple um um example here. Suppose that Dave got a message which is 0x ABCD 1 2 3 4 and uh Dave needs to propagate the message throughout the network. So it sends to Bob and Charlie which are um his immediate neighbors and uh Bob and Charlie um are both connected to Alice um but none of them know that um none of them know the the network topology. So

the natural thing for them to do is to gossip right it's just to flood um the message and uh at the end of the day both of them send the same transaction which is 0x12 ABC 1 2 3 4 to Alice and u um Alice receive the same message twice which is redundancy because Alice only needs to learn about the the message once. Um so um I think pop was um mentioning um gossip subb2 which would uh include I announce messages and uh um however I think the point uh is that uh announcing um inventories announcing like the the messages that are available to send uh with say shorter with shorter hashes is not always optimally

efficient. Um I think in almost every case it's a very practical solution and it's I think a very robust and practical solution. But um I think the point here is that when the actual messages that you are trying to send um is short enough and when you have enough peers then these I announce messages can also constitute um significant overhead because for example here um suppose that Bob Dave and Charlie all have um the same um all have the same uh message to send to Alice. Suppose that the message is again 0x ABCD 1 2 3 4 and the hash of the message is 0x beef. Um so Bob, Dave and Charlie would each send an I

announce message to to Alice and uh so this is already um 12 characters and the actual message that Alice wants to receive is only eight is only eight characters. So it's kind of a motivating example of when this kind of signaling or or portal messages can cause uh um overhead especially when the actual stuff to be sent is very short. Um so let's try to kind of abstract this problem a little bit. So the problem here is for Alice so so kind of let's kind of try to isolate this problem to just one pair of peers like Alice and Bob. So um the the problem here is for Alice to learn only the new items from Bob and vice versa. Um so

here for example Alice holds a set of items that she uh intends to to flood to Bob and Bob also has a a set of items which is B um that he intends to flood to Alice. Um so we we realize here here that um there's significant overlap between the two sets. um both items A and B are present in both um sets. So actually Bob only needs to learn about C and Alice only needs to learn about B. So the problem here is to figure out that fact because Alice did not really know the the content of Bob's set and vice versa. So um it's it's actually very tricky for Alice just figure out that hey Bob is missing C and I should send C to Bob. It's doesn't it doesn't

work right? And I I guess uh sending I announce messages. One way to to to make it work. Basically Bob can kind of describe what's the content of his set using um succinct um identifiers like hashes. But as as I mentioned when the actual items are are short the hashes are not are not much shorter than the actual items and you don't save a lot of bandwidth here. Um so this problem of having two parties u learn about the union of their sets is called the set reconciliation problem. And uh the kind of the definition here is a little bit quirky because based on the definition um only one of the two participants like Alice or Bob needs to learn um the union of their sets in order for this process

to be declared successful. But um it doesn't matter too much because once say Alice received the union uh she can always um send uh the union to Bob because she will actually know which items are missing on Bob's site. So um I think this c this talk is kind of trying to be a like an overview of what's possible with set reconciliation. Um so um let's first define like a parameter of this protocol which is uh the size of the symmetric difference of their sets which we denote as D. So here D is the number of items that are exclusive to only one of the participants. For example, here the size is um two because uh the symmetric

difference is just C and D. So here the parameter D the size of the symmetric difference is two. And uh um set reconciliation is I think it's a it's a very fascinating problem and uh it's first proposed in a in a paper back in 2003 and within the paper the authors actually proposed a a kind of information theoretically optimal solution. Um so which I summarize here on the on the first line which is Alice and Bob can can finish set reconciliation when after communicating exactly um the same amount of bandwidth or the same amount of data as the items and if you think about it that's really the information theoretical lower bound

because um one of the one of the um the one of the participants needs to learn about the symmetric difference in order to reconstruct the union. So if the person is learning D items then it makes sense for the person to receive d uh the amount of communication or the amount of data right so it's a communication is very efficient however there's a kind of a catch which is um it takes quadratic computation and when uh when when the size of the when the size of the individual items are large uh and and also when uh when the number of when when the number d is large is actually quickly adds up. So um the second paper um which is one from uh from 2011 um proposed a kind of a different scheme in

solving this problem which uh successfully brought down the the computation cost from quadratic to to log linear which made this u the scheme very practical and it also retained somewhat the the the kind of the information theoretically optimal um communication bandwidth. it adds a very small factor maybe two or three in front of the number D when it talks to when it talks about communication cost but it's still quite efficient. Um the caveat here is that um the protocol requires um pre-nowing or pre- guessing the size of the symmetric difference or the number of differences that is trying to reconcile. So this is kind of a um uh pretty much impractical thing uh to use

in in in uh in real systems. So the third paper which is the one uh supported by the EF um uh brought this uh solution to the state-of-the-art basically removing the requirement to pre-note uh the number of items to reconcile. So basically now reconciliation is as simple as say Alice sending a stream of data to Bob and Bob can say stop when it receives enough symbols or when it receives kind of enough information from reconciliation and that's that's that's it. So to to kind of to recap the communication cost of state-of-the-art set reconciliation is kind of a small parameter a small coefficient times the size of the

difference to reconcile. So here the actual coefficient is 1.35 um and we can even bring it uh to about 1.10 one zero if we use more sophisticated algorithms but I I I'll leave it um as as kind of future discussion and the computation is lock linear um and um according to my experiments you can achieve tens of megabyte uh sorry tens of megabit per second per CPU core in a somewhat in a somewhat kind of outdated server CPU so it's not not very beefy CPUs and uh it only takes one half of a round trip or a single trip um for reconciliation to finish because Alice can just keep streaming the symbols and uh and Bob can just tell Alice to stop whenever it

finishes and also maybe piggy back um with um uh the items that Alice should learn about in order to reconstruct the set union on her side. So um I'll just spend maybe one minute talking about um the basic idea of how reconciliation is done. So um so let's let's kind of consider a very special case when Alice and Bob sets differ by exactly one item and uh let's just kind of attempt that we can encode um the items into integers. So here in this example Alice has four numbers and Bob has three numbers and there's one number that only Alice has but Bob does not. So Alice can calculate the sum of her items and Bob will calculate the sum

of his items and uh Alice can just send this sum to Bob and uh Bob can just compute the the like the subtraction of the two numbers and uh he can rec he can reconstruct the number that he's actually missing right it's just arithmetics. So when we want to generalize this basic idea to scenarios where A and B does not differ by exactly A and B do not differ by exactly one item then it gets a little bit trickier but uh it's still doable and the main challenge here is to kind of figure out how to group those um subsets that you sum up and uh and how to yeah basically how to group the subsets to sum up sum up and how many such groups or how many

sums do you send over the communication channel and uh for a uh former treatment I would recommend uh taking a read of uh section three of this papers. I think it's less than a page or uh we can watch the first five minutes of this video. Um so I will skip this part because it's just uh kind of a demonstration of how to apply this to to um to signature aggregation in beam call in beam chain. So basically you uh reconcile the sets of uh un aggregated signatures among uh the nodes with the aggregator and uh I as a kind of a a quick u detour I'll mention that second satire constellation

has been u is going to be deployed in bitcoin um there have been two proposals one's called early and one's called graphine and both of them try to use such reconciliation to make um transaction ction propagation more efficient in Bitcoin because if you think about it, transactions are exactly the type of data that are short but are a ton of them and you really want to worry about the the cost of signaling like those I'm like those I announce messages or those those INV messages in in Bitcoin talks. Um, yep. So, um, yeah. So, the idea here is that to to reconcile the hashes of the transactions in people's memory pools instead of flooding them. And, uh, this particular proposal which is early is already

implemented in Bitcoin core actually a few years ago. And, uh, uh, the last time I checked, there's a uh, I think uh, March 2025 or March this year um, update I think uh, saying that it's progressing towards deployment in Bitcoin's mainet. So um to summarize quickly um yeah um the the status of set reconciliation is that uh an an implementation of the state-of-the-art scheme that I described is more or less ready. Um again uh uh supported by the Ethereum foundation. So yeah really uh really appreciative of the support. Um it's in Golang and uh there have been community like volunteer um volunteered implementations in C++ and Rust. I think

it's also being incorporated in some of the frameworks um for building efficient distributed systems. Um I think as a next step some simulations need to be done and uh we need to kind of measure in the particular case of beam chain and signature aggregation does it actually make sense to use set reconciliation and how much gain potentially can we make uh compared to say gossip sub and um there are a few open questions I think um uh for example the top the topology I think do we uh use grid I think grid is kind of a very promising topology but because it's very structured and uh um And yeah, so we should also incorporate that into the simulations and and do some tests and uh and kind of an off-topic point is

that um other applications in the in the Ethereum ecosystem or other applications of uh lip PDP uh may also benefit from uh from this scheme. For example, I performed an experiment trying to um do state healing using set reconciliation instead of walking interactively the the Merkel tries and uh this this kind of this reduced number of interactions basically there's only one round of interactions um really helped in terms of saving the overall uh job completion time. So I will stop my talk here and I'm happy to take questions.

Thank you Lee. Sorry, go ahead if there's any questions. Yeah, I I I guess I have a it's related to the discussion of of simulations and and I understand at one level that's sort of at some most of what people have right now. There's some test implementations, but a lot of it is simulation. But there's a I wonder a little about um a tail wagging dog aspect to some extent. I understand it's much easier to test things um with if you have solid reliable simulations, but I mean multiple speakers and I don't mean to pick too much on this one, but this comes up prominently. I don't think it's that bad a target have emphasized how much easier it is to simulate. I mean, yes, how it's

better in other ways, too. But one of the main ways some of these are better is they're easier to simulate. Okay, great. But is that um let me say how relatively important should that be? I want to kind of pose this as a question in terms of picking a protocol. I is the answer to make better simulation tools a little gibbly. Interesting. Um so if I I think it's a very valid question and uh if so it's kind of the the the I think my habit is to to simulate uh first because it's always good to fail early and uh if simulation tells that hey there's some significant uh issue with a scheme then

I would say that running a simulation in say net++ or or or NS2 N3 is much uh lower cost than uh doing an actual deployment or sorry doing an actual implementation and uh like setting up a like an emulation um like real deal networks. Um yeah. So is it a correct understanding that the alternative would be uh more theoretical study or um more um like real deployments or or real implementations?

Well, I guess what I had in mind was like to what extent this is a is this a question of the simulations are challenging but feasible or to what extent is it that certain of these protocols let's say the gossip sub as we have it today or general wise gossip sub as as age was I I think right presenting it um are just borderline un unsimulatable versus what is it that are more tractable simulations. I think I'm still working with or thinking within the realm of simulation here because I do agree that it's a very valuable tool uh and and theory and and full-on deployment have their place, but simulation is is a great middle ground.

But is it just like 10% easier or is it feasible versus not feasible? Uh very good point. Uh I I see I think it really depends. I think for gossip stuff I think it's I mean it's way more advanced than than some of the ideas including this threat set reconciliation idea proposed in the scheme because um even though say set reconciliation you have the library to to to to kind of to to use you don't really have an end to end like uh executable but it's not the case with um with le P2P um I think there was a a very interesting point made in uh the beam uh research uh telegram group I think someone proposed a a a very nice tool that can just run um uh unmodified

Linux binaries in this simulator and the simulator is going to simulate a network for you but you you just supply it with an unmodified um original uh binary which we already have for for gossip. So I think for gossip sub I think simulation is per per my understanding it's borderline no cost and uh I think it's a very cost effective way to verify a potentially very large scale um of protocol deployments. Um I I personally ran a few um experiments of involving more than a thousand AWS servers and I burnt I think 50k um of my advisor's funding uh because of that and uh then I

started to kind of just switch to simulations first. Um on the other hand um for those newer portals per my experience um simulation is I think 20 or 30% of the cost of doing a proper implementation because you can worry about much less stuff because you have a very nice environment. you there's never uh connection drops. Um and uh you can just focus on writing the core state machine and not worry about like uh writing the boiler plates like connecting to uh like opening up sockets and then like maintaining connections error handling in particular. So um yeah

that that's my limited experience like 30% of the cost of of an actual implementation. Um yeah. Um yeah, I'm I'm not sure if that if that answers your question. Um yeah, it it I mean 30% is quite something. Yeah. Yeah. No, no, absolutely. It it quantifies it in exactly the way I was um looking for. Yeah. Thanks, Lee. Thank you so much for the presentation. Uh one question I have but I'll ask it uh offline is um you know does this help when the the messages are are very small versus very large and I

think in in our use case we have you know very large messages and so quantifying the the possible uh improvement is is something I'm curious about. One of the things that you mentioned was that we have this uh telegram group. So it's the beam peer-to-peer networking telegram group. It's a relatively small group with 29 members right now. If you are interested in contributing to the peer-to-peer networking uh layer, do send me a message and uh we can add you to that group. Okay. Um so now we're going to just close off with two uh smaller uh presentations on implementations of uh lip p. The first one is Mahir uh in implementing LTP and C and then Bing uh

in ZIG. Uh Mahir, the the floor is yours. Yep. Thanks, Justin. I'll just share my screen. Um yeah. Okay. Let me know if you can see the screen and Yep. Can see the screen. Yep. Okay. Yep. Hi everyone, my name is Mir and I'm from the Pier 2 team. Um in this presentation I want to give a brief overview of the progress we've made in the C implementation of lip. Um so basically uh we started development of the library on uh 7th of March and uh this week we actually made the repository public on GitHub. Um we

ended up starting with the multiformats uh modules and have implemented these modules so far. Um for the multibase module, the implementation only supports all the base encoding formats that have the final status in the multibbase specification. But uh we can definitely we will definitely add uh support for more base encodings uh if needed in the future. Um for the multi-ash uh module, we have currently um implemented all the common SHA support for common SHA functions except for SHA one as that has been deprecated. Uh but again uh we will def we can definitely add support for more functions if needed. Um and also for the C module um we're implementing

support for uh visa and we want um at the moment uh we're still making progress with uh the multi address module and as well as the pure ID module. Um the the core functions uh have been implemented. uh we just need to verify the correctness um with test cases and ensure that they can pass on uh multiple different platforms. Um and uh once uh work is done uh on these modules um we'll be able to focus on uh implementing these modules here uh the to-do ones. Um and uh I'm sure that I may not have uh mentioned you know gossip sub but we also do plan to support that as well. Definitely um our

goal is to basically u make the library get the library to a state where it supports enough modules such that it can be used to be able to interact with any uh beacon node in the ethereum's consensus layer. Um once we have you know robust implementation that has been thoroughly tested and works on multiple different platforms uh we would be happy to start sort of prototyping any new protocols uh that will be that are being developed uh for the beam chain. Um, regarding contributions, uh, because the library is still at a very early stage of development, uh, it is not yet intended for public usage, uh, as the maybe some continuous changes to the API. Um, like for the modules that are currently

implemented, I'm expecting that that not to be the case. Um, but uh, there is a bit of slight risk that the API may change. uh but uh once we have finished uh implementing all the like core modules um we'll provide like usage documentation for the API and then we'll be happy to accept any feedback um uh for improvements uh or if there are any errors with the library we'll be happy to accept any pull requests um but yep um just thank you everyone amazing thank you so much uh Mhira any questions. Okay. And thanks again, Mir.

And yeah, looking forward to uh this implementation blossoming over time. Bing. Uh the floor is yours. Yeah. Um, can everyone see my screen? Yes. Right. Um, so yeah, thanks for having me on such such a short notice. I'm just here to share a bit about Z P2P. Um, we are currently building this out at Zen. uh the work is mainly done by uh grape baba or kaun and me. Um so I just want to keep this short

and sweet just to share what we currently have done and what we are focusing on next. So currently we have on this slide you can see this three core projects that we have been working on. Multiformats mice protocol and yamix. Two of the first projects are more or less done. The current focus is kind of on Yamix as well as working on adding examples to noise protocol to demonstrate the library usage. All of our work is open source and discuss at github.com/zen-e. Um feel free to follow us on GitHub and join our target group.

Uh DM us if you have any questions. And yeah, one thing I didn't mention was that yeah, our goal our near-term goal is to eventually pass all the interop test plans that's provided by the P2B team. So if you're interested in Zim and ZIK in general, feel free to follow us and join our Telegram group. Thanks. Thank you, Um, one thing I'm curious about is um, you know, how how are you guys how are you guys funded? My understanding is that Zenf is like a pure public goods entity and I only just learned about uh, the team recently.

Currently, we're just doing this uh, sort of um, like in our time in our own time. Yeah. Okay. Amazing. Thank you so much, Bing. Um, so this any questions for Bing? Yeah, Gajin says, "Go Zigg in the chat." Um, this if there are no questions, uh, this this concludes uh, beam call number three. Um, one thing I do want to mention at the end of this marathon call is that uh there is a telegram group for the beam calls. Um, all of the devs and the researchers should have been

invited. Uh, if you are a dev and researcher and you're not part of that group and you do want to be, uh, do send me a DM. In addition to that, uh, anyone who joins two of the beam calls also gets invited. So, if you're watching this and you made it to the very end of this video, congratulations. Uh, if you've joined two of these calls, uh, as a as an attendee, you're also welcome to join this this this group. That's it, folks. Um, see you see you next time for Beam call number four. Thanks. Bye. Thank you. Thank you.

Bye.