From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 06 Aug 2024 10:50:45 -0700 Received: from mail-yb1-f185.google.com ([209.85.219.185]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sbOKY-0000IP-Cb for bitcoindev@gnusha.org; Tue, 06 Aug 2024 10:50:45 -0700 Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e0ba463c970sf1792099276.0 for ; Tue, 06 Aug 2024 10:50:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1722966636; x=1723571436; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=AiZw12mK9KjWjkYM7zwgddv10f6KVgH85Klo4Kkab6E=; b=IxQD7uYMs6HEMm2mJLa27nZmd6pYHIZmyH+UPxBEE83Ffbmo1yWUzQdW0GtFoTbEF2 LI4zK3zPqWhT/CqWNWGGrs6fkiSLc7c+m2h6gBNKL/B3iTBsrVIXokMeB2qI08syZTbs TDO78jB1JZTayc7jkgEWB0AcyN5NmnoTqqZcbKjReoYmAuReWo7x9bdWHs6ZJobrnxi0 mvO3++oV7MYR32TtNQGHNX3jvar3iVV+fNjiDP22j685Oz5DApg+ts/EdOWAidbeaXAm EUJBaYG8G6M62NHDoPqEvqmaRPek/L3pvCCb9OnDFIpABp86JdJrMwQUYEiKCToLqSPT UASA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722966636; x=1723571436; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:x-beenthere :x-gm-message-state:sender:from:to:cc:subject:date:message-id :reply-to; bh=AiZw12mK9KjWjkYM7zwgddv10f6KVgH85Klo4Kkab6E=; b=mefWn48xgPtdcGTvvi+6Sfxl1vcQHLIF8dOHCC0B6F87cWvM6IID8xpSJsceqHJaMl nTAFjw/3PORrK9sOKhWIFAjZwOaP26sMGsW8XnXVxxrzeZyt2/MfpN+mM73bGalRWKfL dmtYnMR6SL/IVyIE0FNEolNdRaHgFkalynGVC4PO6sRsSK/DQRPESrsXJWGKmD9yROHq 3P4Xl9/UBdILRu8Ah2+R2LKrEBd3pK9GvBWXFyReuaBs7FyjhFquL19hIhXu3OEy5Qfj XxQKMhwQbZbyzoess3ENnOy/Ze2oeFnAdPDDF+GcBbqlXGQipx8RM5mpElpYlxOk7Ttw hZvA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVcE5zcwicbxQ6sccosl43jBID+PWzAuwW+fp61bufXDqetrWq9xovFcS3xCsYbtFPDjHTpvMAw4ICks7aj2h+Wb/8i+Yk= X-Gm-Message-State: AOJu0YyxZXOZQ/pMA2ilIYPTfGmboCREhEULdQVPsdeAt8GHL1EvNtD+ xsanG3jYidMWvvwmVuKJCGntpnrz8sSDIjbaIjABpXcCAKstq5dW X-Google-Smtp-Source: AGHT+IHrrV/vXs2P9SV1GZBghOeaHUd/ngjUy04yztgmBsAzGrcp/9oImF4ibiLWzIqEZzQuKgvAwQ== X-Received: by 2002:a05:6902:114b:b0:e0d:d525:86b8 with SMTP id 3f1490d57ef6-e0dd5258c41mr12855522276.36.1722966635625; Tue, 06 Aug 2024 10:50:35 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:102c:b0:dfd:bfdd:cd15 with SMTP id 3f1490d57ef6-e0bf4c0c531ls5066399276.1.-pod-prod-07-us; Tue, 06 Aug 2024 10:50:33 -0700 (PDT) X-Received: by 2002:a05:690c:2e0e:b0:615:32e1:d82c with SMTP id 00721157ae682-689640aea10mr3084577b3.6.1722966633293; Tue, 06 Aug 2024 10:50:33 -0700 (PDT) Received: by 2002:a05:690c:2884:b0:664:87b6:d9e0 with SMTP id 00721157ae682-698ab783debms7b3; Tue, 6 Aug 2024 10:37:16 -0700 (PDT) X-Received: by 2002:a81:a788:0:b0:697:9aae:1490 with SMTP id 00721157ae682-6979aae1895mr680487b3.1.1722965834835; Tue, 06 Aug 2024 10:37:14 -0700 (PDT) Date: Tue, 6 Aug 2024 10:37:14 -0700 (PDT) From: Hunter Beast To: Bitcoin Development Mailing List Message-Id: <1b86f467-95e5-4558-98bc-b921dd29e1afn@googlegroups.com> In-Reply-To: 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_871338_1805467811.1722965834575" 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_871338_1805467811.1722965834575 Content-Type: multipart/alternative; boundary="----=_Part_871339_835844614.1722965834575" ------=_Part_871339_835844614.1722965834575 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable That's alright, Antoine, it's been a busy month for me too. > So I think it's good to stay cool minded and I think my observation about= =20 talking of "super-exponential rate" as used in maaku old blog post does not > hold a lot of rigor to describe the advances in the field of quantum=20 computing. Note, also how IMB is a commercial entity that can have a lot of= =20 interests > in "pumping" the state of "quantum computing" to gather fundings (there= =20 is a historical anecdote among bitcoin OG circles about Vitalik trying to= =20 do an > ICO to build a quantum computer like 10 years ago, just to remember). Well, it's also important to remember that for every qubit added, it=20 doubles the power of the system. A 2,000 qubit cryptographically-relevant= =20 quantum computer (CRQC) is exponentially faster than a 1,000 qubit one.=20 There's also the capability for cross-links for multiple chips to=20 communicate with each other, which IBM is also researching. The IBM Quantum= =20 System Two can be upgraded to support 16,000 qubits according to their=20 marketing. Also consider that the verification of the results from the CRQC= =20 can be done via classical computer, so a high level of error correction=20 might not be as necessary so long as the program is run enough times. It=20 will take much longer, of course. > I think FALCON is what has the smallest pubkey + sig size for=20 hash-and-sign lattice-based schemes. So I think it's worth reworking the=20 BIP to see what has the smallest generation / validation time and pubkey += =20 size space for the main post-quantum scheme. At least for dilthium, falcon,= =20 sphincs+ and SQISign. For an hypothetical witness discount, a v2 P2QRH=20 could be always be moved in a very template annex tag / field. I've decided in one of my more recent updates to the BIP to default to the= =20 highest level of NIST security, NIST V, which provides 256 bits of=20 security. You can see my rationale for that in this PR: https://github.com/cryptoquick/bips/pull/7/files Then, referencing this table: https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki#security As such, you'll see FALCON is roughly 4x larger than SQIsign signatures.=20 Although supersingular elliptic curve quaternion isogeny-based algorithms= =20 are newer and more experimental than lattice-based cryptography, I think=20 the benefits outweigh the risks, especially when transaction throughput is= =20 a principal concern. It's crucial that the signature and public key both receive the witness=20 discount. Can you go into more detail in how that might be accomplished? Although it's too early to talk about activation of a QuBit soft fork, I've= =20 put some thought into how we can maintain the existing Bitcoin throughput= =20 with a soft fork, and I think it might be prudent to, when the time comes,= =20 introduce a 4x additional QuBit witness discount, maybe we call it the=20 quitness, which is only available to valid P2QRH signatures. This would=20 preclude its abuse for things like inscriptions because the signature data= =20 would need to correspond to the key, and even if this were possible, it's= =20 likely to result in only a burner address. This would increase chain state= =20 growth from roughly 100GB/yr to possibly closer to 2-300GB, depending on=20 adoption. As the state of the art of SSD technology advances, this should= =20 allow plebs to run their own node on a 4TB disk for over a decade, even=20 including existing chain size of ~600GB. If we were to use the same approach for FALCON signatures, a 16x discount= =20 would be needed, and I think that's far too much for the community to=20 accept. As for pub key size and verification time, these are secondary=20 considerations if the primary constraint is maintaining present transaction= =20 throughput. That's what makes SQIsign so promising. > See literature on quantum attacks on bitcoin in the reference of the=20 paper you quote ("The impact of hardware specifications on reaching quantum= =20 advantage in the fault tolerant regime") for a discussion on Grover's=20 search algorithm. The Impact paper seems to dismiss Grover's algorithm, but I think it's=20 important to err on the size of caution and instead use a 32-byte double=20 SHA-2 (HASH256) for additional security in the P2QRH output. > Namely you can introduce an artifical "witness-stack size scale ladder"= =20 in pseudo-bitcoin script: OP_SIZE <1000> OP_EQUALVERIFY OP_DROP=20 ...checksig... > I have not verified it works well on bitcoin core though this script=20 should put the burden on the quantum attacker to have enough bitcoin amount= =20 available to burn in on-chain fees in witness size to break a P2WPKH. I'm not sure I understand what you mean by this... Is your coin scarcity comment related to what I call "satoshi's shield" in= =20 the BIP? > The technical issue if you implement KYC for a mining pool you're=20 increasing your DoS surface and this could be exploited by competing=20 miners. A more reasonable security model can be to have miner coinbase=20 pubkeys being used to commit to the "seen-in-mempool" spends and from then= =20 build "hand wawy" fraud proofs that a miner is quantum attacking you're=20 P2WSH spends at pubkey reveal time during transaction relay. Yes, this makes more sense. I'm not sure anything can be done with the=20 fraud proofs, but they could at least prove that a bad actor is present.=20 Ideally both approaches are combined for maximum security and=20 accountability. Thanks for your time! On Friday, July 12, 2024 at 7:44:27=E2=80=AFPM UTC-6 Antoine Riard wrote: Hi Hunter Beast, Apologies for the delay in answer. > I was thinking of focusing on the IBM Quantum System Two, mention how it= =20 can be scaled, and that although it might be quite limited, if running=20 Shor's variant for a > sufficient amount of time, above a certain minimum= =20 threshold of qubits, it might be capable of decrypting the key to an=20 address within one year. I base this on the estimate > provided in a study= =20 by the Sussex Centre for Quantum Technologies, et. al [1]. They provide two= =20 figures, 317M qubits to decrypt in one hour, 13M qubits to decrypt in one >= =20 day. It would seem it scales roughly linearly, and so extrapolating it=20 further, 36,000 qubits would be needed to decrypt an address within one=20 year. However, the IBM Heron > QPU turned out to have a gate time 100x less= =20 than was estimated in 2022, and so it might be possible to make do with=20 even fewer qubits still within that timeframe. With > only 360 qubits,=20 barring algorithmic overhead such as for circuit memory, it might be=20 possible to decrypt a single address within a year. That might sound like a= =20 lot, but > being able to accomplish that at all would be significant,=20 almost like a Chicago Pile moment, proving something in practice that was= =20 previously only thought theoretically > possible for the past 3 decades.=20 And it's only downhill from there... Briefly surveying the paper "The impact of hardware specifications on=20 reaching quantum advantage in the fault tolerant regime", I think it's a=20 reasonble framework to evaluate the practical efficiency of quantum attacks on bitcoin, it's self=20 consistent and there is a critical approach referencing the usual=20 litterature on quantum attacks on bitcoin. Just note the caveat, one can find in usual quantum complexity litterature,=20 "particularly in regard to end-to-end physical resource estimation. There= =20 are many other error correction techniques available, and the best choice will likely depend on the=20 underlying architecture's characteristics, such as the available physical= =20 qubit=E2=80=93qubit connectivity" (verbatim). Namely, evaluating quantum at= tacks is=20 very dependent on the concrete physical architecture underpinning it. All that said, I agree with you that if you see a quantum computer with the= =20 range of 1000 physical qubits being able to break the DLP for ECC based=20 encryption like secp256k1, even if it takes a year it will be a Chicago=20 Pile moment, or whatever comparative experiments which were happening about= =20 chain of nuclear reactions in 30s / 40s. > I think it's time to revisit these discussions given IBM's progress.=20 They've published a two videos in particular that are worth watching; their= =20 keynote from December of last > year [2], and their roadmap update from=20 just last month [3] I have looked on the roadmap as it's available on the IBM blog post:=20 https://www.ibm.com/quantum/blog/quantum-roadmap-2033#mark-roadmap-out-to-2= 033 They give only a target of 2000 logical qubit to be reach in 2033...which= =20 is surprisingly not that strong...And one expect they might hit likely soli= d state issues in laying out in hardware the Heron processor architecture. As= =20 a point of thinking, it took like 2 decades to advance on the state of art of litography in traditional chips manufacturing. =20 So I think it's good to stay cool minded and I think my observation about= =20 talking of "super-exponential rate" as used in maaku old blog post does not hold a lot of rigor to describe the advances in the field of quantum=20 computing. Note, also how IMB is a commercial entity that can have a lot of= =20 interests in "pumping" the state of "quantum computing" to gather fundings (there is= =20 a historical anecdote among bitcoin OG circles about Vitalik trying to do a= n ICO to build a quantum computer like 10 years ago, just to remember). > I'm supportive of this consideration. FALCON might be a good substitute,= =20 and maybe it can be upgraded to HAWK for even better performance depending= =20 on how much > time there is. According to the BIP, FALCON signatures are=20 ~10x larger t> han Schnorr signatures, so this will of course make the=20 transaction more expensive, but we also > must remember, these signatures= =20 will be going into the witness, which already receives a 4x discount.=20 Perhaps the discount could be incr> eased further someday to fit > more=20 transactions into blocks, but this will also likely result in more=20 inscriptions filling unused space also, which permanently increases the=20 burden of running an archive > node. Due to the controversy s> uch a change= =20 could bring, I would rather any increases in the witness discount be=20 excluded from future activation discussions, so as to be > considered=20 separately, even if it pertains to an increase in P2QRH transaction size. =20 > Do you think it's worth reworking the BIP to use FALCON signatures? I've= =20 only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the= =20 readiness levels between those two are presently worlds apart. I think FALCON is what has the smallest pubkey + sig size for hash-and-sign= =20 lattice-based schemes. So I think it's worth reworking the BIP to see what= =20 has the smallest generation / validation time and pubkey + size space for= =20 the main post-quantum scheme. At least for dilthium, falcon, sphincs+ and= =20 SQISign. For an hypothetical witness discount, a v2 P2QRH could be always= =20 be moved in a very template annex tag / field. > Also, do you think it's of any concern to use HASH160 instead of HASH256= =20 in the output script? I think it's fine for a cryptographic commitment=20 since it's simply a hash of a hash (MD160 of SHA-256). See literature on quantum attacks on bitcoin in the reference of the paper= =20 you quote ("The impact of hardware specifications on reaching quantum=20 advantage in the fault tolerant regime") for a discussion on Grover's=20 search algorithm. > I'm not sure I fully understand this, but even more practically, as=20 mentioned in the BIP, value can simply be kept in P2WPKH outputs, ideally= =20 with a value of fewer than 50 > coins per address, and when funds ever need to be spent, the>=20 transaction is signed and submitted out of band to a trusted mining pool,= =20 ideally one that does KYC, so it's > known which individual miners get to see the public key before it's=20 mined. It's not perfect, since this relies on exogenou> s security=20 assumptions, which is why P2QRH is > proposed. Again, the paper you're referencing ("The impact of hardware specifications= =20 on reaching quantum advantage...") is analyzing the performance of quantum= =20 advantage under 2 dimensions, namely space and time. My observation is in Bitcoin we have= =20 an additional dimension, "coin scarcity" that can be leveraged to build=20 defense of address spends in face of quantum attacks. Namely you can introduce an artifical "witness-stack size scale ladder" in= =20 pseudo-bitcoin script: OP_SIZE <1000> OP_EQUALVERIFY OP_DROP ...checksig... I have not verified it works well on bitcoin core though this script should= =20 put the burden on the quantum attacker to have enough bitcoin amount=20 available to burn in on-chain fees in witness size to break a P2WPKH. > ideally with a value of fewer than 50 coins per address, and when funds= =20 ever need to be spent, the transaction is signed and submitted out of band= =20 to a trusted mining pool, ideally > one that does KYC, so it's known which individual > miners get to see the= =20 public key before it's mined. It's not perfect, since this relies on=20 exogenous security assumptions, which is > why P2QRH is proposed. The technical issue if you implement KYC for a mining pool you're=20 increasing your DoS surface and this could be exploited by competing=20 miners. A more reasonable security model can be to have miner coinbase=20 pubkeys being used to commit to the "seen-in-mempool" spends and from then= =20 build "hand wawy" fraud proofs that a miner is quantum attacking you're=20 P2WSH spends at pubkey reveal time during transaction relay. Best, Antoine ots hash: 1ad818955bbf0c5468847c00c2974ddb5cf609d630523622bfdb27f1f0dc0b30 Le lundi 17 juin 2024 =C3=A0 23:25:25 UTC+1, hunter a =C3=A9crit : -----BEGIN PGP SIGNED MESSAGE-----=20 Hash: SHA256=20 On 2024-06-16 19:31, Antoine Riard wrote:=20 >=20 > Hi Hunter Beast,I think any post-quantum upgrade signature algorithm=20 upgrade proposal would grandly benefit to haveShor's based practical=20 attacks far more defined in the Bitcoin context. As soon you start to talk= =20 aboutquantum computers there is no such thing as a "quantum computer"=20 though a wide array of architecturesbased on a range of technologies to=20 encode qubits on nanoscale physical properties.=20 >=20 Good point. I can write a section in the BIP Motivation or Security section= =20 about how an attack might take place practically, and the potential urgency= =20 of such an attack.=20 =20 I was thinking of focusing on the IBM Quantum System Two, mention how it=20 can be scaled, and that although it might be quite limited, if running=20 Shor's variant for a sufficient amount of time, above a certain minimum=20 threshold of qubits, it might be capable of decrypting the key to an=20 address within one year. I base this on the estimate provided in a study by= =20 the Sussex Centre for Quantum Technologies, et. al [1]. They provide two=20 figures, 317M qubits to decrypt in one hour, 13M qubits to decrypt in one= =20 day. It would seem it scales roughly linearly, and so extrapolating it=20 further, 36,000 qubits would be needed to decrypt an address within one=20 year. However, the IBM Heron QPU turned out to have a gate time 100x less= =20 than was estimated in 2022, and so it might be possible to make do with=20 even fewer qubits still within that timeframe. With only 360 qubits,=20 barring algorithmic overhead such as for circuit memory, it might be=20 possible to decrypt a single address within a year. That might sound like a= =20 lot, but being able to accomplish that at all would be significant, almost= =20 like a Chicago Pile moment, proving something in practice that was=20 previously only thought theoretically possible for the past 3 decades. And= =20 it's only downhill from there...=20 >=20 > This is not certain that any Shor's algorithm variant works smoothly=20 independently of the quantum computerarchitecture considered (e.g gate=20 frequency, gate infidelity, cooling energy consumption) and I think it'san= =20 interesting open game-theory problem if you can concentrate a sufficiant=20 amount of energy before anycoin owner moves them in consequence (e.g seeing= =20 a quantum break in the mempool and reacting with a counter-spend).=20 >=20 It should be noted that P2PK keys still hold millions of bitcoin, and those= =20 encode the entire public key for everyone to see for all time. Thus, early= =20 QC attacks won't need to consider the complexities of the mempool.=20 >=20 > In my opinion, one of the last time the subject was addressed on the=20 mailing list, the description of the state of the quantum computer field=20 was not realistic and get into risk characterization hyperbole talking=20 about "super-exponential rate" (when indeed there is no empirical=20 realization that distinct theoretical advance on quantum capabilities can= =20 be combined with each other) [1].=20 >=20 I think it's time to revisit these discussions given IBM's progress.=20 They've published a two videos in particular that are worth watching; their= =20 keynote from December of last year [2], and their roadmap update from just= =20 last month [3].=20 >=20 > On your proposal, there is an immediate observation which comes to mind,= =20 namely why not using one of the algorithm(dilthium, sphincs+, falcon) which= =20 has been through the 3 rounds of NIST cryptanalysis. Apart of the signature= =20 size,which sounds to be smaller, in a network of full-nodes any PQ=20 signature algorithm should have reasonable verificationperformances.=20 >=20 I'm supportive of this consideration. FALCON might be a good substitute,=20 and maybe it can be upgraded to HAWK for even better performance depending= =20 on how much time there is. According to the BIP, FALCON signatures are ~10x= =20 larger than Schnorr signatures, so this will of course make the transaction= =20 more expensive, but we also must remember, these signatures will be going= =20 into the witness, which already receives a 4x discount. Perhaps the=20 discount could be increased further someday to fit more transactions into= =20 blocks, but this will also likely result in more inscriptions filling=20 unused space also, which permanently increases the burden of running an=20 archive node. Due to the controversy such a change could bring, I would=20 rather any increases in the witness discount be excluded from future=20 activation discussions, so as to be considered separately, even if it=20 pertains to an increase in P2QRH transaction size.=20 =20 Do you think it's worth reworking the BIP to use FALCON signatures? I've=20 only done a deep dive into SQIsign and SPHINCS+, and I will acknowledge the= =20 readiness levels between those two are presently worlds apart.=20 =20 Also, do you think it's of any concern to use HASH160 instead of HASH256 in= =20 the output script? I think it's fine for a cryptographic commitment since= =20 it's simply a hash of a hash (MD160 of SHA-256).=20 >=20 > Lastly, there is a practical defensive technique that can be implemented= =20 today by coin owners to protect in face ofhyptothetical quantum=20 adversaries. Namely setting spending scripts to request an artificially=20 inflated witness stack,as the cost has to be burden by the spender. I think= =20 one can easily do that with OP_DUP and OP_GREATERTHAN and a bitof stack=20 shuffling. While the efficiency of this technique is limited by the max=20 consensus size of the script stack(`MAX_STACK_SIZE`) and the max consensus= =20 size of stack element (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an=20 additional"scarce coins" pre-requirement on the quantum adversarise to=20 succeed. Shor's algorithm is only defined under theclassic ressources of=20 computational complexity, time and space.=20 >=20 I'm not sure I fully understand this, but even more practically, as=20 mentioned in the BIP, value can simply be kept in P2WPKH outputs, ideally= =20 with a value of fewer than 50 coins per address, and when funds ever need= =20 to be spent, the transaction is signed and submitted out of band to a=20 trusted mining pool, ideally one that does KYC, so it's known which=20 individual miners get to see the public key before it's mined. It's not=20 perfect, since this relies on exogenous security assumptions, which is why= =20 P2QRH is proposed.=20 >=20 > Best,Antoine=20 > [1] https://freicoin.substack.com/p/why-im-against-taproot=20 >=20 =20 I'm grateful you took the time to review the BIP and offer your detailed=20 insights.=20 =20 [1] =E2=80=9CThe impact of hardware specifications on reaching quantum adva= ntage in=20 the fault tolerant regime,=E2=80=9D 2022 -=20 https://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardw= are-specifications-on-reaching=20 [2] https://www.youtube.com/watch?v=3DDe2IlWji8Ck=20 [3] https://www.youtube.com/watch?v=3Dd5aIx79OTps=20 =20 >=20 >=20 > Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=A9crit= :=20 >=20 > > Good points. I like your suggestion for a SPHINCS+, just due to how=20 mature it is in comparison to SQIsign. It's already in its third round and= =20 has several standards-compliant implementations, and it has an actual=20 specification rather than just a research paper. One thing to consider is= =20 that NIST-I round 3 signatures are 982 bytes in size, according to what I= =20 was able to find in the documents hosted by the SPHINCS website.=20 > >=20 https://web.archive.org/web/20230711000109if_/http://sphincs.org/data/sphin= cs+-round3-submission-nist.zip=20 > > =20 > > One way to handle this is to introduce this as a separate address type= =20 than SQIsign. That won't require OP_CAT, and I do want to keep this soft=20 fork limited in scope. If SQIsign does become significantly broken, in this= =20 hopefully far future scenario, I might be supportive of an increase in the= =20 witness discount.=20 > > =20 > > Also, I've made some additional changes based on your feedback on X.=20 You can review them here if you so wish:=20 > >=20 https://github.com/cryptoquick/bips/pull/5/files?short_path=3D917a32a#diff-= 917a32a71b69bf62d7c85dfb13d520a0340a30a2889b015b82d36411ed45e754=20 > >=20 > >=20 > > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-Luc Dallair= e-Demers=20 wrote:=20 > > > SQIsign is blockchain friendly but also very new, I would recommend= =20 adding a hash-based backup key in case an attack on SQIsign is found in the= =20 future (recall that SIDH broke over the span of a weekend=20 https://eprint.iacr.org/2022/975.pdf).=20 > > > Backup keys can be added in the form of a Merkle tree where one=20 branch would contain the SQIsign public key and the other the public key of= =20 the recovery hash-based scheme. For most transactions it would only add one= =20 bit to specify the SQIsign branch.=20 > > > The hash-based method could be Sphincs+, which is standardized by=20 NIST but requires adding extra code, or Lamport, which is not standardized= =20 but can be verified on-chain with OP-CAT.=20 > > >=20 > > > On Sunday, June 9, 2024 at 12:07:16=E2=80=AFp.m. UTC-4 Hunter Beast w= rote:=20 > > > > The motivation for this BIP is to provide a concrete proposal for= =20 adding quantum resistance to Bitcoin. We will need to pick a signature=20 algorithm, implement it, and have it ready in event of quantum emergency.= =20 There will be time to adopt it. Importantly, this first step is a more=20 substantive answer to those with concerns beyond, "quantum computers may=20 pose a threat, but we likely don't have to worry about that for a long=20 time". Bitcoin development and activation is slow, so it's important that= =20 those with low time preference start discussing this as a serious=20 possibility sooner rather than later. This is meant to be the first in a=20 series of BIPs regarding a hypothetical "QuBit" soft fork. The BIP is=20 intended to propose concrete solutions, even if they're early and=20 incomplete, so that Bitcoin developers are aware of the existence of these= =20 solutions and their potential. This is just a rough draft and not the=20 finished BIP. I'd like to validate the approach and hear if I should=20 continue working on it, whether serious changes are needed, or if this=20 truly isn't a worthwhile endeavor right now.=20 > > > > =20 > > > > The BIP can be found here:=20 > > > > https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki= =20 > > > > =20 > > > > Thank you for your time.=20 > > > > =20 > > > >=20 > > >=20 > > >=20 > >=20 > >=20 >=20 >=20 > -- You received this message because you are subscribed to a topic in the= =20 Google Groups "Bitcoin Development Mailing List" group. To unsubscribe from= =20 this topic, visit=20 https://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe. To=20 unsubscribe from this group and all its topics, send an email to=20 bitcoindev+...@googlegroups.com. To view this discussion on the web visit= =20 https://groups.google.com/d/msgid/bitcoindev/87b4e402-39d8-46b0-8269-4f81fa= 501627n%40googlegroups.com.=20 -----BEGIN PGP SIGNATURE-----=20 Version: OpenPGP.js v4.10.3=20 Comment: https://openpgpjs.org=20 wsBcBAEBCAAGBQJmcJwuAAoJEDEPCKe+At0hjhkIAIdM7QN9hAO0z+KO7Bwe=20 JT45XyusJmDG1gJbLZtb+SfuE1X5PFDHNTLSNliJWsOImxFCiBPnlXhYQ4B/=20 8gST3rqplUwkdYr52E5uMxTTq9YaXTako4PNb8d7XfraIwDKXAJF+5Skf4f9=20 bQUYMieBAFSEXCmluirQymB+hUoaze60Whd07hhpzbGSwK4DdSXltufkyCDE=20 tJUforNWm8X25ABTSNDh3+if5V/wJuix/u8GJyMHKucaEAO01ki2oyusq2rt=20 Xe6ysUieclusFFdQAs4PfYxhzXTf5XeAbFga/qxrVtbt7q2nUkYklqteT2pp=20 mH/DU20HMBeGVSrISrvsmLw=3D=20 =3D+wat=20 -----END PGP SIGNATURE-----=20 --=20 You received this message because you are subscribed to the Google Groups "= Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/= bitcoindev/1b86f467-95e5-4558-98bc-b921dd29e1afn%40googlegroups.com. ------=_Part_871339_835844614.1722965834575 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable That's alright, Antoine, it's been a busy month for me too.

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

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

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

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

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

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

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

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

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

> Nam= ely you can introduce an artifical "witness-stack size scale ladder" in pse= udo-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 b= itcoin amount available to burn in on-chain fees in witness size to break a= P2WPKH.

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

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

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

Thanks for your time!

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

A= pologies for the delay in answer.

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

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

All that said, I agree with you that if= you see a quantum computer with the range of 1000 physical qubits being ab= le to break the DLP for ECC based encryption like secp256k1, even if it tak= es a year it will be a Chicago Pile moment, or whatever comparative experim= ents which were happening about chain of nuclear reactions in 30s / 40s.
> =C2=A0I think it's time to revisit these discussions given IB= M's progress. They've published a two videos in particular that are worth w= atching; their keynote from December of last > year [2], and their roadm= ap 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-2033
They give only a target of 2000 logical qubit = to be reach in 2033...which is surprisingly not that strong...And one expec= t they might hit likely solid
state issues in laying out in hardware t= he Heron processor architecture. As a point of thinking, it took like 2 dec= ades to advance on the state of art
of litography in traditional chips= manufacturing.
=C2=A0
So I think it's good to stay cool minded a= nd I think my observation about talking of "super-exponential rate" as used= in maaku old blog post does not
hold a lot of rigor to describe the a= dvances in the field of quantum computing. Note, also how IMB is a commerci= al entity that can have a lot of interests
in "pumping" the state of "= quantum computing" to gather fundings (there is a historical anecdote among= bitcoin OG circles about Vitalik trying to do an
ICO to build a quant= um computer like 10 years ago, just to remember).

> I'm suppo= rtive of this consideration. FALCON might be a good substitute, and maybe i= t can be upgraded to HAWK for even better performance depending on how much= > time there is. According to the BIP, FALCON signatures are ~10x large= r t> han Schnorr signatures, so this will of course make the transaction= more expensive, but we also > must remember, these signatures will be g= oing into the witness, which already receives a 4x discount. Perhaps the di= scount could be incr> eased further someday to fit > more transaction= s into blocks, but this will also likely result in more inscriptions fillin= g unused space also, which permanently increases the burden of running an a= rchive > node. Due to the controversy s> uch a change could bring, I = would rather any increases in the witness discount be excluded from future = activation discussions, so as to be > considered separately, even if it = pertains to an increase in 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 acknowledge the rea= diness levels between those two are presently worlds apart.

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

> 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 reference of the paper you quote ("The impact of hardwar= e specifications on reaching quantum advantage in the fault tolerant regime= ") for a discussion on Grover's search algorithm.

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

Again, the paper you're = referencing ("The impact of hardware specifications on reaching quantum adv= antage...") 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 defens= e of address
spends in face of quantum attacks.

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


> =C2=A0ideally with a value of fewer than 50 coins per add= ress, and when funds ever need to be spent, the transaction is signed and s= ubmitted out of band to a trusted mining pool, ideally
> one that d= oes KYC, so it's known which individual > miners get to see the public k= ey before it's mined. It's not perfect, since this relies on exogenous secu= rity assumptions, which is
> why P2QRH is proposed.

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

Best,
Antoine=

ots hash:=C2=A01ad818955bbf0c5468847c00c2974ddb= 5cf609d630523622bfdb27f1f0dc0b30
Le lundi 17 ju= in 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 algor= ithm upgrade proposal would grandly benefit to haveShor's based practical a= ttacks far more defined in the Bitcoin context. As soon you start to talk a= boutquantum computers there is no such thing as a "quantum computer" though= a wide array of architecturesbased on a range of technologies to encode qu= bits on nanoscale physical properties.
>
Good point. I can write a section in the BIP Motivation or Security s= ection about how an attack might take place practically, and the potential = urgency of such an attack.
=C2=A0
I was thinking of focusing on the IBM Quantum System Two, mention how= it can be scaled, and that although it might be quite limited, if running = Shor's variant for a sufficient amount of time, above a certain minimum thr= eshold of qubits, it might be capable of decrypting the key to an address w= ithin one year. I base this on the estimate provided in a study by the Suss= ex Centre for Quantum Technologies, et. al [1]. They provide two figures, 3= 17M qubits to decrypt in one hour, 13M qubits to decrypt in one day. It wou= ld seem it scales roughly linearly, and so extrapolating it further, 36,000= qubits would be needed to decrypt an address within one year. However, the= IBM Heron QPU=C2=A0turned out to have a gate time 100x less than was estim= ated in 2022, and so it might be possible to make do with even fewer qubits= still within that timeframe. With only 360 qubits, barring algorithmic ove= rhead such as for circuit memory, it might be possible to=C2=A0decrypt a si= ngle address within a year. That might sound like a lot, but being able to= =C2=A0accomplish that=C2=A0at all would be significant, almost like a Chica= go Pile moment, proving something in practice that was previously only thou= ght theoretically possible for the past 3 decades. And it's only downhill f= rom there...
>
> This is not certain that any Shor's algorithm variant works smoo= thly independently of the quantum computerarchitecture considered (e.g gate= frequency, gate infidelity, cooling energy consumption) and I think it'san= interesting open game-theory problem if you can concentrate a sufficiant a= mount of energy before anycoin owner moves them in consequence (e.g seeing = a quantum break in the mempool and reacting with a counter-spend).
>
It should be noted that P2PK keys still hold millions of bitcoin, and= those encode the entire public key for everyone to see for all time. Thus,= early QC attacks won't need to consider the=C2=A0complexities of the mempo= ol.
>
> In my opinion, one of the last time the subject was addressed on= the mailing list, the description of the state of the quantum computer fie= ld was not realistic and get into risk characterization hyperbole talking a= bout "super-exponential rate" (when indeed there is no empirical realizatio= n=C2=A0that distinct theoretical advance on quantum capabilities=C2=A0can b= e combined with each other) [1].
>
I think it's time to revisit these discussions given IBM's progress. = They've published a two videos in particular that are worth watching; their= keynote from December of last year [2], and their roadmap update from just= last month [3].
>
> On your proposal, there is an immediate observation which comes = to mind, namely why not using one of the algorithm(dilthium, sphincs+, falc= on) which has been through the 3 rounds of NIST cryptanalysis. Apart of the= signature size,which sounds to be smaller, in a network of full-nodes any = PQ signature algorithm should have reasonable verificationperformances.
>
I'm supportive of this consideration. FALCON might be a good substitu= te, and maybe it can be upgraded to HAWK for even better performance depend= ing on how much time there is. According to the BIP, FALCON signatures are = ~10x larger than Schnorr signatures, so this will of course make the transa= ction more expensive, but we also must remember, these signatures will be g= oing into the witness, which already receives a 4x discount. Perhaps the di= scount could be increased further someday to fit more transactions into blo= cks, but this will also likely result in more inscriptions filling unused s= pace also, which permanently increases the burden of running an archive nod= e. Due to the controversy such a change could bring, I would rather any inc= reases in the witness discount be excluded from future activation discussio= ns, so as to be considered separately, even if it pertains to an increase i= n P2QRH transaction size.
=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 acknowledge= 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 HASH= 256 in the output script? I think it's fine for a cryptographic commitment = since it's simply a hash of a hash (MD160 of SHA-256).
>
> Lastly, there is a practical defensive technique that can be imp= lemented today by coin owners to protect in face ofhyptothetical quantum ad= versaries. Namely setting spending scripts to request an artificially infla= ted witness stack,as the cost has to be burden by the spender. I think one = can easily do that with OP_DUP and OP_GREATERTHAN and a bitof stack shuffli= ng. While the efficiency of this technique is limited by the max consensus = size of the script stack(`MAX_STACK_SIZE`) and the max consensus size of st= ack element (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional"scarce coi= ns" pre-requirement on the quantum adversarise to succeed. Shor's algorithm= is only defined under theclassic ressources of computational complexity, t= ime and space.
>
I'm not sure I fully understand this, but even more practically, as m= entioned in the BIP, value can simply be kept in P2WPKH outputs, ideally wi= th a value of fewer than 50 coins per address, and when funds ever need to = be spent, the transaction is signed and submitted out of band to a trusted = mining pool, ideally one that does KYC, so it's known which individual mine= rs get to see the public key before it's mined. It's not perfect, since thi= s relies on exogenous security assumptions, which is why P2QRH is proposed.
>
> Best,Antoine
> [1]=C2=A0https://freicoin.substack.co= m/p/why-im-against-taproot
>
=C2=A0
I'm grateful you took the time to review the BIP and offer your detai= led insights.
=C2=A0
[1] =E2=80=9CThe impact of hardware specifications on reaching quantu= m advantage in the fault tolerant regime,=E2=80=9D 2022=C2=A0-=C2=A0http= s://pubs.aip.org/avs/aqs/article/4/1/013801/2835275/The-impact-of-hardware-= specifications-on-reaching
[2]=C2=A0https://www.youtube.com/watch?v=3DDe2IlWji= 8Ck
[3]=C2=A0https://www.youtube.com/watch?v=3Dd5aIx79O= Tps
=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 du= e to how mature it is in comparison to SQIsign. It's already in its third r= ound and has several standards-compliant implementations, and it has an act= ual specification rather than just a research paper. One thing to consider = is that NIST-I round 3 signatures are 982 bytes in size, according to what = I was able to find in the documents hosted by the SPHINCS website.
> > https://web.archive.org/web/20230711000109if_/http://sph= incs.org/data/sphincs+-round3-submission-nist.zip
> > =C2=A0
> > One way to handle this is to introduce this as a separate a= ddress type than SQIsign. That won't require OP_CAT, and I do want to keep = this soft fork limited in scope. If SQIsign does become significantly broke= n, in this hopefully far future scenario, I might be supportive of an incre= ase in the witness discount.
> > =C2=A0
> > Also, I've made some additional changes based on your feedb= ack on X. You can review them here if you so wish:
> > https://github.com/cry= ptoquick/bips/pull/5/files?short_path=3D917a32a#diff-917a32a71b69bf62d7c85d= fb13d520a0340a30a2889b015b82d36411ed45e754
> >
> >
> > On Friday, June 14, 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre= -Luc Dallaire-Demers wrote:
> > > SQIsign is blockchain friendly but also very new, I wo= uld recommend adding a hash-based backup key in case an attack on SQIsign i= s found in the future (recall that SIDH broke over the span of a weekend=C2= =A0https://eprint.iacr.org/2022/975.pdf).
> > > Backup keys can be added in the form of a Merkle tree = where one branch would contain the SQIsign public key and the other the pub= lic key of the recovery hash-based scheme. For most transactions it would o= nly add one bit to specify the SQIsign branch.
> > > The hash-based method could be Sphincs+, which is stan= dardized by NIST but requires adding extra code, or Lamport, which is not s= tandardized but can be verified on-chain with OP-CAT.
> > >
> > > 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 concr= ete proposal for adding quantum resistance to Bitcoin. We will need to pick= a signature algorithm, implement it, and have it ready in event of quantum= emergency. There will be time to adopt it. Importantly, this first step is= a more substantive answer to those with concerns beyond, "quantum computer= s may pose a threat, but we likely don't have to worry about that for a lon= g time". Bitcoin development and activation is slow, so it's important that= those with low time preference start discussing this as a serious possibil= ity sooner rather than later. This is meant to be the first in a series of= BIPs regarding a hypothetical "QuBit" soft fork. The BIP is intended to pr= opose concrete solutions, even if they're early and incomplete, so that Bit= coin developers are aware of the existence of these solutions and their pot= ential. This is just a rough draft and not the finished BIP. I'd like to v= alidate the approach and hear if I should continue working on it, whether s= erious changes are needed, or if this truly isn't a worthwhile endeavor rig= ht now.
> > > > =C2=A0
> > > > The BIP can be found here:
> > > > https://gi= thub.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 top= ic in the Google Groups "Bitcoin Development Mailing List" group. To unsubs= cribe from this topic, visit https= ://groups.google.com/d/topic/bitcoindev/Aee8xKuIC2s/unsubscribe. To uns= ubscribe 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-82= 69-4f81fa501627n%40googlegroups.com.

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

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

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