Delivery-date: Sun, 15 Dec 2024 17:53:20 -0800
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) client-ip=69.59.18.99;
Message-ID: <2272e122-c252-48a4-989f-dcedfaadf9cd@mattcorallo.com>
Date: Sun, 15 Dec 2024 20:40:51 -0500
MIME-Version: 1.0
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
To: Weikeng Chen <weikeng.chen@l2iterative.com>,
 Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <52f3bfc0-9446-4400-bf7a-7e38e5777c56@dashjr.org>
 <3b50081e-1a00-4d18-aee3-1cefde230a78n@googlegroups.com>
Content-Language: en-US
From: Matt Corallo <lf-lists@mattcorallo.com>
In-Reply-To: <3b50081e-1a00-4d18-aee3-1cefde230a78n@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"; format=flowed
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

Please see the assumptions list in the OP:

 > (e) its not worth waiting on OP_CAT and the other more general script op=
code additions for this,=20
as those seem stuck in bikeshed hell, not to mention questions around MEVil=
 and Bitcoin's future=20
abound. Further, doing this via dedicated opcode simplifies wallet adoption=
, which is likely to=20
struggle already given the additional workload for wallet developers for no=
 immediate user-facing=20
features.

As Luke notes, wallets should probably just start implementing this today a=
gainst a standard=20
SPHINCS+ implementation. By the time they're ready to ship someone can pick=
 a few constants for the=20
"standard" and we won't have to discuss it further until/unless we get a QC=
.

On 12/15/24 8:30 PM, Weikeng Chen wrote:
> I actually think this is a good reason to open OP_CAT because its ability=
 to do general-purpose=20
> covenants allow different parties to experiment their own PQ signature al=
gorithms before the Bitcoin=20
> core settles on one of them (which I believe would take longer).
> OP_CTV does not enable it. It just needs to be a full transaction hash an=
d the ability to=20
> reconstruct it.
>=20
> If we think we will be able to add QC signatures in 3 years, then we don'=
t need to do that.
> But if we don't think it is easy to settle down on one QC signature, then=
 it is better to let=20
> everyone make their own decisions on PQ solutions.
>=20
> It is okay to start with some less efficient but provably post-quantum al=
gorithm, for example,=20
> Winternitz signatures in BitVM.
> With OP_CAT, the public key can be reduced into a single hash, 32 bytes. =
The signature would still=20
> be 1KB. This is not too different from other PQ proposals.
> Verifying a Winternitz signature costs about 4KB in Bitcoin script. A maj=
or limitation of Winternitz=20
> signatures is that it is one-time, and therefore the keys need to be prot=
ected in a very careful way.
>=20
> Although this is still expensive and would better be handled by a native =
opcode, at least=20
> MicroStrategy and institutions as well as many individuals can move their=
 "long-term" wallet for=20
> Bitcoin into PQ ones and provide enough time for Bitcoin core to decide o=
n a post-quantum algorithm,=20
> ideally when one of them get mainstream adoption (e.g., replaced ECDSA an=
d RSA in web browsers).
>=20
> Nevertheless, the major issue right now with PQ is only P2WSH can be "pos=
t-quantum" while P2TR is=20
> not post-quantum. It may be necessary to have a P2TR new version where th=
e key route is removed=20
> (script-only) or replaced with a PQ signature.
>=20
> On Monday, December 16, 2024 at 8:01:55=E2=80=AFAM UTC+8 Luke Dashjr wrot=
e:
>=20
>     One thing to add: the post-QC script path does not require a softfork=
 to
>     commit to, as long as it is well-defined. So wallets could begin
>     implementing this fallback immediately, without waiting for _any_
>     softfork activation, as soon as the spec is final. They _would_ need =
to
>     guard the post-QC script as if it were itself a private key, which co=
uld
>     be an issue for hardware wallets - but I suspect there's probably a w=
ay
>     around that too...
>=20
>     On 12/15/24 4:42 PM, Matt Corallo wrote:
>      > There's been a few rough ideas for QC robustness in the signature
>      > scheme over Bitcoin transactions over the past many years, but man=
y 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 ha=
ving
>      > an option today for wallets to get QC security later.
>      > (b) Its entirely possible that fundamental scaling constraints wil=
l
>      > emerge and QCs that break EC simply won't ever be reality. We migh=
t
>      > 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 continu=
e 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 c=
oins
>      > today, and are bad candidates for inclusion in Bitcoin's consensus=
 due
>      > to the likelihood of future cryptography research. This implies th=
e
>      > only candidates for post-QC signature security in Bitcoin's consen=
sus
>      > today are hash-based signatures (basically SPHINCS/SPHINCS+).
>      > (e) its not worth waiting on OP_CAT and the other more general scr=
ipt
>      > opcode additions for this, as those seem stuck in bikeshed hell, n=
ot
>      > to mention questions around MEVil and Bitcoin's future abound.
>      > Further, doing this via dedicated opcode simplifies wallet adoptio=
n,
>      > 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-chai=
n
>      > footprint cost to get post-QC security for their transactions *tod=
ay*,
>      > but given upgrade cycles in Bitcoin it also seems ill-advised to n=
ot
>      > have some option for wallets to have "emergency" paths.
>      >
>      > Luckily, taproot provides a great way to build such a scheme! Beca=
use
>      > 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 si=
mple
>      > 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 chang=
es
>      > today). Of course if we do, substantial quantities of Bitcoin whic=
h
>      > 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 whic=
h
>      > 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 existi=
ng
>      > wallets, but it would allow for an opt-out scheme.
>      >
>      > This scheme has the incredibly nice property of not bloating exist=
ing
>      > 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 wheth=
er
>      > to also fail any script-paths that hit an ECDSA signature validati=
on
>      > (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 her=
e
>      > 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 late=
ncy
>      > 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
>      >
>=20
> --=20
> You received this message because you are subscribed to the Google Groups=
 "Bitcoin Development=20
> Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an=
 email to=20
> bitcoindev+unsubscribe@googlegroups.com <mailto:bitcoindev+unsubscribe@go=
oglegroups.com>.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoinde=
v/3b50081e-1a00-4d18-=20
> aee3-1cefde230a78n%40googlegroups.com <https://groups.google.com/d/msgid/=
=20
> bitcoindev/3b50081e-1a00-4d18-aee3-1cefde230a78n%40googlegroups.com?utm_m=
edium=3Demail&utm_source=3Dfooter>.

--=20
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 e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
2272e122-c252-48a4-989f-dcedfaadf9cd%40mattcorallo.com.