4

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?

Mkotori
  • 65
  • 4

1 Answers1

2

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.

Hypatia
  • 317
  • 1
  • 6