Micali’s computationally sound proofs: hashing the verifier away (1994)

Micali made Kilian’s argument non-interactive: the queries are derived by hashing the Merkle root, so the prover can write the whole argument down at once, and anyone can check it later. If the hash behaves like a random oracle, the prover cannot predict which bits will be read before committing.

But it can try again. A cheating prover recommits (here, it changes a salt hashed with the root) until the derived queries happen to miss its lies. If one repetition catches a false proof with probability 1/2, the expected number of attempts is

\[\mathbb{E}[\text{attempts}] = 2^{k}\]

for \(k\) repetitions: the soundness of a non-interactive proof is a cost in hashing, which is why deployed systems target \(2^{100}\) or more.

import matplotlib.pyplot as plt

import blockchainkit as bk

An honest proof anyone can check

system = bk.proofs.QuadraticSystem(
    3, ((((0, 1), (2, 2)), 1), (((1, 2),), 0), (((0, 0), (1, 1)), 0))
)
honest = bk.proofs.micali_proof(system, bk.proofs.hadamard_proof([1, 1, 0]), repetitions=8)
assert bk.proofs.verify_cs_proof(system, honest, repetitions=8)
print(f"a CS proof of {len(honest.openings)} openings and {honest.size} bytes")

a CS proof of 112 openings and 36888 bytes

Grinding: a false proof, rehashed until the queries miss

false_proof = bk.proofs.hadamard_proof([1, 0, 1])  # Encodes a non-solution.
repetitions = range(1, 8)
attempts = []
for k in repetitions:
    tries = []
    for start in range(0, 6 * 2**k * 4, 6 * 2**k):  # Four independent searches.
        salt = start
        while not bk.proofs.verify_cs_proof(
            system,
            bk.proofs.micali_proof(system, false_proof, repetitions=k, salt=salt),
            repetitions=k,
        ):
            salt += 1
        tries.append(salt - start + 1)
    attempts.append(sum(tries) / len(tries))
    print(f"{k} repetitions: about {attempts[-1]:.0f} attempts to forge")
assert attempts[-1] > 8 * attempts[0]

fig, ax = plt.subplots(figsize=(7, 4.5))
ax.semilogy(repetitions, attempts, "o", color="#dc2626", label="measured, mean of 4 searches")
ax.semilogy(repetitions, [2**k for k in repetitions], color="#2563eb", label="2**k")
ax.set(xlabel="repetitions k", ylabel="attempts until a false proof passes")
ax.set_title("Non-interactive soundness is a price in hashes")
ax.legend()
fig.tight_layout()

plt.show()

1 repetitions: about 3 attempts to forge
2 repetitions: about 2 attempts to forge
3 repetitions: about 10 attempts to forge
4 repetitions: about 13 attempts to forge
5 repetitions: about 21 attempts to forge
6 repetitions: about 59 attempts to forge
7 repetitions: about 138 attempts to forge

Exercise

How many repetitions would make grinding cost 2**80 hashes, if every attempt rebuilds a 520-leaf Merkle tree? How many bytes is the proof then?