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;"> >= What prevents arbitrary data being hashed and then included in the attesta= tion <br /> > is, each signature public key pair must be able to verify the t= ransaction <br /> > 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 /> > Public keys that are not needed can be excluded by including th= eir hash in the <br /> > 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 /> > I will admit I don't understand this attack. Can you provide mo= re details on <br /> > 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" 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--