path: root/a5/0221f8786308e587ce116be67d5a1ccba4da33

Delivery-date: Sun, 06 Apr 2025 04:47:29 -0700
Received: from mail-oo1-f58.google.com ([209.85.161.58])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBC3OX2EEU4BRBRGTZG7QMGQEL3JZXOQ@googlegroups.com>)
	id 1u1OTG-0008Bl-SG
	for bitcoindev@gnusha.org; Sun, 06 Apr 2025 04:47:28 -0700
Received: by mail-oo1-f58.google.com with SMTP id 006d021491bc7-60201a116desf946564eaf.2
        for <bitcoindev@gnusha.org>; Sun, 06 Apr 2025 04:47:26 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1743940040; cv=pass;
        d=google.com; s=arc-20240605;
        b=aPaInzc8WXb8HGgU1quWB42kbdYTUkW5tbGYc6IXKPe7M3/+Q2XJ9vQWeLX/64egzg
         qYKI2ZOLmG1WaY7sVWEZVQd2pYZKhyG+TUGB1u2xrhiX3n6XZ2hmswlZkRR3oDN1wPv7
         t1md5m1CvvzOcwW7ugFas6x+Ad1fhW8/VQjcowC3rMd7ejvt4Ti54/CRb8pdeMFmU3Lv
         D6RY57cU5xcXxaBYULO+L/wYnfXEe9uDS62e9/tDC3ZujzTyObzo/o43ZGKRZSBVjf7X
         VCeQAsBdozAhgjRLADhfjQNmaK2jw0MfydHy1CHgS3vfmQyP/GVBO0TEdr2wYxu8ib8g
         /fbw==
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:reply-to:cc:to:subject:message-id
         :date:from:in-reply-to:references:mime-version:dkim-signature;
        bh=X+OYvqxAoAs+MLrqQOIIKP8d3gM6WR9+fBuJ8Qs9FH8=;
        fh=LeI9Rkls1xS53Pt8n+skPEA6GtYOpAVbfaHBKOBziFU=;
        b=NktsM8BI+g51wfrbLtRRgxEO7DPINRXB0x47ufoHl3mKS/6MWqrhsV9Ty6mmF+c5Kn
         /i0XucrS01qoo0RK+We4k8hoW8tawJ2u32XpLa3CvEy4ljqEB6VEs8dyJPXRijWVYdK5
         DgFU11YbPzqG4cLCcCaIrpyQWs6Z0ROdasPu2/SFlaiyGMowfiezi2TIiG9PmzW3BKuT
         ONAYVzHOWyTD5VXMQP1HqygJhELR+f5bpyJr4qKPGCSWHISHdq+OlJ1nz+s2f9zpoSUn
         qB/50qH0lPgk8t1hCd2HYEnlJhNNMpk1D5n2p63BqzlxEhxI/UWjf6K4hxPm9e0MmUmP
         5ngQ==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@starkware.co header.s=google header.b=S9TLfP4D;
       spf=pass (google.com: domain of eli@starkware.co designates 2607:f8b0:4864:20::52f as permitted sender) smtp.mailfrom=eli@starkware.co;
       dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=starkware.co;
       dara=pass header.i=@googlegroups.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1743940040; x=1744544840; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:reply-to
         :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=X+OYvqxAoAs+MLrqQOIIKP8d3gM6WR9+fBuJ8Qs9FH8=;
        b=uAALkGvZ5DL1yrUwPpO7w7cqhXcgZ1UVQU1WHoIrsvWGdD+lO7nWOET96e7cr9Kf4t
         V5oBj2EzOWe7U5ahdy3FncvW8jE8LCTxZRecVjNBsBy16piVSCiS0ttsWVccn0YMtyZO
         wVWHEwYTRUGBppgyjwyLDewSFMhzF0aC+CrX4XfT/rpWfgVWNq+ywOQcDr2yYyjd/jq3
         bTfX6O2cZzBo5RpyCLVQyB6HzR9LrbEzdcx5jHwatvXa8DQ/BMe9MggA7UDXM/HRSPEW
         yWLYcFMBcQ3ykWAOUhZaWMURo7Y+WGX95Z4NqtI7NluIDjNU/NVLYVWWjv+1wjIxjqTq
         TfHw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1743940040; x=1744544840;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:reply-to
         :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:from:to:cc:subject:date:message-id
         :reply-to;
        bh=X+OYvqxAoAs+MLrqQOIIKP8d3gM6WR9+fBuJ8Qs9FH8=;
        b=us717XIM99lInmKADHf/FWa2XidxHrbHvYGRYmb4BR8FcoYgjWWRPZ6BfVUjsb8JLQ
         t6lsVcpRqTJuKFBVXmZspvNCuqRfCjyXmuTMf72y2kd42TC7HVJ0E3Y1xvWo/o1YljFd
         3UF5vKqmzdVxDtvC79CZJtROhMgdFTTucduBwphuVmQU9jpgcqaoRzVKESVQdPIn+3uG
         jKawjF6cud5A26riXxmy5434emrLG6Lb6gCHxTFRcE91w+7QyHXx5GcDBz1j20i82DMU
         NLABcXWSbVr2DPaBEAGbYPnvZ0Wp/xclILjyggwaomqYNQtI1ktz0GO1PrNauxxEJytC
         rLzw==
X-Forwarded-Encrypted: i=2; AJvYcCWB4IlP42NYk83p+GxRGQypfWqku2DzA7TMS18L0XTB8J6rYQ9GXrbmXyxNbkctWsuvIMIARTWJ3Kbd@gnusha.org
X-Gm-Message-State: AOJu0Yz5/NZfCzmez0iqlbBASSx5Y5n/Gu8sQf9iLuyx3H0Egtd0pki3
	3lsFEoMsQPUj1JKrD1Z942LjQrtZyYs3VSH0zb9Peu9hTFyzDAeV
X-Google-Smtp-Source: AGHT+IG9rATxqlS9fdgR7a4CxS3X+VYVhAaJ7Bd93yNKJKcflDx2LzFGYUGLrA72OaFuSGn6bPX4Pw==
X-Received: by 2002:a05:6820:228e:b0:601:a927:351e with SMTP id 006d021491bc7-604200900c2mr3033597eaf.7.1743940040261;
        Sun, 06 Apr 2025 04:47:20 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAL2POAzsZ9h8HfcohDak7kbzi7hfC/3UD5IsAe+sv8HUQ==
Received: by 2002:a05:6820:1acb:b0:5fc:fc5a:c55b with SMTP id
 006d021491bc7-60409e67e4bls1054173eaf.0.-pod-prod-02-us; Sun, 06 Apr 2025
 04:47:15 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCVdZgc9eIbLGsSmVD46VWlqiPEGxYD5jDe6n0v6knYGXyjtvJFbDhJPXAGdMHFRFJfexLNUeclo+D5X@googlegroups.com
X-Received: by 2002:a05:6808:21a4:b0:3fe:b1fd:527f with SMTP id 5614622812f47-4004d9554b8mr2714884b6e.1.1743940035794;
        Sun, 06 Apr 2025 04:47:15 -0700 (PDT)
Received: by 2002:a05:6808:1b8f:b0:3fa:6f09:b173 with SMTP id 5614622812f47-40033cc69d0msb6e;
        Sat, 5 Apr 2025 13:40:45 -0700 (PDT)
X-Forwarded-Encrypted: i=2; AJvYcCUbe7eEyNC6Xb4wz0k+wMM/r3yewHJW4uswCCaRaNxlM+w/we/ao2E/6UNxdqpR+2VjWth8nxzPMh9Q@googlegroups.com
X-Received: by 2002:a05:6830:a92:b0:72a:1dfc:c981 with SMTP id 46e09a7af769-72e40ec179emr3034087a34.25.1743885644225;
        Sat, 05 Apr 2025 13:40:44 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1743885644; cv=none;
        d=google.com; s=arc-20240605;
        b=XcnhF1334Uw64W4wfaVaKED4txX7KHFD7WxdXr6Xj83iiAicWkM/YuGlspdpd1Rijy
         r301y+k/JGfhHGcadG1liW1sLJ7nNV6ZpOJKVuWIiFMZ3XmzgKMKSg2W120RIu+hiDQo
         h5wlQtWCJs5XSxkfmCBba3bfWtBs4hnznj2Tni5N0hUIF/bwLIhTq2L6/hHPIdJK1gGO
         Kai9h4wc+8vuMxNhpC1UyqENahUASC0kv3nc8+Q1pwvLfCFTDLD4FzvLfnxFByBSdWjR
         t2HJlgU4kGNn5fXfS40tm03m6p2jHRNmkd9cazc6Rc/q+QFF901yjTUr+iexY2duKSSD
         1lDw==
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=inH7IcYEF36mnjvmM4mLcUhxjS/v6btfhD5M97wZVtc=;
        fh=42/DGMMtTZ7aAHTtBuGSkvPuHWpnF5SUDtdpyk++WJw=;
        b=JS8yCT5mFjLiHfQgPqaQAjFAZWfm6qX9tS7+l/iqDFLuPVAlLUg5J5/P1LQmXUFkq/
         HiJPE2EoR1HUpGJe/B/PaHVgMSI+E8xLar4IxGoQs0rLswdvEEPbAJRJiZI3CAgjO+zP
         heTjK8pAhme9Z/4crc4KL7Z3BgTJSacq3GUtbN5EPTBVdsnov8AQc6eO2FHTbdPo9YMn
         QvgK2q5JFyaFOINRiZZotQh9osu9+vJRRrmIaXUo0jemBJLYAEMoyuvfKvSMhsfailYS
         CAMRhMpaBTz6WcJGdWptc+k+pTEnF7FWF2oNAPHmMSvxFs5nX4l9h1KEZtKsGRyrQ82K
         eHgQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@starkware.co header.s=google header.b=S9TLfP4D;
       spf=pass (google.com: domain of eli@starkware.co designates 2607:f8b0:4864:20::52f as permitted sender) smtp.mailfrom=eli@starkware.co;
       dmarc=pass (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=starkware.co;
       dara=pass header.i=@googlegroups.com
Received: from mail-pg1-x52f.google.com (mail-pg1-x52f.google.com. [2607:f8b0:4864:20::52f])
        by gmr-mx.google.com with ESMTPS id 46e09a7af769-72e3059ea0esi323849a34.4.2025.04.05.13.40.44
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Sat, 05 Apr 2025 13:40:44 -0700 (PDT)
Received-SPF: pass (google.com: domain of eli@starkware.co designates 2607:f8b0:4864:20::52f as permitted sender) client-ip=2607:f8b0:4864:20::52f;
Received: by mail-pg1-x52f.google.com with SMTP id 41be03b00d2f7-aee79a0f192so1940573a12.3
        for <bitcoindev@googlegroups.com>; Sat, 05 Apr 2025 13:40:44 -0700 (PDT)
X-Forwarded-Encrypted: i=1; AJvYcCVlx+PQTZBPM3kzbxT0eXkcW3aETW/ic7tQzG6pEIq8+F8M6y15DYjeptvrd4420wHJbEprMEO62pVa@googlegroups.com
X-Gm-Gg: ASbGncsMz/5QP0n6kP8XmhyFxvUSOeAn84+GOLVi/nVWtXt6Vn2y0w7cRK4a2r4sIY+
	NcQA9KkFLG5hmZdGnCyhYCYR9Rzk5Eao0+9xHi3/0VBGCAwAItkvQv1KxAoG6l+nFyND1yPO6pM
	RH0cjtjD+ONrc9nSfTkomLEIo1cSa4gitHs6+Mo9vxwjiK03YPXpz31JY7sFc=
X-Received: by 2002:a17:90b:5385:b0:2ff:4a8d:74f8 with SMTP id
 98e67ed59e1d1-306af6ea9demr4457492a91.6.1743885643215; Sat, 05 Apr 2025
 13:40:43 -0700 (PDT)
MIME-Version: 1.0
References: <CAEM=y+XMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg@mail.gmail.com>
 <CAC3UE4K7AG96Njra3WSnt=1yPVZSnT7gktnwktaumPgOD0hU8Q@mail.gmail.com>
In-Reply-To: <CAC3UE4K7AG96Njra3WSnt=1yPVZSnT7gktnwktaumPgOD0hU8Q@mail.gmail.com>
From: "'Eli Ben-Sasson' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
Date: Sat, 5 Apr 2025 23:40:32 +0300
X-Gm-Features: ATxdqUE9afsHY4Dnb6a_uKirYRWkUIGFq12-fW-xeV-r0Kp0xzNniwehXA4MkzI
Message-ID: <CAHLj6=OxUUempwziiFdo2eqEhiTHsobgdT+eDDx_y64bHBGiqA@mail.gmail.com>
Subject: Re: [bitcoindev] Post Quantum Signatures and Scaling Bitcoin
To: Dustin Ray <dustinvonsandwich@gmail.com>
Cc: Ethan Heilman <eth3rs@gmail.com>, 
	Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: multipart/alternative; boundary="0000000000004b149206320e0446"
X-Original-Sender: eli@starkware.co
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@starkware.co header.s=google header.b=S9TLfP4D;       spf=pass
 (google.com: domain of eli@starkware.co designates 2607:f8b0:4864:20::52f as
 permitted sender) smtp.mailfrom=eli@starkware.co;       dmarc=pass
 (p=QUARANTINE sp=QUARANTINE dis=NONE) header.from=starkware.co;
       dara=pass header.i=@googlegroups.com
X-Original-From: Eli Ben-Sasson <eli@starkware.co>
Reply-To: Eli Ben-Sasson <eli@starkware.co>
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: -1.0 (-)

--0000000000004b149206320e0446
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I believe there are quite a few works discussing FRI and STARKs in quantum
oracle model, e.g.:
https://doi.org/10.48550/arXiv.2411.05360
https://doi.org/10.1109/FOCS52979.2021.00014




On Fri, Apr 4, 2025 at 8:27=E2=80=AFPM Dustin Ray <dustinvonsandwich@gmail.=
com>
wrote:

> This is a great post, thank you for sharing. I have one small tiny commen=
t
> 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 propos=
ed
> for critical security infrastructure, there is currently no formal securi=
ty
> argument for FRI against a quantum threat model that I am aware of. I'm n=
ot
> 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> w=
rote:
>
>> 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 =
need 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 scalabil=
ity
>> (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 =
to
>> 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 resistanc=
e=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-55b=
82012452b
>> [3]: John Light, Validity Rollups on Bitcoin (2022)
>>
>> https://github.com/john-light/validity-rollups/blob/main/validity_rollup=
s_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 Group=
s
>> "Bitcoin Development Mailing List" group.
>> To unsubscribe from this group and stop receiving emails from it, send a=
n
>> email to bitcoindev+unsubscribe@googlegroups.com.
>> To view this discussion visit
>> https://groups.google.com/d/msgid/bitcoindev/CAEM%3Dy%2BXMLuGH-MAfkYanfb=
U3Ynduw54jDVguKxgO2xEtnSEkZg%40mail.gmail.com
>> .
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit
> https://groups.google.com/d/msgid/bitcoindev/CAC3UE4K7AG96Njra3WSnt%3D1yP=
VZSnT7gktnwktaumPgOD0hU8Q%40mail.gmail.com
> <https://groups.google.com/d/msgid/bitcoindev/CAC3UE4K7AG96Njra3WSnt%3D1y=
PVZSnT7gktnwktaumPgOD0hU8Q%40mail.gmail.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/=
CAHLj6%3DOxUUempwziiFdo2eqEhiTHsobgdT%2BeDDx_y64bHBGiqA%40mail.gmail.com.

--0000000000004b149206320e0446
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">I believe there are quite a few works discussing FRI and S=
TARKs in quantum oracle model, e.g.:<div><a href=3D"https://doi.org/10.4855=
0/arXiv.2411.05360">https://doi.org/10.48550/arXiv.2411.05360</a></div><div=
><a href=3D"https://doi.org/10.1109/FOCS52979.2021.00014">https://doi.org/1=
0.1109/FOCS52979.2021.00014</a></div><div><br></div><div><br><br></div></di=
v><br><div class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" cla=
ss=3D"gmail_attr">On Fri, Apr 4, 2025 at 8:27=E2=80=AFPM Dustin Ray &lt;<a =
href=3D"mailto:dustinvonsandwich@gmail.com">dustinvonsandwich@gmail.com</a>=
&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div=
 dir=3D"auto">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 underl=
ying commitment scheme) is secure in a quantum adversary model. We conjectu=
re that it is, because it relies only on hashes as the primitive in an erro=
r correcting code, but unlike other cryptographic primitives used or propos=
ed for critical security infrastructure, there is currently no formal secur=
ity 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 secur=
ity arguments are warranted for any potential change to the bitcoin signatu=
re 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"><div dir=3D"ltr" cl=
ass=3D"gmail_attr">On Fri, Apr 4, 2025 at 9:34=E2=80=AFAM Ethan Heilman &lt=
;<a href=3D"mailto:eth3rs@gmail.com" target=3D"_blank">eth3rs@gmail.com</a>=
&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px =
0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">I st=
rongly believe Bitcoin will 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" target=
=3D"_blank">bitcoindev+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&amp;utm_source=3Dfooter" target=3D"_blank">https:=
//groups.google.com/d/msgid/bitcoindev/CAC3UE4K7AG96Njra3WSnt%3D1yPVZSnT7gk=
tnwktaumPgOD0hU8Q%40mail.gmail.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/CAHLj6%3DOxUUempwziiFdo2eqEhiTHsobgdT%2BeDDx_y64bHBGiqA%40mail.g=
mail.com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/=
d/msgid/bitcoindev/CAHLj6%3DOxUUempwziiFdo2eqEhiTHsobgdT%2BeDDx_y64bHBGiqA%=
40mail.gmail.com</a>.<br />

--0000000000004b149206320e0446--