Delivery-date: Sun, 15 Dec 2024 13:57:10 -0800
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 2620:6e:a000:1::99 as permitted sender) client-ip=2620:6e:a000:1::99;
Message-ID: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
Date: Sun, 15 Dec 2024 16:42:59 -0500
MIME-Version: 1.0
Content-Language: en-US
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
From: Matt Corallo <lf-lists@mattcorallo.com>
Subject: [bitcoindev] Trivial QC signatures with clean upgrade path
Content-Type: text/plain; charset="UTF-8"; format=flowed
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

There's been a few rough ideas for QC robustness in the signature scheme over Bitcoin transactions 
over the past many years, but many of them have a number of fairly major drawbacks.

First, some base assumptions:

(a) QCs that can break EC will take a while (probably closer to a decade or two than a few years). 
This lines up with NSA and other recommendations. We have time to upgrade, but we might consider 
having an option today for wallets to get QC security later.
(b) Its entirely possible that fundamental scaling constraints will emerge and QCs that break EC 
simply won't ever be reality. We might not want to bet on this, but its possible.
(c) We'll get some reasonable warning before QCs are there - QC development requires immense 
resources, so much so that only a few organizations in the world can afford to hire the talent 
required and fund the lab. This type of development has and will likely continue to lead to 
announcements as progress continues, and we'll have a few years warning as QCs get closer and closer.
(d) post-QC security assumptions (like Lattices and obviously Supersingular Elliptic Curve Isogeny) 
are insufficient to secure coins today, and are bad candidates for inclusion in Bitcoin's consensus 
due to the likelihood of future cryptography research. This implies the only candidates for post-QC 
signature security in Bitcoin's consensus today are hash-based signatures (basically SPHINCS/SPHINCS+).
(e) its not worth waiting on OP_CAT and the other more general script opcode additions for this, as 
those seem stuck in bikeshed hell, not to mention questions around MEVil and Bitcoin's future 
abound. Further, doing this via dedicated opcode simplifies wallet adoption, which is likely to 
struggle already given the additional workload for wallet developers for no immediate user-facing 
features.


Given these assumptions, it seems ill-advised for wallets today to start locking funds up in a way 
where they need to pay the on-chain footprint cost to get post-QC security for their transactions 
*today*, but given upgrade cycles in Bitcoin it also seems ill-advised to not have some option for 
wallets to have "emergency" paths.

Luckily, taproot provides a great way to build such a scheme! Because taproot script-path spends are 
strongly-bound (the taproot script-path hash t includes the internal key in its hash), a future QC 
could determine the associated private key and script-path merkle root, but it cannot forge an 
alternative script-path merkle-root.

This provides a compelling hook for post-QC security - with the simple addition of an OP_SPHINCS (or 
equivalent post-QC non-one-time-use (i.e. not Lamport/Winternitz) signature verification opcode, 
functioning in much the same was OP_CHECKSIG works today), wallets simply need to construct their 
taproot outputs to always contain a script-path alternative spending condition. When QCs are 
becoming a reality, key-path taproot spends could be disabled via soft-fork, forcing spends to be 
done using the QC-secure path.

This scheme obviously has the major drawback of non-upgraded funds confiscation at the time of QC 
existence, but:

(a) we could instead require explicit opt-in for this scheme. This has the drawback of yet another 
on-chain fingerprint and would require a new scriptPubKey format (but keeping the existing bech32m 
address format, hopefully most wallets support that without any code changes today). Of course if we 
do, substantial quantities of Bitcoin which are unlikely to ever be spent could lead to supply 
shock, severely damaging Bitcoin's utility in other ways,
(b) alternatively, we could allow key-path spends for wallets which prove the script-path is a NUMS 
point (via some new keypath+proof spend variant). I doubt many wallets today bother committing to a 
NUMS point for their taproot output pubkeys, so this would break existing wallets, but it would 
allow for an opt-out scheme.

This scheme has the incredibly nice property of not bloating existing use-cases nearly at all (just 
one extra taproot script-path branch, but that's not a huge deal generally).

There's a few things to bike-shed on here, though - first of all whether to require opt-in or 
provide an opt-out and secondly whether to also fail any script-paths that hit an ECDSA signature 
validation (probably yes?).

I assume this has been written up elsewhere but I couldn't find it. Most of this is due to 
not_nothingmuch, I'm just writing it up here and taking credit for it.

This doesn't address the questions around PoW in a post-QC world, of course, but that likely isn't 
something that can be answered until we see more practical limitations of QCs (eg what is the 
minimal latency of a QC gate? If its particularly low, can we simply complexify Bitcoin's PoW hash 
function in order to delay QC results far past when traditional hardware is able to mine a block?)

Matt

-- 
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/c2684826-6c93-419b-9a96-c0f0a791c9ac%40mattcorallo.com.