Succinct GKR Protocol

Exploring how the GKR Protocol can be made succinct, creating a SNARK

Making the GKR Protocol Succinct with Multilinear KZG Commitments

In the world of verifiable computation, ensuring that a computation has been performed correctly without re-executing it is a game-changer, especially for large datasets or complex circuits. The GKR protocol, named after Goldwasser, Kalai, and Rothblum, is a well-known interactive proof system that achieves this goal. However, its practicality is limited by the proof size, which grows with the depth of the computation circuit. In this article, I’ll share my recent findings on making the GKR protocol succinct by integrating the multilinear KZG polynomial commitment scheme, an approach I’ve implemented in Rust. This enhancement significantly reduces the proof size, making verifiable computation more efficient and scalable.

Introduction to Verifiable Computation and the GKR Protocol

Verifiable computation allows a prover to convince a verifier that a computation—say, evaluating a circuit—was performed correctly, without the verifier needing to redo the work. The GKR protocol is particularly effective for this, as it verifies computations layer by layer using a technique called the sum-check protocol. It’s especially useful for arithmetic circuits, where gates perform addition or multiplication over a finite field.

In the standard GKR protocol, the prover breaks down the circuit into layers, starting from the output and working back to the inputs. For each layer, the prover sends intermediate values (witnesses) and engages in a sum-check protocol to prove their correctness. The verifier checks these proofs recursively until reaching the input layer. While powerful, this approach has a drawback: the proof size grows linearly with the circuit’s depth, as the prover must send witness evaluations for each layer. For deep circuits, this becomes impractical.

A succinct proof system, by contrast, aims to keep the proof size small—ideally polylogarithmic in the computation size—while ensuring verification remains efficient. My solution leverages polynomial commitments to achieve this succinctness, specifically the multilinear KZG scheme, which I’ve integrated into the GKR protocol and implemented in Rust.

Background: Understanding the Components

The GKR Protocol

The GKR protocol operates on an arithmetic circuit with layers of gates. Each layer’s output is expressed as a multilinear polynomial, and the protocol verifies these polynomials recursively:

• Output Layer: The prover asserts the circuit’s output, represented as a multilinear extension $( w_0(x) )$.

• Intermediate Layers: For each layer $( i )$, the prover uses the sum-check protocol to reduce the verification of $( w_i(x) )$ to evaluations of the next layer’s polynomial $( w_{i+1}(x) )$.

• Input Layer: The verifier checks the final evaluations against the circuit’s input.

The sum-check protocol ensures that a claimed sum over a polynomial matches its evaluations at random points, chosen via a Fiat-Shamir transcript for non-interactivity. However, in the standard implementation (as shown in the provided Rust code), the prover sends evaluations $( w_i(b) )$ and $( w_i(c) )$ for each layer, contributing to a proof size proportional to the number of layers.

The Multilinear KZG Polynomial Commitment Scheme

The KZG (Kate-Zaverucha-Goldberg) commitment scheme allows a prover to commit to a polynomial and later open it at specific points, with the verifier checking these openings efficiently. The multilinear version is tailored for polynomials over multiple variables, making it ideal for GKR, where witness polynomials are multilinear extensions of circuit values.

In this scheme:

• Commitment: Given a multilinear polynomial $( p(x_1, ..., x_n) )$ and a structured reference string (SRS) from a trusted setup, the prover computes a commitment in a pairing-friendly elliptic curve group (e.g., $( G_1 )$).

• Opening: To prove $( p(z) = v )$ at point $( z )$, the prover generates an opening proof, typically a single group element.

• Verification: The verifier uses the commitment, the point $( z )$, the value $( v )$, and the opening proof to check consistency, leveraging a pairing check.

This scheme’s efficiency—small commitments and proofs—makes it a perfect fit for compressing GKR proofs.

The Succinct GKR Protocol: How It Works

My approach modifies the GKR protocol by replacing large witness evaluations with compact polynomial commitments. Here’s the high-level idea: instead of sending entire witness polynomials or their evaluations for each layer, the prover commits to these polynomials using the multilinear KZG scheme and provides openings only where needed. This reduces the proof size dramatically.

Protocol Steps

1. Commitment to the Input:

   • The prover interpolates the circuit’s input into a multilinear polynomial $( w_{in}(x) )$.

   • Using the multilinear KZG scheme and an SRS, the prover computes a commitment $( C_{in} )$ and sends it to the verifier.

   • This commitment is appended to the Fiat-Shamir transcript for soundness.

2. Layer-by-Layer Verification:

   • Start with the output layer’s polynomial $( w_0(x) )$, evaluated at a random point $( n_r )$ from the transcript.

   • For each layer $( i )$ (from output to the second-to-last layer):

     • Use the sum-check protocol to verify the layer’s correctness, reducing the claim about $( w_i )$ to evaluations of $( w_{i+1} )$ at points $( r_b )$ and $( r_c )$.

     • Instead of sending $( w_{i+1}(r_b) )$ and $( w_{i+1}(r_c) )$ directly, store them for intermediate layers.

   • The verifier checks each sum-check proof, updating the claim and random points.

3. Final Layer with Openings:

   • At the last layer (before the input), the prover commits to the witness polynomial $( w_{n-1}(x) )$.

   • For the sum-check points $( r_b )$ and $( r_c )$, the prover computes:

     • $( w_{n-1}(r_b) )$ and its KZG opening proof.

     • $( w_{n-1}(r_c) )$ and its KZG opening proof.

   • These openings and proofs are sent as part of the final proof.

4. Verification at the Input Layer:

   • The verifier uses the KZG scheme to check that:

     • $( w_{n-1}(r_b) )$ matches the opening against $( C_{in} )$.

     • $( w_{n-1}(r_c) )$ matches the opening against $( C_{in} )$.

   • Compute the expected claim: $( \alpha \cdot w_{n-1}(r_b) + \beta \cdot w_{n-1}(r_c) )$, where $( \alpha )$ and $( \beta )$ are from the transcript.

   • Verify it equals the final sum-check claim.

Why It’s Succinct

In the standard GKR protocol, the proof includes evaluations $( w_i(b) )$ and $( w_i(c) )$ for each of the $( d )$ layers, leading to a size of $( O(d) )$. In the succinct version:

• Intermediate layers send sum-check proofs (already small due to logarithmic rounds).

• Only the last layer includes KZG opening proofs, each a constant size (e.g., one group element).

• The total proof size becomes $( O(\log d) )$ for sum-checks plus $( O(1) )$ for openings, achieving succinctness.

Implementation in Rust

I’ve implemented this in Rust, extending the standard GKR protocol. Here’s a look at the key differences:

Standard GKR (Snippet)

// In prove:
w_i_b.push(eval_w_i_b);
w_i_c.push(eval_w_i_c);
// In verify:
let w_in_b = w_in.evaluate(&last_rand_b).unwrap();
let w_in_c = w_in.evaluate(&last_rand_c).unwrap();
let expected_claim = last_alpha * w_in_b + last_beta * w_in_c;

The prover sends evaluations directly, and the verifier recomputes them from the input.

Succinct GKR (Snippet)

// In prove (last layer):
let (point_evaluation_w_last_b, proof_w_last_b) =
    MultilinearKZG::open(&srs, &w_i_mle, &last_rand_b);
let (point_evaluation_w_last_c, proof_w_last_c) =
    MultilinearKZG::open(&srs, &w_i_mle, &last_rand_c);
proof_b = SuccinctGKRMultilinearKZGOPenningProof {
    opening: point_evaluation_w_last_b,
    opening_proof: proof_w_last_b,
};
proof_c = SuccinctGKRMultilinearKZGOPenningProof {
    opening: point_evaluation_w_last_c,
    opening_proof: proof_w_last_c,
};

// In verify:
let w_in_b_opening_verification = MultilinearKZG::verify(
    &srs,
    &input_poly_commitment,
    &last_rand_b,
    &proof.w_i_b_last_proof.opening,
    &proof.w_i_b_last_proof.opening_proof,
);
let w_in_c_opening_verification = MultilinearKZG::verify(
    &srs,
    &input_poly_commitment,
    &last_rand_c,
    &proof.w_i_c_last_proof.opening,
    &proof.w_i_c_last_proof.opening_proof,
);
let expected_claim = last_alpha * proof.w_i_b_last_proof.opening
    + last_beta * proof.w_i_c_last_proof.opening;

The prover sends KZG openings, and the verifier checks them against the commitment, avoiding large witness data.

A Simple Example

Consider a circuit with two layers:

• Input Layer: $( x_1 = 2, x_2 = 3, x_3 = 4 )$.

• Layer 1: $( g_1 = x_1 + x_2, g_2 = x_2 \cdot x_3 )$.

• Output Layer: $( o = g_1 \cdot g_2 )$.

Standard GKR

• Prover sends ( $w_1(r_b) = 5$ ) (for $( g_1 )$), ( $w_1(r_c) = 12$ ) (for $( g_2 )$), then $( w_2 )$ evaluations.

• Proof size grows with layers.

Succinct GKR

• Prover commits to $( w_{in}(x) )$ (interpolating $( 2, 3, 4 )$).

• For Layer 1, sends sum-check proof and KZG openings for $( w_1(r_b) = 5 ), ( w_1(r_c) = 12 )$.

• Verifier checks openings against $( C_{in} )$.

• Proof size: sum-check (logarithmic) + 2 openings (constant).

Benefits and Trade-offs

Benefits

• Smaller Proof Size: From $( O(d) )$ to $( O(\log d) )$, ideal for deep circuits.

• Efficient Verification: Verifier handles commitments and openings, not large witnesses.

• Scalability: Practical for large-scale computations.

Trade-offs

• Trusted Setup: The KZG scheme requires an SRS, typically from a trusted setup. A breach compromises security.

• Computational Overhead: Generating KZG proofs adds prover complexity, though this is offset by communication savings.

Mitigations include using transparent setups (e.g., via hash functions) or exploring alternative commitment schemes.

By integrating the multilinear KZG polynomial commitment scheme into the GKR protocol, I’ve developed a succinct version that reduces proof size from linear to polylogarithmic in circuit depth. Implemented in Rust, this approach enhances the practicality of verifiable computation for real-world applications. Future work could optimize the implementation, explore zero-knowledge variants, or replace the trusted setup with more flexible alternatives. This advancement brings us closer to efficient, scalable, and trustless computation verification—stay tuned for more developments!