Delivery-date: Sun, 16 Jun 2024 18:24:57 -0700 Received: from mail-yb1-f187.google.com ([209.85.219.187]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1sJ17A-0000c4-F9 for bitcoindev@gnusha.org; Sun, 16 Jun 2024 18:24:57 -0700 Received: by mail-yb1-f187.google.com with SMTP id 3f1490d57ef6-dff2f9f01f7sf2538067276.1 for ; Sun, 16 Jun 2024 18:24:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1718587490; x=1719192290; 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=1J+/ci698KkDOH8Vb/iKZWy8oMrAHhoHGxdxqhBz1SU=; b=BzTYpg567PiMzkCdFQ4kUJQdChxR2jVtBtQptZ6s2FcYmIgPYPyrKEpLxw8I+1Df+X ShrmmvExe5lKW215VTtb7tEMbumjiJlkuj5RWjOiOWnpz5hc700XkKS7caZtOdLwLzWE 9HG0un1H8/hDMYV+HbFyDMkab7hDjesht/1ZVbPYZlJmEZRurPvmP3bGNiwEv5lrvOQb TLCPGhNe/3ng1zeZe200W0w0jM8VkI2LOh7p0HThflQGnSCldQxUdfAYChnBnXmEw1TK WPHEeJp/CRDgHUsll23jWxO4qq3t8bN4qvToo60yW8VX5gwJaSMvtkG7pOZQg7hXBjze V5FA== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1718587490; x=1719192290; 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=1J+/ci698KkDOH8Vb/iKZWy8oMrAHhoHGxdxqhBz1SU=; b=m+yHUDIwG1PbjrC2b/pB4+qAVkqDnCmYEJj41wBp4v2JGqtVuvxNHhpqZ651DvYRbe 2Wzna20PdlBBrVMLxRPpuYMLBhDs+6At93sRr/Yro4pO3dLIGSeCok+/xlqdzInJHL9a rGaXyCQw1L8WrE8TsNPjEW0Tq/uNZp0t7YYqsBYngcprQtz7AMMGlQs9lZmy92GxM/xF +t49xFOkgM7iLqWGV2wD/0iE2Uilk5eAeuUMQov4A0TT/kFgSbQnsvCpxJjNNQhAfF3a j9MC1oXaX/PN1/F+Ucvvke60iuZlzbKoqJUvQPuGk/zzZ7p7Z5F1EiOBet7S3/GDdCDP BULw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1718587490; x=1719192290; 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=1J+/ci698KkDOH8Vb/iKZWy8oMrAHhoHGxdxqhBz1SU=; b=RRnFfDXZ63M2ZevJZCyIVgd/Cl58qjDytcJFokgjFxN+yana3Ivq8QiRgaHxpyldjS Gc0N9m8n5xlolJqFc3c+RkR6NDFa+zzxLXRy+py3YAjkR3/lQX3wOJnG7oqKdxHHnb29 Pz8EdmCxv84QcQ/c0C+Xr7Qnu6JIhH50YFtRyQrGxhbWZs8iWPHPPKN3SEJyPv185Jdb FvTMRhejyaxZuwhLVqCVfHpZQG0kZkLPmxSlh46IwPailn9nDZYvV1JI22JCM36HXhpw WlIb3qR9ReS/CYBLXDC4obtq+n6eMEbSHkTjRJNrMoVaUtZQi72a/K+yGUyvUsGfSN+O L2Lg== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCWvhK+UjaZgHXTmUF+r2/ZFj5fTSOPLY8n/P7IrqFAYNHMuuDL+aBj31A6xogbSwE2asRSqAMgcwexFOl3QUWAJC/6VPjc= X-Gm-Message-State: AOJu0YwS6VJTmUf+t6mzJ49++glaZvy8hPNfYaxouIZ4w4yqjpfXahX+ dL5YslZnXuYYWEqk0Iu183BTKzCyuSeZsdOgRFtfiBICPxHuMskq X-Google-Smtp-Source: AGHT+IF8QVkWE2w/W+BBAI3urqDOREZFAp5QsA+R7/5MaL5fePyXrdzhb9Bke8Fpm+S9lwOaXlhKow== X-Received: by 2002:a05:6902:1201:b0:dff:2a78:fbe8 with SMTP id 3f1490d57ef6-dff2a78fde8mr5707218276.49.1718587489612; Sun, 16 Jun 2024 18:24:49 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com Received: by 2002:a05:6902:1505:b0:dff:7a3:b0d with SMTP id 3f1490d57ef6-dff07a311bfls4983529276.0.-pod-prod-07-us; Sun, 16 Jun 2024 18:24:48 -0700 (PDT) X-Received: by 2002:a05:6902:2b10:b0:dfa:5a23:379e with SMTP id 3f1490d57ef6-dff153cd4b2mr3114081276.4.1718587488025; Sun, 16 Jun 2024 18:24:48 -0700 (PDT) Received: by 2002:a0d:f244:0:b0:620:26bb:319f with SMTP id 00721157ae682-6321bacb6c0ms7b3; Sun, 16 Jun 2024 18:07:47 -0700 (PDT) X-Received: by 2002:a05:690c:700e:b0:627:a962:4252 with SMTP id 00721157ae682-63224613c12mr21689127b3.7.1718586466437; Sun, 16 Jun 2024 18:07:46 -0700 (PDT) Date: Sun, 16 Jun 2024 18:07:46 -0700 (PDT) From: Antoine Riard To: Bitcoin Development Mailing List Message-Id: <87b4e402-39d8-46b0-8269-4f81fa501627n@googlegroups.com> In-Reply-To: References: <62fd28ab-e8b5-4cfc-b5ae-0d5a033af057n@googlegroups.com> Subject: [bitcoindev] Re: Proposing a P2QRH BIP towards a quantum resistant soft fork MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_200558_411727636.1718586466160" 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_200558_411727636.1718586466160 Content-Type: multipart/alternative; boundary="----=_Part_200559_122869671.1718586466160" ------=_Part_200559_122869671.1718586466160 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Hunter Beast, I think any post-quantum upgrade signature algorithm upgrade proposal would= =20 grandly benefit to have Shor's based practical attacks far more defined in the Bitcoin context. As= =20 soon you start to talk about quantum computers there is no such thing as a "quantum computer" though a= =20 wide array of architectures based on a range of technologies to encode qubits on nanoscale physical=20 properties. This is not certain that any Shor's algorithm variant works smoothly=20 independently of the quantum computer architecture considered (e.g gate frequency, gate infidelity, cooling=20 energy consumption) and I think it's an interesting open game-theory problem if you can concentrate a sufficiant= =20 amount of energy before any coin owner moves them in consequence (e.g seeing a quantum break in the=20 mempool and reacting with a counter-spend). 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 was not realistic and get into risk=20 characterization hyperbole talking about "super-exponential rate" (when indeed there is no empirical=20 realization that distinct theoretical advance on quantum capabilities can be combined with each other) [1]. 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 has been through the 3 rounds of NIST=20 cryptanalysis. Apart of the signature size, which sounds to be smaller, in a network of full-nodes any PQ signature=20 algorithm should have reasonable verification performances. Lastly, there is a practical defensive technique that can be implemented=20 today by coin owners to protect in face of hyptothetical quantum adversaries. Namely setting spending scripts to=20 request an artificially inflated witness stack, as the cost has to be burden by the spender. I think one can easily do that= =20 with OP_DUP and OP_GREATERTHAN and a bit of stack shuffling. While the efficiency of this technique is limited by=20 the max consensus size of the script stack=20 (`MAX_STACK_SIZE`) and the max consensus size of stack element=20 (`MAX_SCRIPT_ELEMENT_SIZE`), this adds an additional "scarce coins" pre-requirement on the quantum adversarise to succeed.=20 Shor's algorithm is only defined under the classic ressources of computational complexity, time and space. Best, Antoine [1] https://freicoin.substack.com/p/why-im-against-taproot Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=A9crit : > Good points. I like your suggestion for a SPHINCS+, just due to how matur= e=20 > it is in comparison to SQIsign. It's already in its third round and has= =20 > 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. > > https://web.archive.org/web/20230711000109if_/http://sphincs.org/data/sph= incs+-round3-submission-nist.zip > > 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 th= is=20 > hopefully far future scenario, I might be supportive of an increase in th= e=20 > witness discount. > > Also, I've made some additional changes based on your feedback on X. You= =20 > can review them here if you so wish: > > 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 Dallaire-= Demers=20 > 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 = the=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 branch= =20 >> would contain the SQIsign public key and the other the public key of the= =20 >> recovery hash-based scheme. For most transactions it would only add one = bit=20 >> to specify the SQIsign branch. >> The hash-based method could be Sphincs+, which is standardized by NIST= =20 >> but requires adding extra code, or Lamport, which is not standardized bu= t=20 >> 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 wrot= e: >> >>> The motivation for this BIP is to provide a concrete proposal for addin= g=20 >>> quantum resistance to Bitcoin. We will need to pick a signature algorit= hm,=20 >>> implement it, and have it ready in event of quantum emergency. There wi= ll=20 >>> be time to adopt it. Importantly, this first step is a more substantive= =20 >>> answer to those with concerns beyond, "quantum computers may pose a thr= eat,=20 >>> but we likely don't have to worry about that for a long time". Bitcoin= =20 >>> development and activation is slow, so it's important that those with l= ow=20 >>> time preference start discussing this as a serious possibility sooner= =20 >>> rather than later. >>> >>> This is meant to be the first in a series of BIPs regarding a=20 >>> hypothetical "QuBit" soft fork. The BIP is intended to propose concrete= =20 >>> solutions, even if they're early and incomplete, so that Bitcoin develo= pers=20 >>> are aware of the existence of these solutions and their potential. >>> >>> This is just a rough draft and not the finished BIP. I'd like to=20 >>> validate the approach and hear if I should continue working on it, whet= her=20 >>> serious changes are needed, or if this truly isn't a worthwhile endeavo= r=20 >>> right now. >>> >>> The BIP can be found here: >>> https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki >>> >>> Thank you for your time. >>> >>> --=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/87b4e402-39d8-46b0-8269-4f81fa501627n%40googlegroups.com. ------=_Part_200559_122869671.1718586466160 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

= Hi Hunter= Beast,

I think any post-quantum upgrade signature algorithm upgrade proposa= l would grandly benefit to have
Shor's based practical attacks far more defined in= the Bitcoin context. As soon you start to talk about
quantum computers there is n= o such thing as a "quantum computer" though a wide array of architectures
based on= a range of technologies to encode qubits on nanoscale physical properties.=

= This is not certain that any Shor's algorithm variant works smoothly indepe= ndently of the quantum computer
architecture considered (e.g gate frequency, gate = infidelity, cooling energy consumption) and I think it's
an interesting open game-= theory problem if you can concentrate a sufficiant amount of energy before = any
coi= n owner moves them in consequence (e.g seeing a quantum break in the mempoo= l and reacting with a counter-spend).

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= field was not realistic and get into risk characterization hyperbole talki= ng about
"super-exponential rate" (when indeed there is no empirical r= ealization=C2=A0that distinct theoretical advance on
quantum capabilit= ies=C2=A0can be combined with each other) [1].

<= font color=3D"#1f2328" face=3D"-apple-system, BlinkMacSystemFont, Segoe UI,= Noto Sans, Helvetica, Arial, sans-serif, Apple Color Emoji, Segoe UI Emoji= ">On your proposal, there is = an immediate observation which comes to mind, namely why not using one of t= he algorithm
(dilthium, sphincs+, falcon) which has been through the 3 rounds of N= IST cryptanalysis. Apart of the signature size,
which sounds to be smaller, in a n= etwork of full-nodes any PQ signature algorithm should have reasonable veri= fication
Lastly, there is a practical defensive technique that can be= implemented today by coin owners to protect in face of
= hyptothetical 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 can easi= ly do that with OP_DUP and OP_GREATERTHAN and a bit
<= span style=3D"caret-color: rgb(31, 35, 40);">of stack shuffling. While the = efficiency of this technique is limited by the max consensus size of the sc= ript stack
(`MAX_STACK_SIZE`) and the max consensus size of stack element (`MAX_S= CRIPT_ELEMENT_SIZE`), this adds an additional
"scarce coins" pre-requirement on th= e quantum adversarise to succeed. Shor's algorithm is only defined under th= e
class= ic ressources of computational complexity, time and space.
Best,
Antoine

[1]=C2=A0https://freicoin.substack.com/p/why-im-against-taproot


Le vendredi 14 juin 2024 =C3=A0 15:30:54 UTC+1, Hunter Beast a =C3=A9cri= t=C2=A0:
Good= points. I like your suggestion for a SPHINCS+, just due to how mature it i= s in comparison to SQIsign. It's already in its third round and has sev= eral standards-compliant implementations, and it has an actual specificatio= n rather than just a research paper. One thing to consider is that NIST-I r= ound 3 signatures are 982 bytes in size, according to what I was able to fi= nd in the documents hosted by the SPHINCS website.

<= div>One way to handle this is to introduce this as a separate address type = than SQIsign. That won't require OP_CAT, and I do want to keep this sof= t fork limited in scope. If SQIsign does become significantly broken, in th= is hopefully far future scenario, I might be supportive of an increase in t= he witness discount.

Also, I've made some additi= onal changes based on your feedback on X. You can review them here if you s= o wish:
On Friday, June 14,= 2024 at 8:15:29=E2=80=AFAM UTC-6 Pierre-Luc Dallaire-Demers wrote:
SQIsign is blockchain friendl= y but also very new, I would recommend adding a hash-based backup key in ca= se an attack on SQIsign is found in the future (recall that SIDH broke over= the span of a weekend=C2=A0https://eprint.iacr.org/2022/975.pdf).
Backup keys can be added i= n the form of a Merkle tree where one branch would contain the SQIsign publ= ic key and the other the public key of the recovery hash-based scheme. For = most transactions it would only add one bit to specify the SQIsign branch.<= /div>
The hash-based method could be Sphincs+, which is standardized by= NIST but requires adding extra code, or Lamport, which is not standardized= but can be verified on-chain with OP-CAT.

On Sunday, June 9, 2024 at 1= 2:07:16=E2=80=AFp.m. UTC-4 Hunter Beast wrote:
The motivation for this BIP is to provide a conc= rete proposal for adding quantum resistance to Bitcoin. We will need to pic= k a signature algorithm, implement it, and have it ready in event of quantu= m emergency. There will be time to adopt it. Importantly, this first step i= s a more substantive answer to those with concerns beyond, "quantum co= mputers may pose a threat, but we likely don't have to worry about that= for a long time". Bitcoin development and activation is slow, so it&#= 39;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 first in a series of BIPs regarding a hypothetical "QuBit" s= oft fork. The BIP is intended to propose concrete solutions, even if they&#= 39;re early and incomplete, so that Bitcoin developers are aware of the exi= stence of these solutions and their potential.

This is just a rough = draft and not the finished BIP. I'd like to validate the approach and h= ear if I should continue working on it, whether serious changes are needed,= or if this truly isn't a worthwhile endeavor right now.

--
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/87b4e402-39d8-46b0-8269-4f81fa501627n%40googlegroups.com.=
------=_Part_200559_122869671.1718586466160-- ------=_Part_200558_411727636.1718586466160--