Score:5

Crypto

Succinct verification of computation without ZKP

Matthias

11/2/23, 6:35 AM

What the state of the art for producing quickly verifiable proofs of correct computation when your proof is allowed to leak knowledge?

For context, I am inspired by Miden VM's promises:

For any program executed on Miden VM, a STARK-based proof of execution is automatically generated. This proof can then be used by anyone to verify that the program was executed correctly without the need for re-executing the program or even knowing the contents of the program.

However, I am wondering whether we can do better (eg decrease proving time or space requirements etc), if we drop the zero knowledge requirement.

134

1 + 0

zero-knowledge-proofs

verifiability

computational-complexity-theory

Score:1

Crypto

James

11/2/23, 1:11 PM

I don't believe ZKPs are capable of proving that a program has been run correctly, where correctly would mean that the verifier can confirm that $f(x)=y$ is true knowing only $x$ and $y$.

Logically we can imagine that a malicious actor could produce two programs $f(x)=y$ and $f'(x)=y'$ where $f'$ is a corrupted version of $f$. Without knowing any details about $f$ or $f'$ it is impossible to distinguish whether $y$ or $y'$ is the "correct" result of the correctly run program $f$.

It may be possible to construct a more efficient form of $f$ that maps the same inputs to the same outputs but is faster to run. However, this is a problem more specific to compilers - you can never guarantee that 'circuits' (programs) of a shorter length will behave the same.

As for the second part of your question this would depend a lot on the specific ZKP algorithm used. In most algorithms the most computationally expensive part is converting everything that needs to be proven into a format that is provable (i.e. turning $x=25$ into some polynomial equation of a large degree).

Therefore the less you need to convert, the more efficient the proof will be. This would mean that you could potentially produce a more efficient operation by hiding less of the information (though as above, I don't believe this would help in the example of Miden).

+ 10

Matthias

11/2/23, 2:22 PM

Oh, I think you are taking the quote to literally. They assume that you know at least a fingerprint of the program. Keep in mind that program and input are interchangeable: your pogram could be an interpreter and the actual program be completely contained in the input. Or conversely, you can hardcode parts of your input in the program.

James

11/2/23, 3:22 PM

"...without the need for re-executing the program or even knowing the contents of the program" seems to be trying to say that someone could run a program while potentially not needing to know the program. If we do assume I am taking the quote beyond its original intent though, than the later parts of my answer still apply. Unless the fingerprint of the function is a more efficient version of the function as created by some compiler then there is really no way to use the fingerprint of the function to verify that $f(x)=y$.

James

11/2/23, 3:36 PM

Zero-Knowledge Proofs are functions of the form $z(x)=y$ where $y$ proves knowledge of $x$ without revealing any details about $x$ itself (from a simplistic sense). It sounds like what is needed for Miden is some function of the form $o(f(x))=y$ where $y$ proves knowledge of $x$, which is perhaps where program-obfuscation comes kind of close to what is needed.

Marc Ilunga

11/2/23, 9:05 PM

The question is more about schemes like pre-processing SNARKS, where the setup algorithm outputs prover and verifier keys such that the verifier does not need to read the circuit or function. Which it seems we have several constructions for: https://cs251.stanford.edu/lectures/lecture15.pdf. The second aspect is about efficiency if we forgot the ZK requirement.

Matthias

11/3/23, 12:13 AM

@MarcIlunga Yes, exactly! I should have probably not brought up Miden at all, even though it was my inspiration. I'm interested in the case where the inputs and the function are public, but perhaps too large and cumbersome.

James

11/3/23, 2:03 AM

@MarcIlunga The first part of the question was asking about the possibilities of verifying the correct execution of a program with little or no knowledge of the program. The example you cite though does not seem to be able to verify that *the* program has been run correctly, just that *a* program has been run correctly which seems to not align with the tag of `verifiability` (cannot distinguish $f$ and $f'$).

James

11/3/23, 2:11 AM

@Matthias This would be the exact same scenario. In any instance where a user cannot (or chooses not to) run the program themselves to verify that a given input will result in a specific output, there is no ZKP that I am aware of that can verify *the* program has been run correctly. You can verify that *a* program has been run correctly, but you will never know if this was the correct program you originally intended to be run. Hence, we arrive at the use cases of progam-obfuscation.

Marc Ilunga

11/3/23, 7:10 AM

@James, the notion of vérifiability in the question is probably better seen as proof that the output correspond to output of an evaluation on some (secret) input. Indeed, there are several equivalent programs(circuits) computing the same function. But I am not actually sure a proof for an some program is valid if the setup was run on another program. After all, we have proof system with non universal setups. So an accepting proof seems to break correctness… This is better explained here https://crypto.stackexchange.com/q/59324/58690

Marc Ilunga

11/3/23, 7:14 AM

@Matthias, my understanding is that adding ZK to a SNARK/STARK is done by some standards transforms where one adds a bit of randomness via addition with an appropriate field element. So it doesn’t seem like ZK is the main bottleneck.

Matthias

11/11/23, 5:31 AM

@MarcIlunga Thanks! I wonder if removing ZK requirements for other approaches does make a difference.

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: Succinct verification of computation without ZKP

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.