💻 computer science

zkCraft: Prompt-Guided LLM as a Zero-Shot Mutation Pattern Oracle for TCCT-Powered ZK Fuzzing

zkCraft is a practical framework that leverages prompt-guided LLMs to generate mutation patterns and employs a novel proof-bearing search mechanism to efficiently detect semantic inconsistencies in zero-knowledge circuits, thereby bridging formal verification and automated debugging with reduced solver dependency.

Original authors: Rong Fu, Jia Yee Tan, Youjin Wang, Ziyu Kong, Zeli Su, Zhaolu Kang, Shuning Zhang, Xianda Li, Kun Liu, Simon Fong

Published 2026-03-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rong Fu, Jia Yee Tan, Youjin Wang, Ziyu Kong, Zeli Su, Zhaolu Kang, Shuning Zhang, Xianda Li, Kun Liu, Simon Fong

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are building a magic vault (a Zero-Knowledge Circuit). This vault allows you to prove you have the right combination to open it without ever showing the combination itself. It's like proving you know a secret password without typing it out loud.

The problem? These vaults are incredibly complex. If you make even a tiny mistake in the blueprint (the code), the vault might:

Let anyone in (Under-constrained): It accepts a wrong password because the lock is too loose.
Lock you out (Over-constrained): It rejects your correct password because the lock is too tight.

Finding these mistakes is like looking for a needle in a haystack, but the haystack is made of math, and the needle is invisible. Traditional methods try to check every single possibility one by one, which takes forever and costs a fortune in computer power.

Enter zkCraft. Think of zkCraft as a super-smart, magical detective that doesn't just look for the needle; it proves the needle exists without ever touching the haystack.

Here is how zkCraft works, broken down into simple steps:

1. The "Prompt-Guided" Detective (The LLM)

Usually, finding bugs is like throwing darts blindfolded. zkCraft uses a Large Language Model (LLM)—basically a very smart AI that reads code—not to solve the math, but to be a creative brainstorming partner.

The Analogy: Imagine you are trying to break a safe. Instead of trying every number from 0000 to 9999, you ask a smart friend, "What are the weird numbers people usually pick?" The friend suggests, "Try 0000, 9999, or 1234."
What it does: The AI suggests specific, tricky changes to the code (mutations) that are likely to expose a flaw. It acts as a "Zero-Shot Oracle," meaning it guesses the best places to look without needing to be taught every specific rule first.

2. The "Row-Vortex" Map (Organizing the Chaos)

Once the AI suggests a few places to look, zkCraft doesn't check them one by one. Instead, it creates a super-compressed map called the Row-Vortex polynomial.

The Analogy: Imagine you have a library with 10,000 books. Instead of checking every book to see if one has a typo, you take a photo of the entire shelf, shrink it down to the size of a postage stamp, and encode the location of every book into that stamp.
What it does: It bundles all the potential "buggy edits" into a single mathematical object. This allows the system to ask a giant question: "Do any of these edits create a bug?" all at once, rather than asking one by one.

3. The "Violation IOP" (The Magic Proof)

This is the coolest part. Instead of running a slow computer simulation to see if a bug exists, zkCraft uses a Zero-Knowledge Proof (specifically a "Violation IOP").

The Analogy: Imagine you want to prove to a guard that you have a red car in your garage, but you can't open the garage door. Instead of opening it, you hand the guard a magic receipt. This receipt is mathematically guaranteed to be true. If the receipt says "Red car inside," the guard knows it's true without ever seeing the car.
What it does: The system generates a tiny, unforgeable digital receipt (a proof) that says, "Yes, there is a bug here, and here is exactly what the input was that caused it." This replaces thousands of slow computer checks with a single, instant verification.

4. The "Proof-as-Counterexample" (The Solution)

In the past, finding a bug meant finding a "maybe." With zkCraft, the proof is the solution.

The Analogy: Usually, a security guard says, "I think someone broke in." zkCraft says, "I have a video recording of the burglar, their name, and the exact time they entered."
What it does: Once the proof is verified, the system automatically extracts the exact code change and the specific input data that caused the bug. It gives the developer a clear "Here is the bug, and here is how to fix it" report.

Why is this a Big Deal?

Speed: It finds bugs much faster than previous tools because it stops checking every single possibility and uses math to prove existence instantly.
Accuracy: It has zero false alarms. If the system says there's a bug, there is definitely a bug.
Scalability: It can handle huge, complex vaults (circuits) that would crash older tools.

In Summary:
zkCraft is like hiring a genius architect (the AI) to suggest where the weak spots might be, then using a magic microscope (the Zero-Knowledge Proof) to instantly confirm if those spots are broken, and finally handing you the exact blueprint repair (the counterexample) so you can fix it immediately. It turns the impossible task of debugging complex privacy systems into a fast, reliable, and automated process.

1. Problem Statement

Zero-knowledge (ZK) circuits are fundamental to privacy-preserving and scalable blockchain systems, but they are notoriously difficult to implement correctly. The core challenge lies in the Trace-Constraint Consistency Test (TCCT): the witness generator (which computes private values) must align perfectly with the constraint system used for verification. Misalignment leads to two critical fault classes:

Under-constrained faults: The constraint system accepts execution traces that no valid witness could produce (allowing invalid proofs).
Over-constrained faults: Valid witness-producing executions are rejected by the constraints (causing denial of service).

Existing solutions face significant limitations:

Static/Pattern-based detectors miss semantic discrepancies that only appear during witness generation.
Formal verification/SMT struggles to scale to large circuits and cannot efficiently handle the combined search space of program edits and input assignments.
Traditional Fuzzing relies on expensive solver calls (SMT/SAT) for validation and often generates low-value candidates due to unguided mutations.
LLM-guided methods improve mutation quality but are often decoupled from proof generation, leading to high validation costs and false positives.

2. Methodology: The zkCraft Framework

zkCraft is a ZK-native pipeline that integrates algebraic localization, succinct zero-knowledge proofs, and deterministic LLM-driven mutation. It reframes the search for vulnerability-inducing edits as a single algebraic existence statement certified by a proof, rather than a sequence of solver queries.

The framework operates in three main stages:

Stage 1: Sparse Signature Extraction (Localization)

Instead of random mutation, zkCraft performs a deterministic, R1CS-aware analysis to prioritize high-yield candidates.

Fingerprinting: It computes diagnostic scores ( $s_i$ ) for every constraint row based on the intersection of witness variables ( $W$ ) and weak-assignment sites ( $K$ ).
Candidate Pool: Rows with the lowest scores (indicating high sensitivity to weak assignments) are selected to form a small candidate pool ( $R_{cand}$ ), typically $k \le 32$ .
LLM Oracles: Deterministic LLMs act as "Zero-Shot Pattern Oracles" to propose Right-Hand-Side (RHS) edits (e.g., edge cases like 0, $q-1$ ) and input sampling heuristics. Crucially, the LLM does not solve constraints; it only biases the search space.

Stage 2: Row-Vortex Commitment & Violation IOP (ZK-Native Engine)

This is the core innovation. zkCraft replaces iterative SMT queries with a single interactive oracle proof.

Row-Vortex Polynomial: Candidate row selections ( $\delta$ ) and substitution constants ( $c$ ) are encoded into a bivariate polynomial $R(X, Y)$ .
Violation IOP: The prover constructs a Violation Interactive Oracle Proof (IOP) to certify the existence of a witness $w'$ $w^{'}$ that:
1. Satisfies the edited constraints ( $F_{\delta,c}(w') = 0$ ).
2. Produces a public output $y'$ different from the original output $y$ ( $y' \neq y$ ).
Sum-Check Protocol: The existence of such a witness is reduced to a Sum-Check identity over a domain $D$ . The prover commits to $R(X, Y)$ and engages in a public-coin protocol to prove the sum of residuals is zero while the output difference polynomial is non-zero.

Stage 3: Proof-as-Counterexample (Extraction)

Auditable Certificate: Upon successful verification, the proof $\pi$ serves as a "Proof-as-Counterexample."
Extraction: An extractor recovers the concrete tuple $(\delta, c, w')$ from the proof openings. If the transcript includes a witness polynomial, interpolation yields $w'$ directly; otherwise, a linear system is solved.
Synthesis: The system deterministically synthesizes the mutated source code $P'$ and the concrete counterexample $(x', z', y')$ without needing a full re-execution of the TCCT, as the proof already guarantees acceptance.

3. Key Contributions

ZK-Native Search Framework: Maps the combinatorial problem of finding vulnerability-inducing edits to a single algebraic existence statement encoded as a Row-Vortex polynomial and certified by a Violation IOP.
Deterministic LLM Integration: Utilizes LLMs strictly as deterministic template oracles for mutation patterns and input biasing, decoupled from the cryptographic proof generation to ensure soundness.
Proof-as-Counterexample: Introduces a workflow where the succinct proof itself acts as the certificate of the bug, allowing for the immediate reconstruction of concrete counterexamples without expensive solver replay.
Row-Vortex Commitment: A novel bivariate polynomial encoding that bundles row selection and substitution parameters, enabling compact representation of mutation choices.
Hybrid Fallback: A robust fallback mechanism to SMT/SAT solvers when ZK-native constraints (degree/domain limits) are exceeded, ensuring completeness.

4. Experimental Results

The authors evaluated zkCraft on 452 real-world Circom circuits (ranging from small to very large, up to 50k constraints) against baselines like Circomspect, ZKAP, Picus, and ZKFUZZ.

Detection Effectiveness:
- True Positives (TP): zkCraft detected 88 unique bugs in the full benchmark, outperforming all baselines.
- Precision: Achieved 100% precision (0 False Positives) across all circuit sizes, whereas baselines like ZKAP and Circomspect had precision rates as low as 0.06–0.46.
- Novelty: Discovered 65 total bugs, including 6 previously unknown vulnerabilities in production-grade circuits (e.g., ownership forgery, incorrect reward calculation).
Efficiency:
- Solver Reduction: Replaced thousands of SMT calls with a single Violation IOP.
- Speed: Converged to 90% of findings within 100 seconds (gold marker in Fig 2), significantly faster than unguided fuzzing.
- Proof Size: Using HyperPlonk+, proof sizes remained constant at 96 bytes regardless of circuit size (within the backend's envelope), while prover time grew sub-linearly ( $O(|C|^{0.7})$ ).
Ablation: Removing the Row-Vortex commitment or the Violation IOP resulted in significant slowdowns (up to 100x) and missed bugs, confirming the necessity of the ZK-native approach.

5. Significance and Impact

Bridging Formal Verification and Fuzzing: zkCraft successfully bridges the gap between the scalability of fuzzing and the rigorous guarantees of formal verification. It provides a scalable path for robust ZK circuit development.
Cost Reduction: By replacing expensive solver interactions with succinct cryptographic proofs, it drastically reduces the computational cost of end-to-end bug discovery.
Developer Workflow: The "Proof-as-Counterexample" feature provides developers with auditable, concrete traces immediately upon verification, streamlining root cause analysis and triage.
Security: The framework's ability to detect both under- and over-constrained faults with zero false positives makes it a critical tool for securing privacy-preserving systems and zkVMs.

In summary, zkCraft represents a paradigm shift in ZK circuit testing, moving from heuristic, solver-heavy approaches to a mathematically rigorous, proof-driven methodology that is both highly efficient and perfectly precise.