path: root/a2/cf48bacd957e38110c7646ef416261b00d19fd

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 <bitcoindev+bncBCQNPUMG2ADBBU6O7C6QMGQEJ6A36MQ@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <bitcoindev@googlegroups.com>
        (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 <bitcoindev@googlegroups.com>; 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 <ianquantum2027@gmail.com>
Date: Mon, 24 Feb 2025 17:12:45 +0100
X-Gm-Features: AWEUYZmCDkZG86uwRF7oDAFmSFfcnyXVT9k7uJrY1KPO4q4KewHdfOfz-zJa2Tc
Message-ID: <CA+7C+cYY_97y_QsSON5U3y7v4a0usGaGmcD+r=8Y05p5Cwmp5w@mail.gmail.com>
Subject: Re: [bitcoindev] P2QRH / BIP-360 Update
To: Hunter Beast <hunter@surmount.systems>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
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: <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 (/)

--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 <hunter@surmount.system=
s> 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
> <https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5-9570-319=
67ee339ecn%40googlegroups.com?utm_medium=3Demail&utm_source=3Dfooter>
> .
>

--=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

<div dir=3D"auto"><p dir=3D"ltr">FALCON+ is more likely to get NIST approva=
l. They struggled to get the algorithm over &quot;80 bits of security&quot;=
 even with a significant set of improvements. I don&#39;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. <a href=3D"https://eprint.iacr.org/2024/1769.pdf">https://eprint.ia=
cr.org/2024/1769.pdf</a></p>
<p dir=3D"ltr">SECP256k1 had significant reductions to it&#39;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.)</p>
<p dir=3D"ltr">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 &quot;weaker than=
 expected&quot; parameters would suggest caution. Once standardized I would=
 suggest rapid implementation but not until then.</p>
<p dir=3D"ltr">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)</p><p dir=3D"ltr">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</p>
<div data-smartmail=3D"gmail_signature">Ian Smith<br>Migrate to Quantum Saf=
ety before 2027</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" =
class=3D"gmail_attr">On Mon, Feb 24, 2025, 12:53=E2=80=AFAM Hunter Beast &l=
t;hunter@surmount.systems&gt; wrote:<br></div><blockquote class=3D"gmail_qu=
ote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex=
">Hi Jonas,<div><br></div><div>On Selective Disclosure,<br><div><br></div><=
div>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? Separat=
e multisig semantics like quorum and total would be needed for each class o=
f key, so that even if Schnorr signatures can be broken (or one or two of t=
he other PQC signatures even), they don&#39;t count towards the quorum of t=
he other signature types.</div><div><br></div><div>On Attestation structure=
,</div><div><br></div><div>What prevents arbitrary data being hashed and th=
en included in the attestation is, each signature public key pair must be a=
ble to verify the transaction message in order to be considered a valid tra=
nsaction. In other words, each public key and signature pair is validated a=
gainst the transaction message upon transaction verification.</div><div><br=
></div><div>On Multisignature 256-bit security,</div><div><br></div><div>To=
 be honest, I&#39;ve read this a couple of times and I will admit I don&#39=
;t understand this attack. Can you provide more details on how it works, an=
d how it might be possible to mitigate?</div><div><br></div><div>On General=
 comments,</div><div><br></div><div>I agree with the worst-case transaction=
 verification concern. I&#39;ll need to put some work into detailing NIST I=
 variants and their signature verification times, and then computing worst-=
case scenarios for different discount constants.</div><div><br></div><div>O=
n 128-bit security... Yes, I&#39;m coming to realize that too. It&#39;s bee=
n a common point of feedback.</div><div><br></div><div>On adding three sche=
mes, there are a couple of advantages of this. First, wallets can automatic=
ally decide how many signatures to add based on the amount being spent. Thi=
s then acts as a sort of MEV opportunity for miners, because the higher the=
 value of the transaction, the more signatures might be included, which inc=
reases fee revenue. Also, it addresses Matt&#39;s concern about security as=
sumptions. There&#39;s a strong desire for SLH-DSA support, even though it&=
#39;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 i=
t does increase complexity, I believe that a libbitcoinpqc library, as ment=
ioned in the BIP, will serve as a useful analogue to libsecp256k1. It&#39;s=
 also worth noting that in my position at Anduro, I have resources to put i=
nto building such a library. Hopefully this can help meet the expectation o=
f a well specified and implemented consensus level library.</div><div><br><=
/div><div>On signature aggregation, yes, I&#39;m excited to see those devel=
opments in FN-DSA, and maybe we can see that filter into SLH-DSA as well. H=
opefully those improvements will be ready once the time comes to activate.<=
/div><div><br></div><div><br><br></div></div><div class=3D"gmail_quote"><di=
v dir=3D"auto" class=3D"gmail_attr">On Friday, February 21, 2025 at 3:18:35=
=E2=80=AFAM UTC-7 Jonas Nick wrote:<br></div><blockquote class=3D"gmail_quo=
te" style=3D"margin:0 0 0 0.8ex;border-left:1px solid rgb(204,204,204);padd=
ing-left:1ex">Hi Hunter,
<br>
<br>Thanks for your work on BIP 360. I think now is a good time to develop =
and
<br>discuss concrete PQ proposals. I have a few questions and comments rega=
rding
<br>some aspects of the proposal:
<br>
<br>Selective disclosure
<br>---
<br>
<br>From, the output contains a root of a Merkle tree of public key hashes =
and
<br>spending from this output requires revealing the public keys and their
<br>corresponding valid signatures. More concretely, if the user creates ro=
ot
<br>
<br>R =3D MerkleRoot([hash(public_key_falcon_1024), hash(public_key_secp256=
k1)]),
<br>
<br>they can spend from R by revealing both public keys and corresponding s=
ignatures.
<br>
<br>The BIP also mentions that the public keys can be selectively disclosed=
:
<br>
<br> &gt; When spending, if a public key hash is provided in the attestatio=
n with an
<br> &gt; empty signature, that hash will be used directly in the merkle tr=
ee computation
<br> &gt; rather than hashing the full public key.
<br>
<br>What prevents an quantum adversary, upon observing a spend from R, from=
 breaking
<br>public_key_secp256k1 and then spending from R by providing
<br>
<br>[
<br>   hash(public_key_falcon_1024),
<br>   empty string,
<br>   public_key_secp256k1,
<br>   a secp256k1 signature forgery
<br>]?
<br>
<br>
<br>Attestation structure
<br>---
<br>
<br>The BIP proposes to an attestation structure alongside the witness whic=
h is
<br>supposed to contain BIP 360 public keys and signatures (instead having =
them in
<br>the witness). The purpose of this structure is to assign a higher weigh=
t
<br>discount than the witness. The &quot;Rationale&quot; and &quot;Output M=
echanics&quot; sections the
<br>BIP describe that, since the attestation structure only contains public=
 keys and
<br>signatures, storage of arbitrary data (&quot;inscriptions&quot;) is pre=
vented.
<br>
<br>Leaving aside that there may be creative ways to embed arbitrary data i=
n public
<br>keys and signatures as well, selective disclosure of the Merkle tree ap=
pears to
<br>allow embedding arbitrary data. For instance, a user can create root
<br>
<br>R =3D MerkleRoot(data, hash(public_key_secp256k1)]),
<br>
<br>where data is an arbitrary 256-bit string. What prevents the user from
<br>pretending that data is the hash of a public key and providing
<br>
<br>[
<br>   data,
<br>   empty string,
<br>   public_key_secp256k1,
<br>   a secp256k1 signature forgery
<br>]
<br>
<br>in the attestation structure to spend from R?
<br>
<br>
<br>Multi-signature 256-bit security
<br>---
<br>
<br>The BIP briefly discusses multi-signature scenarios in the script valid=
ation
<br>section, but the details seem incomplete. From what I can infer, the cu=
rrent
<br>specification fails to achieve the claimed 256-bit security.
<br>
<br>The potential attack would work as follows:
<br>1. The victim provides their public key pk to the adversary.
<br>2. The adversary finds two public keys pk&#39; and pk&#39;&#39; such th=
at
<br>    MerkleRoot(MultiSig[pk, pk&#39;]) =3D MerkleRoot([pk&#39;&#39;])
<br>3. The adversary convinces the victim to send coins to MerkleRoot(Multi=
Sig[pk,
<br>    pk&#39;]) and then steals the coins by opening the Merkle tree root=
 to [pk&#39;&#39;] and
<br>    providing a signature for pk&#39;&#39;.
<br>
<br>Since the Merkle root is the 256-bit output of SHA256, the adversary ca=
n find
<br>this collision with about 2^128 operations.
<br>
<br>If I remember correctly, this attack was discussed on the mailing list =
in the
<br>context of segwit and it&#39;s the reason why P2WSH (unlike P2PKH) requ=
ires 256-bit
<br>hashes.
<br>
<br>
<br>General comments
<br>---
<br>
<br>I think one of the main questions that the BIP does not currently addre=
ss is how
<br>it affects the worst-case validation cost of a block.
<br>
<br>Regarding your question:
<br> &gt; But if the intention was for 256 bits of security, should level V=
 security be
<br> &gt; the default?
<br>
<br>I don&#39;t know what Satoshi&#39;s intentions were, but the secp256k1 =
specification
<br>clearly indicates 128-bit &quot;strength&quot; ([0], Table 1). I believ=
e that&#39;s fairly
<br>well known in the technical Bitcoin space.
<br>
<br>I am not quite convinced that adding three PQ schemes to the Bitcoin co=
nsensus
<br>protocol is a great solution to the problem of not being sure which exa=
ct scheme
<br>to pick. Offloading this decision to users does not really solve this p=
roblem.
<br>Moreover, this adds massive complexity and new cryptographic assumption=
s to the
<br>protocol. Remember that one of the main motivations behind libsecp256k1=
, was
<br>that general purpose cryptographic libraries are not well suited for co=
nsensus
<br>systems. So all new cryptographic schemes added to the consensus protoc=
ol need
<br>to be exceptionally well specified and implemented. That said, it makes=
 a lot of
<br>sense to design a hybrid scheme that also provides security against a c=
lassic
<br>attacker through an established signature scheme (as BIP 360 proposes).
<br>
<br>Lastly, I agree that non-interactive aggregation of PQ schemes might be
<br>promising, as it could mitigate about signature size and verification c=
ost if
<br>aggregation is applied on the transaction level. Recently, there has be=
en
<br>progress on the security of aggregating hash-based signatures [1] and F=
alcon
<br>[2].
<br>
<br>[0] <a href=3D"https://www.secg.org/sec2-v2.pdf" rel=3D"nofollow norefe=
rrer noreferrer" target=3D"_blank">https://www.secg.org/sec2-v2.pdf</a>
<br>[1] <a href=3D"https://eprint.iacr.org/2025/055" rel=3D"nofollow norefe=
rrer noreferrer" target=3D"_blank">https://eprint.iacr.org/2025/055</a>
<br>[2] <a href=3D"https://eprint.iacr.org/2024/311" rel=3D"nofollow norefe=
rrer noreferrer" target=3D"_blank">https://eprint.iacr.org/2024/311</a> (Un=
fortunately, this only beats trivial
<br>     aggregation (concatenation of signatures) when the number of signa=
tures is
<br>     greater than about 110)
<br>
<br>Jonas
<br>
<br></blockquote></div>

<p></p>

-- <br>
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br>
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com" rel=3D"n=
oreferrer noreferrer" target=3D"_blank">bitcoindev+unsubscribe@googlegroups=
.com</a>.<br>
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/16d7adca-a01e-40c5-9570-31967ee339ecn%40googlegroups.com?utm_med=
ium=3Demail&amp;utm_source=3Dfooter" rel=3D"noreferrer noreferrer" target=
=3D"_blank">https://groups.google.com/d/msgid/bitcoindev/16d7adca-a01e-40c5=
-9570-31967ee339ecn%40googlegroups.com</a>.<br>
</blockquote></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/CA%2B7C%2BcYY_97y_QsSON5U3y7v4a0usGaGmcD%2Br%3D8Y05p5Cwmp5w%40ma=
il.gmail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.=
com/d/msgid/bitcoindev/CA%2B7C%2BcYY_97y_QsSON5U3y7v4a0usGaGmcD%2Br%3D8Y05p=
5Cwmp5w%40mail.gmail.com</a>.<br />

--0000000000000f2279062ee59d7d--