diff options
| -rw-r--r-- | 44/f57af6dbf8fcd05c87b8b5448a2c472fa561c5 | 286 |
1 files changed, 286 insertions, 0 deletions
diff --git a/44/f57af6dbf8fcd05c87b8b5448a2c472fa561c5 b/44/f57af6dbf8fcd05c87b8b5448a2c472fa561c5 new file mode 100644 index 000000000..5563b8348 --- /dev/null +++ b/44/f57af6dbf8fcd05c87b8b5448a2c472fa561c5 @@ -0,0 +1,286 @@ +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. + |