PaperlayerView exact revision on arXiv

Source-linked AI summary

PQ-Vault: Provably Quantum-Safe Asset Custody for Unmodified Ethereum

Hassan Khodaiemehr, Khadijeh Bagheri, Chen Feng

arXiv:2610.29230v1quant-phcs.CRcs.DCcs.ITmath.IT

TL;DR

Exposed Ethereum ECDSA accounts can be spent after quantum key recovery, and existing approaches do not provide end-to-end quantum-safe custody on unmodified Ethereum. PQ-Vault combines a PQ-controlled vault, quantum-aware compact certificates and leader election, and an optimistic dispute path. Its evaluation reports checkpoint acceptance for 4.2 × 10^5 gas, while its prototype does not claim a 128-bit lifetime custody guarantee.

  • Problem

    Exposed Ethereum ECDSA accounts can be spent after quantum key recovery, while existing approaches do not provide end-to-end quantum-safe custody on unmodified Ethereum.

    Source: §1 · p. 1

  • Method

    PQ-Vault combines a vault released through ML-DSA and hash checks, a QROM-analyzed compact-certificate scheme and bounded-steering epoch seed, and single-reveal fraud proofs.

    Source: §1 · p. 1

  • Results

    4.2 × 10^5 gas is the acceptance cost for one checkpoint per epoch serving all users, and the evaluation includes real certificates for up to 65,536 validators.

    Source: §1 · p. 2

  • Takeaways & Limitations

    On unchanged account-based L1, a live asset safe after Q-day must be held under a contract predicate resting on PQ assumptions.

    Source: S1.2 Proofs of Theorem 2 and Theorem 3 · p. 14

    The prototype targets λ = 128 for grinding per checkpoint and does not claim a 128-bit lifetime custody guarantee; that target requires widened trees and the λ + log2 E rule.

    Source: §6.4 · p. 7

Abstract

from arXiv · show

A quantum computer could recover the key of any Ethereum account whose public key appears on chain. We prove that no sidechain or bridge that leaves Ethereum's rules unchanged can protect such accounts: their funds must move into a contract whose release condition relies only on quantum-safe primitives. We design \emph{PQ-Vault}, a custody system for unmodified Ethereum combining this vault, a quantum-safe proof-of-stake sidechain whose checkpoints carry compact certificates, and an optimistic dispute protocol. We give the first security proof of compact certificates against quantum attackers and a matching attack: with classically chosen parameters, the guarantee falls from 128 to about 60 bits, and a simple rule restores it. We show that a common seed-update rule in hash-chain proof of stake lets an attacker steer chosen slots and profit from splitting its stake, and give an election whose steering gain and inclusion delay are provably bounded against quantum attackers. Since compressing certificates with a pairing-based SNARK breaks quantum security, we use fraud proofs that need a single signature check. For 65,536 validators, a certificate is 0.8 MB, 260 times smaller than all signatures, and verifies in about 20 ms; the vault accepts a checkpoint for about 420,000 gas.

1 INTRODUCTION

Ethereum’s exposed ECDSA accounts are vulnerable to quantum key recovery, while existing approaches do not provide an end-to-end, quantum-safe custody architecture on unmodified Ethereum. PQ-Vault combines a PQ-controlled vault, quantum-aware certificates and leader election, and an optimistic dispute protocol.

1 INTRODUCTION

  • A quantum computer can recover the key of any Ethereum account whose public key has appeared on chain, enabling a valid transaction to spend its funds.Ethereum EOAs use ECDSA over secp256k1, and consensus relies on BLS signatures; both are broken in polynomial time by Shor’s algorithm.Source: §1 · p. 1
  • Existing approaches either depend on a Layer 1 change, secure assets on separate ledgers, or pay millions of gas for each on-chain post-quantum verification.The paper identifies no existing approach that provides end-to-end quantum-safe custody on unmodified Ethereum while amortizing costs across users.Source: §1 · p. 1

2 RELATED WORK

  • Prior work includes PQ ledgers, smart accounts, sidechains, light clients, and compact certificates, but the paper positions its contribution as their first end-to-end quantum-safe custody architecture for unmodified Ethereum.The authors also describe their quantum analysis of compact certificates as the first of its kind.Source: §1 · p. 1, §2 · p. 2

1 INTRODUCTION

  • Classically chosen compact-certificate parameters retain only about 60 of 128 security bits against quantum grinding, and the paper gives a reveal rule to restore the guarantee.The QROM analysis shows a q^2 grinding factor, rather than the classical q factor.Source: §1 · p. 1, §2 · p. 2
  • PQ-Vault combines an ML-DSA-and-hash-checked vault, a QROM analysis and reveal rule for compact certificates, a bounded-steering epoch seed, and single-reveal fraud proofs.The design targets unmodified Ethereum and gives a proof and evaluation for each component.Source: §1 · p. 1
  • One checkpoint per epoch serves all users and is accepted for 4.2 × 10^5 gas; the evaluation includes real certificates for up to 65,536 validators.The authors also release the evaluation and Solidity vault as an open artifact.Source: §1 · p. 2

3 PRELIMINARIES

The preliminaries specify the quantum-oracle and signature assumptions, then define compact certificates and the tools used to analyze their soundness in the QROM.

Preliminaries

  • The analysis models the hash as a quantum random oracle, treats ML-DSA’s internal hash and the commitment-and-seed cSHAKE256 oracle as independent, and assumes ML-DSA EUF-CMA security.The paper defines q as the adversary’s queries and t as all experiment queries, including honest-party and verifier queries.Source: §3 · p. 2
  • The verifier bounds the number of reveals using krev = ⌈(λ + 2 log2 q + κQ)/log2(Ws/Wp)⌉ and checks coin coverage, signature validity, and both Merkle openings.The listed checks also constrain signer weights and require every revealed signer to cover at least one coin.Source: §3 · p. 3
  • The QROM analysis uses compressed-oracle database properties and their instability to bound query success, with collision instability bounded by t/2^h.For the compact-certificate analysis, the paper also defines conditional instability and relates oracle-game success to checks on the measured database.Source: §3 · p. 3
  • A compact certificate commits to signer signatures and stake intervals, then derives coins to reveal attestors whose intervals cover them.The verifier checks the coins, intervals, signatures, and Merkle openings; the classical soundness bound is q(Wp/Ws)^krev.Source: §3 · p. 3

4 SYSTEM AND THREAT MODEL

The system places assets in an L1 vault and uses a PQ sidechain, relayers, and watchers; its security claims are conditional on stated cryptographic, timing, and monitoring assumptions. A central result is that external PQ checks cannot protect an exposed ECDSA-controlled asset on unchanged L1 unless its release predicate is changed to a PQ-based contract predicate.

4.1 Entities

  • The system comprises an L1 address with ECDSA and ML-DSA keys, ML-DSA-keyed sidechain validators, checkpoint relayers, watchers who may challenge, and a vault that escrows assets.Source: §4.1 · p. 3

4.2 Adversary

  • The adversary can recover exposed ECDSA or BLS keys after Q-day, make quantum oracle queries, corrupt less than one third of each epoch’s stake, suppress up to B honest proposers per slot, and order L1 transactions.Corruptions take effect after three epochs; offline honest validators count as corrupt in the leader-election analysis.Source: §4.2 · p. 3

4.3 Assumptions

  • The assumptions include L1 integrity and bounded transaction inclusion, QPT security of ML-DSA and the quantum random oracle model, slow key recovery for transactions that expose ECDSA keys, and at least one online honest watcher.The watcher must obtain certificate records or determine they are unavailable, evaluate them, and submit eligible timeout and challenge transactions.Source: §4.3 · p. 3

4.4 Security Goals

  • The security goals are custody safety, certificate soundness, explicitly bounded steering-resistant leadership, and bounded-time withdrawal given a live finality gadget.The liveness bound holds except with the small probability specified by Theorem 16.Source: §4.4 · pp. 3–4

4.5 Why External PQ Layers Cannot Protect EOAs

  • On unchanged L1, an exposed ECDSA public key can spend an asset under its ECDSA predicate; a live asset safe after Q-day must instead be held under a contract predicate resting on PQ assumptions.The paper compares this requirement with PQ signature-verifying contract accounts, whose per-operation cost is 1.3–8.2 × 10^6 gas, versus 1.0 × 10^5 gas per exit plus 4.2 × 10^5 gas per shared PQ-Vault checkpoint under the stated assumptions.Source: §4.5 · p. 4

5 PQ-VAULT DESIGN

PQ-Vault moves value through an L1 vault and PQ sidechain, with certified checkpoints and an optimistic dispute path. Its design binds PQ identities with a veto window, uses a steering-resistant stake-weighted election, and relies on validator certification under an explicit stake assumption.

5.1 Vault Contract

  • The vault stores escrowed balances and finalized checkpoint state, proposes bonded checkpoints for challenge, and pays a withdrawal only for an unspent leaf under a finalized withdrawal root.The withdrawal leaf uses a globally unique nonce as a nullifier, which is marked spent before the transfer.Source: §5.1 · p. 4

5.2 Time-Anchored, PQ-Vetoable Identity Binding

  • A rebinding waits D after request, and the current PQ identity can veto it by getting an ML-DSA-signed cancellation into a certified checkpoint by activation time.The stated binding-integrity conditions require D > ∆v and owner availability at least once per D − ∆v window; the adversary can otherwise change the binding only by forging ML-DSA, breaking certificate soundness, or before the first binding transaction is included.Source: §5.2 · p. 4

5.3 Sidechain Protocol

  • QPoS-S commits validators’ epoch seeds before reveal, orders reveals by stake-weighted rank, and derives the election seed from the reveal list; fallback proposers change who proposes, not the seed.The protocol uses ML-DSA-signed registration, cSHAKE256 commitments, and a fixed reveal window; validators missing their reveal are suspended from epoch e + 3 until re-registration.Source: §5.3 · p. 5
  • Honest validators sign a checkpoint only when its prefix is final and valid, its withdrawals root matches executed withdrawals, and its next attestor set is correctly listed.Source: §5.3 · p. 5
  • The vault accepts a checkpoint for certification, not validity, so custody safety depends on corrupt stake remaining below one third of every accepted attestor set.With Wp = ⌊W/3⌋, a sound certificate implies at least one honest validator signed; requiring Wp = 2W/3 would increase reveals and certificate size.Source: §5.3 · p. 6

5.4 End-to-End Flow

  • After deposit, users make PQ-signed sidechain transfers; withdrawals create Merkle leaves, and a relayer proposes a checkpoint that can be finalized after a challenge window or dispute.The end-to-end flow is deposit, sidechain credit, transfer, withdrawal leaf, checkpoint proposal, then an L1 withdrawal using the leaf’s Merkle proof.Source: §5.4 · p. 6

6 COMPACT CERTIFICATES AGAINST QUANTUM PROVERS

The section analyzes compact-certificate soundness against quantum attackers, gives a matching grinding attack, and adjusts the reveal rule. Its deployed prototype targets 128-bit grinding security per checkpoint, not a 128-bit lifetime custody guarantee.

6.1 Security Game

  • CERT-FORGE models an adaptively fixed weighted attestor list and wins when an accepted certificate claims more support than corrupt positions and honest signers provide.With Wp = ⌊W/3⌋, the stated condition f < 1/3 ensures that an accepted certificate that does not win implies an honest attestor signed its message.Source: §6.1 · p. 6

6.2 QROM Soundness

  • The QROM proof bounds certificate forgery without assuming entropy in honest signatures, and under its stated conditions the reduction changes ε(Ws) by at most a factor of 1 + 2^-51.The theorem applies to adversaries making quantum queries to the random oracle; its soundness game counts corrupt positions and honest signers of the forged message.Source: §6.2 · p. 6, §6.1 · p. 6

6.3 The Quadratic Dependence on q Is Necessary

  • With λ = 128, q = 2^64, and Ws/Wp = 2.55, classical parameters guarantee only 61.5 bits, while the attack succeeds with probability 2^-81.1.The attack establishes that the quadratic dependence on q is unavoidable; at Ws = 0.85W and w(C) = 0.30W, it reaches only 2^-102.8.Source: §6.3 · pp. 6–7

6.4 Parameter Rule and Security Budget

  • With λ = 128 and q = 264, the quantum reveal rule increases krev by a factor of 1.35 over the classical rule; measured certificate-size overhead is smaller because size grows with distinct reveals.The deployed bound is dominated by the 256-bit commitment term; the prototype targets λ = 128 per checkpoint for grinding and does not claim a 128-bit lifetime custody guarantee.Source: §6.4 · p. 7
  • Four verifier checks missing from the prior prototype made certificates forgeable: coin coverage, signer interval endpoints, a sound krev rule, and bounded reveal queries.The implementation includes all four checks and tests each negatively.Source: §6.4 · p. 7

7 LEADER ELECTION: FAIRNESS AND STEERING

The section replaces proposer-dependent seed selection with stake-weighted election and an epoch-seed design whose steering and inclusion bounds are analyzed against quantum attackers. The real protocol inherits these bounds under stated assumptions, including bounds on adversarially chosen transaction-inclusion windows.

7.1 Stake-Weighted Scores Form an Exponential Race

  • Stake-weighted exponential-race scores give each identity winning probability proportional to stake, and splitting a stake leaves the coalition’s winning probability unchanged.With h-bit sampled values, the winner differs from the continuous-score winner with probability at most N(N − 1)2^-h.Source: §7.1 · p. 7

7.2 Steering Through Proposer-Dependent Seeds

  • With proposer-dependent seeds, choosing among m candidates raises target-slot capture probability to pm(α) = mα/(1 + (m − 1)α); splitting identities increases the available options.At α = 0.3, the reported capture probability is 0.348 (+16%) with rushing and 0.338 otherwise.Source: §7.2 · pp. 7–8

7.3 Epoch Seeds: Ideal Model

  • In the ideal model, the adversary selects among at most m ≤ 2c reveal-set tables; its target-slot proposal probability is at most 1 − (1 − pB)^m.The expected epoch share is at most pB + c ln 2/(2k), and the probability of no guaranteed slot in a window accounts for candidate tables and possible window starts.Source: §7.3 · p. 8
  • For α = 0.3, the late-reveal bound is δLE ≤ 2^-41.4 without denial of service and ≤ 2^-40.7 with B = 1.These values use Lt = 25 and ℓs = ℓ0 = 52; the expected share excess over pB is at most 0.017 for k = 2000.Source: §7.3 · pp. 8–9

7.4 From the Ideal Model to the Protocol, Against Quantum Adversaries

  • The ideal-to-real QROM argument bounds the leader-election distinguishing error by ϵlead ≤ 2^-178.9 for the stated QPoS-S parameters.It assumes mildly adaptive corruption and the conditions of Theorem 12; the proof uses four hybrids, including hidden-input reprogramming and commitment binding.Source: §7.4 · p. 9
  • The real protocol preserves the ideal-model bounds up to an additive 2E(ϵLE + δLE), including a target-slot proposal bound of πcap + 2E(ϵLE + δLE).This result assumes mildly adaptive corruption and the conditions of Theorem 12.Source: §7.4 · p. 9
  • For α = 0.3 and k = 2000, an adversarially chosen inclusion window needs 31 slots without denial of service or 56 with B = 1 to meet ζ = 2^-40.For E = 2^20, the additional error term is below 2^-19.Source: §7.4 · p. 9

8 ACCEPTING CERTIFICATES ON L1

Direct L1 verification of post-quantum certificates exceeds Ethereum’s transaction gas cap, while a Groth16 acceptance path is unsound against quantum attackers. PQ-Vault instead uses optimistic single-reveal fraud proofs and proves safety and liveness for certificate acceptance and end-to-end custody under stated assumptions.

8 ACCEPTING CERTIFICATES ON L1

  • 1.8×10^8 to 1.1×10^9 gas for direct ML-DSA verification exceeds the per-transaction cap, so certificates must be compressed before L1 acceptance.Source: §8 · p. 9

8.1 A Non-PQ SNARK Cannot Be the Acceptance Path

  • A quantum polynomial-time adversary can use a valid Groth16 proof to finalize an arbitrary checkpoint and arbitrary withdrawals with probability 1 − negl.Shor’s algorithm recovers the CRS trapdoor, enabling proofs of false statements; the paper therefore uses an optimistic protocol with a post-quantum dispute path.Source: §8.1 · p. 9

8.2 Optimistic Acceptance with Single-Reveal Fraud Proofs

  • The optimistic protocol commits per-coin records, lets anyone challenge an index, and rejects a proposal when a response fails its local checks or a challenge goes unanswered.The local checks cover stake and range conditions, Merkle authentication, and signature verification; an open-all option makes records available on calldata for checking.Source: §8.2 · pp. 9–10
  • Honest proposals are eligible for finalization after the challenge period without a dispute, or by the stated post-dispute bound; frivolous challengers pay a bond, while an honest watcher’s cost is bounded.The theorem bounds proposal-safety error by the certificate bound plus δcol and states that a first challenge to a failing record returns the watcher’s bond with a reward.Source: §8.2 · p. 10

8.3 End-to-End Custody

  • Under the stated assumptions, finalized checkpoints preserve custody safety across epochs, and honest withdrawals are paid within a bound when transactions are included and an honest party relays each checkpoint.The proof also relies on corrupt attestor stake below one third, the honest-signing rule, and the sidechain finality event Fin; the lifetime reveal rule accounts for a union bound over epochs.Source: §8.3 · p. 10

9 IMPLEMENTATION AND EVALUATION

The evaluation measures compact-certificate size and verification, signature-scheme baselines, grinding attacks, networked certification, Ethereum gas costs, and leader-election fairness. Results show compact certificates substantially reduce signature data, while the QROM rule restores the stated grinding guarantee and the election bounds adversarial steering.

9.1 Certificate Size and Cost

  • 0.80 MB at N = 216: the QROM certificate is 260× smaller than shipping all signatures, with 18 ms verification on one core.Across configurations, the QROM rule raises krev by 35%, while measured size overhead is 19–34%; under Zipf stake the certificate is 0.57 MB at N = 216.Source: §9.1 · p. 11, Table 5 · p. 11

9.2 Baselines: Falcon and Hash-Based Signatures

  • Falcon-512 yields a certificate 2.2× smaller than Dilithium2 (r3), at 0.40 MB for N = 216 and 11 ms verification.Hash-based signatures produce smaller certificates than ML-DSA but verify 2.5–4.2× slower here and are synchronized; compact certificates lose for very small signer sets and high thresholds.Source: §9.2 · p. 11

9.3 Validating the Grinding Term

  • 81 bits for q = 2^64 and 65 bits for q = 2^80: the attack caps classically parameterized certificates below the intended 128-bit security, while the QROM rule guarantees λ bits for grinding.The SHA3-256 experiment’s mean trials matched (Ws/w(C))^krev within two standard errors across the tested ranges.Source: §9.3 · pp. 11–12

9.4 Networked Certification

  • 321, 288, 408, and 647 ms: median end-to-end certification times for N = 128, 512, 1024, and 2048, respectively; no round exceeded 716 ms.Sequential signature verification at the aggregator accounts for growing collection time, while certificate construction takes at most 22 ms.Source: §9.4 · p. 12

9.5 Cost on Ethereum: Measured Contracts

  • 4.2 × 10^5 gas: the optimistic propose-plus-finalize path per checkpoint, versus direct verification costs 2,600× or 430× more and exceeds the common 128 KB mempool limit.The open-all posting costs 3.0 × 10^7 gas; direct-verification estimates at N = 2^16 are 1.6 × 10^9 and 2.6 × 10^8 gas for the two verifier variants.Source: §9.5 · p. 12, Table 8 · p. 12

9.6 Leader Election

  • 0.347 vs. 0.348 at α = 0.3: under the runner-up rule, simulation matches the theory, while splitting into four identities raises capture to 0.357.With a fixed QPoS-S seed capture equals α within sampling error; steering across epochs remains below the stated πcap bound.Source: §9.6 · p. 12, Figure 3 · p. 13
  • 0.198–0.203: an adversary’s share remains near its 0.2 stake fraction when split across 1–50 identities; the election experiments also test bounds on seed steering and target-slot capture.The evaluation uses 200 validators over 40,000 slots for win frequencies and samples the exponential-race model directly for steering experiments.Source: §9.6 · pp. 12–13

10 DISCUSSION AND CONCLUSION

PQ-Vault protects assets on unmodified Ethereum only after escrow, with every release-path predicate relying on post-quantum assumptions. Its guarantees depend on stated threat, protocol, and evaluation boundaries.

10 DISCUSSION AND CONCLUSION

  • Only escrowed assets can be protected without changing L1, and every predicate on their release path must be post-quantum.The design’s guarantees assume Ethereum consensus is not attacked or is restored by a state-preserving hard fork.Source: §10 · p. 13
  • The sidechain is analyzed by simulation; the WAN experiment emulates latency on shared cores, and gas measurements use a local Foundry EVM.The prototype also omits the binding registry and canary.Source: §10 · p. 13
  • The design realizes quantum-secure compact certificates, steering-resistant stake-weighted proof of stake, and single-reveal fraud proofs, at 19–34% larger certificates and about 4.2 × 10^5 L1 gas per checkpoint.Certification takes 0.65 s at 2048 validators.Source: §10 · p. 13

S1 SYSTEM AND THREAT MODEL: PROOFS

On unmodified Ethereum, an exposed ECDSA key can spend any asset still governed by that predicate, regardless of an external protocol’s checks. Live post-quantum protection therefore requires contract custody and quantum-safe release authorization, assuming L1 consensus remains secure.

S1.1 On Assumption A1

  • If L1 consensus is subverted, no Ethereum contract can protect assets; the threat model instead targets account-level cryptography.The analysis assumes L1 consensus is not attacked or is restored by a state-preserving hard fork.Source: S1.1 On Assumption A1 · p. 13

S1.2 Proofs of Theorem 2 and Theorem 3

  • After Q-day, an adversary can use an exposed public key to create an L1-valid ECDSA transaction, which an external protocol cannot invalidate under unchanged L1 rules.L1 validity depends on its predicate and account state, so transaction ordering determines whether the attacker or owner moves first.Source: S1.2 Proofs of Theorem 2 and Theorem 3 · p. 14
  • For a live asset to remain safe after Q-day, every post-quantum release predicate must rely on PQ assumptions and Assumption A1, with no exposed ECDSA key able to authorize or redirect release without a PQ veto.On an account-based L1, this requires holding the asset under a contract predicate; the result excludes unexposed public keys and permanently unspendable assets.Source: S1.2 Proofs of Theorem 2 and Theorem 3 · p. 14

S2 PQ-VAULT DESIGN: DETAILS AND PROOF

The design replaces an expensive zero-knowledge binding with a timed, cancellable registry, while keeping escrow release independent of that registry. Its security relies on explicit timing and attestor assumptions, and several components remain outside the prototype.

S2.1 Why the Earlier Zero-Knowledge Binding Is Replaced

  • The earlier zero-knowledge binding is costly because it requires secp256k1 scalar multiplication in a transparent circuit, and it does not stop an exposed ECDSA key from spending through L1.The replacement authenticates the binding classically while that remains meaningful, then makes it immutable.Source: S2.1 Why the Earlier Zero-Knowledge… · p. 14

S2.2 Binding Mechanism in Full

  • A rebinding waits until after its activation time and can be cancelled by the current PQ identity through a sidechain operation finalized in a checkpoint.At most one rebinding may be pending; cancellation must be applied by the activation time, while the canary permanently disables ECDSA-authorized registry operations after a fixed-digest ECDSA forgery.Source: S2.2 Binding Mechanism in Full · p. 14

S2.3 Further Details of the Vault and Sidechain

  • Withdrawals use globally unique nonces to prevent duplicate payment, while validator commitments and secrets are sized to keep quantum hiding errors small.A missing reveal suspends a validator from epoch e + 3 rather than slashing it, because an honest censored reveal is indistinguishable.Source: S2.3 Further Details of the Vault and… · p. 14

S2.4 Proof of Theorem 4

  • If D exceeds the owner’s observation, sidechain, checkpoint, and application delays combined, and the owner is online within each D − ∆v window, a binding change requires an ML-DSA forgery, certificate-soundness break, or pre-initial-binding action.The stated timing bounds fail only with the probabilities given by the referenced theorems.Source: S2.4 Proof of Theorem 4 · p. 15

S2.5 Legacy EOAs and Recovery Hard Forks

  • The binding can pre-register a PQ identity for legacy EOA funds, but those funds are not protected by PQ-Vault itself.Escrowed deposits credit the vault directly, so the registry is not on their release path; the canary is defense in depth.Source: S2.5 Legacy EOAs and Recovery Hard Forks · p. 15

S2.6 Transparent Proof Layer

  • The optional transparent proof layer lets light validators check state transitions without re-execution, but certificate soundness does not depend on it.Any party can aggregate signatures into a certificate, so certification is not exclusive to the leader.Source: S2.6 Transparent Proof Layer · p. 15

S2.7 Trust in the Attestor Set: Further Discussion

  • The design assumes corrupt stake stays below one third of every accepted attestor set; the economic rationale for that assumption needs further assumptions about incentives and enforceability.Fraudulent signers are identifiable, but slashing them would require L1-held stake, which the prototype does not implement.Source: S2.7 Trust in the Attestor Set:… · p. 15

S3 COMPACT CERTIFICATES: PROOFS AND DE-

The compact-certificate analysis gives a quantum-query soundness bound and a matching grinding attack, showing that classical parameter choices can weaken the guarantee. The section also distinguishes deployed parameter rules, query-budget conditions, and hash-output-width effects.

S3.1 Proof of Theorem 5

  • The QROM soundness proof bounds certificate forgery by accounting for light, hit coin entries in a hash database and extracting an uncorrupted signer’s forgery otherwise.The database-game bound combines the fixed-property probability with collision and EUF-CMA terms; the real-oracle step then applies the theorem’s quantum-query bound.Source: S3.1 Proof of Theorem 5 · pp. 15–16

S3.2 Remarks on Theorem 5

  • Given 64-bit integer stakes in the contract and δ = 0.1, with krev < 2^11, the reduction term changes ε(Ws) by a factor of at most 1 + 2^-51.Source: S3.2 Remarks on Theorem 5 · p. 16

S3.3 Proof of Theorem 6

  • The matching grinding attack uses Grover search over salts to find a certificate whose sampled coins fall within the adversary’s stake interval.For the stated example, success lies between 2^-81.1 and 2^-61.5, with the factor 3π^2c^2ev left open; this is a query-model result.Source: S3.3 Proof of Theorem 6 · p. 16

S3.4 Deployed Parameters: Algorand State Proofs

  • The paper finds no vulnerability in Algorand state proofs and says their k + 2q target justifies the grinding term up to a 3.6-bit gap; classical k + q parameters fall under the attack theorem.The comparison assumes random-oracle modeling for the hash functions.Source: S3.4 Deployed Parameters: Algorand… · p. 16

S3.5 The Exact Parameter Rule

  • Rule (5) controls only the grinding term; its implication for ηg = 2^-λ is stated for T ≤ q(1 + 2^-20) and Wp ≥ W/4.T counts all hash-oracle queries on the L1 path, including certificate trees and checkpoint headers.Source: S3.5 The Exact Parameter Rule · p. 17

S3.6 Output Width and the Commitment Term

  • The commitment term is an upper bound, not an attack, and the theorem’s collision term uses the smallest output width among the relevant oracles and trees.The deployed vault uses Keccak-256 throughout; a uniformly widened 384-bit-node variant is described but not implemented.Source: S3.6 Output Width and the Commitment… · p. 17

S4 LEADER ELECTION: PROOFS AND DETAILS

The proofs show how seed selection can let a stake-weighted adversary steer leaders, then bound that steering in an ideal model and transfer the bounds to the real protocol under stated conditions. They also quantify reveal inclusion, liveness, and the long-range protection provided by checkpoint anchoring.

S4.1 Exponential Race and Steering

  • With m candidate seeds, the adversary’s target-slot capture probability is mα/(1 + (m −1)α); splitting stake preserves its rank-1 chance but increases its chance of holding multiple top ranks.The proposer-dependent runner-up rule also lets a single-identity adversary exceed its stake share in either analyzed timing case.Source: S4.1 Exponential Race and Steering · p. 17

S4.2 Ideal Model

  • Under one candidate table, a slot is not guaranteed only when its first B + 1 ranks fail to supply an honest proposer; with at most m candidates, target-slot capture is bounded by 1 −(1 −pB)m.The corresponding expected leadership share is at most pB + c ln 2/(2k), and a window of n specified slots has no guaranteed slot with probability at most min{1, mpn B}.Source: S4.2 Ideal Model · pp. 17–18
  • An honest reveal is included if its window has a guaranteed slot after the first, messages arrive within ∆S, slots last at least (L + 2)∆S, and reveal-window blocks finalize in time.For a window of ℓ slots, failure is bounded by pℓ−1 under each candidate table.Source: S4.2 Ideal Model · p. 18

S4.3 From the Ideal Model to the Protocol

  • The real-to-ideal proof hides the last honest secret and replaces candidate-seed scores with fresh independent scores; its query bound counts oracle queries before τ∗, not after.The proof uses a quantum hidden-input reprogramming bound and applies across the first E epochs.Source: S4.3 From the Ideal Model to the… · p. 19
  • For the first E epochs, the real protocol inherits the ideal-model bounds up to additive 2E(ϵLE + δLE), including explicit bounds on target-slot capture and adversarially placed windows.This transfer assumes mildly adaptive corruption and the stated conditions of Theorem 12.Source: S4.3 From the Ideal Model to the… · p. 19

S4.4 Additional Remarks

  • The hash-chain seed update based on the actual proposer lets a coalition choose among candidate next-slot seeds by publishing, skipping, or selecting among its top-ranked identities.The reveal order limits the late-reveal choice, and the stated parameters yield ϵlead ≤2−178.9 for t = 264 and c̄ = 24.Source: S4.4 Additional Remarks · p. 20

S4.5 Consequences in Detail

  • For α = 0.3 and k = 2000, an honest transaction is included within 31 slots without denial of service or 56 slots with B = 1, except with probability ζ + 2E(ϵLE + δLE) for ζ = 2−40.Turning inclusion into finality additionally requires liveness of the chosen finality gadget; the 1,352-slot reveal window occupies about two thirds of a 2,000-slot epoch.Source: S4.5 Consequences in Detail · p. 20

S4.6 Long-Range Attacks

  • Anchoring checkpoints makes forks before the latest vault checkpoint reject outright; a later fork needs a certificate for the current attestor set while its members remain bonded.Bootstrapping nodes use the vault log as their weak-subjectivity source.Source: S4.6 Long-Range Attacks · p. 20

S5 L1 ACCEPTANCE: DISPUTE PROTOCOL AND PROOFS

The dispute protocol lets watchers challenge compact certificate records while keeping safety independent of data blobs and requiring a single-record signature check. Under the stated watcher, timing, and cryptographic assumptions, the proofs bound unsafe finalization and describe honest-proposal liveness and custody safety.

S5.1 Record Commitment

  • The relayer commits records in a Merkle tree whose leaves encode each record and include hashes of its signature and both paths.Source: S5.1 Record Commitment · p. 20

S5.2 State Machine

  • A proposal remains pending until finalized, rejected, or stale; watchers can challenge a coin record or force all records on-chain when blob data are unavailable or inconsistent.An authenticated record that fails Local, or an expired deadline, rejects the proposal; malformed third-party submissions merely revert.Source: S5.2 State Machine · pp. 20–21

S5.3 Timing

  • With Tch = 7 days, ∆open = ∆resp = 1 day, and ∆post = 2 days, every pending proposal is eligible for a final transition by Tfin ≤11 days after inclusion.A transition still requires a party to submit it; safety does not depend on that call.Source: S5.3 Timing · p. 21

S5.4 Proofs

  • A valid Groth16 proof of “all certificates verify” cannot secure vault acceptance against quantum attackers, who can recover the trapdoor and forge a proof for a false statement.The simulator can then produce an accepted proof for an arbitrary checkpoint and withdrawals.Source: S5.4 Proofs · p. 21
  • Theorem 19 bounds unsafe proposal finalization by Theorem 5 plus δcol; an honest relayer’s proposal is eligible by τ0 + Tch without dispute or τ0 + Tfin otherwise.If the relayer submits finalize, it is finalized within a further ∆inc.Source: S5.4 Proofs · p. 21

S5.5 Remarks

  • Custody safety depends on accepted withdrawals being authorized by the legitimate PQ owner on the honest sidechain, with payments bounded by credited deposits and the escrow.The proof also assumes the sidechain finality gadget’s safety; it is not re-analyzed here.Source: S5.4 Proofs · p. 22, S5.5 Remarks · p. 22

S6 EVALUATION: ADDITIONAL DETAILS

The supplementary evaluation details describe the released implementations, test setup, and gas accounting. They report measured checkpoint costs and extrapolated costs for posting all records, alongside constraints on the experiments and verifier.

S6.1 Artifacts

  • The artifact includes Rust and Python certificate implementations, a multi-process network harness, QPoS-S and grinding simulators, and a Solidity vault tested with FIPS 204 signatures.The Rust prototype uses round-3 Dilithium rather than FIPS 204, and a FIPS 204 backend cross-checks headline results.Source: S6.1 Artifacts · p. 22

S6.2 Machines

  • The reported machine timings are single-threaded medians from three two-vCPU environments, including a heterogeneous light-client VM.Source: S6.2 Machines · p. 22

S6.4 Network Experiment Setup

  • The network harness uses real TCP sockets and FIPS 204 signatures, with validators across five latency regions, 10% offline validators, and aggregation stopping at 80% stake.Signing time is charged using measured round-3 Dilithium2 time because validators share two vCPUs.Source: S6.4 Network Experiment Setup · p. 23

S6.5 Contract Implementation and Tests

  • Contract tests confirm that failing authenticated records reject proposals, while tampered records, wrong paths, and wrong key addresses from third parties revert without rejection.The tests also cover challenge completion, open-all posting, substituted withdrawal roots, exact record counts, and single payment of withdrawals.Source: S6.5 Contract Implementation and Tests · p. 23

S6.6 Gas Accounting and Extrapolation

  • The propose and finalize rows sum to 4.2 × 105 gas, while the single happy-path test measures 4.1 × 105 gas with either verifier.Measurements use Foundry under EIP-7623; direct verification exceeds the per-transaction cap.Source: S6.6 Gas Accounting and Extrapolation · p. 23
  • At N = 216 with 189 distinct reveals, open-all posting extrapolates to 1.6 × 109 gas for the NIST verifier and 2.6 × 108 gas for the packed verifier.Posting 193 records takes 803,580 bytes across seven transactions and costs 3.0 × 107 gas.Source: S6.6 Gas Accounting and Extrapolation · p. 23

S7 EXTENDED DISCUSSION

The extended discussion specifies the L1, watcher, and leader-election assumptions, then describes limits in the evaluation and prototype. It also bounds leader-election effects under stated conditions.

S7.1 Scope of the L1 Assumption

  • Assumption A1 requires L1 consensus to remain secure or be restored by a state-preserving hard fork, and bounds censorship by the challenge window Tch.The seven-day window is motivated by the time block producers could be bribed to exclude a challenge; A3 is needed for transactions exposing an ECDSA key.Source: S7.1 Scope of the L1 Assumption · p. 23

S7.2 Data Availability and Watcher Incentives

  • One honest watcher online is assumed; bonds deter griefing, while the prototype omits the binding registry and canary and leaves relayer compensation analysis open.Open-all requests can force a relayer to post records at about 3.0 × 10^7 gas, versus about 2.4 × 10^4 gas for the request; the reveal rule targets λ = 128 per checkpoint, not a lifetime budget.Source: S7.2 Data Availability and Watcher… · pp. 23–24

S7.3 Public Leader Schedule

  • With L = 3 fallback proposers, inclusion requires n = 31 slots without denial of service or n = 56 with B = 1, except with probability 2^-40 + 2E(ϵLE + δLE).At α = 0.3, the honest proposer is available with probability 0.3 per slot without denial of service and 0.514 with B = 1; without fallbacks, suppressing one leader per slot could halt the sidechain.Source: S7.3 Public Leader Schedule · p. 24
  • The QPoS-S reveal order bounds target-slot probability to 0.622 at α = 0.3, versus 0.997 for an adversary owning the last four reveals and 0.348 for the hash-chain runner-up attack.For α ≤ 0.2, target-slot probability is at most 0.265; the result assumes no denial of service, and inclusion of honest reveals assumes each reveal-window block is finalized within its slot.Source: S7.3 Public Leader Schedule · p. 24
  • The leader-election analysis excludes instant adaptive corruption, and hidden schedules requiring a PQ verifiable random function or secret leader election remain unanalyzed.Corruptions take effect three epochs after they are requested; the sidechain is delayed, but certification is not, when a leader is censored or attacked.Source: S7.3 Public Leader Schedule · p. 24

S7.4 Limitations of the Evaluation

  • The sidechain is evaluated by simulation, not deployment; network tests emulate WAN latency on shared cores for five rounds and do not inject relayer or data-withholding faults end to end.Gas measurements use a local Foundry EVM, the hash-based baseline combines measured components, and the standard BFT finality gadget is not re-analyzed; the election bounds assume timely finalization of each reveal-window block.Source: S7.4 Limitations of the Evaluation · p. 24
Loading 2610.29230v1…