Delivery-date: Tue, 25 Feb 2025 12:26:06 -0800 Received: from mail-yw1-f189.google.com ([209.85.128.189]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from <bitcoindev+bncBD3YNWFH7IHBBU6O7C6QMGQECDZREGY@googlegroups.com>) id 1tn1VE-0005ts-IQ for bitcoindev@gnusha.org; Tue, 25 Feb 2025 12:26:06 -0800 Received: by mail-yw1-f189.google.com with SMTP id 00721157ae682-6f2a2ab50f6sf83755467b3.3 for <bitcoindev@gnusha.org>; Tue, 25 Feb 2025 12:26:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1740515158; x=1741119958; 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=vyLvqehAJThQf4wuhXg26Iopi+LWUgzbJrKgoNJr+3s=; b=GUIBppUmxGsqfqvLly0cY6TFE91JuTBb1t4VBMRp0pcgTWHsbniEcjVxSSYPyAhKD0 uEcCEHJDn2wCHSWyACEFWZZ1SgzbwvWp8NNt34t0NlQtlvf7YQZqGlQ531yOWzK+tWJU GNVlmsPvfKIPWp9hTxzIribXIFlEtTWfuSrqqPrLkC7KTAETHywSwldEsBej+4bUiUG9 wnKnLWgol2wEO5VOeSlWrNd2ZPkTIHDPJCFQI6zeQw8h0MDHb/nj6lzhP9p1Sio1aUN7 zmDYKyT1TIXeHfcgz00xm2rURULn+yNELkUE7Cjv0omxSEyY37O0ZhsLRdxadohSpAUC 3mJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740515158; x=1741119958; 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=vyLvqehAJThQf4wuhXg26Iopi+LWUgzbJrKgoNJr+3s=; b=BOLPnGJPxHxx3pypCfEaEOqsWuA3MHUuvNJ0yE514JgsveuTtiKS59htafy9JL1/Ws N5Pf29hNMJKf3rqgcPJGywXL5hox3AnZQZDqFypJWRNSAO5+U9q6rUtvEQ2PUyyEZes4 KOLfH984kSvNz+MogOXlFNbDLRURwizO+tnjY0UqTu1yLettiq7XHyK8yVoG0UhItswl fhOiM7VHSgQRq0NKp5ssatUN7yUxIScjruvVfFQJf9OhMX2vuiApVSGuHJvJpPmMxHKR Dtd8EV7i7GftfDHS3AULEfFsXsTfqTQm87HHluT+xElw2ziDP0A8hklxtqeYmbREeJYH juwQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCVhJp5UxwGgNyllfXJ2aOZoH+T2a4EHcm4szNl/3+DjmC2NDeLIGL+7mshUW0V79fRSUMtNFIcWXXq9@gnusha.org X-Gm-Message-State: AOJu0Yzii+qS0uPXG0L50xiZTHZHGFul6iTdp8Uw/Z4J5SiAPZRin7Nq +w8ZIbadzbEEuMgbWiuAUldh+tFrh5RUjngxRIXqdtkWOEtS+gHY X-Google-Smtp-Source: AGHT+IF8ibsdYI1jr+E1ObOGbairusstBig1RwFvIkGZzr5KfSaSulfIc3KyFc2SRpriQghCfenTng== X-Received: by 2002:a05:690c:6187:b0:6ef:7d51:ebb3 with SMTP id 00721157ae682-6fbcc39428dmr155249507b3.34.1740515158457; Tue, 25 Feb 2025 12:25:58 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVEgB6rBXvHIBYdaFvRZADEDvUTviiChlNUk0iaTz1dTRg== Received: by 2002:a25:e808:0:b0:e60:8c7f:fe47 with SMTP id 3f1490d57ef6-e608c7fff25ls88271276.0.-pod-prod-03-us; Tue, 25 Feb 2025 12:25:55 -0800 (PST) X-Received: by 2002:a05:690c:9c09:b0:6fb:b7b7:f1e5 with SMTP id 00721157ae682-6fbcc781d1cmr154572977b3.14.1740515155103; Tue, 25 Feb 2025 12:25:55 -0800 (PST) Received: by 2002:a81:ad10:0:b0:6fb:3e32:1a09 with SMTP id 00721157ae682-6fbcafd7fe7ms7b3; Tue, 25 Feb 2025 08:54:07 -0800 (PST) X-Received: by 2002:a05:690c:6210:b0:6ef:77e3:efe6 with SMTP id 00721157ae682-6fbcc77d62cmr156010127b3.13.1740502446152; Tue, 25 Feb 2025 08:54:06 -0800 (PST) Date: Tue, 25 Feb 2025 08:54:05 -0800 (PST) From: Hunter Beast <hunter@surmount.systems> To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> Message-Id: <9d6f01ca-9fab-4638-b59b-64db6301c2dbn@googlegroups.com> In-Reply-To: <CABfMNdKy6U+nLbq-nwK53_yiguxqanF1jexYHLGLMyef9cG1mw@mail.gmail.com> References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com> <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com> <16d7adca-a01e-40c5-9570-31967ee339ecn@googlegroups.com> <CABfMNdKy6U+nLbq-nwK53_yiguxqanF1jexYHLGLMyef9cG1mw@mail.gmail.com> Subject: Re: [bitcoindev] P2QRH / BIP-360 Update MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_406880_886688991.1740502445668" X-Original-Sender: hunter@surmount.systems Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: <bitcoindev.googlegroups.com> X-Google-Group-Id: 786775582512 List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com> List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com> List-Archive: <https://groups.google.com/group/bitcoindev List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com> List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>, <https://groups.google.com/group/bitcoindev/subscribe> X-Spam-Score: -0.7 (/) ------=_Part_406880_886688991.1740502445668 Content-Type: multipart/alternative; boundary="----=_Part_406881_1024641612.1740502445668" ------=_Part_406881_1024641612.1740502445668 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Tim, Your spreadsheet makes sense, I think. Does this include an attestation=20 discount? I've also done some similar calculations here: https://x.com/cryptoquick/status/1866986505434264047 On Monday, February 24, 2025 at 8:27:37=E2=80=AFAM UTC-7 Tim Bratton wrote: > I did some quick estimates of the proposals in terms of TPS (Comparison= =20 > chart attached). > > There are tradeoffs to be made for sure. > > Is this in line with what everyone else is thinking too? > > > > > > On Sun, Feb 23, 2025 at 3:53=E2=80=AFPM Hunter Beast <hun...@surmount.sys= tems>=20 > wrote: > >> Hi Jonas, >> >> On Selective Disclosure, >> >> I think we're going to need to add simple multisig semantics to the=20 >> attestation due to its lack of script capability. Would that help? Separ= ate=20 >> multisig semantics like quorum and total would be needed for each class = of=20 >> key, so that even if Schnorr signatures can be broken (or one or two of = the=20 >> other PQC signatures even), they don't count towards the quorum of the= =20 >> other signature types. >> >> On Attestation structure, >> >> What prevents arbitrary data being hashed and then included in the=20 >> attestation is, each signature public key pair must be able to verify th= e=20 >> transaction message in order to be considered a valid transaction. In ot= her=20 >> words, each public key and signature pair is validated against the=20 >> transaction message upon transaction verification. >> >> On Multisignature 256-bit security, >> >> To be honest, I've read this a couple of times and I will admit I don't= =20 >> understand this attack. Can you provide more details on how it works, an= d=20 >> how it might be possible to mitigate? >> >> On General comments, >> >> I agree with the worst-case transaction verification concern. I'll need= =20 >> to put some work into detailing NIST I variants and their signature=20 >> verification times, and then computing worst-case scenarios for differen= t=20 >> discount constants. >> >> On 128-bit security... Yes, I'm coming to realize that too. It's been a= =20 >> common point of feedback. >> >> On adding three schemes, there are a couple of advantages of this. First= ,=20 >> wallets can automatically decide how many signatures to add based on the= =20 >> amount being spent. This then acts as a sort of MEV opportunity for mine= rs,=20 >> because the higher the value of the transaction, the more signatures mig= ht=20 >> be included, which increases fee revenue. Also, it addresses Matt's conc= ern=20 >> about security assumptions. There's a strong desire for SLH-DSA support,= =20 >> even though it's so large. However, from a practicality standpoint=20 >> (thinking of plebs), it will make sense to include the smaller ML-DSA an= d=20 >> FN-DSA also. While it does increase complexity, I believe that a=20 >> libbitcoinpqc library, as mentioned in the BIP, will serve as a useful= =20 >> analogue to libsecp256k1. It's also worth noting that in my position at= =20 >> Anduro, I have resources to put into building such a library. Hopefully= =20 >> this can help meet the expectation of a well specified and implemented= =20 >> consensus level library. >> >> On signature aggregation, yes, I'm excited to see those developments in= =20 >> FN-DSA, and maybe we can see that filter into SLH-DSA as well. Hopefully= =20 >> those improvements will be ready once the time comes to activate. >> >> >> >> On Friday, February 21, 2025 at 3:18:35=E2=80=AFAM UTC-7 Jonas Nick wrot= e: >> >>> Hi Hunter,=20 >>> >>> Thanks for your work on BIP 360. I think now is a good time to develop= =20 >>> and=20 >>> discuss concrete PQ proposals. I have a few questions and comments=20 >>> regarding=20 >>> some aspects of the proposal:=20 >>> >>> Selective disclosure=20 >>> ---=20 >>> >>> From, the output contains a root of a Merkle tree of public key hashes= =20 >>> and=20 >>> spending from this output requires revealing the public keys and their= =20 >>> corresponding valid signatures. More concretely, if the user creates=20 >>> root=20 >>> >>> R =3D MerkleRoot([hash(public_key_falcon_1024),=20 >>> hash(public_key_secp256k1)]),=20 >>> >>> they can spend from R by revealing both public keys and corresponding= =20 >>> signatures.=20 >>> >>> The BIP also mentions that the public keys can be selectively disclosed= :=20 >>> >>> > When spending, if a public key hash is provided in the attestation=20 >>> with an=20 >>> > empty signature, that hash will be used directly in the merkle tree= =20 >>> computation=20 >>> > rather than hashing the full public key.=20 >>> >>> What prevents an quantum adversary, upon observing a spend from R, from= =20 >>> breaking=20 >>> public_key_secp256k1 and then spending from R by providing=20 >>> >>> [=20 >>> hash(public_key_falcon_1024),=20 >>> empty string,=20 >>> public_key_secp256k1,=20 >>> a secp256k1 signature forgery=20 >>> ]?=20 >>> >>> >>> Attestation structure=20 >>> ---=20 >>> >>> The BIP proposes to an attestation structure alongside the witness whic= h=20 >>> is=20 >>> supposed to contain BIP 360 public keys and signatures (instead having= =20 >>> them in=20 >>> the witness). The purpose of this structure is to assign a higher weigh= t=20 >>> discount than the witness. The "Rationale" and "Output Mechanics"=20 >>> sections the=20 >>> BIP describe that, since the attestation structure only contains public= =20 >>> keys and=20 >>> signatures, storage of arbitrary data ("inscriptions") is prevented.=20 >>> >>> Leaving aside that there may be creative ways to embed arbitrary data i= n=20 >>> public=20 >>> keys and signatures as well, selective disclosure of the Merkle tree=20 >>> appears to=20 >>> allow embedding arbitrary data. For instance, a user can create root=20 >>> >>> R =3D MerkleRoot(data, hash(public_key_secp256k1)]),=20 >>> >>> where data is an arbitrary 256-bit string. What prevents the user from= =20 >>> pretending that data is the hash of a public key and providing=20 >>> >>> [=20 >>> data,=20 >>> empty string,=20 >>> public_key_secp256k1,=20 >>> a secp256k1 signature forgery=20 >>> ]=20 >>> >>> in the attestation structure to spend from R?=20 >>> >>> >>> Multi-signature 256-bit security=20 >>> ---=20 >>> >>> The BIP briefly discusses multi-signature scenarios in the script=20 >>> validation=20 >>> section, but the details seem incomplete. From what I can infer, the=20 >>> current=20 >>> specification fails to achieve the claimed 256-bit security.=20 >>> >>> The potential attack would work as follows:=20 >>> 1. The victim provides their public key pk to the adversary.=20 >>> 2. The adversary finds two public keys pk' and pk'' such that=20 >>> MerkleRoot(MultiSig[pk, pk']) =3D MerkleRoot([pk''])=20 >>> 3. The adversary convinces the victim to send coins to=20 >>> MerkleRoot(MultiSig[pk,=20 >>> pk']) and then steals the coins by opening the Merkle tree root to=20 >>> [pk''] and=20 >>> providing a signature for pk''.=20 >>> >>> Since the Merkle root is the 256-bit output of SHA256, the adversary ca= n=20 >>> find=20 >>> this collision with about 2^128 operations.=20 >>> >>> If I remember correctly, this attack was discussed on the mailing list= =20 >>> in the=20 >>> context of segwit and it's the reason why P2WSH (unlike P2PKH) requires= =20 >>> 256-bit=20 >>> hashes.=20 >>> >>> >>> General comments=20 >>> ---=20 >>> >>> I think one of the main questions that the BIP does not currently=20 >>> address is how=20 >>> it affects the worst-case validation cost of a block.=20 >>> >>> Regarding your question:=20 >>> > But if the intention was for 256 bits of security, should level V=20 >>> security be=20 >>> > the default?=20 >>> >>> I don't know what Satoshi's intentions were, but the secp256k1=20 >>> specification=20 >>> clearly indicates 128-bit "strength" ([0], Table 1). I believe that's= =20 >>> fairly=20 >>> well known in the technical Bitcoin space.=20 >>> >>> I am not quite convinced that adding three PQ schemes to the Bitcoin=20 >>> consensus=20 >>> protocol is a great solution to the problem of not being sure which=20 >>> exact scheme=20 >>> to pick. Offloading this decision to users does not really solve this= =20 >>> problem.=20 >>> Moreover, this adds massive complexity and new cryptographic assumption= s=20 >>> to the=20 >>> protocol. Remember that one of the main motivations behind libsecp256k1= ,=20 >>> was=20 >>> that general purpose cryptographic libraries are not well suited for=20 >>> consensus=20 >>> systems. So all new cryptographic schemes added to the consensus=20 >>> protocol need=20 >>> to be exceptionally well specified and implemented. That said, it makes= =20 >>> a lot of=20 >>> sense to design a hybrid scheme that also provides security against a= =20 >>> classic=20 >>> attacker through an established signature scheme (as BIP 360 proposes).= =20 >>> >>> Lastly, I agree that non-interactive aggregation of PQ schemes might be= =20 >>> promising, as it could mitigate about signature size and verification= =20 >>> cost if=20 >>> aggregation is applied on the transaction level. Recently, there has=20 >>> been=20 >>> progress on the security of aggregating hash-based signatures [1] and= =20 >>> Falcon=20 >>> [2].=20 >>> >>> [0] https://www.secg.org/sec2-v2.pdf=20 >>> [1] https://eprint.iacr.org/2025/055=20 >>> [2] https://eprint.iacr.org/2024/311 (Unfortunately, this only beats=20 >>> trivial=20 >>> aggregation (concatenation of signatures) when the number of signatures= =20 >>> is=20 >>> greater than about 110)=20 >>> >>> Jonas=20 >>> >>> --=20 >> You received this message because you are subscribed to the Google Group= s=20 >> "Bitcoin Development Mailing List" group. >> > To unsubscribe from this group and stop receiving emails from it, send an= =20 >> email to bitcoindev+...@googlegroups.com. >> To view this discussion visit=20 >> https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-319= 67ee339ecn%40googlegroups.com=20 >> <https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31= 967ee339ecn%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter> >> . >> > --=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 visit https://groups.google.com/d/msgid/bitcoindev/= 9d6f01ca-9fab-4638-b59b-64db6301c2dbn%40googlegroups.com. ------=_Part_406881_1024641612.1740502445668 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div>Hi Tim,</div><div><br /></div>Your spreadsheet makes sense, I think. D= oes this include an attestation discount?<div><br /></div><div>I've also do= ne some similar calculations here:</div><div><br /></div><div>https://x.com= /cryptoquick/status/1866986505434264047<br /><br /></div><div class=3D"gmai= l_quote"><div dir=3D"auto" class=3D"gmail_attr">On Monday, February 24, 202= 5 at 8:27:37=E2=80=AFAM UTC-7 Tim Bratton wrote:<br/></div><blockquote clas= s=3D"gmail_quote" style=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(= 204, 204, 204); padding-left: 1ex;"><div dir=3D"ltr">I did some quick estim= ates of the proposals in terms of TPS (Comparison chart attached).<br><br>T= here are tradeoffs to be made for sure.<br><br>Is this in line with what ev= eryone else is thinking too?<br><br><br><br><br></div><br><div class=3D"gma= il_quote"></div><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_= attr">On Sun, Feb 23, 2025 at 3:53=E2=80=AFPM Hunter Beast <hun...@surmo= unt.systems> wrote:<br></div></div><div class=3D"gmail_quote"><blockquot= e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s= olid rgb(204,204,204);padding-left:1ex">Hi Jonas,<div><br></div><div>On Sel= ective Disclosure,<br><div><br></div><div>I think we're going to need t= o add simple multisig semantics to the attestation due to its lack of scrip= t capability. Would that help? Separate multisig semantics like quorum and = total would be needed for each class of key, so that even if Schnorr signat= ures can be broken (or one or two of the other PQC signatures even), they d= on't count towards the quorum of the other signature types.</div><div><= br></div><div>On Attestation structure,</div><div><br></div><div>What preve= nts arbitrary data being hashed and then included in the attestation is, ea= ch signature public key pair must be able to verify the transaction message= in order to be considered a valid transaction. In other words, each public= key and signature pair is validated against the transaction message upon t= ransaction verification.</div><div><br></div><div>On Multisignature 256-bit= security,</div><div><br></div><div>To be honest, I've read this a coup= le of times and I will admit I don't understand this attack. Can you pr= ovide more details on how it works, and how it might be possible to mitigat= e?</div><div><br></div><div>On General comments,</div><div><br></div><div>I= agree with the worst-case transaction verification concern. I'll need = to put some work into detailing NIST I variants and their signature verific= ation times, and then computing worst-case scenarios for different discount= constants.</div><div><br></div><div>On 128-bit security... Yes, I'm co= ming to realize that too. It's been a common point of feedback.</div><d= iv><br></div><div>On adding three schemes, there are a couple of advantages= of this. First, wallets can automatically decide how many signatures to ad= d based on the amount being spent. This then acts as a sort of MEV opportun= ity for miners, because the higher the value of the transaction, the more s= ignatures might be included, which increases fee revenue. Also, it addresse= s Matt's concern about security assumptions. There's a strong desir= e for SLH-DSA support, even though it's so large. However, from a pract= icality standpoint (thinking of plebs), it will make sense to include the s= maller ML-DSA and FN-DSA also. While it does increase complexity, I believe= that a libbitcoinpqc library, as mentioned in the BIP, will serve as a use= ful analogue to libsecp256k1. It's also worth noting that in my positio= n at Anduro, I have resources to put into building such a library. Hopefull= y this can help meet the expectation of a well specified and implemented co= nsensus level library.</div><div><br></div><div>On signature aggregation, y= es, I'm excited to see those developments in FN-DSA, and maybe we can s= ee that filter into SLH-DSA as well. Hopefully those improvements will be r= eady once the time comes to activate.</div><div><br></div><div><br><br></di= v></div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_attr">O= n Friday, February 21, 2025 at 3:18:35=E2=80=AFAM UTC-7 Jonas Nick wrote:<b= r></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex= ;border-left:1px solid rgb(204,204,204);padding-left:1ex">Hi Hunter, <br> <br>Thanks for your work on BIP 360. I think now is a good time to develop = and <br>discuss concrete PQ proposals. I have a few questions and comments rega= rding <br>some aspects of the proposal: <br> <br>Selective disclosure <br>--- <br> <br>From, the output contains a root of a Merkle tree of public key hashes = and <br>spending from this output requires revealing the public keys and their <br>corresponding valid signatures. More concretely, if the user creates ro= ot <br> <br>R =3D MerkleRoot([hash(public_key_falcon_1024), hash(public_key_secp256= k1)]), <br> <br>they can spend from R by revealing both public keys and corresponding s= ignatures. <br> <br>The BIP also mentions that the public keys can be selectively disclosed= : <br> <br> > When spending, if a public key hash is provided in the attestatio= n with an <br> > empty signature, that hash will be used directly in the merkle tr= ee computation <br> > rather than hashing the full public key. <br> <br>What prevents an quantum adversary, upon observing a spend from R, from= breaking <br>public_key_secp256k1 and then spending from R by providing <br> <br>[ <br> hash(public_key_falcon_1024), <br> empty string, <br> public_key_secp256k1, <br> a secp256k1 signature forgery <br>]? <br> <br> <br>Attestation structure <br>--- <br> <br>The BIP proposes to an attestation structure alongside the witness whic= h is <br>supposed to contain BIP 360 public keys and signatures (instead having = them in <br>the witness). The purpose of this structure is to assign a higher weigh= t <br>discount than the witness. The "Rationale" and "Output M= echanics" sections the <br>BIP describe that, since the attestation structure only contains public= keys and <br>signatures, storage of arbitrary data ("inscriptions") is pre= vented. <br> <br>Leaving aside that there may be creative ways to embed arbitrary data i= n public <br>keys and signatures as well, selective disclosure of the Merkle tree ap= pears to <br>allow embedding arbitrary data. For instance, a user can create root <br> <br>R =3D MerkleRoot(data, hash(public_key_secp256k1)]), <br> <br>where data is an arbitrary 256-bit string. What prevents the user from <br>pretending that data is the hash of a public key and providing <br> <br>[ <br> data, <br> empty string, <br> public_key_secp256k1, <br> a secp256k1 signature forgery <br>] <br> <br>in the attestation structure to spend from R? <br> <br> <br>Multi-signature 256-bit security <br>--- <br> <br>The BIP briefly discusses multi-signature scenarios in the script valid= ation <br>section, but the details seem incomplete. From what I can infer, the cu= rrent <br>specification fails to achieve the claimed 256-bit security. <br> <br>The potential attack would work as follows: <br>1. The victim provides their public key pk to the adversary. <br>2. The adversary finds two public keys pk' and pk'' such th= at <br> MerkleRoot(MultiSig[pk, pk']) =3D MerkleRoot([pk'']) <br>3. The adversary convinces the victim to send coins to MerkleRoot(Multi= Sig[pk, <br> pk']) and then steals the coins by opening the Merkle tree root= to [pk''] and <br> providing a signature for pk''. <br> <br>Since the Merkle root is the 256-bit output of SHA256, the adversary ca= n find <br>this collision with about 2^128 operations. <br> <br>If I remember correctly, this attack was discussed on the mailing list = in the <br>context of segwit and it's the reason why P2WSH (unlike P2PKH) requ= ires 256-bit <br>hashes. <br> <br> <br>General comments <br>--- <br> <br>I think one of the main questions that the BIP does not currently addre= ss is how <br>it affects the worst-case validation cost of a block. <br> <br>Regarding your question: <br> > But if the intention was for 256 bits of security, should level V= security be <br> > the default? <br> <br>I don't know what Satoshi's intentions were, but the secp256k1 = specification <br>clearly indicates 128-bit "strength" ([0], Table 1). I believ= e that's fairly <br>well known in the technical Bitcoin space. <br> <br>I am not quite convinced that adding three PQ schemes to the Bitcoin co= nsensus <br>protocol is a great solution to the problem of not being sure which exa= ct scheme <br>to pick. Offloading this decision to users does not really solve this p= roblem. <br>Moreover, this adds massive complexity and new cryptographic assumption= s to the <br>protocol. Remember that one of the main motivations behind libsecp256k1= , was <br>that general purpose cryptographic libraries are not well suited for co= nsensus <br>systems. So all new cryptographic schemes added to the consensus protoc= ol need <br>to be exceptionally well specified and implemented. That said, it makes= a lot of <br>sense to design a hybrid scheme that also provides security against a c= lassic <br>attacker through an established signature scheme (as BIP 360 proposes). <br> <br>Lastly, I agree that non-interactive aggregation of PQ schemes might be <br>promising, as it could mitigate about signature size and verification c= ost if <br>aggregation is applied on the transaction level. Recently, there has be= en <br>progress on the security of aggregating hash-based signatures [1] and F= alcon <br>[2]. <br> <br>[0] <a href=3D"https://www.secg.org/sec2-v2.pdf" rel=3D"nofollow" targe= t=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&= ;q=3Dhttps://www.secg.org/sec2-v2.pdf&source=3Dgmail&ust=3D17405887= 20509000&usg=3DAOvVaw3fFJOIAKo89IIs3crPTtPW">https://www.secg.org/sec2-= v2.pdf</a> <br>[1] <a href=3D"https://eprint.iacr.org/2025/055" rel=3D"nofollow" targe= t=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&= ;q=3Dhttps://eprint.iacr.org/2025/055&source=3Dgmail&ust=3D17405887= 20509000&usg=3DAOvVaw00IxexGYOSEYu_hEhatVUu">https://eprint.iacr.org/20= 25/055</a> <br>[2] <a href=3D"https://eprint.iacr.org/2024/311" rel=3D"nofollow" targe= t=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&= ;q=3Dhttps://eprint.iacr.org/2024/311&source=3Dgmail&ust=3D17405887= 20509000&usg=3DAOvVaw3ZWAieZZJBnvKqcSMHjFH-">https://eprint.iacr.org/20= 24/311</a> (Unfortunately, this only beats trivial <br> aggregation (concatenation of signatures) when the number of signa= tures is <br> greater than about 110) <br> <br>Jonas <br> <br></blockquote></div> <p></p></blockquote></div><div class=3D"gmail_quote"><blockquote class=3D"g= mail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204= ,204,204);padding-left:1ex"> -- <br> You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.<br></blockquote></div><d= iv class=3D"gmail_quote"><blockquote class=3D"gmail_quote" style=3D"margin:= 0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href data-email-masked rel=3D"nofollow">bitcoindev+...@googlegro= ups.com</a>.<br> To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com?utm_med= ium=3Demail&utm_source=3Dfooter" target=3D"_blank" rel=3D"nofollow" dat= a-saferedirecturl=3D"https://www.google.com/url?hl=3Den&q=3Dhttps://gro= ups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%254= 0googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&source=3Dgma= il&ust=3D1740588720509000&usg=3DAOvVaw3ZY9a-nrhNiYB3lFCcHgfu">https= ://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31967ee339e= cn%40googlegroups.com</a>.<br> </blockquote></div> </blockquote></div> <p></p> -- <br /> You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.<br /> To unsubscribe from this group and stop receiving emails from it, send an e= mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind= ev+unsubscribe@googlegroups.com</a>.<br /> To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= bitcoindev/9d6f01ca-9fab-4638-b59b-64db6301c2dbn%40googlegroups.com?utm_med= ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= ev/9d6f01ca-9fab-4638-b59b-64db6301c2dbn%40googlegroups.com</a>.<br /> ------=_Part_406881_1024641612.1740502445668-- ------=_Part_406880_886688991.1740502445668--