A PCP verifier for graph 3-coloring

An untrusted prover claims that a graph is 3-colorable, and provides a claimed proof. The verifier wants to check that the proof is correct, but only wants to read a constant number of bits of the proof.

1. Configuration

Choose a graph: Vertices:

Cheating strategy:

The cheating strategy is used only when the graph is not 3-colorable. The verifier is random, so it is run 100 times, to see how often it can catch a wrong proof.

2. Input graph

3. Prover

The proof consists of eight oracle tables. An oracle is simply a large table of bits that the verifier may query at a few chosen positions. They have three different roles.

One coloring oracle

Oracle	Purpose
`chi` (χ)	Encodes the prover's claimed color for every vertex as a low-degree polynomial.

Two proof-of-correctness oracles

Oracle	Purpose
`A0` (A₀)	Certifies that χ assigns every vertex one of the three allowed colors.
`B0` (B₀)	Certifies that the endpoints of every edge receive different colors.

Five supporting oracles

These let the verifier check that the three main oracles above have the promised algebraic form, without reading them in full.

Oracle	Purpose
`chi_lines`	Supplies restrictions of χ to algebraic lines, allowing the verifier to test its degree and locally correct an answer.
`chi_prime` (χ′)	Encodes the derived function χ′(x,y) = χ(x) − χ(y), which is used to compare the colors at two vertices.
`chi_prime_lines`	Supplies line restrictions used to test and locally correct χ′.
`A0_lines`	Supplies line restrictions used to test and locally correct the certificate A₀.
`B0_lines`	Supplies line restrictions used to test and locally correct the certificate B₀.

4. Verifier

The first random round is shown step by step.

Does every oracle have the correct degree-3 Hadamard encoding?
At random inputs, the verifier applies degree-3 Hadamard tests to check that each binary table really encodes the value of a function F_q^k → F_q, rather than being an arbitrary table of bits.
Oracles used: chi, chi_lines, chi_prime, chi_prime_lines, A0, A0_lines, B0, and B0_lines.
Do the oracles represent low-degree polynomials?
The verifier compares each of χ, χ′, A₀, and B₀ with its supporting line oracle. It checks that random line restrictions have the required degree, uses local correction when reading them, and checks that chi_prime agrees with χ(x) − χ(y).
Oracles used: the four pairs chi/chi_lines, chi_prime/chi_prime_lines, A0/A0_lines, and B0/B0_lines. The consistency check also uses chi together with chi_prime.
Does A₀ prove that χ uses only the three allowed colors?
A zero-on-grid test checks the polynomial identity certified by A₀. On the points representing vertices, this identity says that every value of χ belongs to {1, ω, ω²}.
Oracles used: chi, A0, and A0_lines. The line oracle is used to test and locally correct the certificate.
Does B₀ prove that adjacent vertices have different colors?
A second zero-on-grid test uses B₀, the graph's edge function, and χ′. It checks that whenever two vertices are adjacent, their color difference is nonzero. It does not prescribe which of the three colors either endpoint must receive.
Oracles used: chi_prime, B0, and B0_lines, together with the graph's fixed edge function. Step 2 has already tied chi_prime to chi.

The verifier has not run yet.

0/100

5. Result

Generate a graph and run the verifier.

Cheating prover strategies

If the graph is not 3-colorable, the cheating prover submits a false proof based on the strategy selected above. For a 3-colorable graph, the prover is always honest and the selected cheating strategy is ignored.

Closest 3-coloring: Use only the three allowed colors and minimize the number of monochromatic edges. In the generated non-3-colorable examples, exactly one edge is bad. The A₀ check passes, while a B₀ check rejects if it samples the hidden bad edge.
Closest 4-coloring: While the graph is not 3-colorable, a 4-coloring might exist. Properly color every edge using four colors. The B₀ edge check passes, but A₀ rejects when it finds a vertex carrying the forbidden fourth color.
Corrupt the encoding on selected entries: Start with the closest 3-coloring proof, but flip the bits at a fixed small fraction of positions in its Hadamard-encoded oracle tables. In this browser model, 8% of the encoded positions are corrupted. A degree-3 Hadamard test rejects when its random spot-check encounters one of these positions. If the corruption is missed, the B₀ test may still find the bad edge in the underlying closest 3-coloring.

How does the encoding work?

Before encoding, the entries of the oracles are elements of \(\mathbb{F}_q\), where \(q=2^t\). One field element therefore takes \(t=\log_2 q\) bits to write down, which is already more than the verifier is allowed to read. An entry of a line-table oracle contains even more information: it describes a univariate polynomial of degree \(D\) over \(\mathbb{F}_q\).

The four main algebraic objects \(\chi,\chi',A_0,B_0\) are encoded using the degree-3 Hadamard encoding. Fix an \(\mathbb{F}_2\)-linear identification \(\rho:\mathbb{F}_q\to\mathbb{F}_2^t\). For a field element \(a\in\mathbb{F}_q\), its encoding records \(P(\rho(a))\) for every polynomial \(P\in\mathcal{P}_3(t,\mathbb{F}_2)\). Thus every encoded position is a single bit, even though it represents information about an element of \(\mathbb{F}_q\).

This code has constant relative distance. Consequently, the verifier can distinguish two different field elements and test whether a submitted table has the required Hadamard form by reading only a constant number of bits.

For the line tables, the coefficient vector of each degree-\(D\) univariate polynomial is first transformed into a constant-degree multivariate polynomial using the map \(\Psi\). The values of that polynomial are then degree-3 Hadamard encoded in the same way. This lets the verifier combine low-degree tests and local correction with only a constant number of oracle queries, at the cost of a small increase in randomness.