4
$\begingroup$

I have a few questions about how to use zk-snark. Since the basic logic of using zk-snark is:

  1. using a circuit to represent a problem,
  2. generate an R1CS from the circuit,
  3. transform R1CS to QAP and then we can run zk-snark

For the first part, is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs? Besides, how to flatten a problem into a circuit, by programming or using mathematical methods?

$\endgroup$

1 Answer 1

2
$\begingroup$

is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?

Problem should be in NP class. NP problems are problems that there exists an (efficient) algorithm that can decide or prove in polynomial time that is w a witness for the statement s (their statements) or it isn't. Many of zkSNARKs are based on circuit satisfiability problem. Circuit satisfiability is a NP-complete problem. There are two types of circuits: boolean and arithmetic circuits that can be converted to each other. Roughly speaking, we can design circuits for all algorithms (ex. SHA-256) that we can run on our computer. The below picture is a simple boolean circuit consist of wires and logic gates (AND, OR and NOT). In a zkSNARK system based on this simple circuit, prover want to convince the verifier that he knows the inputs ($x_1$ = 1, $x_2$ = 1, $x_3$= 0) that for this inputs the output of circuit is true, in another words, he knows the inputs that satisfy this circuit. enter image description here

how to flatten a problem into a circuit, by programming or using mathematical methods?

After converting a NP problem to a (boolean or arithmetic) circuit, you should convert this circuit to a SNARK-friendly format like R1CS. There are some compilers that you can write your problem in a high-level programming language in them and compile the problem to R1CS format, for example, you can use ZoKrates, a toolbox for zkSNARKs on Ethereum or you can use libsnark's gadget libraries.

$\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.