From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Tue, 25 Feb 2025 12:26:06 -0800 Received: from mail-qt1-f192.google.com ([209.85.160.192]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1tn1VE-0005tt-N7 for bitcoindev@gnusha.org; Tue, 25 Feb 2025 12:26:06 -0800 Received: by mail-qt1-f192.google.com with SMTP id d75a77b69052e-4720468e863sf168648771cf.2 for ; Tue, 25 Feb 2025 12:26:04 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1740515159; cv=pass; d=google.com; s=arc-20240605; b=V6ZvlYSErAfhxtVAigvm0WhB9Tci3qFmu057CV8eBu84FljBduiEcNGrTeTjntSfB3 desPPfl7VRAD6KD9igp8TdZzzu+YtNmbMiwipD2bMqLGCbNxvm6wuxzyPIvDZCSYA5N2 fehsPUXEAiYuXxIV8mWdf86UIR23PRTmIR2BJ0ScLGHqSpE1NAM16r19XPYl6ZVc53eC voDnus5vVbyOwHpyVGEAiwsnKsQjdSDhexogfacATSpOxAzUpn50SKnVRLfeQ9NRSlOC TIbJ1rNpYcD0iBRp/6220fMFyayHx7iGCvt3ESVuqjyAwmwftZrcCTUi0OV5rct80wDx 6pzQ== 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:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:sender:dkim-signature :dkim-signature; bh=mIrHo7nYwFGeSCuHt6fmFaVouPQJsNUUHcHlQ0i/tTg=; fh=NsMrwSYnfE5V1BdtO2nbNnWendCwcJngZ9jxHqVaCW4=; b=QGplAxeW606LXe3z6otG9QFqMG8Hr5HiWNAN/jl9nvdPcsT8sXG1Ozpa3brI1p7ggb ZZlvaPBuoq0s5QA1nP7jECkEo3QCwtVVfdkE0WgB0lZSOepe119KvCiEY/TU08ky91BO oL4tly6m1eYvFoCtK42ttd0iBKkWKOCNPMGK99wXBlgSMHaitsvcXgtsXAfKVC9RPIP6 x8OE6sztgYM+NrmBfm3BkV3Nvfzz6DLftalEf6UIoNQqOimRliAoo+tGK5/VO90WQyqo gQ/eQiwt+kDdH1p+PUQFuBQ1vXHxdaMw4QkGE3d75F8Gu8EM0Jgv2eWvk1FQe32iF/2m BybQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=D1zL2O8S; spf=pass (google.com: domain of ianquantum2027@gmail.com designates 2607:f8b0:4864:20::e36 as permitted sender) smtp.mailfrom=ianquantum2027@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=1740515159; x=1741119959; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:sender:from:to:cc:subject:date:message-id :reply-to; bh=mIrHo7nYwFGeSCuHt6fmFaVouPQJsNUUHcHlQ0i/tTg=; b=n/k2zUCIJuWurTt510oQmcb1kNcfDNXzzrtJC9uAz2Bk/inRUI2hcBU4G8pa7TVF7d MFqMk5Fy6KKv3fwVke2+j8wx1sP1oLeMKEdBXljf+wrV5Th2jvGYbDFogovgSulvO5Ae 7TxUJZRlleX3IRNrQ482kCGpmZNDRzcrGF7TVhGl98YbmyJ35EBr4bM13wypXxvBOOMf dSYBU7vuSa/0Wbz7t6r3feU2RjZowY3Nwe25MQZmvdT9SAaCFTHFSuQYKg8xb6vTgiva rrX5gh1ScuwyYH5aNnSHIpg1uyIh+SyH1dKGWWehwieXXzd7gEtXCCFLRA6HJUriYusV JqHw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1740515159; x=1741119959; 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:cc:to:subject:message-id:date:from:in-reply-to :references:mime-version:from:to:cc:subject:date:message-id:reply-to; bh=mIrHo7nYwFGeSCuHt6fmFaVouPQJsNUUHcHlQ0i/tTg=; b=Tq0J9qcJFB/AgIyahCfuCU2LVyZvUVX9bktoFEiPP/58jA3MEnMElETMGBIdThOUZW /qYSNYSYxIAdxCdg8pJze7DEPQauY9Ws1vtxUVeq9IsbxehXg6XcLIdPRrE38HWo250g bkZIezw+kis7RY7PUa76GHrfuqwH01C15axp7q/EdQbqjsp8ANBBrunIF+lS9MOW9do1 t2SQ2cRB09FdHTTgkkZO9/8U2SOcCQaxETiC0b2PHomLdQaGC2MFODUuq/PyzXbwBkkb 4TxYSPy6bQ50dSumcCkc77nV9CmgCRaHNTygzZdk2Bt/BrcQOEzfUfxb2o7ou+iH38i0 hOvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1740515159; x=1741119959; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:cc: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=mIrHo7nYwFGeSCuHt6fmFaVouPQJsNUUHcHlQ0i/tTg=; b=P5oacUKq9B9t/H1jfISG9B/eJ6N7okvhEBWXRVvSflIq2QmeLN/1dyoY6+ygQas8Sc IWDqreVutl9pSxBR5U+mgODg5ekDpv6AdOXgXBgQvv7F1uNt44oGIeiqewCWrO70vqOQ aGRh5VczGr/c7jH+d50Id86q7n/hzzkfFJGkIZ+resZL+2uPXE8HLEJR8Bmxy/7StZJm b7qU67dm++G9fBqWzmnIxWbE5zXT+qjMNnINLFb7i86HYezGeF/CpRdjW7TC0wlx6sz2 y78CMCnaxmRNleb1A5tXu4+2kxPhPIg6JZoWfYvPcYdSRHU/4idL+xdKfrUYeyOOpiBY ln0w== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=2; AJvYcCW2TmGhaAYZK6VN6ba5Z7EU0MoH7gw3wEeAm29OUW48ik27SuyslXTJAX0TZWsj1M56XH1JZYMEwVUJ@gnusha.org X-Gm-Message-State: AOJu0Yz67xZVSkKHA10cjWW1WoKSR3O7iHsKacUVfpex3c8wLUAx7u37 OqRDp+Z7hB+k9OuCSNVt1FfUl59G/5ef3oBPMcNlzsNwGw6xJrVR X-Google-Smtp-Source: AGHT+IHUQyopa11GDmNgDh1Zl5G3X/wraXa4ykb1oz6OpZs6ZDFr0vPYyr0MoNs8W12YM9z2bcxtkw== X-Received: by 2002:ac8:5f54:0:b0:472:1512:c602 with SMTP id d75a77b69052e-47377227fe7mr57947451cf.25.1740515158879; Tue, 25 Feb 2025 12:25:58 -0800 (PST) X-BeenThere: bitcoindev@googlegroups.com; h=Adn5yVFkHsbW/cr7SQV6B32dw+Nf1b2dbNq/EiqwkWqwGXTgBQ== Received: by 2002:a05:622a:646:b0:471:f3a2:de8a with SMTP id d75a77b69052e-473777932a4ls12214861cf.1.-pod-prod-06-us; Tue, 25 Feb 2025 12:25:55 -0800 (PST) X-Received: by 2002:a05:620a:9370:b0:7c2:40e3:546a with SMTP id af79cd13be357-7c240e35490mr410531485a.9.1740515155302; Tue, 25 Feb 2025 12:25:55 -0800 (PST) Received: by 2002:a05:620a:8112:b0:7c0:9619:31e1 with SMTP id af79cd13be357-7c0cec7c444ms85a; Mon, 24 Feb 2025 08:13:00 -0800 (PST) X-Received: by 2002:a05:622a:58a:b0:472:c7f:a98b with SMTP id d75a77b69052e-4722295d31bmr194429101cf.35.1740413579594; Mon, 24 Feb 2025 08:12:59 -0800 (PST) ARC-Seal: i=1; a=rsa-sha256; t=1740413579; cv=none; d=google.com; s=arc-20240605; b=FQnR97w1We3gV3bk+tEEdoGsJKz7OvQ/YObXH6vbJsY957k2laKHyr2ezcEAiZrBKe 37wf5VvJ1ChlFdCw6UfpNPcrzu+LInsCwboWYJD0jyW3AZ9Bsz0NLlwnM6Z+x7qwz9ga FcrR27CsGP1XAZj5t/d54N0Ef2Az3Hfijg7FjEQBsSLKomvXIyyKthzmbBWFc4IIPz7Y rG1oTQgZepfH/BrWsnql3B7MFKHTx8EJEloR2QN8VsM6rnLF/LJ3FUOv8+XKU6tq4s8I SpYRRGHQ80xhRcF/kvbMZLwWXo9Ua+PI7ow4rmd/7lzhjuqJPqj0FbKmOII9YtQkGJCy B6Hw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=cc:to:subject:message-id:date:from:in-reply-to:references :mime-version:dkim-signature; bh=rpulS01Tx0lJK+j+hF3azGKFvHijZfRLZxhJne7/bk0=; fh=oW5/5oUmRRMvy96u/Fl5uZTynMYP3W/WShfBcMiH4EY=; b=YUHFhJP+fBM/SAnICCGqLNv5AP3uBBoCeGfVQdnzo1Zzdlb+zTuLMNfChuR+QmsbhG JdSUrlFpEbf7ILryBR6UL3BOHsjwqT0rM0VGzLloCw5sQjoT/gCIip/SCyCHgdYZKLtr l/hzl1sluueN+HZpDZa39sz12ShIigYfjcsjjb/sDLHlbzKhyBSaFfxXQ63pNmK+wYOd 5dgNiDvzAWrOVocZ61JPjlq/raW43h1IEtPO0SPid45bp/TKq/gvL3C5f7EK/CUOUA6G Hm4rDaltPHoiclzSjLkL5nQaZ/S9yvAValNFSUBz6BOCTzbiwZlOgimAhngNO9IGG2xR 0Djw==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=D1zL2O8S; spf=pass (google.com: domain of ianquantum2027@gmail.com designates 2607:f8b0:4864:20::e36 as permitted sender) smtp.mailfrom=ianquantum2027@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-vs1-xe36.google.com (mail-vs1-xe36.google.com. [2607:f8b0:4864:20::e36]) by gmr-mx.google.com with ESMTPS id d75a77b69052e-471f3c91ffbsi7812791cf.3.2025.02.24.08.12.59 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Mon, 24 Feb 2025 08:12:59 -0800 (PST) Received-SPF: pass (google.com: domain of ianquantum2027@gmail.com designates 2607:f8b0:4864:20::e36 as permitted sender) client-ip=2607:f8b0:4864:20::e36; Received: by mail-vs1-xe36.google.com with SMTP id ada2fe7eead31-4c009b08ec0so13239137.2 for ; Mon, 24 Feb 2025 08:12:59 -0800 (PST) X-Gm-Gg: ASbGncv/mGCiCNnT/P9TS/toDaIBvoaA/iMP7eYPX0mThBExlC/TKG8SAyaxkvew96A 3iIwPQ9BgoTlaSn4cJuKgKP6mINBmPu3OWP+Bqpb8hprJcgJ+TPLiGfCkLPt8YY2xnBUlwL7y7R VeRqZ29wuV X-Received: by 2002:a05:6102:2ac9:b0:4be:68fe:e698 with SMTP id ada2fe7eead31-4bfc00568c1mr7191467137.10.1740413577665; Mon, 24 Feb 2025 08:12:57 -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: <16d7adca-a01e-40c5-9570-31967ee339ecn@googlegroups.com> From: Ian Quantum Date: Mon, 24 Feb 2025 17:12:45 +0100 X-Gm-Features: AWEUYZmCDkZG86uwRF7oDAFmSFfcnyXVT9k7uJrY1KPO4q4KewHdfOfz-zJa2Tc Message-ID: Subject: Re: [bitcoindev] P2QRH / BIP-360 Update To: Hunter Beast Cc: Bitcoin Development Mailing List Content-Type: multipart/alternative; boundary="0000000000000f2279062ee59d7d" X-Original-Sender: ianquantum2027@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=D1zL2O8S; spf=pass (google.com: domain of ianquantum2027@gmail.com designates 2607:f8b0:4864:20::e36 as permitted sender) smtp.mailfrom=ianquantum2027@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 (/) --0000000000000f2279062ee59d7d Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 with 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? Separa= te > 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 > 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 the > transaction message in order to be considered a valid transaction. In oth= er > 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, and > how it might be possible to mitigate? > > On General comments, > > I agree with the worst-case transaction verification concern. I'll need t= o > put some work into detailing NIST I variants 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, 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 miner= s, > because the higher the value of the transaction, the more signatures migh= t > be included, which increases fee revenue. Also, it addresses Matt's conce= rn > 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 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 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 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 >> 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 roo= t >> >> 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 wit= h >> 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 =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 can >> find >> this collision with about 2^128 operations. >> >> If I remember correctly, this attack was discussed on the mailing list i= n >> 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 addres= s >> 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 exac= t >> 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 protoco= l >> 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 bee= n >> 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/16d7adca-a01e-40c5-9570-3196= 7ee339ecn%40googlegroups.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/= CA%2B7C%2BcYY_97y_QsSON5U3y7v4a0usGaGmcD%2Br%3D8Y05p5Cwmp5w%40mail.gmail.co= m. --0000000000000f2279062ee59d7d Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable

FALCON+ is more likely to get NIST approva= l. They struggled to get the algorithm over "80 bits of security"= even with a significant set of improvements. I don't know if this affe= cts the aggregation features, it would take significant research. The drama= tic security improvements of FALCON+ only cost 5% and 0 bytes additional ov= erhead. 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 Saf= ety before 2027

On Mon, Feb 24, 2025, 12:53=E2=80=AFAM Hunter Beast &l= t;hunter@surmount.systems> wrote:
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 bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.= com/d/msgid/bitcoindev/CA%2B7C%2BcYY_97y_QsSON5U3y7v4a0usGaGmcD%2Br%3D8Y05p= 5Cwmp5w%40mail.gmail.com.
--0000000000000f2279062ee59d7d--