Delivery-date: Mon, 17 Jun 2024 15:25:32 -0700
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of hunter@surmount.systems designates 8.46.89.33 as permitted sender) client-ip=8.46.89.33;
Date: Mon, 17 Jun 2024 14:27:26 -0600
From: hunter <hunter@surmount.systems>
To: "Antoine Riard" <antoine.riard@gmail.com>
Cc: "Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Message-ID: <2cbd432f-ca19-4481-93c5-3b0f7cdea1cb@DS3018xs>
In-Reply-To: <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com>
References: <62fd28ab-e8b5-4cfc-b5ae-0d5a033af057n@googlegroups.com>
 <b3561407-483e-46cd-b5e9-d6d48f8dca93n@googlegroups.com>
 <d78f5dc4-a72d-4da4-8a24-105963155e4dn@googlegroups.com>
 <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com>
Subject: Re: [bitcoindev] Re: Proposing a P2QRH BIP towards a quantum
 resistant soft fork
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: inline
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 2024-06-16 19:31, Antoine Riard <antoine.riard@gmail.com> wrote:

>
> Hi Hunter Beast,I think any post-quantum upgrade signature algorithm upgr=
ade proposal would grandly benefit to haveShor's based practical attacks fa=
r more defined in the Bitcoin context. As soon you start to talk aboutquant=
um computers there is no such thing as a "quantum computer" though a wide a=
rray of architecturesbased on a range of technologies to encode qubits on n=
anoscale physical properties.
>
Good point. I can write a section in the BIP Motivation or Security section=
 about how an attack might take place practically, and the potential urgenc=
y of such an attack.
=C2=A0
I was thinking of focusing on the IBM Quantum System Two, mention how it ca=
n be scaled, and that although it might be quite limited, if running Shor's=
 variant for a sufficient amount of time, above a certain minimum threshold=
 of qubits, it might be capable of decrypting the key to an address within =
one year. I base this on the estimate provided in a study by the Sussex Cen=
tre for Quantum Technologies, et. al [1]. They provide two figures, 317M qu=
bits to decrypt in one hour, 13M qubits to decrypt in one day. It would see=
m it scales roughly linearly, and so extrapolating it further, 36,000 qubit=
s would be needed to decrypt an address within one year. However, the IBM H=
eron QPU=C2=A0turned out to have a gate time 100x less than was estimated i=
n 2022, and so it might be possible to make do with even fewer qubits still=
 within that timeframe. With only 360 qubits, barring algorithmic overhead =
such as for circuit memory, it might be possible to=C2=A0decrypt a single a=
ddress within a year. That might sound like a lot, but being able to=C2=A0a=
ccomplish that=C2=A0at all would be significant, almost like a Chicago Pile=
 moment, proving something in practice that was previously only thought the=
oretically possible for the past 3 decades. And it's only downhill from the=
re...
>
> This is not certain that any Shor's algorithm variant works smoothly inde=
pendently of the quantum computerarchitecture considered (e.g gate frequenc=
y, gate infidelity, cooling energy consumption) and I think it'san interest=
ing open game-theory problem if you can concentrate a sufficiant amount of =
energy before anycoin owner moves them in consequence (e.g seeing a quantum=
 break in the mempool and reacting with a counter-spend).
>
It should be noted that P2PK keys still hold millions of bitcoin, and those=
 encode the entire public key for everyone to see for all time. Thus, early=
 QC attacks won't need to consider the=C2=A0complexities of the mempool.
>
> In my opinion, one of the last time the subject was addressed on the mail=
ing list, the description of the state of the quantum computer field was no=
t realistic and get into risk characterization hyperbole talking about "sup=
er-exponential rate" (when indeed there is no empirical realization=C2=A0th=
at distinct theoretical advance on quantum capabilities=C2=A0can be combine=
d with each other) [1].
>
I think it's time to revisit these discussions given IBM's progress. They'v=
e published a two videos in particular that are worth watching; their keyno=
te from December of last year [2], and their roadmap update from just last =
month [3].
>
> On your proposal, there is an immediate observation which comes to mind, =
namely why not using one of the algorithm(dilthium, sphincs+, falcon) which=
 has been through the 3 rounds of NIST cryptanalysis. Apart of the signatur=
e size,which sounds to be smaller, in a network of full-nodes any PQ signat=
ure algorithm should have reasonable verificationperformances.
>
I'm supportive of this consideration. FALCON might be a good substitute, an=
d maybe it can be upgraded to HAWK for even better performance depending on=
 how much time there is. According to the BIP, FALCON signatures are ~10x l=
arger than Schnorr signatures, so this will of course make the transaction =
more expensive, but we also must remember, these signatures will be going i=
nto the witness, which already receives a 4x discount. Perhaps the discount=
 could be increased further someday to fit more transactions into blocks, b=
ut this will also likely result in more inscriptions filling unused space a=
lso, which permanently increases the burden of running an archive node. Due=
 to the controversy such a change could bring, I would rather any increases=
 in the witness discount be excluded from future activation discussions, so=
 as to be considered separately, even if it pertains to an increase in P2QR=
H transaction size.
=C2=A0
Do you think it's worth reworking the BIP to use FALCON signatures? I've on=
ly done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the r=
eadiness levels between those two are presently worlds apart.
=C2=A0
Also, do you think it's of any concern to use HASH160 instead of HASH256 in=
 the output script? I think it's fine for a cryptographic commitment since =
it's simply a hash of a hash (MD160 of SHA-256).
>
> Lastly, there is a practical defensive technique that can be implemented =
today by coin owners to protect in face ofhyptothetical quantum adversaries=
. Namely setting spending scripts to request an artificially inflated witne=
ss stack,as the cost has to be burden by the spender. I think one can easil=
y do that with OP_DUP and OP_GREATERTHAN and a bitof stack shuffling. While=
 the efficiency of this technique is limited by the max consensus size of t=
he script stack(`MAX_STACK_SIZE`) and the max consensus size of stack eleme=
nt (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional"scarce coins" pre-r=
equirement on the quantum adversarise to succeed. Shor's algorithm is only =
defined under theclassic ressources of computational complexity, time and s=
pace.
>
I'm not sure I fully understand this, but even more practically, as mention=
ed in the BIP, value can simply be kept in P2WPKH outputs, ideally with a v=
alue of fewer than 50 coins per address, and when funds ever need to be spe=
nt, the transaction is signed and submitted out of band to a trusted mining=
 pool, ideally one that does KYC, so it's known which individual miners get=
 to see the public key before it's mined. It's not perfect, since this reli=
es on exogenous security assumptions, which is why P2QRH is proposed.
>
> Best,Antoine
> [1]=C2=A0https://freicoin.substack.com/p/why-im-against-taproot
>
=C2=A0
I'm grateful you took the time to review the BIP and offer your detailed in=
sights.
=C2=A0
[1] =E2=80=9CThe impact of hardware specifications on reaching quantum adva=
ntage in the fault tolerant regime,=E2=80=9D 2022=C2=A0-=C2=A0https://pubs.=
aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specifica=
tions-on-reaching
[2]=C2=A0https://www.youtube.com/watch?v=3DDe2IlWji8Ck
[3]=C2=A0https://www.youtube.com/watch?v=3Dd5aIx79OTps
=C2=A0
>
>
> Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=A9crit=
=C2=A0:
>
> > Good points. I like your suggestion for a SPHINCS+, just due to how mat=
ure it is in comparison to SQIsign. It's already in its third round and has=
 several standards-compliant implementations, and it has an actual specific=
ation rather than just a research paper. One thing to consider is that NIST=
-I round 3 signatures are 982 bytes in size, according to what I was able t=
o find in the documents hosted by the SPHINCS website.
> > https://web.archive.org/web/20230711000109if_/http://sphincs.org/data/s=
phincs+-round3-submission-nist.zip
> > =C2=A0
> > One way to handle this is to introduce this as a separate address type =
than SQIsign. That won't require OP_CAT, and I do want to keep this soft fo=
rk limited in scope. If SQIsign does become significantly broken, in this h=
opefully far future scenario, I might be supportive of an increase in the w=
itness discount.
> > =C2=A0
> > Also, I've made some additional changes based on your feedback on X. Yo=
u can review them here if you so wish:
> > https://github.com/cryptoquick/bips/pull/5/files?short_path=3D917a32a#d=
iff-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82d36411ed45e754
> >
> >
> > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-Luc Dallair=
e-Demers wrote:
> > > SQIsign is blockchain friendly but also very new, I would recommend a=
dding a hash-based backup key in case an attack on SQIsign is found in the =
future (recall that SIDH broke over the span of a weekend=C2=A0https://epri=
nt.iacr.org/2022/975.pdf).
> > > Backup keys can be added in the form of a Merkle tree where one branc=
h would contain the SQIsign public key and the other the public key of the =
recovery hash-based scheme. For most transactions it would only add one bit=
 to specify the SQIsign branch.
> > > The hash-based method could be Sphincs+, which is standardized by NIS=
T but requires adding extra code, or Lamport, which is not standardized but=
 can be verified on-chain with OP-CAT.
> > >
> > > On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4 Hunter Beast w=
rote:
> > > > The motivation for this BIP is to provide a concrete proposal for a=
dding quantum resistance to Bitcoin. We will need to pick a signature algor=
ithm, implement it, and have it ready in event of quantum emergency. There =
will be time to adopt it. Importantly, this first step is a more substantiv=
e answer to those with concerns beyond, "quantum computers may pose a threa=
t, but we likely don't have to worry about that for a long time". Bitcoin d=
evelopment and activation is slow, so it's important that those with low ti=
me preference start discussing this as a serious possibility sooner rather =
than later.  This is meant to be the first in a series of BIPs regarding a =
hypothetical "QuBit" soft fork. The BIP is intended to propose concrete sol=
utions, even if they're early and incomplete, so that Bitcoin developers ar=
e aware of the existence of these solutions and their potential.  This is j=
ust a rough draft and not the finished BIP. I'd like to validate the approa=
ch and hear if I should continue working on it, whether serious changes are=
 needed, or if this truly isn't a worthwhile endeavor right now.
> > > > =C2=A0
> > > > The BIP can be found here:
> > > > https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki
> > > > =C2=A0
> > > > Thank you for your time.
> > > > =C2=A0
> > > >
> > >
> > >
> >
> >
>
>
> -- You received this message because you are subscribed to a topic in the=
 Google Groups "Bitcoin Development Mailing List" group. To unsubscribe fro=
m this topic, visit https://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2=
s/unsubscribe. To unsubscribe from this group and all its topics, send an e=
mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion on=
 the web visit https://groups.google.com/d/msgid/bitcoindev/87b4e402-39d8-4=
6b0-8269-4f81fa501627n%40googlegroups.com.

-----BEGIN PGP SIGNATURE-----
Version: OpenPGP.js v4.10.3
Comment: https://openpgpjs.org

wsBcBAEBCAAGBQJmcJwuAAoJEDEPCKe+At0hjhkIAIdM7QN9hAO0z+KO7Bwe
JT45XyusJmDG1gJbLZtb+SfuE1X5PFDHNTLSNliJWsOImxFCiBPnlXhYQ4B/
8gST3rqplUwkdYr52E5uMxTTq9YaXTako4PNb8d7XfraIwDKXAJF+5Skf4f9
bQUYMieBAFSEXCmluirQymB+hUoaze60Whd07hhpzbGSwK4DdSXltufkyCDE
tJUforNWm8X25ABTSNDh3+if5V/wJuix/u8GJyMHKucaEAO01ki2oyusq2rt
Xe6ysUieclusFFdQAs4PfYxhzXTf5XeAbFga/qxrVtbt7q2nUkYklqteT2pp
mH/DU20HMBeGVSrISrvsmLw=3D
=3D+wat
-----END PGP SIGNATURE-----

--=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 on the web visit https://groups.google.com/d/msgid/=
bitcoindev/2cbd432f-ca19-4481-93c5-3b0f7cdea1cb%40DS3018xs.