> Layerwise ZK Proofs for LLM Inference: Sumcheck and Constraint Reduction

Zero-Knowledge Proofs 专家 2026-04-01 22:52 2026-04-01
#zero-knowledge proofs #LLM inference #sumcheck #Halo2 #IPA #transformer verification #cryptography

How to cryptographically prove correct LLM inference without revealing model weights. Sumcheck reduces MLP constraints 306x and attention constraints 40,044x. LLaMA-3-1B: 620ms proof, 2.4KB, 22ms verification.

// TABLE_OF_CONTENTS

Layerwise ZK Proofs for LLM Inference

The Problem

When you pay a cloud provider to run an LLM, how do you verify: - They ran the correct model (not a cheaper substitute)? - They didn't skip layers or use lower precision? - The output genuinely corresponds to your input?

ZK proofs provide cryptographic guarantees without revealing model weights.

Core Architecture: Layerwise Decomposition

Each transformer layer is proved independently, connected by SHA-256 commitment chains:

Input → [Layer 0 proof] → commit_0 → [Layer 1 proof] → commit_1 → ... → Output

Properties: - O(log n) proof size via Halo2 IPA (~2.3KB per layer, constant regardless of model width) - Parallel proving across layers - Selective verification (prove only important layers) - Compositional soundness: \(\epsilon < 10^{-37}\) for 32 layers - No trusted setup (transparent, post-quantum compatible)

Sumcheck Protocol: The Key Breakthrough

The bottleneck for large models is constraint count in matrix multiplication verification.

Component d Naive Constraints Sumcheck Reduction
MLP 768 4.7M 15,450 306x
Attention (seq=128) 768 327M 8,170 40,044x
Full GPT-2 block 768 332M 220K 1,511x

For a matmul \(C = A \times B\) where \(C_{ij} = \sum_k A_{ik} B_{kj}\), the sumcheck protocol: 1. Verifier sends random challenge \(r\) 2. Prover commits to univariate polynomial \(p(X) = \sum_k A_{ik}(X) \cdot B_{kj}(X)\) 3. Verified in \(O(\log d)\) rounds instead of \(O(d)\) constraints

Lookup Table Approximations

Non-arithmetic operations (softmax, GELU, RMSNorm) are ZK-unfriendly. Solution: 16-bit fixed-point lookup tables.

Model Dataset PPL Change
GPT-2 WikiText-2 0.00%
GPT-2-Medium WikiText-2 0.00%
TinyLLaMA-1.1B WikiText-2 0.00%
Polynomial approx. WikiText-2 ~133% (unusable)

Lookup tables preserve accuracy perfectly. Polynomial approximations fail catastrophically.

Performance Results

Model d Prove Time Proof Size Verify
GPT-2 (d=64, naive) 64 3,400ms 7.7KB —
GPT-2 (d=64, sumcheck) 64 250ms 1.8KB —
GPT-2 (d=768, MLP) 768 850ms 2.0KB 22ms
LLaMA-3-1B 2,048 620ms 2.4KB 22ms

vs EZKL baseline: 70x smaller proofs, 5.7x faster proving.

GPU Acceleration

Optimization Speedup
GPU MSM at k=20 (1M points) 7.6x
GPU Fp matmul (3072x768) 49x
GPU sumcheck session (22 rounds) 23x
Window size tuning (k=17) 2.2x

GPU MSM for Pallas curve published as hanfei-shu on crates.io (v0.2.1).

Fisher-Guided Verification Budget

When proving all layers is too expensive, Fisher information identifies important layers:

Budget Fisher Coverage Random Coverage Improvement
25% 43.1% 24.3% +78%
50% 68.4% 42.8% +60%
75% 85.2% 75.1% +13%

At 50% budget: 74.2% model importance covered (GPT-2 scale).

< BACK_TO_NOTES()