A Simple, Direct Reduction from Circuit SAT to Graph 3-Coloring

Table of Contents

1. What is the Point?
2. Structure of the Reduction
3. Proof for the OR Gadget
4. NOR, AND, NAND. XOR?
5. Related Work and Comparison to Other Approaches

What is the Point?

When introducing somebody to zero-knowledge for the first time, it's common to prove that there exists a zero-knowledge proof for the language of 3-colorable graphs, and then use the fact that graph 3-coloring is NP complete to conclude that zero-knowledge proofs exist for all NP languages. For example, both Goldreich and Pass and shelat take this approach in their cryptography textbooks. The zero-knowledge proof for 3-coloring is so simple that it can be understood by people with no background in computer science at all (physical commitments can easily be constructed using paper and tape, if necessary). The proof that graph 3-coloring is NP complete is much less intuitive, however.

The typical pathway for proving that graph 3-coloring is NP complete involves a reduction from any NP problem to SAT (i.e. the Cook-Levin theorem), then a reduction from SAT to 3SAT, and finally a reduction from 3SAT to graph 3-coloring. So far as I can tell, this chain of reductions is not usually taught in introductory cryptography classes, even when the zero-knowledge proof of graph 3-coloring is.

This document describes a direct reduction from CSAT to graph 3-coloring which is, to my mind, far easier and faster to teach than the traditional reduction chain. The purpose is not to replace the traditional reduction chain (which is often taught in introductory theory of computation courses), but to make it possible to teach zero-knowledge for all of NP without relying too much on prior knowledge. In other words, to make the whole topic accessible to those who have not yet taken (or do not remember) a theory of computation course.

CSAT is useful for this purpose because it captures the notion of computability intuitively even for those who do not yet understand NP completeness. In the real world, computers are made up of boolean circuits, and most people know this (although of course it is a gross oversimplification). It is quite natural to say that if you can prove a statement to a computer, then the computer verifies the proof by evaluating a boolean circuit on it.

I have tried to write the following document in a way that is reasonably understandable to beginners, without getting bogged down in preliminaries. Readers not familiar with CSAT or graph 3-coloring are invited to familiarize themselves with these ideas before continuing.

A Note on Novelty.

I do not claim that anything here is novel or surprising. I was unable to find this kind of reduction in the literature, but it may very well exist, and if it does, I would be very happy to know about it.

Structure of the Reduction

Our reduction will construct a graph 3-coloring problem for any boolean circuit (not just circuits that are valid CSAT instances). It will have the following invariants:

• For each wire in the circuit (or variable in the corresponding equation) there is exactly one vertex in the graph.
• For every proper 3-coloring of the graph, there is a valid assignment of the wires in the circuit (or variables in the equation) such that if a set of vertices are colored the same, then their corresponding wires assume the same value.
• For every valid assignment of the wires in the circuit (or variables in the equation), there is at least one proper 3-coloring of the graph such that if a set of wires assume the same value, then their corresponding vertices are colored the same.
• It is possible to construct a fixed, injective mapping between wire values and vertex colors.

In addition to the vertices corresponding to wires, our graph will include vertices representing constant values, and a number of additional helper vertices that grows in proportion to the number of gates in the circuit. Helper vertices do not correspond directly to anything in the circuit, and unlike the other vertices they may take on colors that do not correspond to logical values on specfic wires.

We will consider boolean circuits made up of NOT ($\neg$) an OR ($\vee$) gates, equality constraints ($=$), and constants ($\{\mathrm{0,1}\}$). This collection of primitives is complete for boolean computation, and we will represent circuits using equations made up of these primitives. If the final element of a circuit is an equality constraint with the constant 1 (i.e. it can be represented using an equation with 1 on the right hand side of the equals sign), then it is an instance of the CSAT problem, and valid assignments of the input wires (i.e. variables) for such a circuit is a witness that the circuit is satisfiable.

Establishing a Correspondence between Wire Values and Colors.

Since we wish to establish one-to-one mapping between the values that wires can assume and the colors of the corresponding vertices, we will begin by creating a set of color reference vertices corresponding to the values. We can then determine which color represents which value by observing the colors that the color-reference vertices assume. The wires of a boolean circuit have two possible values, and there are three possible colors in a 3-coloring problem. Thus, we must have a color that does map to a wire value. We will call this color (and its reference vertex) neither, and denote it $\mathrm{N}$. The three reference vertices are connected to one another in a triangle, forcing them to assume three distinct colors, as follows:

From now on, the logical value 0 will be represented by the color white, the logical value 1 will be represented by the color black, and the neither color will be blue. This is just a convention; any three colors will do.

Wires and NOT Gates.

For every wire in the circuit (without loss of generality, let us consider input wire $x$), we will create exactly one corresponding vertex in the graph. We will also create a vertex $\bar{x}$ representing the complement of $x$. We connect these two new vertices in a triangle with the $\mathrm{N}$ vertex, as follows:

Notice that in any valid 3-coloring, the vertices $x$ and $\bar{x}$ must assume different colors, neither of which is the color $\mathrm{N}$. In other words, we have implemented the simple circuit $\bar{x}=\neg x$, which contains only a NOT gate. There are two possible colorings of the above graph, which correspond to the rows in the truth table of a NOT gate:

Asserting Equality, or Forcing Wires to Assume Certain Values.

We can represent an equality constraint between two wires by connecting the vertex that corresponds to one of them to the vertex corresponding to the complement of the other. This also works with constant values. For example, the boolean equation $x=1$ is equivalent to the following 3-coloring problem, in which the 1 vertex must always be colored the same as the $x$ vertex in any proper coloring:

OR Gates.

Representing OR gates is somewhat trickier. In order to do so, we must introduce a set of helper vertices and arrange them into a gadget. In the following OR gadget graph, is equivalent to the gate $z=x\vee y$. In the next section, we prove that the proper colorings of this graph are equivalent to valid assignments of $\{x,y,z\}$.

The gadget above was found by exhaustive search and is one of 12 graphs with 3 helper vertices and 15 edges that meet the criteria of equivalence to and OR gate. No graph with fewer helper vertices or edges exists.

Putting it Together.

We can combine the above ideas to encode any boolean circuit as a graph 3-coloring problem, such that proper colorings correspond to valid assignments of the wires in the original circuit. For example, $x\vee \neg y=1$ can be encoded as a 3-coloring problem in the following way:

Since the above equation asserts equality with 1, it is a CSAT instance, which is satisfiable if and only if the above graph is 3-colorable. Indeed, the following coloring corresponds to $x=0,y=0$:

The above example includes only one gate of each type, and no wires beyond the inputs and outputs and their complements. For circuits that have an OR-depth greater than one, we must introduce vertices for the interior wires, in addition to the inputs and outputs. We never introduce more than one vertex per wire (plus one for its complement), however. For example, consider the circuit $z=w\vee (x\vee y)$, which has a single interior wire carrying the output of the parenthesized expression. If we name this interior wire $v$, then we can rewrite the circuit as $\{z=w\vee v,v=x\vee y\}$, and encode it as a 3-coloring problem in the following way:

In the above example, the two distinct OR gadget patterns are individually highlighted. Each has its own helper vertices, and the output vertex $v$ of one is also an input vertex of the other. For an additional example including several OR and NOT gates, see the construction of a graph for the XOR gate, below.

Proof for the OR Gadget

For the sake of clarity, we will flatten the OR gadget presented above and label the three helper vertices $\{a,b,c\}$. Thus for the one-gate circuit $z=x\vee y$, we have the following graph:

We will show that for every coloring of the vertices $\{x,y,z\}$ that corresponds to a row in the truth table of an OR gate, there exists a proper coloring of the entire gadget, and on the other hand, for every coloring of the vertices $\{x,y,z\}$ that does not correspond to a row in the truth table of an OR gate, there must be some vertex in the gadget that is adjacent to vertices of all three colors (and thus not itself properly colorable).

Consider the first row in the truth table of OR; i.e. consider the case that $x=y=z=0$. We have the following proper coloring which is consistent with this assignment of wire values:

On the other hand, $x=y=0$ and $z=1$ is not a row in the truth table of an OR gate. Notice that if we color the vertices in the corresponding way, then helper vertex $b$ is adjacent to both black and white vertices, and must therefore be blue. This implies that helper vertex $c$ is adjacent to vertices of all three colors, and the gadget is thus not 3-colorable:

Next, consider the case that $x=1$. In this case, $z=x\vee y$ implies $z=1$ regardless of the value of $y$. And indeed, the following coloring is proper whether the vertex corresponding to $y$ is colored black or white.

On the other hand, consider $x=1$ and $z=0$. Since no row in the truth table of OR has this combination of values, there should be no proper 3-coloring consistent with them, regardless of the value of $y$. If we color the vertices in the corresponding way, then helper vertex $b$ is adjacent to both black and white vertices, and again must be blue, which implies that vertex $a$ is adjacent to all three colors. This is true independently of the color of $y$, as expected.

This leaves only one row in the truth table of the OR gate, i.e. $y=z=1$ and $x=0$. And, as expected, we have a proper 3-coloring consistent with this assignment of wire values:

The final invalid assignment of variables is $x=z=0$ and $y=1$. If we color the vertices in the corresponding way, then helper vertex $b$ must be blue once again, and vertex $c$ is adjacent to vertices of all three colors.

We have now exhausted all of the possible boolean assignments of $\{x,y,z\}$ and shown that for each, then there exists a 3-coloring of the gadget consistent with that assignment if and only if $z=x\vee y$. It remains to rule out 3-colorings that are not consistent with any boolean assignment of the variables: in particular, we must rule out colorings where a vertex corresponding to a wire (or its complement) is blue. This is trivial, since all vertices that correspond to wires are adjacent to the $\mathrm{N}$ vertex by construction.

NOR, AND, NAND. XOR?

We now have a way to represent wires, constants, NOT gates, and OR gates. Since this collection of operations is complete for boolean computation, we can use it to reduce any boolean circuit to a graph coloring problem. We need not introduce anything more. Nevertheless, we will briefly explore graph gadgets for additional boolean gates.

Let us begin with AND. Because the OR gadget introduced above is exactly equivalent to an OR gate (regardless of the gate's output value), we can easily produce a gadget for the AND gate using De Morgan's Law:

Similarly efficient gadgets for NOR and NAND can be derived from the OR and AND gadgets respectively by replacing the output vertex with the vertex corresponding to the complement of the output.

Next, consider the circuit $z=x\oplus ︎y$, which contains a single XOR gate. Unfortunately, exhaustive search did not reveal an XOR gadget with 4 or fewer helper vertices and 17 or fewer edges. Searching any further rapidly becomes too computationally expensive. Instead, we will rewrite XOR in terms of NOT and OR gates, which gives us $z=x\oplus ︎y=(\bar{x}\wedge y)\vee (x\wedge \bar{y})=\neg (x\vee \bar{y})\vee \neg (\bar{x}\vee y)$. This rewriting introduces two intermediate wires (for the outputs of parenthesized expressions) and their complements, and when we use the above method to find an equivalent graph, that graph has 21 vertices (3 for the base colors, 1 for the output wire, 8 in total for the other 4 wires and their complements, and 9 helpers in total for 3 OR gates). Here is that graph:

Related Work and Comparison to Other Approaches

There are (so far as I know) two other approaches to showing the NP-completeness of 3-coloring. The first can be found in various online lecture notes for complexity and theory of computation courses, and seems to originate in Stockmeyer's 1973 paper Planar 3-colorability is Polynomial Complete, which was the first to prove the NP-completeness of 3-coloring. It relies first on reducing any NP-language to 3SAT, and then demonstrating that the following graph gadget is equivalent to a single 3SAT clause $w\vee x\vee y=1$:

Multiple clauses can be constructed by reusing the vertices that correspond to the variables, and the variables can be inverted using the same technique for complements/NOT gates discussed above. In this way, an entire 3SAT instance can be converted into an equivalent 3-coloring problem.

It is tempting to think this gadget might be equivalent to a three-input OR gate with five helper vertices, if only we eliminate the edge connecting the output vertex $z$ to the 0 vertex. Unfortunately, there is no such equivalence. Consider the case that $w=z=0$ and $x=y=1$. Although this is an invalid assignment of variables for three-input OR, there is nevertheless a proper 3-coloring:

It seems that the equality constraint between the output and 1 is necessary in Stockmeyer's 3SAT gadget, which means that it cannot be used to directly represent arbitrary circuits as graph-coloring problems. This motivates the OR gadget introduced above.

The second prior approach was introduced recently by Güngör in his paper, A Systematic Study of Single-Anchor Logical Gadgets. Whereas in the approach presented here, exactly one color maps to 0 and exactly one color maps to 1 (these are the two anchors), with all other colors mapping to no logical value at all, Güngör's approach maps one color to 0 (the single anchor), and all other colors to 1. Güngör develops gadgets for a many boolean gates, which are, as the author admits, somewhat larger and more complex than they might be in a two-anchor approach. Indeed, Güngör's OR gadget involves four helper vertices, whereas the one presented here requires only three. Moreover, the simplicity of a one-to-one mapping between vertex colors and wire values makes a two-anchor approach easy to teach and understand, even if, as Güngör claims, it is "unnatural from a graph-theoretic perspective."