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 &lt;hun...@surmo=
unt.systems&gt; 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&#39;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&#39;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&#39;ve read this a coup=
le of times and I will admit I don&#39;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&#39;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&#39;m co=
ming to realize that too. It&#39;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&#39;s concern about security assumptions. There&#39;s a strong desir=
e for SLH-DSA support, even though it&#39;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&#39;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&#39;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> &gt; When spending, if a public key hash is provided in the attestatio=
n with an
<br> &gt; empty signature, that hash will be used directly in the merkle tr=
ee computation
<br> &gt; 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 &quot;Rationale&quot; and &quot;Output M=
echanics&quot; sections the
<br>BIP describe that, since the attestation structure only contains public=
 keys and
<br>signatures, storage of arbitrary data (&quot;inscriptions&quot;) 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&#39; and pk&#39;&#39; such th=
at
<br>    MerkleRoot(MultiSig[pk, pk&#39;]) =3D MerkleRoot([pk&#39;&#39;])
<br>3. The adversary convinces the victim to send coins to MerkleRoot(Multi=
Sig[pk,
<br>    pk&#39;]) and then steals the coins by opening the Merkle tree root=
 to [pk&#39;&#39;] and
<br>    providing a signature for pk&#39;&#39;.
<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&#39;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> &gt; But if the intention was for 256 bits of security, should level V=
 security be
<br> &gt; the default?
<br>
<br>I don&#39;t know what Satoshi&#39;s intentions were, but the secp256k1 =
specification
<br>clearly indicates 128-bit &quot;strength&quot; ([0], Table 1). I believ=
e that&#39;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&amp=
;q=3Dhttps://www.secg.org/sec2-v2.pdf&amp;source=3Dgmail&amp;ust=3D17405887=
20509000&amp;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&amp=
;q=3Dhttps://eprint.iacr.org/2025/055&amp;source=3Dgmail&amp;ust=3D17405887=
20509000&amp;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&amp=
;q=3Dhttps://eprint.iacr.org/2024/311&amp;source=3Dgmail&amp;ust=3D17405887=
20509000&amp;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&quot; 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&amp;utm_source=3Dfooter" target=3D"_blank" rel=3D"nofollow" dat=
a-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp;q=3Dhttps://gro=
ups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%254=
0googlegroups.com?utm_medium%3Demail%26utm_source%3Dfooter&amp;source=3Dgma=
il&amp;ust=3D1740588720509000&amp;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&quot; 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--