QROM Grover Barrier

Transcript

Um, hello everyone. Uh, I'm I'm C. I uh, I'm going to talk about proof of work and uh, random oracle specifically um, and their kind of post-quantum implications. Um, in particular this is like work in progress. I am not going to claim that I 100% understand everything. Uh, so feel free to ask questions and if you spot any mistakes, feel free to stop me. Okay, great. So, I'll start with uh, introducing defining proof of work. What they are.

Um, a proof of work is a proof system uh, where we have a solver and a verifier, something that we're super familiar with. And the interface is like um, the solver is going to receive a challenge, usually sampled by some outside party, X, and then it's going to give a solution Y to the verifier. Sometimes the solution also involves a proof attached to the solution to help the verifier with verification. And then at the end the verifier decide whether to accept or reject.

Okay? And uh, I'm going to focus specifically on hash-based proof of work or by saying this, what I actually want to do is just to introduce random oracle. So, this talk is going to be fully in the random oracle model. Okay? And uh, uh, specifically the solver and the verifier, they're going to have oracle access to the random oracle or the hash function. And um, kind of the theoretical model we're assuming is that the solver is going to ask T queries to the random oracle model, while the verifier is going to ask much, much less number of queries to the same random oracle model. So, we have 16 verification.

Okay? And uh, um, there are kind of three very, very important properties we care about um that we want proof of works to satisfy. So, I'm going to start with the first one that I hope everyone is familiar with, the proof of work being Bitcoin friendly. In fact, Bitcoin is using like our most uh familiar form of proof of work, the pre-image proof of work, that I'm going to explain uh and present in a second. But basically, for a proof of work to be Bitcoin friendly, what we want to ensure is that one a proof a solver is able to make partial progress.

Meaning that we know that by definition, the uh kind of the given solver is able to give a satisfying or an accepting solution to the verifier after making capital T many queries. Right? But at the same time, we want to make sure that if I am the solver, I have enough computing time to make little Q many queries, then I'm guaranteed that roughly I made Q over T progress in terms of getting a solution.

So, that's abstractly what we want for a Bitcoin proof of work uh or Bitcoin-friendly proof of work to satisfy. Okay? Do you agree with that? >> Why? >> Uh that that's how like uh my understanding is that's how mining works. >> But what about the difficulty adjustment that comes with >> Yeah, exactly. >> Well, I think it's just artifact of Bitcoin proof of work that kind of how to measure the contribution to the pool. Because well, if there are no pools, no one would care what's kind of how your probability changes.

Maybe if uh it's enough to have uh well, if uh probability becomes one after you make uh omega of Q queries. >> Uh everything in the expectation is true that if you're like extremely lucky, then you can get the solution with one query. But here we're talking about expected amount of work and expectation, what I want is after making some proportion of the effort putting into getting the solution, then I get the same amount of rewards that I'm supposed to get.

So so I'm not saying that you cannot There is like the probability of solving everything with one query is is zero. I'm not claiming that. But in expectation, to solve the the Bitcoin proof of work, usually I need T many queries. And I want to make sure that if I spend partial work, I get partial reward. >> To get partial reward To get partial reward, you don't have to have a linear growth of probability. Right? >> You >> In practice, it's it's easy to construct schemes that don't have linear probability but you don't want that because you don't want, for example, centralization um

uh due to kind of people who can afford over a certain threshold of hash power having a disproportionate advantage over people who have a relatively smaller amount of hash power. So it's it's a decentralization requirement. As well as the as I said before the um it makes the difficulty adjustment work better. We we considered this when we were designing the proof of work for Zcash. >> Thank you. >> What are the two lines? Why is there a dash line and a red line and they're not the same?

>> Uh the the dash line is just the slope. Um and the it's like one query gives you roughly like one over T amount of reward. >> Okay, but why is the red line not straight? >> It it doesn't have to be. It it could be, but it doesn't have to. >> Uh-huh, okay. >> Okay, any other questions? Okay. So second property that we call it grinding resistant and we can first introduce the property and explain why it's called grinding resistant. So basically, what we have want to make sure is that okay, finding one solution takes T queries.

How about finding two solutions, three solutions? And I want to make sure that finding K solutions cost approximately in expectation K times T many queries. And why do we want why do we care about this specifically? SNARKs. And specifically this is important for what we our favorite transformation, Fiat-Shamir transformation. So, just a quick recap. Consider an interactive proof where the prover sends the first message and the verifier pick a random challenge and then the prover replies to this random challenge.

And then with Fiat-Shamir, meaning that we use a hash function or we use random oracle to compute the verifier challenge according to the prover's first message. Okay, that's Fiat-Shamir. And then one kind of now we're in the in the I don't I'm I'm so sorry. I really don't know how this works. Uh Yeah, good. Okay. So, um kind of the the application of proof of work in this context is really that we want to prevent any adversary from doing this specific attack, which is brute force or like find like a way to

find the first message so that the resulting hash give you a verifier randomness that you can basically fool the verifier. So, if for example, I don't have any proof of work in the Fiat-Shamir, then here the prover is able to is able to afford like a polynomial prover adversary, so able to afford like going over like polynomially many first message to find a verify randomness that I can actually cheat.

Yeah. >> I'm really sorry. But that doesn't it somewhat contradict actually the previous reason? Because if we want the adversary to have like as few chance as possible up until the very end, we would rather benefit non-linear growth. >> Uh that that I'm not sure I understand the question. The this property and the previous one you're saying that they're contradicting each other?

>> Yeah, for example, suppose you have growth not linear, but say quadratic. And in this case the probability the chance to to to win in the first attempt is lower and in the second is lower and third is lower. So the adversary actually has no hope to win up until the very end of kind of this workload. This if we had this situation, this would further demotivate the adversary to to cheat here because with quadratic or any other way of non-linear growth of of probability of advantage, he would have much less chance to win.

So that's why I say it's something like >> to win? Like what's the adversary's goal in your situation? Like in your setting like >> Adversary goal to pass pass the check to to hit the orange box. >> Yeah. >> And if you have linear growth, then adversary has non-negligible chance to win in the kind of first attempts. Right? >> Yeah. >> But if you if the if the growth would be not such not such linear, but more penalizing for the adversary in the first stage, then he would also have less chance to win here. So, this I'm just trying to say that this situation has some sort of opposite. So, one

favors linearity because we want decentralization and fairness, but in the second case, we don't want fairness. We want that adversary doesn't succeed at all. >> Uh >> Does that make sense? >> No, but but we can wait until I go into actual construction. I'm not sure I fully understand what you mean. But basically here, like I guess we agree that the goal is to make make it hard for the adversary to keep like finding the kind of correct first message so that I could cheat. Right?

So, that's what we want to define what we call grinding friendly. And again here, everything is in expectation. I want to make sure that any expected polytime prover, for example, any prover that runs in expected time K times T query, makes K times T query in expectation, then in expectation it can find at most K solutions. So, that's the definition. And actually we're going to see that the Bitcoin proof of work or the pre-image proof of work satisfy both this and the previous um Bitcoin friendly property.

So, I'm not sure whether this answer your question, but we can also take it >> good. Totally good. >> Okay. So, then the last property we want to kind of we want our proof of work to have is what we call strongness. And strongness is saying that um we have T queries in total for the honest solver. And we want to make sure that any solver that makes less than T queries can only succeed with at most negligible success probability. And why do we want that? Again, uh, SNARKs. And specifically, Fiat-Shamir again.

And uh, uh, Jack Mall talked about uh, attacks on Fiat-Shamir that specifically diagonalization attacks on Fiat-Shamir. And uh, uh, kind of a long and Gal they proposed to fix Fiat-Shamir and specifically avoid diagonalization attack by using what they call the extended Fiat-Shamir. And in the extended Fiat-Shamir, they specifically use proof of work to prevent diagonalization. And the property they need from their proof of work is what we call the strongness. Okay? And uh, uh, so that's why that that's the three properties that currently we use for

from a proof of work. And there are also, as mentioned uh, earlier, uh, we have existing proof of work construction. And the one that we're most familiar with is what we call the pre-image proof of work, which is just given a uh, random challenge X, and the goal is to find Y, the solution, such that the hash value of X and Y start with a bunch of zeros. That's the Bitcoin proof of work. And now, the property that it has is that um, for an honest solver, if it makes T random queries, then the kind of the

expected uh, the the probability that it solves this uh, whole challenge, if find such Y that start with a bunch of zeros, the the success probability is going to be very very high. And also satisfy kind of this amortized or like um, this Bitcoin friendly um, notion, which we know that every single random query a solver could make or an adversary could make is going to give us one over T roughly Success probability. Okay? And it is also it is also grinding friendly because everything is like purely random independent. So, this particular proof of work satisfy both what we want for Bitcoin and what we

want for kind of Fiat-Shamir grinding um attacks. Do you agree with that? Okay. Um then um so, it's Bitcoin friendly and grinding resistant. And the other proof of work that actually Elon and Gal constructed in their extended Fiat-Shamir paper is what they call the Merkle tree proof of work. So, we all know what is a Merkle tree. It's a way that we do commitment. We have a bunch of values on the on the leaf layer and then the goal is to repeatedly hash the leaf values in a like binary tree fashion until we get to a root.

And then the kind of uh proof of work challenger, the verifier, is going to pick um some lambda many leaves to open and then the opening proof is just the Merkle tree opening proof. The solution is particularly consists of the root value and the corresponding opening path. So, that's uh what I mean uh at the beginning when I was defining proof of work that we have both solution and proofs in some situations. Okay? And for Merkle tree proof of work, um we know that this is kind of is strong. It's friendly for extended uh for for extended Fiat-Shamir um because

it's almost impossible for an adversary to get a root and its corresponding opening for random locations without doing all the work. So, if the tree has size T, it's very difficult to cheat without actually doing all those queries that's required by the tree structure. Okay? So, we say that we we observe that this proof of work and it's actually proved in their paper that this is a strong proof of work.

Okay? And then now finally the focus of today, we're going to like the the quantum age and like all the security have been proven like for the two proof of work that we just saw uh in the classical sense. But what if we have a quantum adversary? How do they behave? Do we still have all the properties that we want? Okay? So then this is kind of a new property that's relevant mostly in the quantum case which we call the quantum tightness.

So again, um uh classically we have the solver that has oracle access to the random oracle and uh um the goal is to give the challenge output a solution within T queries. And in the quantum case now the solver is a quantum algorithm. And a quantum algorithm, specifically when it's given oracle access to a a a function a classical function deterministic function, it's able to do quantum superposition queries to this deterministic oracle function.

No. For uh adversarial solver, this is what we call the quantum random oracle model. Okay? And the question is really we want to have proof of work that is quantum tight in the sense that we want the proof of work to behave in a way such that we still, even with superposition queries, we still need at least T queries. Or like like maybe I I allow the quantum solver to be slightly uh more powerful than the classical one. Maybe I can uh find a solution in T over two many queries.

But for example, I don't want it to be able to break my proof of work with a poly-log T many queries. Okay? That's what we mean by quantum tightness. And then, the question is, do we actually obtain quantum tightness for the two proof of works that we just saw? So, let's look at the first one. Preimage proof of work. And now, my claim is that it's definitely, absolutely not quantum tight. Why is that? Because like actually, the preimage proof of work is kind of like literally the in the form that allow Grover's algorithm to work. Because it's a search problem. We're trying to If we kind of flatten the random oracle, um

instead of like viewing it as a function, we view it as a table where each entry of the table like has the hash value. Then, we're just like trying to search one entry in this large array, large table that satisfies some property. And in this case, we can literally just directly use Grover, and they give us square root T many queries. So, this is not quantum tight. And then, the question is, can we change the construction? Can we improve the construction by doing some like, I don't know, some like uh weird [clears throat] stuff to avoid Grover to be that effective?

And the answer is Shor's algorithm doesn't work. The answer The answer is no, because uh Niakan and Soonow they actually proved an impossibility result uh a few years ago. And the uh kind of the digestion of the result can be summarized in this one sentence. We can say that no Bitcoin-friendly proof of work is actually quantum tight. And in particular, like the square root is the best you can do. So, remember that the Bitcoin proof of work is trying to make sure that you have partial progress according to the like amount of queries you made compared to the like kind of pre-prescribed amount of work that's required.

But, preimage proof of work as mentioned before, it's not only like Bitcoin friendly, we also said that it's grinding resistant. And maybe like we can say that okay, Bitcoin is bad. Okay, what about SNARKs? Can we still have grinding um resistant um proof of work that doesn't suffer from the square root T uh Grover advantage? And it's actually I I don't know like I tried to make this impossibility result work for grinding resistance as well because they really they because they has been satisfied by the same proof of work. So then intuitively like maybe the impossibility still works, but I have no idea how to extend the impossibility.

Um so, open problem one, whether the impossibility extend in this case for um grinding friendly where we have to make sure that the work cannot be amortized. Finding case solutions, you need K amount of work. And on the construction side, on the construct Okay, good. On the construction side, um I didn't spend as much time as the impossibility result, but on the

construction side, which um my ChatGPT told me is that we can actually find a construction where we do satisfy grinding resistant in the pure random oracle model, meaning that all the algorithms there are query restricted but not time restricted. And when we're in this kind of black box pure random oracle model where you don't care about the running time of your algorithm or adversary, then if the honest party is willing to pay in time complexity while still being query efficient, then we're able to have quantum tight grinding resistant proof of work.

But personally, I don't think this construction is like super useful um b- precisely because the honest party need to spend a lot of time. So even if we like remove the idealization layer, if we like get out of the random oracle model with a hash function, the time complexity cannot be improved with um kind of this de-idealization of um the random oracle. So another open problem is uh uh if you don't like to think about impossibility, whether we can improve the um construction to uh actually be time and query efficient in this case.

Okay. So that's uh uh grinding resistant and uh Bitcoin friendly. And then the good news like finally some good news in this talk is that Merkle tree proof of work, the one for extended uh Fiat-Shamir, is actually quantum tight. And the reason for that is actually really cute. So we know that um uh as I mentioned before, a quantum adversary is very very powerful in the sense that it can make superposition queries.

But this lead to the question um making superposition queries like one query in superposition, I'm going to get back the answer in superposition. But intuitively, I'm going to claim that if the answers are in superposition, I don't really have them. They're in superposition. I don't get any information unless I do the measurement. But if I do the measurement, then I collapse to one hash. If I just naively do measurement on the answer I just I received, this means that my one quantum query, the one quantum query in superposition is not so different from one classical query

because I learn one information about like one answer in this like big table that I want to learn. And actually Ali and Nick and Peter, they a few years ago they proved kind of a lower bound saying that this is not far from what you can do. And in the context of actually like analyzing post-quantum security of SNARKs, Miccali and BCS in the random oracle model. Okay? So, that's the working assumption because we're not doing a search problem anymore. Merkle tree is not a search problem. We're actually tried trying to compute something.

And now with the lower bound, we know that one superposition query is not that much more effective than one classical query because to learn the information we have to do measurement. So, that's the intuition and then basically one can actually formally show that Merkle tree proof of work is resistant to this kind of superposition queries and superposition attacks. And in particular, even a quantum solver in order to get like a reasonable root and corresponding opening path, the challenge that Merkle tree proof of work is trying to impose it still need team many queries.

Okay? And but unfortunately, another impossibility result that I just published actually with Benedict and Jessica from NYU where we show that well, it's great that now we have strong proof of work that is quantum tight. But then this goes back to the previous slide on the two open problem like the impossibility result and the potential construction of grinding resistant proof of work because we like we're still care about normal Fiat-Shamir, right?

But then we show that uh if a proof of work is strong, which means that it's friendly for current Yashmir, there's no way that the cur- the the same proof of work is going to work to prevent grinding. Or grinding challenge. So, impossibility result. Those two cannot be obtained at the same time. And because this this is a pure classical result, of course it also is compatible with quantum adversaries. Okay. So, it's uh unfortunately another bad news that uh Merkle tree proof of work uh not only doesn't work for for Bitcoin, but also wouldn't work for grinding.

To prevent grinding. Okay. So, just summary. We saw two proof of work construction, the almost like the only two um that uh we uh we were aware of right now, the Bitcoin one, uh the pre-image one, and the Merkle tree one. And the good news is that the Merkle tree proof of work is uh quantum friendly because quantum adversary cannot give you very meaningful speed up in this case. And uh uh the bad news is that we just cannot hope for quantum tightness for the at least the current objective of like having Bitcoin friendly proof of work.

And uh open problem is all like inside this grinding resistant uh box where uh we cannot show, at least I cannot show similar impossibility um with regard to like uh the uh quantum tightness and grinding resistance. And I also don't know how to do a construction that is friendly in both the random oracle model and also like random oracle with uh computational assumptions. Um but keep in mind that there's no way for Merkle tree proof of work or any proof of work that satisfies strongness to work because of this new impossibility result.

Okay. Questions? Yeah. >> Um if we relax the grinding resistance property so that we're kind of um, grinding resistant up to a constant factor, um, then does the incompatibility still apply? >> It still applies. So, basically, the impossibility is saying that even if you consider, like, for example, uh, you want to have, um, two solutions in, uh, about, like, 1.5 t amount of work in expectation, the impossibility still applies.

>> Okay, that's kind of That sucks. >> It's a It's a relatively strong impossibility. But, I I don't think that's the end of the world. Like, every impossibility has a way to get around it. For this one, particularly, I don't have like uh a very good idea. But, like, just to Just in comparison, so, this particular impossibility is proven in almost the same way as the impossibility of verifiable delay function in the random oracle model. And we know that Well, it's it's not, uh, the impossibility of VDF in the ROM came after the VDF constructions in practice.

Although, like, VDF construction has a different issue, which is most of all of it actually rely on algebraic assumptions, which we we don't like anymore, uh, because they're not quantum friendly. Um, but still, like, uh, random oracle impossibility that this kind of shows that this specific family of random oracle impossibility might be, um, avoidable using, like, some ideas from the VDF construction literature. >> I thought that you could construct a VDF from, um, a SNARK, and so you could, uh, recursive SNARK, and then you >> Yeah, it has it has knowledge assumption, so it's not in the black box

random oracle anymore. >> Yeah, okay, that's That's fair. >> Sorry, I may ask again, uh, the grinding resistant, what what we want to require there again? >> Uh we want to say that expectation to get K solution. >> Uh-huh. >> Um like whether it's like K challenge solution pairs or um the K different solution for the same challenge, you need to pay K times the the work of getting one solution. >> But if I make K Merkle trees, it doesn't work that way.

>> Uh uh the it was formally proven that Merkle tree proof of work cannot be grinding resist. Merkle tree, particularly attacking Merkle tree, is extremely simple because once you do one you compute one Merkle tree, like you have the hash value of every single node in the tree, you can just like flip one of them and it's still going to work. >> Uh-huh. >> With high probability because everything is random. >> Okay. Another thing I had in mind, it's probably not satisfy uh strictly the properties, but we can also make a Merkle tree and require some property of the root. And so we have a a mix. You have to spend some time to work on the Merkle tree and then a bit easier.

>> Uh that that's a that's a very great construction, actually. Um I want now trying to improve the strong proof of work. So now um there are some like constant loss or like poly log loss in the quantum attack still. But if you, for example, um augment every single leaf by adding some sequential hardness, like uh replace each leaf with like a hash chain of the leaf, then you can make it more quantum tight, but it wouldn't be um >> It's not rich, but maybe we can reach something good enough.

>> Uh it would still suffer from the same issue where once you get one solution, it's very easy to get polynomially many different solutions. >> Uh-huh. Okay, thank you. >> Sorry to interrupt. to cure my conference in the meantime. Uh a A about grinding resistance. So like So, the the property of grinding resistance kind of stated as a kind of stand-alone property, but for the setting, let's say of uh use within a SNARK, right? There, let's say we pay attention to the use like an XFS.

There, we have the privilege of being able to domain separate. Like, let's say this session from some other session because, you know, we have the instance, we can also add additional tags, right? And doesn't it in a sense give back some of the grinding resistance across these sessions? >> Uh yeah. >> So, in a sense, maybe we're like within this particular application, we're like maybe less affected just because we have things we can hang on to for domain separation or >> Right. Uh that that's that's uh actually the other result in this uh BCG paper that I didn't mention, which is specifically combining with domain separation and use both proof of work,

the pre-image proof of work and the Merkle tree proof of work were able to do uh grinding resistant uh security analysis for extended Feistel-Miyaguchi. So, in combination of the domain separation and everything, but uh it is uh you mean Do you mean that you use domain separation to like totally get around this possibility? >> Because I'm not sure it really get I mean, it gets around it in the sense that grinding resistance as a property doesn't say anything about domain separation, right? And so, when you're in a setting where you bring it in, maybe maybe it doesn't hold anymore.

But, I was thinking both for XFS and also for actual grinding inside uh Like, if I want to do grinding for like balancing around brown arrows >> Mhm. >> in the quantum setting, maybe I'm better off doing it with the Merkle tree proof of work rather. >> Yeah. >> Because like I will not have this kind of annoying gap where now my kind of honest prover has to kind of lag behind the the like a malicious prover, right? >> Right. Yeah. >> So, basically basically what I'm saying is is it the case that a takeaway that is in the post-quantum setting, the per round grinding for for leveling around around errors should actually be done via like a Merkle tree proof of work?

>> Yes. Yeah. >> Um did you look at uh Equihash? >> What what cash? >> [laughter] >> That's some forgotten proof of work. Uh well, in Equihash uh it was designed for for memory hard proof of work, but I think what's interesting there I'm not sure I 100% understand this grinding resistant thing, but what we uh did there was for example we artificially limited the number of solutions so that you just can't get too many solutions no matter how much work I've done. And the second thing is since it it relies on uh the hardness of generalized birthday

problem, and in generalized birthday we have well, not super tight quantum algorithms, but the gap between best quantum and best classical is much smaller than in simple Grover. >> Okay, the the birthday attack I agree, but for for the first point, how did you restrict the number of solutions? So you're not in the idealized model anymore. You are saying that your verifier has a predetermined group of solutions that it's going to accept, and anything outside you don't accept anymore?

Or >> Yeah, well, you just kind of you you accept solutions from a certain set with high probability there is one solution with kind of negligible probability there are two solutions, but like three, four, and five you can rule out with really good probability, something like this. >> Uh so so you're saying basically you're enforcing almost computational uniqueness. >> Maybe it can be said so. >> Um Okay, I can't say that 100% understand, but then if that's the case, if you're able to like restrict the number of solution, then it uh it doesn't even go back to this

impossibility. This would fall back into the fact that you cannot construct VDF in the random oracle model, but once you're outside of random oracle model, yeah, you can do a lot of different things. But But here the impossibility here is purely in the black box random oracle. >> It's also in black box. The hash is purely black box random oracle. Just the set of inputs is restricted, basically. >> The set of inputs is restricted? >> The set of inputs of the random oracle is restricted, and that's why basically the set of solutions is restricted.

>> Maybe we can take this offline. I I think I am not sure I completely understand the model here. >> We're well over time, but I do have one final quick question. Um so, is the suggestion that in the context of hash-based signatures, we replace the grinding with the the proof of the Bitcoin-style grinding with the Merkle tree grinding? >> If we can, yes. >> Yeah, okay. Cool. Okay. See, thank you so much for your talk. >> [applause]