From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Fri, 12 Jul 2024 18:44:36 -0700 Received: from mail-yb1-f183.google.com ([209.85.219.183]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sSRoQ-00010H-PU for bitcoindev@gnusha.org; Fri, 12 Jul 2024 18:44:36 -0700 Received: by mail-yb1-f183.google.com with SMTP id 3f1490d57ef6-e03a59172dbsf4275328276.3 for ; Fri, 12 Jul 2024 18:44:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1720835067; x=1721439867; 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=EmDsrXP4v9cpCFupBuBiY780M8VNv3o3VvWQ/BZlFuM=; b=fGNcQNd1/iw9mDBw1P7mxOKP+/Spjn7NvR1WLlq52e1ZgQQwud0XZt9b/qtr+2Z0wz ZxknRhY6AoZCMIKrjDzal0QR+UmgAciuskvPb19By0gTzIjjRa0+EgUYTx4z3G/IknAe I++V4TqjJ/Ss4d4conMGeOZUIZDf+iO1FGTecgmQerf29sDMRgYlji6dL7npAaqVNOLd fOd6D7QHpDDAbjm4Dfmu25ZYVoDPht2bN/eJv9DEeyiuk5NHDq/46YmhVfUP0VvXb7oP vXOOwal/JNGiHDxevARjWcXOdgci3qdxx0d+vNd3RCrY12gZ30JRhcWGeS0DBHW3bsnO Y1cA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1720835067; x=1721439867; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=EmDsrXP4v9cpCFupBuBiY780M8VNv3o3VvWQ/BZlFuM=; b=NG/DFOXyCgT3aa7mx3N45ipUzWRJsi8pZLSz1ypUOItmXjdKD375m1y0w2SUss0r20 hKJETQ3WBdLisgAc4WObLya0zEYFCt59h+OExJ45EtxngY6h4zEdxly4R53z5u6cweGn MwhLxuu743ccgYDzKPAki/1GmQjaG2s3c3r7HTs4DfScvL1bYnY4bFOa0xOjmf9A2cG/ o+pHBtNeqYBkfzRGlMWU1i2FceKRx8zGZfj5Sz8uOGkpWFLuiA7sKWKr4P9ME9iza7Hp A+yWmcJYntDcKx7m6JWR1JzEIfeZDtQR9dRFEP3kGFFY9l3JKThBC/eeo1Dg/e3UHomn tMSQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1720835067; x=1721439867; 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=EmDsrXP4v9cpCFupBuBiY780M8VNv3o3VvWQ/BZlFuM=; b=msGCWwUz+P+CapwLRjyG6AEi1tXql5ZDhjIUDUpcIe7TctEDBvodzEeSataDYRLHqP vb6ya+szHdeTtdgmtDCLoO65l1hsnvp88XvlyPIH9wNNohsCCrllC0CzI/DHs6B2KIge UorIbdmyzeNGgXsjkSDmX0hr5Jsl4kvOkkCudOu2E0fKO6qrJN79/miqC4x66Hrg0U/A VAOFGJ0G7hN3JvSDaBD6jq4FdR/2GQ8QNJ9N7tT8L1rksokXYcU8T4EoASFduP1Dj5Cp Qq4NUhJ2OO+UiNwgm9PQ2FX3/SXYQweqFA2Vo6y7POIOhVEwyJAUljUdKS8pwjpwV1LJ 039A== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCXGZ0yIjPdHeWfJCEopCXLNeO6yU+opIwAkQpQTaP2IFo4oxdrS2X+JhdBI2UIAlA9R+k5wL4AxKH85dnp5HYvtFKgpuaw= X-Gm-Message-State: AOJu0YzYILZPbhOVO9FVH74W+RDqcJgNFCoadF1wTZdBtu3j0DfinD+s cFg2CXig6yRXFgv5GnjH5sFeU9NaNDuihIyqAgbt+PHZ7fKyiW5P X-Google-Smtp-Source: AGHT+IFVniQva7Cg6o3DMkKFyPbK7xTyxSmSGS6MjjHgHj+BxGOh7n5UOrkh/RjllM+jL37sRZEadg== X-Received: by 2002:a25:aca0:0:b0:e03:6445:8ce with SMTP id 3f1490d57ef6-e041b11d23fmr13902587276.44.1720835067224; Fri, 12 Jul 2024 18:44:27 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:18d2:b0:df4:e17a:8653 with SMTP id 3f1490d57ef6-e0579035fd5ls3874609276.1.-pod-prod-08-us; Fri, 12 Jul 2024 18:44:25 -0700 (PDT) X-Received: by 2002:a05:6902:e01:b0:e05:6026:f741 with SMTP id 3f1490d57ef6-e056026f8aemr393401276.2.1720835065599; Fri, 12 Jul 2024 18:44:25 -0700 (PDT) Received: by 2002:a05:690c:3202:b0:63b:c3b0:e1c with SMTP id 00721157ae682-65f73f2fa06ms7b3; Fri, 12 Jul 2024 18:34:21 -0700 (PDT) X-Received: by 2002:a05:6902:2b8f:b0:e05:62b5:e70c with SMTP id 3f1490d57ef6-e0562b5f941mr712199276.0.1720834459971; Fri, 12 Jul 2024 18:34:19 -0700 (PDT) Date: Fri, 12 Jul 2024 18:34:19 -0700 (PDT) From: Antoine Riard To: Bitcoin Development Mailing List Message-Id: In-Reply-To: <2cbd432f-ca19-4481-93c5-3b0f7cdea1cb@DS3018xs> References: <62fd28ab-e8b5-4cfc-b5ae-0d5a033af057n@googlegroups.com> <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com> <2cbd432f-ca19-4481-93c5-3b0f7cdea1cb@DS3018xs> Subject: Re: [bitcoindev] Re: Proposing a P2QRH BIP towards a quantum resistant soft fork MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_438322_752256595.1720834459750" X-Original-Sender: antoine.riard@gmail.com 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.5 (/) ------=_Part_438322_752256595.1720834459750 Content-Type: multipart/alternative; boundary="----=_Part_438323_1854552589.1720834459750" ------=_Part_438323_1854552589.1720834459750 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Hunter Beast, Apologies for the delay in answer. > I was thinking of focusing on the IBM Quantum System Two, mention how it= =20 can be scaled, and that although it might be quite limited, if running=20 Shor's variant for a > sufficient amount of time, above a certain minimum= =20 threshold of qubits, it might be capable of decrypting the key to an=20 address within one year. I base this on the estimate > provided in a study= =20 by the Sussex Centre for Quantum Technologies, et. al [1]. They provide two= =20 figures, 317M qubits to decrypt in one hour, 13M qubits to decrypt in one >= =20 day. It would seem it scales roughly linearly, and so extrapolating it=20 further, 36,000 qubits would be needed to decrypt an address within one=20 year. However, the IBM Heron > QPU turned out to have a gate time 100x less= =20 than was estimated in 2022, and so it might be possible to make do with=20 even fewer qubits still within that timeframe. With > only 360 qubits,=20 barring algorithmic overhead such as for circuit memory, it might be=20 possible to decrypt a single address within a year. That might sound like a= =20 lot, but > being able to accomplish that at all would be significant,=20 almost like a Chicago Pile moment, proving something in practice that was= =20 previously only thought theoretically > possible for the past 3 decades.=20 And it's only downhill from there... Briefly surveying the paper "The impact of hardware specifications on=20 reaching quantum advantage in the fault tolerant regime", I think it's a=20 reasonble framework to evaluate the practical efficiency of quantum attacks on bitcoin, it's self=20 consistent and there is a critical approach referencing the usual=20 litterature on quantum attacks on bitcoin. Just note the caveat, one can find in usual quantum complexity litterature,=20 "particularly in regard to end-to-end physical resource estimation. There= =20 are many other error correction techniques available, and the best choice will likely depend on the=20 underlying architecture's characteristics, such as the available physical= =20 qubit=E2=80=93qubit connectivity" (verbatim). Namely, evaluating quantum at= tacks is=20 very dependent on the concrete physical architecture underpinning it. All that said, I agree with you that if you see a quantum computer with the= =20 range of 1000 physical qubits being able to break the DLP for ECC based=20 encryption like secp256k1, even if it takes a year it will be a Chicago=20 Pile moment, or whatever comparative experiments which were happening about= =20 chain of nuclear reactions in 30s / 40s. > I think it's time to revisit these discussions given IBM's progress.=20 They've published a two videos in particular that are worth watching; their= =20 keynote from December of last > year [2], and their roadmap update from=20 just last month [3] I have looked on the roadmap as it's available on the IBM blog post:=20 https://www.ibm.com/quantum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2= 033 They give only a target of 2000 logical qubit to be reach in 2033...which= =20 is surprisingly not that strong...And one expect they might hit likely soli= d state issues in laying out in hardware the Heron processor architecture. As= =20 a point of thinking, it took like 2 decades to advance on the state of art of litography in traditional chips manufacturing. =20 So I think it's good to stay cool minded and I think my observation about= =20 talking of "super-exponential rate" as used in maaku old blog post does not hold a lot of rigor to describe the advances in the field of quantum=20 computing. Note, also how IMB is a commercial entity that can have a lot of= =20 interests in "pumping" the state of "quantum computing" to gather fundings (there is= =20 a historical anecdote among bitcoin OG circles about Vitalik trying to do a= n ICO to build a quantum computer like 10 years ago, just to remember). > I'm supportive of this consideration. FALCON might be a good substitute,= =20 and maybe it can be upgraded to HAWK for even better performance depending= =20 on how much > time there is. According to the BIP, FALCON signatures are=20 ~10x larger t> han Schnorr signatures, so this will of course make the=20 transaction more expensive, but we also > must remember, these signatures= =20 will be going into the witness, which already receives a 4x discount.=20 Perhaps the discount could be incr> eased further someday to fit > more=20 transactions into blocks, but this will also likely result in more=20 inscriptions filling unused space also, which permanently increases the=20 burden of running an archive > node. Due to the controversy s> uch a change= =20 could bring, I would rather any increases in the witness discount be=20 excluded from future activation discussions, so as to be > considered=20 separately, even if it pertains to an increase in P2QRH transaction size. =20 > Do you think it's worth reworking the BIP to use FALCON signatures? I've= =20 only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the= =20 readiness levels between those two are presently worlds apart. I think FALCON is what has the smallest pubkey + sig size for hash-and-sign= =20 lattice-based schemes. So I think it's worth reworking the BIP to see what= =20 has the smallest generation / validation time and pubkey + size space for= =20 the main post-quantum scheme. At least for dilthium, falcon, sphincs+ and= =20 SQISign. For an hypothetical witness discount, a v2 P2QRH could be always= =20 be moved in a very template annex tag / field. > Also, do you think it's of any concern to use HASH160 instead of HASH256= =20 in the output script? I think it's fine for a cryptographic commitment=20 since it's simply a hash of a hash (MD160 of SHA-256). See literature on quantum attacks on bitcoin in the reference of the paper= =20 you quote ("The impact of hardware specifications on reaching quantum=20 advantage in the fault tolerant regime") for a discussion on Grover's=20 search algorithm. > I'm not sure I fully understand this, but even more practically, as=20 mentioned in the BIP, value can simply be kept in P2WPKH outputs, ideally= =20 with a value of fewer than 50 > coins per address, and when funds ever need to be spent, the>=20 transaction is signed and submitted out of band to a trusted mining pool,= =20 ideally one that does KYC, so it's > known which individual miners get to see the public key before it's=20 mined. It's not perfect, since this relies on exogenou> s security=20 assumptions, which is why P2QRH is > proposed. Again, the paper you're referencing ("The impact of hardware specifications= =20 on reaching quantum advantage...") is analyzing the performance of quantum= =20 advantage under 2 dimensions, namely space and time. My observation is in Bitcoin we have= =20 an additional dimension, "coin scarcity" that can be leveraged to build=20 defense of address spends in face of quantum attacks. Namely you can introduce an artifical "witness-stack size scale ladder" in= =20 pseudo-bitcoin script: OP_SIZE <1000> OP_EQUALVERIFY OP_DROP ...checksig... I have not verified it works well on bitcoin core though this script should= =20 put the burden on the quantum attacker to have enough bitcoin amount=20 available to burn in on-chain fees in witness size to break a P2WPKH. > ideally with a value of fewer than 50 coins per address, and when funds= =20 ever need to be spent, the transaction is signed and submitted out of band= =20 to a trusted mining pool, ideally > one that does KYC, so it's known which individual > miners get to see the= =20 public key before it's mined. It's not perfect, since this relies on=20 exogenous security assumptions, which is > why P2QRH is proposed. The technical issue if you implement KYC for a mining pool you're=20 increasing your DoS surface and this could be exploited by competing=20 miners. A more reasonable security model can be to have miner coinbase=20 pubkeys being used to commit to the "seen-in-mempool" spends and from then= =20 build "hand wawy" fraud proofs that a miner is quantum attacking you're=20 P2WSH spends at pubkey reveal time during transaction relay. Best, Antoine ots hash: 1ad818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb27f1f0dc0b30 Le lundi 17 juin 2024 =C3=A0 23:25:25 UTC+1, hunter a =C3=A9crit : > > -----BEGIN PGP SIGNED MESSAGE----- > Hash: SHA256 > > On 2024-06-16 19:31, Antoine Riard wrote: > > > > > 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. > > > 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 > 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... > > > > 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). > > > 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. > > > > 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]. > > > 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]. > > > > 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. > > > 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 > 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 > 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). > > > > 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. > > > 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. > > > > Best,Antoine > > [1] https://freicoin.substack.com/p/why-im-against-taproot > > > =20 > I'm grateful you took the time to review the BIP and offer your detailed= =20 > insights. > =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 > [2] https://www.youtube.com/watch?v=3DDe2IlWji8Ck > [3] https://www.youtube.com/watch?v=3Dd5aIx79OTps > =20 > > > > > > Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=A9cr= it : > > > > > 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 > https://web.archive.org/web/20230711000109if_/http://sphincs.org/data/sph= incs+-round3-submission-nist.zip > > > =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 > > > Also, I've made some additional changes based on your feedback on X.= =20 > You can review them here if you so wish: > > >=20 > https://github.com/cryptoquick/bips/pull/5/files?short_path=3D917a32a#dif= f-917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82d36411ed45e754 > > > > > > > > > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-Luc=20 > Dallaire-Demers wrote: > > > > 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). > > > > 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. > > > > 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. > > > > > > > > On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4 Hunter Beast= wrote: > > > > > 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 > > > > > The BIP can be found here: > > > > > https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawik= i > > > > > =20 > > > > > Thank you for your time. > > > > > =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 > . > > -----BEGIN PGP SIGNATURE----- > Version: OpenPGP.js v4.10.3 > Comment: https://openpgpjs.org > > wsBcBAEBCAAGBQJmcJwuAAoJEDEPCKe+At0hjhkIAIdM7QN9hAO0z+KO7Bwe > JT45XyusJmDG1gJbLZtb+SfuE1X5PFDHNTLSNliJWsOImxFCiBPnlXhYQ4B/ > 8gST3rqplUwkdYr52E5uMxTTq9YaXTako4PNb8d7XfraIwDKXAJF+5Skf4f9 > bQUYMieBAFSEXCmluirQymB+hUoaze60Whd07hhpzbGSwK4DdSXltufkyCDE > tJUforNWm8X25ABTSNDh3+if5V/wJuix/u8GJyMHKucaEAO01ki2oyusq2rt > Xe6ysUieclusFFdQAs4PfYxhzXTf5XeAbFga/qxrVtbt7q2nUkYklqteT2pp > mH/DU20HMBeGVSrISrvsmLw=3D > =3D+wat > -----END PGP SIGNATURE----- > > --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= bitcoindev/cd6bda66-39d3-49ca-9f3c-f610258626b0n%40googlegroups.com. ------=_Part_438323_1854552589.1720834459750 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Hunter Beast,

Apologies for the delay in answer.

&= gt; 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 = threshold of qubits, it might be capable of decrypting the key to an addres= s within one year. I base this on the estimate > provided in a study by = the Sussex Centre for Quantum Technologies, et. al [1]. They provide two fi= gures, 317M qubits to decrypt in one hour, 13M qubits to decrypt in one >= ; day. It would seem it scales roughly linearly, and so extrapolating it fu= rther, 36,000 qubits would be needed to decrypt an address within one year.= However, the IBM Heron > QPU turned out to have a gate time 100x less t= han was estimated in 2022, and so it might be possible to make do with even= fewer qubits still within that timeframe. With > only 360 qubits, barri= ng 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 &= gt; being able to accomplish that at all would be significant, almost like = a Chicago Pile moment, proving something in practice that was previously on= ly thought theoretically > possible for the past 3 decades. And it's onl= y downhill from there...

Briefly surveying the paper "The impact= of hardware specifications on reaching quantum advantage in the fault tole= rant regime", I think it's a reasonble framework to evaluate
the pract= ical efficiency of quantum attacks on bitcoin, it's self consistent and the= re is a critical approach referencing the usual litterature on quantum atta= cks on bitcoin. Just
note the caveat, one can find in usual quantum co= mplexity litterature, "particularly in regard to end-to-end physical resour= ce estimation. There are many other error correction
techniques availa= ble, and the best choice will likely depend on the underlying architecture'= s characteristics, such as the available physical qubit=E2=80=93qubit conne= ctivity" (verbatim). Namely, evaluating quantum attacks is very dependent o= n the concrete physical architecture underpinning it.

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

> =C2=A0I think it's time to revis= it these discussions given IBM's progress. They've published a two videos i= n particular that are worth watching; their keynote from December of last &= gt; 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/quantum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2033They give only a target of 2000 logical qubit to be reach in 2033...whic= h is surprisingly not that strong...And one expect they might hit likely so= lid
state issues in laying out in hardware the Heron processor archite= cture. As a point of thinking, it took like 2 decades to advance on the sta= te of art
of litography in traditional chips manufacturing.
=C2= =A0
So I think it's good to stay cool minded and I think my observatio= n about talking of "super-exponential rate" as used in maaku old blog post = does not
hold a lot of rigor to describe the advances in the field of = quantum computing. Note, also how IMB is a commercial entity that can have = a lot of interests
in "pumping" the state of "quantum computing" to ga= ther fundings (there is a historical anecdote among bitcoin OG circles abou= t Vitalik trying to do an
ICO to build a quantum computer like 10 year= s ago, just to remember).

> I'm supportive of this considerat= ion. FALCON might be a good substitute, and maybe it can be upgraded to HAW= K for even better performance depending on how much > time there is. Acc= ording to the BIP, FALCON signatures are ~10x larger t> han Schnorr sign= atures, so this will of course make the transaction more expensive, but we = also > must remember, these signatures will be going into the witness, w= hich already receives a 4x discount. Perhaps the discount could be incr>= eased further someday to fit > more transactions into blocks, but this = will also likely result in more inscriptions filling unused space also, whi= ch permanently increases the burden of running an archive > node. Due to= the controversy s> uch a change could bring, I would rather any increas= es in the witness discount be excluded from future activation discussions, = 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 re= working the BIP to use FALCON signatures? I've only done a deep dive into S= QIsign and SPHINCS+, and I will acknowledge the readiness levels between th= ose two are presently worlds apart.

I think FALCON is what has t= he smallest pubkey + sig size for hash-and-sign lattice-based schemes. So I= think it's worth reworking the BIP to see what has the smallest generation= / validation time and pubkey + size space for the main post-quantum scheme= . 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 an= nex tag / field.

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

See literature on quantum attacks on bitcoin in the refer= ence of the paper you quote ("The impact of hardware specifications on reac= hing quantum advantage in the fault tolerant regime") for a discussion on G= rover's search algorithm.

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

Again, the paper you're referencing ("The impact= of hardware specifications on reaching 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, "c= oin scarcity" that can be leveraged to build defense of address
spends= in face of quantum attacks.

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

> =C2=A0ideally wit= h a value of fewer than 50 coins per address, and when funds ever need to b= e spent, the transaction is signed and submitted out of band to a trusted m= ining pool, ideally
> one that does KYC, so it's known which indivi= dual > 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 implement KY= C for a mining pool you're increasing your DoS surface and this could be ex= ploited by competing miners. A more reasonable security model can be to hav= e miner coinbase pubkeys being used to commit to the "seen-in-mempool" spen= ds and from then build "hand wawy" fraud proofs that a miner is quantum att= acking you're P2WSH spends at pubkey reveal time during transaction relay.<= br />
Best,
Antoine

ots hash:=C2=A01ad= 818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb27f1f0dc0b30
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...@gmail.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.o= rg/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-4f81fa50162= 7n%40googlegroups.com.

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

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

--
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/cd6bda66-39d3-49ca-9f3c-f610258626b0n%40googlegroups.com.=
------=_Part_438323_1854552589.1720834459750-- ------=_Part_438322_752256595.1720834459750--