path: root/53/49185dec9cd53ec6ea0218da3ea0e126e37fe8

Delivery-date: Tue, 06 Aug 2024 10:50:45 -0700
Received: from mail-yb1-f185.google.com ([209.85.219.185])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBD3YNWFH7IHBB2OEZG2QMGQE2U5R4KA@googlegroups.com>)
	id 1sbOKY-0000IP-Cb
	for bitcoindev@gnusha.org; Tue, 06 Aug 2024 10:50:45 -0700
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e0ba463c970sf1792099276.0
        for <bitcoindev@gnusha.org>; Tue, 06 Aug 2024 10:50:41 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1722966636; x=1723571436; 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=AiZw12mK9KjWjkYM7zwgddv10f6KVgH85Klo4Kkab6E=;
        b=IxQD7uYMs6HEMm2mJLa27nZmd6pYHIZmyH+UPxBEE83Ffbmo1yWUzQdW0GtFoTbEF2
         LI4zK3zPqWhT/CqWNWGGrs6fkiSLc7c+m2h6gBNKL/B3iTBsrVIXokMeB2qI08syZTbs
         TDO78jB1JZTayc7jkgEWB0AcyN5NmnoTqqZcbKjReoYmAuReWo7x9bdWHs6ZJobrnxi0
         mvO3++oV7MYR32TtNQGHNX3jvar3iVV+fNjiDP22j685Oz5DApg+ts/EdOWAidbeaXAm
         EUJBaYG8G6M62NHDoPqEvqmaRPek/L3pvCCb9OnDFIpABp86JdJrMwQUYEiKCToLqSPT
         UASA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1722966636; x=1723571436;
        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=AiZw12mK9KjWjkYM7zwgddv10f6KVgH85Klo4Kkab6E=;
        b=mefWn48xgPtdcGTvvi+6Sfxl1vcQHLIF8dOHCC0B6F87cWvM6IID8xpSJsceqHJaMl
         nTAFjw/3PORrK9sOKhWIFAjZwOaP26sMGsW8XnXVxxrzeZyt2/MfpN+mM73bGalRWKfL
         dmtYnMR6SL/IVyIE0FNEolNdRaHgFkalynGVC4PO6sRsSK/DQRPESrsXJWGKmD9yROHq
         3P4Xl9/UBdILRu8Ah2+R2LKrEBd3pK9GvBWXFyReuaBs7FyjhFquL19hIhXu3OEy5Qfj
         XxQKMhwQbZbyzoess3ENnOy/Ze2oeFnAdPDDF+GcBbqlXGQipx8RM5mpElpYlxOk7Ttw
         hZvA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVcE5zcwicbxQ6sccosl43jBID+PWzAuwW+fp61bufXDqetrWq9xovFcS3xCsYbtFPDjHTpvMAw4ICks7aj2h+Wb/8i+Yk=
X-Gm-Message-State: AOJu0YyxZXOZQ/pMA2ilIYPTfGmboCREhEULdQVPsdeAt8GHL1EvNtD+
	xsanG3jYidMWvvwmVuKJCGntpnrz8sSDIjbaIjABpXcCAKstq5dW
X-Google-Smtp-Source: AGHT+IHrrV/vXs2P9SV1GZBghOeaHUd/ngjUy04yztgmBsAzGrcp/9oImF4ibiLWzIqEZzQuKgvAwQ==
X-Received: by 2002:a05:6902:114b:b0:e0d:d525:86b8 with SMTP id 3f1490d57ef6-e0dd5258c41mr12855522276.36.1722966635625;
        Tue, 06 Aug 2024 10:50:35 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:102c:b0:dfd:bfdd:cd15 with SMTP id
 3f1490d57ef6-e0bf4c0c531ls5066399276.1.-pod-prod-07-us; Tue, 06 Aug 2024
 10:50:33 -0700 (PDT)
X-Received: by 2002:a05:690c:2e0e:b0:615:32e1:d82c with SMTP id 00721157ae682-689640aea10mr3084577b3.6.1722966633293;
        Tue, 06 Aug 2024 10:50:33 -0700 (PDT)
Received: by 2002:a05:690c:2884:b0:664:87b6:d9e0 with SMTP id 00721157ae682-698ab783debms7b3;
        Tue, 6 Aug 2024 10:37:16 -0700 (PDT)
X-Received: by 2002:a81:a788:0:b0:697:9aae:1490 with SMTP id 00721157ae682-6979aae1895mr680487b3.1.1722965834835;
        Tue, 06 Aug 2024 10:37:14 -0700 (PDT)
Date: Tue, 6 Aug 2024 10:37:14 -0700 (PDT)
From: Hunter Beast <hunter@surmount.systems>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <1b86f467-95e5-4558-98bc-b921dd29e1afn@googlegroups.com>
In-Reply-To: <cd6bda66-39d3-49ca-9f3c-f610258626b0n@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>
 <2cbd432f-ca19-4481-93c5-3b0f7cdea1cb@DS3018xs>
 <cd6bda66-39d3-49ca-9f3c-f610258626b0n@googlegroups.com>
Subject: Re: [bitcoindev] Re: Proposing a P2QRH BIP towards a quantum
 resistant soft fork
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_871338_1805467811.1722965834575"
X-Original-Sender: hunter@surmount.systems
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.7 (/)

------=_Part_871338_1805467811.1722965834575
Content-Type: multipart/alternative; 
	boundary="----=_Part_871339_835844614.1722965834575"

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

That's alright, Antoine, it's been a busy month for me too.

> So I think it's good to stay cool minded and I think my observation about=
=20
talking of "super-exponential rate" as used in maaku old blog post does not
> hold a lot of rigor to describe the advances in the field of quantum=20
computing. Note, also how IMB is a commercial entity that can have a lot of=
=20
interests
> in "pumping" the state of "quantum computing" to gather fundings (there=
=20
is a historical anecdote among bitcoin OG circles about Vitalik trying to=
=20
do an
> ICO to build a quantum computer like 10 years ago, just to remember).

Well, it's also important to remember that for every qubit added, it=20
doubles the power of the system. A 2,000 qubit cryptographically-relevant=
=20
quantum computer (CRQC) is exponentially faster than a 1,000 qubit one.=20
There's also the capability for cross-links for multiple chips to=20
communicate with each other, which IBM is also researching. The IBM Quantum=
=20
System Two can be upgraded to support 16,000 qubits according to their=20
marketing. Also consider that the verification of the results from the CRQC=
=20
can be done via classical computer, so a high level of error correction=20
might not be as necessary so long as the program is run enough times. It=20
will take much longer, of course.

> I think FALCON is what has the smallest pubkey + sig size for=20
hash-and-sign lattice-based schemes. So I think it's worth reworking the=20
BIP to see what has the smallest generation / validation time and pubkey +=
=20
size space for the main post-quantum scheme. At least for dilthium, falcon,=
=20
sphincs+ and SQISign. For an hypothetical witness discount, a v2 P2QRH=20
could be always be moved in a very template annex tag / field.

I've decided in one of my more recent updates to the BIP to default to the=
=20
highest level of NIST security, NIST V, which provides 256 bits of=20
security. You can see my rationale for that in this PR:
https://github.com/cryptoquick/bips/pull/7/files
Then, referencing this table:
https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki#security
As such, you'll see FALCON is roughly 4x larger than SQIsign signatures.=20
Although supersingular elliptic curve quaternion isogeny-based algorithms=
=20
are newer and more experimental than lattice-based cryptography, I think=20
the benefits outweigh the risks, especially when transaction throughput is=
=20
a principal concern.

It's crucial that the signature and public key both receive the witness=20
discount. Can you go into more detail in how that might be accomplished?

Although it's too early to talk about activation of a QuBit soft fork, I've=
=20
put some thought into how we can maintain the existing Bitcoin throughput=
=20
with a soft fork, and I think it might be prudent to, when the time comes,=
=20
introduce a 4x additional QuBit witness discount, maybe we call it the=20
quitness, which is only available to valid P2QRH signatures. This would=20
preclude its abuse for things like inscriptions because the signature data=
=20
would need to correspond to the key, and even if this were possible, it's=
=20
likely to result in only a burner address. This would increase chain state=
=20
growth from roughly 100GB/yr to possibly closer to 2-300GB, depending on=20
adoption. As the state of the art of SSD technology advances, this should=
=20
allow plebs to run their own node on a 4TB disk for over a decade, even=20
including existing chain size of ~600GB.

If we were to use the same approach for FALCON signatures, a 16x discount=
=20
would be needed, and I think that's far too much for the community to=20
accept. As for pub key size and verification time, these are secondary=20
considerations if the primary constraint is maintaining present transaction=
=20
throughput. That's what makes SQIsign so promising.

> See literature on quantum attacks on bitcoin in the reference of the=20
paper you quote ("The impact of hardware specifications on reaching quantum=
=20
advantage in the fault tolerant regime") for a discussion on Grover's=20
search algorithm.

The Impact paper seems to dismiss Grover's algorithm, but I think it's=20
important to err on the size of caution and instead use a 32-byte double=20
SHA-2 (HASH256) for additional security in the P2QRH output.

> Namely you can introduce an artifical "witness-stack size scale ladder"=
=20
in pseudo-bitcoin script: OP_SIZE <1000> OP_EQUALVERIFY OP_DROP=20
...checksig...
> I have not verified it works well on bitcoin core though this script=20
should put the burden on the quantum attacker to have enough bitcoin amount=
=20
available to burn in on-chain fees in witness size to break a P2WPKH.

I'm not sure I understand what you mean by this...
Is your coin scarcity comment related to what I call "satoshi's shield" in=
=20
the BIP?

> The technical issue if you implement KYC for a mining pool you're=20
increasing your DoS surface and this could be exploited by competing=20
miners. A more reasonable security model can be to have miner coinbase=20
pubkeys being used to commit to the "seen-in-mempool" spends and from then=
=20
build "hand wawy" fraud proofs that a miner is quantum attacking you're=20
P2WSH spends at pubkey reveal time during transaction relay.

Yes, this makes more sense. I'm not sure anything can be done with the=20
fraud proofs, but they could at least prove that a bad actor is present.=20
Ideally both approaches are combined for maximum security and=20
accountability.

Thanks for your time!

On Friday, July 12, 2024 at 7:44:27=E2=80=AFPM UTC-6 Antoine Riard wrote:

Hi Hunter Beast,

Apologies for the delay in answer.

> I was thinking of focusing on the IBM Quantum System Two, mention how it=
=20
can be scaled, and that although it might be quite limited, if running=20
Shor's variant for a > sufficient amount of time, above a certain minimum=
=20
threshold of qubits, it might be capable of decrypting the key to an=20
address within one year. I base this on the estimate > provided in a study=
=20
by the Sussex Centre for Quantum Technologies, et. al [1]. They provide two=
=20
figures, 317M qubits to decrypt in one hour, 13M qubits to decrypt in one >=
=20
day. It would seem it scales roughly linearly, and so extrapolating it=20
further, 36,000 qubits would be needed to decrypt an address within one=20
year. However, the IBM Heron > QPU turned out to have a gate time 100x less=
=20
than was estimated in 2022, and so it might be possible to make do with=20
even fewer qubits still within that timeframe. With > only 360 qubits,=20
barring algorithmic overhead such as for circuit memory, it might be=20
possible to decrypt a single address within a year. That might sound like a=
=20
lot, but > being able to accomplish that at all would be significant,=20
almost like a Chicago Pile moment, proving something in practice that was=
=20
previously only thought theoretically > possible for the past 3 decades.=20
And it's only downhill from there...

Briefly surveying the paper "The impact of hardware specifications on=20
reaching quantum advantage in the fault tolerant regime", I think it's a=20
reasonble framework to evaluate
the practical efficiency of quantum attacks on bitcoin, it's self=20
consistent and there is a critical approach referencing the usual=20
litterature on quantum attacks on bitcoin. Just
note the caveat, one can find in usual quantum complexity litterature,=20
"particularly in regard to end-to-end physical resource estimation. There=
=20
are many other error correction
techniques available, and the best choice will likely depend on the=20
underlying architecture's characteristics, such as the available physical=
=20
qubit=E2=80=93qubit connectivity" (verbatim). Namely, evaluating quantum at=
tacks is=20
very dependent on the concrete physical architecture underpinning it.

All that said, I agree with you that if you see a quantum computer with the=
=20
range of 1000 physical qubits being able to break the DLP for ECC based=20
encryption like secp256k1, even if it takes a year it will be a Chicago=20
Pile moment, or whatever comparative experiments which were happening about=
=20
chain of nuclear reactions in 30s / 40s.

>  I think it's time to revisit these discussions given IBM's progress.=20
They've published a two videos in particular that are worth watching; their=
=20
keynote from December of last > year [2], and their roadmap update from=20
just last month [3]

I have looked on the roadmap as it's available on the IBM blog post:=20
https://www.ibm.com/quantum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2=
033
They give only a target of 2000 logical qubit to be reach in 2033...which=
=20
is surprisingly not that strong...And one expect they might hit likely soli=
d
state issues in laying out in hardware the Heron processor architecture. As=
=20
a point of thinking, it took like 2 decades to advance on the state of art
of litography in traditional chips manufacturing.
=20
So I think it's good to stay cool minded and I think my observation about=
=20
talking of "super-exponential rate" as used in maaku old blog post does not
hold a lot of rigor to describe the advances in the field of quantum=20
computing. Note, also how IMB is a commercial entity that can have a lot of=
=20
interests
in "pumping" the state of "quantum computing" to gather fundings (there is=
=20
a historical anecdote among bitcoin OG circles about Vitalik trying to do a=
n
ICO to build a quantum computer like 10 years ago, just to remember).

> I'm supportive of this consideration. FALCON might be a good substitute,=
=20
and maybe it can be upgraded to HAWK for even better performance depending=
=20
on how much > time there is. According to the BIP, FALCON signatures are=20
~10x larger t> han Schnorr signatures, so this will of course make the=20
transaction more expensive, but we also > must remember, these signatures=
=20
will be going into the witness, which already receives a 4x discount.=20
Perhaps the discount could be incr> eased further someday to fit > more=20
transactions into blocks, but this will also likely result in more=20
inscriptions filling unused space also, which permanently increases the=20
burden of running an archive > node. Due to the controversy s> uch a change=
=20
could bring, I would rather any increases in the witness discount be=20
excluded from future activation discussions, so as to be > considered=20
separately, even if it pertains to an increase in P2QRH transaction size.
=20
> Do you think it's worth reworking the BIP to use FALCON signatures? I've=
=20
only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the=
=20
readiness levels between those two are presently worlds apart.

I think FALCON is what has the smallest pubkey + sig size for hash-and-sign=
=20
lattice-based schemes. So I think it's worth reworking the BIP to see what=
=20
has the smallest generation / validation time and pubkey + size space for=
=20
the main post-quantum scheme. At least for dilthium, falcon, sphincs+ and=
=20
SQISign. For an hypothetical witness discount, a v2 P2QRH could be always=
=20
be moved in a very template annex tag / field.

> Also, do you think it's of any concern to use HASH160 instead of HASH256=
=20
in the output script? I think it's fine for a cryptographic commitment=20
since it's simply a hash of a hash (MD160 of SHA-256).

See literature on quantum attacks on bitcoin in the reference of the paper=
=20
you quote ("The impact of hardware specifications on reaching quantum=20
advantage in the fault tolerant regime") for a discussion on Grover's=20
search algorithm.

> I'm not sure I fully understand this, but even more practically, as=20
mentioned in the BIP, value can simply be kept in P2WPKH outputs, ideally=
=20
with a value of fewer than 50
> coins per address, and when funds ever need to be spent, the>=20
 transaction is signed and submitted out of band to a trusted mining pool,=
=20
ideally one that does KYC, so it's
> known which individual miners get to see the public key before it's=20
mined. It's not perfect, since this relies on exogenou> s security=20
assumptions, which is why P2QRH is
> proposed.

Again, the paper you're referencing ("The impact of hardware specifications=
=20
on reaching quantum advantage...") is analyzing the performance of quantum=
=20
advantage under
2 dimensions, namely space and time. My observation is in Bitcoin we have=
=20
an additional dimension, "coin scarcity" that can be leveraged to build=20
defense of address
spends in face of quantum attacks.

Namely you can introduce an artifical "witness-stack size scale ladder" in=
=20
pseudo-bitcoin script: OP_SIZE <1000> OP_EQUALVERIFY OP_DROP ...checksig...
I have not verified it works well on bitcoin core though this script should=
=20
put the burden on the quantum attacker to have enough bitcoin amount=20
available to burn in on-chain fees in witness size to break a P2WPKH.


>  ideally with a value of fewer than 50 coins per address, and when funds=
=20
ever need to be spent, the transaction is signed and submitted out of band=
=20
to a trusted mining pool, ideally
> one that does KYC, so it's known which individual > miners get to see the=
=20
public key before it's mined. It's not perfect, since this relies on=20
exogenous security assumptions, which is
> why P2QRH is proposed.

The technical issue if you implement KYC for a mining pool you're=20
increasing your DoS surface and this could be exploited by competing=20
miners. A more reasonable security model can be to have miner coinbase=20
pubkeys being used to commit to the "seen-in-mempool" spends and from then=
=20
build "hand wawy" fraud proofs that a miner is quantum attacking you're=20
P2WSH spends at pubkey reveal time during transaction relay.

Best,
Antoine

ots hash: 1ad818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb27f1f0dc0b30
Le lundi 17 juin 2024 =C3=A0 23:25:25 UTC+1, hunter a =C3=A9crit :


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

On 2024-06-16 19:31, Antoine Riard <antoin...@gmail.com> wrote:=20

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


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

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

--=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/1b86f467-95e5-4558-98bc-b921dd29e1afn%40googlegroups.com.

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

That's alright, Antoine, it's been a busy month for me too.<div><br /></div=
><div>&gt; So I think it's good to stay cool minded and I think my observat=
ion about talking of "super-exponential rate" as used in maaku old blog pos=
t does not<br />&gt; hold a lot of rigor to describe the advances in the fi=
eld of quantum computing. Note, also how IMB is a commercial entity that ca=
n have a lot of interests<br />&gt; in "pumping" the state of "quantum comp=
uting" to gather fundings (there is a historical anecdote among bitcoin OG =
circles about Vitalik trying to do an<br />&gt; ICO to build a quantum comp=
uter like 10 years ago, just to remember).</div><div><br /></div><div>Well,=
 it's also important to remember that for every qubit added, it doubles the=
 power of the system. A 2,000 qubit cryptographically-relevant quantum comp=
uter (CRQC) is exponentially faster than a 1,000 qubit one. There's also th=
e capability for cross-links for multiple chips to communicate with each ot=
her, which IBM is also researching. The IBM Quantum System Two can be upgra=
ded to support 16,000 qubits according to their marketing. Also consider th=
at the verification of the results from the CRQC can be done via classical =
computer, so a high level of error correction might not be as necessary so =
long as the program is run enough times. It will take much longer, of cours=
e.</div><div><br /></div><div>&gt; I think FALCON is what has the smallest =
pubkey + sig size for hash-and-sign lattice-based schemes. So I think it's =
worth reworking the BIP to see what has the smallest generation / validatio=
n time and pubkey + size space for the main post-quantum scheme. At least f=
or dilthium, falcon, sphincs+ and SQISign. For an hypothetical witness disc=
ount, a v2 P2QRH could be always be moved in a very template annex tag / fi=
eld.</div><div><br /></div><div>I've decided in one of my more recent updat=
es to the BIP to default to the highest level of NIST security, NIST V, whi=
ch provides 256 bits of security. You can see my rationale for that in this=
 PR:</div><div>https://github.com/cryptoquick/bips/pull/7/files</div><div>T=
hen, referencing this table:</div><div>https://github.com/cryptoquick/bips/=
blob/p2qrh/bip-p2qrh.mediawiki#security<br /></div><div>As such, you'll see=
 FALCON is roughly 4x larger than SQIsign signatures. Although supersingula=
r elliptic curve quaternion isogeny-based algorithms are newer and more exp=
erimental than lattice-based cryptography, I think the benefits outweigh th=
e risks, especially when transaction throughput is a principal concern.</di=
v><div><br /></div><div>It's crucial that the signature and public key both=
 receive the witness discount. Can you go into more detail in how that migh=
t be accomplished?</div><div><br /></div><div>Although it's too early to ta=
lk about activation of a QuBit soft fork, I've put some thought into how we=
 can maintain the existing Bitcoin throughput with a soft fork, and I think=
 it might be prudent to, when the time comes, introduce a 4x additional QuB=
it witness discount, maybe we call it the quitness, which is only available=
 to valid P2QRH signatures. This would preclude its abuse for things like i=
nscriptions because the signature data would need to correspond to the key,=
 and even if this were possible, it's likely to result in only a burner add=
ress. This would increase chain state growth from roughly 100GB/yr to possi=
bly closer to 2-300GB, depending on adoption. As the state of the art of SS=
D technology advances, this should allow plebs to run their own node on a 4=
TB disk for over a decade, even including existing chain size of ~600GB.</d=
iv><div><br /></div><div>If we were to use the same approach for FALCON sig=
natures, a 16x discount would be needed, and I think that's far too much fo=
r the community to accept. As for pub key size and verification time, these=
 are secondary considerations if the primary constraint is maintaining pres=
ent transaction throughput. That's what makes SQIsign so promising.</div><d=
iv><br /></div><div>&gt; See literature on quantum attacks on bitcoin in th=
e reference of the paper you quote ("The impact of hardware specifications =
on reaching quantum advantage in the fault tolerant regime") for a discussi=
on on Grover's search algorithm.</div><div><br /></div><div>The Impact pape=
r seems to dismiss Grover's algorithm, but I think it's important to err on=
 the size of caution and instead use a 32-byte double SHA-2 (HASH256) for a=
dditional security in the P2QRH output.</div><div><br /></div><div>&gt; Nam=
ely you can introduce an artifical "witness-stack size scale ladder" in pse=
udo-bitcoin script: OP_SIZE &lt;1000&gt; OP_EQUALVERIFY OP_DROP ...checksig=
...</div><div>&gt; I have not verified it works well on bitcoin core though=
 this script should put the burden on the quantum attacker to have enough b=
itcoin amount available to burn in on-chain fees in witness size to break a=
 P2WPKH.</div><div><br /></div><div>I'm not sure I understand what you mean=
 by this...</div><div>Is your coin scarcity comment related to what I call =
"satoshi's shield" in the BIP?</div><div><br /></div><div>&gt; The technica=
l issue if you implement KYC for a mining pool you're increasing your DoS s=
urface and this could be exploited by competing miners. A more reasonable s=
ecurity model can be to have miner coinbase pubkeys being used to commit to=
 the "seen-in-mempool" spends and from then build "hand wawy" fraud proofs =
that a miner is quantum attacking you're P2WSH spends at pubkey reveal time=
 during transaction relay.</div><div><br /></div><div>Yes, this makes more =
sense. I'm not sure anything can be done with the fraud proofs, but they co=
uld at least prove that a bad actor is present. Ideally both approaches are=
 combined for maximum security and accountability.</div><div><br /></div><d=
iv>Thanks for your time!</div><div><div><br /></div><div><div dir=3D"auto">=
On Friday, July 12, 2024 at 7:44:27=E2=80=AFPM UTC-6 Antoine Riard wrote:<b=
r /></div><blockquote style=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px =
solid rgb(204, 204, 204); padding-left: 1ex;">Hi Hunter Beast,<br /><br />A=
pologies for the delay in answer.<br /><br />&gt; I was thinking of focusin=
g on the IBM Quantum System Two, mention how it can be scaled, and that alt=
hough it might be quite limited, if running Shor's variant for a &gt; suffi=
cient 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 thi=
s on the estimate &gt; provided in a study by the Sussex Centre for Quantum=
 Technologies, et. al [1]. They provide two figures, 317M qubits to decrypt=
 in one hour, 13M qubits to decrypt in one &gt; day. It would seem it scale=
s roughly linearly, and so extrapolating it further, 36,000 qubits would be=
 needed to decrypt an address within one year. However, the IBM Heron &gt; =
QPU turned out to have a gate time 100x less than was estimated in 2022, an=
d so it might be possible to make do with even fewer qubits still within th=
at timeframe. With &gt; only 360 qubits, barring algorithmic overhead such =
as for circuit memory, it might be possible to decrypt a single address wit=
hin a year. That might sound like a lot, but &gt; being able to accomplish =
that at all would be significant, almost like a Chicago Pile moment, provin=
g something in practice that was previously only thought theoretically &gt;=
 possible for the past 3 decades. And it's only downhill from there...<br /=
><br />Briefly surveying the paper "The impact of hardware specifications o=
n reaching quantum advantage in the fault tolerant regime", I think it's a =
reasonble framework to evaluate<br />the practical efficiency of quantum at=
tacks on bitcoin, it's self consistent and there is a critical approach ref=
erencing the usual litterature on quantum attacks on bitcoin. Just<br />not=
e the caveat, one can find in usual quantum complexity litterature, "partic=
ularly in regard to end-to-end physical resource estimation. There are many=
 other error correction<br />techniques available, and the best choice will=
 likely depend on the underlying architecture's characteristics, such as th=
e available physical qubit=E2=80=93qubit connectivity" (verbatim). Namely, =
evaluating quantum attacks is very dependent on the concrete physical archi=
tecture underpinning it.<br /><br />All that said, I agree with you that if=
 you see a quantum computer with the range of 1000 physical qubits being ab=
le to break the DLP for ECC based encryption like secp256k1, even if it tak=
es a year it will be a Chicago Pile moment, or whatever comparative experim=
ents which were happening about chain of nuclear reactions in 30s / 40s.<br=
 /><br />&gt; =C2=A0I think it's time to revisit these discussions given IB=
M's progress. They've published a two videos in particular that are worth w=
atching; their keynote from December of last &gt; year [2], and their roadm=
ap update from just last month [3]<br /><br />I have looked on the roadmap =
as it's available on the IBM blog post: <a href=3D"https://www.ibm.com/quan=
tum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2033" target=3D"_blank" r=
el=3D"nofollow">https://www.ibm.com/quantum/blog/quantum-roadmap-2033#mark-=
roadmap-out-to-2033</a><br />They give only a target of 2000 logical qubit =
to be reach in 2033...which is surprisingly not that strong...And one expec=
t they might hit likely solid<br />state issues in laying out in hardware t=
he Heron processor architecture. As a point of thinking, it took like 2 dec=
ades to advance on the state of art<br />of litography in traditional chips=
 manufacturing.<br />=C2=A0<br />So I think it's good to stay cool minded a=
nd I think my observation about talking of "super-exponential rate" as used=
 in maaku old blog post does not<br />hold a lot of rigor to describe the a=
dvances in the field of quantum computing. Note, also how IMB is a commerci=
al entity that can have a lot of interests<br />in "pumping" the state of "=
quantum computing" to gather fundings (there is a historical anecdote among=
 bitcoin OG circles about Vitalik trying to do an<br />ICO to build a quant=
um computer like 10 years ago, just to remember).<br /><br />&gt; I'm suppo=
rtive of this consideration. FALCON might be a good substitute, and maybe i=
t can be upgraded to HAWK for even better performance depending on how much=
 &gt; time there is. According to the BIP, FALCON signatures are ~10x large=
r t&gt; han Schnorr signatures, so this will of course make the transaction=
 more expensive, but we also &gt; must remember, these signatures will be g=
oing into the witness, which already receives a 4x discount. Perhaps the di=
scount could be incr&gt; eased further someday to fit &gt; more transaction=
s into blocks, but this will also likely result in more inscriptions fillin=
g unused space also, which permanently increases the burden of running an a=
rchive &gt; node. Due to the controversy s&gt; uch a change could bring, I =
would rather any increases in the witness discount be excluded from future =
activation discussions, so as to be &gt; considered separately, even if it =
pertains to an increase in P2QRH transaction size.<br />=C2=A0<br />&gt; Do=
 you think it's worth reworking the BIP to use FALCON signatures? I've only=
 done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the rea=
diness levels between those two are presently worlds apart.<br /><br />I th=
ink FALCON is what has the smallest pubkey + sig size for hash-and-sign lat=
tice-based schemes. So I think it's worth reworking the BIP to see what has=
 the smallest generation / validation time and pubkey + size space for the =
main post-quantum scheme. At least for dilthium, falcon, sphincs+ and SQISi=
gn. For an hypothetical witness discount, a v2 P2QRH could be always be mov=
ed in a very template annex tag / field.<br /><br />&gt; 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).<br /><br />See literature on quantum attacks=
 on bitcoin in the reference of the paper you quote ("The impact of hardwar=
e specifications on reaching quantum advantage in the fault tolerant regime=
") for a discussion on Grover's search algorithm.<br /><br />&gt; I'm not s=
ure I fully understand this, but even more practically, as mentioned in the=
 BIP, value can simply be kept in P2WPKH outputs, ideally with a value of f=
ewer than 50<div>&gt; coins per address, and when funds ever need to be spe=
nt, the&gt; =C2=A0transaction is signed and submitted out of band to a trus=
ted mining pool, ideally one that does KYC, so it's</div><div>&gt; known wh=
ich individual miners get to see the public key before it's mined. It's not=
 perfect, since this relies on exogenou&gt; s security assumptions, which i=
s why P2QRH is</div><div>&gt; proposed.<br /><br />Again, the paper you're =
referencing ("The impact of hardware specifications on reaching quantum adv=
antage...") is analyzing the performance of quantum advantage under<br />2 =
dimensions, namely space and time. My observation is in Bitcoin we have an =
additional dimension, "coin scarcity" that can be leveraged to build defens=
e of address<br />spends in face of quantum attacks.<br /><br />Namely you =
can introduce an artifical "witness-stack size scale ladder" in pseudo-bitc=
oin script: OP_SIZE &lt;1000&gt; OP_EQUALVERIFY OP_DROP ...checksig...<br /=
>I have not verified it works well on bitcoin core though this script shoul=
d put the burden on the quantum attacker to have enough bitcoin amount avai=
lable to burn in on-chain fees in witness size to break a P2WPKH.</div><div=
><br /><br />&gt; =C2=A0ideally with a value of fewer than 50 coins per add=
ress, and when funds ever need to be spent, the transaction is signed and s=
ubmitted out of band to a trusted mining pool, ideally<br />&gt; one that d=
oes KYC, so it's known which individual &gt; miners get to see the public k=
ey before it's mined. It's not perfect, since this relies on exogenous secu=
rity assumptions, which is<br />&gt; why P2QRH is proposed.<br /><br /></di=
v><div>The technical issue if you implement KYC for a mining pool you're in=
creasing your DoS surface and this could be exploited by competing miners. =
A more reasonable security model can be to have miner coinbase pubkeys bein=
g used to commit to the "seen-in-mempool" spends and from then build "hand =
wawy" fraud proofs that a miner is quantum attacking you're P2WSH spends at=
 pubkey reveal time during transaction relay.<br /><br />Best,<br />Antoine=
</div><div><br /></div><div>ots hash:=C2=A01ad818955bbf0c5468847c00c2974ddb=
5cf609d630523622bfdb27f1f0dc0b30</div><div><div dir=3D"auto">Le lundi 17 ju=
in 2024 =C3=A0 23:25:25 UTC+1, hunter a =C3=A9crit=C2=A0:<br /></div><block=
quote style=3D"margin: 0px 0px 0px 0.8ex; border-left: 1px solid rgb(204, 2=
04, 204); padding-left: 1ex;">
<br />-----BEGIN PGP SIGNED MESSAGE-----
<br />Hash: SHA256
<br />
<br />On 2024-06-16 19:31, Antoine Riard &lt;<a rel=3D"nofollow">antoin...@=
gmail.com</a>&gt; wrote:
<br />
<br />&gt;
<br />&gt; Hi Hunter Beast,I think any post-quantum upgrade signature algor=
ithm upgrade proposal would grandly benefit to haveShor's based practical a=
ttacks far more defined in the Bitcoin context. As soon you start to talk a=
boutquantum computers there is no such thing as a "quantum computer" though=
 a wide array of architecturesbased on a range of technologies to encode qu=
bits on nanoscale physical properties.
<br />&gt;
<br />Good point. I can write a section in the BIP Motivation or Security s=
ection about how an attack might take place practically, and the potential =
urgency of such an attack.
<br />=C2=A0
<br />I was thinking of focusing on the IBM Quantum System Two, mention how=
 it can 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 thr=
eshold of qubits, it might be capable of decrypting the key to an address w=
ithin one year. I base this on the estimate provided in a study by the Suss=
ex Centre for Quantum Technologies, et. al [1]. They provide two figures, 3=
17M qubits to decrypt in one hour, 13M qubits to decrypt in one day. It wou=
ld seem it scales roughly linearly, and so extrapolating it further, 36,000=
 qubits would be needed to decrypt an address within one year. However, the=
 IBM Heron QPU=C2=A0turned out to have a gate time 100x less than was estim=
ated in 2022, and so it might be possible to make do with even fewer qubits=
 still within that timeframe. With only 360 qubits, barring algorithmic ove=
rhead such as for circuit memory, it might be possible to=C2=A0decrypt a si=
ngle address within a year. That might sound like a lot, but being able to=
=C2=A0accomplish that=C2=A0at all would be significant, almost like a Chica=
go Pile moment, proving something in practice that was previously only thou=
ght theoretically possible for the past 3 decades. And it's only downhill f=
rom there...
<br />&gt;
<br />&gt; This is not certain that any Shor's algorithm variant works smoo=
thly independently of the quantum computerarchitecture considered (e.g gate=
 frequency, gate infidelity, cooling energy consumption) and I think it'san=
 interesting open game-theory problem if you can concentrate a sufficiant a=
mount of energy before anycoin owner moves them in consequence (e.g seeing =
a quantum break in the mempool and reacting with a counter-spend).
<br />&gt;
<br />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 mempo=
ol.
<br />&gt;
<br />&gt; In my opinion, one of the last time the subject was addressed on=
 the mailing list, the description of the state of the quantum computer fie=
ld was not realistic and get into risk characterization hyperbole talking a=
bout "super-exponential rate" (when indeed there is no empirical realizatio=
n=C2=A0that distinct theoretical advance on quantum capabilities=C2=A0can b=
e combined with each other) [1].
<br />&gt;
<br />I think it's time to revisit these discussions given IBM's progress. =
They've published a two videos in particular that are worth watching; their=
 keynote from December of last year [2], and their roadmap update from just=
 last month [3].
<br />&gt;
<br />&gt; On your proposal, there is an immediate observation which comes =
to mind, namely why not using one of the algorithm(dilthium, sphincs+, falc=
on) which has been through the 3 rounds of NIST cryptanalysis. Apart of the=
 signature size,which sounds to be smaller, in a network of full-nodes any =
PQ signature algorithm should have reasonable verificationperformances.
<br />&gt;
<br />I'm supportive of this consideration. FALCON might be a good substitu=
te, and maybe it can be upgraded to HAWK for even better performance depend=
ing on how much time there is. According to the BIP, FALCON signatures are =
~10x larger than Schnorr signatures, so this will of course make the transa=
ction more expensive, but we also must remember, these signatures will be g=
oing into the witness, which already receives a 4x discount. Perhaps the di=
scount could be increased further someday to fit more transactions into blo=
cks, but this will also likely result in more inscriptions filling unused s=
pace also, which permanently increases the burden of running an archive nod=
e. Due to the controversy such a change could bring, I would rather any inc=
reases in the witness discount be excluded from future activation discussio=
ns, so as to be considered separately, even if it pertains to an increase i=
n P2QRH transaction size.
<br />=C2=A0
<br />Do you think it's worth reworking the BIP to use FALCON signatures? I=
've only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge=
 the readiness levels between those two are presently worlds apart.
<br />=C2=A0
<br />Also, do you think it's of any concern to use HASH160 instead of HASH=
256 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).
<br />&gt;
<br />&gt; Lastly, there is a practical defensive technique that can be imp=
lemented today by coin owners to protect in face ofhyptothetical quantum ad=
versaries. Namely setting spending scripts to request an artificially infla=
ted witness stack,as the cost has to be burden by the spender. I think one =
can easily do that with OP_DUP and OP_GREATERTHAN and a bitof stack shuffli=
ng. While the efficiency of this technique is limited by the max consensus =
size of the script stack(`MAX_STACK_SIZE`) and the max consensus size of st=
ack element (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional"scarce coi=
ns" pre-requirement on the quantum adversarise to succeed. Shor's algorithm=
 is only defined under theclassic ressources of computational complexity, t=
ime and space.
<br />&gt;
<br />I'm not sure I fully understand this, but even more practically, as m=
entioned in the BIP, value can simply be kept in P2WPKH outputs, ideally wi=
th a value of fewer than 50 coins per address, and when funds ever need to =
be spent, 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 mine=
rs get to see the public key before it's mined. It's not perfect, since thi=
s relies on exogenous security assumptions, which is why P2QRH is proposed.
<br />&gt;
<br />&gt; Best,Antoine
<br />&gt; [1]=C2=A0<a href=3D"https://freicoin.substack.com/p/why-im-again=
st-taproot" rel=3D"nofollow" target=3D"_blank">https://freicoin.substack.co=
m/p/why-im-against-taproot</a>
<br />&gt;
<br />=C2=A0
<br />I'm grateful you took the time to review the BIP and offer your detai=
led insights.
<br />=C2=A0
<br />[1] =E2=80=9CThe impact of hardware specifications on reaching quantu=
m advantage in the fault tolerant regime,=E2=80=9D 2022=C2=A0-=C2=A0<a href=
=3D"https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-h=
ardware-specifications-on-reaching" rel=3D"nofollow" target=3D"_blank">http=
s://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-=
specifications-on-reaching</a>
<br />[2]=C2=A0<a href=3D"https://www.youtube.com/watch?v=3DDe2IlWji8Ck" re=
l=3D"nofollow" target=3D"_blank">https://www.youtube.com/watch?v=3DDe2IlWji=
8Ck</a>
<br />[3]=C2=A0<a href=3D"https://www.youtube.com/watch?v=3Dd5aIx79OTps" re=
l=3D"nofollow" target=3D"_blank">https://www.youtube.com/watch?v=3Dd5aIx79O=
Tps</a>
<br />=C2=A0
<br />&gt;
<br />&gt;
<br />&gt; Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =
=C3=A9crit=C2=A0:
<br />&gt;
<br />&gt; &gt; Good points. I like your suggestion for a SPHINCS+, just du=
e to how mature it is in comparison to SQIsign. It's already in its third r=
ound and has several standards-compliant implementations, and it has an act=
ual specification 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 to find in the documents hosted by the SPHINCS website.
<br />&gt; &gt; <a href=3D"https://web.archive.org/web/20230711000109if_/ht=
tp://sphincs.org/data/sphincs+-round3-submission-nist.zip" rel=3D"nofollow"=
 target=3D"_blank">https://web.archive.org/web/20230711000109if_/http://sph=
incs.org/data/sphincs+-round3-submission-nist.zip</a>
<br />&gt; &gt; =C2=A0
<br />&gt; &gt; One way to handle this is to introduce this as a separate a=
ddress type than SQIsign. That won't require OP_CAT, and I do want to keep =
this soft fork limited in scope. If SQIsign does become significantly broke=
n, in this hopefully far future scenario, I might be supportive of an incre=
ase in the witness discount.
<br />&gt; &gt; =C2=A0
<br />&gt; &gt; Also, I've made some additional changes based on your feedb=
ack on X. You can review them here if you so wish:
<br />&gt; &gt; <a href=3D"https://github.com/cryptoquick/bips/pull/5/files=
?short_path=3D917a32a#diff-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b=
82d36411ed45e754" rel=3D"nofollow" target=3D"_blank">https://github.com/cry=
ptoquick/bips/pull/5/files?short_path=3D917a32a#diff-917a32a71b69bf62d7c85d=
fb13d520a0340a30a2889b015b82d36411ed45e754</a>
<br />&gt; &gt;
<br />&gt; &gt;
<br />&gt; &gt; On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre=
-Luc Dallaire-Demers wrote:
<br />&gt; &gt; &gt; SQIsign is blockchain friendly but also very new, I wo=
uld recommend adding a hash-based backup key in case an attack on SQIsign i=
s found in the future (recall that SIDH broke over the span of a weekend=C2=
=A0<a href=3D"https://eprint.iacr.org/2022/975.pdf" rel=3D"nofollow" target=
=3D"_blank">https://eprint.iacr.org/2022/975.pdf</a>).
<br />&gt; &gt; &gt; Backup keys can be added in the form of a Merkle tree =
where one branch would contain the SQIsign public key and the other the pub=
lic key of the recovery hash-based scheme. For most transactions it would o=
nly add one bit to specify the SQIsign branch.
<br />&gt; &gt; &gt; The hash-based method could be Sphincs+, which is stan=
dardized by NIST but requires adding extra code, or Lamport, which is not s=
tandardized but can be verified on-chain with OP-CAT.
<br />&gt; &gt; &gt;
<br />&gt; &gt; &gt; On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4=
 Hunter Beast wrote:
<br />&gt; &gt; &gt; &gt; The motivation for this BIP is to provide a concr=
ete proposal for adding quantum resistance to Bitcoin. We will need to pick=
 a signature algorithm, 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 substantive answer to those with concerns beyond, "quantum computer=
s may pose a threat, but we likely don't have to worry about that for a lon=
g time". Bitcoin development and activation is slow, so it's important that=
 those with low time preference start discussing this as a serious possibil=
ity 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 pr=
opose concrete solutions, even if they're early and incomplete, so that Bit=
coin developers are aware of the existence of these solutions and their pot=
ential.  This is just a rough draft and not the finished BIP. I'd like to v=
alidate the approach and hear if I should continue working on it, whether s=
erious changes are needed, or if this truly isn't a worthwhile endeavor rig=
ht now.
<br />&gt; &gt; &gt; &gt; =C2=A0
<br />&gt; &gt; &gt; &gt; The BIP can be found here:
<br />&gt; &gt; &gt; &gt; <a href=3D"https://github.com/cryptoquick/bips/bl=
ob/p2qrh/bip-p2qrh.mediawiki" rel=3D"nofollow" target=3D"_blank">https://gi=
thub.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki</a>
<br />&gt; &gt; &gt; &gt; =C2=A0
<br />&gt; &gt; &gt; &gt; Thank you for your time.
<br />&gt; &gt; &gt; &gt; =C2=A0
<br />&gt; &gt; &gt; &gt;
<br />&gt; &gt; &gt;
<br />&gt; &gt; &gt;
<br />&gt; &gt;
<br />&gt; &gt;
<br />&gt;
<br />&gt;
<br />&gt; -- You received this message because you are subscribed to a top=
ic in the Google Groups "Bitcoin Development Mailing List" group. To unsubs=
cribe from this topic, visit <a href=3D"https://groups.google.com/d/topic/b=
itcoindev/Aee8xKuIC2s/unsubscribe" rel=3D"nofollow" target=3D"_blank">https=
://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe</a>. To uns=
ubscribe from this group and all its topics, send an email to <a rel=3D"nof=
ollow">bitcoindev+...@googlegroups.com</a>. To view this discussion on the =
web visit <a href=3D"https://groups.google.com/d/msgid/bitcoindev/87b4e402-=
39d8-46b0-8269-4f81fa501627n%40googlegroups.com" rel=3D"nofollow" target=3D=
"_blank">https://groups.google.com/d/msgid/bitcoindev/87b4e402-39d8-46b0-82=
69-4f81fa501627n%40googlegroups.com</a>.
<br />
<br />-----BEGIN PGP SIGNATURE-----
<br />Version: OpenPGP.js v4.10.3
<br />Comment: <a href=3D"https://openpgpjs.org" rel=3D"nofollow" target=3D=
"_blank">https://openpgpjs.org</a>
<br />
<br />wsBcBAEBCAAGBQJmcJwuAAoJEDEPCKe+At0hjhkIAIdM7QN9hAO0z+KO7Bwe
<br />JT45XyusJmDG1gJbLZtb+SfuE1X5PFDHNTLSNliJWsOImxFCiBPnlXhYQ4B/
<br />8gST3rqplUwkdYr52E5uMxTTq9YaXTako4PNb8d7XfraIwDKXAJF+5Skf4f9
<br />bQUYMieBAFSEXCmluirQymB+hUoaze60Whd07hhpzbGSwK4DdSXltufkyCDE
<br />tJUforNWm8X25ABTSNDh3+if5V/wJuix/u8GJyMHKucaEAO01ki2oyusq2rt
<br />Xe6ysUieclusFFdQAs4PfYxhzXTf5XeAbFga/qxrVtbt7q2nUkYklqteT2pp
<br />mH/DU20HMBeGVSrISrvsmLw=3D
<br />=3D+wat
<br />-----END PGP SIGNATURE-----
<br />
<br /></blockquote></div></blockquote></div></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 on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/1b86f467-95e5-4558-98bc-b921dd29e1afn%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/1b86f467-95e5-4558-98bc-b921dd29e1afn%40googlegroups.com</a>.=
<br />

------=_Part_871339_835844614.1722965834575--

------=_Part_871338_1805467811.1722965834575--