diff options
| -rw-r--r-- | 72/3a8195b66b16d7562b314eb5b9b6f300a45071 | 684 |
1 files changed, 684 insertions, 0 deletions
diff --git a/72/3a8195b66b16d7562b314eb5b9b6f300a45071 b/72/3a8195b66b16d7562b314eb5b9b6f300a45071 new file mode 100644 index 000000000..cb19d0330 --- /dev/null +++ b/72/3a8195b66b16d7562b314eb5b9b6f300a45071 @@ -0,0 +1,684 @@ +Delivery-date: Fri, 04 Apr 2025 10:26:38 -0700 +Received: from mail-qt1-f189.google.com ([209.85.160.189]) + by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 + (Exim 4.94.2) + (envelope-from <bitcoindev+bncBCXOL6U6XMBRBQNMYC7QMGQEPJ5LVWA@googlegroups.com>) + id 1u0koN-0003m0-US + for bitcoindev@gnusha.org; Fri, 04 Apr 2025 10:26:37 -0700 +Received: by mail-qt1-f189.google.com with SMTP id d75a77b69052e-4766afee192sf57330411cf.0 + for <bitcoindev@gnusha.org>; Fri, 04 Apr 2025 10:26:36 -0700 (PDT) +ARC-Seal: i=2; a=rsa-sha256; t=1743787589; cv=pass; + d=google.com; s=arc-20240605; + b=BbI3HA2siCkLE4MEp/Jpk9DUUDAjLq6HY9eWufuyqtlG+HZVGGHdxXtKcqeXk9MHZa + 3k+yHe/zIT05Yz4t1oNVPGWgwdr+s5vRzP4XQXwivSYt/cGLRURwk2lVRxSVWKOOZgIc + rbamiD8fVRnf3UqV+lf1ivCZl8noBAkgPwYKcWPKlD4/GMybmG97awscf6/BU+OeCwAr + PY5jHIVpA3fm0KYTRjyclQvNdG4ReqZy18Mz3OiYuHFa5GN+rLxFmY2XjqaJ4GuWmFjx + PcaIpIcwHMWTPKxCfwEU0B+YGSeypnkMT+igC6Y0nIffuNQxJwZ8IGnkO0OYdi+NHs7R + i0JA== +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=hDqkrcPBT7VZ503ZQDNDHEzBJm9DNjpmwwJxQG9xnAM=; + fh=UuwUlpcHxMDfm/kuooPmpoSs8qfP8WAjokZ+Tp1cIYI=; + b=Npf/CkIEfo8GM70cvvVLNP5TwoNN4NBMSAiXjIAY9bCPM0o7xp/eHxlcLtTpRmAfoC + K4JUTtJqFo2/DIEtHi+mTnjCFZpMOcQ7pTjSHCNgJCM1/yguCaqQ5sdUMiMoPA163LLJ + urLfirFHTNyszRPfmp/LFn6iVeTPJH0I8/kH7HP8Ach53YkvjooYNr2viHP41IdVWhWf + XosdkwAtyh1vH7dHuZ8h2XgpSq2VAFB6x5fVFK8v/ehtWFdV74MxXcKdNgXNUh44YdaQ + cDmxE1+naLpV+XPWbnl2l3f+cLVaDjKWmdutHZqlS76IG4PvcDpGg9BWSh12IPsfHtqm + wBUA==; + darn=gnusha.org +ARC-Authentication-Results: i=2; gmr-mx.google.com; + dkim=pass header.i=@gmail.com header.s=20230601 header.b=EmDNEfeh; + spf=pass (google.com: domain of dustinvonsandwich@gmail.com designates 2607:f8b0:4864:20::c36 as permitted sender) smtp.mailfrom=dustinvonsandwich@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=1743787589; x=1744392389; 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=hDqkrcPBT7VZ503ZQDNDHEzBJm9DNjpmwwJxQG9xnAM=; + b=LVqX695jIovsE1GjQiDM2DT1oqlJBqn7ky3X8uW/D76u0OLPaIKLf8Ld4WdrQ2cECq + Hz4x9Jw2/aDaKX3F9qG6jrpc3FbXREzW63wIsrKaCTH/cZrkLkgIkYmpTyjDoGzqNkrd + xkTv1T6proS6i7AQuMNXvHC6mmaOC69D78d9y52AURR0HLLIX0TXks4Kwknu5buUj2eK + qqRHJNqLZtjK3QHonJ32ymcY6jkCC17lonkR8Hyq5SJPQp/eWrsoOnB00haA07jU2T32 + JnXOayTdGzqNxv1jk9YhRnDlM7RAjly0PY7TXgfRSkzC4p46ai0Y1BhIujVqIDAFwTrv + cUYA== +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1743787589; x=1744392389; 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=hDqkrcPBT7VZ503ZQDNDHEzBJm9DNjpmwwJxQG9xnAM=; + b=T98kVPbXQyVeGorwFoloxUq1iGOaqExC7VQqKiyBEN3GGRjJGnVGv7F/6z3VSx+9do + aoKtpFt73N2ACD1EWEjNBpOAr+Cwb4ZFvvw8YnpFSEVdXqWSAzL5VP3HQgdQKuytdJzp + GGM1hg8phicLmvBynTEsvqrIB05hvD+RRcYzSm9/RfsbtZKte//bDUj9vmMbL9t8i5Pu + WQ36iLykg6EbLizHDaGY7daQgbyl7Ye8RKRVXQj427cWplAWxDd4slFjytCT8MLJTx+S + 0ZrduIxgw2e2+4iWyJuWPl5SlLUmxC1GDq9ZaND+hNo8h6rOmlPA8dnmf/xOYhEQBxaT + FwlQ== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1743787589; x=1744392389; + 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=hDqkrcPBT7VZ503ZQDNDHEzBJm9DNjpmwwJxQG9xnAM=; + b=FOw4a6HGb1V9sjg3OJHy45t1tcTVKHHAletGHnZg2BC6UvJxWoe1StfcZOvA5/0AcT + CJZnXDpXNzeqY+7OJSBZHUvNmhEN5Bkfzmk5R3XKYt+HIwrNySiIKrZ1Liigu7A48vbx + Xlk6x9MXEJfDKX23gK8mSeMvFqJ2jijBDstbTFSig79xI3QrqWd7hFDv16FglnxWfopY + ndpR3fq+zNWfnea1oD+v3hRXphq1Hz8OpF/waZZie3RXh2UGs6q5CaIYAWd37h88nA8A + ije/Un4KDFGS2eu8bs20d/P2i4sE/SjaXfdZYg/isiKMHoBLnqqsSET1p87GFWRdykXc + 38kA== +Sender: bitcoindev@googlegroups.com +X-Forwarded-Encrypted: i=2; AJvYcCVBpbbAo845UiBGc/8mFD9swjUED5dFUp3MiJiRDvp3ZfLkK+jRomJmrMO2M0eW585LbKagJf+4fBPL@gnusha.org +X-Gm-Message-State: AOJu0YyOMhV0XKrhfHlRc8CWOg8PpWoztcJg3xolqKKMf/g0O+infPMS + yGkc1lTMEfOPdUAh42AL/PKJpZevB+lvWZhXt5EtFHFiiXkdV3Jz +X-Google-Smtp-Source: AGHT+IGGw79ExqTrjMTy6LPbBPUz8EZTjMbjcgRGsmCDGNiwZESq0YIh9LohP8+T0lGkyrytwPoWhw== +X-Received: by 2002:a05:622a:4cf:b0:477:6f2c:4a07 with SMTP id d75a77b69052e-479249037a7mr61546691cf.4.1743787588675; + Fri, 04 Apr 2025 10:26:28 -0700 (PDT) +X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAILyxchHTTk6jFkQWYQZ+jaF4qauzJi5rqjiN+MtXLOOw== +Received: by 2002:ac8:40d9:0:b0:476:b5d0:6c0 with SMTP id d75a77b69052e-4791634e434ls22314041cf.2.-pod-prod-04-us; + Fri, 04 Apr 2025 10:26:25 -0700 (PDT) +X-Received: by 2002:a05:620a:430c:b0:7c5:5cd6:5cea with SMTP id af79cd13be357-7c774d2cb64mr462684685a.15.1743787585507; + Fri, 04 Apr 2025 10:26:25 -0700 (PDT) +Received: by 2002:a05:620a:3c9:b0:7b6:d2da:e6ae with SMTP id af79cd13be357-7c76434178bms85a; + Fri, 4 Apr 2025 10:18:08 -0700 (PDT) +X-Received: by 2002:a05:620a:190f:b0:7c5:4de8:bf65 with SMTP id af79cd13be357-7c774dd6e50mr641215385a.36.1743787087948; + Fri, 04 Apr 2025 10:18:07 -0700 (PDT) +ARC-Seal: i=1; a=rsa-sha256; t=1743787087; cv=none; + d=google.com; s=arc-20240605; + b=aE/s8PY/QRiOnMHzpFBXhTwS5G/KEpAs8HW2rhVLuDOmD9Doxu//bsf95sZiKDp7+s + UfnkzgZ46EDO8jKzvDogOsthl6MfnUH09CCfG8qcM0AmlTGtpUXt3meDI5ex+cb6+qXJ + 85gXJlTbs8bwHcPoft96FwtDMsAC6u+5tVIkjZSwE5jdFN9jkpwMowwslkqzPn0z20/7 + 9jSdkgFlS+SAuKHhb4nophxg3aGrv5SVzBRbYYOUyc1Pk5zMXYWV43gjr7Vi8axWz+HR + nUAwEDOuDnr/wKGtTu8U9PhXKsYstQEB8EJqITzD+Rueoporwm7hk4noFPKTm2KXs9Cm + n7rw== +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=hcRtRFOkr1rILqsaP8MRldVe8lbpdpCQboYgZHp9t3A=; + fh=MhNL3lrwfbsRO5DJHn9ZZ/LeA3+mAuX0vCziGEghh6s=; + b=Rd9uEAI2WfLsG1+ogiSSnO2teXfXWX6h3q5NlmSw3tTAlwAk70uk+qkzvPj4k2S07s + swepg8YcQtzGiYITl8kzFQUvzwIPKscg++NxbwXHoJ0oO0Ttt4G+NR0inWhXc1OXqMwh + CKzc6ih/sSeQ+PP6xAW0CHACdbayRxt7/zS1M68RNnLI/4WgDsSzOdFFj/QHQrCqTZv2 + xximOO14dVtl0bIgleQDyNv7LjpxgvC5YXI5NdMr5VzKkYd70voFlFxu21cmg88DhMdl + iiT+hP9TyIKCTopzQnwOSQKl758kUxrNwNfD4gkUwMHN8VNhmJBIvvgCwk9BgeqCsxQD + JOMA==; + dara=google.com +ARC-Authentication-Results: i=1; gmr-mx.google.com; + dkim=pass header.i=@gmail.com header.s=20230601 header.b=EmDNEfeh; + spf=pass (google.com: domain of dustinvonsandwich@gmail.com designates 2607:f8b0:4864:20::c36 as permitted sender) smtp.mailfrom=dustinvonsandwich@gmail.com; + dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; + dara=pass header.i=@googlegroups.com +Received: from mail-oo1-xc36.google.com (mail-oo1-xc36.google.com. [2607:f8b0:4864:20::c36]) + by gmr-mx.google.com with ESMTPS id 6a1803df08f44-6ef0efc047asi1709336d6.1.2025.04.04.10.18.07 + for <bitcoindev@googlegroups.com> + (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); + Fri, 04 Apr 2025 10:18:07 -0700 (PDT) +Received-SPF: pass (google.com: domain of dustinvonsandwich@gmail.com designates 2607:f8b0:4864:20::c36 as permitted sender) client-ip=2607:f8b0:4864:20::c36; +Received: by mail-oo1-xc36.google.com with SMTP id 006d021491bc7-601c469cce3so577798eaf.2 + for <bitcoindev@googlegroups.com>; Fri, 04 Apr 2025 10:18:07 -0700 (PDT) +X-Gm-Gg: ASbGncv0wslRNL+vx5qFhWxo20ata1cYQdqYFj7WPGaIpz3UMJrM3r3PGtfadBgmwS4 + rbe7EpAksisy5mLfb7rt6JW52wIsMe6Pp7NFNltteBHRwedTVqL+ExgRDFxLDXFMozTrQJyPQpM + ldbl0kXbRKdHuyBNRHFkBKnLpArm21iI7FVsqzcXSb4y37yhnH4HVsMUmjajD31DnEWdBAfw== +X-Received: by 2002:a05:6820:1c90:b0:604:117:1a5d with SMTP id + 006d021491bc7-604157fe7fdmr1708558eaf.7.1743787087063; Fri, 04 Apr 2025 + 10:18:07 -0700 (PDT) +MIME-Version: 1.0 +References: <CAEM=y+XMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg@mail.gmail.com> +In-Reply-To: <CAEM=y+XMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg@mail.gmail.com> +From: Dustin Ray <dustinvonsandwich@gmail.com> +Date: Fri, 4 Apr 2025 10:17:56 -0700 +X-Gm-Features: ATxdqUFB7nHb0sOGJLn72-YVhypf0rzDMVwavdqyHvi-rO7xoAU2G7ZlP5KiVaU +Message-ID: <CAC3UE4K7AG96Njra3WSnt=1yPVZSnT7gktnwktaumPgOD0hU8Q@mail.gmail.com> +Subject: Re: [bitcoindev] Post Quantum Signatures and Scaling Bitcoin +To: Ethan Heilman <eth3rs@gmail.com> +Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Content-Type: multipart/alternative; boundary="000000000000e376a00631f711ae" +X-Original-Sender: Dustinvonsandwich@gmail.com +X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass + header.i=@gmail.com header.s=20230601 header.b=EmDNEfeh; spf=pass + (google.com: domain of dustinvonsandwich@gmail.com designates + 2607:f8b0:4864:20::c36 as permitted sender) smtp.mailfrom=dustinvonsandwich@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 (/) + +--000000000000e376a00631f711ae +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +This is a great post, thank you for sharing. I have one small tiny comment +that may or may not be relevant, but there is an existing gap in the +literature for a security proof that STARKs (rather FRI, the underlying +commitment scheme) is secure in a quantum adversary model. We conjecture +that it is, because it relies only on hashes as the primitive in an error +correcting code, but unlike other cryptographic primitives used or proposed +for critical security infrastructure, there is currently no formal security +argument for FRI against a quantum threat model that I am aware of. I'm not +sure how much this matters, but some may argue that stronger security +arguments are warranted for any potential change to the bitcoin signature +model in a PQ landscape. That's just my two cents anyways. + +On Fri, Apr 4, 2025 at 9:34=E2=80=AFAM Ethan Heilman <eth3rs@gmail.com> wro= +te: + +> I strongly believe Bitcoin will need to move to PQ signatures in the +> near future. The rest of this email is premised on this belief. +> +> PQ (Post Quantum) signatures present a problem for Bitcoin: +> +> First, they are large. Of the three proposed in BIP-360 [0], the +> smallest is 1.5kb for the public key + signature [1]. Without a +> discount this represents a massive reduction in Bitcoin's transaction +> volume due to the increase in transaction size of Bitcoin payment +> using such signatures. +> - Second, even if we discount PQ signatures and public keys so that +> the maximum number of transactions that can fit in a block is +> unchanged we still have the problem that these blocks and transactions +> will be an order of magnitude bigger. If it is the case that we can +> handle these extra bytes without degrading performance or +> decentralization, then consider the head room we are giving up that +> could be used for scalability. +> +> Beyond this there is also the risk that techniques could be developed +> to encode JPEGs and other data in these discounted PQ signatures or +> public keys. BIP-360 takes steps to make an abuse of this discount +> more difficult by requiring that a PQ signature and public key can +> only be written to the blockchain if they verify. We do not need PQ +> Signatures to be completely =E2=80=9CJPEG resistant=E2=80=9D, they just n= +eed PQ +> signatures to not enable significantly cheaper storage than payments. +> The degree to which the proposed PQ signature algorithms resist being +> repurposed as a storage mechanism is an open question and worth +> investigating. +> +> If it turned out PQ signatures could be used to encode data very +> cheaply, then Bitcoin faces the dilemma that if you discount PQ +> signatures, you make the JPEG problem worse and may price out the +> payment use case. If you don't discount PQ, you price out most people +> from sending payments in Bitcoin since non-PQ witness data can be used +> for storage +> +> I want to draw the community's attention to a solution that could not +> only address these problems but also increase Bitcoin=E2=80=99s scalabili= +ty +> (and privacy): +> +> Non-interactive Transaction Compression (NTC) for Transactions +> supporting PQ signatures. This is sometimes called Non-Interactive +> Witness Aggregation (NIWA) [2]. +> +> This would require a new transaction type supporting PQ signatures. +> The miner of a block would then pull out the signatures and hash +> pointers from transactions to compress transaction data and +> non-interactively aggregate all the PQ signatures in all the +> transactions in a block, replacing them with one big STARK (STARKS are +> a form of SNARK which is PQ). This would make PQ signatures +> significantly smaller and cheaper than ECDSA and schnorr signatures. +> +> Consider the following back of the envelope math: +> +> 2 bytes per Input =3D 2 bytes per TXID, 0 bytes per signature +> 37 bytes per output =3D 32 bytes pubkey hash + 5 bytes value (max 2.8m +> BTC per output) +> +> 1-input-2-output transaction would be: 2 + 2*37 =3D 76 bytes +> (4,000,000/76)/(60*10) =3D ~87 txns/sec +> +> You could shave some bytes off the value, or add some bytes to the +> TXID. [3] provides a more detailed estimate, proposing 113.5 weight +> units (WU) for a 1-input-2-output transaction with no address reuse. +> However it does not consider TXID compression. If desired an +> account-based model could push this even further to 12 bytes per +> transaction per block [4]. This would enable approximately +> 4,000,000/(12*60*10) =3D 555 txns/second. +> +> A secondary benefit of having on-chain PQ payments only be ~76 bytes +> in size is that it fundamentally changes the pricing relationship +> between payments and on-chain JPEG/complex contracts. The problem with +> on-chain JPEGs is not that they are possible, but that they are price +> competitive with payments. At ~76 bytes per payment or better yet ~76 +> bytes per LN channel open/close, JPEGs no longer present the same fee +> competition to payments as payments become much cheaper. +> +> Such a system would present scaling issues for the mempool because +> prior to aggregation and compression, these transactions would be 2kb +> to 100kb in size and there would be a lot more of them. It is likely +> parties producing large numbers of transactions would want to +> pre-aggregate and compress them in one big many input, many output +> transactions. Aggregating prior to the miner may have privacy benefits +> but also scalability benefits as it would enable cut-throughs and very +> cheap consolidation transactions. ~87/txns a second does not include +> these additional scalability benefits. +> +> Consider an exchange that receives and sends a large number of +> transactions. For instance between block confirmations customers send +> the exchange 10 1-input-2-output transactions in deposits and the +> exchange sends out 10 1-input-2-output transactions in withdrawals. +> The exchange could consolidate all of the outputs paying the exchange, +> including chain outputs, into one output and do the same for inputs. +> This would reduce not just size, but also validation costs. +> +> (10 * 2 + 20 * 2 * 37) + (10 * 2 + 20 * 2 * 37) =3D 3000 bytes +> becomes +> (10 * 2 + 11 * 2 * 37) + (2 + 11 * 2 * 37) =3D 1650 bytes +> +> If constructing these proofs turned out to be as expensive as +> performing POW, it would make block generation not progress free. +> Essentially you'd have a two step POW: proof generation and then the +> actual POW. Such a scenario would be very bad and cause the biggest +> miner to always be the one that generates blocks. A critical +> assumption I am making is that such proof generation is not +> particularly expensive in the scheme of POW. I am optimistic that +> proof generation will not be this expensive for two reasons +> +> There are PQ signature schemes which support non-interactive +> aggregation such as LaBRADOR [5]. Thus, the STARK wouldn=E2=80=99t need t= +o +> perform the block-wide signature aggregation and would only need to +> perform transaction compression, cut throughs and consolidation. +> +> We could make use of recursive STARKs [8] to allow miners to +> parallelize proof generation to reduce latency or to decentralize +> proof generation. Users creating transactions could perform +> non-interactive coinjoins with other users or settlement/batching. +> This would not only take proof generation pressure off of the miners +> and reduce the strain on the mempool but in some circumstances it +> would provide privacy if used with payjoin techniques like receiver +> side payment batching [7]. +> +> The approach we are proposing treats the STARK the miner produces as +> free from a blocksize perspective. This is important for bootstrapping +> because it means that fees are significantly cheaper for a +> transaction, even if it is the only compressed transaction in the +> block. This encourages adoption. Adoption helps address the chicken +> and egg problem of wallets and exchanges not investing engineering +> resources to support a new transaction type if no one is using it and +> no one wants to use it because it isn't well supported. By having a +> single format, built into the block we both accelerate the switch over +> and prevent a fragmented ecosystem that might arise from doing this in +> Bitcoin script. Fragmentation reduces the scalability benefits because +> validators have to validate multiple STARKs and reduces the privacy +> benefits because there are many coinjoins, rather than each being a +> coinjoin. +> +> Even if our approach here turns out to be infeasible, we need a way to +> reduce the size of PQ signatures in Bitcoin. The ability to move +> coins, including the ability to move coins that represent JPEGs, is +> the main functionality of Bitcoin. If we make storage/JPEG too price +> competitive with the ability to transfer coins, we destroy that +> essential functionality and decrease the utility of Bitcoin for +> everyone. Currently moving coins securely requires at least one 64 +> byte signature, which is an unfortunate tax on this most vital of all +> use cases. I believe removing that tax with signature aggregation will +> be beneficial for all parties. +> +> Consider the world of PQ signatures in Bitcoin without STARKs: +> - The large size of PQ signatures will make it more expensive for +> users to use them prior to the invention of a CRQC (Cryptographically +> Relevant Quantum Computer). This means that most outputs will not be +> protected by PQ signatures. Once a CRQC arises there will be a rush to +> move funds under the protection of PQ signatures but due to the large +> size of PQ signatures the fees will be too expensive for most outputs. +> Users will instead need to move their funds to centralized custodial +> wallets that can use a small number of outputs. In such a world it +> will be much harder and expensive to self-custody. +> - Without a solution here the large sizes of PQ signatures will limit +> Bitcoin's functionality to move coins using on-chain payments. This +> will also favor centralized custodians and erode the decentralized +> nature of Bitcoin. +> +> None of this is an argument against adopting BIP-360 or other PQ +> signatures schemes into Bitcoin. On the contrary, having PQ signatures +> in Bitcoin would be a useful stepping stone to PQ transaction +> compression since it would allow us to gain agreement on which PQ +> signature schemes to build on. Most importantly, in the event of a +> CRQC being developed it will be far better to have uncompressed PQ +> signatures in Bitcoin than none at all. +> +> Acknowledgements: +> These ideas arose out of correspondence with Hunter Beast. I want to +> thank Neha Narula, John Light, Eli Ben-Sasson for their feedback, +> Jonas Nick for his feedback and his idea to use LaBRADOR for signature +> aggregation, Tadge Dryja for suggesting the term =E2=80=9CJPEG resistance= +=E2=80=9D and +> his ideas around its feasibility. I had a number of fruitful +> discussions over lunch with members of the MIT DCI and on the Bitcoin +> PQ working group. These acknowledgements should not be taken as an +> agreement with or endorsement of the ideas in this email. +> +> [0]: Hunter Beast, BIP-360: QuBit - Pay to Quantum Resistant Hash +> (2025) https://github.com/bitcoin/bips/pull/1670/files# +> [1]: Benchmark Report: Post-Quantum Cryptography vs secp256k1 +> https://github.com/cryptoquick/libbitcoinpqc/blob/main/benches/REPORT.md +> [2]: Ruben Somsen, SNARKs and the future of blockchains (2020) +> +> https://medium.com/@RubenSomsen/snarks-and-the-future-of-blockchains-55b8= +2012452b +> [3]: John Light, Validity Rollups on Bitcoin (2022) +> +> https://github.com/john-light/validity-rollups/blob/main/validity_rollups= +_on_bitcoin.md +> [4] Vitalik Buterin, An Incomplete Guide to Rollups (2021) +> https://vitalik.eth.limo/general/2021/01/05/rollup.html +> [5]: Aardal, Aranha, Boudgoust, Kolby, Takahashi, Aggregating Falcon +> Signatures with LaBRADOR (2024) https://eprint.iacr.org/2024/311 +> [6]: Gidi Kaempfer, Recursive STARKs (2022) +> https://www.starknet.io/blog/recursive-starks/ +> [7]: Dan Gould, Interactive Payment Batching is Better (2023) +> https://payjoin.substack.com/p/interactive-payment-batching-is-better +> [8] John Tromp, Fee burning and Dynamic Block Size (2018) +> https://lists.launchpad.net/mimblewimble/msg00450.html +> +> -- +> 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/CAEM%3Dy%2BXMLuGH-MAfkYanfbU= +3Ynduw54jDVguKxgO2xEtnSEkZg%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/= +CAC3UE4K7AG96Njra3WSnt%3D1yPVZSnT7gktnwktaumPgOD0hU8Q%40mail.gmail.com. + +--000000000000e376a00631f711ae +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"auto">This is a great post, thank you for sharing. I have one s= +mall tiny comment that may or may not be relevant, but there is an existing= + gap in the literature for a security proof that STARKs (rather FRI, the un= +derlying commitment scheme) is secure in a quantum adversary model. We conj= +ecture that it is, because it relies only on hashes as the primitive in an = +error correcting code, but unlike other cryptographic primitives used or pr= +oposed for critical security infrastructure, there is currently no formal s= +ecurity argument for FRI against a quantum threat model that I am aware of.= + I'm not sure how much this matters, but some may argue that stronger s= +ecurity arguments are warranted for any potential change to the bitcoin sig= +nature model in a PQ landscape. That's just my two cents anyways.</div>= +<div dir=3D"auto"><br></div><div><div class=3D"gmail_quote gmail_quote_cont= +ainer"><div dir=3D"ltr" class=3D"gmail_attr">On Fri, Apr 4, 2025 at 9:34=E2= +=80=AFAM Ethan Heilman <<a href=3D"mailto:eth3rs@gmail.com">eth3rs@gmail= +.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"mar= +gin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;padding= +-left:1ex;border-left-color:rgb(204,204,204)">I strongly believe Bitcoin wi= +ll need to move to PQ signatures in the<br> +near future. The rest of this email is premised on this belief.<br> +<br> +PQ (Post Quantum) signatures present a problem for Bitcoin:<br> +<br> +First, they are large. Of the three proposed in BIP-360 [0], the<br> +smallest is 1.5kb for the public key + signature [1]. Without a<br> +discount this represents a massive reduction in Bitcoin's transaction<b= +r> +volume due to the increase in transaction size of Bitcoin payment<br> +using such signatures.<br> +- Second, even if we discount PQ signatures and public keys so that<br> +the maximum number of transactions that can fit in a block is<br> +unchanged we still have the problem that these blocks and transactions<br> +will be an order of magnitude bigger. If it is the case that we can<br> +handle these extra bytes without degrading performance or<br> +decentralization, then consider the head room we are giving up that<br> +could be used for scalability.<br> +<br> +Beyond this there is also the risk that techniques could be developed<br> +to encode JPEGs and other data in these discounted PQ signatures or<br> +public keys. BIP-360 takes steps to make an abuse of this discount<br> +more difficult by requiring that a PQ signature and public key can<br> +only be written to the blockchain if they verify. We do not need PQ<br> +Signatures to be completely =E2=80=9CJPEG resistant=E2=80=9D, they just nee= +d PQ<br> +signatures to not enable significantly cheaper storage than payments.<br> +The degree to which the proposed PQ signature algorithms resist being<br> +repurposed as a storage mechanism is an open question and worth<br> +investigating.<br> +<br> +If it turned out PQ signatures could be used to encode data very<br> +cheaply, then Bitcoin faces the dilemma that if you discount PQ<br> +signatures, you make the JPEG problem worse and may price out the<br> +payment use case. If you don't discount PQ, you price out most people<b= +r> +from sending payments in Bitcoin since non-PQ witness data can be used<br> +for storage<br> +<br> +I want to draw the community's attention to a solution that could not<b= +r> +only address these problems but also increase Bitcoin=E2=80=99s scalability= +<br> +(and privacy):<br> +<br> +Non-interactive Transaction Compression (NTC) for Transactions<br> +supporting PQ signatures. This is sometimes called Non-Interactive<br> +Witness Aggregation (NIWA) [2].<br> +<br> +This would require a new transaction type supporting PQ signatures.<br> +The miner of a block would then pull out the signatures and hash<br> +pointers from transactions to compress transaction data and<br> +non-interactively aggregate all the PQ signatures in all the<br> +transactions in a block, replacing them with one big STARK (STARKS are<br> +a form of SNARK which is PQ). This would make PQ signatures<br> +significantly smaller and cheaper than ECDSA and schnorr signatures.<br> +<br> +Consider the following back of the envelope math:<br> +<br> +2 bytes per Input =3D 2 bytes per TXID, 0 bytes per signature<br> +37 bytes per output =3D 32 bytes pubkey hash + 5 bytes value (max 2.8m<br> +BTC per output)<br> +<br> +1-input-2-output transaction would be: 2 + 2*37 =3D 76 bytes<br> +(4,000,000/76)/(60*10) =3D ~87 txns/sec<br> +<br> +You could shave some bytes off the value, or add some bytes to the<br> +TXID. [3] provides a more detailed estimate, proposing 113.5 weight<br> +units (WU) for a 1-input-2-output transaction with no address reuse.<br> +However it does not consider TXID compression. If desired an<br> +account-based model could push this even further to 12 bytes per<br> +transaction per block [4]. This would enable approximately<br> +4,000,000/(12*60*10) =3D 555 txns/second.<br> +<br> +A secondary benefit of having on-chain PQ payments only be ~76 bytes<br> +in size is that it fundamentally changes the pricing relationship<br> +between payments and on-chain JPEG/complex contracts. The problem with<br> +on-chain JPEGs is not that they are possible, but that they are price<br> +competitive with payments. At ~76 bytes per payment or better yet ~76<br> +bytes per LN channel open/close, JPEGs no longer present the same fee<br> +competition to payments as payments become much cheaper.<br> +<br> +Such a system would present scaling issues for the mempool because<br> +prior to aggregation and compression, these transactions would be 2kb<br> +to 100kb in size and there would be a lot more of them. It is likely<br> +parties producing large numbers of transactions would want to<br> +pre-aggregate and compress them in one big many input, many output<br> +transactions. Aggregating prior to the miner may have privacy benefits<br> +but also scalability benefits as it would enable cut-throughs and very<br> +cheap consolidation transactions. ~87/txns a second does not include<br> +these additional scalability benefits.<br> +<br> +Consider an exchange that receives and sends a large number of<br> +transactions. For instance between block confirmations customers send<br> +the exchange 10 1-input-2-output transactions in deposits and the<br> +exchange sends out 10 1-input-2-output transactions in withdrawals.<br> +The exchange could consolidate all of the outputs paying the exchange,<br> +including chain outputs, into one output and do the same for inputs.<br> +This would reduce not just size, but also validation costs.<br> +<br> +(10 * 2 + 20 * 2 * 37) + (10 * 2 + 20 * 2 * 37)=C2=A0 =3D 3000 bytes<br> +becomes<br> +(10 * 2 + 11 * 2 * 37) + (2 + 11 * 2 * 37) =3D 1650 bytes<br> +<br> +If constructing these proofs turned out to be as expensive as<br> +performing POW, it would make block generation not progress free.<br> +Essentially you'd have a two step POW: proof generation and then the<br= +> +actual POW. Such a scenario would be very bad and cause the biggest<br> +miner to always be the one that generates blocks. A critical<br> +assumption I am making is that such proof generation is not<br> +particularly expensive in the scheme of POW. I am optimistic that<br> +proof generation will not be this expensive for two reasons<br> +<br> +There are PQ signature schemes which support non-interactive<br> +aggregation such as LaBRADOR [5]. Thus, the STARK wouldn=E2=80=99t need to<= +br> +perform the block-wide signature aggregation and would only need to<br> +perform transaction compression, cut throughs and consolidation.<br> +<br> +We could make use of recursive STARKs [8] to allow miners to<br> +parallelize proof generation to reduce latency or to decentralize<br> +proof generation. Users creating transactions could perform<br> +non-interactive coinjoins with other users or settlement/batching.<br> +This would not only take proof generation pressure off of the miners<br> +and reduce the strain on the mempool but in some circumstances it<br> +would provide privacy if used with payjoin techniques like receiver<br> +side payment batching [7].<br> +<br> +The approach we are proposing treats the STARK the miner produces as<br> +free from a blocksize perspective. This is important for bootstrapping<br> +because it means that fees are significantly cheaper for a<br> +transaction, even if it is the only compressed transaction in the<br> +block. This encourages adoption. Adoption helps address the chicken<br> +and egg problem of wallets and exchanges not investing engineering<br> +resources to support a new transaction type if no one is using it and<br> +no one wants to use it because it isn't well supported. By having a<br> +single format, built into the block we both accelerate the switch over<br> +and prevent a fragmented ecosystem that might arise from doing this in<br> +Bitcoin script. Fragmentation reduces the scalability benefits because<br> +validators have to validate multiple STARKs and reduces the privacy<br> +benefits because there are many coinjoins, rather than each being a<br> +coinjoin.<br> +<br> +Even if our approach here turns out to be infeasible, we need a way to<br> +reduce the size of PQ signatures in Bitcoin. The ability to move<br> +coins, including the ability to move coins that represent JPEGs, is<br> +the main functionality of Bitcoin. If we make storage/JPEG too price<br> +competitive with the ability to transfer coins, we destroy that<br> +essential functionality and decrease the utility of Bitcoin for<br> +everyone. Currently moving coins securely requires at least one 64<br> +byte signature, which is an unfortunate tax on this most vital of all<br> +use cases. I believe removing that tax with signature aggregation will<br> +be beneficial for all parties.<br> +<br> +Consider the world of PQ signatures in Bitcoin without STARKs:<br> +=C2=A0- The large size of PQ signatures will make it more expensive for<br> +users to use them prior to the invention of a CRQC (Cryptographically<br> +Relevant Quantum Computer). This means that most outputs will not be<br> +protected by PQ signatures. Once a CRQC arises there will be a rush to<br> +move funds under the protection of PQ signatures but due to the large<br> +size of PQ signatures the fees will be too expensive for most outputs.<br> +Users will instead need to move their funds to centralized custodial<br> +wallets that can use a small number of outputs. In such a world it<br> +will be much harder and expensive to self-custody.<br> +- Without a solution here the large sizes of PQ signatures will limit<br> +Bitcoin's functionality to move coins using on-chain payments. This<br> +will also favor centralized custodians and erode the decentralized<br> +nature of Bitcoin.<br> +<br> +None of this is an argument against adopting BIP-360 or other PQ<br> +signatures schemes into Bitcoin. On the contrary, having PQ signatures<br> +in Bitcoin would be a useful stepping stone to PQ transaction<br> +compression since it would allow us to gain agreement on which PQ<br> +signature schemes to build on. Most importantly, in the event of a<br> +CRQC being developed it will be far better to have uncompressed PQ<br> +signatures in Bitcoin than none at all.<br> +<br> +Acknowledgements:<br> +These ideas arose out of correspondence with Hunter Beast. I want to<br> +thank Neha Narula, John Light, Eli Ben-Sasson for their feedback,<br> +Jonas Nick for his feedback and his idea to use LaBRADOR for signature<br> +aggregation, Tadge Dryja for suggesting the term =E2=80=9CJPEG resistance= +=E2=80=9D and<br> +his ideas around its feasibility. I had a number of fruitful<br> +discussions over lunch with members of the MIT DCI and on the Bitcoin<br> +PQ working group. These acknowledgements should not be taken as an<br> +agreement with or endorsement of the ideas in this email.<br> +<br> +[0]: Hunter Beast, BIP-360: QuBit - Pay to Quantum Resistant Hash<br> +(2025) <a href=3D"https://github.com/bitcoin/bips/pull/1670/files#" rel=3D"= +noreferrer" target=3D"_blank">https://github.com/bitcoin/bips/pull/1670/fil= +es#</a><br> +[1]: Benchmark Report: Post-Quantum Cryptography vs secp256k1<br> +<a href=3D"https://github.com/cryptoquick/libbitcoinpqc/blob/main/benches/R= +EPORT.md" rel=3D"noreferrer" target=3D"_blank">https://github.com/cryptoqui= +ck/libbitcoinpqc/blob/main/benches/REPORT.md</a><br> +[2]: Ruben Somsen, SNARKs and the future of blockchains (2020)<br> +<a href=3D"https://medium.com/@RubenSomsen/snarks-and-the-future-of-blockch= +ains-55b82012452b" rel=3D"noreferrer" target=3D"_blank">https://medium.com/= +@RubenSomsen/snarks-and-the-future-of-blockchains-55b82012452b</a><br> +[3]: John Light, Validity Rollups on Bitcoin (2022)<br> +<a href=3D"https://github.com/john-light/validity-rollups/blob/main/validit= +y_rollups_on_bitcoin.md" rel=3D"noreferrer" target=3D"_blank">https://githu= +b.com/john-light/validity-rollups/blob/main/validity_rollups_on_bitcoin.md<= +/a><br> +[4] Vitalik Buterin, An Incomplete Guide to Rollups (2021)<br> +<a href=3D"https://vitalik.eth.limo/general/2021/01/05/rollup.html" rel=3D"= +noreferrer" target=3D"_blank">https://vitalik.eth.limo/general/2021/01/05/r= +ollup.html</a><br> +[5]: Aardal, Aranha, Boudgoust, Kolby, Takahashi, Aggregating Falcon<br> +Signatures with LaBRADOR (2024) <a href=3D"https://eprint.iacr.org/2024/311= +" rel=3D"noreferrer" target=3D"_blank">https://eprint.iacr.org/2024/311</a>= +<br> +[6]: Gidi Kaempfer, Recursive STARKs (2022)<br> +<a href=3D"https://www.starknet.io/blog/recursive-starks/" rel=3D"noreferre= +r" target=3D"_blank">https://www.starknet.io/blog/recursive-starks/</a><br> +[7]: Dan Gould, Interactive Payment Batching is Better (2023)<br> +<a href=3D"https://payjoin.substack.com/p/interactive-payment-batching-is-b= +etter" rel=3D"noreferrer" target=3D"_blank">https://payjoin.substack.com/p/= +interactive-payment-batching-is-better</a><br> +[8] John Tromp, Fee burning and Dynamic Block Size (2018)<br> +<a href=3D"https://lists.launchpad.net/mimblewimble/msg00450.html" rel=3D"n= +oreferrer" target=3D"_blank">https://lists.launchpad.net/mimblewimble/msg00= +450.html</a><br> +<br> +-- <br> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" group.<br> +To unsubscribe from this group and stop receiving emails from it, send an e= +mail to <a href=3D"mailto:bitcoindev%2Bunsubscribe@googlegroups.com" target= +=3D"_blank">bitcoindev+unsubscribe@googlegroups.com</a>.<br> +To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/= +bitcoindev/CAEM%3Dy%2BXMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg%40mail.g= +mail.com" rel=3D"noreferrer" target=3D"_blank">https://groups.google.com/d/= +msgid/bitcoindev/CAEM%3Dy%2BXMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg%40= +mail.gmail.com</a>.<br> +</blockquote></div></div> + +<p></p> + +-- <br /> +You received this message because you are subscribed to the Google Groups &= +quot;Bitcoin Development Mailing List" 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/CAC3UE4K7AG96Njra3WSnt%3D1yPVZSnT7gktnwktaumPgOD0hU8Q%40mail.gma= +il.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/= +msgid/bitcoindev/CAC3UE4K7AG96Njra3WSnt%3D1yPVZSnT7gktnwktaumPgOD0hU8Q%40ma= +il.gmail.com</a>.<br /> + +--000000000000e376a00631f711ae-- + |