Hi List, With the progress of BIP360's P2MR address format, and Ethan's recent thread [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 OP_CHECKSIG Nothing crazy going on here. It's just your regular old secp256k1 Schnorr spending condition. Leaf 2: SPHINCS OP_DROP 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 [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 [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: OP_DROP OP_CHECKSIGVERIFY ... 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 [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.