In my last post, we discussed about the mind-bending world of P v NP. We talked about problems that are easy to solve (P) versus problems that are hard to solve (NP). We used Sudoku as our guiding example: finding the solution to a blank 9x9 grid is fiendishly difficult, but it’s the perfect example of an NP problem. But there’s a secret superpower hidden inside the “NP” name that i saved for today. This secret is the entire reason Zero-Knowledge Proofs (ZKPs) can even exist.
The “A-ha!” Moment: What “NP” Really Means
“NP” (Nondeterministic Polynomial time) is a computer science term, but for our purposes, it has a simple, powerful meaning:
NP Problems are problems whose solutions are easy to verify.
This is the “a-ha” moment.
Think about your Sudoku puzzle. Starting at a blank grid is hard (really hard to solve). But if i give you a completed puzzle, you can check my work almost instantly. You just trace your finger down each row, each column, and each 3x3 box, checking for duplicates. This verification process is incredibly fast (easy to verify).
This is the entire foundation of ZKPs. A Zero-Knowledge Proof is not about solving the hard problem. It’s about a Prover convincing a Verifier that they already have a valid solution (a “witness”) that verifies correctly all without revealing the solution itself.
Isn’t this cool??
But this raises the critical, multi-billion-dollar question: how do you formally “verify” a computation? You can’t just trust someone’s Python script. You need a formal, mathematical way to represent the program logic. This is where circuits come in.

What is a ZK Circuit? The “Cryptographic Contract”
When we say “circuit” in the ZK world, we’re not talking about a physical piece of silicon. A ZK circuit is a mathematical construct or an “encoding” of a program. Its entire job is to define the rule and logic to verify that a program was run correctly. This process of converting a program logic into a set of mathematical equations is called Arithmetization.

Think of a ZK circuit as a “cryptographic contract.” This contract is made of constraints a list of mathematical equations that must be true.

  • Prover’s Job: To create a valid proof, the prover must provide inputs that satisfy every single constraint in the contract.
  • Verifier’s Job: The Verifier just checks the proof, which confirms that the prover honored the contract.

Let’s use our Sudoku example. The “cryptographic contract” for a Sudoku circuit would be a set of mathematical constraints asserting:

  1. Rule 1: Every cell must contain a number between 1 and 9.
  2. Rule 2: Every number in a row must be unique.
  3. Rule 3: Every number in a column must be unique.
  4. Rule 4: Every number in a 3x3 box must be unique.

A prover can prove they solved the puzzle by submitting their solution to this circuit. The proof generation process will only succeed if all the specified rules are satisfied. So, how do we write these rules? This brings us to the first, most intuitive “type” of circuit.
Type 1: Boolean Circuits(The intuitive, but Flawed, Approach)
This is the circuit from your “Computer Science 101” class. It’s a basic building block of all digital computers.

  • Wires: Carry binary values (bits): 0 (False) or 1 (True).
  • Gates: Perform logical operations: AND, OR, NOT.

For ZK systems to understand this, we need to convert the logic into math. Let’s make a simple logical statement: (a AND b) OR (NOT c). Let’s see how it became the set of math constraints:

  1. Force wires to be a boolean: First, we need to make sure that a,b, and c are 0 or 1. We do this with the polynomial constraint: x . (x - 1) === 0. This equation wis only true if x = 0 or x = 1
  2. Translate the Gates:
    • NOT c becomes the equation: (1 - c)
    • a AND b becomes the equation: (a . b)
    • X or Y (complex one) becomes: X + Y - (X . Y)

We can already see it is getting complicated. A simple OR statement becomes the three-term equation. Now just imagine a 3D Sudoku circuit that’s 9 * 9 * 9 = 729 variables, just to describe the board we even write the uniqueness rules!

The Cons: Why Boolean Circuits Are a Bad Fit For ZK If i want to describe the issue in a single word is inefficiency. Boolean circuits are “verbose”. They force users to break every computation down to the bit level, which creates a “polynomial blow up” in the number of constraints.
Let’s use a simple example:
Problem: prove: a + b = c, where a,b, and c are 32-bit numbers.

  • In a Boolean Circuit: This is a nightmare. You can’t just “add” them. You need to model the computation at the bit level. This means you would need 3 * 32 = 96 input wires and a massive, complex web of thousands of AND, OR, and NOT gates to build a “32-bit adder” circuit.
  • The number of constraints becomes enormous, making the proof slow to generate and huge is size.

Type 2: Arithmetic Circuits (The Zk Standard)
Instead of breaking everything down into bits, what if we could just do math directly? That;s exactly what an arithmetic circuit does. These are the standards for virtually all modern ZK proof systems.

  • Wires: Carry numbers. Specifically, they carry elements from a “finite field,” which is a fancy way of saying numbers that “wrap around” (like a clock) and don’t have rounding errors.
  • Gates: Perform arithmetic operations: ADD (+) and MUL (*)

That’s it, doesn’t this look and sound simple? Yes, it is now we can write any program that you want to prove, no matter how complex it is, but it must be flattened into a list of simple addition and multiplication steps.
Why are arithmetic circuits so much better?
There are two Big reasons why we use these:

  1. Massive Efficiency: Let’s revisit our a + b = c (with 32-bit numbers) example.
    • Boolean Circuit: needs 96+ wires and thousands of gates
    • Arithmetic Circuit: 3 wires(a,b,c) and one single constraint: a + b - c === 0

This reduces the circuit size drastically. This makes proofs for math operations millions of times more efficient.

  1. Cryptographic alignment: The cryptography that secures most Zk proofs already operates over these finite fields.

By using these arithmetic circuits, the computation you are proving and the cryptography you are using to prove it speak the same language. This is the perfect alignment that avoids messy, inefficient conversion and makes the whole system fast and practical.

Conclusion: Setting Up Our Next Step
Let’s recap the journey.

  1. We started with P vs. NP and our Sudoku problem, discovering that NP’s secret is that its solutions are easy to verify.
  2. We learned that to formally verify a program, we must encode its rules into a circuit—a set of mathematical constraints.
  3. We saw that the intuitive Boolean Circuit (AND/OR/NOT) is a dead end because it’s horribly inefficient.
  4. We found the ZK standard: the Arithmetic Circuit (ADD/MUL), which is hyper-efficient and “aligns” perfectly with the underlying cryptography.

We now have our big-picture tool. We know that we must “flatten” any program we want to prove into a long, messy list of simple ADD/MUL equations. But… how? How do we organize this list in a standard, efficient way that a real ZK proving system can actually use?
That is the job of a Constraint System. In my next post, we’ll dive into Finite Fields and Modular Arithmetic, and later, we’ll move to constraint systems with all the required knowledge.