Three STARK Primitives
Most Post-Quantum Projects Haven't Built Yet.

The Problem

When an enterprise uses encrypted documents — contracts, health records, financial data, legal filings — every access event needs to be auditable. Who opened it. When. For how long. Whether the document was modified. Whether access was authorized at the time.

The standard approach is a log file. Log files can be edited, deleted, or fabricated. Even "immutable" append-only logs depend on trusting the infrastructure operator. In regulated environments — HIPAA, SOC 2, PCI DSS, FedRAMP — "trust the log" is not a compliance answer.

STARK proofs solve the trust problem. Each access event gets a zero-knowledge proof that the event occurred, computed correctly, and was authorized. The proof is hash-based (SHA3-256), requires no trusted setup, and is quantum-resistant. No one can forge a proof. No one can alter a proof after the fact.

But generating and managing individual STARK proofs per event introduces three problems that the academic literature describes elegantly and that almost nobody has implemented in production:

1. Proof IDs are linkable. If the same vendor generates proofs across multiple sessions, an observer watching the verification endpoint can correlate them. They can track when you re-scan, how often you access documents, and build a behavioral profile — all without seeing the documents themselves.

2. Server-generated proofs are fingerprintable. If the server generates the STARK proof and the client submits it, the server can compare the exact bytes of what it generated against what appears downstream. It can identify which client submitted which proof, breaking the privacy guarantee that zero-knowledge proofs are supposed to provide.

3. Audit trails grow linearly. A document accessed 10,000 times has 10,000 individual proofs. Verifying the full audit trail means checking all 10,000. That's O(n) verification for a process that should be O(1).

Primitive 1: Epoch-Evolved Nullifiers

A nullifier is a proof identifier derived from a secret key. Epoch-evolved nullifiers rotate that identifier per time window without changing the underlying key.

The construction:

η_e ← SHA3-256(k_vendor ‖ binding ‖ epoch_id)

Where k_vendor is the vendor's persistent secret key (never revealed), binding is the codebase or document commitment (Merkle root), and epoch_id is derived from the current time window.

Same vendor. Same document. Different epoch. Completely different nullifier. An observer watching the verification endpoint sees pseudorandom identifiers with no structural relationship. They cannot determine if two nullifiers came from the same vendor without knowing k_vendor.

We support six epoch modes: hourly, daily, weekly, monthly, per-session, and custom. The vendor chooses based on their privacy requirements. Per-session mode generates a unique nullifier for every viewing session — maximum unlinkability. Daily mode balances privacy with auditability.

Verification is constant-time (timing-attack resistant). The vendor can prove a nullifier was correctly derived by revealing k_vendor to an auditor. Third parties verify the STARK proof, not the nullifier derivation.

Primitive 2: Proof Re-Randomization

Unlike Groth16 SNARKs — which support algebraic re-randomization via group element multiplication on elliptic curves — STARK proofs are hash-based. There's no algebraic structure to blind directly. Multiplying a Merkle commitment by a scalar doesn't produce a valid commitment.

Our solution: commitment-based re-randomization.

The client receives a raw STARK proof from the server. It generates a random blinding factor r, derives an encryption key k = KDF(r), and encrypts the proof: blinded = AES-256-GCM(k, proof). It also computes a blinding commitment: SHA3-256(r ‖ proof_hash).

The blinded proof is submitted. The server that generated the original proof cannot match the encrypted bytes to its output. Different blinding factors produce completely different byte representations of the same logical proof.

Verification has two modes. Structural verification (no decryption) confirms the blinded proof exists and the commitment is well-formed. Full verification (with the revealed blinding factor) decrypts the proof and runs the complete STARK verification. The client chooses when to reveal.

Replay detection works via the proof hash — even with different blinding factors, the same underlying proof produces the same hash. A verifier can detect if the same proof was submitted twice without knowing the blinding factor.

Primitive 3: Recursive Incremental Accumulation

This is the one that changes the verification economics.

Instead of storing N individual proofs for N access events, we fold them incrementally into a single accumulator. After each event, the accumulator absorbs the event's proof:

acc_new = SHA3-256(acc_old ‖ event_root ‖ data_hash)

After 10,000 events, the accumulator is still 32 bytes. The verifier checks one hash, not ten thousand proofs. Verification is O(1) regardless of trail length.

To prove a specific event was included, we generate a Merkle inclusion proof — logarithmic in the number of events. Proving event #7,342 out of 10,000 requires ~14 hash comparisons, not 10,000.

The accumulator also maintains a chain hash for sequential ordering. Changing any event in the sequence breaks the chain. Tamper detection is immediate: recompute the chain from the event roots and compare to the stored chain hash. If they diverge, someone altered the history.

For enterprise audit trails, this means a compliance auditor can verify the entire access history of a document with one constant-time check. They can then drill into any specific event with a logarithmic inclusion proof. No linear scan. No trust in the infrastructure operator. Math only.

The Audit Trail Flow

These three primitives compose into a complete document access auditing system:

1. Access request. Client requests access to an encrypted document. Server generates an ephemeral session key via Kyber ML-KEM-768 key exchange. The document is decrypted to memory only — plaintext never touches disk.

2. Proof generation. A STARK proof is generated for the access event, binding who, what, when, and the session key hash. An epoch-evolved nullifier provides an unlinkable proof identifier.

3. Accumulation. The event proof is folded into the document's recursive accumulator. The accumulator root, chain hash, and event count update in constant time.

4. Session close. Client closes the document. Session key is destroyed. A close event is generated and accumulated. The plaintext is gone.

5. Verification. Any party can verify the full audit trail via the accumulator root (constant-time) or drill into a specific event via Merkle inclusion proof (logarithmic). No trust in H33. No trust in the infrastructure. Trust the math.

6. Export. The full audit trail exports to JSON, CSV, or SIEM format. Accumulator root and chain hash allow independent verification. Customer can host the audit data on their own infrastructure.

Why This Matters

Most zero-knowledge proof systems ship the core proof generation and verification. The infrastructure around the proofs — privacy of proof identifiers, protection against server fingerprinting, and efficient verification at scale — is left as an exercise for the implementer.

In production, these gaps are where the system breaks. A STARK proof that can be correlated across sessions leaks metadata even though the proof itself reveals nothing. A proof that the server can fingerprint breaks the trust model. An audit trail that requires linear verification doesn't scale.

All three primitives are pure Rust, SHA3-256 only, Goldilocks field (p = 2⁶⁴ - 2³² + 1). No elliptic curves. No BLS12-381. No trusted setup. Post-quantum by construction.

The code is live. The endpoints are deployed. The audit trail API accepts access requests, generates STARK proofs, accumulates them recursively, and exports verifiable audit data. Every document access event produces an unlinkable, un-fingerprintable, recursively accumulated proof that any party can verify without trusting anyone.

The three primitives — epoch-evolved nullifiers, proof re-randomization, and recursive incremental accumulation — are not theoretical. They're production Rust modules with comprehensive test suites. They compose into a document access audit trail that is cryptographically tamper-evident, privacy-preserving, and constant-time verifiable.

If your audit trail is a log file, it's a trust assumption. If it's a STARK-attested recursive accumulator with epoch-evolved nullifiers, it's a mathematical fact.