The PCP theorem: checking a proof by reading a few bits (1992)

Arora and Safra, and Arora, Lund, Motwani, Sudan and Szegedy, proved that every NP statement has a probabilistically checkable proof: a verifier tosses coins, reads a constant number of the proof’s bits, and accepts a correct proof always and an incorrect one with probability at most 1/2. Repeating drives the error down to \(2^{-k}\).

Its first ingredient is a proof that is exponentially long but very easy to check. To show that quadratic equations over GF(2) have a solution \(u\), write out every parity \(\langle u, x\rangle\) and every \(\langle u \otimes u, y\rangle\). The verifier checks with 14 queries that both tables are linear (the Blum-Luby-Rubinfeld test, \(f(x) + f(y) = f(x + y)\)), that the second is the tensor square of the first, and that a random sum of the equations holds.

import matplotlib.pyplot as plt

import blockchainkit as bk

A system with two solutions

u0 u1 + u2 = 1, u1 u2 = 0, and u0 + u1 = 0.

system = bk.proofs.QuadraticSystem(
    3, ((((0, 1), (2, 2)), 1), (((1, 2),), 0), (((0, 0), (1, 1)), 0))
)
print("solutions:", system.solutions())
proof = bk.proofs.hadamard_proof([1, 1, 0])
print(f"the proof has {len(proof.bits)} bits for a 3-bit witness")
assert all(bk.proofs.pcp_verify(system, proof, seed=s).accepted for s in range(200))

solutions: ((0, 0, 1), (1, 1, 0))
the proof has 520 bits for a 3-bit witness

Wrong proofs are caught with constant probability per repetition

wrong_assignment = bk.proofs.hadamard_proof([1, 0, 1])  # Well formed, but not a solution.
corrupted_bits = list(proof.bits)
for i in range(8, 520, 3):
    corrupted_bits[i] ^= 1  # A third of the quadratic table flipped.
corrupted = bk.proofs.HadamardProof(tuple(corrupted_bits[:8]), tuple(corrupted_bits[8:]))
unsatisfiable = bk.proofs.QuadraticSystem(2, ((((0, 0),), 1), (((0, 0),), 0)))

repetitions = range(1, 9)
cases = {
    "non-solution, encoded correctly": (system, wrong_assignment),
    "solution, one third corrupted": (system, corrupted),
    "unsatisfiable system": (unsatisfiable, bk.proofs.hadamard_proof([1, 0])),
}
rates = {}
for label, (statement, candidate) in cases.items():
    rates[label] = [
        sum(
            bk.proofs.pcp_verify(statement, candidate, repetitions=k, seed=s).accepted
            for s in range(400)
        )
        / 400
        for k in repetitions
    ]
    print(
        f"{label}: accepted {rates[label][0]:.0%} with 14 queries, {rates[label][-1]:.1%} with 112"
    )
    assert rates[label][-1] < 0.05

fig, ax = plt.subplots(figsize=(7, 4.5))
for (label, rate), color in zip(rates.items(), ("#2563eb", "#dc2626", "#16a34a"), strict=True):
    ax.semilogy(
        [14 * k for k in repetitions], [max(r, 1e-3) for r in rate], "o-", color=color, label=label
    )
ax.semilogy(
    [14 * k for k in repetitions], [0.5**k for k in repetitions], "k:", label="1 / 2 per repetition"
)
ax.set(xlabel="proof bits read", ylabel="probability a wrong proof is accepted")
ax.set_title("A Hadamard PCP read a few bits at a time")
ax.legend()
fig.tight_layout()

plt.show()

non-solution, encoded correctly: accepted 55% with 14 queries, 0.2% with 112
solution, one third corrupted: accepted 21% with 14 queries, 0.0% with 112
unsatisfiable system: accepted 49% with 14 queries, 0.5% with 112

Exercise

A Hadamard proof for n variables has 2**n + 2**(n**2) bits. For n = 10, how many bits is that, and how many does the verifier read for an error below one in a million, assuming each repetition halves it? A worked solution is in Exercises: proof systems.