STARK Proof Performance

1. Scope

This document presents production benchmarks for the H33 STARK proof systems: Lookup STARK (used in the production ZKP pipeline) and AIR STARK (used in H33-74-AIR for secp256k1 signature circuit proving). All numbers are from Graviton4 bare metal. STARKs require no trusted setup and derive their security from the collision resistance of SHA3-256, providing post-quantum security.

2. Definitions

STARK (Scalable Transparent ARgument of Knowledge)

A proof system in which a prover demonstrates knowledge of a computation's execution trace without revealing the trace itself. STARKs are transparent (no trusted setup), scalable (logarithmic verification time), and post-quantum secure (based on hash function collision resistance).

Lookup STARK

A STARK variant optimized for proving membership of a value in a pre-committed table. Used in the H33 pipeline to prove that a ZKP lookup result was correctly computed from the committed table without revealing the lookup key.

AIR (Algebraic Intermediate Representation)

The constraint system format used by STARKs. An AIR defines polynomial constraints over an execution trace. The prover demonstrates that a trace satisfies all constraints; the verifier checks a succinct proof without seeing the trace.

H33-74-AIR

The H33 STARK circuit for proving secp256k1 ECDSA signature validity. Used in the Proof of Life system. The circuit encodes the full secp256k1 scalar multiplication and signature verification algorithm as AIR constraints.

Cold / Cached

Cold proving includes one-time setup costs (trace generation, FFT twiddle factor computation, constraint compilation). Cached proving reuses precomputed structures from a previous cold invocation.

3. Lookup STARK Performance

The Lookup STARK is used in Stage 3 (ZKP) of the H33 production pipeline. It proves that a cached value was correctly looked up from a committed table.

Metric	Cold	Cached (CacheeEngine)
Prove latency	4.2 us	0.062 us
Verify latency	1.8 us	0.358 us
Proof size	1,024 bytes	1,024 bytes
Table size (entries)	up to 2^20	up to 2^20
Speedup (cold vs cached)	--	67.7x prove, 5.0x verify

The 0.062 us cached prove latency (62 nanoseconds) is achieved by precomputing the polynomial commitment and reusing it across lookups into the same table. The CacheeEngine stores precomputed commitments in its LFU cache layer.

4. AIR STARK Performance

4.1. Generic AIR Circuits

Circuit	Trace Rows	Constraints	Prove (cold)	Prove (cached)	Verify	Proof Size
Fibonacci (2^10)	1,024	2	12 ms	0.8 ms	0.3 ms	4.2 KiB
SHA3-256 (single)	32,768	48	180 ms	14 ms	2.1 ms	18 KiB
Merkle tree (depth 8)	65,536	96	420 ms	34 ms	3.8 ms	28 KiB
secp256k1 ECDSA	131,072	256	495 ms	1.75 ms	0.071 ms	42 KiB

4.2. H33-74-AIR: secp256k1 Circuit

The H33-74-AIR circuit is the STARK proof component of the Proof of Life system. It proves that a secp256k1 ECDSA signature is valid without revealing the private key or the full signature.

Metric	Value
Cold prove	495 ms
Cached prove	1.75 ms
Verify	71 us (0.071 ms)
Cache speedup	282x
Proof size	42 KiB
Trace rows	131,072
Constraint count	256
Field	Goldilocks (p = 2^64 - 2^32 + 1)
Hash	SHA3-256
Security level	128-bit (conjectured post-quantum)
Test coverage	22 tests, 1,100 keys validated

The 282x cache speedup (495 ms to 1.75 ms) is achieved by precomputing the constraint evaluation domain, twiddle factors, and the low-degree extension of the execution trace. On subsequent proofs with the same circuit structure (different witnesses), only the witness-dependent portions of the computation are re-executed.

5. No Trusted Setup

STARKs are transparent proof systems. Unlike SNARKs (which require a trusted setup ceremony to generate a structured reference string), STARKs derive their soundness from the collision resistance of the hash function. This provides two properties:

1. No toxic waste. There are no secret parameters generated during setup that, if compromised, would allow proof forgery.
2. Post-quantum security. The security of the proof system is bounded by the collision resistance of SHA3-256 (128-bit post-quantum security per NIST SP 800-185). No lattice or number-theoretic assumptions are required.

Property	STARK (H33)	Groth16 SNARK	PLONK SNARK
Trusted setup	None	Per-circuit	Universal
Post-quantum secure	Yes	No	No
Proof size	10-50 KiB	192 bytes	384 bytes
Verify time	0.07-4 ms	1.5 ms	3 ms
Prover time	1-500 ms	2-10 s	5-30 s

STARKs trade larger proof sizes (10-50 KiB vs 192-384 bytes for SNARKs) for elimination of trusted setup, post-quantum security, and significantly faster proving times. For the H33 use case (server-side proving, not on-chain verification), the proof size tradeoff is acceptable.

6. SHA3-256 Post-Quantum Security

All H33 STARK implementations use SHA3-256 (NIST FIPS 202) as the hash function for Merkle tree commitments, Fiat-Shamir transcript generation, and FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity) commitments. SHA3-256 provides:

• Collision resistance: 128 bits (classical and quantum, per Grover's bound).
• Preimage resistance: 256 bits (classical), 128 bits (quantum).
• No algebraic structure: SHA3 is a sponge construction with no exploitable algebraic structure, unlike algebraic hash functions used in some SNARK-friendly constructions.

7. Scaling Characteristics

Trace Rows	Prove (cold)	Verify	Proof Size
2^10 (1K)	12 ms	0.3 ms	4.2 KiB
2^14 (16K)	85 ms	1.2 ms	12 KiB
2^17 (128K)	495 ms	2.8 ms	42 KiB
2^20 (1M)	3,200 ms	4.1 ms	68 KiB

Prove time scales as O(n log n) where n is the number of trace rows. Verify time scales as O(log^2 n), remaining sub-5ms even for million-row traces. Proof size scales as O(log^2 n).

8. Reproducibility

9. Integration in H33 Pipeline

STARKs are used in two distinct locations within the H33 system:

1. Production pipeline (Stage 3): Lookup STARK via CacheeEngine. 0.358 us verify latency per authentication. Less than 1% of pipeline time.
2. H33-74-AIR (Proof of Life): secp256k1 STARK circuit for proving ECDSA signature validity. Used for on-demand attestation of key possession, not in the hot authentication path.

See Agent Infrastructure Benchmarks for the pipeline context of Lookup STARK performance.