Post-Quantum Cryptography: P2P Aggregation

Transcript

Today I will speak about the P2P aspect of signature aggregation. Um yeah I'm Camil I'm from Codriium and that's the I will present some efforts from our team and also uh well the result of some discussions for with EF research team. So yeah let's get started. Um so yeah with postquantum signatures really a lot of um assumptions that we have today are changing. So uh basically the size of uh signatures that we have grows from something like six bytes to 3 kilobytes.

Also the aggregation size increases to 128 kilobytes. Well the exact numbers still depends on the scheme that we're going to choose but yeah approximately um in the order of magnitude it's how it's going to look like. Um also the aggregation cost increases. So previously the aggregation cost was pretty low. So basically any tester in the network could perform an aggregation and now it's relatively high because we have to perform uh snark aggregation and um yeah for that uh what what is changing is that we cannot anymore just simply rotate who is current aggregator to within the subnet to perform an aggregation. So um uh there there should be some process of selecting uh the

aggregator and well they're going to be the basically uh the members of the subnets who going to be performing the aggregation. Um yeah just some numbers that we considered in our work is well that would have something like between 8 to 32k number of validators. So that's basically the amount of signatures that we need to aggregate. uh also we have like now four second slots uh but but general approach I think uh uh would be more or less the same. So basically we have like two-tier architecture where we first begin with uh subnet aggregation.

So um within the subnet we perform first aggregation but instead of BLS aggregation it's going to be snark we call just snark one and then there going to be some global aggregation topic uh where the peers the global aggregators would further recursively aggregate this snarks into some global snark which uh we're going to put on chain. Um yeah, of course that's still a matter of modification. So maybe yeah, we'll come up with a better scheme. But yeah, that's how we projected so far. And uh yeah, this opens up certain P2P design space that we consider like first is how we perform uh subnet aggregation. uh for example whether we like wait for uh some

certain threshold number of signatures that we want to collect um before we actually perform the aggregation or maybe we come up with some kind of well aggregators collect some certain number of signatures then they um aggregate them create snark propagate it to other participants in the subnet then they keep updating this snark uh so yeah there might be different strategies how we actually perform this agree regation. Um the next thing is subnet topology. Like again here we have we have to kind of agree on some assumptions that we want to choose before we uh agree on which topology is the best suits for for for these needs. And uh the next thing would be kind of how we communicate

between subnets. So that once we have uh subnet aggregates how we do we broadcast it to global aggregators so that we then create the global uh snark. Uh so for for the sub topology yeah there are some key questions that really affect how uh how we're going to choose the best topology that we can use. So for example whether we can have assumption that validators or aggregators addresses are public currently it's not the case. So basically because we're using cosips um yeah there is no need to um presume that addresses are known. So yeah, basically validators they just subscribes to subnet aggregator topic and broadcast their signatures there. Uh then there is a question like whether we need all

validators to receive all signatures in the subnet. U well I mean like if we have validators that only perform at the station uh and they are not performing aggregation whether it's really needed for us to for them to then to actually receive the signatures from other participants within the subnet. And the same question like whether uh validators the testing validators actually need to uh receive the uh subnet level aggregations. Obviously they need to eventually get the final aggregation but for the subnet aggregation uh yeah there's a question whether they really need it or not. Um yeah depending on how you answer the question yeah we really can choose I think the best topology. Um uh yeah in our work we

considered we started just as some simple direct topology where uh just a testing validators would create a signature and then uh there are um some local aggregators inside the subnet. Uh their addresses are known. So they just can so testing validators can just connect to them directly and send their signatures. Then aggregators would propagate it within uh well to other aggregators and then once they have enough they prepare they generate a snark. Um the another thing that we obviously need to consider is the gossip. It's a well battle tested topology. Um here all our testers and aggregators they kind of

participate in the same topic kind of what we have now with BLS signature aggregation. Um yeah there are mesh connections where we actually send the um signature messages and um non-mesh connections where we send different kind of I have I want messages to um optimize gossiping. So yeah with that topology well everyone in the topic would receive a signature receive aggregation um there is no requirement for anyone to actually expose their public address. Um so yeah another interesting topology that we think might be also considered is grid. Without going just deeply into details uh with grid we can basically uh

it is possible to send any signature from any validator to any other validators to within at most two hopes. Uh so the propagation is really fast also because there are only two ways how uh each individual signature can uh get from one validator to another uh there are really at most one duplicate that any participant can get u but yeah to uh to make it work to make uh yeah each validator should have the same view of the this two dimensional latis of nodes and yeah for that we need in all validators to kind of be aware of addresses of other validators in the subnet. Um yeah, we can combine you can

just take any of these topology as a building blocks and combine them together like for example u for example testing validators they can send to aggregators which are connected using grid topology and then they propagate the signatures to each other very fast. That way we only need to expose public addresses of aggregators not the validators. So yeah there's there are a lot of design space here. Uh then uh yeah once we have uh the subnet aggregation uh this first snark um obviously because they have weight of 128 kilobytes it doesn't make sense to just simply gossip them uh but instead it makes sense to kind of just announce that the uh that the aggregator actually

has a snark. This could be done in the form of a bit field uh so that when global aggregator for example receives this bit field he can decide like whether he needs this snark or not depending on whether global aggregator already observed the snark for this subnet. Um or maybe they now observe the better snark which aggregates more signatures. Um so yeah the topology I think is the way here to implement this. So yeah to test all of these assumptions and to implement them uh yeah we created a very simple simulator. Yeah we just go with the name beam sim for now uh it is discrete event simulator. So that means it allows us to actually have very reproducible results.

We just supply with some seat and then yeah if we want to repeat the test we can do this. uh it simulates real TCP and UDP transport beneath and um yeah it actually horizontally scalable with the number of CPU cores because uh NS3 has very good MPI support. So uh each subnet we can put into separate uh process and run in a separate CP CPU core and only there are not much really between interprocess communication. So only when the final aggregation or the aggregation is done only then yeah we communicate with other subnets. So yeah um it is available on GitHub. Yeah uh there are instructions how to it is written in C++

there are instructions how to actually build the project and uh but if you're lazy to build it yeah there is a docker which you can use if you want. Um it is not as stable. I just checked yesterday unfortunately NPI is not working very stably under docker environment but still um yeah you can give it a try if you want. Um and uh yeah once uh you have a project built uh it looks uh something like this um Jupiter notebook where you can um basically configure some default parameters for your network like number of validators, number of local or global aggregators uh some for example if you go with

gossip subtopology go sub parameters uh different well cryptographic constants like size of signatures of snark marks like how many signatures we need to collect before we actually perform an aggregation um aggregation well rate per second like how many signatures we can verify um um well how many signatures we can aggregate within a second how many snarks we can aggregate and so on so and then um yeah we choose basically the topologies that we want to run and then yeah uh we can see like how long it took for uh to uh generate uh the snarks like the first snarks and then the global snarks

and once we had like the global aggregators collected enough local snarks they perform an aggregation and then we see the exact point in time like when the uh the very first global snark was produced. Um yeah then we can also check like what was the total network traffic consumed in the network what was the peak bandwidth uh for different types of nodes like uh validators local aggregators or global aggregators. Um yeah uh I think uh yeah I really hope this will kind of spark some discussions like about the design like what we actually um uh want to implement and uh check different assumptions. So yeah if

you have any suggestions feel free to approach me or contact me. Um yeah that's all I had. Thanks Dave. Can you talk a little bit about your different options for simulating networks? Which ones you considered? Why you didn't go with the other directions? Because in lip, right, we're doing awesome scaling. I know Giannis is here too. They're doing simulation stuff. There's several options. Why did you go with NS3? Because this is not what the other project.

Yeah, I think that's the most asked question like why not shadow like um here. Yeah, the the thing is that yeah with shadow uh we kind of the shadow is great for just taking like for example real client implementation and just simply replacing the system calls and that way we can simulate the network. The thing is that we run the real binary and uh uh so we basically have as many processes is in the network as many u well as many nodes we want to simulate with an S3 approach we uh we basically run the entire subnet in a in a single CPU core. So we consider this

kind to be u more scalable and also we don't really need to have a real client implementation uh to test this. we only testing the one particular aspect one or just small part of the uh client which is the signature aggregation part. Um so we can really optimize for that. Uh so yeah uh in our test we were able to simulate like 5,000 nodes on a uh on a laptop. Yeah this this might take I don't know maybe um depends on the size of the subnet but 4,000 nodes it could take maybe 30 minutes or so but for smaller subnets yeah it runs faster. Uh but still it's possible to do in a single laptop. it doesn't consume as

much RAM as it would if you use shadow for the same number of um nodes. So yeah, but still we can we it is great. Yeah, we because we listen to suggestions like shadow for example has this right atlas database which has the latencies between the nodes from real world and we also we we parse this uh data from shadow and took it. So in our simulator we also use real world latencies to kind of have uh the very close environment to the simulator. Also um yeah it's still we still simulate CP and UDP transfer. So things like TCP congestion if we observe them in real network like if all uh participant can send their message to one exact one the

same um uh aggregator for example then we might end up with CCP congestion in our simulator would actually have the same behavior that's kind of in contrast to something like maybe 3SF mini uh that's uh well it checks the algorithm part but it doesn't simulate the or the networking transport as thoroughly as um NS3. So yeah that's that's why but yeah we open to suggestion here if we can actually try to use shadow as well but for now we thought yeah three actually makes sense here. Yeah thanks question.

Yep. So I haven't followed what studies you did but what are the challenges that you that you've seen at that layer like um I don't know with regard to the topology the different topologies or the protocols or the cost of sub settings any any take-home kind of uh results um yeah so basically what we observe is that uh what challenges well we basically comparing different topologies obviously the direct topology that uh I showed previously was the fastest But again it's kind of has certain assumptions that we need to consider. Uh we notice that for example cos actually runs as fast as grid for relatively small number of uh nodes in the subnet.

For example, here we have just 64 nodes. But if this number grows, the um uh for for the grid topology actually if we very fast signature verification time then the time of aggregation stays more or less the same for grid topology in contrast to gossip because in gossip we kind of have starts having more uh hops between communic for communication. Um yeah well there there there's still few things that we need to improve here for scalability u uh of the simulation uh just uh we want to reduce like the if the challenge with implementation was like if we have

if if we put if if we have for example if we use MPI and we run and we have a lot of between process communication then this really slows down uh simulation. Uh so uh but if we can avoid this for example we don't need to put all local aggregators into the same topic so that they don't really talk to each other but they rather speak directly to global aggregators then simulation runs much faster. Uh so yeah we're trying to implement this thing for example. Um so yeah uh I don't know the main challenge is well the basically thing is that we we have to just agree on certain assumptions like which topology we should use and then yeah uh with this framework I believe it's easy

to implement and check the assumptions. So we just hope that this would give kind of some tool for uh cryptographers just to check their uh assumptions like if we use for example this snark scheme with this verification time with this n proof uh what effect this would have like what would be the peak uh traffic consumption for different nodes and whether we can afford this uh for our nodes. Yeah. Yep. Yeah. uh basically do you simulate the latency uh like subnet and between subets or just between subets like what is the assumption?

Yeah, we simulate latency between any pair of node uh for communication. So we just take the right at database which has real world data for latencies between nodes around the world. Well, it has just around 2,000 nodes, but we extrapolated it a bit this database so that we have for our test scenarios where we run for example 5,000 nodes, we still can use it. Uh, but yeah, we run it we have latency between any pair of not only within subnet but also between subnets to global uh networks as well. Yeah. Yeah.

Okay. If that's all um yeah, I'll be here. So, feel free to approach me if you have any suggestions or questions. So thanks. Thank you.