The 42-Byte Verification Receipt: Why Signatures Don't Need to Persist

The Persistence Assumption

Every discussion about post-quantum signature sizes starts with the same assumption: the signature needs to be stored somewhere. If Dilithium produces a 3,309-byte signature, you need 3,309 bytes of storage. If you add FALCON (657 bytes) and SPHINCS+ (17,088 bytes), you need 21,054 bytes. Per event. Forever.

This assumption drives every objection to multi-family PQ signing. "We can't put 21KB per transaction on a blockchain." "We can't store 21KB per API call in a database." "We can't transmit 21KB per authentication in a real-time system." All true. All based on the premise that the signatures persist.

What if they don't?

What a Signature Actually Proves

A digital signature proves one thing: that a specific private key authorized a specific message at a specific time. After verification, the fact of authorization is what matters. The raw cryptographic proof—the thousands of bytes of lattice vectors or hash chain traversals—served its purpose during verification. It doesn't need to continue existing.

This is not a new concept. In physical security, a guard checks your ID at the door and issues a badge. You don't carry the guard and the ID verification equipment with you through the building. The badge is the persistent artifact. The verification was ephemeral.

The same principle applies to cryptographic verification. The signature is the ID check. The receipt is the badge.

The Receipt

A verification receipt is a compact artifact that cryptographically proves verification occurred, without carrying the verification inputs.

Our receipt is 42 bytes. It contains:

• A version byte (1 byte) identifying the receipt format
• A verification hash (32 bytes) that binds to the exact message, public keys, and signatures that were verified
• A timestamp (8 bytes) recording when verification occurred
• An algorithm flags byte (1 byte) recording which signature families were verified

The verification hash is the critical component. It is a collision-resistant hash (SHA3-256) computed over the signing message concatenated with all public keys and all signatures. If any input changes—different message, different key, different signature, different algorithm—the hash changes completely.

This means the 42-byte receipt is cryptographically bound to the specific 21,054 bytes of signatures that produced it. You cannot create a receipt that matches a different set of signatures. You cannot modify the signatures and keep the receipt valid. The binding is as strong as the hash function.

The Lifecycle

Here's how 21KB becomes 42 bytes:

T=0ms: The signing message is derived from a canonical commitment (a deterministic hash of the computation being attested). 32 bytes.

T=0-1ms: Three signature algorithms each sign the message. Dilithium produces 3,309 bytes. FALCON produces ~657 bytes. SPHINCS+ produces 17,088 bytes. Total in memory: ~21,054 bytes.

T=1-15ms: Each signature is independently verified against its corresponding public key. All three pass.

T=15ms: The verification hash is computed: SHA3-256 of the signing message concatenated with all three public keys and all three signatures. The 42-byte receipt is assembled. The raw signatures are overwritten with zeros in memory. The 21,054 bytes are gone.

T=15ms+: The 42-byte receipt is stored in a lookup layer, keyed by the 32-byte signing message (which is the same value that lives on-chain). From this point forward, every verification check is a lookup returning 42 bytes. No signatures. No public keys. No multi-kilobyte payloads. Just the receipt.

The 21KB existed for 15 milliseconds. The 42 bytes exist forever.

Why Not Just Store the Signatures?

The obvious alternative is to store the full signatures and verify them on demand. Let's compare the approaches at scale.

At 1 million attestations per day

Approach	Daily storage	Annual storage	Lookup size
Full signatures (3-family)	21 GB	7.7 TB	~21KB per lookup
Full signatures (Dilithium only)	3.3 GB	1.2 TB	~3.3KB per lookup
42-byte receipt	42 MB	15.3 GB	42 bytes per lookup

The receipt approach uses 500x less storage than full three-family signatures and 79x less than Dilithium alone. At a billion attestations, the receipt approach needs 15.3 TB annually. The full signature approach needs 7.7 PB. One fits on a server. The other requires a data center.

Lookup performance

Retrieving a 42-byte receipt from a key-value lookup takes under a microsecond. Retrieving 21KB of signatures, deserializing three different signature formats, and running three different verification algorithms takes milliseconds. For a system that needs to verify millions of attestations per second, the difference is the difference between "works" and "doesn't work."

Our production system verifies attestations at 0.059 microseconds per lookup. That's approximately 17 million verifications per second on a single core. At full three-family signature verification (without caching), it's roughly 65 verifications per second per core (dominated by SPHINCS+ verification time). That's a 260,000x throughput difference.

The Trust Model

A receipt is not a signature. It does not carry the mathematical proof that a private key authorized a message. It carries proof that someone computed a hash over those mathematical proofs. The trust question is: who computed that hash?

In our system, the attestation pipeline computes the receipt immediately after verifying all three signatures, within the same process, within the same memory space, within the same 15-millisecond window. The receipt is produced by the same system that performed the verification. It's not a third-party assertion. It's a first-party computation result.

If you trust the verification system to correctly verify signatures (which you must, since that's what signature verification systems do), you trust it to correctly compute a hash over the inputs it just verified. The receipt adds no additional trust assumption beyond the one you already made when you decided to use the system.

For organizations that require independent re-verification, the system supports it. The public keys are known. A fresh attestation can be produced for the same computation, generating new signatures and a new receipt. The new receipt will have a different verification hash (because the signatures are probabilistic and will differ) but will attest to the same computation at a new timestamp.

What the Receipt Doesn't Do

A receipt is not a zero-knowledge proof. It doesn't prove that the signatures were valid without revealing the signatures. The signatures were valid—they were verified by the attestation system—but the receipt doesn't carry a mathematical proof of that fact that a third party can independently check without trusting the attestation system.

For most use cases, this distinction doesn't matter. The attestation system is infrastructure you operate or contract. You trust it the same way you trust your HSM or your CA. The receipt is the output of that trusted system.

For use cases that require trustless verification—where even the attestation system's honesty must be provable—STARK proofs can replace the hash-based receipt. A STARK proof says "I verified three PQ signatures and they were all valid" in a way that anyone can check without trusting the prover. The tradeoff is size: STARK proofs are larger than 42 bytes (typically 400-800 bytes) but still far smaller than the raw signatures.

The 42-byte receipt is the pragmatic choice for trusted infrastructure. The STARK proof is the option for trustless verification. Both are available. Most deployments use the receipt.

The Cacheable Verification Pattern

The receipt architecture turns signature verification into a caching problem. And caching problems are solved problems.

Every verification after the first is a cache hit. The cache key is the 32-byte signing message (which is also the on-chain anchor, if one exists). The cache value is the 42-byte receipt. The cache is a key-value store optimized for small values and fast lookups.

This pattern has several properties that make it operationally excellent:

• Horizontal scaling: The cache can be replicated across regions, data centers, and continents. Each replica is 42 bytes per entry. Global verification at local latency.
• Cold start resilience: If the cache is empty (cold start, migration, disaster recovery), attestations can be re-generated from the original computation outputs and public keys. The cache is recoverable, not precious.
• TTL flexibility: Receipts can have time-to-live policies. Recent attestations stay in hot cache. Older ones move to warm or cold storage. The 42-byte size makes even cold storage trivially inexpensive.
• Multi-tenant isolation: Each attestation is keyed by its signing message, which is derived from the specific computation. There's no cross-tenant information leakage in the cache structure.

The Economic Insight

Signature verification is expensive. It involves parsing complex algebraic structures, performing modular arithmetic or hash traversals, and checking mathematical relations. SPHINCS+ verification alone involves thousands of hash computations.

The 42-byte receipt converts this expensive operation into a cheap one: a key-value lookup. The expensive computation happens once. The cheap lookup happens every time after.

At scale, the economics are compelling. If your system verifies 10 million attestations per day, and each full verification costs 15 milliseconds of CPU time:

• Full verification: 10M × 15ms = 150,000 CPU-seconds per day = ~1.7 CPU-days
• Receipt lookup: 10M × 0.059μs = 0.59 CPU-seconds per day

That's a 254,000x reduction in CPU cost for verification. The attestation cost (producing the signatures and receipt) is the same either way. The verification cost is where the receipt pays for itself, and it pays for itself on the first day.

42 Bytes Is Not Arbitrary

The receipt size is the minimum needed to carry the verification commitment, a timestamp, and algorithm identification:

• 1 byte version: future-proofs the format. If we need to change the receipt structure, the version byte tells parsers which format to expect.
• 32 bytes verification hash: SHA3-256 provides 128-bit post-quantum collision resistance. This is the binding between the receipt and the original signatures. Reducing this would weaken the cryptographic binding.
• 8 bytes timestamp: millisecond-precision Unix timestamp. Needed for freshness checks, TTL enforcement, and audit trails.
• 1 byte algorithm flags: a bitmask recording which of the three families verified. This enables graceful degradation: if a family is later compromised, verifiers can check which families attested a specific event.

Remove any component and you lose a property. Reduce the hash size and you weaken the binding. Remove the timestamp and you lose audit capability. Remove the flags and you lose degradation information. 42 bytes is the tight lower bound for a verification receipt with these properties.

The Pattern, Not the Product

The ephemeral-signature-with-cached-receipt pattern is not specific to post-quantum cryptography. It applies to any situation where:

1. The verification proof is large
2. Verification is computationally expensive
3. The verification result is queried far more often than it's produced
4. The proof doesn't need to be independently re-verifiable by untrusted parties

Post-quantum signatures happen to hit all four criteria hard. But the pattern works for ZK proof verification, FHE computation attestation, multi-party computation results, and any other cryptographic operation where the proof is large and the query is frequent.

We applied it to PQ signatures because that's where the size problem was most acute. 21,054 bytes is a lot of proof. 42 bytes is not. The gap between them is where the architecture lives.