From mboxrd@z Thu Jan 1 00:00:00 1970
Delivery-date: Wed, 14 Aug 2024 22:25:10 -0700
Received: from mail-yb1-f190.google.com ([209.85.219.190])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBD3YNWFH7IHBBK5C622QMGQE3FJMIMY@googlegroups.com>)
id 1seSyx-00074q-Ij
for bitcoindev@gnusha.org; Wed, 14 Aug 2024 22:25:10 -0700
Received: by mail-yb1-f190.google.com with SMTP id 3f1490d57ef6-e0be7c74d79sf924178276.0
for <bitcoindev@gnusha.org>; Wed, 14 Aug 2024 22:25:07 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1723699501; x=1724304301; 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=HvxBoqFf3afTYwOPAPXl22ZQeK/aPo+5w41nGg8v5b8=;
b=xJyIycvFcJhYgzPBK8k6NVIhw52IlcXBbyC32fpxsOnDm1kfjPynPYxKzIUfBti7e0
qCkNiFkaJZDDFlZo4GwRnhramv9CkX7859kKPrxvXd6GSlMDX2jSL8gBjOXOE0AONojV
uST3tvMVpMM4PIiJ+8CfVZTByiXuc6XD5WqcL7pTs8a8roJ9N9nbWEJxgFJNTPmHXt0L
acWOAShQRLJApQ2Ee/T0jZNYxTeWS+dzESExdB2YPAUThY33pCZ7jObw6ezRng6l4v9c
WjsVSAGR8e/5u3E7jsokq4rJG55NCQ5+ZbNl3rqV5b1XdQbP9S5ucyx3146T00RYxHDY
59zg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1723699501; x=1724304301;
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=HvxBoqFf3afTYwOPAPXl22ZQeK/aPo+5w41nGg8v5b8=;
b=Ls8kBE5V7ptz4v7pE949f8vOHQ2/T1yKmet8Mc1Xr97V4/CJ/89GkkGMBJNs88EVr3
l3q5AESez74sLk6PePnWcwfjzBCy6rNoT/fwd2UPefRrrt2MMnWuEqfGZoXzLcIl37k2
5A3rCWys/01jgoviph7G8ylw9COdk0G7Cul1ybFcmGrL7RTdj6TeHgpxkxNVl8cAOoAn
72CVU1khpEleROFuGoZ9uy6tbxxmDag1x6VccH2BDtHvnG+47GOsfco/cGenMixErgeG
aejAJCrDGk9UWpkatSzXDNM3eBgQ4GBBCsc/KED/TETWMY5o+pXXaUY+O4dLOe4dacPd
SL8g==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCUkeqWXJM3N6NGaPk0nxuW9Bfya3hMZYfpXqTVhjPyyQQZactyDlNCRJatgU7hnRYg3894gTEmnK4QElqL6AX2hU7o2Lvo=
X-Gm-Message-State: AOJu0YxBNfTYe3GT7O9ggXokbhjBFzhu1SBSGotisZivVdiA31WABYmF
R/pjzqGdQrspzBZoR6hj5PSmqOnREKoYAWoVXiOVwyo5grPUMpd3
X-Google-Smtp-Source: AGHT+IHox+sbl4KVRE9mEZePqW814Rg0sfKQHymyYgNeBmgG0pqWOGcjvePs9Sazx2ROV+Ax8/y2zw==
X-Received: by 2002:a05:6902:2306:b0:e0e:4171:aee6 with SMTP id 3f1490d57ef6-e1155b85bffmr5285905276.42.1723699500827;
Wed, 14 Aug 2024 22:25:00 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6902:100b:b0:e03:64a5:8bb0 with SMTP id
3f1490d57ef6-e116beb5998ls697379276.1.-pod-prod-00-us; Wed, 14 Aug 2024
22:24:59 -0700 (PDT)
X-Received: by 2002:a25:910e:0:b0:e0b:a34d:f223 with SMTP id 3f1490d57ef6-e116cecab95mr40522276.5.1723699498683;
Wed, 14 Aug 2024 22:24:58 -0700 (PDT)
Received: by 2002:a81:ad22:0:b0:699:2980:4ef6 with SMTP id 00721157ae682-6ad3b31e44ems7b3;
Wed, 14 Aug 2024 22:05:47 -0700 (PDT)
X-Received: by 2002:a05:6902:18d:b0:e03:589b:cbe1 with SMTP id 3f1490d57ef6-e1155b67c75mr150327276.7.1723698345452;
Wed, 14 Aug 2024 22:05:45 -0700 (PDT)
Date: Wed, 14 Aug 2024 22:05:45 -0700 (PDT)
From: Hunter Beast <hunter@surmount.systems>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <ac28feaf-6649-4501-9b1a-1410e5baa05dn@googlegroups.com>
In-Reply-To: <1b86f467-95e5-4558-98bc-b921dd29e1afn@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>
<1b86f467-95e5-4558-98bc-b921dd29e1afn@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_147024_1588655007.1723698345128"
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_147024_1588655007.1723698345128
Content-Type: multipart/alternative;
boundary="----=_Part_147025_918105580.1723698345128"
------=_Part_147025_918105580.1723698345128
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I've taken Antoine's feedback to heart and added FALCON to the=20
specification, including a section that addresses the increased maintenance=
=20
burden of adding two distinct post-quantum cryptosystems.
Please review.
https://github.com/cryptoquick/bips/pull/9/files
On Tuesday, August 6, 2024 at 11:50:35=E2=80=AFAM UTC-6 Hunter Beast wrote:
> 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=20
> about talking of "super-exponential rate" as used in maaku old blog post=
=20
> 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 Quant=
um=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 CR=
QC=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, falco=
n,=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 th=
e=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#securi=
ty
> 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 i=
s=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,=20
> I've put some thought into how we can maintain the existing Bitcoin=20
> throughput with a soft fork, and I think it might be prudent to, when the=
=20
> time comes, introduce a 4x additional QuBit witness discount, maybe we ca=
ll=20
> it the quitness, which is only available to valid P2QRH signatures. This=
=20
> would preclude its abuse for things like inscriptions because the signatu=
re=20
> data would need to correspond to the key, and even if this were possible,=
=20
> it's likely to result in only a burner address. This would increase chain=
=20
> state growth from roughly 100GB/yr to possibly closer to 2-300GB, dependi=
ng=20
> on adoption. As the state of the art of SSD technology advances, this=20
> should allow plebs to run their own node on a 4TB disk for over a decade,=
=20
> even 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 transacti=
on=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 quant=
um=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 amou=
nt=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" i=
n=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 the=
n=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 i=
t=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 stud=
y=20
> by the Sussex Centre for Quantum Technologies, et. al [1]. They provide t=
wo=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 le=
ss=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 =
attacks 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=
=20
> the range of 1000 physical qubits being able to break the DLP for ECC bas=
ed=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 abo=
ut=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; the=
ir=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=
-2033
> 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 so=
lid
> state issues in laying out in hardware the Heron processor architecture.=
=20
> As a point of thinking, it took like 2 decades to advance on the state of=
=20
> 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 n=
ot
> 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 i=
s=20
> a historical anecdote among bitcoin OG circles about Vitalik trying to do=
an
> 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 dependin=
g=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 chan=
ge=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'v=
e=20
> only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge t=
he=20
> readiness levels between those two are presently worlds apart.
>
> 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, falco=
n,=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.
>
> > Also, do you think it's of any concern to use HASH160 instead of HASH25=
6=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 pape=
r=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=20
> specifications on reaching quantum advantage...") is analyzing the=20
> performance of quantum 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" i=
n=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=20
> should put the burden on the quantum attacker to have enough bitcoin amou=
nt=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 fund=
s=20
> ever need to be spent, the transaction is signed and submitted out of ban=
d=20
> to a trusted mining pool, ideally
> > one that does KYC, so it's known which individual > miners get to see=
=20
> the 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 the=
n=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: 1ad818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb27f1f0dc0b3=
0
> 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 tal=
k=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=20
> section about how an attack might take place practically, and the potenti=
al=20
> urgency 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, almos=
t=20
> like a Chicago Pile moment, proving something in practice that was=20
> previously only thought theoretically possible for the past 3 decades. An=
d=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'sa=
n=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 seei=
ng=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=20
> those encode the entire public key for everyone to see for all time. Thus=
,=20
> early 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; the=
ir=20
> keynote from December of last year [2], and their roadmap update from jus=
t=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) whi=
ch=20
> has been through the 3 rounds of NIST cryptanalysis. Apart of the signatu=
re=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 dependin=
g=20
> on how much time there is. According to the BIP, FALCON signatures are ~1=
0x=20
> larger than Schnorr signatures, so this will of course make the transacti=
on=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 t=
he=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=
=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).=20
> >=20
> > Lastly, there is a practical defensive technique that can be implemente=
d=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 thi=
nk=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 consensu=
s=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 wh=
y=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 ad=
vantage=20
> in the fault tolerant regime,=E2=80=9D 2022 -=20
> https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-har=
dware-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=A9cr=
it :=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 an=
d=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/sph=
incs+-round3-submission-nist.zip=20
> > > =20
> > > One way to handle this is to introduce this as a separate address typ=
e=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 th=
is=20
> hopefully far future scenario, I might be supportive of an increase in th=
e=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#dif=
f-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82d36411ed45e754=20
> > >=20
> > >=20
> > > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-Luc=20
> Dallaire-Demers 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 t=
he=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 o=
ne=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 standardize=
d=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=
wrote:=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 thes=
e=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.mediawik=
i=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=
=20
> the Google Groups "Bitcoin Development Mailing List" group. To unsubscrib=
e=20
> from 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-4f81=
fa501627n%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/ac28feaf-6649-4501-9b1a-1410e5baa05dn%40googlegroups.com.
------=_Part_147025_918105580.1723698345128
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
I've taken Antoine's feedback to heart and added FALCON to the specificatio=
n, including a section that addresses the increased maintenance burden of a=
dding two distinct post-quantum cryptosystems.<div>Please review.</div><div=
>https://github.com/cryptoquick/bips/pull/9/files<br /><br /></div><div cla=
ss=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">On Tuesday, Augus=
t 6, 2024 at 11:50:35=E2=80=AFAM UTC-6 Hunter Beast wrote:<br/></div><block=
quote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px =
solid rgb(204, 204, 204); padding-left: 1ex;">That's alright, Antoine, =
it's been a busy month for me too.<div><br></div><div>> So I think i=
t's good to stay cool minded and I think my observation about talking o=
f "super-exponential rate" as used in maaku old blog post does no=
t<br>> hold a lot of rigor to describe the advances in the field of quan=
tum computing. Note, also how IMB is a commercial entity that can have a lo=
t of interests<br>> in "pumping" the state of "quantum co=
mputing" to gather fundings (there is a historical anecdote among bitc=
oin OG circles about Vitalik trying to do an<br>> ICO to build a quantum=
computer like 10 years ago, just to remember).</div><div><br></div><div>We=
ll, it's also important to remember that for every qubit added, it doub=
les the power of the system. A 2,000 qubit cryptographically-relevant quant=
um computer (CRQC) is exponentially faster than a 1,000 qubit one. There=
9;s also the capability for cross-links for multiple chips to communicate w=
ith each other, which IBM is also researching. The IBM Quantum System Two c=
an be upgraded to support 16,000 qubits according to their marketing. Also =
consider that 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 ne=
cessary so long as the program is run enough times. It will take much longe=
r, of course.</div><div><br></div><div>> I think FALCON is what has the =
smallest pubkey + sig size for hash-and-sign lattice-based schemes. So I th=
ink it's worth reworking the BIP to see what has the smallest generatio=
n / validation time and pubkey + size space for the main post-quantum schem=
e. At least for dilthium, falcon, sphincs+ and SQISign. For an hypothetical=
witness discount, a v2 P2QRH could be always be moved in a very template a=
nnex tag / field.</div><div><br></div><div>I've decided in one of my mo=
re recent updates to the BIP to default to the highest level of NIST securi=
ty, NIST V, which provides 256 bits of security. You can see my rationale f=
or that in this PR:</div><div><a href=3D"https://github.com/cryptoquick/bip=
s/pull/7/files" target=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"=
https://www.google.com/url?hl=3Den&q=3Dhttps://github.com/cryptoquick/b=
ips/pull/7/files&source=3Dgmail&ust=3D1723784448237000&usg=3DAO=
vVaw3TJXTTXTNEojxsKtZDqS0y">https://github.com/cryptoquick/bips/pull/7/file=
s</a></div><div>Then, referencing this table:</div><div><a href=3D"https://=
github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki#security" target=
=3D"_blank" rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com=
/url?hl=3Den&q=3Dhttps://github.com/cryptoquick/bips/blob/p2qrh/bip-p2q=
rh.mediawiki%23security&source=3Dgmail&ust=3D1723784448237000&u=
sg=3DAOvVaw1BhegPvbzao2Z-8BQgFvkE">https://github.com/cryptoquick/bips/blob=
/p2qrh/bip-p2qrh.mediawiki#security</a><br></div><div>As such, you'll s=
ee FALCON is roughly 4x larger than SQIsign signatures. Although supersingu=
lar elliptic curve quaternion isogeny-based algorithms are newer and more e=
xperimental than lattice-based cryptography, I think the benefits outweigh =
the risks, especially when transaction throughput is a principal concern.</=
div><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 =
might be accomplished?</div><div><br></div><div>Although it's too early=
to talk about activation of a QuBit soft fork, I've put some thought i=
nto how we can maintain the existing Bitcoin throughput with a soft fork, a=
nd I think it might be prudent to, when the time comes, introduce a 4x addi=
tional QuBit witness discount, maybe we call it the quitness, which is only=
available to valid P2QRH signatures. This would preclude its abuse for thi=
ngs like inscriptions because the signature data would need to correspond t=
o the key, and even if this were possible, it's likely to result in onl=
y a burner address. This would increase chain state growth from roughly 100=
GB/yr to possibly closer to 2-300GB, depending on adoption. As the state of=
the art of SSD technology advances, this should allow plebs to run their o=
wn node on a 4TB disk for over a decade, even including existing chain size=
of ~600GB.</div><div><br></div><div>If we were to use the same approach fo=
r FALCON signatures, a 16x discount would be needed, and I think that's=
far too much for the community to accept. As for pub key size and verifica=
tion time, these are secondary considerations if the primary constraint is =
maintaining present transaction throughput. That's what makes SQIsign s=
o promising.</div><div><br></div><div>> See literature on quantum attack=
s on bitcoin in the reference of the paper you quote ("The impact of h=
ardware specifications on reaching quantum advantage in the fault tolerant =
regime") for a discussion on Grover's search algorithm.</div><div>=
<br></div><div>The Impact paper seems to dismiss Grover's algorithm, bu=
t I think it's important to err on the size of caution and instead use =
a 32-byte double SHA-2 (HASH256) for additional security in the P2QRH outpu=
t.</div><div><br></div><div>> Namely you can introduce an artifical &quo=
t;witness-stack size scale ladder" in pseudo-bitcoin script: OP_SIZE &=
lt;1000> OP_EQUALVERIFY OP_DROP ...checksig...</div><div>> I have not=
verified it works well on bitcoin core though this script should put the b=
urden on the quantum attacker to have enough bitcoin amount available to bu=
rn 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 yo=
ur coin scarcity comment related to what I call "satoshi's shield&=
quot; in the BIP?</div><div><br></div><div>> The technical issue if you =
implement KYC for a mining pool you're increasing your DoS surface and =
this could be exploited by competing miners. A more reasonable security mod=
el can be to have miner coinbase pubkeys being used to commit to the "=
seen-in-mempool" spends and from then build "hand wawy" frau=
d proofs that a miner is quantum attacking you're P2WSH spends at pubke=
y 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 proo=
fs, but they could at least prove that a bad actor is present. Ideally both=
approaches are combined for maximum security and accountability.</div><div=
><br></div><div>Thanks for your time!</div><div><div><br></div><div><div di=
r=3D"auto">On Friday, July 12, 2024 at 7:44:27=E2=80=AFPM UTC-6 Antoine Ria=
rd wrote:<br></div><blockquote style=3D"margin:0px 0px 0px 0.8ex;border-lef=
t:1px solid rgb(204,204,204);padding-left:1ex">Hi Hunter Beast,<br><br>Apol=
ogies for the delay in answer.<br><br>> I was thinking of focusing on th=
e IBM Quantum System Two, mention how it can be scaled, and that although i=
t might be quite limited, if running Shor's variant for a > sufficie=
nt 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 o=
n the estimate > provided in a study by the Sussex Centre for Quantum Te=
chnologies, et. al [1]. They provide two figures, 317M qubits to decrypt in=
one hour, 13M qubits to decrypt in one > day. It would seem it scales r=
oughly linearly, and so extrapolating it further, 36,000 qubits would be ne=
eded to decrypt an address within one year. However, the IBM Heron > QPU=
turned out to have a gate time 100x less than was estimated in 2022, and s=
o 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 decrypt a single address within=
a year. That might sound like a lot, but > being able to accomplish tha=
t at all would be significant, almost like a Chicago Pile moment, proving s=
omething in practice that was previously only thought theoretically > po=
ssible for the past 3 decades. And it's only downhill from there...<br>=
<br>Briefly surveying the paper "The impact of hardware specifications=
on reaching quantum advantage in the fault tolerant regime", I think =
it's a reasonble framework to evaluate<br>the practical efficiency of q=
uantum attacks on bitcoin, it's self consistent and there is a critical=
approach referencing the usual litterature on quantum attacks on bitcoin. =
Just<br>note the caveat, one can find in usual quantum complexity litteratu=
re, "particularly in regard to end-to-end physical resource estimation=
. There are many other error correction<br>techniques available, and the be=
st choice will likely depend on the underlying architecture's character=
istics, such as the available physical qubit=E2=80=93qubit connectivity&quo=
t; (verbatim). Namely, evaluating quantum attacks is very dependent on the =
concrete physical architecture underpinning it.<br><br>All that said, I agr=
ee with you that if you see a quantum computer with the range of 1000 physi=
cal qubits being able to break the DLP for ECC based encryption like secp25=
6k1, even if it takes a year it will be a Chicago Pile moment, or whatever =
comparative experiments which were happening about chain of nuclear reactio=
ns in 30s / 40s.<br><br>> =C2=A0I think it's time to revisit these d=
iscussions 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><br>I have=
looked on the roadmap as it's available on the IBM blog post: <a href=
=3D"https://www.ibm.com/quantum/blog/quantum-roadmap-2033#mark-roadmap-out-=
to-2033" rel=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https:/=
/www.google.com/url?hl=3Den&q=3Dhttps://www.ibm.com/quantum/blog/quantu=
m-roadmap-2033%23mark-roadmap-out-to-2033&source=3Dgmail&ust=3D1723=
784448237000&usg=3DAOvVaw2XePFcFO5jr0z2TyPoSBr9">https://www.ibm.com/qu=
antum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2033</a><br>They give o=
nly a target of 2000 logical qubit to be reach in 2033...which is surprisin=
gly not that strong...And one expect they might hit likely solid<br>state i=
ssues in laying out in hardware the Heron processor architecture. As a poin=
t of thinking, it took like 2 decades to advance on the state of art<br>of =
litography in traditional chips manufacturing.<br>=C2=A0<br>So I think it&#=
39;s good to stay cool minded and I think my observation about talking of &=
quot;super-exponential rate" as used in maaku old blog post does not<b=
r>hold a lot of rigor to describe the advances in the field of quantum comp=
uting. Note, also how IMB is a commercial entity that can have a lot of int=
erests<br>in "pumping" the state of "quantum computing"=
to gather fundings (there is a historical anecdote among bitcoin OG circle=
s about Vitalik trying to do an<br>ICO to build a quantum computer like 10 =
years ago, just to remember).<br><br>> I'm supportive of this consid=
eration. FALCON might be a good substitute, and 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 larger t> han Schnorr =
signatures, so this will of course make the transaction more expensive, but=
we also > must remember, these signatures will be going into the witnes=
s, which already receives a 4x discount. Perhaps the discount could be incr=
> eased further someday to fit > more transactions into blocks, but t=
his will also likely result in more inscriptions filling unused space also,=
which permanently increases the burden of running an archive > node. Du=
e to the controversy s> uch 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 incre=
ase in P2QRH transaction size.<br>=C2=A0<br>> Do you think it's wort=
h reworking the BIP to use FALCON signatures? I've only done a deep div=
e into SQIsign and SPHINCS+, and I will acknowledge the readiness levels be=
tween those two are presently worlds apart.<br><br>I think FALCON is what h=
as 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 ge=
neration / validation time and pubkey + size space for the main post-quantu=
m scheme. At least for dilthium, falcon, sphincs+ and SQISign. For an hypot=
hetical witness discount, a v2 P2QRH could be always be moved in a very tem=
plate annex tag / field.<br><br>> Also, do you think it's of any con=
cern 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 ha=
sh (MD160 of SHA-256).<br><br>See literature on quantum attacks on bitcoin =
in the reference of the paper you quote ("The impact of hardware speci=
fications on reaching quantum advantage in the fault tolerant regime")=
for a discussion on Grover's search algorithm.<br><br>> I'm not=
sure I fully understand this, but even more practically, as mentioned in t=
he BIP, value can simply be kept in P2WPKH outputs, ideally with a value of=
fewer than 50<div>> coins per address, and when funds ever need to be s=
pent, the> =C2=A0transaction is signed and submitted out of band to a tr=
usted mining pool, ideally one that does KYC, so it's</div><div>> kn=
own which individual miners get to see the public key before it's mined=
. It's not perfect, since this relies on exogenou> s security assump=
tions, which is why P2QRH is</div><div>> proposed.<br><br>Again, the pap=
er you're referencing ("The impact of hardware specifications on r=
eaching quantum advantage...") 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 defense of address<br>spends in face of quantum a=
ttacks.<br><br>Namely you can introduce an artifical "witness-stack si=
ze scale ladder" in pseudo-bitcoin script: OP_SIZE <1000> OP_EQU=
ALVERIFY OP_DROP ...checksig...<br>I have not verified it works well on bit=
coin core though this script should put the burden on the quantum attacker =
to have enough bitcoin amount available to burn in on-chain fees in witness=
size to break a P2WPKH.</div><div><br><br>> =C2=A0ideally with a value =
of fewer than 50 coins per address, and when funds ever need to be spent, t=
he transaction is signed and submitted out of band to a trusted mining pool=
, ideally<br>> one that does KYC, so it's known which individual >=
; miners get to see the public key before it's mined. It's not perf=
ect, since this relies on exogenous security assumptions, which is<br>> =
why P2QRH is proposed.<br><br></div><div>The technical issue if you impleme=
nt KYC for a mining pool you're increasing your DoS surface and this co=
uld be exploited by competing miners. A more reasonable security 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 proof=
s that a miner is quantum attacking you're P2WSH spends at pubkey revea=
l time during transaction relay.<br><br>Best,<br>Antoine</div><div><br></di=
v><div>ots hash:=C2=A01ad818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb2=
7f1f0dc0b30</div><div><div dir=3D"auto">Le lundi 17 juin 2024 =C3=A0 23:25:=
25 UTC+1, hunter a =C3=A9crit=C2=A0:<br></div><blockquote style=3D"margin:0=
px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>-----BEGIN PGP SIGNED MESSAGE-----
<br>Hash: SHA256
<br>
<br>On 2024-06-16 19:31, Antoine Riard <<a rel=3D"nofollow">antoin...@gm=
ail.com</a>> wrote:
<br>
<br>>
<br>> Hi Hunter Beast,I think any post-quantum upgrade signature algorit=
hm upgrade proposal would grandly benefit to haveShor's based practical=
attacks far more defined in the Bitcoin context. As soon you start to talk=
aboutquantum computers there is no such thing as a "quantum computer&=
quot; though a wide array of architecturesbased on a range of technologies =
to encode qubits on nanoscale physical properties.
<br>>
<br>Good point. I can write a section in the BIP Motivation or Security sec=
tion about how an attack might take place practically, and the potential ur=
gency of such an attack.
<br>=C2=A0
<br>I was thinking of focusing on the IBM Quantum System Two, mention how i=
t can be scaled, and that although it might be quite limited, if running Sh=
or's variant for a sufficient amount of time, above a certain minimum t=
hreshold 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 Su=
ssex Centre for Quantum Technologies, et. al [1]. They provide two figures,=
317M qubits to decrypt in one hour, 13M qubits to decrypt in one day. It w=
ould seem it scales roughly linearly, and so extrapolating it further, 36,0=
00 qubits would be needed to decrypt an address within one year. However, t=
he IBM Heron QPU=C2=A0turned out to have a gate time 100x less than was est=
imated in 2022, and so it might be possible to make do with even fewer qubi=
ts still within that timeframe. With only 360 qubits, barring algorithmic o=
verhead such as for circuit memory, it might be possible to=C2=A0decrypt a =
single address within a year. That might sound like a lot, but being able t=
o=C2=A0accomplish that=C2=A0at all would be significant, almost like a Chic=
ago Pile moment, proving something in practice that was previously only tho=
ught theoretically possible for the past 3 decades. And it's only downh=
ill from there...
<br>>
<br>> This is not certain that any Shor's algorithm variant works sm=
oothly independently of the quantum computerarchitecture considered (e.g ga=
te frequency, gate infidelity, cooling energy consumption) and I think it&#=
39;san interesting open game-theory problem if you can concentrate a suffic=
iant amount of energy before anycoin owner moves them in consequence (e.g s=
eeing a quantum break in the mempool and reacting with a counter-spend).
<br>>
<br>It should be noted that P2PK keys still hold millions of bitcoin, and t=
hose encode the entire public key for everyone to see for all time. Thus, e=
arly QC attacks won't need to consider the=C2=A0complexities of the mem=
pool.
<br>>
<br>> In my opinion, one of the last time the subject was addressed on t=
he mailing list, the description of the state of the quantum computer field=
was not realistic and get into risk characterization hyperbole talking abo=
ut "super-exponential rate" (when indeed there is no empirical re=
alization=C2=A0that distinct theoretical advance on quantum capabilities=C2=
=A0can be combined with each other) [1].
<br>>
<br>I think it's time to revisit these discussions given IBM's prog=
ress. They've published a two videos in particular that are worth watch=
ing; their keynote from December of last year [2], and their roadmap update=
from just last month [3].
<br>>
<br>> 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 s=
ignature size,which sounds to be smaller, in a network of full-nodes any PQ=
signature algorithm should have reasonable verificationperformances.
<br>>
<br>I'm supportive of this consideration. FALCON might be a good substi=
tute, and maybe it can be upgraded to HAWK for even better performance depe=
nding on how much time there is. According to the BIP, FALCON signatures ar=
e ~10x larger than Schnorr signatures, so this will of course make the tran=
saction more expensive, but we also must remember, these signatures will be=
going into the witness, which already receives a 4x discount. Perhaps the =
discount could be increased further someday to fit more transactions into b=
locks, but this will also likely result in more inscriptions filling unused=
space also, which permanently increases the burden of running an archive n=
ode. Due to the controversy such a change could bring, I would rather any i=
ncreases in the witness discount be excluded from future activation discuss=
ions, so as to be considered separately, even if it pertains to an increase=
in 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 ackno=
wledge 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 HA=
SH256 in the output script? I think it's fine for a cryptographic commi=
tment since it's simply a hash of a hash (MD160 of SHA-256).
<br>>
<br>> Lastly, there is a practical defensive technique that can be imple=
mented today by coin owners to protect in face ofhyptothetical quantum adve=
rsaries. Namely setting spending scripts to request an artificially inflate=
d witness stack,as the cost has to be burden by the spender. I think one ca=
n easily 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 si=
ze of the script stack(`MAX_STACK_SIZE`) and the max consensus size of stac=
k element (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional"scarce =
coins" pre-requirement on the quantum adversarise to succeed. Shor'=
;s algorithm is only defined under theclassic ressources of computational c=
omplexity, time and space.
<br>>
<br>I'm not sure 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 fewer than 50 coins per address, and when funds ever need t=
o be spent, the transaction is signed and submitted out of band to a truste=
d mining pool, ideally one that does KYC, so it's known which individua=
l miners get to see the public key before it's mined. It's not perf=
ect, since this relies on exogenous security assumptions, which is why P2QR=
H is proposed.
<br>>
<br>> Best,Antoine
<br>> [1]=C2=A0<a href=3D"https://freicoin.substack.com/p/why-im-against=
-taproot" rel=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https:=
//www.google.com/url?hl=3Den&q=3Dhttps://freicoin.substack.com/p/why-im=
-against-taproot&source=3Dgmail&ust=3D1723784448237000&usg=3DAO=
vVaw3xfPaBI-3gkPq49QJ98MWl">https://freicoin.substack.com/p/why-im-against-=
taproot</a>
<br>>
<br>=C2=A0
<br>I'm grateful you took the time to review the BIP and offer your det=
ailed insights.
<br>=C2=A0
<br>[1] =E2=80=9CThe impact of hardware specifications on reaching quantum =
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" data=
-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3Dhttps://pubs=
.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-specific=
ations-on-reaching&source=3Dgmail&ust=3D1723784448238000&usg=3D=
AOvVaw2-ANDMo5BObp63Ez3IVoQW">https://pubs.aip.org/avs/aqs/article/4/1/0138=
01/2835275/The-impact-of-hardware-specifications-on-reaching</a>
<br>[2]=C2=A0<a href=3D"https://www.youtube.com/watch?v=3DDe2IlWji8Ck" rel=
=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https://www.google.=
com/url?hl=3Den&q=3Dhttps://www.youtube.com/watch?v%3DDe2IlWji8Ck&s=
ource=3Dgmail&ust=3D1723784448238000&usg=3DAOvVaw2M97ubyUrPGDNyqY_K=
riDE">https://www.youtube.com/watch?v=3DDe2IlWji8Ck</a>
<br>[3]=C2=A0<a href=3D"https://www.youtube.com/watch?v=3Dd5aIx79OTps" rel=
=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"https://www.google.=
com/url?hl=3Den&q=3Dhttps://www.youtube.com/watch?v%3Dd5aIx79OTps&s=
ource=3Dgmail&ust=3D1723784448238000&usg=3DAOvVaw2Ch-tXx3oN3cuiFXgB=
ss1D">https://www.youtube.com/watch?v=3Dd5aIx79OTps</a>
<br>=C2=A0
<br>>
<br>>
<br>> Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=
=A9crit=C2=A0:
<br>>
<br>> > Good points. I like your suggestion for a SPHINCS+, just due =
to how mature it is in comparison to SQIsign. It's already in its third=
round and has several standards-compliant implementations, and it has an a=
ctual specification rather than just a research paper. One thing to conside=
r is that NIST-I round 3 signatures are 982 bytes in size, according to wha=
t I was able to find in the documents hosted by the SPHINCS website.
<br>> > <a href=3D"https://web.archive.org/web/20230711000109if_/http=
://sphincs.org/data/sphincs+-round3-submission-nist.zip" rel=3D"nofollow" t=
arget=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&q=3Dhttps://web.archive.org/web/20230711000109if_/http://sphincs.org/d=
ata/sphincs%2B-round3-submission-nist.zip&source=3Dgmail&ust=3D1723=
784448238000&usg=3DAOvVaw1dSnU51zH19R2947BTxLSD">https://web.archive.or=
g/web/20230711000109if_/http://sphincs.org/data/sphincs+-round3-submission-=
nist.zip</a>
<br>> > =C2=A0
<br>> > One way to handle this is to introduce this as a separate add=
ress type than SQIsign. That won't require OP_CAT, and I do want to kee=
p this soft fork limited in scope. If SQIsign does become significantly bro=
ken, in this hopefully far future scenario, I might be supportive of an inc=
rease in the witness discount.
<br>> > =C2=A0
<br>> > Also, I've made some additional changes based on your fee=
dback on X. You can review them here if you so wish:
<br>> > <a href=3D"https://github.com/cryptoquick/bips/pull/5/files?s=
hort_path=3D917a32a#diff-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82=
d36411ed45e754" rel=3D"nofollow" target=3D"_blank" data-saferedirecturl=3D"=
https://www.google.com/url?hl=3Den&q=3Dhttps://github.com/cryptoquick/b=
ips/pull/5/files?short_path%3D917a32a%23diff-917a32a71b69bf62d7c85dfb13d520=
a0340a30a2889b015b82d36411ed45e754&source=3Dgmail&ust=3D17237844482=
38000&usg=3DAOvVaw3vaFu9P2g4gNAg4Avi9fOd">https://github.com/cryptoquic=
k/bips/pull/5/files?short_path=3D917a32a#diff-917a32a71b69bf62d7c85dfb13d52=
0a0340a30a2889b015b82d36411ed45e754</a>
<br>> >
<br>> >
<br>> > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-L=
uc Dallaire-Demers wrote:
<br>> > > SQIsign is blockchain friendly but also very new, I woul=
d recommend adding 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=
=A0<a href=3D"https://eprint.iacr.org/2022/975.pdf" rel=3D"nofollow" target=
=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&=
q=3Dhttps://eprint.iacr.org/2022/975.pdf&source=3Dgmail&ust=3D17237=
84448238000&usg=3DAOvVaw206Q3qIeCaGCHzKaBukj0m">https://eprint.iacr.org=
/2022/975.pdf</a>).
<br>> > > Backup keys can be added in the form of a Merkle tree wh=
ere one branch would contain the SQIsign public key and the other the publi=
c key of the recovery hash-based scheme. For most transactions it would onl=
y add one bit to specify the SQIsign branch.
<br>> > > The hash-based method could be Sphincs+, which is standa=
rdized by NIST but requires adding extra code, or Lamport, which is not sta=
ndardized but can be verified on-chain with OP-CAT.
<br>> > >
<br>> > > On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4 H=
unter Beast wrote:
<br>> > > > The motivation for this BIP is to provide a concret=
e 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 e=
mergency. There will be time to adopt it. Importantly, this first step is a=
more substantive answer to those with concerns beyond, "quantum compu=
ters may pose a threat, but we likely don't have to worry about that fo=
r a long time". Bitcoin development and activation is slow, so it'=
s important that those with low time preference start discussing this as a =
serious possibility sooner rather than later. This is meant to be the firs=
t in a series of BIPs regarding a hypothetical "QuBit" soft fork.=
The BIP is intended to propose concrete solutions, even if they're ear=
ly and incomplete, so that Bitcoin developers are aware of the existence of=
these solutions and their potential. This is just a rough draft and not t=
he finished BIP. I'd like to validate the approach and hear if I should=
continue working on it, whether serious changes are needed, or if this tru=
ly isn't a worthwhile endeavor right now.
<br>> > > > =C2=A0
<br>> > > > The BIP can be found here:
<br>> > > > <a href=3D"https://github.com/cryptoquick/bips/blob=
/p2qrh/bip-p2qrh.mediawiki" rel=3D"nofollow" target=3D"_blank" data-safered=
irecturl=3D"https://www.google.com/url?hl=3Den&q=3Dhttps://github.com/c=
ryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki&source=3Dgmail&ust=
=3D1723784448238000&usg=3DAOvVaw1XIrMxoXso5rmnEQe4coP1">https://github.=
com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki</a>
<br>> > > > =C2=A0
<br>> > > > Thank you for your time.
<br>> > > > =C2=A0
<br>> > > >
<br>> > >
<br>> > >
<br>> >
<br>> >
<br>>
<br>>
<br>> -- You received this message because you are subscribed to a topic=
in the Google Groups "Bitcoin Development Mailing List" group. T=
o unsubscribe from this topic, visit <a href=3D"https://groups.google.com/d=
/topic/bitcoindev/Aee8xKuIC2s/unsubscribe" rel=3D"nofollow" target=3D"_blan=
k" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3Dhttps=
://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe&source=
=3Dgmail&ust=3D1723784448238000&usg=3DAOvVaw1JNfzM3u7ZOpfYpavBjii3"=
>https://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe</a>. =
To unsubscribe from this group and all its topics, send an email to <a rel=
=3D"nofollow">bitcoindev+...@googlegroups.com</a>. To view this discussion =
on the web visit <a href=3D"https://groups.google.com/d/msgid/bitcoindev/87=
b4e402-39d8-46b0-8269-4f81fa501627n%40googlegroups.com" rel=3D"nofollow" ta=
rget=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&=
amp;q=3Dhttps://groups.google.com/d/msgid/bitcoindev/87b4e402-39d8-46b0-826=
9-4f81fa501627n%2540googlegroups.com&source=3Dgmail&ust=3D172378444=
8238000&usg=3DAOvVaw1midwGtk-zEeU9aCYJsQ96">https://groups.google.com/d=
/msgid/bitcoindev/87b4e402-39d8-46b0-8269-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" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3Dh=
ttps://openpgpjs.org&source=3Dgmail&ust=3D1723784448238000&usg=
=3DAOvVaw0hxd3_vC9lpb4RrCAX6nmP">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></blockquote></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" 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/ac28feaf-6649-4501-9b1a-1410e5baa05dn%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/ac28feaf-6649-4501-9b1a-1410e5baa05dn%40googlegroups.com</a>.=
<br />
------=_Part_147025_918105580.1723698345128--
------=_Part_147024_1588655007.1723698345128--