VDFs and Filecoin - Jeromy Johnson

Cool. So, hi. I'm Jeremy. I work at Filecoin as mentioned. I'm going to give a short presentation on how we're thinking about using VDFs and how exploring different ways that we might do that in our protocol.

Um so, there's three main areas of exploration here. There's we have two main proofs, proof of replication and proof of space time, which both have timing assumptions. Um and so, currently these are like kind of dependent on VDFs in in a way. And then we have expected consensus, which is our consensus algorithm, where we're exploring the use of VDFs to improve security, but it's not necessarily needed. So, proof of replication, for those who are unfamiliar, is a slow unique encoding of some input data.

Can be any data. It protects against deduplication attacks. Um this is important when you're like giving people some resource based on the number of replicas they have. And in the context of the proof of space time, this protects against what's called a generation attack. The way it kind of works is you take a file, you break it up, put it into and you map it onto a graph.

You encrypt it based on the edges of the graph, which is an inherently like sequential operation. And then you use the outputs of that to create your replica. Um it's kind of like a CBC mode encryption, except more robust against removing random nodes in the graph and regenerating things. And in order to slow this down, you can add more layers to the graph and make it even more sequential. Um And so, the main the main thing this helps the timing assumption here helps protect against is what's called a generation attack.

So, imagine you have an honest person and an attacker and you have some verifier. The verifier sends a sends a challenge to each person. The attacker doesn't have the data. So, they haven't done the the seal, they haven't made the replica, but the honest person has. So, when they receive the challenge, the honest person can immediately process the challenge.

Well, the attacker has to start doing this um slow encoding operation. The honest person can respond immediately, while the attacker still has to continue doing this slow, you know, effectively sequential operation. They finish, they can do the thing, they can send it back, and it's some very noticeable amount of time later, and they get caught. So, what are VDFs? Yay.

Um Basically, this whole process is slowing forcing you to slow down an encoding such that if you're trying to recompute the encoding on the fly, you get caught. Um And so, it takes some inputs, produces an output after a prescribed time. The same inputs always produce the same output. Um and the verifier can efficiently check that it was done correctly. Um this is done with some like SNARK Merkle proof magic, um which is actually the fast part about the whole thing.

Um and so, that's kind of one way that we're like it is a VDF, and you can keep it you can prove you can slow down the um the attacker even more by this graph here is actually each of those edges is a um an encryption operation. And what you can do is the key derivation function for each of those lines can itself be a VDF. And so, you can take it as an input, run it through a VDF, like if we have a nice fast, you know, exponentiation VDF, and then use that as the encryption key for the next node. So, now in order to encrypt node seven, you have to encrypt two, five, and six. In order to encrypt six, you have to encrypt four, and then that requires five and three, and which requires one.

And so, in order to re-encrypt any random node in the graph, it requires a long sequential computation. Um so, that's one of the things. The next one is a proof of space time. So, this is kind of like the other side of this. So, this proves to the verifier that some known data was correctly stored over a given period of time.

Uh and so, the main thing we're trying to prove here is that the space that you're claiming to have wasn't reused for some other purpose during the time period that you're proving it to us. Um has a non-interactive succinct output it's non-interactive and has a succinct output, and it must not be computable too much faster than the expected duration. Kind of sounds familiar. Um so, the way this briefly works is you have some time period, you have some input challenge, and then the the the prover takes that challenge, does some like Merkle proofs on their entire storage, then takes the output of that into a VDF, slows them down, does some more challenges, another VDF, another VDF, you get it. Um keep doing that, and at the end you gather all this together and you have to compute a proof, you know, we SNARK it up.

Um And then you submit that to the chain. And so, what what we're doing here is we're trying to make sure that like ideally, this entire thing would just be these challenges, like entirely consist of proving to me you have random pieces of file. The problem is you can't prove that in a SNARK efficiently. And so, we lower the number of actual challenges that you have to do and replace that time with something that takes a verifiable amount of time. And so, you can lower lower that a bit because these challenges can be done really arbitrarily fast and are like almost cacheable if you have enough space.

So, adding this slowness in here. Um the attack is if somebody can do this much much faster, they could take and if they could do the entire thing in this amount of time, then they could wait until the very end, regenerate all their data, and then just do it here. And so, for the rest of the time they could be reusing the space for saying they have all sorts of other storage, which is bad. Um and so, what we can also do here, instead of having each of those blue lines be a VDF, or in addition to those blue lines being a VDF, who knows, we could have a random beacon that is made with constructed out of VDFs and use the output of the random beacon at each step to reseed these. So, this all this means that if you have an advantage, you can't you can't complete this early.

You have to wait at least until the very last random beacon element is known, and then you're able to complete it. And so, combining this with a random beacon basically allows you to prevent an attacker from going arbitrarily fast. Um This whole process does look a lot like a VDF. There is some fixed input that produces a known output. It's verifiable um and takes some prescribed amount of time.

And internally is comprised of many little pieces that are meant to slow things down. Um Yeah. So, that's kind of like the main our main like use of VDFs in there. Yeah. Yeah.

So, this would be like the the Randa random beacon that um that is proposed by Ethereum people, you know. Um Or some other mechanism. Yeah. So, here's the interesting thing. Given a sufficiently large advantage, um let's say that I have really really really fast computation the of all of this all this work, I could just wait until here and do it all right here.

Um obviously, that's really really impractical, and the expense of doing that and like the hardware required to do that would be absurd, but just keeping this VDF in here um makes that much more expensive and makes it much more unlikely that you'll be able to pull that off. And it's it's not strictly necessary, but it does like this is this is a game of increasing the cost for an attacker. That's all this is. We're just trying to make an attacker have to spend a lot more money to beat us. Um like the whole VDF thing is that.

Uh so, then yeah. Then the third the third like piece we're looking at is our consensus mechanism. Um which elects on expectation one leader per round, which is why it's called expected consensus. Um includes all blocks in the previous round as parents. It's uh and it's kind of like a proof of stakey um consensus protocol.

And one the thing we're exploring is a lot of these protocols, you can look look into the future to see the randomness generated like if if you win this block, if you win at this block, if you win at this block. And a way to prevent people from looking in the future in these is just forcing the computer VDF between every block. Um this is only more useful if you have a like a very strong VDF because this is like 30 seconds, and if an attacker has a 10x advantage, it's uh it's not super useful. Uh like a low Amax, sorry. A what?

A low Amax. Yeah. So, if we can be more confident that the the lower bound is a lower number, then this becomes more useful. Um you also have to worry about network propagation to like make sure your block time is right. Um Uh Uh it go it it changes a lot.

The Ethereum people say they're targeting a 100x um with the ASIC that um Supernational is looking to build, we're targeting 10x uh 10 Amax. Um So, it's it it's unclear, but that's like more research to figure out what that actual number is. Yeah. Yep. And so, instead of running a VDF between each of these, we could also use a random beacon.

Um The random beacon means that you can look So, depending on how you construct it, the random beacon has the similar problem where you could um collect all these things into the past, and then you could since all the all the randomness is now known in the past, you could reconstruct a chain depending on your algorithm, like depending on how you you allow people to do this, you could reconstruct the chain um from the past. And so, if you force enforce the VDF between each block, then you wouldn't be able to easily go back and just recompute an entirely new chain cuz you need the randomness. And I think we talked about this last night and you had a point about if the chain does influence the beacon, then that won't work. So, the beacon if you're using a random beacon like this, you need to make sure there's some receding period. Also, isn't that a little bit circular in a sense?

Like, the beacon has to come from somewhere. Yeah. We just have one. It's just one beacon somewhere, you know? It's great.

We could take We could put these VDF hardware on satellites in space and just like throw them out there and they can beam back random numbers. It's great. Just don't worry about it. What are we doing here? Um So, yeah, that's um that's what we're thinking.

And if you have any questions, let me know. Otherwise, let's talk later.