* [bitcoindev] Post Quantum HD Wallets with fallback SPHINCS keys
@ 2026-03-28 20:29 'conduition' via Bitcoin Development Mailing List
0 siblings, 0 replies; only message in thread
From: 'conduition' via Bitcoin Development Mailing List @ 2026-03-28 20:29 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 20811 bytes --]
Hi List,
With the progress of BIP360's P2MR address format, and Ethan's recent thread
<https://groups.google.com/g/bitcoindev/c/7jkVS1K9WLo> [1] about
cryptographic agility, now seems a good time to consider how wallet
standards would look in a quantum-resistant environment. This email demos
techniques we can use as drop-in post-quantum replacements for classical HD
wallet standards, and shows how to mitigate problems that many people
commonly believe to be practical impediments to PQ wallet design.
Most people I've seen engage with the subject of quantum resistance seem
receptive to the idea of hash-based signatures as a conservative "backup"
algorithm, to be used in the event a Cryptographically Relevant Quantum
Computer (CRQC) threatens UTXO ownership before a more succinct and
efficient cryptosystem is discovered, standardized, and adopted into
consensus. Though the exact "backup" sig algorithm to use is an open
debate, discussions tend to converge on SPHINCS+/SLH-DSA, or some
derivative thereof.
For the purposes of this email, I will assume that someday we will add
verification opcodes for some SPHINCS variant to consensus, and extrapolate
what we can build based on that premise.
Design Goals
- *Drop-in replacement*: All major features of BIP32, BIP39, and BIP44
remain usable under a quantum-aware standard.
- *Performance*: High-frequency operations like child key derivation have
approximately the same performance as classical algorithms.
- *Evergreen*: Should provide a framework for long-term holding which is
resilient against novel cryptanalytic attacks on either signature
algorithm. The basic design can be reused if newer cryptosystems are
adopted in the future.
Approach
Drop-in replacement for BIP32's `CKDpriv` algorithm is easy. We simply
extend it to derive a child SPHINCS key pair alongside the child secp256k1
keypair, and append the SPHINCS key to the BIP32 xpriv structure. To ensure
SPHINCS keys aren't made vulnerable if parent secp256k1 keys are
compromised, we mix the parent SPHINCS secret key into the child key
derivation hash function when available.
Drop-in replacement for BIP32's `CKDpub` algorithm is more difficult.
SPHINCS does not have any algebraic structure, and so we cannot define any
way to derive child SPHINCS public keys using an existing parent public
key. However, since SPHINCS is expected to be used only as an emergency
fallback, we can construct a post-quantum xpub by attaching an SPHINCS
public key to a regular BIP32 xpub, and allow unhardened child xpubs to
simply inherit the SPHINCS public key of the parent xpub. This will require
some mitigations to curb surveillance.
SPHINCS Review
Let's review the structure of SPHINCS keypairs. This will be important
since we want to securely generate them deterministically.
A SPHINCS keypair consists of four byte strings of equal size (16 bytes
each for a NIST-I (128-bit classical) security level):
- `sk_seed`: A secret seed value. This is, more or less, the secret key
material. (SECRET)
- `sk_prf`: A secret salt which randomizes the exact hypertree path used
for SPHINCS signatures. (SECRET)
- `pk_seed`: A public salt which randomizes all hash operations for the
signer and any verifiers. (PUBLIC)
- `pk_root`: The root hash of a merkle tree, computed deterministically
from `sk_seed` and `pk_seed`. When validating a signature, verifiers
attempt to recompute this. (PUBLIC)
In the official specs, a SPHINCS secret key consists of all four of these
values, while the pubkey consists of just `(pk_seed, pk_root)`.
Core Ideas
In a PQ wallet with fallback SPHINCS-like keys, a *quantum extended secret
key (`qxsk`)* is composed of:
- A chaincode (16 or 32 bytes)
- A secp256k1 secret key (uint256)
- A SPHINCS secret key, which we *redefine* as `sk_seed || pk_seed` (bytes)
For *hardened* secret key derivation, we can hash/HMAC these three values,
along with a 32-bit integer index `i`, to produce a "Key Delta" for a given
child `i`, which is then applied to the parent secp256k1 & SPHINCS keys
using scalar addition and XOR respectively. This derives the `i`-th child
secret key.
An *quantum extended public key (`qxpk`)* is composed of:
- A chaincode (16 or 32 bytes)
- A secp256k1 public key (Point)
- A SPHINCS public key, which is `pk_seed || pk_root` (bytes)
For *non-hardened* key derivation, we can hash/HMAC these three values,
along with a 32-bit integer index `i`, to produce a similar "Key Delta",
which is then applied to the parent secp256k1 public key. In this case,
there is no way to homomorphically rerandomize the parent SPHINCS pubkey,
so instead all child `qxpk`s inherit the SPHINCS pubkey from their parent.
Address Construction
Let's assume BIP360's P2MR address format is available so we have quantum
resistant script pubkeys with taproot-esque script trees.
We can then construct what I'll call a *Single-Signer Quantum Resistant
(SSQR)* address from a `qxpk` using the following script leaves:
Leaf 1: Schnorr
<ec_pubkey> OP_CHECKSIG
Nothing crazy going on here. It's just your regular old secp256k1 Schnorr
spending condition.
Leaf 2: SPHINCS
<nonce> OP_DROP <spx_pubkey> <OP_SPXCHECKSIG>
This leaf assumes a hypothetical `OP_SPXCHECKSIG` opcode in consensus which
validates signatures for some variant of SPHINCS. In general it could be
any hash-based signature scheme though.
The `nonce` which is dropped at the beginning of the script is a
pseudorandom byte string (probably 16 bytes should suffice),
deterministically derived uniquely for this address. It exists to randomize
the script's TapLeaf hash, which is necessary to preserve on-chain privacy
of SSQR addresses.
Since any unhardened child `qxpk` inherits a SPHINCS pubkey from its
nearest hardened parent, any addresses in the same BIP44 account will share
the same `spx_pubkey`. Without the nonce, any Schnorr spends from such SSQR
addresses in the same account would be linkable on-chain, because they
would share a common merkle node in their P2MR witness data. With a unique
nonce per address, each tap leaf hash is distinct and appears unrelated
unless the scripts are revealed.
The nonce should be derived from off-chain data so that observers cannot
predict or guess it. The most obvious solution is to hash/HMAC the Schnorr
and SPHINCS pubkeys and the chaincode, which are all contained in a `qxpk`.
Usage
An SSQR address of this form could be spent from using *EITHER* a Schnorr
signature from `ec_pubkey`, *OR* a SPHINCS signature from `spx_pubkey`.
Regular everyday spending from such addresses would use the Schnorr leaf.
The addition of the second leaf would add 32 bytes to the merkle path
witness data on top of the 32 byte pubkey and 64 byte BIP340 signature when
spending via the Schnorr leaf, but otherwise this is the only effect the
SPHINCS leaf would have upon everyday transaction sizes for now.
Coins secured in a fresh SSQR address should be secure against breaks in
either Schnorr or SPHINCS signature algorithms. In case of a cryptanalytic
break in either algorithm, a hodler may simply use the opposite algorithm
when spending. I expect the most likely use case for this will be for
hodlers who migrate to SSQR wallets in the next few years. If a CRQC
appears some time in the next decade or three, these long-term hodlers may
recover their coins safely via the SPHINCS script leaf even after decades
of inactivity. If no CRQC appears, they can use the Schnorr leaf.
This premise of safety this only applies if the address is unused. For
instance: If the Schnorr script leaf has been revealed, a powerful CRQC
could steal any coins sent to the address in the future by applying Shor's
algorithm to invert the secp256k1 pubkey.
Properties
- Even if a CRQC attacker - like a CRQC - learns a secp256k1 parent secret
key, they cannot derive hardened child keys without also cracking the
SPHINCS keypair: They need `sk_seed` to produce hardened Key Deltas.
However, the attacker *can* produce non-hardened Key Deltas, and thus find
child secp256k1 keys which they can use to steal coins. Thus, a `qxpk` is
still as sensitive as today's BIP32 xpubs, and should be guarded from
quantum-enabled attackers.
- Key Deltas are not sensitive data - the key material is. By themselves,
Key Deltas give no information about the child or parent keys. Key deltas
can thus be generated from an intermediate pseudorandom key `prk`, derived
from the parent secret key material. The `prk` can be safely cached in
memory or stored on disk in plaintext.
- The child key derivation algorithms and SSQR address construction
template can be repurposed in the future if we were to adopt a more
efficient - but probably more risky - signature algorithm such as isogeny-based
schemes SQIsign and PRISM
<https://delvingbitcoin.org/t/compact-isogeny-pqc-can-replace-hd-wallets-key-tweaking-silent-payments/2324>
[3], or a hypothetical lattice-based signature scheme which supports
rerandomization. In this future, the Schnorr leaf of the SSQR address could
be replaced by the novel signature scheme, and stalwart SPHINCS remains in
the backup leaf in case of cryptanalytic breakthroughs.
I'll now elaborate on the motivation for some of the design choices I'm
suggesting.
Eliding `sk_prf`
Astute readers will notice I omitted `sk_prf` from SPHINCS secret key
representations.
*`sk_prf` is only needed during SPHINCS signing, not for pubkey generation*.
The only purpose of `sk_prf` is to protect against attackers who can
compromise the RNG of the signer at *signing time* but not at *keygen time*.
Think of it as "backup randomness" for signature generation.
*`sk_prf` is non-critical to the soundness and correctness of the SPHINCS
signature scheme*. Concretely: Rotating `sk_prf` after key-generation time
does not adversely affect correctness of signatures made after rotation,
nor would it meaningfully affect security of the key, provided the new
`sk_prf` isn't predictable by attackers.
Because `sk_prf` is not necessary to compute the public key, and because in
an HD wallet environment we would end up generating `sk_prf`
deterministically anyway, we elide it from secret key representations.
Wallets may generate `sk_prf` on demand during signing by taking bytes from
a hash or HMAC of meaningful secret key material, e.g.
`TaggedHash("SLH-DSA/sk_prf", sk_seed || pk_seed)`. We should standardize
some technique to derive `sk_prf`, but for technical correctness it is not
strictly or urgently required: `sk_prf` can be any unpredictably-random
16-byte string.
Deferring `pk_root` Computation
You may notice that in hardened key derivation steps, I omitted `pk_root`
from the inputs of the hash used to derive hardened key deltas.
A SPHINCS pubkey consists of two values: `pk_seed` and `pk_root`. The
`pk_seed` can be derived pseudorandomly from secret data much like a
chain-code in BIP32, and handed out as-is. However `pk_root` must be
computed from `pk_seed` and `sk_seed`.
`pk_root` generation in SPHINCS is a *very computationally intense task*.
While it can be accelerated through parallelization as my earlier research
<https://conduition.io/code/fast-slh-dsa/> [2] has shown, it still takes at
least a millisecond on modern CPUs to derive a `pk_root`. Less optimized
implementations take 30+ milliseconds. The problem gets even worse on
embedded systems like hardware wallets, where it can take several seconds
to compute a single `pk_root`. So it'd be nice if we could defer this task
as much as possible. Turns out, it is very possible.
`pk_root` is a deterministic output of a pure function:
`spx_keygen(sk_seed, pk_seed)`. Thus if we have a hash `H(sk_seed ||
pk_seed || pk_root)`, then `pk_root` contributes no entropy into the
resulting output hash, and we can omit it without changing the security
properties of the output.
In the context of HD wallets, this means when we derive child secret keys
with a "hardened" derivation step a la BIP32's `CKDpriv`, we can safely
omit the `pk_root` from any hashing inputs. This is not necessarily the
case for "non-hardened" public key derivation where `sk_seed` isn't always
available, and so we include `pk_root` in the hash function inputs there so
that it may serve as an indirect commitment to `sk_seed` [4].
With this construction, we can defer computation of `pk_root` until we
reach the first non-hardened derivation step.
Imagine we follow BIP44 standards and introduce a new purpose constant
`360` for the first generation of SSQR addresses. We derive an HD wallet
receiving address for account 2 at index `i` with the key path:
m/360'/0'/2'/0/i
*Then the first three steps (m/360'/0'/2') in this derivation do not
require any SPHINCS algorithms at all!* We need only to generate
pseudorandom SPHINCS key material via hash/HMAC calls, and use XOR to
combine SPHINCS keys with key deltas. This is very efficient, faster even
than the concurrent secp256k1 operations.
After the last hardened step (.../2'), we must now compute the `pk_root` of
the SPHINCS key, because it is required for subsequent non-hardened child
key derivation. This takes heavy work, but because child keys inherit
`pk_root` from their parents, this `pk_root` can be cached and reused for *every
non-hardened child key* in the BIP44 account at `m/360'/0'/2'`.
Since most single-signer wallets follow BIP44 structure, *most wallets will
only ever need to run the SPHINCS keygen algorithm once at account genesis*,
and from then on the wallet can fetch `pk_root` from a secure cache on
disk, or else re-derive it once at wallet startup.
This possibility should especially excite hardware wallets devs, whose
platforms have very constrained compute power and can't efficiently execute
SPHINCS keygen repeatedly with the current generation of hardware. SPHINCS
keygen can be amortized to an up-front setup cost, paid once per BIP44
account. HW users can stash their coins in SSQR cold wallet addresses while
still using today's hardware wallets. Someday if they need to rescue their
coins from a CRQC using SPHINCS, then users may upgrade to new future
hardware which may be better optimized for SPHINCS by then.
Deferring SPHINCS Implementation
When PQ wallets are first standardized, it will take time for devs to write
and audit SPHINCS libraries, and even more time for wallets to adopt those
libraries. Some of those wallets will act faster than others.
To grease the wheels of this migration, early-adopter wallets which jump to
support SPHINCS key generation right away can export serialized `qxsk`s
which contain a `pk_root` in addition to other SPHINCS key material.
A wallet importing this type of key will NOT have to derive `pk_root` on
their own. *The importing wallet can construct SSQR addresses using the
`pk_root` supplied externally without having to recompute it or understand
SPHINCS algorithms at all*. The wallet's devs can introduce SPHINCS signing
and keygen code on their own time, when/if SPHINCS is ever needed, without
compromising the safety or security of the user, and still spend with
secp256k1 keys in the meantime.
Compatibility
The `qxsk` design is easily integrated with existing seed phrase standards
like BIP39, SLIP39, or Aezeed. However, it is NOT compatible with BIP32.
While we retain the usage framework of BIP32 with this design, the
algorithms are entirely different.
For wallets which already have access to seed entropy or a seed phrase, we
could design an algorithm which securely hashes the seed into a `qxsk`, and
proceed with child derivation from there. This would be straightforward and
parallel to BIP32 master key derivation. With a SPHINCS keygen
implementation and a `qxsk`, any wallet could easily derive SSQR addresses
independently and would require no additional user action to migrate
besides unlocking the wallet.
However, some wallets may have only a master BIP32 extended private key,
i.e. the root xpriv at `m/`, and may not save the seed phrase entropy. I
believe this is the case for LND for instance, but LN devs please correct
me if I'm wrong. Such wallets would have to ask the user to input their
seed phrase again so that we can reuse a hypothetical master `qxsk`
derive-from-seed algorithm.
Alternatively, the best option to maximize compatibility would be to derive
a master `qxsk` as an "offshoot" of a BIP32 master xpriv, i.e. a child
thereof. While this is mostly secure since BIP32 master pubkeys are rarely
if ever exported, from an engineering perspective this commits wallets to
always supporting BIP32 master keygen as a prerequisite to `qxsk` master
keygen, even well into the uncertain post-quantum future where BIP32 may
well be a relic of the past. Thankfully BIP32 master keygen doesn't involve
any secp256k1 point arithmetic, and so would be quite straightforward to
keep around if we needed to go this way.
The more significant concern is for airgapped or hardware wallets, which
generally don't treat any BIP32 xpubs (even master xpubs) as secret data,
and so will gladly give them up to the host system if requested. This could
be an attack vector, because a quantum enabled attacker could ask the
airgapped wallet for its BIP32 master xpub, crack its secp256k1 public key
to get the corresponding BIP32 master xpriv, and then derive the master
`qxsk` from it.
A survey of wallets is needed to determine which option is best.
Multisignature
We can non-interactively combine two or more `qxpk`s into an n-of-n
Multi-Signer Quantum Resistant (MSQR) address, by aggregating BIP340 public
keys using MuSig2 to form the Schnorr leaf, and using both SPHINCS pubkeys
in the SPHINCS leaf:
<nonce> OP_DROP <spx_pubkey1> OP_CHECKSIGVERIFY ... <spk_pubkey2>
OP_CHECKSIG
The SPHINCS leaf nonce would be derived deterministically from the
chaincodes and pubkeys from both contributing `qxsk`s.
Yes, combining SPHINCS keys in this way will require witnesses which grow
linearly with the number of pubkeys involved. It has awful compactness. But
remember, this leaf is only ever meant to be used as a backup in case of a
sudden cryptanalytic breakthrough against secp256k1. Ideally the peers in a
multisig could come to agreement on this risk when it becomes imminent, and
use the Schnorr leaf to move to a new (TBD) secure signature scheme before
that leaf is ever needed.
For as long as the Schnorr path remains usable, spends from an MSQR address
are indistinguishable from those of an SSQR address, and so we retain
taproot's privacy benefits for multisignature contracts.
More complex multiparty contracts like HTLCs could be constructed in
similar ways, adding more leaves and structuring the P2MR tree to give the
most commonly used spending paths the highest positions in the P2MR tree.
Conclusions
I hope this shows how, despite hash-based signatures' lack of algebraic
structure, we can still use them as drop-in additions to bolster existing
wallet standards without compromising on user experience. Yes, it will take
work and engineering, and it's a complex coordination problem, but it's
completely surmountable if we put in the work.
For a more long-term solution which competes with the compactness of
Schnorr, I am hopeful about the idea of pursuing compact isogeny-based
signature schemes
<https://delvingbitcoin.org/t/compact-isogeny-pqc-can-replace-hd-wallets-key-tweaking-silent-payments/2324> [3],
but whether or not we take that route in the future, having a framework for
agile, secure, and efficient wallets with conservative fallback keys is a
thing we'll want either way to hedge our bets.
regards,
conduition
[1]: https://groups.google.com/g/bitcoindev/c/7jkVS1K9WLo
[2]: https://conduition.io/code/fast-slh-dsa/
[3]: https://delvingbitcoin.org/t/compact-isogeny-pqc-can-replace-hd-wallets-key-tweaking-silent-payments/2324
[4]: One could make an argument that we could elide `pk_root` from
non-hardened derivation hash inputs as well, but doing so does not provide
much performance benefit, since any child `qxsk` inherits `pk_root` from
its parent, and that `pk_root` will have to be computed (or fetched from a
cache) for the child keys to be useful. As such I took a more cautious
stance and included `pk_root` in the non-hardened derivation inputs.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/03e2dd41-7161-4779-a4ed-fad8dedd24b1n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 22416 bytes --]
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2026-03-28 21:19 UTC | newest]
Thread overview: (only message) (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2026-03-28 20:29 [bitcoindev] Post Quantum HD Wallets with fallback SPHINCS keys 'conduition' via Bitcoin Development Mailing List
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox