A Hybrid VDF Prover - Benjamin Wesolowski

Thank you, sir. I'm going to talk about a hybrid construction for VDF provers. So, a hybrid between two previous provers that were already mentioned this morning, which we'll call the the Wesolowski prover and the Pietrzak prover, which I'm going to present in more technical details than what was just briefly mentioned in previous talks. Um so, first, as it was already said, it's a scheme that works in a group of a known order. So, we're going to fix a group G.

I'm just going to write it G, but imagine an RSA group or a class group, whichever you prefer. And um basically, the VDF is a sequential sequential amount of squarings. So, the input of your VDF would be an element G from the group, and then you have to square it T times until you obtain the final element G to the power 2 to the power T, which is the output of your VDF. So, you could just pick that as as your VDF, but then the problem is can you efficiently verify that the output has been computed correctly? So, say you're given a pair G and H that Alice claims is the out is H is the output of the VDF on input G.

Um can anyone verify this claim without having to recompute everything? So, can can Alice convince the entire world that she did the computation properly without having everyone recompute the whole thing cuz it takes a lot of time. So, here's the problem trying to solve. Alice wants to prove that H is the correct output. And the way it's going to be done is thanks to some auxiliary proof.

So, Alice, when she's evaluating the VDF, not only she's exponentiating G T times to obtain H, she's also computing some kind of proof, which is um a helper for everyone else to verify that the computation has been done improperly. We will call this pi, the proof. And now given the triple g, h, and pi, anyone can efficiently verify that h is g to the power 2 to the power of t. So two mostly two methods have been proposed to to provide efficient proofs of the statement. Uh one which I will call the Wesolowski prover provides very small proofs pi.

So the proof is essentially one element from the group g. And the verification is very efficient. It's going to be two small exponentiations in the group. Um but computing the proof pi will take a little bit of time. It's going to add some overhead to the whole VDF computation.

So it's not going to be as long as the VDF computation itself. So you're going to have to do uh t sequential squarings to compute your VDF and then you're going to have a little bit of extra work which will be around maybe 10% of the time it took you to evaluate the VDF. 10% can be a lot. We're going to maybe reduce that. The second um construction proposed by Pietrzak uh proposes proofs that are longer, around 40 times longer for reasonable parameters, and the verification is also slower by the same order of magnitude.

Uh but computing the proof pi is extremely efficient. It adds pretty much no overhead. So you do your VDF computation, you do your t squarings, and then the proof comes pretty much for free with a negligible cost. Can you compare the sort of the space requirements for generating the proofs? So uh for generating the Pietrzak proof efficiently, you're going to need square root of t, around square root of t uh memory.

Um and for the Wesolowski proof, it's more uh tricky. It depends on how fast, how optimal you want your prover to be. Uh you can get s- pretty close to the best speed up also with square root of uh t group elements. And you did this all at one You can't do it like sort of streaming. Like you need square root T elements at some point in the Yeah.

Yeah. Yeah. Yeah. Yeah, it's a square root T precomputed values. So, uh values that you've encountered during the computation.

I'm going to say a bit more on this when we go into the technical details. Um so, our question and our real question is, can we get Can we get somehow the best of both worlds? Can we combine these constructions in a way that we get small proofs, efficient verification, but also computing the proof is fast? Um for To simplify the presentation, I'm going to present everything in an interactive approach. So, originally we say we have Alice that wants to evaluate the VDF and convince the rest of the world.

In an interactive setting, she just wants to convince a verifier Bob, and they are allowed to interact. Um this will be simpler to present, and then you can use some standard tricks to remove the the uh interactivity of the scheme and get some non-interactive VDF. Um so, first the uh Wesolowski prover. So, presented in this interactive setting. So, it's a discussion between Alice and Bob.

Alice claims that the pair GH satisfies H equals the correct output of the VDF. And now there's going to be an exchange between Alice and Bob. Alice tries to convince Bob that it's correct. So, it's going to be a challenge response exchange. The challenge will be a random, rather large prime number L.

Large means um not as large as RSA parameters, but something like uh 100 bits or 200 bits. So, Bob sends this random prime number to Alice. Now, Alice is going to compute uh the Euclidean division of 2 to the power T by this random prime L. So, you get that 2 to the power T is the quotient Q times the random prime L plus some remainder. And Alice sends to Bob the proof pi, which is the element G, raised to the power Q, the quotient.

Now, Bob can easily compute the remainder of this division by L, which is R. And then he's going to accept the proof if this equality is satisfied. So, the proof pi to the power L times the element G to the power the remainder equals H. So, it's very easy to see that if everything went correctly and everything everyone did his job honestly, then the equality is satisfied. You just have to replace pi by G to the Q, and then you see that you get G to the power the Q times L plus R, which is just G to the T.

So, then it's correct. It's a little bit more tricky to see that it would be difficult for Alice to produce a proof that satisfies this equation if the initial statement is wrong. So, I'm not going to um go into the the security reduction, but we can say something like if Alice is capable of producing misleading proofs, she's able to solve some supposedly difficult problems in groups of unknown order. So, this is the interactive version. You're going to make this non-interactive by uh replacing Bob by a hash function.

Um and Alice to provide a non-interactive proof is will just pick the prime L to be the next prime of some hash of everything that is in the input of the protocol. Yeah. The number of rounds will be of your interactive proof will be T. Uh no, this is this is the entire proof. One round.

Yeah. Yeah. I think that this has good soundness. Hm? I think he's asking about the soundness of the protocol.

He says it has good soundness. Yeah. Yeah. The soundness error is very low. You only have to repeat once.

Yeah, you have Yeah, exactly. You have to You have to repeat only once because the soundness is very low. It's very good. Um So, just to sum up the construction in a non-interactive fashion, so if Alice wants to evaluate the VDF on input G, first she's going to compute H by two sequential squaring. This is the slow part.

And then she's going to have to compute the proof. And to do so, she's generating uh the next prime of the hash of everything she computed. Then she's going to compute this uh Euclidean division and compute the proof pi, which is G to the power the quotient. And the output of the the VDF is the pair H, which is the actual output, and pi, which is the proof. So, we need two group elements.

Yeah. I think practically it might make more sense to just hash GHT and the nonce and then send the nonce along cuz then uh the verifier only has to do one run out of the check. So, you can have GHT and the nonce until you hit a prime. Yeah, yeah, yeah. Choose the nonce freely.

Yeah, true. Then So, the question is you can uh you can have a nonce in the hash so that the nonce uh necessarily gives you a prime number, and then the verification doesn't need to uh compute the next prime. Yeah. Um So, you get uh a small output, only two group elements, and a fast verification cuz you essentially have two small exponentiations in the group. Now, the big question is how can you compute this proof efficiently?

Because it's uh G to the power Q, and Q has uh a pretty bit big bit length. It looks like it's going to be as expensive to compute pi as it was to compute H. We want to go a little bit faster. So, what are the main methods to compute pi? So, the trivial method would be to just do uh a long division to compute your quotient Q, and then you compute pi, which is G to the Q.

But this will take essentially time and space big O of T cuz uh Q is of big O of T bits. Uh so, it's going to take a while and a lot of uh of memory. So, first you have a no memory variant. If you observe that to compute your exponentiation pi to the Q, you are going to you're going to use the bits of Q one at a time. So, you can just instead of computing Q at the beginning, just compute it on the fly with this formula, which gives you the bit the binary expansion of Q.

So, now no memory, but still time big O of T. Now, there are faster variants if you use some precomputed values. So, uh when you're computing H, which is G to the 2 to the T, you encounter a lot of powers of G on the way. You encounter all the powers of the form G to the 2 to the I, where I is between 0 and T. So, you can store a bunch of them, and they are going to help you uh in computing the exponentiation by Q much faster.

So, if you store around square root of T intermediate steps, you can compute the proof pi in time essentially uh 2T divided by log T. So, uh here's the first challenge. Can you do better than that? The the problem can be expressed very easily. It's just uh suppose you're given a bunch of precomputed values of the form G to the 2 to the I, and then you're given a random number Q of T bits.

How fast can you compute uh G to the Q? So, with the current methods, you can go as fast as T divided by AB, where AB are any two parameters that you want. Um No, sorry. Using T divided by AB precomputed values, you can compute uh the exponentiation in time T divided by A plus B times 2 to the A. So, then you can tune A and B to minimize this, and this is how we find this uh um possibly 2T divided by log T run time.

So, our first question is can you go faster, and the a second, can you go well, maybe as fast, but with less precomputed values? This is a pretty fun uh pretty fun challenge if you like to if you like all kinds of tricks to do very fast computations. So, now uh the second the second prover is a Pietrzak prover. Still, I'm going to present it in a an interactive setup. So, the idea behind the Pietrzak prover is you take a recursive approach.

Uh Alice wants to prove to Bob that H is the correct output for the VDF. And you observe that uh the output of the VDF is essentially you take a you take T squarings. So, it's a long sequence of squarings. You can cut the sequence in the middle. And uh then you have two sequences of half the length.

And the idea is uh can Alice prove simultaneously the two uh pieces of the path. Can you she prove simultaneously that G' prime, the value in the middle, is the first value raised to the power 2 to the power 2 over 2? And that H, the last value, is the middle value raised to the power 2 to the power T over 2. Okay. And um if she can prove both of them simultaneously, you can take a recursive approach and divide by two the length of what you're trying to prove at each step.

And in fact, you can by using some random linear combination of your two equations that you're trying to prove. So, to obtain a random linear combination, we're going to let Bob choose how to combine them. So, Bob chooses a random integer R. And then we consider the two new elements G1, which is G to the power R times G' prime, and H1, which is uh G' prime to the power R times H. And now the statement that Alice is supposed to prove is the linear combination of these two statements.

Here is it. Recursive things, you have to store a bunch of values. And essentially, in the end, you can see that by storing square root of T intermediate values, the whole proof can be computed in square root of t group operations. So, the square root of t group operations it's uh totally negligible next to the bigger of t cost of computing the VDF. So, the proof comes almost for free.

So, computing the proof is very efficient. But, uh the proofs are longer. All right, because each round of the of the of the of the proof every every recursive round, you increase the length of the proof by one group element. So, in the end uh the proof consists in uh around log of t group elements. So, for realistic parameters, log of of t will be around 40.

And if you're using an RSA group of 2,000 bits, in the end you get a proof that is around 10 kilobytes, which is a bit a bit more than what you would like. Um so, now you can try to combine the two approaches and get smaller proofs uh that are easy to compute. So, the hybrid construction is pretty straightforward. It's not so difficult to figure out. Uh still same problem, Alice wants to prove the statement to Bob.

Uh they can first do a few rounds of the Pietrzak prover. And after k rounds, they end up with uh proving a statement of the form h prime equals g prime to the power 2 to the power t divided by 2 to the k. Because each round divides by two the length of the statement you're trying to prove. So, in the end you have a length of t divided by 2 to the k. So, each round divides by two.

And at the end you have this kind of statement to prove where h prime and g prime are not the same as the original h prime and g prime, though. But then, instead of uh continuing with your Pietrzak prover until you reach a thing that is trivial to prove, you stop there and you use a Visolvsky prover, uh which can produce a proof for this statement, which is only one group element, and can be computed in time bigger of the length of the statement t divided by 2 to the k. Or faster if you're trying to use some optimizations with using precomputed values. Okay. So, how how how efficient is it?

So, if you're using k rounds of PHK and then Wesolowski, each round of PHK adds one element to the proof. So, in the end you have k plus one group elements. So, that's the length of the proof. And now, how difficult is it to compute it? So, we can neglect the cost of the PHK rounds cuz they are very efficient.

And if we look only at the cost of computing the final Wesolowski proof, it will be bigger of t divided by 2 to the k. So, you can tune your parameters like it like this depending on how fast you want to be. You can go faster by having longer proofs. So, it's a trade-off. Now, you can use some optimizations using precomputed values for the Wesolowski proof.

And essentially, if the number of rounds you consider it a constant, then the cost of computing the Wesolowski proof is essentially bigger of this fraction there. When I say k a constant, I mean that in the bigger you have some dependencies in k. They're constants in the bigger. Um So, why is that? Why having a too many rounds will be a problem.

Um It's because to compute the Wesolowski proof, say for the statement h equals g to the 2 to the t as fast as possible, if you want to use all the optimizations, you need to use the precomputed values of the form g to the 2 to the i. And these are readily available. You encountered them during your initial computation. But now, once you've done a few rounds of your checks proof, you don't have G and H anymore. You have H prime and G prime, which are new.

So, you need to update all your precomputed values. So, if you have a lot of precomputed values, this will be very costly to update them all. We can do it. We can transform all the precomputed values of the form G to the 2 to the I into G prime to the 2 to the I, but it comes with a cost. Um essentially, the computation that you have to do is something like this.

So, this is another challenge. Uh try to compute this as fast as possible. So, you're given K integers R0, R1 up to RK - 1. These are the random numbers that are issued by Bob in the interaction. And then you're given 2 to the power K group elements C0, C1 up to uh C uh There's a typo there.

C 2 to the power K - 1. And then you have to compute this big product, which are product of It It's the product of all the values Cn raised to the power uh products of Ri's, where you pick only the Ri's where the uh ice bit of n is 1. Now, if you can compute this super fast, then you can update all your precomputed values super fast. So, this is another challenge to do this as fast as possible. Um currently, uh we know how to do this in time 2 to the K minus 1 uh exponentiations by Ri values.

Plus as many uh group multiplications. But it's not clear that this is optimal. Uh so, can you do better? Or or can you like prove that it's optimal somehow? Uh that would be interesting.

That's it. Yes. So, for your for the original Wesolowski proof, not the hybrid. So, you're taking 2 to the T and then you're doing the remainder 2 to the T equals QL plus R, and you're worried about the bits of Q. We can control the size of Q by making L like just big enough so that Q's powers are like much less than T, like square root of T.

So, can't you just use this to control the number of squarings you need to do? Uh you mean Like so here you're worried about the fact that for Q, like computing G to the Q is like expensive, right? Yes. don't we just control the size of Q by controlling the size of L? Okay, so the question is can you if I understand properly, can you make Q uh smaller by choosing L bigger?

we know how to make a commitment for like 100% Uh except they are really like different orders of magnitude. Uh L will be You don't want Bob to generate a prime that's pretty much as long as half the length of 2 to the T. That would be an enormous number. I think it's good to give numbers. L is like a 128-bit prime.

I see. Yeah. And 2 to the T is 40 million bits or so. I see. Okay.

Yes. And so the wouldn't the sort of in terms of efficiency a similar approach would be maybe to compute uh Wesolowski proof for the first half, then you know, from half to the 3/4 and so on and so forth, cuz these proofs are going to finish before you finish the Yeah, this is what Justin referred to as the iterated Wesolowski prover. So, at least I mean, there uh it seems to have the same proof size and you don't have to uh well, at least you don't get the overhead of computing I know the overhead of computing uh Kristol's proof is small, but at least you you don't have it at all because you most of your proofs will finish before you're done with the computation. Yeah, so the the is uh can you like do a Visolosky proof for say the first half and then a Visolosky proof for half of what remains and then something like this? Uh using the fact that computing the proof is anyway shorter than the entire the the whole computation.

Uh I guess this is an approach that we explored, yes. And one of the possible problems will be that uh it's unclear at the moment how much faster it will be to compute the proof uh be- cause here we give counts in terms of number operations in the group, but multiplications will be maybe twice as expensive as uh squarings. And you need to do a lot of multiplications in your proof, but you don't need to do any multiplication in the VDF evaluation. So you could get maybe a factor a new factor two uh in the time it takes you to compute the proof just from the fact that you need to do multiplications instead of squarings. But maybe if if uh if the multiplication is fast enough compared to the squarings, maybe that's an approach that uh should be considered.

Well, yeah. The nice thing I'm wondering whether then you can also once you've computed the proof for the first half, you can throw away those values. That probably doesn't save too much. You can throw away the the intermediary values for the first half. Something like I mean again, I don't know much about it, but just going on what Benedict is saying, you can compute Merkle trees with order log space.

You You keep accumulating and you can always store just log number of values at any point. Yeah, I guess. Possibly you could do this in log space. Again, I'm just speculating here. If you had sort of some way of accumulating these proofs and discarding values that you don't need then Yeah, or I guess that's um many directions to that remain to be explored.

Yeah, work for this afternoon. Yes. Yeah, so the question is it's not Bob's job to generate a random L because we're going to use a non-interactive version anyway, so it's it will be Alice's job. But in any case generating an enormous prime will be so costly. You cannot and the verification becomes expensive if L is too big because you have an expression of change an expression by L to do.

Yeah. I think it gets to like a really minimal advantage to to pick a big L because they're like Q is two to the T bits and then you subtract to that the bit length of L is going to be extremely close to you two to the T unless you pick L to be outrageously big. All good?