Proving Graph 3-Coloring with Go and Zero-Knowledge Proofs

Edward Wibowo, May 15 2024

The 3-color problem asks whether there exists a proper coloring of a graph that uses at most $3$ colors. Symbolically, a given graph $G$ is 3-colorable if there exists a coloring

\phi : V(G) \rightarrow \{0, 1, 2\}

such that for every edge $uv \in E(G)$ , $\phi(u) \neq \phi(v)$ [2]. This is an interesting problem in the realm of computer science because it is NP-complete, meaning that it is computationally intractable to solve in polynomial time and any NP problem is polynomial-time reducible to it [1].

Zero-knowledge proofs (ZKP) are a way of proving the validity of a statement without revealing any information about the statement itself. In relation to the 3-color problem, a ZKP can be used to prove that a graph is 3-colorable without revealing the actual coloring of the graph.

For example, suppose we have a prover $P$ and a verifier $V$ . $P$ wants to prove to $V$ that a graph $G$ is 3-colorable. One way that $P$ can do this is by simply showing $V$ a valid 3-coloring of $G$ . Another way $P$ can do this is by using a ZKP to prove that $G$ is 3-colorable without revealing the actual coloring. If $P$ knows a proper 3-coloring of $G$ , the protocol will increase $V$ ‘s confidence that $G$ is 3-colorable without revealing $P$ ‘s 3-coloring.

Since 3-coloring is NP-complete, a ZKP for 3-coloring implies that there exists a ZKP for any NP problem. To do so, we can simply take the NP problem, reduce it to 3-coloring (which is valid since 3-coloring is NP-complete), and then use the ZKP for 3-coloring to prove the validity of the NP problem.

Project Overview

The project produces two binaries: one for the prover and one for the verifier.

The verifier is a server and takes as input the port number to listen on (TCP) and the number of rounds to run the protocol.
The prover is a client and takes as input the IP address of the verifier, the port number to connect to, and the graph to prove.

The project was implemented in Go because it has many built-in cryptographic libraries and supports networking out of the box. The choice of language, however, is not crucial to the implementation of the protocol.

Example Usage

For this example, the following graph and coloring will be used:

This graph is encoded as a text file:

0 red
1 red
2 green

0 1
1 2
2 0

After running

./verifier -port 1234 -repetitions 1000 and
./prover -address localhost -port 1234 -graph graphs/improper-c3.txt,

the output will look something like this:

❌ Summary: 311 failed out of 1000

In the graph, exactly one out of the three edges has vertices with the same color. So, assuming the verifier picks edges randomly, the prover should fail about one third of the time.

Commitment Scheme

We used SHA-256 as our commitment scheme. Although this isn’t a true random oracle, it is a cryptographic hash function that is widely used and is considered secure. It meets the requirements for being a commitment scheme because it is both hiding and binding.

Hiding: the output hash value does not reveal any information about the input message. It is seemingly random.
Binding: it is computationally infeasible to find two different messages that hash to the same value. This is a consequence of the collision resistance property of cryptographic hash functions.

This commitment scheme is used to commit to a coloring of a graph. So, for some graph $G$ and vertex $v \in V(G)$ , we define

c_v = \text{SHA-256}(\pi(\phi(v)) \text{ } || \text{ } r_v)

where $\pi$ is a permutation of the colors, $\phi$ is a coloring, and $r_v$ is a random key.

This functionality is implemented as follows:

func commit(color string, r int64) [32]byte {
    rBytes := make([]byte, 8)
    binary.LittleEndian.PutUint64(rBytes, uint64(r))
    hash := sha256.Sum256([]byte(color + string(rBytes)))
    return hash
}

The Protocol

The entire protocol can be summarized as follows:

In particular, the prover must first send the graph $G$ and the verifier will then send back the number of repetitions. During this preparation phase, the graph’s coloring is never sent over the TCP connection. Also the prover generates new commitments and permutes the colors for each repetition.

After each repetition, the verifier checks the following conditions:

$c_u = \text{SHA-256}(\pi(\phi(u)) \text{ } || \text{ } r_u)$ ,
$c_v = \text{SHA-256}(\pi(\phi(v)) \text{ } || \text{ } r_v)$ ,
$\pi(\phi(u)) \neq \pi(\phi(v))$ ,
and $\pi(\phi(u)), \pi(\phi(v)) \in \{\texttt{"red"}, \texttt{"green"}, \texttt{"blue"}\}$ .

If all of these conditions are met, the prover is considered to have passed the repetition.

Benchmarks

There are multiple factors that may contribute to the time it takes to run the protocol. For example:

Graph size: larger graphs (with more vertices and edges) will take longer parse, serialize/deserialize, and commit.
Number of repetitions: more repetitions will take longer.

The protocol was run multiple times for each trial to test the effect of these factors.

Varying Graph Size

The protocol was ru: $100,000$ times on a proper 3-colored Petersen graph (also known as a Kneser graph with $K(5,2)$ ) and a proper 3-colored $C_3$ . Results are shown in the table below.

Graph	Number of Repetitions	Time (s)
$C_3$	100,000	4.071
$K(5,2)$	100,000	6.640

These findings confirm our expectations that larger graphs (meaning more vertices/edges) take longer to run the protocol. The increase in time may be due to increased time to serialize/deserialize the graph and generate commitments.

Varying Number of Repetitions

An improper coloring of $C_3$ was run for different numbers of repetitions. Results are shown in the table below.

Number of Repetitions	Time (s)
100	0.011
1,000	0.053
10,000	0.420
100,000	4.115
1,000,000	41.509

As expected, the time to run the protocol increases with the number of repetitions.

Conclusion

This project implements a protocol where a prover can prove to a verifier that a graph is 3-colorable without revealing the actual coloring. The implementation leverages a custom graph library, networking protocol over TCP, and scalable ZKP protocol that can be repeated multiple times to increase the verifier’s confidence in the proof.

The benchmarks indicate that the time to run the protocol increases with the size of the graph and the number of repetitions. At its current state, the ZKP protocol can handle $1$ million iterations in less than a minute on a standard machine.

Bibliography

[1] M. Sipser. Introduction to the theory of computation. Cengage Learning, Australia Brazil Japan Korea Mexiko Singapore Spain United Kingdom United States, third edition, international edition edition, 2013.

[2] D. B. West. Introduction to graph theory. Prentice Hall, Upper Saddle River, N.J, 2nd ed edition, 2001.