H33-74-AIR: Zero-Knowledge Proof of Bitcoin Key Ownership

There are approximately 1.1 million Bitcoin sitting in early mining addresses widely attributed to Satoshi Nakamoto. The public keys are known. The balances are visible on-chain. The coins have not moved since 2010. And with that stillness comes a question that has haunted the Bitcoin ecosystem for over a decade: can anyone prove they control those keys?

Until now, there were exactly two options, and both were unacceptable.

The first option: move the coins. Sign a transaction, broadcast it, let the network verify. This proves control definitively, but the cost is enormous. Moving even a fraction of those holdings would destabilize markets, attract regulatory attention worldwide, and permanently link the controller's identity to the most scrutinized addresses in cryptocurrency history. For anyone holding keys to dormant Bitcoin -- whether Satoshi, an early miner, a deceased holder's estate, or an institutional custodian -- moving coins is not proof of control. It is surrender of privacy.

The second option: reveal the private key. This proves knowledge but destroys security. The moment a 256-bit scalar is disclosed, anyone who sees it can spend the funds. There is no partial reveal, no take-backs. Key disclosure is catastrophic and irreversible.

There was no third option. We built one.

The Third Option: Algebraic Intermediate Representation

H33-74-AIR is a ZK-STARK circuit that proves knowledge of a Bitcoin private key without revealing it and without moving a single satoshi. The prover demonstrates that they know a scalar sk such that sk * G = pk, where pk is the known public key and G is the secp256k1 generator point. The private key is the witness -- it satisfies the constraints inside the proof, but it never appears in the output. A verifier checks the polynomial math. No key material crosses the boundary. No trust is required. No coins move.

The circuit is built on Algebraic Intermediate Representation, the constraint system native to ZK-STARKs. Unlike trusted-setup schemes, STARKs rely on nothing but hash functions and algebraic structure. There is no toxic waste, no ceremony, no multi-party computation that could be compromised years later. The security of the proof rests on the collision resistance of SHA3-256 and the algebraic properties of the Goldilocks field -- transparent, auditable, and post-quantum resistant from the foundation up.

The implementation lives in src/zkp/stark/secp256k1_air.rs, with the elliptic curve primitives in src/proof_of_life/secp256k1.rs and the post-quantum binding layer in src/proof_of_life/binding.rs. The H33-74 type identifier is PostQuantumMigration (0x12).

The Mathematics: secp256k1 Over Goldilocks

Every Bitcoin public key is derived from a private key by a single mathematical operation: elliptic curve scalar multiplication. Given a private key sk (a 256-bit integer) and the secp256k1 generator point G, the public key is pk = sk * G. This operation is a sequence of 256 point doublings and conditional point additions -- the double-and-add algorithm that has been the backbone of elliptic curve cryptography since its inception.

The challenge is encoding this operation as polynomial constraints over a finite field that the STARK prover can work with. The secp256k1 base field is a 256-bit prime (p = 2^256 - 2^32 - 977). The Goldilocks field used by the AIR is 64-bit (p = 2^64 - 2^32 + 1). These are fundamentally different sizes. A single secp256k1 field element does not fit in a single Goldilocks element.

Non-Native Field Arithmetic

The solution is limb decomposition. Each 256-bit secp256k1 coordinate is represented as four 64-bit Goldilocks limbs. Every field operation -- addition, multiplication, reduction modulo the secp256k1 prime -- must be expressed as constraints over these four-limb representations. A single secp256k1 multiplication becomes a series of Goldilocks multiplications with carry propagation between limbs, range proofs ensuring no limb exceeds 64 bits, and modular reduction constraints that enforce the result remains in the secp256k1 field.

Point doubling on secp256k1 requires computing a slope lambda = (3 * x^2 + a) / (2 * y), then deriving the new coordinates. Each of these sub-operations -- the squaring, the scalar multiply by 3, the modular inverse for division, the final coordinate computation -- expands into dozens of Goldilocks constraints when expressed over 4-limb representations. Point addition is similarly decomposed: slope computation, new x-coordinate, new y-coordinate, each with full carry propagation and range enforcement.

The Execution Trace

The private key is 256 bits. The double-and-add algorithm processes one bit per step. Each step performs a point doubling (always) and a conditional point addition (when the current bit is 1). The execution trace is therefore 512 rows -- one row per scalar bit, though the trace interleaves doublings and additions across two rows per bit to keep the constraint degree manageable.

At each row, the AIR constraints enforce:

• Point doubling correctness: The doubled point satisfies the elliptic curve equation and the doubling formula.
• Conditional addition correctness: If the scalar bit is 1, the accumulated point is the sum of the doubled point and G. If the bit is 0, the accumulated point equals the doubled point unchanged.
• Carry propagation: Intermediate products from 4-limb multiplications produce 8-limb results that must be reduced back to 4 limbs, with carries constrained to be non-negative and bounded.
• Range proofs on limbs: Every limb in every intermediate value is range-checked to ensure it fits in 64 bits, preventing malicious provers from smuggling overflow values that would satisfy constraints spuriously.
• Boundary constraints: The initial accumulator is the identity point. The final accumulator, after all 256 double-and-add steps, must equal the claimed public key pk.

The total constraint count is approximately 147,000 Goldilocks constraints. This is large by STARK standards, but the structure is highly regular -- the same doubling and addition sub-circuits repeat 256 times -- which makes the FRI (Fast Reed-Solomon Interactive Oracle Proofs of Proximity) commitment phase efficient.

Post-Quantum Binding: Three Hardness Assumptions

A zero-knowledge proof of key ownership is valuable on its own. But the secp256k1 curve will not survive a sufficiently large quantum computer. Shor's algorithm reduces the discrete logarithm problem on elliptic curves from exponential to polynomial time. If you can prove you own a key today, that proof should remain meaningful after quantum computers arrive.

H33-74 binds the STARK proof to three post-quantum signature families simultaneously:

• ML-DSA-65 (Dilithium): Based on the Module Learning With Errors problem over structured lattices. This is NIST's primary post-quantum signature standard (FIPS 204). Breaking it requires solving hard lattice problems.
• FALCON-512: Based on the NTRU lattice problem and short integer solutions over NTRU lattices. Mathematically distinct from the lattices underlying ML-DSA. Compact signatures make it practical for on-chain anchoring.
• SLH-DSA-SHA2-128f (SPHINCS+): A stateless hash-based signature scheme. Its security rests solely on the collision resistance of SHA-2 -- no algebraic structure, no lattice assumptions, no number-theoretic hardness. If hash functions remain secure, SPHINCS+ remains secure.

Three independent mathematical bets. An attacker must break MLWE lattices, NTRU lattices, and stateless hash functions simultaneously to forge an attestation. There is no known mathematical relationship between these three hardness assumptions. A breakthrough against one leaves the other two intact.

The binding process, implemented in src/proof_of_life/binding.rs, takes the STARK proof output and signs a compact message under all three schemes. The result is a 74-byte attestation: 32 bytes for the signing message (a SHA3-256 hash binding the proof to the public key and a timestamp) and 42 bytes for the compact receipt. This is the H33-74 format -- 74 bytes that attest to key ownership across three post-quantum families, anchored to Bitcoin via OP_RETURN. Immutable, timestamped, verifiable by anyone running a Bitcoin full node.

Performance

A proof system that takes minutes is an academic exercise. H33-74-AIR generates and verifies proofs at speeds that make it practical for production use.

Metric	Value	Notes
Cold proof generation	495ms	Apple Silicon (M-series)
Cold proof generation	813ms	Graviton4 (ARM64)
Cached proof generation	1.75ms	282x faster than cold
Cold verification	71us	Full constraint check
Cached verification	<1us	Sub-microsecond
Constraint count	~147,000	Goldilocks field
Execution trace	512 rows	One per scalar bit
Output	74 bytes	32B message + 42B receipt

Cold proof generation on Apple Silicon completes in 495 milliseconds. On Graviton4 ARM64, 813 milliseconds. These are full proof generations from scratch -- the prover builds the entire execution trace, commits via FRI, and produces the STARK proof. Once the twiddle factors, domain evaluations, and FRI layer commitments are cached, subsequent proofs for different keys drop to 1.75 milliseconds. That is a 282x speedup from caching alone.

Verification is even faster. A cold verification -- deserializing the proof, recomputing the FRI queries, checking all constraint evaluations -- takes 71 microseconds. With cached verification infrastructure, it drops below one microsecond. For comparison, a typical REST API round-trip is 50-200 milliseconds. The cryptographic verification is three orders of magnitude faster than the network latency to request it.

Beyond Bitcoin: Every secp256k1 Key, Everywhere

secp256k1 is not exclusive to Bitcoin. Ethereum uses the same curve. Every Ethereum address, every smart contract deployer key, every multisig signer -- all are secp256k1 public keys derived from private keys by the same scalar multiplication. H33-74-AIR works identically for any of them.

The applications extend far beyond individual key holders proving ownership to satisfy curiosity:

• Proof of reserves: Exchanges can prove they control the keys to their cold storage addresses without moving customer funds. Auditors verify the STARK proof and the on-chain OP_RETURN anchor. No trust in the exchange is required -- the math is the audit.
• Estate settlement: When a key holder dies, executors can prove to probate courts that the estate controls specific cryptocurrency addresses without exposing the keys to any party in the legal proceeding. The proof is filed as evidence. The keys remain secure in hardware custody until the court orders a transfer.
• Regulatory compliance: Institutions subject to proof-of-asset requirements can demonstrate control of on-chain holdings to regulators without creating transaction history, without revealing key material, and without the market impact of moving large positions.
• Key migration: Organizations transitioning from classical ECDSA to post-quantum signature schemes can use H33-74-AIR to create a verifiable, timestamped record linking their classical keys to their new PQ identities. The PostQuantumMigration (0x12) type is designed specifically for this use case -- a bridge from the pre-quantum to the post-quantum world, anchored immutably on Bitcoin.
• Dormant address verification: Any early Bitcoin miner, lost-key claimant, or institutional holder of unmoved coins can prove liveness without the existential risk of a transaction. The proof says "I am here, I hold this key, and I chose not to move these coins." Nothing more. Nothing less.

Why STARK, Not a Trusted-Setup Scheme

There are faster ZK proof systems for specific computations. Groth16 produces smaller proofs. PLONK requires a one-time universal setup. We use neither.

ZK-STARKs are transparent: no trusted setup, no ceremony, no multi-party computation generating parameters that must be destroyed. The security rests entirely on hash functions (SHA3-256) and the algebraic structure of the Goldilocks field. Both are well-understood. Both are quantum-resistant. There is no "toxic waste" -- no secret randomness that, if reconstructed, would allow forging proofs.

For a proof system that attests to control of potentially billions of dollars in cryptocurrency, the transparency guarantee is not a nice-to-have. It is a hard requirement. A trusted-setup ceremony conducted in 2026 might be compromised by a quantum computer in 2035. A STARK proof verified today will be equally valid in 2035, 2045, and beyond. The math does not age.

The 74-byte output size achieves this without bloat. Raw STARK proofs are larger -- kilobytes to hundreds of kilobytes depending on the circuit. The H33-74 format compresses the attestation to its essential content: the binding hash and the compact PQ receipt. The full proof can be reconstructed and reverified from the on-chain anchor at any time.

The Constraint Structure

For those interested in the AIR internals, here is a condensed view of the constraint layout:

// secp256k1 scalar multiplication AIR
// Field: Goldilocks (2^64 - 2^32 + 1)
// Trace width: 512 rows
// Constraint degree: 4 (point doubling) / 3 (conditional add)

// Each row contains:
//   - Accumulator point (x, y): 8 Goldilocks limbs (4 per coordinate)
//   - Scalar bit: 1 Goldilocks element (binary-constrained)
//   - Carry witnesses: variable count per operation
//   - Intermediate products: doubling slope, addition slope

// Boundary constraints:
//   Row 0: accumulator = identity point
//   Row 511: accumulator = claimed public key (pk)

// Transition constraints (per row):
//   1. Point doubling: lambda = (3*x^2) / (2*y) over 4-limb repr
//   2. New x = lambda^2 - 2*x (with carry propagation)
//   3. New y = lambda*(x - new_x) - y (with carry propagation)
//   4. Conditional add: if bit=1, add G to doubled result
//   5. Range checks: all limbs in [0, 2^64)

The full implementation is in src/zkp/stark/secp256k1_air.rs. The secp256k1 point arithmetic primitives -- constant-time, side-channel resistant -- are in src/proof_of_life/secp256k1.rs.

Prove It Without Moving It

H33-74-AIR eliminates the forced choice between privacy and proof. For the first time, any holder of a secp256k1 private key -- Bitcoin, Ethereum, or any chain using the same curve -- can demonstrate control without exposure, without movement, and with post-quantum security that will outlast the classical cryptography the keys were originally built on.

The proof is 74 bytes. The math is transparent. The anchoring is immutable. Patent pending.