STARK proof verification

A STARK — Scalable Transparent ARgument of Knowledge — is a zero-knowledge proof system that allows a prover to convince a verifier that a computation was performed correctly without revealing the inputs to that computation. The verifier learns nothing except that the statement is true.

STARKs differ from other zero-knowledge proof systems (SNARKs, Groth16, PLONK) in two critical ways. First, they require no trusted setup. There is no ceremony, no toxic waste, no multi-party computation to generate common reference strings. The public parameters are derived from public randomness. Second, their security is based entirely on collision-resistant hash functions, not on elliptic curve pairings or discrete logarithm assumptions.

This matters because elliptic curve assumptions are broken by quantum computers running Shor's algorithm. Hash function security is not. STARKs are post-quantum secure by construction. H33 uses SHA3-256 as the hash function, which provides 128 bits of post-quantum security.

H33 implements two distinct STARK proof systems, each optimized for a different class of verification problem. Both share the same SHA3-256 hash foundation and the same no-trusted-setup guarantee, but they prove different things.

The Lookup STARK is the workhorse of H33's attestation pipeline. Every time a biometric match is verified, a control is attested, or a signature is validated, the result is stored in a lookup table. Subsequent verifications check the table: does this proof already exist?

The lookup proof demonstrates that a given value is present in the table without revealing the value, the table, or the position. The verifier receives a STARK proof and either accepts or rejects it. The proof is computed over a polynomial representation of the table membership relation.

The cached lookup path achieves 0.358 microseconds per verification in the production pipeline. This is possible because the lookup table is stored in a DashMap — a concurrent, lock-free hash map that runs in the same process as the verification engine. There is no network hop, no serialization, no TCP overhead. The lookup is a direct memory access.

This design was validated against a TCP-based cache (RESP protocol). The in-process DashMap is 44x faster per lookup and eliminates TCP contention entirely at 96 concurrent workers. The TCP approach caused an 11x throughput regression. In-process is the correct architecture for this workload.

The AIR STARK encodes a computation as a set of polynomial constraints over an execution trace. Each row of the trace represents one step of the computation. The constraints enforce that each step follows correctly from the previous step. The prover generates a proof that the trace satisfies all constraints. The verifier checks the proof without re-executing the computation.

H33 uses AIR STARKs for cryptographic proof of life. The secp256k1 STARK circuit proves that a private key operation was performed correctly over a specific public key, without revealing the private key. This is the foundation of H33-74-AIR (Proof of Life), which provides cryptographic evidence that a signing key is live and under the control of a specific entity.

The cold proof generation time of 495 milliseconds is for the full secp256k1 modular multiplication circuit. Once the circuit is cached, subsequent proofs drop to 1.75 milliseconds — a 282x speedup. Verification is constant at 71 microseconds regardless of caching state. The circuit was validated using k256 differential testing, which uncovered and fixed a modular multiplication bug during development.

Many zero-knowledge proof systems require a trusted setup ceremony. During this ceremony, secret values are generated, used to compute public parameters, and then destroyed. If the secret values are not properly destroyed, anyone who retained them can forge proofs.

STARKs do not have this problem. The public parameters are derived from public randomness — typically the output of a hash function applied to the proof statement. There are no secret values. There is no ceremony. There is no trust assumption beyond the collision resistance of the hash function.

This is particularly important for enterprise and government deployments where the security of the entire system cannot depend on the integrity of a ceremony conducted by a third party. With STARKs, the security depends on SHA3-256. SHA3-256 is a NIST standard. Its security properties are well understood and publicly verifiable.

The verification process is deterministic and non-interactive. Given a proof and a public statement, any party can verify the proof without any secret keys, without any interaction with the prover, and without any trusted third party. The verification cost is logarithmic in the size of the computation — verifying a proof of a million-step computation takes roughly the same time as verifying a proof of a hundred-step computation.

In H33's pipeline, STARK verification accounts for less than 1% of the total per-authentication latency. The FHE batch and the Dilithium signature dominate. The STARK proof is essentially free at the margins.

The STARK proof is the third stage of the authentication pipeline. After the FHE biometric match (stage 1) and the Dilithium signature attestation (stage 2), the STARK lookup verifies that the attestation has been recorded in the verified set. This provides a zero-knowledge proof of membership: the attestation exists, and it can be verified without revealing the attestation itself.

The full pipeline — FHE, attestation, and ZKP — completes in 1,345 microseconds for a batch of 32 users (42 microseconds per authentication). The STARK verification contributes 0.358 microseconds of that total. It is the fastest stage by three orders of magnitude.