QProof: Quantum-Resilient Web3 Research Paper

BF

BountyForge Team

October 24, 2026

quantum computingweb3saveproffingQProof

Oct 24, 2026 · @Jeffrey agabaenwere Linkdlin X

Abstract

Quantum computers threaten web3 in two separate ways, and they need two separate fixes: Shor's algorithm breaks the signatures that authorize spending, while Grover's algorithm distorts the incentives of proof-of-work without breaking it. Bul-Q is a proposed design that addresses both: a hybrid classical plus post-quantum signature layer with hash-based (STARK) aggregation, a proof-based migration path for legacy keys, and QR-PoW, a proof-of-work construction that closes the known quantum mining attacks.

The signature problem is the urgent one. Public 2026 estimates put a cryptographically relevant attack on secp256k1 at roughly 1,200 to 2,330 logical qubits, and recent hardware-architecture studies put the physical footprint between about 19,000 and under 500,000 qubits depending on assumptions. The PoW problem is subtler: raw Grover mining is uneconomic, but the Superlinearity Problem (Park and Spooner) and the difficulty-increase attack (Bailey and Sattath) show that a small, fast quantum miner can still bend consensus.

This document gives the threat model, the architecture, the QR-PoW construction, a security analysis with explicit open problems, an evaluation plan and a four-phase implementation plan. Status: a design proposal. The PoW security claims are conjectures until proven in the quantum random oracle model, and the plan treats that proof as a deliverable, not an assumption.

1. Threat model and state of the art (Oct 2026)

Shor's algorithm is the near-term threat to web3 because it breaks the elliptic-curve signatures (ECDSA over secp256k1, BLS over BLS12-381) that authorize every transfer; Grover's algorithm is a slower, mostly economic threat to proof-of-work. No hardware today can run either attack at scale: the best demonstrated machines have about 1,000 to 1,200 physical qubits and at most around 100 logical qubits, per the Quantum Horizon survey. The gap is closing on paper, though, and resource estimates for secp256k1 fell repeatedly in 2026.

1.1 Shor against signatures: published resource estimates

Source	Date	Logical qubits	Physical qubits	Notes
Google Quantum AI and Ethereum Foundation whitepaper	Mar 2026	not stated here	under 500,000	Superconducting architecture; circuits withheld, zero-knowledge proof of existence released
Schrottenloher open reproduction	May 2026	about 1,192 (space-optimized), 1,446 (gate-optimized)	not stated here	Public circuit reproduction; scales as 4.355n + O(sqrt n)
IonQ end-to-end blueprint	Sep 2026	1,457	19,397	Trapped-ion, qLDPC codes; 25.7 days per attempt; 63.3% heuristic success; an estimate, not a demonstration
Quantum Horizon survey (arXiv 2606.14484)	Jun 2026	about 1,200 to 2,330	about 0.5 to 320 million	Range across conservative to aggressive assumptions

The spread in physical qubits (tens of thousands to hundreds of millions) is the real uncertainty, not the logical count. The planning consequence is that migration must start now and finish on a multi-year schedule, because the hardware timeline is unknowable and the migration timeline is not.

1.2 Grover against proof-of-work

Grover search finds a hashcash solution in about sqrt(N) oracle calls instead of N. Three facts make raw quantum mining uneconomic today:

Each oracle call is a fault-tolerant reversible double-SHA-256 circuit of roughly 474,168 T-gates, far costlier than an ASIC hash.
Parallel Grover scales only as the square root of the number of machines, against linear scaling for ASIC farms.
Difficulty adjustment absorbs any uniform speedup.

That is the conclusion of the Quantum Horizon survey and of earlier analysis (Aggarwal et al., 2017). It is not the end of the story. Three structural attacks exploit Grover's shape rather than its raw speed:

Superlinearity (Park and Spooner, FC 2023). Success probability after k Grover iterations grows like k squared, not k. Doubling sequential depth quadruples success, which breaks the linear reward-per-work assumption that makes mining incentive-compatible. They prove an impossibility result for a large class of PoW puzzles and propose a design in a random-beacon model.
Difficulty-increase attack (Bailey and Sattath, 2024). A quantum miner manipulates timestamps to multiply difficulty by c. Classical miners pay c times more; Grover pays only sqrt(c) times more, while fork choice credits the block with weight c. By choosing c large, a single small quantum miner builds a shorter chain with more cumulative work. Time to attack scales as 1/r squared epochs, where r is the miner's fair share of rewards.
Progress-free stale blocks (Aggarwal et al., 2018). A quantum miner can stop Grover and measure at any moment, so blocks arrive in bursts and stale rates rise. Their countermeasure is to commit to the timestamp before the Grover iterations begin.

P_k = \sin^2\!\big((2k+1)\,\theta\big), \qquad \sin\theta = \sqrt{p}

Verified numerically (p = 2^-40): doubling k from 10,000 to 20,000 multiplies P_k by 4.00, where a classical miner's success only doubles.

1.3 Standards, policy and chain status

NIST: FIPS 203 (ML-KEM), FIPS 204 (ML-DSA) and FIPS 205 (SLH-DSA) were finalized on August 13, 2024. FN-DSA (Falcon, FIPS 206) was still a draft through mid-2026, so QProof treats it as optional.
Policy: the G7 Cyber Expert Group's January 2026 roadmap sets a 2026 to 2029 migration window and quantum-resistant systems through 2034. Google moved its internal post-quantum deadline to 2029.
Bitcoin: BIP-360 (Pay-to-Merkle-Root, a quantum-resistant output type) was merged in February 2026 and deliberately contains no post-quantum signature algorithm; BIP-361 proposes a migration framework with a legacy-signature sunset.
Ethereum: the Ethereum Foundation formed a post-quantum team in January 2026; EIP-8141 (frame transactions, draft) offers signature agility so accounts can switch verification schemes.
Others: Algorand has published a Falcon-based roadmap, QRL is post-quantum by design, and Project Eleven announced a collaboration with the Solana Foundation.

2. Design goals and non-goals

QProof must let a chain survive the day a cryptographically relevant quantum computer (CRQC) appears, without a flag-day hard fork and without trusting a new, unproven assumption for funds that are safe today.

Goals

G1, safe spending: no key whose public half has ever been exposed can authorize a transfer once a CRQC exists, unless it is also protected by a post-quantum key.
G2, crypto-agility: signature schemes are replaceable per account without a chain-wide fork.
G3, legacy recovery: holders of existing ECDSA or Ed25519 funds can migrate with a proof that does not reveal the exposed public key.
G4, quantum-robust consensus: a quantum miner gains no more than its square-root hash speedup, and no structural fork-choice advantage.
G5, bounded cost: block size, verification time and fees grow by a stated, measured factor, not an open-ended one.

Non-goals

Quantum key distribution or quantum networking (a separate technology track).
Protecting data that was already public and weakly signed before migration (see risks, section 8).
Replacing proof-of-stake chains' consensus; the signature layer applies to them, QR-PoW applies only to PoW chains and to PoW-style anti-spam or sybil puzzles.
Claiming a proof. Where this document says "conjecture", the evaluation plan names the experiment or proof that would settle it.

3. QProof architecture

QProof has three layers that can ship independently: a hybrid signature layer, a hash-based aggregation layer that pays for the size of post-quantum signatures, and a migration module that brings legacy funds across.

[embedded content: architecture · 3 lanes, 9 components]

Migration ends in an account that follows the hybrid rule of the first lane, and the consensus lane applies only to chains that mine.

3.1 Hybrid signature layer

During the transition an account is valid only if both a classical signature and a post-quantum signature verify (an AND rule). A CRQC then cannot spend from an account whose post-quantum key was registered before its classical public key was ever exposed. Once the community judges the classical half obsolete, accounts switch to post-quantum-only verification through a per-account flag, with no hard fork.

User accounts: ML-DSA-44 or ML-DSA-65 (FIPS 204), chosen per account.
Long-lived roots (validator identities, treasuries, bridge multisigs, contract upgrade keys): SLH-DSA (FIPS 205), because its security rests only on hash functions.
Optional: FN-DSA (Falcon) for compact signatures once FIPS 206 is final.

Size is the cost that hits first. Public key plus signature, computed from the FIPS parameter sets:

Scheme	Public key (bytes)	Signature (bytes)	Total (bytes)	Multiple of ECDSA
ECDSA secp256k1 (compressed key)	33	64	97	1.0x
ML-DSA-44	1,312	2,420	3,732	38.5x
ML-DSA-65	1,952	3,309	5,261	54.2x
ML-DSA-87	2,592	4,627	7,219	74.4x
SLH-DSA-SHA2-128s	32	7,856	7,888	81.3x

3.2 Aggregation layer

Each block carries one STARK proof that all N signatures in the block verify, instead of N raw signatures. STARKs are hash-based, so they are themselves post-quantum and need no trusted setup. A proposer or an open prover market builds the proof; validators check only the proof. This is the main R&D risk in the design: the proving cost of verifying ML-DSA inside a STARK is unmeasured, so Phase 2 has a hard gate on it (section 7). If the gate fails, the fallback is raw signatures with a larger block-size budget and a fee schedule priced per byte.

3.3 Legacy migration

Funds fall into two classes, and only one of them can be saved by proof alone.

Public key never exposed (for example, pay-to-public-key-hash outputs never spent from): the holder proves, in a STARK, knowledge of a secret key whose public key hashes to the address, and binds that proof to a new post-quantum key. The classical public key is never revealed, so a CRQC has nothing to attack. This follows the framework in IACR ePrint 2026/352; this document reviewed its abstract only, and Phase 0 includes a full review.
Public key already exposed (reused addresses, key-path outputs, any account that has signed): a CRQC can derive the secret key, so proof of knowledge of that key proves nothing. These funds can be saved only by proof of knowledge of the wallet seed or of an earlier commitment. Funds with neither are the policy problem behind Bitcoin's BIP-361 debate over a legacy-signature sunset.

3.4 Chain integration points

Chain family	Entry point	QProof module	Status
EVM (Ethereum, L2s)	Account abstraction; EIP-8141 draft adds verification-scheme agility	ML-DSA verifier plus AND-rule account	Draft EIP; feasibility to confirm in Phase 1
Bitcoin	BIP-360 Pay-to-Merkle-Root output type (no signature scheme specified)	Hash-based leaf scripts, migration proofs	Signature opcode not yet specified
Solana	Program-owned vault accounts	Anchor program with hash-based or ML-DSA authorization	Compute-budget fit unmeasured
Move chains (Aptos, Sui)	Account authenticator and key rotation	PQ authenticator plus rotation module	Per-chain support to confirm in Phase 1

4. QR-PoW: quantum-robust proof-of-work

QR-PoW keeps hashcash's asymmetry (cheap to verify, costly to find) and removes the three structural quantum advantages from section 1.2 by making time objective, bounding coherent search depth, and capping what any one block can claim. It is a conjecture-level design: Park and Spooner prove that a large class of ordinary puzzles cannot be fixed, so QR-PoW deliberately leaves that class. This document reviewed their abstract, not the full construction; Phase 0 reconciles QR-PoW with their random-beacon scheme and adopts theirs wherever it is stronger.

4.1 The four rules

R1, beacon-bound, time-boxed rounds. Time is divided into rounds of length tau. The puzzle for round r is H(beta_r, parent, tx_root, miner_key, nonce) < T, where beta_r is a public random value unpredictable before round r begins. A solution is valid only for its own round and must arrive within a bounded delay. A miner can therefore never carry a coherent quantum search across rounds, which caps sequential Grover depth at k_max per round.
R2, no miner-chosen time. Headers carry the round index, not a free timestamp. Time is whatever the beacon says it is. This removes the timestamp lever behind the difficulty-increase attack and the commit-before-search countermeasure of Aggarwal et al. is satisfied by construction.
R3, clamped retarget and capped weight. Difficulty is retargeted per epoch from the count of beacon rounds the epoch actually took, with a per-epoch change clamp (initial proposal: 1.25x up or down, against Bitcoin's 4x). Fork choice credits each block with min(D_b, (1+eps) * D_expected), so no block can be worth more than the schedule allows.
R4, memory-hard oracle (optional hardening). The hash is replaced by a memory-hard function in the style of Argon2 or RandomX, so each reversible quantum oracle call needs large quantum memory or heavy recomputation. This raises the per-call quantum cost but costs verification time and weakens ASIC and GPU neutrality arguments, so it is a configuration flag, not a core rule.

4.2 Why this should work, and the break-even condition

The superlinearity comes from sequential depth: success after k Grover iterations is about (2k+1)^2 * p for small p. Running K independent machines at fixed depth scales success only linearly in K. R1 bounds depth at k_max, so a quantum miner's advantage per oracle call becomes a constant factor A, which difficulty adjustment absorbs, instead of a factor that grows with effort.

A \approx \frac{(2k_{\max}+1)^2\, p}{k_{\max}\, p} \approx 4\,k_{\max}, \qquad k_{\max} \le \frac{\tau}{t_{\text{oracle}}}

Quantum mining is unprofitable per unit cost when A is smaller than rho_q, the cost of one fault-tolerant quantum oracle call divided by the cost of one classical ASIC hash. Published circuit analysis (about 474,168 T-gates per double-SHA-256 oracle) and the Quantum Horizon survey place quantum mining thousands of times slower than ASICs today. The parameter tau must be chosen so that the inequality holds with margin: shorter rounds shrink k_max and A, but raise network-delay sensitivity. Phase 1 turns this into a measured tau range.

4.3 Open dependency: the beacon

R1 and R2 need a beacon that no miner can bias or predict. On a pure proof-of-work chain there is no committee to produce it, and deriving it from previous block hashes lets miners grind by withholding blocks. Two candidate instantiations go to Phase 1:

Hybrid beacon: a post-quantum distributed randomness beacon run by a staked committee (hash-based designs such as HashRand and Silk are post-quantum friendly), with PoW still selecting blocks.
Sequential-work beacon: a hash-chain proof of sequential work, whose quantum security for the Cohen-Pietrzak construction was shown using the compressed-oracle technique (ePrint 2020/1305), anchored by block hashes.

Until one passes analysis, the design is not complete. This is the honest weak point, and it is the first item on the research agenda.

5. Security analysis and open problems

Of the seven threats below, three are covered by established assumptions, two rest on conjectures this project must test, and two are open. Nothing here is proven for QR-PoW yet.

Threat	Mitigation	Status
Shor on an exposed signature key	AND-rule hybrid account; post-quantum key registered before the classical key is exposed	Established, assuming ML-DSA and SLH-DSA hold
Shor on legacy keys already exposed	Seed-knowledge proof; otherwise policy (freeze or sunset)	Partly open: policy, not cryptography
Raw Grover mining	Difficulty adjustment; optional R4	Known uneconomic today; R4 benefit is conjecture H2
Superlinearity (Park and Spooner)	R1 caps coherent depth	Conjecture H1
Difficulty-increase attack (Bailey and Sattath)	R2 removes miner timestamps; R3 clamps retarget and caps weight	Argued, not proven
Progress-free stale-block bursts	R2 commits time before search (Aggarwal et al.)	Follows published countermeasure
Beacon bias or grinding	Hybrid or sequential-work beacon	Open

Open problems

P1, formal proof. Prove QR-PoW incentive-compatible in the quantum random oracle model, or reduce it to the Park and Spooner construction.
P2, beacon instantiation. Choose and analyze the beacon for pure-PoW and hybrid chains (section 4.3).
P3, proving cost. Measure the STARK cost of verifying ML-DSA signatures; it decides whether aggregation is viable.
P4, quantum cost ratio. Derive rho_q from published reversible-circuit costs and update it as estimates fall; the estimates for breaking secp256k1 fell several times in 2026 alone.
P5, unmigrated funds. Decide, through each chain's governance and not through this project, what happens to funds whose owners never migrate.

Separately, confidentiality needs its own track: signatures protect authorization, not secrecy, so any on-chain encryption or encrypted-mempool design needs ML-KEM (FIPS 203) against harvest-now-decrypt-later. That is outside QProof's scope but is flagged so it is not forgotten.

6. Evaluation plan and benchmarks

Six experiments decide whether each conjecture and cost assumption survives contact with measurement. The pass gates are proposals for you to confirm or change, not industry standards.

The size problem is concrete: 1,000 transactions with ML-DSA-65 keys and signatures carry about 5.26 MB of authorization data, against about 97 KB with ECDSA, a 54x increase before any aggregation.

Experiment	What it measures	Proposed pass gate
E1, STARK proving cost	Time and memory to prove N ML-DSA-65 verifications; proof size and verify time	Block-sized proof built within one block interval on 8 or fewer commodity GPUs; verify under 50 ms
E2, raw-signature fallback	Block propagation and orphan rate with 5.26 MB of signatures per 1,000 transactions	Orphan rate rises by under 1 percentage point on a simulated 100-node WAN
E3, quantum-miner simulation	Attacker share of chain work under the Bailey and Sattath strategy, with and without R2 and R3	Attacker advantage stays at or below its square-root hash-power gain
E4, round-length sensitivity	Orphan rate and finality delay as tau varies	A tau range exists where E3 holds and orphan rate stays under 2%
E5, quantum cost ratio	rho_q computed from published reversible oracle circuits, re-run as estimates change	A(tau) is below rho_q with at least 10x margin at the chosen tau
E6, migration proof	Size, proving time and on-chain verification cost of the legacy-key proof	Proof verifies within 2x the gas or compute of a plain ML-DSA transfer

Results go in a public benchmark repository with reproducible scripts, so reviewers can rerun them as the underlying quantum resource estimates change.

7. Implementation plan

The plan runs 12 months in four phases, each ending in a gate that can change the plan; phase 2 is the pivot because experiment E1 decides whether block-level aggregation is viable. Month ranges are proposals sized for a small team and are not commitments.

[embedded content: roadmap · 4 phases, 4 gates]

Phase 1 delivers the parts that protect funds soonest, the hybrid accounts and the simulator, and does not wait on the beacon problem.

Stack

Core: Rust for verifiers, prover glue and the simulator; Solidity with Foundry for the EVM account; Anchor for Solana; Move for Aptos and Sui.
Post-quantum primitives: audited ML-DSA and SLH-DSA implementations only, such as liboqs or PQClean-derived code, never hand-written.
STARK frameworks to evaluate in E1: Plonky3, Stwo and RISC Zero, compared on proving time and proof size for ML-DSA verification.

First two weeks

Read Park and Spooner (ePrint 2022/1423), Bailey and Sattath (arXiv 2403.08023) and ePrint 2026/352 in full, then write the QR-PoW reconciliation memo.
Create the repository with CI, a benchmark-harness skeleton and a threat-model file taken from section 1.
Run an audited ML-DSA-65 verifier inside a Foundry test and record gas per verification; it feeds E2 and E6.
Build the E3 simulator skeleton: honest miners, one quantum miner paying the square root of difficulty, timestamp manipulation switched on and off.
Decide public or private for the first ePrint draft (section 8).

8. Risks and decisions needed

The largest risks are technical dependencies that could force a fallback, and each has one.

Risk	Effect	Fallback
STARK proving of ML-DSA too costly (E1 fails)	No aggregation; blocks grow about 54x in signature data	Raw signatures, larger block budget, per-byte fee schedule
No bias-resistant beacon for pure PoW (P2)	R1 and R2 cannot ship on a pure-PoW chain	Hybrid PoW plus staked-committee beacon
QR-PoW not provable (P1)	Security stays a conjecture	Adopt the Park and Spooner construction as published
Standards churn (FN-DSA draft, HQC)	Rework of verifiers	Scheme-agile account format from day one
Side channels in ML-DSA and SLH-DSA code	Key leakage	Audited libraries only, constant-time tests, fuzzing, external review
Estimates fall again	Timeline compresses	Re-run E5 quarterly; keep Phase 3 releasable early
Chains do not adopt	No deployment path	Ship as a library, SDK and migration tool usable per account

Decisions needed

Target: build QProof first as a signature-and-migration library for existing chains, or as a new PoW chain that carries QR-PoW. This document assumes the library first, because it is the part that protects funds sooner and does not depend on the open beacon problem.
Order: write the paper first and prototype second, or prove the aggregation cost (E1) first, because that result decides whether the architecture changes.
Venue: a public ePrint and open repository from the start, or private until Phase 1 results exist.

References

As of 2026-10-14. Only the Bailey and Sattath abstract was opened in full; every other entry was read as a search-result excerpt, so figures marked as estimates should be checked against the primary paper before this goes public (that check is the first Phase 0 task).

Quantum attacks on signatures

Quantum attacks on proof-of-work

Migration and standards

Beacons