From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Sun, 23 Feb 2025 15:53:40 -0800 Received: from mail-yw1-f186.google.com ([209.85.128.186]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tmLn0-0008Jo-VJ for bitcoindev@gnusha.org; Sun, 23 Feb 2025 15:53:40 -0800 Received: by mail-yw1-f186.google.com with SMTP id 00721157ae682-6fbbb28b070sf36386797b3.1 for ; Sun, 23 Feb 2025 15:53:39 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1740354813; x=1740959613; 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=hcOMyY5bo7tGxhVsMV0PPlBMI02j/gl7MS+dNFReaBo=; b=uiO2DB/NESkvZ6ILPCxio+BKGPswf0a2w2+ZqR3I0pVT2Obp+VgAdI1kesEd+9MBEE 71ToqP9t4OJ7UotpC3AsD6N57Uz16NnBZ4aPNxM94RFoO5ESpdj+46bJO1QmdtLEtnSy iYXCCFx2VWq6duqmRHBUnyHmGmJm0/iFC0cV94GEmvDJl9P/d3ERr811KjbOl6651zvv Qv2Nlu3AVgfE/cOnh2NK6DavGWD9l0UVI69qFY+/VfUCoW+QaoXqaqQ2oi4kErsmEQQz a4c0Reri2stpWMr21zf4MUYymqDXdjC/8Zeg5kHIV2QmabfK5PkDHjNioFGtRbcvh24Y 0W1w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740354813; x=1740959613; 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=hcOMyY5bo7tGxhVsMV0PPlBMI02j/gl7MS+dNFReaBo=; b=YnKFV/KTSsp1YOgvAh5KXmis+wqIa6/psjTdz4/HOxhomVoCVFV1QYTv2gipLF/HHK 2TwUrVX/2bjol6zkBDkMpVnmO4se/chq0KVytKDRFSkxm9gCuZpQsLgbbRB6R5Ce2kI+ LMgmoR/UHH4e54ZzVhGJLRM6aEd8Zs3swWJAGWF79B0CNh0ZS5+JyD8GdgT+ivX+tokT ZcnCNgfJGEsylXBIWwHKgz8PHWlT3UnaLX1z/+j/uE96C1EAz14/F+NW7c91e9dwFDuh 1jHDXZ7ljOdvI84vyQSvgTYaYTPFXwvAQNR7chPgmCkFRF+uNLDdDmcWbwI1rdSniQER v5iA== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCX0IX3we7cRM8FuyMFkA0zxcLQW5ZEpaZSKEgUj8YVvpog7EEGSRZL2uWwL6TUFBTm0oiQVRm7/AbLW@gnusha.org X-Gm-Message-State: AOJu0Yyn+x/K8PyU/jcKHkWktq5myVnmsS91gqkU/o1XtLDvo8QxpqIz 6Qyzoan/16p5PH5tWZGIi7Iu7TjP7kzb0cvBvSKwKMEoV++Bfu3b X-Google-Smtp-Source: AGHT+IG+FOqXf/2yHALMM6p/vNinhcCT+xFwt+YI2X9mT/Z58DZcCCiYg6ib07F9qTkVJRN5KVrbgg== X-Received: by 2002:a05:6902:240d:b0:e57:2ff6:945a with SMTP id 3f1490d57ef6-e5e24502779mr7630321276.0.1740354813127; Sun, 23 Feb 2025 15:53:33 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVEFowSPsE1920EA4nqMGw95hIsfcidhVzxLVXfB3+PeaQ== Received: by 2002:a25:9b48:0:b0:e5e:1412:d7d7 with SMTP id 3f1490d57ef6-e5e18e09c2cls3611588276.2.-pod-prod-05-us; Sun, 23 Feb 2025 15:53:30 -0800 (PST) X-Received: by 2002:a05:690c:4d09:b0:6ef:7dde:bdef with SMTP id 00721157ae682-6fbcc383217mr86275507b3.23.1740354810544; Sun, 23 Feb 2025 15:53:30 -0800 (PST) Received: by 2002:a81:ad10:0:b0:6fb:3e32:1a09 with SMTP id 00721157ae682-6fbcafd7fe7ms7b3; Sun, 23 Feb 2025 12:58:09 -0800 (PST) X-Received: by 2002:a05:690c:6c06:b0:6fb:24e1:2d03 with SMTP id 00721157ae682-6fbcc2356edmr86799527b3.10.1740344288756; Sun, 23 Feb 2025 12:58:08 -0800 (PST) Date: Sun, 23 Feb 2025 12:58:08 -0800 (PST) From: Hunter Beast To: Bitcoin Development Mailing List Message-Id: <16d7adca-a01e-40c5-9570-31967ee339ecn@googlegroups.com> In-Reply-To: <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com> References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com> <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com> Subject: Re: [bitcoindev] P2QRH / BIP-360 Update MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_371650_856770385.1740344288302" 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_371650_856770385.1740344288302 Content-Type: multipart/alternative; boundary="----=_Part_371651_924092519.1740344288302" ------=_Part_371651_924092519.1740344288302 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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? Separate= =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 the= =20 transaction message in order to be considered a valid transaction. In other= =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, and= =20 how it might be possible to mitigate? On General comments, I agree with the worst-case transaction verification concern. I'll need to= =20 put some work into detailing NIST I variants and their signature=20 verification times, and then computing worst-case scenarios for different= =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 miners,= =20 because the higher the value of the transaction, the more signatures might= =20 be included, which increases fee revenue. Also, it addresses Matt's concern= =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 and= =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 wrote: > Hi Hunter, > > Thanks for your work on BIP 360. I think now is a good time to develop an= d > discuss concrete PQ proposals. I have a few questions and comments=20 > regarding > some aspects of the proposal: > > Selective disclosure > --- > > From, the output contains a root of a Merkle tree of public key hashes an= d > spending from this output requires revealing the public keys and their > corresponding valid signatures. More concretely, if the user creates root > > R =3D MerkleRoot([hash(public_key_falcon_1024), hash(public_key_secp256k1= )]), > > they can spend from R by revealing both public keys and corresponding=20 > signatures. > > The BIP also mentions that the public keys can be selectively disclosed: > > > When spending, if a public key hash is provided in the attestation with= =20 > an > > empty signature, that hash will be used directly in the merkle tree=20 > computation > > rather than hashing the full public key. > > What prevents an quantum adversary, upon observing a spend from R, from= =20 > breaking > public_key_secp256k1 and then spending from R by providing > > [ > hash(public_key_falcon_1024), > empty string, > public_key_secp256k1, > a secp256k1 signature forgery > ]? > > > Attestation structure > --- > > The BIP proposes to an attestation structure alongside the witness which = is > supposed to contain BIP 360 public keys and signatures (instead having=20 > them in > the witness). The purpose of this structure is to assign a higher weight > discount than the witness. The "Rationale" and "Output Mechanics" section= s=20 > the > BIP describe that, since the attestation structure only contains public= =20 > keys and > signatures, storage of arbitrary data ("inscriptions") is prevented. > > Leaving aside that there may be creative ways to embed arbitrary data in= =20 > public > keys and signatures as well, selective disclosure of the Merkle tree=20 > appears to > allow embedding arbitrary data. For instance, a user can create root > > R =3D MerkleRoot(data, hash(public_key_secp256k1)]), > > where data is an arbitrary 256-bit string. What prevents the user from > pretending that data is the hash of a public key and providing > > [ > data, > empty string, > public_key_secp256k1, > a secp256k1 signature forgery > ] > > in the attestation structure to spend from R? > > > Multi-signature 256-bit security > --- > > The BIP briefly discusses multi-signature scenarios in the script=20 > validation > section, but the details seem incomplete. From what I can infer, the=20 > current > specification fails to achieve the claimed 256-bit security. > > The potential attack would work as follows: > 1. The victim provides their public key pk to the adversary. > 2. The adversary finds two public keys pk' and pk'' such that > MerkleRoot(MultiSig[pk, pk']) =3D MerkleRoot([pk'']) > 3. The adversary convinces the victim to send coins to=20 > MerkleRoot(MultiSig[pk, > pk']) and then steals the coins by opening the Merkle tree root to [pk'']= =20 > and > providing a signature for pk''. > > Since the Merkle root is the 256-bit output of SHA256, the adversary can= =20 > find > this collision with about 2^128 operations. > > If I remember correctly, this attack was discussed on the mailing list in= =20 > the > context of segwit and it's the reason why P2WSH (unlike P2PKH) requires= =20 > 256-bit > hashes. > > > General comments > --- > > I think one of the main questions that the BIP does not currently address= =20 > is how > it affects the worst-case validation cost of a block. > > Regarding your question: > > But if the intention was for 256 bits of security, should level V=20 > security be > > the default? > > I don't know what Satoshi's intentions were, but the secp256k1=20 > specification > clearly indicates 128-bit "strength" ([0], Table 1). I believe that's=20 > fairly > well known in the technical Bitcoin space. > > I am not quite convinced that adding three PQ schemes to the Bitcoin=20 > consensus > protocol is a great solution to the problem of not being sure which exact= =20 > scheme > to pick. Offloading this decision to users does not really solve this=20 > problem. > Moreover, this adds massive complexity and new cryptographic assumptions= =20 > to the > protocol. Remember that one of the main motivations behind libsecp256k1,= =20 > was > that general purpose cryptographic libraries are not well suited for=20 > consensus > systems. So all new cryptographic schemes added to the consensus protocol= =20 > need > to be exceptionally well specified and implemented. That said, it makes a= =20 > lot of > sense to design a hybrid scheme that also provides security against a=20 > classic > attacker through an established signature scheme (as BIP 360 proposes). > > Lastly, I agree that non-interactive aggregation of PQ schemes might be > promising, as it could mitigate about signature size and verification cos= t=20 > if > aggregation is applied on the transaction level. Recently, there has been > progress on the security of aggregating hash-based signatures [1] and=20 > Falcon > [2]. > > [0] https://www.secg.org/sec2-v2.pdf > [1] https://eprint.iacr.org/2025/055 > [2] https://eprint.iacr.org/2024/311 (Unfortunately, this only beats=20 > trivial > aggregation (concatenation of signatures) when the number of signatures i= s > greater than about 110) > > Jonas > > --=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/= 16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com. ------=_Part_371651_924092519.1740344288302 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hi Jonas,

On Selective Disclosure,

I think we're going to need to add simple multisig semantics to the= attestation due to its lack of script capability. Would that help? Separat= e multisig semantics like quorum and total would be needed for each class o= f key, so that even if Schnorr signatures can be broken (or one or two of t= he other PQC signatures even), they don't count towards the quorum of the o= ther signature types.

On Attestation structure,<= /div>

What prevents arbitrary data being hashed and th= en included in the attestation is, each signature public key pair must be a= ble to verify the transaction message in order to be considered a valid tra= nsaction. In other words, each public key and signature pair is validated a= gainst the 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 u= nderstand this attack. Can you provide more details on how it works, and ho= w it might be possible to mitigate?

On General c= omments,

I agree with the worst-case transaction= verification concern. I'll need to put some work into detailing NIST I var= iants and their signature verification times, and then computing worst-case= scenarios for different discount constants.

On = 128-bit security... Yes, I'm coming to realize that too. It's been a common= point of feedback.

On adding three schemes, the= re are a couple of advantages of this. First, wallets can automatically dec= ide how many signatures to add based on the amount being spent. This then a= cts as a sort of MEV opportunity for miners, because the higher the value o= f the transaction, the more signatures might be included, which increases f= ee revenue. Also, it addresses Matt's concern about security assumptions. T= here's a strong desire for SLH-DSA support, even though it's so large. Howe= ver, from a practicality standpoint (thinking of plebs), it will make sense= to include the smaller ML-DSA and FN-DSA also. While it does increase comp= lexity, I believe that a libbitcoinpqc library, as mentioned in the BIP, wi= ll serve as a useful analogue to libsecp256k1. It's also worth noting that = in my position at Anduro, I have resources to put into building such a libr= ary. Hopefully this can help meet the expectation of a well specified and i= mplemented consensus level library.

On signature= aggregation, yes, I'm excited to see those developments in FN-DSA, and may= be we can see that filter into SLH-DSA as well. Hopefully those improvement= s will be ready once the time comes to activate.



On Friday, February 21, 2025 at 3:18:35=E2=80=AFAM UTC-7 Jo= nas Nick wrote:
Hi Hunter,

Thanks for your work on BIP 360. I think now is a good time to develop = and
discuss concrete PQ proposals. I have a few questions and comments rega= rding
some aspects of the proposal:

Selective disclosure
---

From, the output contains a root of a Merkle tree of public key hashes = and
spending from this output requires revealing the public keys and their
corresponding valid signatures. More concretely, if the user creates ro= ot

R =3D MerkleRoot([hash(public_key_falcon_1024), hash(public_key_secp256= k1)]),

they can spend from R by revealing both public keys and corresponding s= ignatures.

The BIP also mentions that the public keys can be selectively disclosed= :

> When spending, if a public key hash is provided in the attestatio= n with an
> empty signature, that hash will be used directly in the merkle tr= ee computation
> rather than hashing the full public key.

What prevents an quantum adversary, upon observing a spend from R, from= breaking
public_key_secp256k1 and then spending from R by providing

[
hash(public_key_falcon_1024),
empty string,
public_key_secp256k1,
a secp256k1 signature forgery
]?


Attestation structure
---

The BIP proposes to an attestation structure alongside the witness whic= h is
supposed to contain BIP 360 public keys and signatures (instead having = them in
the witness). The purpose of this structure is to assign a higher weigh= t
discount than the witness. The "Rationale" and "Output M= echanics" sections the
BIP describe that, since the attestation structure only contains public= keys and
signatures, storage of arbitrary data ("inscriptions") is pre= vented.

Leaving aside that there may be creative ways to embed arbitrary data i= n public
keys and signatures as well, selective disclosure of the Merkle tree ap= pears to
allow embedding arbitrary data. For instance, a user can create root

R =3D MerkleRoot(data, hash(public_key_secp256k1)]),

where data is an arbitrary 256-bit string. What prevents the user from
pretending that data is the hash of a public key and providing

[
data,
empty string,
public_key_secp256k1,
a secp256k1 signature forgery
]

in the attestation structure to spend from R?


Multi-signature 256-bit security
---

The BIP briefly discusses multi-signature scenarios in the script valid= ation
section, but the details seem incomplete. From what I can infer, the cu= rrent
specification fails to achieve the claimed 256-bit security.

The potential attack would work as follows:
1. The victim provides their public key pk to the adversary.
2. The adversary finds two public keys pk' and pk'' such th= at
MerkleRoot(MultiSig[pk, pk']) =3D MerkleRoot([pk''])
3. The adversary convinces the victim to send coins to MerkleRoot(Multi= Sig[pk,
pk']) and then steals the coins by opening the Merkle tree root= to [pk''] and
providing a signature for pk''.

Since the Merkle root is the 256-bit output of SHA256, the adversary ca= n find
this collision with about 2^128 operations.

If I remember correctly, this attack was discussed on the mailing list = in the
context of segwit and it's the reason why P2WSH (unlike P2PKH) requ= ires 256-bit
hashes.


General comments
---

I think one of the main questions that the BIP does not currently addre= ss is how
it affects the worst-case validation cost of a block.

Regarding your question:
> But if the intention was for 256 bits of security, should level V= security be
> the default?

I don't know what Satoshi's intentions were, but the secp256k1 = specification
clearly indicates 128-bit "strength" ([0], Table 1). I believ= e that's fairly
well known in the technical Bitcoin space.

I am not quite convinced that adding three PQ schemes to the Bitcoin co= nsensus
protocol is a great solution to the problem of not being sure which exa= ct scheme
to pick. Offloading this decision to users does not really solve this p= roblem.
Moreover, this adds massive complexity and new cryptographic assumption= s to the
protocol. Remember that one of the main motivations behind libsecp256k1= , was
that general purpose cryptographic libraries are not well suited for co= nsensus
systems. So all new cryptographic schemes added to the consensus protoc= ol need
to be exceptionally well specified and implemented. That said, it makes= a lot of
sense to design a hybrid scheme that also provides security against a c= lassic
attacker through an established signature scheme (as BIP 360 proposes).

Lastly, I agree that non-interactive aggregation of PQ schemes might be
promising, as it could mitigate about signature size and verification c= ost if
aggregation is applied on the transaction level. Recently, there has be= en
progress on the security of aggregating hash-based signatures [1] and F= alcon
[2].

[0] https://www.secg.org/sec2= -v2.pdf
[1] https://eprint.iacr.org/2= 025/055
[2] https://eprint.iacr.org/2= 024/311 (Unfortunately, this only beats trivial
aggregation (concatenation of signatures) when the number of signa= tures is
greater than about 110)

Jonas

--
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/16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com.
------=_Part_371651_924092519.1740344288302-- ------=_Part_371650_856770385.1740344288302--