Hash-Based Proofs Without Hashes

Transcript

So, yeah, so I'm going to give this talk about hash based proofs except without the hashes. Which may sound strange, but that's what we're going to do. It's actually based on an old work, ancient work with mine with my brother guy. Back from 2020. No LLMs and so on. The reason I'm giving a talk about it is because I think the type of things we we show in this work are very relevant to kind of this crowd. It's a very theoretical kind of oriented work. But we're doing kind of things that are I think the the type of things we're proving are very very relevant and we're doing it in kind of like a I think a fundamentally different way than what is very common and known to people here. I think people are unaware that there is sort of an

alternative. Which I want to present today. I want to kind of like preface and say that this work was written and is from a theoretical perspective. I think that quantitatively it will not like don't implement this as is. I you know, could not stop myself. I tried to like play around with LLMs to see how much I can like improve it. Like I don't think there's like nothing to me that there's something like very immediate that you can do. I think the most promising direction what might be like to combine ideas from this work with ideas that were more familiar with to get kind of speed ups from there. But anyway, that's kind of prefacing and I want to just show you a very different route that I think might be surprising to some of you. So do things that we know how to do

differently. Okay, so so let's start. So the motivating example that we're going to focus on in this work is just proving a bunch of hashes. So let H be your favorite hash function SHA-256 beside and whatever. Let's fix it. And what I want to to do is be able to prove to you a bunch of hash evaluations. Okay, this is obviously of immense interest to people here. Hashing dominates real workloads. We do like Merkle paths, signatures. You need to do a bunch of hashes. You know, we we have this work flock where our main thing was proving a lot of hashes. So, that's what we want to focus on today, proving a bunch of hashes.

So, the setting specifically that I want to think of is that the verifier knows the outputs kind of the YIs. Those are kind of public. The prover knows the preimages XIs and it's trying to prove to that it knows these these preimages and maybe they satisfy some some like constraints or each XI satisfies some phi of XI. Okay, some predicate. So, how do we do this? Well, um you know, we have all of these like seemingly different approaches. You know, you have like flock, you can do binary field, you can do prime field, you can use a ZK VM. Fundamentally, all of these are are kind of uh from a bird's-eye view, they're all the same. They use like an IOP. They use kind of the Kilian Micali BCS uh transformation of, you know, send

oracles, compile them using Merkle trees, do Fiat-Shamir, and you might want to like optimize your your Merkle tree, um do the T5 uh T8 is it in the year uh T17 thingy. Fundamentally, it kind of, you know, it's an IOP that is uh then compiled. Um what I want to show you today is a different way to prove a bunch of hashes that's going to involve no oracles, no Merkle tree, so T zero or T infinity. Uh I don't know uh what what T. Um so, no explicit commitment.

The only place where we're using hashes is that the statements we're proving are hash evaluations. And and that's it. Like beyond that, we're not explicitly going to be hashing anything. Okay, so no No, better thing than a smaller Merkle tree is no Merkle tree. Um yeah. So, which I think is kind of like surprising that we can do something like this. And it's kind of different, I think, than all the hash-based schemes that I know. Um so, I want to introduce this different approach. Um again, I think it's qualitatively different, and I would even say interesting. Quantitatively, um I don't think it will outperform what we currently have, but I think there's promise there.

Okay. So, what is the typical approach? We already said it's kind of the IOP approach. We start we want to prove K statements. We arithmetize using our our favorite like our arithmetization language. Eventually we get we write down a polynomial IOP. We then transform that into a SNARK using commitments, Merkle tree in the hash based regime, do Fiat-Shamir and we get a SNARK. Right, that's a typical thing we we all do. Of course there's a lot of richness in optimizing different parts of this, but at a high level that's what what we do. Um, the hashes appear kind of both in the statement. We're proving a bunch of hashes, but then that all of this like techniques here is particularly the red boxes are using hashes internally.

Right, both for the Merkle trees and Fiat-Shamir. Uh, at the IOP level it's unconditionally sound, but once you do the transformations it becomes computationally sound. And we pay for this transformation we need to produce the Merkle trees in terms of proof because we need to open the Merkle trees. The our proof size is dominated by just opening these things. If we can prove these things in a different way which will not involve opening Merkle trees, that's already like fundamentally different than what other approaches do. Right?

Um, yeah. So, we want to prove all of my hashes without committing to anything. Um, and the only thing I'm going to rely on is that function H itself that I'm proving is itself collision resistant. Okay? We agree that this is kind of like different than what we're used to. Um, okay. So, right. So, we're going to produce and I'll describe it as an interactive argument. You can of course compile it using Fiat-Shamir to be non-interactive. Um, that kind of then you will need Fiat-Shamir as a hash which we are sort of promising you don't. I think, you know, that is still it still keeps the fact of being like very different from anything else. So, I wouldn't like put all the like the emphasis on being interactive. You You can, as usual, make

it non-interactive and it will still be very different than things we we are aware of. So, don't think of the emphasis as uh being on that. Um something that I think is really unique and interesting is the fact that if what you're proving is not hash evaluations, but rather statements in which so a hash evaluation has the property that from a computational perspective once you give yi the input message xi computationally is unique, right? Cuz it's hard to find collisions. In other statements, um this aspect is not computational. It's actually, you know, if I'm trying to prove to you something about the discrete logs, if I give you g to the x, x is uniquely determined and it's not computationally.

It is just determined. So, for statements in which it is really unique, then you get here in this protocol you're going to get statistical soundness. Meaning that no prover with, you know, even aided by an element will not be able to to break soundness of the system. Okay? With short proofs, no oracles, um which is kind of unique. Yeah, so that's in the setting where things are kind of uh uniquely determined. No Merkle trees as I was saying. And in terms of like the the proof length, here m is going to denote um the size of sort of a single hash.

Okay? Or a single witness when we kind of generalize. And k is the number of hashes that we're proving. So, we see that the the proof length is kind of like if you kind of ignore poly log factors, which you know, being theoreticians we're going to, um it's kind of the size of like one-ish uh of the of the witnesses. Okay? Any questions? >> Wait, m is the number of hashes? >> No, k. K is the number of hashes. M is kind of the think of the input as single hash or or witness size. Okay? M witness size, k the number of hashes.

Um and the prover kind of if you think, you know, the input is like K of these hashes, best case scenario would be like something like K * M, we're going to have maybe K * M squared. Okay, but still nothing uh certainly from a theoretical perspective not outrageous and now it's kind of a really a question of like optimizing beyond that. Okay, what do we pay for this? So, first of all, it's kind of interactive. You can get rid of this interactive with uh interactive aspect with Fiat-Shamir well and I did don't think it like uh trivializes in any way the result.

Um so, I wouldn't put emphasis on that. We need the fact that the witness is computationally unique, which is because it's a hash kind of. And if it's statistically unique, even better. And the the main thing is sort of an asymptotic result. Don't implement this as described, it won't be better, but I think it has interesting ideas. Okay? Yeah. >> So, then idea you could possibly use this as the first layer and then you could switch to the standard SNARK. >> Yeah. >> And you maybe get like the best of both >> Yes, I think I think the most promising direction is some combinations. Here kind of when we did this work, really our our focus was on the the unique thingy setting and not using any cryptography, but the thing I think is most like interesting is to say, you know, not be purist and say, you know, we're

willing to do cryptography, we just want better efficiency. So, how can we use these ideas? So, I think a combination is the best way forward. Okay, so I want to tell you about how we achieve this. We'll see how much we manage. Okay, so the kind of statement that we're interested in are, as I was saying, kind of we have like a Y, an output of a hash, and we want to prove that there exists a preimage X that hashes to uh Y and it satisfies some uh predicate uh phi. And from a computation perspective, kind of there's a unique witness here. In reality, there are many witnesses, computationally you can only find uh at most one.

The actual thing I want to focus is on it's going to be on the statistical setting, it's kind of like if you think of uh that it's not just that it's computationally uh to find two witnesses really they don't exist two preimages. This is known as UP, so kind of a unique unique NP. So, these are statements for which really there's only one exists only one witness. Okay, or or none. So, either none or one. And in that setting it's going to have statistical soundness. Right, so the reason that why we in the hash case we get computational soundness is because it's no longer really UP, it's only computational UP.

Okay? Um yeah, so the main result we show in the paper is kind of, you know, we have uh this UP problem denoted L. We want to prove that K statements are true. Okay, so either we know that they're either all true or maybe some of them uh so, if they're true they have like unique reasons for being true or maybe some of them are not true. The communi- the communication as I was saying before is something like m times polylog. Um yeah, so these are kind of like similar parameters to what what I was hinting to before, so I won't repeat them. Just emphasize again that this is statistically sound. So, quantum can't break it, ElGamal can't break it, even if you P is equal to NP you can't

break it. Unconditionally sound. Um let's skip this. Okay, so so let's do that. And actually a bunch of things here are going to look familiar to you guys. Um so, let's see. So, our starting point is that we have a witness vector, so W1 up to WK. These are say all the preimages of the hash or I want to to stop thinking of the hash example cuz I'm thinking of UP. Right, so we have K like statements and think of W1 up to WK as the unique corresponding witnesses. Okay, so let's plug them all into this long vector capital W.

And it's held by the prover. Never sent, never committed to. Right, we're in kind of this regime. So, first, you know, let's kind of forget that we're in the weird regime and kind of continue as we as we know. What do you do? You start proving stuff, right? So, you run your your sumcheck, your GKR uh to prove that all of these statements are correct. Okay? You run it, everyone's happy, whatever. Eventually, you're going to get a multilinear evaluation claim on your uh vector W.

And if we were in the, you know, usual regime that we all know and love, you'd say, "Ah, great. I've already committed to W using a PCS. Now, I'll run my PCS evaluation, prove it, and I'm all done." But, the problem is that I haven't committed to W, and I can't do this. So, I need to do something else. But, is that setting clear? Okay, so we have not explicitly committed to W. Notice that in a sense, um sort of information-theoretically, W is committed to because all the statements have unique witnesses. So, I haven't, you know, like cryptographically committed to them, but information-theoretically, it's all determined.

Cuz they're unique witnesses. Um but, I don't as a verifier don't have access to these witnesses, so it's not clear that it helps. So far, so good? Okay. Right, so in the usual like snarky IOP regime, I would open the commitment. Here, I don't have a commitment to open. So, here's the twist we're going to do, and this is based on work of Guy with uh Salil Vadhan and Avi Wigderson. So, and it's not at all clear why this helps, but instead of running my GKR once, I'm going to run it uh T, which is equal to 2M times repetitions. So, instead of getting a single multilinear evaluation claim about W, I have T multilinear evaluation claims about W.

I can't verify them, but I have them. So, I'm kind of in even like more trouble cuz I have more claims I want to check, and I I have a mechanism to to check them. But I'm doing that. Okay? Why do I do this? Because actually this is going to give me some sort of like robustness or distance. So the property that I have is if one of my statements is incorrect, one of the YJ's is false, then not only does uh do I know that So let's imagine pretend that, you know, we are in the case of a cheating prover for a false statement, one of the YJ's is false.

Um in this case still the vector W is determined, right? So for every you know, we have the K instances. For those that are correct, I'll put in the unique witness. For those that are incorrect, I'll just by default put in zeros. So the vector W even in the false case is fully determined. And we know that because of soundness of, you know, sum check or GKR, whatever, for we when I run uh GKR for this fixed vector W, I'm going to get a false claim. Right? But now that I've run it T times, I'm going to get T claims.

And I want to claim that not only are these claims going to be false, even if I kind of modify some of my vector W, they will remain false. Intuitively, you have to modify at least like T-ish entries of W to make all these claims true. Does that make sense? We have like T linear claims. They're kind of in the linearly independent-ish in the right way. So if I have T of the claims, not only is uh are these claims false for W, they're uh false around W and the all around W.

Okay? So here's kind of the name of the game. There's this vector W to which I don't have like direct access as a verifier, but I I can sort of if I really want to check like one entry of W, I can just ask, you know, "Hey Mr. prover, send me WI." That will be the cost of sending a single witness. So if I just want to query the vector W in a few places, I can do that. I don't have it fully, but if I want to query a few places I can. So, I can query W in a few places. I have T multilinear evaluation claims about W.

And I want to check that like, you know, accept if all these claims are true and reject if W is far from any string that would make these accept. Does this like setting ring a bell? It's a very kind of a proximity or fry like setting. So, I want to check that my vector W is close to a vector satisfying all my multilinear all my T multilinear evaluation claims. And specifically what I'm going to show you is that I can reduce checking T multilinear evaluation claims about W to reading only N capital N over T of the entries of W. I'll remind you in a second what capital N is.

It's going to have this protocol is going to have T communication. Um and it's going to kind of catch strings W that are T far from all strings, which is what we had before. So, just to remind you capital N was the overall length of the entire vector W, which is just the length of like K witnesses. Okay? >> But right now, I can choose W after seeing the claims, right? >> No. >> After seeing all the >> No, because we've we've fixed the statements that we're proving. So, it's a bunch of the cash outputs or whatever. >> Yeah, but the multilinear evaluation claims at the end of the sum check, I can choose W >> No, so so so so so W think of it as it's Once I fix my statements my KUP statements for each UP statement, if it's a correct

statement, then WI will be the unique accepting witness for it. And if it's a false instance, it just be default zeros. So, once you've like said what your what the statements are, the string W is determined. >> Okay. >> Okay, before running sum check, before running GKRS. >> All right. >> Okay? So, it's it's kind of like I don't as a verifier I don't have direct access to it, but it is determined before the protocol even started. >> Okay, maybe I'll see the how it continues. It seems like okay, but why do I have to use that W? I haven't committed to anything.

>> Right. Okay, so so in what ways it it in what ways it determined for the verifier? Like if I'm the verifier, so let's say I run the GKR on some check, and I'm super interested for some reason in W7. How can I access it and can the prover answer in an adaptive way based on the multilinear evaluation claims? And I claim it cannot cuz when I ask for W7, um let's say the W7 if it was a false instance, I'll say uh hey Ariel, can you send me the witness for W for like X7, you cannot.

And if it's a true instance, there's only one thing you can send cuz it's UP. >> And what are the instances you're claiming? >> So, I I do have sort of as a verifier I have oracle access to W via the prover. >> Oh, or maybe in UP the instance is a commitment to the >> Yes, exactly. It is. That's exactly my point. The instance is a commitment to the witness. >> But for one bit of W7? >> No, I have to pay the entire W7. Yes. Yes. So, when when I want to open something, I need the entire witness.

>> Right. Right. >> Yes. Okay? Okay. Um Cool. So, why is this useful this thing? So, I'm claiming that I'm going to show you how I can reduce the T multilinear evaluation claims to making capital N over T queries to W and with T communication. First of all, notice that T communication I'm okay with. T was like about M, so it's like more or less like a single witness, so that I'm okay with. Why do I say that it's like really interesting that N over T queries suffice?

So, remember that N was like M times K and T was uh like 2M. So overall the number of queries that I'm going to make to the string W is K over 2. That means that from here on the queries that I want to to show are only for half of the witnesses. And now I can recurse. Okay, so I have a product it's kind of it's it's essentially folding. I want I'm interested in batch verification of K thingies. I've done this procedure. Now I'm only interested in K over two of the thingies.

And I can run the same protocol I'll only be interested in K over four. I'll keep doing it until I'm you know constant number and then just send all of them. So really this is the key thing. Once I have this thing that I can check T multilinear like proximity to satisfying T multilinear evaluation claims with only capital N over two queries I'm done. I have folding and I'm done. Okay? Um yeah, so this is just a direct question.

So the key thing I need to show you is how to do uh ah I'm not allowed to go back. Uh Oh no. Um Okay. Cool. So and what I the only thing I need to show you is a proximity test for multilinear evaluation for T multilinear evaluations. So here's the like new setup you should be thinking of. We have our input which is this long vector W. I'll denote it as a two by something matrix because it will be convenient for us. That's the input just putting in all the witnesses concatenated together and splitting them into two rows.

Um think of this row as kind of the Boolean hypercube. And I have my T multilinear evaluation queries on this. Um so let's draw it this way. The big box the the small box is the thing that I as a verifier can sort of like access locally to make queries into. The big box is the entire multilinear evaluation of everything. And I'll be interested in kind of looking specifically at the first and second row, which are like sort of like Yeah. Okay, the picture makes sense so far?

Cool. So I have my T multilinear evaluation claims at like random locations. These are the red boxes. And I want to verify them. What I'll uh Skip this. What am I going to do? Kind of the main thing we we we know how to do. What was it? Divide and conquer? Nico, how was you describing it? Split and fold. Yeah, so I'm going to do that. So first thing I'll do is I kind of ask, "Hey Mr. Prover, would you mind decomposing these claims into the contribution separately of row one and row two?"

Okay, so for each column in which I have a red claim, I have, you know, "Prover, can you please decompose the claim?" That gives me sort of T claims about row number one and T claims about row number two. And you know, if some of the claims are false, then I'll get false claims here. Now what I'll do is fold. And um yeah, and this is actually so introducing the same work by RVW. This is sort of the first proximity gaps paper which did it for this kind of reason. And so the idea is so I have like F0 and F1. Intuitively, if the original statement were delta far from satisfying the T multilinear evaluation claims, then on average F0 and F1 um should be

more or less delta far in relative distance from satisfying the T multilinear evaluation claims. And now, you know, we do the random linear combination, which we kind of know from Fry and and other places. And you'd expect that F prime is also delta far from satisfying the T multilinear evaluation claims that we we get. So if we're in the Fry regime, what you'd maybe expect to see is that the prover would commit to F prime. You'd maybe like check consistency between F prime and F and then recurse on F prime.

But we're not allowed to commit. We're not allowed to send Oracle. So, what I'm going to propose, which sounds problematic, is that we don't commit to F prime, but rather like each time the verifier will want to query a coordinate of F prime, it will just emulate it by querying the two corresponding coordinates from F0 and F1. And that sounds like a really bad idea because kind of you know, when we recurse, the problem size shrinks by a factor of half, but the query overhead doubles. Each query in the recursion is going to cost two queries when I unfold the recursion.

So, I'm really not making any progress. But uh soon we'll see that I I am. Okay? Does make sense? Okay. So, no commitment, right? So, each query to F prime is emulated by two queries to F. Okay. So, let's see, you know, I was saying that it's kind of like take it uh you know, take my word for it that if the original function F was delta far from satisfying the T multilinear evaluation claims, then F0 and F1 kind of each are delta far uh from satisfying their own claims.

And now um when you take the random linear combination, there's a question of like how far will F prime be from the its multilinear evaluation claims? And in this nice picture that I have here, where the errors are kind of not aligned, actually F prime the its distance from satisfying the claims is going to double. Because you're going to pick up the errors that when the errors are unaligned, you're going to pick up both errors and the distance doubles. So, that's kind of like, you know, nice friendly uh cheaters who don't align their errors, actually, you know, the like two good things will happen and one bad thing will happen. The two good things are that F' is half the size, um its distance has doubled,

and now the query overhead also doubles, but again, two good things have happened and only one bad thing, so overall good thing has happened. Okay? >> So, now you don't need to query both. >> Um okay, so now there's a question of what happens when you align the errors. Um so when you align the errors, um you don't get amplification if you have a delta far and delta far, you combine and it's still delta far, and now you're in a bit of a problem. And um I'm not sure what Elan suggested, but uh it sounds maybe like what was originally proposed by uh the RVW paper.

Um we're going to do something different here okay? Um does this make sense? So, in this thing where the errors are aligned, distance doesn't double and we kind of have not made progress. So, the fix is going to be uh it's inspired by a work by uh Bensusan, Koparty, and Sarif. And the idea is really simple. It's going to be to shuffle one of the rows before folding. What do I mean by that? So, instead of taking the original row, so I had like F0, I had F1, I'm going to kind of just compose F1 by taking an affine shift.

Okay, so instead of thinking of you know, F1 of X is a multilinear function, I'm going to choose a random vector B and think of F1 of X XOR B. The XOR is kind of like before you apply F1. Okay? The effect is sort of like um think of it as sort of like some permutation of the input of uh of F1, which is going to permute in a way also the uh the errors. Okay, so now because like F0 and F1 have been fixed, the location of the errors have been fixed, when I apply this permutation, now they're no longer fixed.

And now the errors, you can hope for them to uh um uh accumulate. Yeah. Okay, 5 minutes. Okay. Um one thing that is very you you might say that what is special about this permutation? What's It's really simple, but the key property that we we use is that you can translate multilinear evaluation claims about the composed function or rather multilinear evaluation claims about F1 into multilinear evaluation claim about the composed thing because it's only an affine shift. Okay, so the multilinear extension of F1 composed with this permutation is just um applying it sort of after you take the multilinear evaluation because of sort of linearity. If the uh transformation were were non-linear

in one of the variables, we would be we would have a problem. Yes. Yes. Um Yeah so in this case, the errors are kind of unaligned and indeed we get distance 2 delta. A problem that I think I'm going to skip over is that the multilinear evaluation claims are also are no longer aligned as well. Like previously, we had like T multilinear evaluation claims about F both F0 and F1. We just moved the F1 guys, so they're not aligned so when now in terms of multilinear evaluation claims about F prime, um you know, even if you think of like even if the prover helps us out, we're going

to have two T claims. So we're going to have another uh little baby protocol that reduces the two T claims back to T claims. I'll skip over that one. Okay, but just to summarize what happens in this reduction is that the size of the problem reduces by by a factor two. The distance grows by a factor of close to two. The number of query doubles, unfortunately. That's sort of what sending oracles would have saved you, but we're not sending oracles, but overall, if you do the calculation, um the situation has improved by two. Um Yeah.

So you repeat this protocol uh um So, you repeat this protocol enough times so that the problem is small enough and then you can solve the problem kind of just directly by yourself. Okay? So, I want to like uh zoom out again, repeat that what I was kind of saying before. Um when you're interested in proving a bunch of of of hashes, we have sort of the main approach that kind of all of us are doing which is based on on IOPs, a lot of the clever protocols and so on, but same like high-level idea, you do a like a PCS of the of the witness or the computation trace, um you compile it using Merkle hashing and so on. Um it works great.

Um what I was so forth we try to do in this work is tell you that, you know, there's a different approach um which is certainly different. You're sort of I think maybe the fundamental difference is that commitment is information theoretically by the uniqueness rather than by explicit uh Merkle tree. Um it's cool because it means that the prover work the prover doesn't need to do any explicit hashing. Okay, so you're saving yourselves the entire Merkle tree computation. We also never needed to do kind of a a Reed-Solomon encoding or stuff of that nature. So, the workload is very different.

Um all you're doing is just like field arithmetic, all these tricks that I was describing. Um this in contrast to the general approach that works for all of NP, this is sort of for like batch UP or batch computational uh hashes. Um and in terms of like the the the status of, you know, this is deployed, we're all running these kind of things, this is kind of an asymptotic result. Um but I, you know, my my hopeful perspective is that this sort of similar to how the GKR protocol was originally described as, you know, uh theoretical work, it had like a polynomial time prover, there was a cubic overhead and it took like a bunch of follow-up works to make it actually

practical. So, what I'm hopeful is maybe this something similar can be done here or something weaker of the just like getting inspired by these ideas or combining them with existing things to get the best of both worlds. I think that's all yeah. So, um in terms of like open problems I think as I was kind of like uh preparing these slides and taking like a more practical perspective on this problem, I think there are asymptotic improvements that sort of need to be done before this there's hope for this to be practical.

For example, um one thing that comes up is that we need to repeat the GKR many times and that's going to introduce sort of quadratic running time to the prover which we don't like. We'd like linear or close to linear provers. So, that's kind of of an issue. Once we resolve that then or like sidestep those can we get concrete efficiency? Um maybe motivated by the sessions from before um when we wrote this paper we were really thinking about UP and not the computational UP setting that I was kind of telling you about. Um to make the computational UP thing really so the thing when like prepared the slides I convinced myself of is I can you can show soundness showing knowledge soundness seems more tricky.

Um so trying to do that would be very cool. Um trying to get similar results beyond unique witnesses seems difficult but that's another uh open problem. Yeah. Um any questions? >> So, I think so this works for batch, right? >> So, if you have a batch of case statements even without a unique witness kind of you can cheaply commit to the witnesses. Not a commit to read Solomon encoding of the witnesses, just to the witnesses.

>> Okay. >> Um and then when you want to open a witness, you kind of check that it's let's say with a Merkle tree then consistent. Then you kind of just reduce back to the computational unique >> So you're saying that the in the you like batch NP setting, you can do the same thing with a Merkle tree but but still avoid um the the encoding. >> Yeah, which is the slowest part, right? >> Yeah. Yeah. I'm good. >> So this is this is using the MLE as as an as an encoding, which if I remember correctly is a Reed-Muller code, right?

>> Yes, but it's it's doing it in an interesting way. It's saying it's not like the usual way you view MLE as an encoding is you take your vector, you evaluate its MLE at like all points and that's the encoding. Here it's saying the encoding is all strings whose MLE at a bunch of points is equal to a bunch of values. >> Yeah, you effectively have the entire domain as your code as your code. >> No, no, no. So it's not that that would be the what you're saying would be like the typical way to think of MLE as an encoding. This is saying valid codewords I'm not going to tell you how to encode even. I'm just going to describe what makes a codeword valid.

A codeword is valid if you look at it, you compute its MLE at a bunch of points that I tell you, and you check their values. Any string that satisfies that requirement is a valid codeword. That is different than taking the string and evaluating its MLE everywhere. And and and and yeah. So in particular the like the the the domain of the codeword is not F to the N. It's just like some two to the N thingy. >> Got you. >> Yeah. >> Then the my following question is is there a univariate version or a a different code um that you could use here?

>> So I was asking myself this especially in the context like of efficiency. So for example, it seems um you need to like compute the multilinear evaluation at a bunch of points and that's kind of expensive, whereas computing the univariate evaluation at a bunch of points is is cheaper using uh the FFT. Um one point that I didn't get to discuss in which this seems tricky is the 2t to t uh reduction. So, we have the 2t claims, reduce it back to t. That uses like nice thing that we do in like multivariate land of taking a curve through these points.

Um so, I think it's a great question that I don't know how to I I ran into I tried it and I ran into a problem. Yeah. >> Uh what what is the the soundness error? >> Um all right. So, in the paper I'm sure we wrote it that it's half um and then you repeat to amplify to reduce it. >> So, it So, it also you'd have a times lambda maybe >> Yes. Yes.

Yeah yeah. You you should have a times lambda on on efficiency of everything. >> And on proof size. >> Yeah. And proof size. >> proof size and >> Also, also on proof size. Yes. >> And we'd also want to assume lambda on soundness maybe. >> Yes. Yes. But all of those are No, I think after we like I I would do these things after we convince ourselves that it's promising in terms of uh uh efficiency and I don't think it as is is promising because we have these quadratic factors both in prover time and so, I really like your your point about here is like I I think an interesting about what Ariel was saying.

So, there's like lambda m uh proof size likely maybe maybe a little bit better with something like that and that is sort of like um if you So, so say you want you want to use this system in order to just like um recurse like prove a bunch of Merkle paths in recursion. Um so, you have many many Merkle paths and you want to prove them. Eventually, the proof size will be like lambda times a single one. So, it seems like maybe So, think of you know, you could have uh use an outer proof system like an outer proof, an initial proof that has a lot of queries.

And you can use this to reduce the number of queries down to uh lambda m. Yeah. Yeah. Okay, so I think I'll stop here. Thank you. >> [applause]