path: root/c0/3f146282f1dbe44848d33cbf92c96f50f942df

Delivery-date: Tue, 25 Feb 2025 12:26:05 -0800
Received: from mail-yb1-f190.google.com ([209.85.219.190])
	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-0005tr-HX
	for bitcoindev@gnusha.org; Tue, 25 Feb 2025 12:26:05 -0800
Received: by mail-yb1-f190.google.com with SMTP id 3f1490d57ef6-e5dd164ee83sf257925276.1
        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=RUM348WlHHC0JzxPe2gbn6Mr7GYByPWzRADz6mX3A2A=;
        b=s/KRl7n38TOUALw5PUZ5KYM27+SgPxI3jqG7NXy4WX/7YzM2i1kr/vxlkkhmq6CZAa
         o6MiqfIBOGaEV66z3bZnbTYKu1ah3yQxHsNbUO0vnZRFvvfNji2OVKZ5UstrZSOPwZeg
         owumQOWmHdHTJ2EpyO5rDFLdYjt0w+Jww0bHhovX3mOsZPq6CLzPXBoNuffd2nnLL8B8
         eSUH0ZrF94gp348IVsQuNw+bg/d1a4+O3Gwe+AJaIwnTIW82qXhjG1tyn6q7GB5tUBMz
         1xS5ntJ14HPOXxSrgyB1FJQdQNOgmyY4qGekPLhjOo3mDl9SCquUYoUjRIjcraS29CXg
         QZvw==
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=RUM348WlHHC0JzxPe2gbn6Mr7GYByPWzRADz6mX3A2A=;
        b=AYjuGWwSMWgigOQcB6IgblLfl0wWMIBNwHB+uQUedn5eIPDRhM+4DJLQUS85vo4Kxt
         Pb5Ve25Bw9zuQrpxvGTCoqQ2uhAgoEzhHCJLGqWOCyLufSXGin4SY0tIAguedC4eQgtm
         rXx98zCcUZ9AtztrDiADK5q6NgMLSXHb//QAV8L4FZR2mFk8ebeB2CYb8/WHCVk3uT5K
         LR1PCcOKgE2BH3ejTRgjS3JeysnBgDaUuJoU+yr3rH9jMgsce5rh4pbjThB8+PyW6Q7c
         1yhHD+EzGPtiY8XN8SYWqSE0zfw/PjUIO3qnGRu+gLm0fiuT3MvjVeVke0wTgATKwBkW
         K6JA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCUYwfizmv04ChmF4e0NwyC7A1bXVgtGC7xPEkZhO4wNc2NMsGNAixoih/AYNmRD02lbDFQbS5lQNlUH@gnusha.org
X-Gm-Message-State: AOJu0Yw78j2HyNez+YDwhNFoWZcINzEWDU9Zr0XOers1MfiDiDsC4Byz
	hglmR+ngoIADHhz1YwMPwQ+sMBptlLcwTF2KslQCKfd6FnpXptJQ
X-Google-Smtp-Source: AGHT+IEy/454IfCi2Aql/Z0PsRk9QVrsV2gPhGbtABeJUmHu89SnwFkvvFSNQPLJRV9hxxtAQKBqYQ==
X-Received: by 2002:a05:6902:1b84:b0:e58:b99:6a5b with SMTP id 3f1490d57ef6-e5e24864353mr16305895276.8.1740515158455;
        Tue, 25 Feb 2025 12:25:58 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVHr1SXQJ9LPuNKgMNe1nNkWVe5UMszas1VhhJbRkT+WKA==
Received: by 2002:a25:bbc7:0:b0:e60:8883:5aa4 with SMTP id 3f1490d57ef6-e6088835d2els555630276.2.-pod-prod-03-us;
 Tue, 25 Feb 2025 12:25:55 -0800 (PST)
X-Received: by 2002:a05:690c:6888:b0:6fb:b36b:300f with SMTP id 00721157ae682-6fbcc81788emr155230147b3.27.1740515155100;
        Tue, 25 Feb 2025 12:25:55 -0800 (PST)
Received: by 2002:a05:690c:600d:b0:6f9:77a0:782b with SMTP id 00721157ae682-6fbcb177b37ms7b3;
        Tue, 25 Feb 2025 10:04:01 -0800 (PST)
X-Received: by 2002:a05:690c:744a:b0:6ef:64e8:c708 with SMTP id 00721157ae682-6fd10a15e15mr37900727b3.17.1740506638561;
        Tue, 25 Feb 2025 10:03:58 -0800 (PST)
Date: Tue, 25 Feb 2025 10:03:58 -0800 (PST)
From: Hunter Beast <hunter@surmount.systems>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <8e1cf1b5-27d1-4510-afec-52fb28959189n@googlegroups.com>
In-Reply-To: <5550807e-0655-4895-bc66-1b67bfde8c3e@gmail.com>
References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com>
 <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com>
 <16d7adca-a01e-40c5-9570-31967ee339ecn@googlegroups.com>
 <5550807e-0655-4895-bc66-1b67bfde8c3e@gmail.com>
Subject: Re: [bitcoindev] P2QRH / BIP-360 Update
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_413862_852546399.1740506638105"
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_413862_852546399.1740506638105
Content-Type: multipart/alternative; 
	boundary="----=_Part_413863_246398833.1740506638105"

------=_Part_413863_246398833.1740506638105
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Jonas,

I think I understand what you're getting at with your first point. The=20
thing is, to be able to include arbitrary data in the hashes provided to=20
resolve the Merkle tree, it would require an extraordinary amount of=20
computation to wind up with enough to store arbitrary data. And remember,=
=20
this is competing with just storing that data in the witness, so it has to=
=20
be 4x more economical. Consider a 1/1024 multisig, and the key being spent=
=20
is at the furthest depth in the tree. This means that they would need to=20
grind generating an elliptic curve public key in the hopes of getting a=20
hash collision just to include 11 hashes, or 352 bytes of arbitrary data.=
=20
This would also have to be a valid public key and signature pair. I don't=
=20
see this approach as being practical.

As for your second point, a 256 bit hash provides 128 bits of security,=20
correct? If so, I think that's still fine. Others in this thread have=20
commented that 256 bits is overkill.

Hunter

On Monday, February 24, 2025 at 8:27:53=E2=80=AFAM UTC-7 Jonas Nick wrote:

> What prevents arbitrary data being hashed and then included in the=20
attestation=20
> is, each signature public key pair must be able to verify the transaction=
=20
> message in order to be considered a valid transaction.=20

This appears to contradict the selective disclosure mechanism described in=
=20
the=20
BIP and this sentence in the "Script Validation" section:=20

> Public keys that are not needed can be excluded by including their hash=
=20
in the=20
> attestation accompanied with an empty signature=20

Even if the selective disclosure vulnerability is fixed by committing to=20
the=20
multisig semantics in the P2QRH output, any unopened public key commitment=
=20
could=20
still be "abused" for arbitrary data storage. Similar to the scenario in my=
=20
previous post, if the root R is MerkleRoot([leafhash1, leafhash2]) and the=
=20
multisig policy is "1-of-2", then we can set=20

leafhash1 :=3D data=20
leafhash2 :=3D hash(public_key_secp256k1)=20

and post the data to the chain by spending the output using an attestation=
=20
structure that includes leafhash1, an empty signature, public_key_secp256k1=
=20
and=20
the corresponding signature.=20

> I will admit I don't understand this attack. Can you provide more details=
=20
on=20
> how it works, and how it might be possible to mitigate?=20

To give more context, this attack is intended as a concrete demonstration=
=20
of how=20
breaking the collision resistance of the hash function used in the Merkle=
=20
tree=20
can enable an adversary to steal coins. Here's a different explanation for=
=20
essentially the same attack in the context of P2SH vs. P2WSH:=20
https://bitcoin.stackexchange.com/a/54847/35586=20

The attack against the BIP's proposed signature scheme (where the Merkle=20
tree is=20
constructed from public keys and then an ordinary signature scheme is=20
applied to=20
one or more of the committed public keys) can be mitigated by using a hash=
=20
function with a larger output space (e.g., SHA-512).=20

However, I'm not suggesting to do this. My point is that while the BIP aims=
=20
for=20
256 bits of security by using NIST strength level V parameters, it does not=
=20
actually achieve that security level (when the adversary can affect any of=
=20
the=20
leaves as in multisignatures, for example).=20

The Bitcoin protocol relies heavily on collision-resistance of SHA-256,=20
which is=20
pretty much the definition of NIST strength level II [0].=20

[0]=20
https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-crypt=
ography-standardization/evaluation-criteria/security-(evaluation-criteria)=
=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 visit https://groups.google.com/d/msgid/bitcoindev/=
8e1cf1b5-27d1-4510-afec-52fb28959189n%40googlegroups.com.

------=_Part_413863_246398833.1740506638105
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Hi Jonas,<div><br /></div><div>I think I understand what you're getting at =
with your first point. The thing is, to be able to include arbitrary data i=
n the hashes provided to resolve the Merkle tree, it would require an extra=
ordinary amount of computation to wind up with enough to store arbitrary da=
ta. And remember, this is competing with just storing that data in the witn=
ess, so it has to be 4x more economical. Consider a 1/1024 multisig, and th=
e key being spent is at the furthest depth in the tree. This means that the=
y would need to grind generating an elliptic curve public key in the hopes =
of getting a hash collision just to include 11 hashes, or 352 bytes of arbi=
trary data. This would also have to be a valid public key and signature pai=
r. I don't see this approach as being practical.</div><div><br /></div><div=
>As for your second point, a 256 bit hash provides 128 bits of security, co=
rrect? If so, I think that's still fine. Others in this thread have comment=
ed that 256 bits is overkill.</div><div><br /></div><div>Hunter<br /><br />=
<div><div dir=3D"auto">On Monday, February 24, 2025 at 8:27:53=E2=80=AFAM U=
TC-7 Jonas Nick wrote:<br /></div><blockquote style=3D"margin: 0px 0px 0px =
0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;"> &gt;=
 What prevents arbitrary data being hashed and then included in the attesta=
tion
<br /> &gt; is, each signature public key pair must be able to verify the t=
ransaction
<br /> &gt; message in order to be considered a valid transaction.
<br />
<br />This appears to contradict the selective disclosure mechanism describ=
ed in the
<br />BIP and this sentence in the "Script Validation" section:
<br />
<br /> &gt; Public keys that are not needed can be excluded by including th=
eir hash in the
<br /> &gt; attestation accompanied with an empty signature
<br />
<br />Even if the selective disclosure vulnerability is fixed by committing=
 to the
<br />multisig semantics in the P2QRH output, any unopened public key commi=
tment could
<br />still be "abused" for arbitrary data storage. Similar to the scenario=
 in my
<br />previous post, if the root R is MerkleRoot([leafhash1, leafhash2]) an=
d the
<br />multisig policy is "1-of-2", then we can set
<br />
<br />leafhash1 :=3D data
<br />leafhash2 :=3D hash(public_key_secp256k1)
<br />
<br />and post the data to the chain by spending the output using an attest=
ation
<br />structure that includes leafhash1, an empty signature, public_key_sec=
p256k1 and
<br />the corresponding signature.
<br />
<br /> &gt; I will admit I don't understand this attack. Can you provide mo=
re details on
<br /> &gt; how it works, and how it might be possible to mitigate?
<br />
<br />To give more context, this attack is intended as a concrete demonstra=
tion of how
<br />breaking the collision resistance of the hash function used in the Me=
rkle tree
<br />can enable an adversary to steal coins. Here's a different explanatio=
n for
<br />essentially the same attack in the context of P2SH vs. P2WSH:
<br /><a href=3D"https://bitcoin.stackexchange.com/a/54847/35586" target=3D=
"_blank" rel=3D"nofollow">https://bitcoin.stackexchange.com/a/54847/35586</=
a>
<br />
<br />The attack against the BIP's proposed signature scheme (where the Mer=
kle tree is
<br />constructed from public keys and then an ordinary signature scheme is=
 applied to
<br />one or more of the committed public keys) can be mitigated by using a=
 hash
<br />function with a larger output space (e.g., SHA-512).
<br />
<br />However, I'm not suggesting to do this. My point is that while the BI=
P aims for
<br />256 bits of security by using NIST strength level V parameters, it do=
es not
<br />actually achieve that security level (when the adversary can affect a=
ny of the
<br />leaves as in multisignatures, for example).
<br />
<br />The Bitcoin protocol relies heavily on collision-resistance of SHA-25=
6, which is
<br />pretty much the definition of NIST strength level II [0].
<br />
<br />[0] <a href=3D"https://csrc.nist.gov/projects/post-quantum-cryptograp=
hy/post-quantum-cryptography-standardization/evaluation-criteria/security-(=
evaluation-criteria)" target=3D"_blank" rel=3D"nofollow">https://csrc.nist.=
gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardiz=
ation/evaluation-criteria/security-(evaluation-criteria)</a>
<br /></blockquote></div></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/8e1cf1b5-27d1-4510-afec-52fb28959189n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/8e1cf1b5-27d1-4510-afec-52fb28959189n%40googlegroups.com</a>.<br />

------=_Part_413863_246398833.1740506638105--

------=_Part_413862_852546399.1740506638105--