Delivery-date: Fri, 21 Feb 2025 02:18:42 -0800
Received: from mail-oo1-f61.google.com ([209.85.161.61])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDD5RM5R7QJRB6NF4G6QMGQE7MGPI7A@googlegroups.com>)
	id 1tlQ7F-00007P-Kg
	for bitcoindev@gnusha.org; Fri, 21 Feb 2025 02:18:42 -0800
Received: by mail-oo1-f61.google.com with SMTP id 006d021491bc7-5f6e2ef3190sf1834439eaf.1
        for <bitcoindev@gnusha.org>; Fri, 21 Feb 2025 02:18:41 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1740133116; cv=pass;
        d=google.com; s=arc-20240605;
        b=IKfjUOgrLybxHf0w9EJgo363UhHprmbY6Y7z0VzgYmBQdF+cviqdSii8edCaWAPcih
         5MTMQPF+Oh5b1kMcgCWIVKT0YtA4KUD0w3n+u+2ZuGYPhRyzHauqw3sK+5fB3frGMOqr
         SpaFXjW73xfClTJZjPItsK1fg7mZ4HJRbVXT1EmDusu7g2UhsQtZLV6iKVDn0tM6TLWc
         VV2y5tgpEJpH3ukjdY4eq2xT7SR4PDYCqQ0W25ovyuGMypVVvv1YnWGzJ6Tf3vANV3Ym
         f/Iu1X8Q9oqAKlaNalbl8jtyAMSA+A3FeH/2aGMUWQ1NbEtkx3Jn85KZm3ULB2RJFR3Y
         1SxA==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:in-reply-to:from:content-language
         :references:to:subject:user-agent:mime-version:date:message-id
         :sender:dkim-signature;
        bh=f7TABnqojRBHldbdRBPugUODAEcUdHnZ3lqnHFLkW+c=;
        fh=u0bBXao5BN7zaYlF6jJbvTcJZTp39rRJTyUU84Tel1o=;
        b=Oy4qS1PgES9OabEGHdJuYeQlzkzFR0ikyVWZ2T+p8kXJL0HH9nHdGpxs9WZLmkdb1Q
         rRohYPR926qdkwiwvkchPUe8cY/Zzi9JoDA3bZdSnfluoWL7yYZwCpi6AEf2/1JKFM8J
         VQuI9CO/3JFLRCc8XdmPi6oLRf/wHYr0X9n3O3LKhlZf4blGh5BRLt9NV/NIJvJLirhC
         uWxDsS2GCdo+BPIXkYIuRMeJwD9+AdZxb0rQmmDnF+tw7VwCqIYcxEqasEjszTJguCu1
         4OKQ9HbxsEt3JwlQe6zaHNAkveRYhb1aqDNqPkgFy9SEcDc74q2vIxCksYLrobH8wVDr
         BvlQ==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Iuziu6H2;
       spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::534 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1740133116; x=1740737916; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:in-reply-to:from:content-language:references:to
         :subject:user-agent:mime-version:date:message-id:sender:from:to:cc
         :subject:date:message-id:reply-to;
        bh=f7TABnqojRBHldbdRBPugUODAEcUdHnZ3lqnHFLkW+c=;
        b=m1Ajx6j4Ksr6PmjIDbXcPJSPw5M5E/83m5fDuIXvgndWiDo23hJoAIg3+RyQtmZX9V
         eYvJxKXUN1H+BT2L7lBItsYjE6bOmCmgCF4VOZpi6F0fYo6CihZ+lcJHwpCdZodxNmC0
         Czw3XZ2s+Uj5f2NniJ/sZW2b02WGJHfxXwy95eu7IKRVmvLa5It83sDSjMl/RUhRCUA6
         AytqGQ8I3bz9qQtZ2v70szFgatczqO3N7ByoZW1guVuKaKGB+Q8bZxqEfwNi+ppSRzPk
         DiNg/1YrzOgxEhd9NK6NKNtyyF8yxWeKCSw0fuYyfYCb+jzYfP6t/GMQ8rpyt3jnajx9
         b7tw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1740133116; x=1740737916;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:in-reply-to:from:content-language:references:to
         :subject:user-agent:mime-version:date:message-id:sender:x-beenthere
         :x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
        bh=f7TABnqojRBHldbdRBPugUODAEcUdHnZ3lqnHFLkW+c=;
        b=RaAs6s5DHxo2JjHMdBp5xjVKiMX2ZY4ElDBeUpTsGUq9vGtnMCk05+5uYcmu7h5J6X
         DZk60vJn40NAIjQNo3/FrKoYbjsaODyLxzqBArr4CYsx0xKWMokCYHNyQKeOKlqau8ki
         nBcwcgHShDlhJGzfYik5cHNFtYB/lVQsgibTfyArvqxRrS6UzBBea64xXcnRPPIz2gjS
         oTmg7VshPDwMTeIYw7q+Jgz+Q2HMoC+sKIdTZ++pmuxu+7p3XlfTSwoZ8oaRFXrtTElf
         cl+Raa0FAUroAOFbXGYh4LtILc2M0KM3cqAGzIeyL77vnKaY9PBVI+K/v/oc2GdkKh4V
         UXNA==
X-Forwarded-Encrypted: i=2; AJvYcCWC3c8xwW+OwfVHVIhcfGrj0vPcNgsVDFccVIUQwCJPzUkj0mRiwkjRcjdAfcUpVZ4DGSwgnRX4MgqI@gnusha.org
X-Gm-Message-State: AOJu0Yz6UbqAzwpZpDVBkvaV6GBL45/5yaFkf20c7oJAK71yrRkl7GE5
	QQe+gPjEId95kRZIdUqcGJrfGZfi+Kzjr5YrkuBazZP4wOXY7sxL
X-Google-Smtp-Source: AGHT+IGZ5xfS2aQ823fhTzEUEzXed51dRNrFgdLtdVF7lB8cvOCy4oA1jPb9N8vwOqz75gt9jCnfew==
X-Received: by 2002:a05:6820:8ca:b0:5fc:f9b4:7f46 with SMTP id 006d021491bc7-5fd199ade92mr2016672eaf.0.1740133115641;
        Fri, 21 Feb 2025 02:18:35 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVHl9ZGwB4yVXEYXF5jIqJPc66vTmZV++IhQa5jEEp4YKw==
Received: by 2002:a05:6820:3d5:b0:5fc:f5f4:d806 with SMTP id
 006d021491bc7-5fd0b0f6611ls810411eaf.1.-pod-prod-00-us; Fri, 21 Feb 2025
 02:18:33 -0800 (PST)
X-Received: by 2002:a05:6808:238e:b0:3f3:d291:f12b with SMTP id 5614622812f47-3f424cf2549mr1571033b6e.18.1740133113525;
        Fri, 21 Feb 2025 02:18:33 -0800 (PST)
Received: by 2002:a05:600c:3c9c:b0:439:a596:e64 with SMTP id 5b1f17b1804b1-439ae26b648ms5e9;
        Fri, 21 Feb 2025 00:54:08 -0800 (PST)
X-Received: by 2002:a5d:5988:0:b0:38f:4a0b:e764 with SMTP id ffacd0b85a97d-38f6e97a74amr2318430f8f.28.1740128046324;
        Fri, 21 Feb 2025 00:54:06 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1740128046; cv=none;
        d=google.com; s=arc-20240605;
        b=CSBVfSZK8xbpgiG2+YbG93y71N4s2pu9oDazAInjEPd9e+JaoT9vXP3kEEf8BsBk9D
         wcVXsGZrZIEHv5neEQg24pC5jSnuQWU0BoDBk19ZjcAzfdW2sSRHt96TzMnPZPKHsnP8
         QqGJcAaqvHzk5aBE4liBUVvuWshqMg9tejvZCjKUQCUPK7eSV1c4d3iC6I0Etxk9b+wE
         QrJRq29iIqTXGNzq8NpXe1XbwfUAAA4ylxumfTHCK5HKtovkL2WG3FgnVi18wv0DnyCr
         Xfhj6TCxAOCkDTyJOk1e9S64bdzNw2owuAklzxaCZfTyfEwxx8qf674jcFmj6aHAzkUM
         NXkg==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=content-transfer-encoding:in-reply-to:from:content-language
         :references:to:subject:user-agent:mime-version:date:message-id
         :sender:dkim-signature;
        bh=auQYy0oJ6+FD9OVThTo2fM7zXNhidX3qtDISdyiUCP0=;
        fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=;
        b=lV5TSMHZ7gTZb/2B4wxh2Akv9+ffDMVcXyrtWFrGC3BCxPU5bn9V5ZlRBpSe6c371f
         fsaqxUKhwsqn26/8P5qRJJuPVQS8cZvfDWeEN1gVAUcHVkAHkhlI6xewbp553sn6PPnH
         KZtU+2+Qu6wgWo4ZEHmzYMT7+B91o51uMuN0sIKI0XswLbUBk2mO0Qvy9gtOZC04RdTf
         afQ2iqKAg7pdB9d5egmODfGSP/+E/FYp/hW1Q2m8Kr4DPpv0CQNrxYJdebG7FbxWksU+
         INdQC6Rx3U1iRQpVGS5lgtpfOjgp/Jqs2jCRrj1NlQhSqcBw01wa4PmqSeJJogBDFVYd
         D9Rg==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=Iuziu6H2;
       spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::534 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-ed1-x534.google.com (mail-ed1-x534.google.com. [2a00:1450:4864:20::534])
        by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-4399c51ec18si2323915e9.1.2025.02.21.00.54.06
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Fri, 21 Feb 2025 00:54:06 -0800 (PST)
Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::534 as permitted sender) client-ip=2a00:1450:4864:20::534;
Received: by mail-ed1-x534.google.com with SMTP id 4fb4d7f45d1cf-5e0373c7f55so2775246a12.0
        for <bitcoindev@googlegroups.com>; Fri, 21 Feb 2025 00:54:06 -0800 (PST)
X-Gm-Gg: ASbGnctDOy02Xz1MmynYtTX6Cs2BY4RSlc9WMVXwc+OW/ftbC4+4ABRHMOhJJQwP4EB
	pLy6Ya8UIsJhWyEiv093//AubVSKiLSCrxyFuUbLUxOx8ZorNBSGTr31J/q6nLvAYRmO49cYet8
	Vi9mgp3itz/vxQCCHYBQ2vHt2knDfivPDqq5Sw0VvhvCp3MfQNQA3Y5wPLBwNV3l9SYismCw/RX
	a4f4tktww5JFEgKa++icCYgYOGYCcx+nIFCWygXQjxQKP8ZEP8IWxYJiV2SuPM+r5ClCf02C4dq
	BKNFVYAREU4BKxs4YuUyxYj2SrfRfPwZ/7fnBSFvTMOu2e6+IX5B9sNAlnpudnpY09GwhHqV
X-Received: by 2002:a05:6402:27d0:b0:5e0:5605:211a with SMTP id 4fb4d7f45d1cf-5e0b7108b2fmr1993317a12.18.1740128045486;
        Fri, 21 Feb 2025 00:54:05 -0800 (PST)
Received: from [192.168.1.55] (91-115-48-225.adsl.highway.telekom.at. [91.115.48.225])
        by smtp.googlemail.com with ESMTPSA id 4fb4d7f45d1cf-5dece287cebsm13288456a12.74.2025.02.21.00.54.03
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Fri, 21 Feb 2025 00:54:04 -0800 (PST)
Sender: Jonas Nick <jonasdnick@gmail.com>
Message-ID: <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com>
Date: Fri, 21 Feb 2025 08:54:02 +0000
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: [bitcoindev] P2QRH / BIP-360 Update
To: bitcoindev@googlegroups.com
References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com>
Content-Language: en-US
From: Jonas Nick <jonasd.nick@gmail.com>
In-Reply-To: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"; format=flowed
X-Original-Sender: jonasdnick@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=Iuziu6H2;       spf=pass
 (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::534
 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com;       dmarc=pass
 (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;       dara=pass header.i=@googlegroups.com
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.5 (/)

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 regarding
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 root

R = MerkleRoot([hash(public_key_falcon_1024), hash(public_key_secp256k1)]),

they can spend from R by revealing both public keys and corresponding 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 an
 > empty signature, that hash will be used directly in the merkle tree 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 which 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 weight
discount than the witness. The "Rationale" and "Output Mechanics" sections the
BIP describe that, since the attestation structure only contains public keys and
signatures, storage of arbitrary data ("inscriptions") is prevented.

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

R = 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 validation
section, but the details seem incomplete. From what I can infer, the 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']) = MerkleRoot([pk''])
3. The adversary convinces the victim to send coins to MerkleRoot(MultiSig[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 can 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) requires 256-bit
hashes.


General comments
---

I think one of the main questions that the BIP does not currently address 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 believe that's fairly
well known in the technical Bitcoin space.

I am not quite convinced that adding three PQ schemes to the Bitcoin consensus
protocol is a great solution to the problem of not being sure which exact scheme
to pick. Offloading this decision to users does not really solve this problem.
Moreover, this adds massive complexity and new cryptographic assumptions to the
protocol. Remember that one of the main motivations behind libsecp256k1, was
that general purpose cryptographic libraries are not well suited for consensus
systems. So all new cryptographic schemes added to the consensus protocol 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 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 cost if
aggregation is applied on the transaction level. Recently, there has been
progress on the security of aggregating hash-based signatures [1] and 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 trivial
     aggregation (concatenation of signatures) when the number of signatures is
     greater than about 110)

Jonas

-- 
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 email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5667eb21-cd56-411d-a29f-81604752b7c4%40gmail.com.