Filecoin Filecoin Liftoff - the Main Event, 22 Oct 2020

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: Filecoin Proofs and Upcoming Improvements

Description

In this session, we hear about the development of Filecoin proofs and some of the exciting improvements planned in the coming months.

Join us for Filecoin Liftoff Week, an action-packed series of talks, workshops, and panels curated by the web3 community to celebrate the Filecoin mainnet launch and chart the network’s future.
https://liftoff.filecoin.io/

Events take place all week, October 19-23, 2020. #FilecoinLiftoff

For more information on Filecoin
- visit the project website: https://filecoin.io/
- or follow Filecoin on Twitter: https://twitter.com/Filecoin

Get Filecoin community news and announcements in your inbox, monthly: http://eepurl.com/gbfn1n

Chapters
00:00 Introductions
01:50 Sealing
10:44 Signatures
17:55 SNARKs
25:50 Next steps

A

Hello, everyone- I I'm really excited to be here finally have some time to actually talk about the things that we've done in the past months.

A

um Yeah, as mentioned, my name is dig um alfredo, uh whatever you like- uh and I work with protocol labs um here with me- are sean and kelly from supernational who have been collaborating with us for quite a while now, but especially this past month, to push the crypto and file client to the next level and to make falcoid really fast network.

A

So um without further ado sean. If you want to say some words about you, kelly.

B

Sure thanks radio, my name is sean gulley, I'm a co-founder here at supranational, where we focus on hardware and software acceleration of computationally intensive algorithms and of late. Our primary focus has been around cryptography operations and the blockchain ecosystem, and prior to that, I was at intel for about 20 years. As a principal engineer where I commented, some of these cpu features that we'll talk about today.

C

Excellent thanks sean uh yeah, my name's kelly olsen, I'm on the product team here at supernational and as sean mentioned, we're focusing on accelerating uh verifiable and confidential computing. So back to you, dig thank.

A

You uh yeah, as I mentioned, I have been with pro collabs for a while now over four years, and I've been focusing on the proof's implementation and so got to work with sean and kelly on this. So we're gonna look at three things today that we've worked on as the title hints at ceiling, signatures and snarks, and so let's get it started.

A

So the first big and the biggest thing that probably everybody who has run a minor so far is knows that there is a process called ceiling, which is the first step in proof of replication and you've likely also heard it. Maybe under the code name called pre-commit one, and it is the slow bus very crucially slow part when you onboard new sectors ceiling, is designed to be very computationally intensive, that that is what it makes secure.

A

But we end up, of course, um not wanting that everyone has to pay a high cost, but only as much cost as we really absolutely need to achieve our security, which is why it's crucial that the implementations that are out there are as fast as we can make them now.

A

The other part where it's really good if these implementations are faster, is that the difference then, between the host between the honest and the malicious miners becomes less because if all the honest miners already know the really good code and have it running, then there's slightly simply less room for malicious matters to improve on and as such, making the network more secure. We also really want everybody to be able to mine as easily as possible, so we really want this process to be as results.

C

A

Little take as little resources as possible, but I don't of course unfortunately still takes a lot of resources, but we've done a lot of work to reduce that and sean is going to tell you a little bit about what we're we've achieved. There.

B

Thanks yeah, so here you guys can see on the left hand, side a picture of what's called a stack depth, robust graph, and this is from a paper by um the great ben frisch at stanford from a couple years ago. That was the foundation for what what's in filecoin today and you'll, see these nodes and each node is represented by a 32, byte, sha, 256, digest and you'll see the red lines are the edges that represent base parents so- and this is all intra layer and then you'll see these blue edges below those blue edges.

B

They are inter layer and they represent what's called expander parents, and the idea here is that it's a very serial process. As dig said, where you've got a node that you compute, then you've got the next node and it relies on the previous node or the previous layers nodes, and so what you'll do is you'll concatenate the value of those nodes that the edges connect to into a into a buffer and then you'll hash it.

B

So the key point here being that the theoretical limit to this.

A

B

When all of the edges are kind of randomized and pointing to um previous notes, then you'll have whatever your hashing compute can handle. That should be what your theoretical limit is. So when we looked at what can we do with ceiling as it is? We looked in two places. One was all right. What's that theoretical limit for the.

C

B

And then two, where are some of these bottlenecks, and it turns out the bottlenecks mostly are in the memory reads. So what we did in terms of the process is, you know most of the miners.

B

Now when you generate the the graph you'll only do it once and then you'll cache it on your on your machine, so whether you're doing a 32, gig or 64 the executive deal you'll cache that graph for later use. So if you're sealing a whole bunch of sectors, you don't have to repeat that process.

B

So what we do is we we pull that that cache graph into memory. We pin it in there. um You gotta, lock it in there, so it doesn't get swapped out so that grab is always fresh in memory.

B

uh Then, when we look at uh the buffers we have we kind of map this current layer, and then we have another buffer for the previous layer, and so that's those are our three kind of working memory spaces uh to deal with it.

B

So we put some constructs into to make those efficient uh and then the next piece that we looked at was a sort of a threading, so we create one thread, that's doing all the hashing and then we create in this case we use two two threads for prefetching all of this previous node data.

B

So in this producer consumer model we create two threads that go off and run and do the pre-fetching based off of what's in that parent node cache, and then we have the other node, that's pulling them off of a ring buffer, that's shared between them and actually hashing them. uh So this whole process. We have another product in there that that tracks hey what? If what? If I was pre-fetching a node and it was it was too close, so the base threat was too close.

B

We tracked that and then the hashing thread can pull that in. So we found that to be like all right. Two threads with some with some tuning of some parameters was sufficient enough to read a head back, pulling out of memory or even off of disk into the localized cache.

B

uh Another thing we do in this case is: we also pin the process to a certain say complex, so in this case we're using the sha extensions that are in mostly the ryzens or amd core, so amd's set up in a complex where you'll have four cores in a complex with a shared cache and what we do is we pin the process to sit in that context. So you'll have maybe a your hashing thread and then you've got your pre-fetching.

A

Thread another pre-fetching.

B

Thread and they're all running tightly in this complex that all have a shared cache, so everything's, really hot, and so really it all comes down to. How fast can I hash uh be? Assuming all of the all of the data is uh is available, so we can just uh turn the page a little bit and then we can see just some of the results that we got here.

B

So we started off just using you know if you kids could use like lotus bench and things like that to see where it was before, and a lot of people were reporting in this four hour-ish range and by just doing a couple of these tricks. Well, we brought it down to around two hours and if you presume that the the graph is entirely serial- and there is no way to hash another node before you completely hash the previous node, then we are close to that sort of theoretical limit in general.

B

Amd can can hash at two cycles per byte, so we could take how many bytes are we hashing in the buffer? We could figure out how many cycles it takes based off of frequency, say you know about four or something gigahertz. Perhaps that two hour range is pretty close to about as fast as you as you should be able to to uh seal a graph. That's entirely serial, so yeah.

C

One thing I may add here that just may be relevant uh to the miners in the audience. Is um you know the amd processors today do have the special instruction set that makes uh hashing faster and they have sort of a custom accelerator within the cpu.

C

um That accelerator is going to be extending you know, expanding out into other both intel and also arm processors. But just one thing to sort of keep in mind is if you're looking to you know, do the ceiling as quickly as possible. You know at least today you're going to get probably uh the faster times using the amd processors because of this uh specific accelerator for the hashing yep.

A

uh Also a note we do have experimental arm support and I believe technically we actually do call the current arm instructions in most of the code. So I believe some some people already reported that they are also doing this hashing with on iron, with the sped up instructions, if you have an actual rm64 processor supporting those.

A

um If uh folks out there are running this and they're seeing times will be really interesting because we haven't done any larger tests on arm processors. So any any info that you can send our way and that would be appreciated.

A

All right, so I'm pretty good right, 2x, that's pretty good! Let's see if we can do better, so signatures uh signatures um most blockchains. Well, I'm saying most, I assume all blockchains um use signatures for signing their messages um or transactions, depending on the lingo falcon additionally uses signatures to also in its consensus process for for sending messages. We have two options currently available and one of them is bli signatures. uh The other is the classic site. Pk bls signatures are uh have the the big bonus for us that they allow aggregation and so in.

A

If you look at the block production in falcoin all messages that have been signed with a bls signature, they get aggregated by the block producer to a single signature, and so, if you verify the signatures for a block, you only need to verify the single aggregated signature. But that means you have to verify an aggregated signature, and so this is one of the verification methods that gets called quite heavily.

A

The other part is we use it in the vrf to generate the election ticket. It gets signed, there's a signature based on the private key of the miner. That is, mining. The block, and so any block validation also has to verify that signature when doing the block verification, and so you can see that every block that you need to sync and produce heavily uses these signatures, and so, let's take a look. How fast we have made and been able to improve on these signatures.

B

Right yeah, thank you. So when we look at signatures just in general, from a bls perspective, there were a handful of libraries that existed somewhere somewhat experimental. Some were kind of driven by researchers when they were getting this off the ground and there's a couple that are were pretty pretty good performance.

C

To begin with,.

B

But when we took a a bigger look at where the problems were, we thought hey. I think we could do a little bit better, and since this is new, this is emerging uh just for us. We thought hey. This is great, like foil coin's. Using this, this has been being pushed by other blockchains as well, so hey.

B

We should really do a a pretty nice library for this, so this is great, because this is the file going as the the first production blockchain that we've we've put this library into, and we created what's called blast, and this blast library is, is kind of comprised of a few different areas. One. We looked at some algorithmic approaches, and these are some of the more classical approaches to field and curve operations like just using montgomery multiplication.

B

Things like that. How do you represent points? Some of the endomorphisms and batch efficiencies are, are additional techniques that you could be used when you're dealing with a lot of a lot of different points, um and in this particular case you know for fall coins. As dave mentioned, these these aggregated signatures and and aggregate verification of a signature is anywhere where we were starting to deal with.

B

There's a there's a whole bunch of points here that we're going to have to deal because, at the end of the day, a signature just blows down to a point on the curve. um So we were, we were focusing on algorithms of that space. We also focused a lot on assembly.

B

So, given our background, most of our experience came from assembly coding on cpus, whether that's the x86 or arm, and one of the first things we saw when we looked at a rust, which was, which is what the pure sort of native rust, which uh filecoin was using before we were able to get a 3x performance improvement just by hand tuning the codes, so it wasn't compiled, but it was more assembly based.

B

I was using instructions like molex ad cx ato x for parallel carry chain, and things like that in in the in the very intensive modular arithmetic and then the last piece which actually drove a huge performance improvement. So as as you're saying like hey, I'm a miner, I'm generating a block, I have, I have a whole bunch of different signatures that I need to aggregate when you look at the actual operation underneath that that can be paralyzed heavily. So I could take a huge chunk of signatures. I could break them up into buckets.

B

I could feed them to a variety of threads and, as we talked about earlier, if you're talking about using an amd processor, as we know, those processors now come heavily loaded with a lot of course, and so we started to take heavy advantage of parallelization and it was on a very fine grain using lightweight threads.

B

So we saw that even in rust, we played around with built-in libraries with rust and decided to create a different thread pool associate associated with our code so that we could we could maximize the performance, especially over the long run.

B

So you could see on the on the next slide, what where we ended up getting as a result, so the the x-axis is the batch size. So it's considered, as you know, a single value would be a single signature and then so on. The left is aggregating signatures. So if you're a miner producing a block, now you you've aggregated, say all the way on the right hand, side would be say a thousand signatures uh and then, on the right hand, graph.

B

This is signature um verification, so I've got an aggregate signature and as part of that, I read signature, you need to. You need a whole list of public keys and a whole list of messages associated with it, so it also could be heavily parallelized, and so what we see is we're. You know we're tapping out in this. This 5 to 8x performance improvement range, so we were seeing that potentially 3x off the bat with some of the assembly optimizations that were made and some of the algorithmic opera optimizations and then by adding the threading.

B

We started to get that that much bigger boost so that the whole key point here is that we're trying to alleviate bottlenecks in the system. You know, so it allows you to decrease block times it. It gives you a little bit more room to transfer things over the network, which could be a little bit haphazard.

B

It can allow for more things in a specific block, so all told it really by expanding into these these bigger numbers. Now we can really scale scale file coin much greater, so I think we're pretty happy with the result.

A

All right: well, that's pretty.

C

A

Five to eight x right anybody, anybody think we can do better any way you want to do better than that all right. Let's take a look at the our third problem, um snipes or uh short for zk snacks, um so zk stocks uh have been around for a while.

A

Well, you know in crypto terms they haven't been around for a while, but in blockchain term I think they have been around for a while now um and they are starting to get more and more adoption by different systems um in order to improve what can be done in terms of computations off-chain but verified on chain, um following very early on decided to use this, to allow the proof of storage that we need to do to be verified by all participants on chain, and so we currently use this for the power app.

A

In order to make the commitment to the storage and to prove the correctness of the aforementioned seal, we generate currently 10 snarks. Well, the reminder generates 10 specs when they onboard a sector of 32 gigabytes and then for post. Both winning and window post generate a snark that gets posted on chain uh for every such post. So you can see that we generate quite a lot of snokes, but especially there's a lot of need to verify these snarks as everybody needs to verify the blocks that contain these snarks to get posted on chain.

A

So um we've looked heavily into snug verification as such, and so sean will tell you a little bit about what we achieved there.

B

Thanks eddie, so you know, as dave's mentioned this, the stark verification is a is, it can be a pretty big bottleneck, and I guess you know today already we're seeing thousands of snarks being generated by file coin a day, so anything we can do to speed this up once again helps helps impact scalability and helps improve validator performance.

B

So when we look at it, there's there's, as you mentioned, there were three different types of proofs that would need to be verified so that that winning the seal and the window post realistically, where, where the bottleneck becomes, is in this multi-scale or multiplication operation, and each one of the proofs has a different number of points that need to be multiplied and added together and you can see winning and seal are relatively small, but window is much larger and window is the thing that you're, you know, you're constantly being challenged.

C

B

This is a it's a it's a pretty common snark to be getting, and it's not just a one-time thing. This will be happening over and over and over again through the life of the the storage. So it was a.

B

It was a big area of focus for us, and so we looked at again that three sort of areas we're looking at the algorithm, we're looking at assembly code and we're looking at multi-threading so from an algorithmic perspective, the next the interesting thing about the snarks was we had some interesting opportunities here for pre-computation, so there's a verification key that was generated along with the the um srs, the structured reference string as part of the the parameter generation, the trusted setup. So these values are fixed for all time and we can pre-compute some things.

B

So there's some greeks! You can see that the formula is in the is there it's a little convoluted, but you can see we could do some precomputation on some of those greeks and then we could also pre-compute on some of those points and that that middle sigma function right there and we ended up using this fixed window. This eight bit fixed window, uh multiscale or multiplication operation and that dramatically sped up um their performance and another thing is these pairings? So there's there's not just the multi-scale. There's three pairing operations.

B

We combined the three pairing operations into into.

C

B

And we also would do those operations in parallel with the with the exponential multi-scale multiplication so that parallelism starts coming in and that that multi-threading, so we talked about the gros 16- is the proof system that they use.

B

We use the pairing and the exponentiation together in parallel, but there's another added feature that we had, that that helped significantly improve performance, and that was d serialization of these proofs, so as they get sent over the network they come in, we need to deserialize them and then, as as part of the validation responsibility, you're supposed to check hey. Are these valid points in the in the group. The elliptic curve group.

A

B

That's another expensive operation, we're able to paralyze that so between these sort of three four different buckets here, we were able to shrink it and dig on the next slide. You could see the the performance that we're able to get across the three, so uh you know on the big one on the window, which is happening every day. We've got the 12x performance improvement so that made something that was, you know a scalability potential concern and we shrunk it down a lot.

B

So this is great, so this means you know there could there's opportunity for more challenges or there's opportunity just to just to validate a lot more storage and challenge a whole lot more storage on the network, and similarly, we got 10x and 8x respectively for uh winning and seal. So again, this is all lightening the load on on validators.

B

um So we were also uh extremely happy with these. uh These performance improvements.

C

Yeah, I think one thing to add is you know the this work uh and the use of snarks is really groundbreaking here for filecoin, uh so sean mentioned, I think you know we're seeing uh at least eight thousand or nine thousand snarks being processed today by the the network, which, I think is uh you know unprecedented on on main net systems today right.

C

So this is a one snark every 10 seconds or something like that, and um you know, even even on some of the uh maybe more established blockchains we're not seeing this uh this sort of use of advanced cryptography. So it's you know, really groundbreaking work, and um you know I think this optimization work is going to be more important as uh snarks are, are more widely deployed by uh you know not only filecoin, but also other blockchain networks.

A

Yeah um one smaller to these things and when they will get deployed um so as as nikola mentioned earlier in the chat, the ceiling improvements are currently in lotus and at least most of them, and there's a link to instructions on how you can enable them. They're, currently still remarked as experimental until we have further wider testing, um the snug verification um and the uh the start, verification uh is coming soon. um It is currently partial you can currently also enable it.

A

um There is a use, fill blast flag that I believe we have some documentation, we'll post something later in slack and the phil proof's channel for details and the bls improvements are actually already deployed by default. Currently in lotus, they are only in lotus deployed. As far as I know, I don't know about fujwang and forest when they sit there.

C

But I know that they are deployed.

A

In the lotus, currently um yeah sweet all right, so the future, um so there's certainly a future here. This is not the end. This is the beginning now that we have made that anyway and in performance optimization, certainly there's still a lot to be done.

A

This is also called to the community. We really want your help and any ideas how crazy they might be. Some of the ideas that we had were certainly crazy, but they didn't work out. So that's nice send them over make prs.

C

A

Us know what ideas you have to make these things faster: um it it just benefits the whole community. If the default implementations get better and better and people can learn from this code, all the code that we've discussed so far is definitely it's already open. It's just not necessarily integrated already in the chains.

A

um Some of the topics we hope to be looking into where I already started looking into for the next are snug proofing, as as we mentioned earlier, is block snipe, proving is still pretty heavy for all miners, um so making that better and faster. It's definitely going to help the network.

A

Syncing syncing is still not as fast as we would like it to be so improving that in all areas is going to be a focus, and then bdfs are the next level we're still looking into bdfs, and especially supernational has been working on on them for quite a while and hopefully at one point we will have a vdf that can integrate into falcoin so definitely stay tuned there yeah. Thank you.

A

Everyone kelly sean. If you want to say some last words.

C

I think that's, I think, that's great, um you know certainly feel free to to reach out to uh any of us here on on the panel today. If you have any questions, you know always looking to, uh uh you know, add value or expertise. If there are questions that you have for your projects or your deployments.

B

Yeah- and I just want to thank the the protocol- housing filecoin, guys and the whole team- I mean it's been great because you've been super receptive to just improving, and so you guys, every single day are doing your best to improve the protocol and improve the network improve the code base solid. So I mean it's a super solid project with a great team, so we're.

A

B

Ecstatic to be a part of it.

A

Yeah, I want to extend that. Thank you, supernational. They have been amazing partners and they have been teaching us uh at least me- and I know some of my teammates day in and day out and how computers work and how to make them do what you want a little bit faster.

A

So thanks so much.