From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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,

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.

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.

Hunter

=
On Monday, February 24, 2025 at 8:27:53=E2=80=AFAM U= TC-7 Jonas Nick wrote:
>= What prevents arbitrary data being hashed and then included in the attesta= tion
> is, each signature public key pair must be able to verify the t= ransaction
> message in order to be considered a valid transaction.

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

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

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

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

and post the data to the chain by spending the output using an attest= ation
structure that includes leafhash1, an empty signature, public_key_sec= p256k1 and
the corresponding signature.

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

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

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

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

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

[0] https://csrc.nist.= gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardiz= ation/evaluation-criteria/security-(evaluation-criteria)

--
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 visit https://groups.google.com/d/msgid/bitcoind= ev/8e1cf1b5-27d1-4510-afec-52fb28959189n%40googlegroups.com.
------=_Part_413863_246398833.1740506638105-- ------=_Part_413862_852546399.1740506638105--