Delivery-date: Sun, 15 Dec 2024 17:33:35 -0800
Sender: bitcoindev@googlegroups.com
Date: Sun, 15 Dec 2024 17:30:22 -0800 (PST)
From: Weikeng Chen <weikeng.chen@l2iterative.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <3b50081e-1a00-4d18-aee3-1cefde230a78n@googlegroups.com>
In-Reply-To: <52f3bfc0-9446-4400-bf7a-7e38e5777c56@dashjr.org>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <52f3bfc0-9446-4400-bf7a-7e38e5777c56@dashjr.org>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_128474_1989002088.1734312622325"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_128474_1989002088.1734312622325
Content-Type: multipart/alternative; 
	boundary="----=_Part_128475_506545668.1734312622325"

------=_Part_128475_506545668.1734312622325
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I actually think this is a good reason to open OP_CAT because its ability=
=20
to do general-purpose covenants allow different parties to experiment their=
=20
own PQ signature algorithms before the Bitcoin core settles on one of them=
=20
(which I believe would take longer).
OP_CTV does not enable it. It just needs to be a full transaction hash and=
=20
the ability to reconstruct it.

If we think we will be able to add QC signatures in 3 years, then we don't=
=20
need to do that.=20
But if we don't think it is easy to settle down on one QC signature, then=
=20
it is better to let everyone make their own decisions on PQ solutions.

It is okay to start with some less efficient but provably post-quantum=20
algorithm, for example, Winternitz signatures in BitVM.=20
With OP_CAT, the public key can be reduced into a single hash, 32 bytes.=20
The signature would still be 1KB. This is not too different from other PQ=
=20
proposals.=20
Verifying a Winternitz signature costs about 4KB in Bitcoin script. A major=
=20
limitation of Winternitz signatures is that it is one-time, and therefore=
=20
the keys need to be protected in a very careful way.

Although this is still expensive and would better be handled by a native=20
opcode, at least MicroStrategy and institutions as well as many individuals=
=20
can move their "long-term" wallet for Bitcoin into PQ ones and provide=20
enough time for Bitcoin core to decide on a post-quantum algorithm, ideally=
=20
when one of them get mainstream adoption (e.g., replaced ECDSA and RSA in=
=20
web browsers).

Nevertheless, the major issue right now with PQ is only P2WSH can be=20
"post-quantum" while P2TR is not post-quantum. It may be necessary to have=
=20
a P2TR new version where the key route is removed (script-only) or replaced=
=20
with a PQ signature.

On Monday, December 16, 2024 at 8:01:55=E2=80=AFAM UTC+8 Luke Dashjr wrote:

> One thing to add: the post-QC script path does not require a softfork to=
=20
> commit to, as long as it is well-defined. So wallets could begin=20
> implementing this fallback immediately, without waiting for _any_=20
> softfork activation, as soon as the spec is final. They _would_ need to=
=20
> guard the post-QC script as if it were itself a private key, which could=
=20
> be an issue for hardware wallets - but I suspect there's probably a way=
=20
> around that too...
>
> On 12/15/24 4:42 PM, Matt Corallo wrote:
> > There's been a few rough ideas for QC robustness in the signature=20
> > scheme over Bitcoin transactions over the past many years, but many of=
=20
> > 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=20
> > decade or two than a few years). This lines up with NSA and other=20
> > recommendations. We have time to upgrade, but we might consider having=
=20
> > an option today for wallets to get QC security later.
> > (b) Its entirely possible that fundamental scaling constraints will=20
> > emerge and QCs that break EC simply won't ever be reality. We might=20
> > not want to bet on this, but its possible.
> > (c) We'll get some reasonable warning before QCs are there - QC=20
> > development requires immense resources, so much so that only a few=20
> > organizations in the world can afford to hire the talent required and=
=20
> > fund the lab. This type of development has and will likely continue to=
=20
> > lead to announcements as progress continues, and we'll have a few=20
> > years warning as QCs get closer and closer.
> > (d) post-QC security assumptions (like Lattices and obviously=20
> > Supersingular Elliptic Curve Isogeny) are insufficient to secure coins=
=20
> > today, and are bad candidates for inclusion in Bitcoin's consensus due=
=20
> > to the likelihood of future cryptography research. This implies the=20
> > only candidates for post-QC signature security in Bitcoin's consensus=
=20
> > today are hash-based signatures (basically SPHINCS/SPHINCS+).
> > (e) its not worth waiting on OP_CAT and the other more general script=
=20
> > opcode additions for this, as those seem stuck in bikeshed hell, not=20
> > to mention questions around MEVil and Bitcoin's future abound.=20
> > Further, doing this via dedicated opcode simplifies wallet adoption,=20
> > which is likely to struggle already given the additional workload for=
=20
> > wallet developers for no immediate user-facing features.
> >
> >
> > Given these assumptions, it seems ill-advised for wallets today to=20
> > start locking funds up in a way where they need to pay the on-chain=20
> > footprint cost to get post-QC security for their transactions *today*,=
=20
> > but given upgrade cycles in Bitcoin it also seems ill-advised to not=20
> > have some option for wallets to have "emergency" paths.
> >
> > Luckily, taproot provides a great way to build such a scheme! Because=
=20
> > taproot script-path spends are strongly-bound (the taproot script-path=
=20
> > hash t includes the internal key in its hash), a future QC could=20
> > determine the associated private key and script-path merkle root, but=
=20
> > it cannot forge an alternative script-path merkle-root.
> >
> > This provides a compelling hook for post-QC security - with the simple=
=20
> > addition of an OP_SPHINCS (or equivalent post-QC non-one-time-use=20
> > (i.e. not Lamport/Winternitz) signature verification opcode,=20
> > functioning in much the same was OP_CHECKSIG works today), wallets=20
> > simply need to construct their taproot outputs to always contain a=20
> > script-path alternative spending condition. When QCs are becoming a=20
> > reality, key-path taproot spends could be disabled via soft-fork,=20
> > forcing spends to be done using the QC-secure path.
> >
> > This scheme obviously has the major drawback of non-upgraded funds=20
> > confiscation at the time of QC existence, but:
> >
> > (a) we could instead require explicit opt-in for this scheme. This has=
=20
> > the drawback of yet another on-chain fingerprint and would require a=20
> > new scriptPubKey format (but keeping the existing bech32m address=20
> > format, hopefully most wallets support that without any code changes=20
> > today). Of course if we do, substantial quantities of Bitcoin which=20
> > are unlikely to ever be spent could lead to supply shock, severely=20
> > damaging Bitcoin's utility in other ways,
> > (b) alternatively, we could allow key-path spends for wallets which=20
> > prove the script-path is a NUMS point (via some new keypath+proof=20
> > spend variant). I doubt many wallets today bother committing to a NUMS=
=20
> > point for their taproot output pubkeys, so this would break existing=20
> > wallets, but it would allow for an opt-out scheme.
> >
> > This scheme has the incredibly nice property of not bloating existing=
=20
> > use-cases nearly at all (just one extra taproot script-path branch,=20
> > but that's not a huge deal generally).
> >
> > There's a few things to bike-shed on here, though - first of all=20
> > whether to require opt-in or provide an opt-out and secondly whether=20
> > to also fail any script-paths that hit an ECDSA signature validation=20
> > (probably yes?).
> >
> > I assume this has been written up elsewhere but I couldn't find it.=20
> > Most of this is due to not_nothingmuch, I'm just writing it up here=20
> > and taking credit for it.
> >
> > This doesn't address the questions around PoW in a post-QC world, of=20
> > course, but that likely isn't something that can be answered until we=
=20
> > see more practical limitations of QCs (eg what is the minimal latency=
=20
> > of a QC gate? If its particularly low, can we simply complexify=20
> > Bitcoin's PoW hash function in order to delay QC results far past when=
=20
> > traditional hardware is able to mine a block?)
> >
> > Matt
> >
>

--=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/=
3b50081e-1a00-4d18-aee3-1cefde230a78n%40googlegroups.com.

------=_Part_128475_506545668.1734312622325
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I actually think this is a good reason to open OP_CAT because its ability t=
o do general-purpose covenants allow different parties to experiment their =
own PQ signature algorithms before the Bitcoin core settles on one of them =
(which I believe would take longer).<div>OP_CTV does not enable it. It just=
 needs to be a full transaction hash and the ability to reconstruct it.</di=
v><div><br /></div><div>If we think we will be able to add QC signatures in=
 3 years, then we don't need to do that.=C2=A0</div><div>But if we don't th=
ink it is easy to settle down on one QC signature, then it is better to let=
 everyone make their own decisions on PQ solutions.<br /><div><br /></div><=
div>It is okay to start with some less efficient but provably post-quantum =
algorithm, for example, Winternitz signatures in BitVM.=C2=A0</div><div>Wit=
h OP_CAT, the public key can be reduced into a single hash, 32 bytes. The s=
ignature would still be 1KB. This is not too different from other PQ propos=
als.=C2=A0</div><div>Verifying a Winternitz signature costs about 4KB in Bi=
tcoin script. A major limitation of Winternitz signatures is that it is one=
-time, and therefore the keys need to be protected in a very careful way.</=
div><div><br /></div><div>Although this is still expensive and would better=
 be handled by a native opcode, at least MicroStrategy and institutions as =
well as many individuals can move their "long-term" wallet for Bitcoin into=
 PQ ones and provide enough time for Bitcoin core to decide on a post-quant=
um algorithm, ideally when one of them get mainstream adoption (e.g., repla=
ced ECDSA and RSA in web browsers).</div></div><div><br /></div><div>Nevert=
heless, the major issue right now with PQ is only P2WSH can be "post-quantu=
m" while P2TR is not post-quantum. It may be necessary to have a P2TR new v=
ersion where the key route is removed (script-only) or replaced with a PQ s=
ignature.</div><div><br /></div><div class=3D"gmail_quote"><div dir=3D"auto=
" class=3D"gmail_attr">On Monday, December 16, 2024 at 8:01:55=E2=80=AFAM U=
TC+8 Luke Dashjr wrote:<br/></div><blockquote class=3D"gmail_quote" style=
=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding=
-left: 1ex;">One thing to add: the post-QC script path does not require a s=
oftfork to=20
<br>commit to, as long as it is well-defined. So wallets could begin=20
<br>implementing this fallback immediately, without waiting for _any_=20
<br>softfork activation, as soon as the spec is final. They _would_ need to=
=20
<br>guard the post-QC script as if it were itself a private key, which coul=
d=20
<br>be an issue for hardware wallets - but I suspect there&#39;s probably a=
 way=20
<br>around that too...
<br>
<br>On 12/15/24 4:42 PM, Matt Corallo wrote:
<br>&gt; There&#39;s been a few rough ideas for QC robustness in the signat=
ure=20
<br>&gt; scheme over Bitcoin transactions over the past many years, but man=
y of=20
<br>&gt; them have a number of fairly major drawbacks.
<br>&gt;
<br>&gt; First, some base assumptions:
<br>&gt;
<br>&gt; (a) QCs that can break EC will take a while (probably closer to a=
=20
<br>&gt; decade or two than a few years). This lines up with NSA and other=
=20
<br>&gt; recommendations. We have time to upgrade, but we might consider ha=
ving=20
<br>&gt; an option today for wallets to get QC security later.
<br>&gt; (b) Its entirely possible that fundamental scaling constraints wil=
l=20
<br>&gt; emerge and QCs that break EC simply won&#39;t ever be reality. We =
might=20
<br>&gt; not want to bet on this, but its possible.
<br>&gt; (c) We&#39;ll get some reasonable warning before QCs are there - Q=
C=20
<br>&gt; development requires immense resources, so much so that only a few=
=20
<br>&gt; organizations in the world can afford to hire the talent required =
and=20
<br>&gt; fund the lab. This type of development has and will likely continu=
e to=20
<br>&gt; lead to announcements as progress continues, and we&#39;ll have a =
few=20
<br>&gt; years warning as QCs get closer and closer.
<br>&gt; (d) post-QC security assumptions (like Lattices and obviously=20
<br>&gt; Supersingular Elliptic Curve Isogeny) are insufficient to secure c=
oins=20
<br>&gt; today, and are bad candidates for inclusion in Bitcoin&#39;s conse=
nsus due=20
<br>&gt; to the likelihood of future cryptography research. This implies th=
e=20
<br>&gt; only candidates for post-QC signature security in Bitcoin&#39;s co=
nsensus=20
<br>&gt; today are hash-based signatures (basically SPHINCS/SPHINCS+).
<br>&gt; (e) its not worth waiting on OP_CAT and the other more general scr=
ipt=20
<br>&gt; opcode additions for this, as those seem stuck in bikeshed hell, n=
ot=20
<br>&gt; to mention questions around MEVil and Bitcoin&#39;s future abound.=
=20
<br>&gt; Further, doing this via dedicated opcode simplifies wallet adoptio=
n,=20
<br>&gt; which is likely to struggle already given the additional workload =
for=20
<br>&gt; wallet developers for no immediate user-facing features.
<br>&gt;
<br>&gt;
<br>&gt; Given these assumptions, it seems ill-advised for wallets today to=
=20
<br>&gt; start locking funds up in a way where they need to pay the on-chai=
n=20
<br>&gt; footprint cost to get post-QC security for their transactions *tod=
ay*,=20
<br>&gt; but given upgrade cycles in Bitcoin it also seems ill-advised to n=
ot=20
<br>&gt; have some option for wallets to have &quot;emergency&quot; paths.
<br>&gt;
<br>&gt; Luckily, taproot provides a great way to build such a scheme! Beca=
use=20
<br>&gt; taproot script-path spends are strongly-bound (the taproot script-=
path=20
<br>&gt; hash t includes the internal key in its hash), a future QC could=
=20
<br>&gt; determine the associated private key and script-path merkle root, =
but=20
<br>&gt; it cannot forge an alternative script-path merkle-root.
<br>&gt;
<br>&gt; This provides a compelling hook for post-QC security - with the si=
mple=20
<br>&gt; addition of an OP_SPHINCS (or equivalent post-QC non-one-time-use=
=20
<br>&gt; (i.e. not Lamport/Winternitz) signature verification opcode,=20
<br>&gt; functioning in much the same was OP_CHECKSIG works today), wallets=
=20
<br>&gt; simply need to construct their taproot outputs to always contain a=
=20
<br>&gt; script-path alternative spending condition. When QCs are becoming =
a=20
<br>&gt; reality, key-path taproot spends could be disabled via soft-fork,=
=20
<br>&gt; forcing spends to be done using the QC-secure path.
<br>&gt;
<br>&gt; This scheme obviously has the major drawback of non-upgraded funds=
=20
<br>&gt; confiscation at the time of QC existence, but:
<br>&gt;
<br>&gt; (a) we could instead require explicit opt-in for this scheme. This=
 has=20
<br>&gt; the drawback of yet another on-chain fingerprint and would require=
 a=20
<br>&gt; new scriptPubKey format (but keeping the existing bech32m address=
=20
<br>&gt; format, hopefully most wallets support that without any code chang=
es=20
<br>&gt; today). Of course if we do, substantial quantities of Bitcoin whic=
h=20
<br>&gt; are unlikely to ever be spent could lead to supply shock, severely=
=20
<br>&gt; damaging Bitcoin&#39;s utility in other ways,
<br>&gt; (b) alternatively, we could allow key-path spends for wallets whic=
h=20
<br>&gt; prove the script-path is a NUMS point (via some new keypath+proof=
=20
<br>&gt; spend variant). I doubt many wallets today bother committing to a =
NUMS=20
<br>&gt; point for their taproot output pubkeys, so this would break existi=
ng=20
<br>&gt; wallets, but it would allow for an opt-out scheme.
<br>&gt;
<br>&gt; This scheme has the incredibly nice property of not bloating exist=
ing=20
<br>&gt; use-cases nearly at all (just one extra taproot script-path branch=
,=20
<br>&gt; but that&#39;s not a huge deal generally).
<br>&gt;
<br>&gt; There&#39;s a few things to bike-shed on here, though - first of a=
ll=20
<br>&gt; whether to require opt-in or provide an opt-out and secondly wheth=
er=20
<br>&gt; to also fail any script-paths that hit an ECDSA signature validati=
on=20
<br>&gt; (probably yes?).
<br>&gt;
<br>&gt; I assume this has been written up elsewhere but I couldn&#39;t fin=
d it.=20
<br>&gt; Most of this is due to not_nothingmuch, I&#39;m just writing it up=
 here=20
<br>&gt; and taking credit for it.
<br>&gt;
<br>&gt; This doesn&#39;t address the questions around PoW in a post-QC wor=
ld, of=20
<br>&gt; course, but that likely isn&#39;t something that can be answered u=
ntil we=20
<br>&gt; see more practical limitations of QCs (eg what is the minimal late=
ncy=20
<br>&gt; of a QC gate? If its particularly low, can we simply complexify=20
<br>&gt; Bitcoin&#39;s PoW hash function in order to delay QC results far p=
ast when=20
<br>&gt; traditional hardware is able to mine a block?)
<br>&gt;
<br>&gt; Matt
<br>&gt;
<br></blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/3b50081e-1a00-4d18-aee3-1cefde230a78n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/3b50081e-1a00-4d18-aee3-1cefde230a78n%40googlegroups.com</a>.<br />

------=_Part_128475_506545668.1734312622325--

------=_Part_128474_1989002088.1734312622325--