From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 26 Feb 2025 02:00:41 -0800 Received: from mail-oa1-f58.google.com ([209.85.160.58]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tnEDW-0001sL-PE for bitcoindev@gnusha.org; Wed, 26 Feb 2025 02:00:40 -0800 Received: by mail-oa1-f58.google.com with SMTP id 586e51a60fabf-2acd587d640sf5057272fac.0 for ; Wed, 26 Feb 2025 02:00:38 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1740564033; cv=pass; d=google.com; s=arc-20240605; b=SOQ5AB9A2LCqVdzMyO8613v0npvr/2L/j+P42a7uvcnCwKmOo6R770J1YSQNsTECJC yR3LknYhzhdj1CdqCCdH0PzyCA15BfvPG76219VjIuKLU912IhNo4p1Jefio8/kvq7m9 xEvW7lKK4fSzCdxdvQ0M4G7sJ3QY6Xv7Yltmx4Xe+SPWYFo95pQPsy7JV00wVcVyV7DX jDRXuzhFtjwWBblLVpDn8tyZzZiDedtgCK92zHncM9szXt6GlJygeXX42O4zrCjtSKw6 vt/H8wxi/9BkLdK4QAB4xk9rodZRiwknW5+CbA6TWYZF/CV7vZ2hq/u3JCynASxMD+8u C4BQ== 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:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=VMyoyV6hLN4gmRYsoLiGCVtLpjq2bGz0U1sza3QU0JI=; fh=8IxpodaC2FclbY48MT8yjaaWdCCzi1CuB3Vu7oEZSyM=; b=QcC3bHcGmHBNgRywDKgI5fndOyfEkHU/lWEvPwsq35GxJQ5VlAcB8rINNZ059ofAzl /a3ImSRoC6vxcwYFrXgPf8gD6Ud/BlXsLvbElJ5HVzvWm18wOO0XKJ7N2OmL27VDaAXH DuUGYsrtCw9gJoumZS9dD/qxT+F3h2M8FZ3XcM9uELX05YpydwX5FG3HNoz5vBVJe1nB CT6TxnIi2N+KO8ctylztXaXDoBUpaqlleSDO/sgqAInd5HP4k1c0h4s8mn2Py4XRfoD9 +FvZUq0YIa7xKRsQi573PNNvDCtqsIhqocuvBXtml13wStPgf6ewo/NoSAGEcI8u6RRA WSmw==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=hA+GaAeu; spf=pass (google.com: domain of tim.bratton@gmail.com designates 2a00:1450:4864:20::62a as permitted sender) smtp.mailfrom=tim.bratton@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=googlegroups.com; s=20230601; t=1740564033; x=1741168833; 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:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=VMyoyV6hLN4gmRYsoLiGCVtLpjq2bGz0U1sza3QU0JI=; b=Ahk+nXxzPv1Js6JgUvVLsm8oxmQnaLXC+q26BoDLwNqqg3s++UuTBf+2b0THkpO7jt uzgsFdt4zeoQg8qrOf9HLeK2miknAF1GEzuhYSDhdK7er0GE9WNJUzwxq1Ssm1KNGvUV gJiCvBkI1r7U07X/w9YGDNZesQfHhJnEBpApO1/y7mn16dT7sgmWlhsRw66FuG+Dc2DG oF8U71V/mQ5gfQZFPPJ0Ccs5iCiJdhL061RwlNzo6V1aMTVZYy9L4/Jd0X8J5/iMqoX5 EuUCJezDIolS2RiHrX1HkQPb/fMlBGGklmXSwDxTqv1yaourSlij7n+H0Cc7ZGdfXCsq aPyQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1740564033; x=1741168833; 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:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=VMyoyV6hLN4gmRYsoLiGCVtLpjq2bGz0U1sza3QU0JI=; b=byMI3UwK/g6CXpMga+xqT4dFLZpHIdnOnHH9ORbGuZa9+S310ypZLI2Tpn7Bb9oY7f 1RjUaTW4lqIFuwA+r7p1fPZYzggaHTxTKZaW65ScFnRdNrjFPK7l9Q9RZT0Q9Ig29tQ2 xMOeC5xScFSP6BEqSuJWa0qygZabVB/YbFPjvk43jm9oqyIHBYI37Juzu22c/YMQTQZW DBVhLcs5AuZ+qLcrXGbcpQFU0ohOSO2JHyZAGuAy+7CG3Z/iTtnryqpnsWo5wzAe1mtj sSwm24MTt09TGDdUo4KeGogYTbSGOxFD9EEY1Ke6osw12H2qMxlziBhpye14/5EqAvwI x+Qw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740564033; x=1741168833; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:to:subject:message-id:date:from:in-reply-to :references:mime-version:x-beenthere:x-gm-message-state:sender:from :to:cc:subject:date:message-id:reply-to; bh=VMyoyV6hLN4gmRYsoLiGCVtLpjq2bGz0U1sza3QU0JI=; b=uj8j1K+QyRxEFl6Cb0pvh/uoj4CofHBFV5zSbd0YN9syqT+jRYPAo9JF6JQu7qnKfP GcYS0fuCT2Vn7yqs3whcVLoHXgg7LqkC3E0fh5ty+aepXTjdM/NDjKnqDDxsXu0UJ3Qx HSU7IwD2xCxtKz93HkRDqdR2OWpTxSH2o3zApqdTisDlMhLacPvueQ5vSBYtWQ3cjD9x 8QjFE7xwqmkZVlTXELBOpdqonlN0lVRCzaoNp+GBa+iDCpHx0+7pvb1ft+rDivgpZKR2 Nx+XgpSxS9YB1xJKbT1CN/PakYZjs8bJvSJ3viBL8zRl5wRehFVbFOrpnriOpYuSZCRQ JI8A== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCWmun4w+hW4kkU24SdLtm7Uu6TyWYEf/jU10uomqZGkG8ZloZOG61ZNQVRVpl95o29IkIZ/sxR0HiTF@gnusha.org X-Gm-Message-State: AOJu0YwmryK8Zu83oJTxoxlgXoeAMnJwAJLzDFJY/riC94mZ0LzmvPjh 7kTAWyBn/PhnV46xPHyPple/2fj3ZFu1C8Q30LsFo0ZFEWkrBe5s X-Google-Smtp-Source: AGHT+IGFkSfenkQQ9mjr5U6iffJIO0APyCKTfvnOJtW+59qPMtHoT+Zt9Fhpbid+gVUXzQpMzZUE9w== X-Received: by 2002:a05:6870:4d0e:b0:2b8:e4b9:47a3 with SMTP id 586e51a60fabf-2c1303cbce4mr1694772fac.22.1740564032594; Wed, 26 Feb 2025 02:00:32 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVHp5PJ3TIBbe3y5mbxhYK1OXN1Ie7tWM5t4aK/8VEUFeA== Received: by 2002:a05:6870:c10f:b0:2a0:1e92:8674 with SMTP id 586e51a60fabf-2c132b5c02els427316fac.1.-pod-prod-08-us; Wed, 26 Feb 2025 02:00:29 -0800 (PST) X-Received: by 2002:a05:6808:118b:b0:3f3:c948:6d28 with SMTP id 5614622812f47-3f547d4b927mr1368983b6e.0.1740564029138; Wed, 26 Feb 2025 02:00:29 -0800 (PST) Received: by 2002:ab3:4887:0:b0:290:2c36:6830 with SMTP id a1c4a302cd1d6-29053c24fb7msc7a; Tue, 25 Feb 2025 16:04:13 -0800 (PST) X-Received: by 2002:a05:651c:2204:b0:2ff:56a6:2992 with SMTP id 38308e7fff4ca-30a80cb7d4bmr40043701fa.37.1740528250808; Tue, 25 Feb 2025 16:04:10 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1740528250; cv=none; d=google.com; s=arc-20240605; b=Tm1TypSq6JcJbd0meeqGQg6UtmDKXUMzPWvTo/w8D/n5SG/ZvNfuiCspE1/kLF5t7+ KNt34tMaOktzFc5v46ArBWk4u7dtrbrA9cMGGY5HU3+8pTFRm77HT+htzfrhOtEvVPVq GLLZmfnr/zq9zKSGeyv6W92tFjRJWZIboukwb2OT6r+VeJappFFTT+LDaNB9fAPAVIN5 BAqqW29YZx1kecarCrcBpxwxfyrBLqLpyk3eJzfKQexL50gBOxbqj0h1zJQg1KrMx/92 D1Jcxz66thwCd/SLkOQyfQvX5zOFLRGAowh1elG0yEu9Jz/j3wZrgVjRV2Gr6o4HjLOJ Ejmw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=to:subject:message-id:date:from:in-reply-to:references:mime-version :dkim-signature; bh=bxX6lbP6uaJSA8FOKJnkHoNUvkY5eLtNgCBjV2njp14=; fh=DMP0F9ULS1guKiqimntQRCN8ZraraesEgQuVcn7F0Z0=; b=XE7lt0ZzqvQ0FXxNjy90pFxXVpi6k2qtha94mSmnfdc8Gnu6yT1dnu/4aUvhygbFjt WZ5p1o1bjRPkWR+N6SnG4V1pyHARU3eFgj26hQI51+A8Dn/DQ6cIaoqeG/TBIZj9NJ1w A1Oh+7r7ko/2CL1tNWu/GSAZhmZLMQGa9Zs0LaXZYtbb+UHvckWsVc/iVPz6jZpqyjOd 8UG3elZHDyO9nav6kCVev1mrAPjGtfm6rbwR7VWtR25ODaJStTtmxP27lqo404llqQWI jbc7xJvKsF07zNl4S0LLRWyOrJuML890JC37B0zeYLTeX81L+tEe0zZFXRHmByz6uNSY VG4Q==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=hA+GaAeu; spf=pass (google.com: domain of tim.bratton@gmail.com designates 2a00:1450:4864:20::62a as permitted sender) smtp.mailfrom=tim.bratton@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-ej1-x62a.google.com (mail-ej1-x62a.google.com. [2a00:1450:4864:20::62a]) by gmr-mx.google.com with ESMTPS id 38308e7fff4ca-30a81a2dd0asi1912441fa.3.2025.02.25.16.04.10 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Tue, 25 Feb 2025 16:04:10 -0800 (PST) Received-SPF: pass (google.com: domain of tim.bratton@gmail.com designates 2a00:1450:4864:20::62a as permitted sender) client-ip=2a00:1450:4864:20::62a; Received: by mail-ej1-x62a.google.com with SMTP id a640c23a62f3a-abbac134a19so950858366b.0 for ; Tue, 25 Feb 2025 16:04:10 -0800 (PST) X-Gm-Gg: ASbGncvnMaOpznuJXkA5DBR+TZrup8108qqSHMa0JE3IDYNvMnMd5Kc0naS+jpZzdoP Q2Z/m/Jsmq/4oL3P+MmuaDsSAdimE3xbUybyq+3KyolRQNii+of1wjzD6/2uEB5ujBbwrIQ0Xzl 2qJv/J9iWieqVb5w1Z9WdhESnRTPk+RR4mvWjykCSl8Q0WeCujmEKDZUQjQvQp X-Received: by 2002:a17:906:328c:b0:ab7:c358:2fec with SMTP id a640c23a62f3a-abed0c6695dmr443144766b.5.1740528248927; Tue, 25 Feb 2025 16:04:08 -0800 (PST) MIME-Version: 1.0 References: <8797807d-e017-44e2-b419-803291779007n@googlegroups.com> <5667eb21-cd56-411d-a29f-81604752b7c4@gmail.com> <16d7adca-a01e-40c5-9570-31967ee339ecn@googlegroups.com> In-Reply-To: From: Tim Bratton Date: Tue, 25 Feb 2025 16:03:56 -0800 X-Gm-Features: AWEUYZm3m2cD4QAMkxj38oaHn3M1utQFJW_z9R_uZs5ieyPGRPyD0cMA-QmG6cU Message-ID: Subject: Re: [bitcoindev] P2QRH / BIP-360 Update To: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="000000000000ffbdf8062f004f58" X-Original-Sender: tim.bratton@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=hA+GaAeu; spf=pass (google.com: domain of tim.bratton@gmail.com designates 2a00:1450:4864:20::62a as permitted sender) smtp.mailfrom=tim.bratton@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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) --000000000000ffbdf8062f004f58 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable *Hi Hunter,* Thanks for sharing your detailed calculations. Your breakdown aligns closely with what I=E2=80=99ve modeled, and I appreciate the depth you went= into on the chain growth rates and hardware implications. Yes, it *does include an attestation discount*. I considered the three primary scenarios you outlined in your analysis: 1. *QuBit16 (16x Attestation Discount):* - *~10MB blocks* - *~3,000 transactions per block* - *~5.6 TPS* (3,000 tx/block =C3=B7 600 seconds per block) - *~500GB annual chain growth* 2. *QuBit64 (64x Attestation Discount):* - *~17MB blocks* - *~5,000 transactions per block* - *~8.3 TPS* - *~900GB annual chain growth* 3. *QuBitWit (No Attestation Discount):* - *~3.5MB blocks* - *~1,000 transactions per block* - *~1.7 TPS* - *~185GB annual chain growth* - The *QuBit64 scenario* offers the *highest TPS (~8.3)* but comes with *significant chain growth (~900GB/year)*, which could present hardware challenges for personal node operators. - The *QuBit16 scenario* is a *balanced approach* with *moderate TPS (~5.6)* and *more manageable chain growth (~500GB/year)*. - Without an attestation discount (*QuBitWit*), the TPS drops dramatically to *~1.7*, although this would keep storage growth more manageable. - Given Bitcoin=E2=80=99s current TPS is around *7* (with SegWit and Tap= root improvements), the *QuBit64 scenario* would provide a *comparable throughput* with the added benefit of quantum resistance. - However, the *hardware demands* (with nearly *1TB of chain growth per year*) could limit *decentralization* if smaller node operators struggle to keep up. - The *QuBit16 approach* feels like a *sweet spot*, offering *decent TPS= * and a *storage growth rate* that aligns better with current node capabilities. - *Consensus Preference:* Exchanges and miners, having the most at stake, would likely favor *higher TPS (QuBit64)* for operational efficiency. - *Node Decentralization:* From a decentralization perspective, *QuBit16= * might be more appealing due to lower storage demands. - *Future Hardware Improvements:* As *8TB+ NVMe drives* become more accessible and affordable, the higher chain growth rates may become less concerning. Would love to hear if others in the community lean toward maximizing TPS ( *QuBit64*) or maintaining lower storage requirements (*QuBit16*). Also, how much would decentralization concerns influence the final consensus here? On Tue, Feb 25, 2025 at 12:25=E2=80=AFPM Ian Quantum wrote: > FALCON+ is more likely to get NIST approval. They struggled to get the > algorithm over "80 bits of security" even with a significant set of > improvements. I don't know if this affects the aggregation features, it > would take significant research. The dramatic security improvements of > FALCON+ only cost 5% and 0 bytes additional overhead. > https://eprint.iacr.org/2024/1769.pdf > > SECP256k1 had significant reductions to it's security over the last 16 > years but none of the attacks detailed by Bernstein directly impact the > security as implemented into Bitcoin. (Mitigations and non-interactive > signing, salt and hash were excellent design choices.) > > I would suggest delaying FALCON or FALCON+ until standardized. There are > significant weaknesses but no full break. The brittleness of the random > numbers, exposure to inverse function and a lot "weaker than expected" > parameters would suggest caution. Once standardized I would suggest rapid > implementation but not until then. > > NTRU Prime is a favored alternate candidate of mine, as communicated > previously. Cryptographers suspect that NIST has again inserted PQC > backdoors following the last 3 public key standards being standardized wi= th > very suspicious parameters. (P224, P256, P384) > > I hope we can get some momentum around protecting Bitcoin. 1-6 million > (depending on estimate) BTC have known public keys and while most could > transfer to p2pkh the creation of quantum safe addresses is a strong > signal. The implementation of post quantum cryptography is also required = by > many government agencies around the world, including the White House. > Ian Smith > Migrate to Quantum Safety before 2027 > > On Mon, Feb 24, 2025, 12:53=E2=80=AFAM Hunter Beast > wrote: > >> 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? Separ= ate >> multisig semantics like quorum and total would be needed for each class = of >> key, so that even if Schnorr signatures can be broken (or one or two of = the >> other PQC signatures even), they don't count towards the quorum of the >> other signature types. >> >> On Attestation structure, >> >> What prevents arbitrary data being hashed and then included in the >> attestation is, each signature public key pair must be able to verify th= e >> transaction message in order to be considered a valid transaction. In ot= her >> words, each public key and signature pair is validated against 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 >> understand this attack. Can you provide more details on how it works, an= d >> how it might be possible to mitigate? >> >> On General comments, >> >> I agree with the worst-case transaction verification concern. I'll need >> to put some work into detailing NIST I variants and their signature >> verification times, and then computing worst-case scenarios for differen= t >> 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, there are a couple of advantages of this. First= , >> wallets can automatically decide how many signatures to add based on the >> amount being spent. This then acts as a sort of MEV opportunity for mine= rs, >> because the higher the value of the transaction, the more signatures mig= ht >> be included, which increases fee revenue. Also, it addresses Matt's conc= ern >> about security assumptions. There's a strong desire for SLH-DSA support, >> even though it's so large. However, from a practicality standpoint >> (thinking of plebs), it will make sense to include the smaller ML-DSA an= d >> FN-DSA also. While it does increase complexity, I believe that a >> libbitcoinpqc library, as mentioned in the BIP, will 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 library. Hopefully >> this can help meet the expectation of a well specified and implemented >> consensus level library. >> >> On signature aggregation, yes, I'm excited to see those developments in >> FN-DSA, and maybe we can see that filter into SLH-DSA as well. Hopefully >> 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 wrot= e: >> >>> 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 =3D 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 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 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 i= n >>> 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 =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 >>> 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']) =3D 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 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) 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 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 >>> 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 Group= s >> "Bitcoin Development Mailing List" group. >> To unsubscribe from this group and stop receiving emails from it, send a= n >> email to bitcoindev+unsubscribe@googlegroups.com. >> To view this discussion visit >> https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-319= 67ee339ecn%40googlegroups.com >> >> . >> > -- > 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/CA%2B7C%2BcYY_97y_QsSON5U3y7= v4a0usGaGmcD%2Br%3D8Y05p5Cwmp5w%40mail.gmail.com > > . > --=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/= CABfMNdL9XDBCM4fw9wpGDj8e9yJh%2B-6F6%3DQA8i5MUS%3Dbj1Pcrw%40mail.gmail.com. --000000000000ffbdf8062f004f58 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

Hi Hunter,

Thanks for sharing yo= ur detailed calculations. Your breakdown aligns closely with what I=E2=80= =99ve modeled, and I appreciate the depth you went into on the chain growth= rates and hardware implications.

Yes, it does include an at= testation discount. I considered the three primary scenarios you o= utlined in your analysis:

  1. QuBit16 (16x Attestation Di= scount):

    • ~10MB blocks
    • = ~3,000 transactions per block
    • ~5.6 TPS (3= ,000 tx/block =C3=B7 600 seconds per block)
    • ~500GB annual c= hain growth

  2. QuBit64 (64x Attestation = Discount):

    • ~17MB blocks
    • ~5,000 transactions per block
    • ~8.3 TPS<= /li>
    • ~900GB annual chain growth

  3. QuBitWit (No Attestation Discount):

    • ~3.5M= B blocks
    • ~1,000 transactions per block
    • ~1.7 TPS
    • ~185GB annual chain growth<= /strong>
  • The QuBit64 scenario o= ffers the highest TPS (~8.3) but comes with signif= icant chain growth (~900GB/year), which could present hardware cha= llenges for personal node operators.
  • The QuBit16 scenario is a balanced approach with moderate TPS (= ~5.6) and more manageable chain growth (~500GB/year).
  • Without an attestation discount (QuBitWit), t= he TPS drops dramatically to ~1.7, although this would kee= p storage growth more manageable.
  • Given Bitcoin=E2=80= =99s current TPS is around 7 (with SegWit and Taproot impr= ovements), the QuBit64 scenario would provide a co= mparable throughput with the added benefit of quantum resistance.<= /li>
  • However, the hardware demands (with nearly 1TB of chain growth per year) could limit decentralizatio= n if smaller node operators struggle to keep up.
  • The QuBit16 approach feels like a sweet spot, offe= ring decent TPS and a storage growth rate= that aligns better with current node capabilities.
  • Consensus Preference: Exchanges and miners, having the most = at stake, would likely favor higher TPS (QuBit64) for oper= ational efficiency.
  • Node Decentralization: From a = decentralization perspective, QuBit16 might be more appeal= ing due to lower storage demands.
  • Future Hardware Improveme= nts: As 8TB+ NVMe drives become more accessible a= nd affordable, the higher chain growth rates may become less concerning.

Would love to hear if others in the community lean toward max= imizing TPS (QuBit64) or maintaining lower storage require= ments (QuBit16). Also, how much would decentralization con= cerns influence the final consensus here?




On Tue, Feb 25, 2025 at 12:25=E2=80=AFPM Ian Quantum <ianquantum2027@gmail.com> wrote:
=

FALCON+ is more likely to get NIST approval. They struggled = to get the algorithm over "80 bits of security" even with a signi= ficant set of improvements. I don't know if this affects the aggregatio= n features, it would take significant research. The dramatic security impro= vements of FALCON+ only cost 5% and 0 bytes additional overhead. https://eprint.ia= cr.org/2024/1769.pdf

SECP256k1 had significant reductions to it's security ov= er the last 16 years but none of the attacks detailed by Bernstein directly= impact the security as implemented into Bitcoin. (Mitigations and non-inte= ractive signing, salt and hash were excellent design choices.)

I would suggest delaying FALCON or FALCON+ until standardize= d. There are significant weaknesses but no full break. The brittleness of t= he random numbers, exposure to inverse function and a lot "weaker than= expected" parameters would suggest caution. Once standardized I would= suggest rapid implementation but not until then.

NTRU Prime is a favored alternate candidate of mine, as comm= unicated previously. Cryptographers suspect that NIST has again inserted PQ= C backdoors following the last 3 public key standards being standardized wi= th very suspicious parameters. (P224, P256, P384)

I hope = we can get some momentum around protecting Bitcoin. 1-6 million (depending = on estimate) BTC have known public keys and while most could transfer to p2= pkh the creation of quantum safe addresses is a strong signal. The implemen= tation of post quantum cryptography is also required by many government age= ncies around the world, including the White House.=C2=A0

Ian Smith
Migrate to Quantum Safety before 2027

On Mon, Feb 24= , 2025, 12:53=E2=80=AFAM Hunter Beast <hunter@surmount.systems> wrote= :
Hi Jonas,
=
On Selective Disclosure,

I think we&#= 39;re going to need to add simple multisig semantics to the attestation due= to its lack of script capability. Would that help? Separate multisig seman= tics like quorum and total would be needed for each class of key, so that e= ven if Schnorr signatures can be broken (or one or two of the other PQC sig= natures even), they don't count towards the quorum of the other signatu= re types.

On Attestation structure,

=
What prevents arbitrary data being hashed and then included in t= he attestation is, each signature public key pair must be able to verify th= e transaction message in order to be considered a valid transaction. In oth= er words, each public key and signature pair is validated against the trans= action message upon transaction verification.

On M= ultisignature 256-bit security,

To be honest, I= 9;ve read this a couple of times and I will admit I don't understand th= is attack. Can you provide more details on how it works, and how it might b= e possible to mitigate?

On General comments,
=

I agree with the worst-case transaction verification co= ncern. I'll need to put some work into detailing NIST I variants and th= eir signature verification times, and then computing worst-case scenarios f= or different discount constants.

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

On adding three schemes, there are a= couple of advantages of this. First, wallets can automatically decide how = many signatures to add based on the amount being spent. This then acts as a= sort of MEV opportunity for miners, because the higher the value of the tr= ansaction, the more signatures might be included, which increases fee reven= ue. Also, it addresses Matt's concern about security assumptions. There= 's a strong desire for SLH-DSA support, even though it's so large. = However, from a practicality standpoint (thinking of plebs), it will make s= ense to include the smaller ML-DSA and FN-DSA also. While it does increase = complexity, I believe that a libbitcoinpqc library, as mentioned in the BIP= , will serve as a useful analogue to libsecp256k1. It's also worth noti= ng that in my position at Anduro, I have resources to put into building suc= h a library. Hopefully this can help meet the expectation of a well specifi= ed and implemented consensus level library.

On sig= nature aggregation, yes, I'm excited to see those developments in FN-DS= A, and maybe we can see that filter into SLH-DSA as well. Hopefully those i= mprovements 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 = 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/2025/055
[2] https://eprint.iacr.org/2024/311 (Un= fortunately, 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 bitcoindev+unsubscribe@googlegroups= .com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5= -9570-31967ee339ecn%40googlegroups.com.

--
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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit = https://groups.google.com/d/msgid/bitcoindev/CA%2B7C%2BcYY_97y_QsSON5U3y7v4= a0usGaGmcD%2Br%3D8Y05p5Cwmp5w%40mail.gmail.com.

--
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.co= m/d/msgid/bitcoindev/CABfMNdL9XDBCM4fw9wpGDj8e9yJh%2B-6F6%3DQA8i5MUS%3Dbj1P= crw%40mail.gmail.com.
--000000000000ffbdf8062f004f58--