0
$\begingroup$

My understanding of zk SNARK is as follows: through (flattening -> R1CS -> QAP), bind the answer of the original proposition to the solution vector s of QAP, and then because QAP is an NP problem. So if the verification is passed, the verifier can be sure that the prover knows s. And because of the NP problem, the only way for the prover to know s, other than good luck, is to solve the original proposition

But if the original proposition is not NP, the prover may cheat

What if the answer to the original proposition is unique? For example, I want to prove that I know what x is for x-5=0? Of course, in this way, the dimension of QAP may be too small, and the attacker can generate many legitimate s, then if I change the dimension of the equation to be solved to 1 million

$\endgroup$
4
  • $\begingroup$ Your example is clearly an NP-problem. The witness is the value of x. $\endgroup$
    – Maeher
    Sep 19 at 6:03
  • $\begingroup$ Solving equations is an NP-problem ? $\endgroup$
    – Steven Wu
    Sep 19 at 13:17
  • $\begingroup$ A language is in NP, iff there exists an efficient algorithms, called a verifier, such that for every word in the language (and only those in the language) there exists a short witness, such that the verifier can check that the word is indeed in the language. Ignoring for a moment that what you describe there is a very trivial language, because any equation of that form would be in the language, this is clearly true for the problem you describe. Given the witness 5 I can efficiently verify that 5-5=0. $\endgroup$
    – Maeher
    Sep 19 at 13:37
  • $\begingroup$ @StevenWu is the current answer acceptable? $\endgroup$
    – Wilson
    Sep 21 at 22:57

1 Answer 1

1
$\begingroup$

The comment by @Maeher states that the language you're considering is in NP.

However, a direct answer to your question is: We do not currently have zk-SNARKs for languages beyond NP. What we do have is practical Zero Knowledge proofs for UNSAT. Thus, we have practical ZK for CoNP (for a specific definition of practical, refer to paper).

The work Proving UNSAT in Zero Knowledge is published in CCS22. It is important to note that this is ZK not a ZK-SNARK because we do not know how to make the protocol in the paper non-interactive or succinct.

$\endgroup$

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.