Nostr Web Client

Turns out Taproot is great for post-Quantum in Bitcoin. https://groups.google.com/g/bitcoindev/c/8O857bRSVV8

Hey nostr:npub185h9z5yxn8uc7retm0n6gkm88358lejzparxms5kmy9epr236k2qcswrdp, I can't reply on google groups but you should check out my article on hash-based signatures and my DASK proposal, it's very similar to your idea, in the way clients can opt into future quantum resistance without any consensus changes.

https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin

I chose a different mechanism for my approach. Instead of an opcode in a tapscript leaf, DASK uses a PQ signature scheme pubkey as an secp256k1 secret key, and assumes future PQ bitcoin clients will validate against that PQ pubkey.

I think your proposal has a major benefit over mine in that it makes soft-fork compliance way easier. My DASK idea seems like it would need a hard fork on Q-Day, but yours would seem to be fully compatible with old clients. Big props 🎉

One idea from my post which I think you might want to consider copying is: Instead of committing to a SPHINCS key on-chain, commit to a hash-based certification key with shorter signatures, like WOTS.

Yes, it's a one-time signature scheme so we can't reuse the key, but we can be pretty sure than post-quantum cryptography will progress a long way in the coming decades, and we can use that one-time signature (which we are highly confident is secure today) to endorse a post-quantum key for a signature algorithm that might not exist yet, or that might exist today but that we don't know is secure, like Kyber.

Your opcode soft-fork would have to specify the exact validation semantics later, but the WOTS authentication key has already been committed to, so the coins are safe.

Reply to this note

Please Login to reply.

Discussion

Matt Corallo 1y ago 💬 1

Yes, I saw your post, I thought it was quite clever! That said, I think the Taproot approach is slightly cleaner - it allows wallets more flexibility (eg they could use a static PQ key for all their addresses, and no one would ever know unless they were used).

In terms of one-time vs larger-signatures, my mental model here is basically this stuff will only be used on the margin. Wallets that upgrade today and that people don’t touch for two decades will be safe, but wallets people sure actively using in five or seven years might use other, newer options for PQC. Thus, a bit worse design is fine, if it makes the solution more bulletproof. Now, that said, maybe that’s indeed an argument for a single-use scheme, just because it’s simpler to implement.

conduition 1y ago

I definitely agree, taproot approach is much better. I updated my post to point to yours. DASK is neat but I don't think we need to be that fancy, and your Taproot approach is more soft-fork friendly.

I do still think using a lighter-weight signature scheme like WOTS for certification would be better and more future proof than committing directly to SPHINCS right now.

If we do end up wanting to use SPHINCS in 20-30 years, it'd still be an option: Just enforce that the WOTS key must sign a SPHINCS pubkey, and verify everything else against the certified SPHINCS key. That would only add a kilobyte to the already-huge SPHINCS signature data.

Think of it this way: if you're correct and this is just an edgecase fallback opcode that only a few people ever end up using, then do we really want the huge kitchen-sink of bringing SPHINCS into the bitcoin consensus layer, just for it to be barely ever used?

On the other hand, if this PQ fallback opcode is used a LOT, then we stand to save a LOT of witness space by biding our time and seeing where the cards fall on the landscape of many-time post-quantum signatures, rather than committing to huge SPHINCS signatures today.