2
$\begingroup$

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.

$\endgroup$

1 Answer 1

0
$\begingroup$

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).

$\endgroup$
10
  • $\begingroup$ 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. $\endgroup$
    – Matthias
    Nov 2 at 14:22
  • $\begingroup$ "...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$. $\endgroup$
    – James
    Nov 2 at 15:22
  • 1
    $\begingroup$ 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: cs251.stanford.edu/lectures/lecture15.pdf. The second aspect is about efficiency if we forgot the ZK requirement. $\endgroup$ Nov 2 at 21:05
  • 1
    $\begingroup$ @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 crypto.stackexchange.com/q/59324/58690 $\endgroup$ Nov 3 at 7:10
  • 1
    $\begingroup$ @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. $\endgroup$ Nov 3 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.