Way overkill for the migration period. If you are going to do hybrid, then a simple WOTS+C that takes about 400 bytes will suffice as preparation for q-day, assuming no key reuse as standard practice. Since q-day may never actually come, and there is no working CRQC out there as far as we know, accidental key reuse is still secure under ECDL security assumption. On the day that breaks, you can look around for a better alternative. Lot of R&D may go into PQ signatures in the mean time.
Good point, OTS + stateless hybrid is safe against key reuse as long as the stateless leg is not broken, but I worry about people screwing up key management and forgetting about the issue and later causing a mess if q-day ever comes.
If wallets have to worry about key reuse then it is not a drop-in replacement. IMO only practically stateless schemes should qualify for OP_CHECKSIG overload since that is the established norm with secp256k1. One or few-time schemes can either get their own opcode or just be done via Script.
Falcon is small but risky, SPHINCS+ is safe but big, so I wouldn’t expect many P2PKH users now. But think about other uses:
- for oracles, an OP_CHECKDATASIG oracle attestation needs to happen only once and small proofs can be emitted as NFTs so you “pay” the 8kB only once.
- for vaults, the SPHINCS+ OP_CHECKSIG can be a conditional which the contract would carry but would flip to only post q-day, and in the meantime the vault would use secp256k1.
Also, the P2PKH:SPHINCS+ creates a reliable target for which to prepare migration plans. If we work out the commit-delay-reveal-challenge scheme then we must have a reliable migration target for it, so people can pre-commit and save their commitments knowing that they’ll be good indefinitely. If q-day never comes, they just keep using same old P2PKH:secp256k1. If q-day comes, they have their aged commitment which they can use to safely migrate P2PKH:secp256k1 to P2PKH:SPHINCS+, and then from there maybe migrate to some lighter future scheme.
But OTS (one-time-signature) / FTS (few-time-signature) schemes can be used too, maybe we should propose OP_CHECKFTS and OP_CHECKDATAFTS instead of this overload now.
PS if wallets are ready to prevent key reuse, then this contract is a generic way to allow yourself safe migration in case of q-day:
OP_DEPTH <2> OP_EQUAL
OP_IF
OP_DUP
OP_HASH160
<$(<key.public_key> OP_HASH160)>
OP_EQUALVERIFY
OP_CHECKSIG
OP_ELSE
OP_DUP
OP_HASH256
<{migration function body hash}>
OP_EQUALVERIFY
<0> OP_DEFINE
<0> OP_INVOKE
OP_ENDIF
The function body is a simple forward covenant that moves the UTXO’s contents to a pre-committed locking script and without revealing the P2PKH key from the other IF branch:
// pre-committed migration function
// migrates without exposing the p2pkh key
<
// set the pre-commited locking script on the output
<{migration target locking script}>
OP_INPUTINDEX OP_OUTPUTBYTECODE OP_EQUAL
// pass on UTXO's state to the output
OP_INPUTINDEX OP_UTXOVALUE <300> OP_SUB
OP_INPUTINDEX OP_OUTPUTVALUE OP_LESSTHANOREQUAL OP_VERIFY
OP_INPUTINDEX OP_UTXOTOKENCATEGORY
OP_INPUTINDEX OP_OUTPUTTOKENCATEGORY OP_EQUALVERIFY
OP_INPUTINDEX OP_UTXOTOKENCOMMITMENT
OP_INPUTINDEX OP_OUTPUTTOKENCOMMITMENT OP_EQUALVERIFY
OP_INPUTINDEX OP_UTXOTOKENAMOUNT
OP_INPUTINDEX OP_OUTPUTTOKENAMOUNT OP_EQUAL
>
But for this to work, you need to have a good migration target so you can write that function now and start using such wallet now.
This is compact: only 71 bytes redeem script (BitauthIDE link).
1 Like
Yeah, I keep thinking being quantum ready just means you have the ability to spend your cold storage funds long and short range protected. For that SPHINCS+ feels overkill. It’s perfectly okay as an option, but technically an OTS is also enough.
Post q-day hybrid might be pointless. It’s really just there to have an extra protection for the migration itself imo. Altho the value that is economically rational to attack with a q-computer might be quiet high for a good while. So not necessarily immediately defunct.
Key reuse is a big problem especially since the centralized exchanges nowadays tend to encourage or even demand it for “verification” in compliance with idiotic regulation.
1 Like
Exactly. With the above contract:
- You just spend normally via the EC path, inputs are still small. But you must not reuse keys, so your current UTXO keys are always hidden behind P2PKH hash. You can use this even after q-day if QCs are too slow. But if you get hit by a bus your coins will be safe for inheritors because the state there will be UTXOs with hidden keys.
- Q-day comes. Instead of revealing the P2PKH path, you use the migration path to safely move all UTXOs to a new address. The address needs to be a reliable target you can commit to now and store the redeem script contract in backup alongside your wallet seed.
Imagine you leave a wallet seed as inheritance. It’s not touched for 10 years. Q-day comes after 5 years. Your inheritor uses the migration path to move everything to SPHINCS+. That could be multiple UTXOs with the same address. It’s still safe because SPHINCS+ is stateless. From there, he can make N 8kB spends to move to whatever more efficient system will be available in 10 years.
But if you made an unreliable migration target then your inheritor is stuck:
- Use the P2PKH path and QCA can potentially steal.
- Use the migration path and have coins moved to a now-broken scheme and QC or classical attackers can steal.
IMO we need at least 1 reliable stateless scheme. If price is 8kB input, so be it, you won’t use this by default. You’d only use this as a safe target to activate emergency migrations at unknown point in the future, like the above contract’s path, or to prepare an aged commitment in advance of consensus-level migration activation. We use it as hedge, because it’s the most reliable and least likely to have some cryptosystem flaw.
2 Likes
Yes I get where you are coming from. I think for bitcoin block space efficiency is crucially important. Stateful signers with only fallback to stateless signing are a smaller price to pay overall. It pushes a lot of complexity to the wallet, not ideal.
If you have an PQ OTS primitive and you can do merkle trees (maybe an other primitive to most efficiently verify leaf inclusion?) then you can do any kind of EC/EC+OTS/EC+FTS schemes with a few base primitives, tailored by wallet and app devs to the use case at hand.
Imagine a balanced merkle structure (or sub-structure of a larger merkle forest), the path you go down can be represented by a binary sequence, 011001… which can come from a cryptographic hash of the EC signature so you can trivially implement flexible stateless signing. As opposed to implementing SPHINCS+ as an OP with a baked in parameter set, I generally prefer this flexible approach.
1 Like
Block space efficiency matters, but it’s not the binding constraint right now. FYI right now it is actually CPU efficiency that’s the propagation bottleneck (not bandwidth, not UTXO db). If there’s just 1 TX missing then compact block relay won’t propagate the block until full validation is completed. In principle this can be solved, then it will be just PoW check and Merkle tree verification on relaying critical path and bandwidth will become the bottleneck. Check analysis here: ac-0353f40e / Faster Blocks for Bitcoin Cash · GitLab
Our limit right now is 32 MB, but only about 100-200kB are used. Even if everyone switched to SPHINCS+ as default, we’d go up to ~16 MB and TX fee would jump 80x-160x (still cheap, tho). But we don’t plan to remain at 20k TXs/day forever. So yes, post q-day we will need something more efficient as the daily driver.
What I’m saying is: secp256k1 will remain as the efficient daily driver. What we need first is a hedge, not an immediate replacement. We will just keep using secp256k1. SPHINCS+ would be used only as a nuclear bunker to survive q-day, as a place to where you safely evacuate to temporarily. We don’t know when q-day will happen. By the time it happens maybe FN-DSA and ML-DSA will get broken and replaced by something else. Chances are SPHINCS+ won’t. The bunker survives. Then when dust settles you can move from the bunker to something more efficient.
The wallet complexity is exactly the problem. Stateful schemes (WOTS+, XMSS, LMS) break catastrophically on index reuse. A wallet restore from seed, a hardware signer reset, or a poorly-implemented exchange hot wallet burns the key, and the user learns about it only when their coins are stolen. The CHIP explicitly rejects stateful schemes in the OP_CHECKSIG path for this reason: that opcode carries an implicit contract of “reuse is safe.” Adding a footgun to it is worse than adding nothing.
We can add those primitives later as a parallel path. They don’t replace SPHINCS+ but give wallets that want to build custom constructions the tools to do so. The CHIP just ships one reliable complete scheme first.
Bitcoin didn’t ship with OP_ECADD and OP_ECMUL and let everyone implement their own signature scheme in Script. Satoshi picked ECDSA, it was good enough, and that standardization is why seed imports between wallets actually work. SPHINCS+ fills the same role for the PQ era: one scheme everyone can target. SLH-DSA is FIPS 205 final: no pending changes, no wire-format risk. That’s what makes it a reliable bunker you can commit to now.
Only later did people think about adding primitives for other curve operations. But first, we needed a reliable OP_CHECKSIG. SPHINCS+ gives us that for the PQ era. Give it a decade and we may add a lighter registry entry for the daily driver, and dedicated opcodes for stateful schemes, but the bunker is the prerequisite. Something like this strategy:
Step 1: SPHINCS+ activated in consensus
- Reliable migration target for everyone
Step 2: Vault pattern (userspace)
- Self-sovereign migration option for proactive users
- Deterministic from seed, no extra backup
- Quantumroot (LM-OTS vault) fits here, too, available already now without needing any consensus changes
Step 3: Commit-delay-reveal-challenge (future consensus)
- Protocol-level migration for legacy secp256k1 coins
- Needs SPHINCS+ as its reliable target
- Needs to be specified BEFORE secp256k1 lockdown
- Users can start aging commitments early
Step 4:
- Lighter OP_CHECKSIG in the future when lattices mature more
- More efficient stateful signature support with dedicated opcodes
1 Like
Agreed, unlikely that SPHINCS+ will be broken. It’s ginormous, complicated and not designed for blockchain use. An other aspect worth considering is airgaped signers. They will likely go extinct with schemes like SPHINCS+.
1 Like
Haha, point taken. Though secp256k1 wasn’t designed for blockchain either, it just existed. ECC was novel in 2009 while RSA dominated, and it turned out fine. Maybe lattices will, too.
The difference is: Satoshi limited himself to exactly one curve, and today we still can’t make use of all the nice secp256r1 hardware. We don’t have to limit ourselves that way. The registry lets us ship SPHINCS+ as the hash-based bunker AND plan to follow on with ML-DSA shortly after, or even at the same time. If lattices hold, ML-DSA becomes the daily driver with hardware support. If they don’t, SPHINCS+ still works. We’re not forced to bet on one family the way Satoshi bet on one curve.
1 Like
Few more thoughts…
This sounds nice, since right now these could offer the most byte-efficient PQ authentication schemes. However, the potential for a shitshow is there: with everyone rolling their own the risk of buggy implementations grows and we also fragment the wallet ecosystem.
It’s a different flavor of the same problem we see with ML-DSA and FN-DSA signing: the gap between “the math works” and “nobody loses money” is wide, and filling it correctly across dozens of independent wallet implementations is where things break.
OP_CHECKSIG “registry” framework prepares us to one day easily activate whatever will be proven good. Right now, the only safe stateless scheme seems to be SPHINCS+. That’s just the state of things now, and it will buy us time until another reliable stateless scheme surfaces.
NIST is evaluating 9 more systems: AEST, HAWK, MAYO, MQOM, QR-UOV, SDitH, SNOVA, SQIsign, UOV
It’s not clear what will survive the apocalypse and be used as a future daily driver. We can afford to wait because we don’t need a daily driver now, because secp256k1 is still good. Right now, all we really need is a bunker.
1 Like
Absolutely. I think SHRINCS/SPHINCS works the following: you have a stateful signer that can use extremely efficient signatures, and you have static backup, but on that path you only have access to SHPINCS as in stateless signing in case your trusted hw device croaked. You simply have different EC keys, the recovery derivation has no access to the stateful signing EC private keys only the xpubs.
1 Like
This? SHRINCS: 324-byte stateful post-quantum signatures with static backups - Protocol Design - Delving Bitcoin Feel free to share any other relevant links.
From that topic:
So this would effectively introduce
OP_SPHINCSandOP_WOTSrather than a singleOP_SHRINCS, and let wallets implement theSHRINCSscheme via the Taproot tree. I agree this is a valid approach.
Since we’re doing hard-forks we can just overload OP_CHECKISG for SPHINCS+ (as proposed) and have the reliable backup. Hypothetical OP_CHECKOTS would complement that. Thing is, functionally we already have PQC one time signatures (Script-implemented). We don’t have stateless PQC signatures. That’s why I feel our priority now should be adding SPHINCS+ to OP_CHECKSIG.
They can also be implemented in script. The diff between stateful and stateless is how your merkle leafs are selected. If your path depends on a cryptographic hash of the message signed and the tree is large enough for practically unlimited signing, you are stateless.
1 Like
That’s not the only diff. The number of leaves needs to be huge so there’s no chance of picking the same leaf multiple times. Practical difference is one scheme can fit in Script now, the other can’t. If we had Nervos VM (compiles to RISC-V bytecode) then we could just implement whatever we want in Script (and they did SPHINCS+).
So what should our strategy be? Make VM and limits expressive and loose enough so that we can implement both in Script? Or “hardcode” vetted schemes behind an opcode (OP_CHECKSIG overload for stateless, hypothetical OP_CHECKOTS for stateful)? What’s the benefit of going in the direction of flexibility here? OP_CHECKSIG is a core feature, imagine if we didn’t have it and had only OP_ECADD/MUL and every wallet rolled their own in Script, what a mess that would be!
2 Likes
There’s also stateless-ish 
So EVM folks thought to make a trade-off where they get higher risk of internal key reuse but smaller on-chain footprint. Still practically stateless. It would be interesting to see what’s the current maximum count of a single key re-use across popular blockchains.
1 Like
Your script that verifies the signature is fairly compact. The signature itself is huge. It’s just a bitcoin weirdness that the “witness” data of the transaction is also in limited script form. Still the whole thing should fit into 10KB comfortably.
I can’t help to think that it’s a mistake for blockchains to just adopt standards made for web certificates and ssl handshakes. We have very different statistical usage patterns, costs and constraints. It’s at least worth to investigate what the best tradeoffs could be between size and reuseability.
2 Likes
I think we’re talking about different things. I’m talking about implementing SPHINCS+ in Script vs implementing some OTS/FTS in Script. I don’t know how big of a bytecode SPHINCS+ would be but I doubt it can fit into VM limits, whereas some OTS/FTS can already fit.
Maybe in the future SPHINCS+ will be able to fit, maybe in the future we will have read-only inputs or global function tables so we can avoid a consensus change and someone would just vet a Script which anyone could call with <32-byte identifier> OP_INVOKE.
It’s not either / or, though. We can have some vetted schemes under the OP_CHECKSIG umbrella, and have a powerful VM that exposes some primitives and allows people to implement others. If they get used enough, later bring them under OP_CHECKSIG umbrella, too. But we have to think about timelines. Using off-the-shelf vetted schemes has less room for errors and allows us to have something reliable next year as backup / shelter.
What was ECDSA made for? Bitcoin got lucky that it adopted ECDSA just at the right time: early to be among the first to reap the size benefits over RSA, and late enough to not be broken later. Would Bitcoin have worked with RSA? I think it would have, and maybe first blocksize limit would’ve been set to 10 MB. Then our today’s discussion would be comparing 8kB with 768B, “only” a 10x, and would seem less drastic than 80x. We just got spoiled by elliptic curve crypto, and it will be missed, especially due to other cool stuff it enables, like confidential transactions. I wish it never gets broken and we never have to evacuate to our hash-based bunker.
Yes, but it all relies on assumption that you can safely reuse keys and signatures. Why break that promise when we don’t really need to? Q-day hasn’t come yet, even if we enable SPHINCS+ most people won’t use it. Maybe only institutions will adopt it, so it won’t be a large blocksize footprint. By the time Q-day comes maybe a nice and small drop-in will become available (e.g. SQIsign, the isogeny-based candidate with ~200-byte signatures, if it survives cryptanalysis). Then, we can add it to OP_CHECKSIG registry and keep all our current usage patterns.
You seem to be imagining a future where we’re stuck with SPHINCS+ just because we added it first. I’m imagining it just helps us get through the transition, and later we move on to use something better. We don’t have Bitcoin’s 2009 luck of having a small (on-chain bytes) AND convenient (wallet UX, no state management, airgapped signers work) AND secure (still secure vs classical) scheme available. We don’t have that option, so we pick two (secure + convenient) and pay the size cost temporarily. OTS/FTS would be another two-pick (secure + small).
1 Like
Ahh, so I was talking about implementing stateless signatures in script not exactly SPHINCS+ just something comparable. Something where you can sign like a million times without much statistical chance of reusing an OTS pub.
You can also decrease the signature sizes not just by decreasing the reusability, but also by using smaller hashes. While this may not be the endgame, for specifically the migration period (where we have like a reasonable suspicion that a CRQC is out there) they would suffice with hybrid schemes.
Finally, small amounts don’t require the same security guarantees as treasury amounts, but would be more sensitive to on-chain fees by a huge degree.
Fair point. I don’t have a lot of confidence in the other schemes at this point in time. I also don’t have a lot of confidence in “we can do it better later”.
1 Like
Trauma from BTC carried over
Here we CAN do better later, as we did when we added Schnorr. It was actually our first OP_CHECKSIG overload. It dispatches based on size of pushed signature and uses it to pick between ECDSA and Schnorr verification.
OP_CHECKMULTISIG Schnorr overload is nice, too, because it reused the infamous “dummy” element as pubkey bitfield and switches on it instead of signature size(s), so it’s actually nicer to use than the legacy ECDSA version.
This proposal would continue in that manner, and formalize a framework for dispatching based on first byte of the pushed pubkey.
1 Like
That’s good, but I think we can agree that if the application developers can work around the holes left by the protocol developers, that’s a form of future-proofing. Which is probably not a bad thing either way.
1 Like