path: root/73/827bcbcd1619b8f1d4211c06af14501510be7b

Delivery-date: Tue, 17 Dec 2024 20:19:29 -0800
Received: from mail-yb1-f183.google.com ([209.85.219.183])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBC3PT7FYWAMRBRU2RG5QMGQEW666TLQ@googlegroups.com>)
	id 1tNlWx-0006xe-Sx
	for bitcoindev@gnusha.org; Tue, 17 Dec 2024 20:19:29 -0800
Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e35e9d36da3sf7889642276.1
        for <bitcoindev@gnusha.org>; Tue, 17 Dec 2024 20:19:27 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1734495562; x=1735100362; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:sender:from
         :to:cc:subject:date:message-id:reply-to;
        bh=klU2emGFiRujazO8GnRw1LhLZXmwMQYxUN9J7AmKp/A=;
        b=VL5xxBwQpPX7wMqA65iHYiC3FlzaSm+IGycqCvENMNmHYhbkjVfxAjQM5DYUwfkyYn
         IUAylcid24trKnfYgBEPcDcUhSp8DTZSoIUBEQKHnTDFDXwemIECEuZVvfvXVOPjXacZ
         ExTRrAkB6MNKcMOC7Ypa51LdWDA6yLN34neqG8Uv3FDE5BKeBQKD41mTeBsFXrix8RgA
         GXl542PDp101MKvDWmt5bFfeReIq2J5Ui7bZZCip/lr8oG1GiR8wGdfHVMmxSr/2B01X
         F36KkcimVm+5R6BVT3S1eABkUFvZwpBQUT/Ptw4RR4g9Li2t7PGZieLJnBG1oIBLtYdI
         tddg==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1734495562; x=1735100362; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:from:to:cc
         :subject:date:message-id:reply-to;
        bh=klU2emGFiRujazO8GnRw1LhLZXmwMQYxUN9J7AmKp/A=;
        b=GMREl5pUYEI/uap7WhnjsTbkPq3EP6O21Tw8YWd4Xjh7pX0XZynQg70CdOAxzRwiuO
         Zk5l222PZNlbn1gNnaQwsQ5mZEKjXzVguUPxUL0ebgk1rROHgUBegvKbu6yJPYPM2SP4
         7cIFJOJgMf3KqBRStrQi+cBA+EMEVybpQlozICa+HFH3kYMl9bGfexDiRphCkun7vwaf
         4YZzuWDUREOuyL8Cy+E8qI9JAPenjug1bRNQryZXHn5ghNoNMg7f1rnkPhBdq4UV/Obg
         kaXNwc2jvJVgwzZtOCvNpTavKbld8/hIS382Mso7mt1mY32CVypS0A1SyhBx9FPPtSN1
         +Fkw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1734495562; x=1735100362;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-sender:mime-version
         :subject:references:in-reply-to:message-id:to:from:date:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=klU2emGFiRujazO8GnRw1LhLZXmwMQYxUN9J7AmKp/A=;
        b=H7Ot0muHA3nwqfoqh7Ko3ffLZ8/YGQddeKLz2+kalBEOx9gpWlWszM0kV/BXHXIzjk
         HF6rGN+uzUyNkwlTuVhy+YaX/wr1nxcfkpN4S3Mfa9RqEghH0TN4ie761Tw+4raCgctA
         fn3dmU1LNH+GORKjX6t99EJzeiBoHiF2SJMfZ4jV9iRH3Nu0rdvvS6EaHvKJqYxczH3V
         uN2a41pWYv+8aW1yVf+CNj4nUoF8gYzJowaIyMRoxl7GO0lVGxhQHOIr9JIgPBsKyyBL
         w3hZEapmaf/a/XOegwZlhnTlQBBWyJBiTLMNOIgpHQIbokX1s0QTYkUXo5uW7oF56LV7
         xiYA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVjzuORADnKjeZeRutx+t7flh4azTdDf1Mu7xITmADQVB31bPQMRsYIuyXiZb/yWLl1/o6cgu/p02XC@gnusha.org
X-Gm-Message-State: AOJu0YzJCFjoz/i7wQD0dncepRvWoErDrwj05sNmuvk0LmMSajTG4EhK
	s6Zoxf1zbzvxyW4M1Al8gDRWy+e9tSQuGKVjxWcz/944IX9FsxRW
X-Google-Smtp-Source: AGHT+IGPgwq2O8QDYYRvUNnJJujGibnqNBVd69DSNt8b0u3u/ha8gR3qwey+UN8ev6PZhW195ekpsA==
X-Received: by 2002:a05:6902:2293:b0:e4b:3d71:346a with SMTP id 3f1490d57ef6-e536218d6b1mr1063305276.11.1734495561458;
        Tue, 17 Dec 2024 20:19:21 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:aace:0:b0:e38:7d9d:de43 with SMTP id 3f1490d57ef6-e43b1e7c95fls2058539276.2.-pod-prod-02-us;
 Tue, 17 Dec 2024 20:19:18 -0800 (PST)
X-Received: by 2002:a05:690c:46c3:b0:6ef:9dbe:9f82 with SMTP id 00721157ae682-6f3d2696cc4mr11066497b3.29.1734495558574;
        Tue, 17 Dec 2024 20:19:18 -0800 (PST)
Received: by 2002:a81:a9ca:0:b0:6ef:9b37:85ef with SMTP id 00721157ae682-6f3113d2d5ams7b3;
        Tue, 17 Dec 2024 19:29:18 -0800 (PST)
X-Received: by 2002:a05:690c:6210:b0:6ef:4a57:fc7c with SMTP id 00721157ae682-6f3d0f2bbbfmr10119937b3.16.1734492557547;
        Tue, 17 Dec 2024 19:29:17 -0800 (PST)
Date: Tue, 17 Dec 2024 19:29:17 -0800 (PST)
From: Antoine Riard <antoine.riard@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <2c9a1ffa-8e7b-4de3-b176-e5b24f3bac9fn@googlegroups.com>
In-Reply-To: <0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n@googlegroups.com>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <Z2ALlBGIyZLVbfVG@erisian.com.au>
 <374d6201-fb43-48df-abbc-f01ef1944a7dn@googlegroups.com>
 <0f6e4dd0-30c2-489a-8f90-a9507dbeb5a7n@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_30744_2094829782.1734492557115"
X-Original-Sender: antoine.riard@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)

------=_Part_30744_2094829782.1734492557115
Content-Type: multipart/alternative; 
	boundary="----=_Part_30745_56714383.1734492557115"

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

Hi all,

In my understanding, whatever the recent advances in error code
corrections to get universal quantum computer in the real-world,
there is still big unknowns if all the scalability challenges can
be solved as the number of physical qubits is going up, whatever
the underlying information support (e.g the spin of an electron).

All the efforts by many well-funded research team all over
the world at building QC might just end up on discovering new
law of physics rending intractable the realization of QC...

On the other hand, given the slowness of any consensus upgrade
in bitcoin this is definitely an area of concern to keep an
eye on it in the situation where QC would become practical
enough to break the DL problem.

I think Tadge's idea of introducing a PoQC, assuming it's
feasible, can be brilliant to enhance all the "pubkey"
exposed coins. For all the old coins (e.g P2PK more than
10 years ago), there could be a soft-fork introduces to
restrain the spend to some "seal" PoQC, of which the spend
would trigger the key-path spend knock-out of all "pubkey-exposed"
coins starting at the next block (or at spend height + N).

This soft-fork could require the unseal spend of a PoQC
to have an inflated weight of 4 MB to make the validity
transition easy. The new "seal" PoQC could be made consensus
mandatory for old pubkeys types and user opted-in for newer
ones like P2TR (i.e the PQ2TR). Spending a _single_ mandatory
or opted-in "sealed" pubkey would trigger the key-path spend
desactivation for all the affected UTXOs. While this would
be sacrifying one UTXO to save many of them, I think it would
minimizes expectations magical coordination of the community
when we see a real QC attacker in the wild to rollout a soft-fork.

I'm not sure if we can come up with a post-quantum scheme to
unlock pubkeys exposed through key-path, like any post-quantum
scheme would have to assume some secret proof of knowledge, though
once the DL is broken what information is remaining to the "legit"
coins owners to prove their know a speicifc scalar before the
PoQC "seal" has been reached ...? A Shor-efficient QC would break
the secrecy currently affordness by the hardness of factorization.

A client-side option could start to anchor the hash of EC secret
key as an ordering to solve the double-spend problem towards a
future QC attacker...even if we don't know yet how to make this
proof valid yet within future post-quantum secure scheme.

I don't think we should go for now on one post-quantum scheme like
Sphincs, while its cryptanalytic assumptions are easier to understand,
it's not like CRYSTALS or FALCON have also been successfully vetted
by the NIST. A user could script-path commit to a a number of "reserved"
OP_SUCCESS leafs, and then they can become valid either when the PoQC
is unsealed by a QC attacker or by a soft-fork ulterior to the PoQC
soft-fork. The on-chain fee cost of uncertainty on the most robust
post-quantum scheme is burden by the user, rather than picking up one
scheme as the only one (...there is little available litterature on the
post-quantum Grover's algorithm to break hash functions).

Additionally, I don't think pre-signed smarts contracts will be
condemned to close down, as long as a parallel post-quantum state
is counter-signed all along the classical state. There is no
guarantee ahead that the new signature scheme will have a consensus
validity (e.g SPHINCS or CRYSTALS signatures becoming valid), but
at least the parallel state, quantum or classic will be ordered by
on-chain spend of the UTXO.

While this is an open question in the QC field how much time it would
take to break a public key DL, and if it's going to be in average inferior
to 600 seconds, I think looking for any solution where the PoW is=20
accelerated
will condemn us to a never-ending race, as QC latency is improving. We=20
should
rather design consensus rules to yield a new block every 10 min,=20
indifferently
of access to a classic or quantum computer and with only the quantity of=20
energy
as a distinction factor.

So to make a digest, in my view I think the main problems are the following=
:
- (a) can we come up with a practical PoQC scheme that can be implemented=
=20
as full-node consensus rules ?
- (b) what is socially acceptable to do with the QC-exposed old "pubkeys"=
=20
coins that their users will never touch again ?
- (c) what are the client-side opted-in post-quantum hooks that could be=20
implemented _now_ ?

Ideally, we can solve (a) to make the (c) hooks automatically blessed with
consensus meaning, and that way minimizing community coordination when it's
time to upgrade to post-quantum cryptography. I don't think there is a good
answer for (b) assuming no future magic post-quantum scheme to prove a=20
knowledge
before a time T, other than anticipating the QC problem _now_ to minimize=
=20
the
numbers of potentially affected coins in the future.

Best,
Antoine
ots hash: 9238d0a7ce681f0dc944b28745d379b41cd2491d
Le mardi 17 d=C3=A9cembre 2024 =C3=A0 05:42:33 UTC, conduition a =C3=A9crit=
 :

> Hey all, and thank you for this great idea Matt. It rhymes a little with =
my=20
> DASK idea=20
> <https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin> but I=
=20
> actually like yours a lot better, as it provides a cleaner upgrade path f=
or=20
> soft-fork compatibility than DASK.
>
> However, I suggest we use one of the more succinct Winternitz one-time=20
> signature algorithms instead of committing to SPHINCS right away. This=20
> gives us the option of using the WOTS key as a certification layer for so=
me=20
> pubkey from a future signature algorithm, which may or may not even exist=
=20
> yet.
>
> Not only does this give researchers more time to find better algorithms,=
=20
> it also makes devs' lives easier, and makes the transition to a PQ world=
=20
> more incremental than a head-first dive committing to SPHINCS. WOTS is ve=
ry=20
> simple: it'd be easy to standardize and easy for wallets to implement and=
=20
> derive. Its signatures can be as small as 1 kilobyte. Even if we do end u=
p=20
> choosing SPHINCS as the 2nd-layer whose pubkey we certify, the time/space=
=20
> overhead added by one WOTS signature is negligible in comparison. Once th=
e=20
> WOTS pubkey is standardized, we can take our time choosing and=20
> standardizing the probably-much-more-complicated 2nd layer signing=20
> algorithm.
>
> This certification layer idea is straight from SPHINCS' own whitepaper.=
=20
> This is how SPHINCS authors created its many-time property without blowin=
g=20
> up the runtime.
>
> ----------
>
> Tadge, your PoQC idea is neat but it relies on at least one "good guy" QC=
=20
> willing to produce the proof. A self-interested QC would never willingly=
=20
> crack a pubkey which it knows would activate a soft-fork against its own=
=20
> interest. Any publicly-advertised PoQC honeypot addresses able to gather=
=20
> large donations would be obvious, and a rational QC would ignore them. I=
=20
> suppose users could sprinkle some hidden honeypot addresses around the=20
> network and hope the QC bites one of them, but I don't think that's=20
> practical - The QC would probably prioritize addresses with large balance=
s=20
> like Satoshi's wallets. I'm not sure if I have any better ideas though,=
=20
> besides the also-risky option of relying on the community to act in uniso=
n,=20
> triggering activation manually if/when a QC appears to be coming soon to =
a=20
> blockchain near us. So a PoQC might be a good additional trigger, but we=
=20
> also need to be able to manually activate the post-quantum upgrade in cas=
e=20
> the PoQC is unavailable.
>
> ----------
>
> Another fun aspect of QC's we haven't discussed yet is BIP32. Whatever=20
> pubkey we hide in the OP_SUCCESS tap leaf, it needs to be derived via=20
> quantum-secure means. So there can be no unhardened BIP32 anywhere in the=
=20
> derivation chain of the PQ-secret-key, or else xpubs can be sold to a QC=
=20
> for profit, even if the PQ soft fork upgrade is activated on time.
>
> It seems like whatever upgrade path we go with, it will mean the end of=
=20
> BIP32 xpubs as we know them. A 3rd party won't be able to derive my=20
> post-quantum P2TR address from a regular xpub alone without also knowing=
=20
> the OP_SUCCESS script's tap leaf hash, which by necessity must be=20
> completely independent of the xpub. Sounds like we may need a new standar=
d=20
> for that too. Perhaps some kind of 'wrapper' which embeds a regular BIP32=
=20
> xpub, plus the tap leaf hash of the OP_SUCCESS script? That'd be enough f=
or=20
> an untrusted 3rd party to derive a standard set of P2TR addresses with th=
e=20
> attached PQ fallback leaf script hash.
>
> A second wacky idea which modifies (bastardizes) BIP32 instead of=20
> replacing it: Replace the xpub's chain code with the OP_SUCCESS script's=
=20
> tap leaf hash before distributing. You could derive the PQ keypair from t=
he=20
> parent xpriv, to maintain the integrity of BIP32's chained derivation, so=
=20
> in a it would be like inserting a little modification into BIP32's harden=
ed=20
> derivation logic. Software which doesn't have PQ-fallback support will=20
> derive the standard P2TR addresses we all use today. Software which *does=
* have=20
> PQ-fallback support will derive the same child taproot internal keys, but=
=20
> tweaked with a PQ-fallback script leaf. I imagine this might make=20
> compatibility very complicated though, so i'm not sure if this is a smart=
=20
> choice - throwing this out there in case it inspires better ideas but i=
=20
> wouldn't advocate for it myself.
>
> -c
>
> On Monday, December 16, 2024 at 5:22:44=E2=80=AFPM UTC-5 Tadge Dryja wrot=
e:
>
>> Hi everyone
>>  (disclosure: I'm highly skeptical QCs will break secp256k1 in my=20
>> lifetime, but who knows)
>>
>> IMHO the activation dilemma is the trickiest part of Bitcoin dealing wit=
h=20
>> QCs.  On the one hand, you want a very long term plan, many years ahead =
of=20
>> time, so that everyone has time to migrate and not get their coins stole=
n=20
>> or destroyed.  But the further out a QC is, the less likely it seems it=
=20
>> will ever occur, and thus the less reason there is to write software to=
=20
>> deal with a theoretical, far off problem. (And that's not even getting i=
nto=20
>> the fact that nobody's in charge of Bitcoin so there's no long term road=
map=20
>> anyway.)
>>
>> The ability to have a PQ fallback key with zero or very low on-chain cos=
t=20
>> helps a lot with this, whichever activation path ends up happening. =20
>> Picking something and committing to it in wallets today, before any kind=
 of=20
>> activation, is a bit scary since the PQ pubkey does become an exposed=20
>> private key.  But I think there is a pretty good way to do it with a=20
>> consensus level proof of quantum computer.
>>
>> On Monday, December 16, 2024 at 7:35:47=E2=80=AFAM UTC-5 Anthony Towns w=
rote:
>>
>>
>>
>> - Disabling key path taproot spends via soft-fork is extremely=20
>> confiscatory -- for the consensus cleanup, we worry about even the=20
>> possibility of destroying funds due to transaction patterns never=20
>> seen on the network; here, shutting down key path spends would be=20
>> knowingly destroying an enormous range of utxos.=20
>>
>>
>> This is true, but faced with a QC you're in trouble either way: either=
=20
>> the coins are destroyed, or the first (non-nice) entity to get a QC stea=
ls=20
>> them.  We can hope that if the QC ever does arrive there will be enough=
=20
>> warning and coordination that there won't be *too* many of these utxos a=
t=20
>> that point.
>>
>> But there are still a lot of lost coins where nobody knows the private=
=20
>> keys anymore and in those cases, the lead time doesn't matter. The origi=
nal=20
>> owners who lost the keys would probably prefer those coins to be destroy=
ed=20
>> rather than stolen.  But of course there's no way for them to reliably=
=20
>> express that preference since they can no longer sign.
>>
>> An on-chain proof of quantum computer (PoQC I guess :) ) would be a way=
=20
>> to reduce the damage of activation forks.  One way to build it: Create a=
=20
>> NUMS point pubkey - something like described in BIP341.  Send some coins=
 to=20
>> that address, then watch if it gets spent.  Providing a preimage of the=
=20
>> x-coordinate of a point, as well as a valid signature from that point me=
ans=20
>> that either the hash function is broken or (what we're assuming here) th=
e=20
>> one-wayness of the EC base point multiplication has been broken.  Nodes =
can=20
>> then have code which watches for such a proof and changes consensus rule=
s=20
>> based on it.
>>
>> This can be useful for the activation, or persistence of a confiscatory=
=20
>> restriction of key path spends.  For example:
>>
>> Say people worry about an immanent QC.  They estimate it will be built i=
n=20
>> 5-8 years.  They write software which contains a temporary fork, which=
=20
>> activates in 3 years and *de*activates in 8 years.  This fork disables=
=20
>> almost all key path spends (as well as ECDSA signatures).  The only key=
=20
>> path spends allowed are from the NUMS utxos, and if any NUMS utxo is spe=
nt,=20
>> then the EC prohibition locks in to become permanent instead of revertin=
g 3=20
>> years after initial enforcement.
>>
>> In this case the soft fork is only (permanently) confiscatory if the QC=
=20
>> provably exists and would have (presumably, sooner or later) confiscated=
=20
>> all those coins anyway.  It also could also allow people to enable PQ=20
>> signatures and disable EC signatures a bit sooner than they otherwise wo=
uld=20
>> have, since the cost of being wrong about a QC is lessened -- losing EC=
=20
>> operations would be painful, but even more so if it turns out the nearly=
=20
>> finished QC never quite gets there.
>>
>> An opt-in, non-confiscatory fork could also use this mechanism.  A new=
=20
>> P2TR output type (PQ2TR?) could be used which is explicitly not=20
>> key-spendable post-PoQC, but the older P2TR, P2WPKH, etc output types ar=
e=20
>> still EC spendable (better move em quick).
>>
>> It can also work the other way: The new PQ output type can work just lik=
e=20
>> P2TR, except that one opcode (the OP_PQCHECKSIG) becomes an OP_FAIL unti=
l=20
>> the PoQC.  Given PoQC, it's OP_SUCCESS.  That way we don't have to have =
a=20
>> consensus level definition the actual PQ signature algorithm yet; we've=
=20
>> just put a placeholder PQ signature opcode in, and an activation method.=
  A=20
>> later soft fork can then define the signature algo.  You'd want to defin=
e=20
>> it pretty soon after, since wallets committing to PQ pubkeys for schemes=
=20
>> that end up not getting implemented doesn't help.  But it does allow=20
>> wallets to do something soon for people who are worried and want to be=
=20
>> "quantum safe".
>>
>> -Tadge
>>
>>
>>
>>

--=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/=
2c9a1ffa-8e7b-4de3-b176-e5b24f3bac9fn%40googlegroups.com.

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

Hi all,<br /><br />In my understanding, whatever the recent advances in err=
or code<br />corrections to get universal quantum computer in the real-worl=
d,<br />there is still big unknowns if all the scalability challenges can<b=
r />be solved as the number of physical qubits is going up, whatever<br />t=
he underlying information support (e.g the spin of an electron).<br /><br /=
>All the efforts by many well-funded research team all over<br />the world =
at building QC might just end up on discovering new<br />law of physics ren=
ding intractable the realization of QC...<br /><br />On the other hand, giv=
en the slowness of any consensus upgrade<br />in bitcoin this is definitely=
 an area of concern to keep an<br />eye on it in the situation where QC wou=
ld become practical<br />enough to break the DL problem.<br /><br />I think=
 Tadge's idea of introducing a PoQC, assuming it's<br />feasible, can be br=
illiant to enhance all the "pubkey"<br />exposed coins. For all the old coi=
ns (e.g P2PK more than<br />10 years ago), there could be a soft-fork intro=
duces to<br />restrain the spend to some "seal" PoQC, of which the spend<br=
 />would trigger the key-path spend knock-out of all "pubkey-exposed"<br />=
coins starting at the next block (or at spend height + N).<br /><br />This =
soft-fork could require the unseal spend of a PoQC<br />to have an inflated=
 weight of 4 MB to make the validity<br />transition easy. The new "seal" P=
oQC could be made consensus<br />mandatory for old pubkeys types and user o=
pted-in for newer<br />ones like P2TR (i.e the PQ2TR). Spending a _single_ =
mandatory<br />or opted-in "sealed" pubkey would trigger the key-path spend=
<br />desactivation for all the affected UTXOs. While this would<br />be sa=
crifying one UTXO to save many of them, I think it would<br />minimizes exp=
ectations magical coordination of the community<br />when we see a real QC =
attacker in the wild to rollout a soft-fork.<br /><br />I'm not sure if we =
can come up with a post-quantum scheme to<br />unlock pubkeys exposed throu=
gh key-path, like any post-quantum<br />scheme would have to assume some se=
cret proof of knowledge, though<br />once the DL is broken what information=
 is remaining to the "legit"<br />coins owners to prove their know a speici=
fc scalar before the<br />PoQC "seal" has been reached ...? A Shor-efficien=
t QC would break<br />the secrecy currently affordness by the hardness of f=
actorization.<br /><br />A client-side option could start to anchor the has=
h of EC secret<br />key as an ordering to solve the double-spend problem to=
wards a<br />future QC attacker...even if we don't know yet how to make thi=
s<br />proof valid yet within future post-quantum secure scheme.<br /><br /=
>I don't think we should go for now on one post-quantum scheme like<br />Sp=
hincs, while its cryptanalytic assumptions are easier to understand,<br />i=
t's not like CRYSTALS or FALCON have also been successfully vetted<br />by =
the NIST. A user could script-path commit to a a number of "reserved"<br />=
OP_SUCCESS leafs, and then they can become valid either when the PoQC<br />=
is unsealed by a QC attacker or by a soft-fork ulterior to the PoQC<br />so=
ft-fork. The on-chain fee cost of uncertainty on the most robust<br />post-=
quantum scheme is burden by the user, rather than picking up one<br />schem=
e as the only one (...there is little available litterature on the<br />pos=
t-quantum Grover's algorithm to break hash functions).<br /><br />Additiona=
lly, I don't think pre-signed smarts contracts will be<br />condemned to cl=
ose down, as long as a parallel post-quantum state<br />is counter-signed a=
ll along the classical state. There is no<br />guarantee ahead that the new=
 signature scheme will have a consensus<br />validity (e.g SPHINCS or CRYST=
ALS signatures becoming valid), but<br />at least the parallel state, quant=
um or classic will be ordered by<br />on-chain spend of the UTXO.<br /><br =
/>While this is an open question in the QC field how much time it would<br =
/>take to break a public key DL, and if it's going to be in average inferio=
r<br />to 600 seconds, I think looking for any solution where the PoW is ac=
celerated<br />will condemn us to a never-ending race, as QC latency is imp=
roving. We should<br />rather design consensus rules to yield a new block e=
very 10 min, indifferently<br />of access to a classic or quantum computer =
and with only the quantity of energy<br />as a distinction factor.<br /><br=
 />So to make a digest, in my view I think the main problems are the follow=
ing:<br />- (a) can we come up with a practical PoQC scheme that can be imp=
lemented as full-node consensus rules ?<br />- (b) what is socially accepta=
ble to do with the QC-exposed old "pubkeys" coins that their users will nev=
er touch again ?<br />- (c) what are the client-side opted-in post-quantum =
hooks that could be implemented _now_ ?<br /><br />Ideally, we can solve (a=
) to make the (c) hooks automatically blessed with<br />consensus meaning, =
and that way minimizing community coordination when it's<br />time to upgra=
de to post-quantum cryptography. I don't think there is a good<br />answer =
for (b) assuming no future magic post-quantum scheme to prove a knowledge<b=
r />before a time T, other than anticipating the QC problem _now_ to minimi=
ze the<br />numbers of potentially affected coins in the future.<br /><br /=
>Best,<br />Antoine<br />ots hash: 9238d0a7ce681f0dc944b28745d379b41cd2491d=
<br /><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">Le =
mardi 17 d=C3=A9cembre 2024 =C3=A0 05:42:33 UTC, conduition a =C3=A9crit=C2=
=A0:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8=
ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">Hey all,=
 and thank you for this great idea Matt. It rhymes a little with <a href=3D=
"https://conduition.io/cryptography/quantum-hbs/#Upgrading-Bitcoin" target=
=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com=
/url?hl=3Dfr&amp;q=3Dhttps://conduition.io/cryptography/quantum-hbs/%23Upgr=
ading-Bitcoin&amp;source=3Dgmail&amp;ust=3D1734578850394000&amp;usg=3DAOvVa=
w2YTAAXc7Bgby5onACaF7fw">my DASK idea</a>=C2=A0but I actually like yours a =
lot better, as it provides a cleaner upgrade path for soft-fork compatibili=
ty than DASK.<br><br>However, I suggest we use one of the more succinct Win=
ternitz one-time signature algorithms instead of committing to SPHINCS righ=
t away. This gives us the option of using the WOTS key as a certification l=
ayer for some pubkey from a future signature algorithm, which may or may no=
t even exist yet.<br><br>Not only does this give researchers more time to f=
ind better algorithms, it also makes devs&#39; lives easier, and makes the =
transition to a PQ world more incremental than a head-first dive committing=
 to SPHINCS. WOTS is very simple: it&#39;d be easy to standardize and easy =
for wallets to implement and derive. Its signatures can be as small as 1 ki=
lobyte. Even if we do end up choosing SPHINCS as the 2nd-layer whose pubkey=
 we certify, the time/space overhead added by one WOTS signature is negligi=
ble in comparison. Once the WOTS pubkey is standardized, we can take our ti=
me choosing and standardizing the probably-much-more-complicated 2nd layer =
signing algorithm.<div><div><br>This certification layer idea is straight f=
rom SPHINCS&#39; own whitepaper. This is how SPHINCS authors created its ma=
ny-time property without blowing up the runtime.<br><br>----------<br><br>T=
adge, your PoQC idea is neat but it relies on at least one &quot;good guy&q=
uot; QC willing to produce the proof. A self-interested QC would never will=
ingly crack a pubkey which it knows would activate a soft-fork against its =
own interest. Any publicly-advertised PoQC honeypot addresses able to gathe=
r large donations would be obvious, and a rational QC would ignore them. I =
suppose users could sprinkle some hidden honeypot addresses around the netw=
ork and hope the QC bites one of them, but I don&#39;t think that&#39;s pra=
ctical - The QC would probably prioritize addresses with large balances lik=
e Satoshi&#39;s wallets. I&#39;m not sure if I have any better ideas though=
, besides the also-risky option of relying on the community to act in uniso=
n, triggering activation manually if/when a QC appears to be coming soon to=
 a blockchain near us. So a PoQC might be a good additional trigger, but we=
 also need to be able to manually activate the post-quantum upgrade in case=
 the PoQC is unavailable.</div><div><br></div><div>----------</div><div><br=
></div><div>Another fun aspect of QC&#39;s we haven&#39;t discussed yet is =
BIP32. Whatever pubkey we hide in the OP_SUCCESS tap leaf, it needs to be d=
erived via quantum-secure means. So there can be no unhardened BIP32 anywhe=
re in the derivation chain of the PQ-secret-key, or else xpubs can be sold =
to a QC for profit, even if the PQ soft fork upgrade is activated on time.<=
/div><div><br></div><div>It seems like whatever upgrade path we go with, it=
 will mean the end of BIP32 xpubs as we know them. A 3rd party won&#39;t be=
 able to derive my post-quantum P2TR address from a regular xpub alone with=
out also knowing the OP_SUCCESS script&#39;s tap leaf hash, which by necess=
ity must be completely independent of the xpub. Sounds like we may need a n=
ew standard for that too. Perhaps some kind of &#39;wrapper&#39; which embe=
ds a regular BIP32 xpub, plus the tap leaf hash of the OP_SUCCESS script? T=
hat&#39;d be enough for an untrusted 3rd party to derive a standard set of =
P2TR addresses with the attached PQ fallback leaf script hash.</div><div><b=
r></div><div>A second wacky idea which modifies (bastardizes) BIP32 instead=
 of replacing it: Replace the xpub&#39;s chain code with the OP_SUCCESS scr=
ipt&#39;s tap leaf hash before distributing. You could derive the PQ keypai=
r from the parent xpriv, to maintain the integrity of BIP32&#39;s chained d=
erivation, so in a it would be like inserting a little modification into BI=
P32&#39;s hardened derivation logic. Software which doesn&#39;t have PQ-fal=
lback support will derive the standard P2TR addresses we all use today. Sof=
tware which=C2=A0<i>does</i>=C2=A0have PQ-fallback support will derive the =
same child taproot internal keys, but tweaked with a PQ-fallback script lea=
f. I imagine this might make compatibility very complicated though, so i&#3=
9;m not sure if this is a smart choice - throwing this out there in case it=
 inspires better ideas but i wouldn&#39;t advocate for it myself.</div><div=
><br></div><div><div><div>-c<br><br></div></div></div></div><div class=3D"g=
mail_quote"><div dir=3D"auto" class=3D"gmail_attr">On Monday, December 16, =
2024 at 5:22:44=E2=80=AFPM UTC-5 Tadge Dryja wrote:<br></div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0 0 0 0.8ex;border-left:1px solid rgb(2=
04,204,204);padding-left:1ex"><div>Hi everyone<br></div><div></div><div>=C2=
=A0(disclosure: I&#39;m highly skeptical QCs will break secp256k1 in my lif=
etime, but who knows)<br></div><div><br></div><div><div>IMHO the activation=
 dilemma is the trickiest part of Bitcoin=20
dealing with QCs. =C2=A0On the one hand, you want a very long term plan, ma=
ny
 years ahead of time, so that everyone has time to migrate and not get=20
their coins stolen or destroyed. =C2=A0But the further out a QC is, the les=
s=20
likely it seems it will ever occur, and thus the less reason there is to
 write software to deal with a theoretical, far off problem. (And that&#39;=
s
 not even getting into the fact that nobody&#39;s in charge of Bitcoin so=
=20
there&#39;s no long term roadmap anyway.)<br><br>The ability to have a PQ=
=20
fallback key with zero or very low on-chain cost helps a lot with this,=20
whichever activation path ends up happening.=C2=A0 Picking something and co=
mmitting to it in wallets today, before any kind of activation, is a bit sc=
ary since the PQ pubkey does become an exposed private key.=C2=A0 But I thi=
nk there is a pretty good way to do it with a consensus level proof of quan=
tum computer.</div><div><br></div></div><div></div><div><div dir=3D"auto">O=
n Monday, December 16, 2024 at 7:35:47=E2=80=AFAM UTC-5 Anthony Towns wrote=
:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so=
lid rgb(204,204,204);padding-left:1ex"><br>
<br> - Disabling key path taproot spends via soft-fork is extremely
<br>   confiscatory -- for the consensus cleanup, we worry about even the
<br>   possibility of destroying funds due to transaction patterns never
<br>   seen on the network; here, shutting down key path spends would be
<br>   knowingly destroying an enormous range of utxos.
<br></blockquote><div><br></div></div><div><div>This is true, but faced wit=
h a QC you&#39;re in trouble either way: either the coins are destroyed, or=
 the first (non-nice) entity to get a QC steals them. =C2=A0We can hope tha=
t if the QC ever does arrive there will be enough warning and coordination =
that there won&#39;t be *too* many of these utxos at that point.<br></div><=
div><br></div><div>But there are still a lot of lost coins where nobody kno=
ws the private keys anymore and in those cases, the lead time doesn&#39;t m=
atter. The original owners who lost the keys would probably prefer those co=
ins to be destroyed rather than stolen. =C2=A0But of course there&#39;s no =
way for them to reliably express that preference since they can no longer s=
ign.<br><br>An on-chain proof of quantum computer (PoQC I guess :) ) would =
be a way to reduce the damage of activation forks.=C2=A0 One way to build i=
t: Create a NUMS point pubkey - something like described in BIP341.=C2=A0 S=
end some coins to that address, then watch if it gets spent.=C2=A0 Providin=
g a preimage of the x-coordinate of a point, as well as a valid signature f=
rom that point means that either the hash function is broken or (what we&#3=
9;re assuming here) the one-wayness of the EC base point multiplication has=
 been broken.=C2=A0 Nodes can then have code which watches for such a proof=
 and changes consensus rules based on it.<br><br>This can be useful for the=
 activation, or persistence of a confiscatory restriction of key path spend=
s.=C2=A0 For example:<br><br>Say people worry about an immanent QC. =C2=A0T=
hey estimate it will be built in 5-8 years. =C2=A0They write software which=
 contains a temporary fork, which activates in 3 years and *de*activates in=
 8 years. =C2=A0This fork disables almost all key path spends (as well as E=
CDSA signatures). =C2=A0The only key path spends allowed are from the NUMS =
utxos, and if any NUMS utxo is spent, then the EC prohibition locks in to b=
ecome permanent instead of reverting 3 years after initial enforcement.<br>=
<br>In this case the soft fork is only (permanently) confiscatory if the QC=
 provably exists and would have (presumably, sooner or later) confiscated a=
ll those coins anyway. =C2=A0It also could also allow people to enable PQ s=
ignatures and disable EC signatures a bit sooner than they otherwise would =
have, since the cost of being wrong about a QC is lessened -- losing EC ope=
rations would be painful, but even more so if it turns out the nearly finis=
hed QC never quite gets there.<br><br>An opt-in, non-confiscatory fork coul=
d also use this mechanism. =C2=A0A new P2TR output type (PQ2TR?) could be u=
sed which is explicitly not key-spendable post-PoQC, but the older P2TR, P2=
WPKH, etc output types are still EC spendable (better move em quick).<br></=
div><div><br></div><div>It can also work the other way: The new PQ output t=
ype can work just like P2TR, except that one opcode (the OP_PQCHECKSIG) bec=
omes an OP_FAIL until the PoQC.=C2=A0 Given PoQC, it&#39;s OP_SUCCESS.=C2=
=A0 That way we don&#39;t have to have a consensus level definition the act=
ual PQ signature algorithm yet; we&#39;ve just put a placeholder PQ signatu=
re opcode in, and an activation method.=C2=A0 A later soft fork can then de=
fine the signature algo.=C2=A0 You&#39;d want to define it pretty soon afte=
r, since wallets committing to PQ pubkeys for schemes that end up not getti=
ng implemented doesn&#39;t help.=C2=A0 But it does allow wallets to do some=
thing soon for people who are worried and want to be &quot;quantum safe&quo=
t;.</div><div><br></div><div>-Tadge<br></div><div><br></div><div><br></div>=
<div><br></div></div></blockquote></div></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/2c9a1ffa-8e7b-4de3-b176-e5b24f3bac9fn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/2c9a1ffa-8e7b-4de3-b176-e5b24f3bac9fn%40googlegroups.com</a>.<br />

------=_Part_30745_56714383.1734492557115--

------=_Part_30744_2094829782.1734492557115--