NP(-Complete) and Circuits
In previous blog, we introduced the notion of interactive proof. In interactive proof, there are two entities, a prover and a verifier, they interact with each other for several rounds. At the end of interactive proof, the verifier decides to accept or reject.
Circuit is a fundamental component in proving system and all computations in NP can be represented as corresponding circuits. In this blog, we first give the definition of ’P’ and ’NP’ and then introduce the circuit.
The general class of questions for which some algorithms can provide an answer in polynomial time is ”P” or ”class P”. For some questions, there is no known way to find an answer quickly, but if one is provided with information showing what the answer is, it is possible to verify the answer quickly. These questions are regarded as ”NP” or ”class NP”. Most importantly, all problems in NP are in zero-knowledge, and problems in P are subset of problems in NP.
Next, we will introduce the notion of problems in NP- complete. It is really important as all problems in NP can be reduced to a NP-complete problem in polynomial time. Namely, one NP-complete problem can represent any problem in NP, then it can be proven with a zero-knowledge proof. If a problem is in NP-complete if it satisfies the following properties:
• 1. It is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying all possible solutions.
• 2. The problem can be used to simulate every other problem for which we can verify quickly that a solution is correct. In this sense, problems in NP-complete are the hardest of the problems to which solutions can be verified quickly. If we could find solutions of some problems in NP-complete quickly, we could quickly find the solutions of every other problem to which a given solution can be easily verified.
Formally, a decision problem c is NP-complete if c is in NP and every problem in NP can be reduced to c in polynomial time.
The Boolean satisfiability problem (SAT) is the problem of determining if there exists an interpretation that satisfies a given Boolean formula. For example, for a Boolean expression a AND b, there exists a = 1 and b = 1 such that the Boolean expression outputs true. SAT is the first problem that was proven in NP-complete, which means all problems in NP can be reduced to SAT in polynomial time. In addition, any Boolean expression can be expressed as a Boolean circuit. Therefore, we can use a circuit to represent any problem in NP and prove the evaluation of the circuit in zero-knowledge.
Fix a finite field F = {0, . . . , p − 1} for some large prime p > 2. An arithmetic circuit C : Fn → F is a directed acyclic graph (DAG) where internal nodes are labeled as +, −, ∗ (addition, subtraction, multiplication) and inputs are labeled as 1, x1, . . . , xn.
An example of the arithmetic circuit is shown in Figure 1. This example implements x1(x1+x2+1)(x2−1) with only addition and multiplication gates (subtraction gates can be regarded as plus the inversed number). In addition, the circuit size is denoted as the number of gates in the circuit. The circuit size of the example is 3.
In next blog, we will present some cryptographic building blocks and give an interactive proof called ’commit-and-prove paradigm’ for proving the evaluation of a given circuit.
Reference:
https://zk-learning.org/assets/Lecture2-2023.pdf
