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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <1b86f467-95e5-4558-98bc-b921dd29e1afn@googlegroups.com> References: <62fd28ab-e8b5-4cfc-b5ae-0d5a033af057n@googlegroups.com> <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com> <2cbd432f-ca19-4481-93c5-3b0f7cdea1cb@DS3018xs> <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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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 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.
Please review.
https://github.com/cryptoquick/bips/pull/9/files

On Tuesday, Augus= t 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 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
> 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
> 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
> ICO to build a quantum= computer like 10 years ago, just to remember).

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.

> 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.

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:
Then, referencing this table:
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.

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?

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.

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.

> 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.
=
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.

> 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...
> 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.

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

> 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.

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.

Thanks for your time!

On Friday, July 12, 2024 at 7:44:27=E2=80=AFPM UTC-6 Antoine Ria= rd wrote:
Hi Hunter Beast,

Apol= ogies for the delay in answer.

> 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...
=
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
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
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
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.

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.

> =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]

I have= looked on the roadmap as it's available on the IBM blog post: https://www.ibm.com/qu= antum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2033
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
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
of = litography in traditional chips manufacturing.
=C2=A0
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 nothold 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
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
ICO to build a quantum computer like 10 = years ago, just to remember).

> 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.
=C2=A0
> 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.

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.

> 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).

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.

> 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
> 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
> 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
> proposed.

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
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
spends in face of quantum a= ttacks.

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...
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.


> =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
> 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
> = why P2QRH is proposed.

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.

Best,
Antoine

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

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

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

>
> 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.
>
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.
=C2=A0
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...
>
> 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).
>
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.
>
> 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].
>
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].
>
> 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.
>
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.
=C2=A0
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.
=C2=A0
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).
>
> 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.
>
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.
>
> Best,Antoine
> [1]=C2=A0https://freicoin.substack.com/p/why-im-against-= taproot
>
=C2=A0
I'm grateful you took the time to review the BIP and offer your det= ailed insights.
=C2=A0
[1] =E2=80=9CThe impact of hardware specifications on reaching quantum = advantage in the fault tolerant regime,=E2=80=9D 2022=C2=A0-=C2=A0https://pubs.aip.org/avs/aqs/article/4/1/0138= 01/2835275/The-impact-of-hardware-specifications-on-reaching
[2]=C2=A0https://www.youtube.com/watch?v=3DDe2IlWji8Ck
[3]=C2=A0https://www.youtube.com/watch?v=3Dd5aIx79OTps
=C2=A0
>
>
> Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3= =A9crit=C2=A0:
>
> > Good points. I like your suggestion for a SPHINCS+, just due = to how 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.
> > https://web.archive.or= g/web/20230711000109if_/http://sphincs.org/data/sphincs+-round3-submission-= nist.zip
> > =C2=A0
> > 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.
> > =C2=A0
> > Also, I've made some additional changes based on your fee= dback on X. You can review them here if you so wish:
> > https://github.com/cryptoquic= k/bips/pull/5/files?short_path=3D917a32a#diff-917a32a71b69bf62d7c85dfb13d52= 0a0340a30a2889b015b82d36411ed45e754
> >
> >
> > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-L= uc Dallaire-Demers wrote:
> > > 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= =A0https://eprint.iacr.org= /2022/975.pdf).
> > > 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.
> > > 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.
> > >
> > > On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4 H= unter Beast wrote:
> > > > 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.
> > > > =C2=A0
> > > > The BIP can be found here:
> > > > https://github.= com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki
> > > > =C2=A0
> > > > Thank you for your time.
> > > > =C2=A0
> > > >
> > >
> > >
> >
> >
>
>
> -- You received this message because you are subscribed to a topic= in the Google Groups "Bitcoin Development Mailing List" group. T= o unsubscribe from this topic, visit https://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe. = To unsubscribe from this group and all its topics, send an email to bitcoindev+...@googlegroups.com. To view this discussion = on the web visit https://groups.google.com/d= /msgid/bitcoindev/87b4e402-39d8-46b0-8269-4f81fa501627n%40googlegroups.com<= /a>.

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

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

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msg= id/bitcoindev/ac28feaf-6649-4501-9b1a-1410e5baa05dn%40googlegroups.com.=
------=_Part_147025_918105580.1723698345128-- ------=_Part_147024_1588655007.1723698345128--