> For the complete documentation index, see [llms.txt](https://quantumwing.gitbook.io/quantumwing/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://quantumwing.gitbook.io/quantumwing/advanced-features/zk-proofs.md).

# ZK-STARK Proofs

## Overview

QuantumWing's cross-chain bridge uses **ZK-STARK (Zero-Knowledge Scalable Transparent Arguments of Knowledge)** for efficient attestation batching. The constraint system is now production-grade with mathematically sound vanishing constraints, correct FRI `/2x` folding, IFFT-based degree checks, and full configurability.

**Status:** ✅ PRODUCTION-READY (Constraints + FFI Integration) · ⏳ On-Chain Verifier Pending

{% hint style="success" %}
**Update (June 2026):** Constraint system and prover/verifier components are complete with **120/120 tests passing** (plus 1 ignored). FFI integration operational - bridge generates 9900-byte STARK proofs in production using the Rust backend (`-tags zkffi`). The **on-chain ZK verifier path is still pending** — it depends on the same counter-evidence STARK prover that gates autonomous bridge dispute resolution.
{% endhint %}

{% hint style="info" %}
**Scope:** This documentation covers the **Bridge ZK-STARK** implementation only (Phase 3 of the cross-chain bridge). For the full ZK privacy system (zkVM, shielded pools, private transactions), see [zk-production.md](/quantumwing/roadmap/zk-production.md).
{% endhint %}

***

## What are ZK-STARKs?

ZK-STARKs are a type of zero-knowledge proof that allows one party to prove they know something without revealing the information itself.

### Key Properties

* **Zero-Knowledge:** Proves validity without revealing data
* **Scalable:** Proof size and verification time grow logarithmically
* **Transparent:** No trusted setup required
* **Quantum-Resistant:** Based on hash functions, not elliptic curves

***

## Production Status

### ✅ What's Complete

| Component                    | Status             | Evidence                                             |
| ---------------------------- | ------------------ | ---------------------------------------------------- |
| **Mathematical Correctness** | ✅ Production       | Vanishing polynomials, FRI `/2x`, IFFT degree check  |
| **Constraint System**        | ✅ Production       | Configurable finalization epochs with validation     |
| **Test Coverage**            | ✅ Comprehensive    | 120/120 passing (+1 ignored); adversarial + fuzz     |
| **Documentation**            | ✅ Production-grade | Integration guide, API examples, pitfalls documented |
| **Robustness**               | ✅ Verified         | 200 random fuzz cases, zero crashes                  |
| **Validation**               | ✅ Runtime checks   | Assert `finalization_epoch <= trace_length`          |

### ✅ Bridge Integration (Phase 4)

* **Status**: ✅ Operational - FFI integration complete (Nov 2025)
* **Implementation**: `blockchain/bridge/zkproof.go` - `generateWithFFI()`
* **Production**: Generates 9900-byte proofs via Rust backend
* **Remaining**: On-chain smart contract verifier hookup

***

## Use Case: Bridge Attestation Batching

### Problem Without ZK

```
1000 attestations × 100,000 gas each = 100,000,000 gas
At 30 gwei: ~$9,000 per batch
```

### Solution With ZK-STARK

```
1 proof × 1,000,000 gas = 1,000,000 gas
At 30 gwei: ~$90 per batch
Savings: 99% reduction in gas costs
```

***

## Implementation

### Constraint System (Production)

```rust
// zk-prover/src/bid_constraints.rs

// Create constraint system with custom finalization epoch
let system = BIDConstraintSystem::with_finalization_epoch(
    trace_length,       // e.g., 64 slots
    finalization_epoch, // e.g., 32 (when attestations freeze)
);

// Constraints:
// 1. Bit constraints: b(b-1) = 0 enforces b ∈ {0,1}
// 2. Boundary constraint: T(0) = expected_value
// 3. Transition constraint: T(X+1) = T(X) after finalization (vanishing polynomial)
// 4. Range constraint: T(X) ∈ {0, ..., 255} (product polynomial)
```

### Proof Generation

```go
// Generate proof for epoch (e.g., hourly batch)
proof, err := zkProver.GenerateProofWithFinalization(
    trace,             // Attestation counts per slot
    finalizationSlot,  // When attestations freeze (from blockchain config)
)

if err != nil {
    return fmt.Errorf("proof generation failed: %w", err)
}

// Proof contains:
// - Circuit hash (commitment to computation)
// - Public inputs (epoch, binding count)
// - STARK proof data (~10-100 KB)
```

### Proof Verification

```go
// Verify proof on-chain or off-chain
valid, err := zkProver.VerifyProof(proof, publicInputs)

if valid {
    // All attestations in batch are valid
    // Transition bindings: ATTESTED → PROVEN
    registry.TransitionToProven(bids)
}
```

***

## Batch Processing

### Epoch-Based Batching

```
Epoch 0 (Hour 0):  Generate proof for 100 bindings
Epoch 1 (Hour 1):  Generate proof for 150 bindings
Epoch 2 (Hour 2):  Generate proof for 200 bindings
...
```

### Production Benefits

1. **Gas Efficiency:** \~99% gas reduction (1M gas vs 100M gas)
2. **Privacy:** Batching hides individual attestations
3. **Scalability:** Supports thousands of bindings per epoch
4. **Security:** Mathematically sound (vanishing polynomials, correct FRI folding)

***

## Security Guarantees

### Quantum Resistance

* **Hash Functions**: SHA3-256 (NIST approved, quantum-safe)
* **Signature Scheme**: Dilithium Mode 3 (post-quantum, 192-bit security)
* **FRI Protocol**: `/2x` folding (mathematically correct)

### Soundness

* **Vanishing Polynomials**: Constraints evaluate to 0 when satisfied
* **Low-Degree Testing**: IFFT-based (not heuristic)
* **Out-of-Domain Verification**: Lagrange interpolation for challenge points

### Completeness

* **120 Tests Passing**: Adversarial + fuzz + panic + edge cases
* **200 Random Fuzz Cases**: Zero crashes with arbitrary inputs
* **Configuration Validation**: Runtime assertions prevent misconfiguration

***

## API Reference

### Generate Proof (Production)

```go
// blockchain/bridge/zkproof.go

func (r *Registry) GenerateEpochProof(epoch uint64) ([]byte, error) {
    // Get BIDs for epoch
    bids := r.GetBIDsByEpoch(epoch)

    // Create execution trace
    trace := createAttestationTrace(bids)

    // Get finalization from blockchain config
    finalizationSlot := blockchain.Config.SlotsPerEpoch  // e.g., 32

    // Generate proof with explicit finalization
    proof, err := zkProver.GenerateProofWithFinalization(trace, finalizationSlot)
    if err != nil {
        return nil, fmt.Errorf("proof generation failed: %w", err)
    }

    return proof, nil
}
```

### Verify Proof

```go
valid, err := zkProver.VerifyProof(proof *ZKProof, publicInputs []byte)
```

### Get Proof by Epoch

```go
proof, err := zkProofs.GetProofByEpoch(epoch uint64)
```

***

## Technical Details

### Constraint System

**Vanishing Polynomial Constraints**:

* **TransitionMonotonicConstraint**: `(X - N) · (T(X+1) - T(X)) = 0`
  * Vanishes when `X < N` (before finalization) OR `T(X+1) = T(X)` (constant)
* **RangeConstraint**: `∏(T(X) - i) = 0` for i = 0..max\_value
  * Vanishes iff `T(X) ∈ {0, 1, ..., max_value}`
* **BitConstraint**: `b(b-1) = 0`
  * Vanishes iff `b ∈ {0, 1}`
* **BoundaryConstraint**: `(X - position) · (T(X) - expected) = 0`
  * Vanishes when `X = position` and `T(X) = expected`

### FRI Protocol

**Correct Folding Formula** (Fix):

```rust
// f_next(x²) = (f(x) + α·f(-x)) / 2x
let omega_i = domain.twiddles[i];  // x = ω^i (root of unity)
let two_x = FieldElement::new(2).mul(&omega_i);
let folded = numerator.div(&two_x);  // Correct: /2x, not /2
```

### Low-Degree Testing

**IFFT-Based** (Fix):

```rust
// Convert evaluations to coefficients via IFFT
let coeffs = domain.ifft(evals);

// Check all coefficients beyond max_degree are zero
for i in (max_degree + 1)..n {
    if coeffs[i].value() > threshold.value() {
        return false;  // High-degree coefficient non-zero → invalid
    }
}
```

***

## Roadmap & Status

### STARK Development Phases

1. ✅ **Phase 0 (Complete):** FFI, transcript, Merkle commitments
2. ✅ **Phase 1 (Complete):** Algebraic constraint system with vanishing polynomials
3. ✅ **Phase 2 (Complete):** FFT-based LDE with correct `/2x` FRI folding
4. ✅ **Phase 3 (Complete):** IFFT-based low-degree testing
5. ✅ **Phase 4 (Complete):** Bridge FFI integration - Rust prover operational (Nov 2025)
6. ⏳ **Phase 5 (Pending):** On-chain smart contract verifier

### Recent Achievements

**Nov 2025 - FFI Integration** ✅:

* ✅ Bridge FFI integration complete (`blockchain/bridge/zkproof.go`)
* ✅ Production proofs: 9900 bytes via Rust backend
* ✅ Full bridge flow: ATTESTED → PROVEN → REDEEMED operational
* ✅ Build tag: `-tags zkffi` for Rust prover

**Oct 2025 - Mathematical Fixes** ✅:

* ✅ Vanishing polynomial constraints (not arbitrary values)
* ✅ FRI `/2x` formula (not `/2`)
* ✅ IFFT degree check (not heuristic)

**Production Hardening** ✅:

* ✅ Configurable finalization epochs (`with_finalization_epoch`)
* ✅ 6 adversarial tests (boundary violations, edge cases)
* ✅ 3 fuzz tests (200 random cases)
* ✅ Runtime validation (assert `finalization_epoch <= trace_length`)

**Test Results**: 120/120 passing (0 failed, 1 ignored)

***

## Integration Guide

See the bridge ZK wrapper [`blockchain/bridge/zkproof.go`](https://github.com/dolfrin/QuantumWing/blob/master/blockchain/bridge/zkproof.go) and the Rust prover under [`zk-prover/`](https://github.com/dolfrin/QuantumWing/blob/master/zk-prover/README.md) for:

* API examples (Rust FFI, Go CGO wrappers)
* Common pitfalls (wrong epoch, trace not frozen, off-by-one errors)
* Production deployment checklist
* Validation helpers

**Quick Example**:

```go
// CORRECT: Specify finalization from blockchain config
proof := zkProver.GenerateProofWithFinalization(trace, blockchain.SlotsPerEpoch)

// WRONG: Using default when protocol has custom finalization
proof := zkProver.GenerateProof(trace)  // Uses trace_length/2 (may be wrong!)
```

***

## References

* **Constraint System:** [`zk-prover/src/bid_constraints.rs`](https://github.com/dolfrin/QuantumWing/blob/master/zk-prover/src/bid_constraints.rs)
* **FRI Implementation:** [`zk-prover/src/fri.rs`](https://github.com/dolfrin/QuantumWing/blob/master/zk-prover/src/fri.rs)
* **Bridge Integration:** [Cross-Chain Bridge → Phase 3](/quantumwing/advanced-features/bridge.md#phase-3-zero-knowledge-proofs)
* **Full ZK Privacy Roadmap:** [zk-production.md](/quantumwing/roadmap/zk-production.md)

***

**Status:** ✅ Production-Ready (Constraints + FFI Integration) · ⏳ On-Chain Verifier Pending


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the following URL with the `ask` and `goal` query parameters:

```
GET https://quantumwing.gitbook.io/quantumwing/advanced-features/zk-proofs.md?ask=<question>&goal=<user_goal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is what the user is ultimately trying to achieve, the reason they need the answer. Sharing it helps GitBook give you a better, more relevant answer. A goal is most helpful when it describes the outcome the user wants rather than restating the question. For example, with `ask=how do I create an API token`, a goal like `build a script that syncs our docs to a CMS` lets GitBook tailor the answer to that use case.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.