toxic-waste-forgery.ipynb

Kernel: SageMath 10.0

Break: Forging Proofs with Compromised Trusted Setup

Module 10 | Breaking Weak Parameters

If the toxic waste from a Groth16 ceremony leaks, anyone can forge proofs for false statements.

Why This Matters

Groth16 requires a trusted setup ceremony that generates a Common Reference String (CRS) from secret randomness called the toxic waste ($\tau, \alpha, \beta, \gamma, \delta$). After the CRS is published, the toxic waste must be destroyed.

If anyone retains the toxic waste, they can forge valid-looking proofs for any statement, true or false. This completely breaks the soundness of the proof system:

Property	With destroyed toxic waste	With leaked toxic waste
Soundness	Computationally sound	Broken
Zero-knowledge	Yes	Yes (irrelevant, attacker doesn't need ZK)
Completeness	Yes	Yes

Your task: given the toxic waste, forge a Groth16 proof that a false statement is true.

The Scenario

Consider a simple R1CS constraint: prove knowledge of $x$ such that $x^2 = 9$ over $\mathbb{F}_{101}$.

An honest prover has witness $x = 3$ (since $3^2 = 9$). We will:

1. Set up a Groth16-style CRS with toxic waste

2. Show an honest proof with witness $x = 3$

3. Forge a proof claiming $x = 5$ satisfies $x^2 = 9$ (it doesn't: $5^2 = 25 \neq 9$)

4. Verify that the forged proof passes the verification equation

We work in $\mathbb{F}_{101}$ and simulate the pairing check algebraically using exponent arithmetic. The key insight: the Groth16 pairing equation $e(A, B) = e(\alpha G_1, \beta G_2) \cdot e(\text{pub}, \gamma G_2) \cdot e(C, \delta G_2)$ reduces to a scalar equation $a \cdot b \equiv \alpha \cdot \beta + \text{pub\_term} + c \cdot \delta \pmod{q}$ in the exponent.

# === Setup: work in F_101 ===
p = 101
F = GF(p)

# Our R1CS constraint: x^2 = 9
# Variables: z = (1, x, x^2)
# Constraint: (0*1 + 1*x + 0*x^2) * (0*1 + 1*x + 0*x^2) = (0*1 + 0*x + 1*x^2)
# Plus a public output constraint: x^2 = 9, i.e., z[2] = 9

# The R1CS matrices (single constraint: x * x = x^2)
# A_mat = [0, 1, 0]  (selects x)
# B_mat = [0, 1, 0]  (selects x)
# C_mat = [0, 0, 1]  (selects x^2)

A_vec = vector(F, [0, 1, 0])
B_vec = vector(F, [0, 1, 0])
C_vec = vector(F, [0, 0, 1])

# Honest witness: x = 3, x^2 = 9
x_honest = F(3)
z_honest = vector(F, [1, x_honest, x_honest^2])  # (1, 3, 9)

print(f"Field: F_{p}")
print(f"Constraint: x * x = x^2, with public output x^2 = 9")
print(f"Honest witness: z = {list(z_honest)}")
print(f"Check: A.z * B.z = {A_vec.dot_product(z_honest)} * {B_vec.dot_product(z_honest)} = {A_vec.dot_product(z_honest) * B_vec.dot_product(z_honest)}")
print(f"       C.z = {C_vec.dot_product(z_honest)}")
print(f"Satisfied? {A_vec.dot_product(z_honest) * B_vec.dot_product(z_honest) == C_vec.dot_product(z_honest)}")

Step 1: Groth16 Trusted Setup (with toxic waste)

The setup ceremony generates secret random values and computes the CRS. We simulate the full Groth16 verification equation in the exponent.

The Groth16 verification equation (simplified for one constraint) is:

$$a \cdot b = \alpha \cdot \beta + \text{pub} \cdot \gamma^{-1} \cdot \gamma + c \cdot \delta$$

which simplifies to: $a \cdot b = \alpha \cdot \beta + \text{pub\_term} + c \cdot \delta$

The prover computes scalars $a$, $b$, $c$ (which become curve points in the real protocol), and the verifier checks this equation using pairings.

# === Trusted Setup: generate toxic waste ===
set_random_seed(42)

# Toxic waste: secret random field elements
alpha = F.random_element()
while alpha == 0:
    alpha = F.random_element()
beta = F.random_element()
while beta == 0:
    beta = F.random_element()
gamma = F.random_element()
while gamma == 0:
    gamma = F.random_element()
delta = F.random_element()
while delta == 0:
    delta = F.random_element()
tau = F.random_element()
while tau == 0:
    tau = F.random_element()

print("=== TOXIC WASTE (must be destroyed!) ===")
print(f"  alpha = {alpha}")
print(f"  beta  = {beta}")
print(f"  gamma = {gamma}")
print(f"  delta = {delta}")
print(f"  tau   = {tau}")

# CRS elements (what's published):
# In the real protocol these are elliptic curve points.
# Here we work with the scalar exponents directly.

# For the QAP evaluated at tau:
# L(tau) encodes how public inputs enter the verification equation
# For our constraint, the QAP polynomials evaluated at tau give:
A_tau = A_vec.dot_product(vector(F, [1, tau, tau^2]))  # A polynomial at tau
B_tau = B_vec.dot_product(vector(F, [1, tau, tau^2]))  # B polynomial at tau
C_tau = C_vec.dot_product(vector(F, [1, tau, tau^2]))  # C polynomial at tau

print(f"\nQAP evaluations at tau:")
print(f"  A(tau) = {A_tau}, B(tau) = {B_tau}, C(tau) = {C_tau}")

# The CRS includes alpha*beta, gamma, delta, and encoded QAP values
# (In practice, these are curve points; we track scalars.)
alpha_beta = alpha * beta
print(f"\nCRS verification element: alpha*beta = {alpha_beta}")

# === Step 2: Honest Proof (witness x = 3) ===

# The honest prover has the witness z = (1, 3, 9)
# They compute proof elements a, b, c such that:
#   a * b = alpha*beta + pub_term + c * delta
#
# In simplified Groth16:
#   a = alpha + A(tau)  (the "left" proof element)
#   b = beta + B(tau)   (the "right" proof element)
#   c encodes the quotient polynomial H(tau) and the witness

# For the honest prover:
# The QAP equation: A(tau)*B(tau) - C(tau) = H(tau)*Z(tau)
# where Z(tau) is the vanishing polynomial

# Simplified: prover constructs a, b, c from the witness
# We use the witness-dependent computation
wit_A = A_vec.dot_product(z_honest)  # = x = 3
wit_B = B_vec.dot_product(z_honest)  # = x = 3
wit_C = C_vec.dot_product(z_honest)  # = x^2 = 9

# Proof elements (simplified Groth16)
a_honest = alpha + wit_A
b_honest = beta + wit_B

# The public input term: the verifier knows x^2 = 9
# In Groth16, public inputs are separated from the proof
pub_input_val = F(9)  # the public output x^2 = 9

# c is chosen so the verification equation holds:
# a * b = alpha*beta + pub_term + c * delta
# => c = (a*b - alpha*beta - pub_term) / delta
pub_term = pub_input_val  # simplified encoding of public input
c_honest = (a_honest * b_honest - alpha_beta - pub_term) * delta^(-1)

print("=== Honest Proof (x = 3, x^2 = 9) ===")
print(f"  Proof element a = {a_honest}")
print(f"  Proof element b = {b_honest}")
print(f"  Proof element c = {c_honest}")

# Verify: a * b == alpha*beta + pub_term + c * delta
lhs = a_honest * b_honest
rhs = alpha_beta + pub_term + c_honest * delta
print(f"\nVerification: a*b = {lhs}")
print(f"              alpha*beta + pub + c*delta = {rhs}")
print(f"              Valid proof? {lhs == rhs}")

Step 3: Forge a Proof for a FALSE Statement

Now suppose the attacker has the toxic waste ($\alpha, \beta, \gamma, \delta, \tau$).

The attacker wants to prove: "I know $x = 5$ such that $x^2 = 9$."

This is false: $5^2 = 25 \neq 9$ in $\mathbb{F}_{101}$.

Without the toxic waste, the attacker cannot produce valid proof elements because the QAP divisibility check would fail. But with the toxic waste, the attacker can directly compute $a$, $b$, $c$ that satisfy the verification equation for any claimed public output.

# === Step 3: Forge a proof for x=5 satisfying x^2=9 (FALSE!) ===

x_fake = F(5)
print(f"Attacker claims x = {x_fake}")
print(f"Reality: x^2 = {x_fake^2} != 9")
print(f"This is a FALSE statement!\n")

# The attacker still claims the public output is 9
pub_term_fake = F(9)  # lying about the output

# With toxic waste, the attacker can pick ANY a, b and solve for c:
# Just need a*b = alpha*beta + pub_term + c*delta
# Pick a and b freely (no constraint from the witness!)
a_forged = F(42)  # arbitrary choice
b_forged = F(73)  # arbitrary choice

# Solve for c using the toxic waste (knowing delta)
c_forged = (a_forged * b_forged - alpha_beta - pub_term_fake) * delta^(-1)

print("=== Forged Proof (x = 5, claiming x^2 = 9) ===")
print(f"  Proof element a = {a_forged}  (chosen freely)")
print(f"  Proof element b = {b_forged}  (chosen freely)")
print(f"  Proof element c = {c_forged}  (computed using delta^(-1))")

# Verify the forged proof
lhs_forged = a_forged * b_forged
rhs_forged = alpha_beta + pub_term_fake + c_forged * delta
print(f"\nVerification: a*b = {lhs_forged}")
print(f"              alpha*beta + pub + c*delta = {rhs_forged}")
print(f"              Valid proof? {lhs_forged == rhs_forged}")
print(f"\nThe FORGED proof PASSES verification!")
print(f"The verifier accepts that x^2 = 9, even though the 'witness' x=5 is wrong.")

# === Step 4: Why this works ===

# The verification equation is: a*b = alpha*beta + pub_term + c*delta
#
# Without toxic waste: the prover must construct a, b, c from the CRS
# (curve points). They can compute a = alpha + witness_stuff and
# b = beta + witness_stuff, but they CANNOT freely choose c because
# they don't know delta as a scalar, only [delta]_2 as a curve point.
#
# With toxic waste: delta is known as a SCALAR, so the attacker can
# solve c = (a*b - alpha*beta - pub_term) / delta for ANY a, b.

print("=== Why the Forgery Works ===")
print()
print("Without toxic waste (curve points only):")
print("  Prover has:  [alpha]_1, [beta]_2, [delta]_2")
print("  Prover can:  compute [a]_1 = [alpha]_1 + [witness*stuff]_1")
print("  Prover CANNOT: solve for [c]_1 because dividing by [delta]_2")
print("                 requires knowing delta as a scalar.")
print()
print("With toxic waste (scalars known):")
print(f"  Attacker knows: delta = {delta}")
print(f"  Attacker computes: delta^(-1) = {delta^(-1)}")
print(f"  c = (a*b - alpha*beta - pub) * delta^(-1)")
print(f"    = ({a_forged * b_forged} - {alpha_beta} - {pub_term_fake}) * {delta^(-1)}")
print(f"    = {(a_forged * b_forged - alpha_beta - pub_term_fake)} * {delta^(-1)}")
print(f"    = {c_forged}")
print()
print("The CRS hides the algebraic structure behind the DLP.")
print("Knowing the secrets bypasses that protection entirely.")

The Fix: Multi-Party Computation Ceremonies

In practice, Groth16 ceremonies use MPC (multi-party computation) so that the toxic waste is never held by a single party:

1. Participant 1 generates $\tau_1$, computes $[\tau_1]$ on curve points, passes to next

2. Participant 2 generates $\tau_2$, updates to $[\tau_1 \cdot \tau_2]$, passes on

3. $\ldots$ continue for $N$ participants

4. Final CRS encodes $\tau = \tau_1 \cdot \tau_2 \cdots \tau_N$

Security guarantee: as long as any single participant destroys their share, the combined toxic waste is unrecoverable. Zcash's Sapling ceremony had hundreds of participants across the world.

Alternatively, use transparent proof systems (STARKs, Bulletproofs) that need no trusted setup at all.

# === Exercises ===

# Exercise 1: Forge a proof for the statement x^2 = 50 (any x)
# There is NO x in F_101 with x^2 = 50? Let's check.
print("Exercise 1: Is there any x in F_101 with x^2 = 50?")
solutions = [x for x in range(101) if F(x)^2 == F(50)]
print(f"  Solutions: {solutions}")
has_solution = len(solutions) > 0
print(f"  Solvable? {has_solution}")
print()

# Forge a proof regardless!
pub_ex1 = F(50)
a_ex1 = F(10)  # arbitrary
b_ex1 = F(20)  # arbitrary
c_ex1 = (a_ex1 * b_ex1 - alpha_beta - pub_ex1) * delta^(-1)

lhs_ex1 = a_ex1 * b_ex1
rhs_ex1 = alpha_beta + pub_ex1 + c_ex1 * delta
print(f"Forged proof for x^2 = 50:")
print(f"  a = {a_ex1}, b = {b_ex1}, c = {c_ex1}")
print(f"  Verification: {lhs_ex1} == {rhs_ex1}? {lhs_ex1 == rhs_ex1}")
print(f"  The forged proof passes even if x^2=50 is {'solvable' if has_solution else 'UNSOLVABLE'}!")

# Exercise 2: Forge proofs for multiple different false claims using the same CRS
print("Exercise 2: Forge proofs for various false statements\n")

false_claims = [0, 1, 7, 42, 99]  # claim x^2 equals these values

for claim in false_claims:
    pub_val = F(claim)
    # Pick random a, b
    a_val = F.random_element()
    while a_val == 0:
        a_val = F.random_element()
    b_val = F.random_element()
    while b_val == 0:
        b_val = F.random_element()
    c_val = (a_val * b_val - alpha_beta - pub_val) * delta^(-1)
    
    verified = (a_val * b_val == alpha_beta + pub_val + c_val * delta)
    actual_roots = [x for x in range(101) if F(x)^2 == pub_val]
    
    print(f"  Claim: x^2 = {claim}  |  Real solutions: {str(actual_roots)}  |  Forged proof valid? {verified}")

print(f"\nWith toxic waste, the attacker can prove ANY statement, true or false.")
print(f"This is a TOTAL break of soundness.")

Summary

Aspect	Without toxic waste	With toxic waste
Proof construction	Must use valid witness	Can pick arbitrary $a, b$, solve for $c$
Key operation	Cannot compute $c$ (DLP hides $\delta$)	$c = (a \cdot b - \alpha\beta - \text{pub}) \cdot \delta^{-1}$
Soundness	Computationally sound	Completely broken
False statement proofs	Impossible (with overwhelming probability)	Trivially constructible

Key takeaways:

• Groth16 soundness relies entirely on the secrecy of the toxic waste.

• Knowing $\delta$ (or any of $\alpha, \beta, \gamma, \delta, \tau$) lets you bypass the constraint check.

• MPC ceremonies distribute trust: only one honest participant needed.

• Transparent systems (STARKs, Bulletproofs) eliminate this attack vector entirely.

---

Back to Module 10: SNARKs and STARKs