path: root/72/3a8195b66b16d7562b314eb5b9b6f300a45071

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&#39;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&#39;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 &lt;<a href=3D"mailto:eth3rs@gmail.com">eth3rs@gmail=
.com</a>&gt; 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&#39;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&#39;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&#39;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&#39;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&#39;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&#39;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&quot; 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&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/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--