How to construct a circuit in zkSNARK

Question

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?

Answer 1

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.

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.

Answer 2

To answer your first question, the feature of problem is usually from NP Class where you compute in Non-deterministic Polynomial(NP) time, but verifying the computation should take less than or equal to Polynomial time.

One of the problems that we deal with ZK-SNARKS is proving statements which take NP time but verifying the proof takes less than or equal to Polynomial time. You can prove the statement "I've signed this transaction using my private key" and the verifier can verify using the public inputs (transaction and public key). You can create circuits for say, ECDSA that generates the proof providing the authenticity of signature or a Merkle tree circuit that proves the inclusion of the data.

To answer your second question, theoretically, you can create circuits for statements that can be converted into algebraic equations. Every algorithm that we code can be turned into a circuit where every step of the algorithm is constrained (the constrain must be satisfied to generate a valid proof). It is useful to have some mathematical thinking to create circuits especially when you're programming with languages like Circom. Whereas in Noir which is another DSL for Circuit programming, you're just away from declaring constrain(a + b - c == 0) to create constraints. Every other thing remains same as normal programming. But Noir still lacks some features as it is too early. You can also use Rust because some proving systems like Halo2 are in Rust but you need to deal with boilerplates.