path: root/86/7fa203a9937414bf6892eda5cd10e20383e066

Delivery-date: Mon, 14 Apr 2025 13:49:23 -0700
Received: from mail-qv1-f59.google.com ([209.85.219.59])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDSJ7DXSQ4PRBSPJ6W7QMGQEAECUYXQ@googlegroups.com>)
	id 1u4Qk6-0007Fw-JJ
	for bitcoindev@gnusha.org; Mon, 14 Apr 2025 13:49:23 -0700
Received: by mail-qv1-f59.google.com with SMTP id 6a1803df08f44-6e900f6dcadsf102271226d6.3
        for <bitcoindev@gnusha.org>; Mon, 14 Apr 2025 13:49:22 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1744663756; cv=pass;
        d=google.com; s=arc-20240605;
        b=Od0bfUGk8cgYMw2ZNxmdu1tBlAsEkcMTiRAWVNErFh+aiMGcjn/e1TYRWMo+MVnQTb
         W0ylVVZ5QYo8krlPl9ahr/+5fOGf7Vf6SOWNRwLY6PDH6khdEFY02FuNNX3TnFXF+tsT
         w2uZEPxRiTWRkDwAYTupOd/b2Ri7V7hFvax+Zs+2/aNQwdEoyFhPDwUS9K34sy80UFOh
         iFPdvsPFB4xmc5IMGAWrGcRg5CTHfqIF0W2CqQOGggp6pRuCIEDIqTWdg+oUb1Uekwvs
         dhho+NKgw1knwlaBxuupwKwgt0Z1O668bVJ0Gwa6gHMN2v/lJtRrHDwLAu/0YRhewlYM
         yxvw==
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:content-transfer-encoding:cc:to
         :subject:message-id:date:from:in-reply-to:references:mime-version
         :sender:dkim-signature:dkim-signature;
        bh=7rIUuDJoXgWt3CpnEh4caW3AjVdbwX3CkaijLEJENS0=;
        fh=3kR7CRWIerS170f+m1VQBMcgsa+aa24BIOyYDkVO+x8=;
        b=X2k4YcoACkJa7JxM9tJgOjMguCQFP5sgdWu5IwlAwkdQ5vNDUlf5RP+0XCECuPVnlT
         ERgAF4aVSsqLdobLbXag7BsH3TmK9w/2+GnDm5t+9dp8DapyhwTjAaPzbJBi9SEW6d2H
         1Wqvzp2XzJ+7gIzm2tYPvy+ArtBdKmBYSyhDnOzIwVgKrEFlk0zmd2QJrM7gzF9jIipr
         n8GFg2NOc+6lmVQdtJFfbRUWkymurjbuC+Nyd64wcEp36EFK2Rp5RBKHe3Ph7d8BXoS9
         DDVhQsMMzIF61y4cKdFlnOle4IYFXn4L3nrBLKDsOdkMoWwIlPeiOnt7nruTUpWzHkbh
         6ttQ==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=jrFHtxtx;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::631 as permitted sender) smtp.mailfrom=eth3rs@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=1744663756; x=1745268556; 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:content-transfer-encoding:cc:to:subject
         :message-id:date:from:in-reply-to:references:mime-version:sender
         :from:to:cc:subject:date:message-id:reply-to;
        bh=7rIUuDJoXgWt3CpnEh4caW3AjVdbwX3CkaijLEJENS0=;
        b=abykLXzZFVH450dr04InRAsRSke2W0CgpJ3ffqjTbM7FQDRKI59FyYmtHpI/TuQnNG
         uxZXAdRNVFLtB96Z2VN6d4UeRQ5tg5k2Ky+vIAolSNXwbrJnd8ilBraUYp2b/fhBMwjk
         VjDIlH41WXngMOXKS1nyomTCn8dukdcVbrrWNU6B01756bRYsINAg9rwwg9wwjIN9Utm
         Fbf4+j3DZ+8LUHo3m9ASabWXMEAHkuEPVZ7pdk6jwJ+xFiIS4bWXVtB3HOCQj8A//TlY
         hsSMk4Teg2so7y8qTEJBFqZ6VH47YeIBonlpY0oZFcScJD0WOdAWgm6VyiKmKlGMPT7r
         mD6Q==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1744663756; x=1745268556; 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:content-transfer-encoding:cc:to:subject
         :message-id:date:from:in-reply-to:references:mime-version:from:to:cc
         :subject:date:message-id:reply-to;
        bh=7rIUuDJoXgWt3CpnEh4caW3AjVdbwX3CkaijLEJENS0=;
        b=MipFpkNjCRmtbe9Fc/eXtFzzyW04NlBhf8QCtUaJQVEaTZpfmNzB4h+VBNzrwlwaF3
         /JSOZbnEL+M4onBpbuiEiDHJz1QWVLCkxLVmB17TYU841aLv9D+JFEZ5Teo/WquKBPMQ
         PQ2QrgkrwE3sI6aE62tQtg2k30dr1MaVYuhaydfZh53na7zhhJXWpi9AIjxzz+h5cbRp
         3nUZqO/gAUzwY+xaWAK19lbM5Hh24zi3Xh8ULsoFQPB9fss29Q0eCgTOvFlfSOlhUmig
         MzG3h5WgA2f5FoN4cJf+NJjAcguORFKnhP7sBVJFlI1tsoKjPf/IhayBFmppUWMVcuKE
         76Fg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1744663756; x=1745268556;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:content-transfer-encoding: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=7rIUuDJoXgWt3CpnEh4caW3AjVdbwX3CkaijLEJENS0=;
        b=NCmy4f/gVzpcQ+7Nl5czG8MabiNPFGcVBeb8m6hFwSVyi/asKjkc/0wBfsrYZMBjQT
         CNtTwb0qAqqNYL2UylIjLdsQciG14aA1vUpjf7OKU9TBRur4tqm5FVDZz5vP0fMu5Jyd
         uYfTf1+CPR0H7VSPc+Uzc7oi/tdqfvBltnsEe5c//M9gSBkWYOT4KbxoI6yG4dlHKJgV
         rlwGzXNsHTHdvctiypYO3clGct7ygNU6BrjetJ/VGwqis473kj7kaUk9UjRS919gClY9
         xjpY538q38EI2AdR2efqBUjgv2Pe7jKMg7I9W2u1gmKk++HBhRTm4VLtWF06d7RAbZgS
         mRhQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCXaMlmCkrp8idSVWanMXnx3rlCj+OQa1ll8oU/HFeFrS0d/hNXcVAFJ3197JHfo3JeP1WqBp5E5fR68@gnusha.org
X-Gm-Message-State: AOJu0YwKHXVu4jjT+draqS/pIu+fz4FXfaw9TaqbP6iiUAVNeIDb0yLz
	uvvdNvR/3GG7PPxfkTqHN/Crocu5cfW86sjfVdS34c0l3xVnZXQt
X-Google-Smtp-Source: AGHT+IHeSx1PF8zCKMHiVPCHsKPgDHQtjOTEhJu56tbZww7Eysv6EgsHZG8vCehXUNLpEAzIzcE3gQ==
X-Received: by 2002:a05:622a:11c8:b0:476:76bc:cfc4 with SMTP id d75a77b69052e-479775478f8mr245344191cf.21.1744663756484;
        Mon, 14 Apr 2025 13:49:16 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJccxDNeESRsjm09ItmakhwIQ5nlzfFhzkcJ9OLEGk8mQ==
Received: by 2002:a05:622a:17c9:b0:476:da84:1d52 with SMTP id
 d75a77b69052e-4796b31b660ls10740131cf.0.-pod-prod-09-us; Mon, 14 Apr 2025
 13:49:13 -0700 (PDT)
X-Received: by 2002:a05:620a:1aa7:b0:7c7:a614:7214 with SMTP id af79cd13be357-7c7af0f8835mr1892644685a.5.1744663753230;
        Mon, 14 Apr 2025 13:49:13 -0700 (PDT)
Received: by 2002:a05:600c:1d0d:b0:43d:85ca:231a with SMTP id 5b1f17b1804b1-43f387f2bf6ms5e9;
        Mon, 14 Apr 2025 12:36:12 -0700 (PDT)
X-Received: by 2002:a05:600c:1d84:b0:43d:b3:f95 with SMTP id 5b1f17b1804b1-43f3a9af802mr106055505e9.28.1744659370609;
        Mon, 14 Apr 2025 12:36:10 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1744659370; cv=none;
        d=google.com; s=arc-20240605;
        b=BF7VE3n2qaP8eUN0sR9rQurfnoxhgcwCAS1Exmq3Mu11ytwvvn7zHvrzX/UZ95hafo
         rItEyvUcQERPH/TmKo0b890QSOCiPFiMnD5RoJpnBdhAZRMVm9wd3sKmYLB61k5b6V2d
         qms4Anl42C2WlgM+lGMNEbPVJ9lZ/B6FFEJ8pd0m+Dbt+nevTm69Ez35t4ZGl7GDQCaF
         yQCHgxMNblzDgvQmd2e4ubPQAIvL77cKZpuba0FhjSKn/OIAcCPaAo+wxUjPnZ65CZ+U
         OVjpobKBf3bQtHAw9Fe0cp07P2uu7aUqQl7VfABddq8nJnFCsPemiUq5TH2f5gLy4BTw
         HzsA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=content-transfer-encoding:cc:to:subject:message-id:date:from
         :in-reply-to:references:mime-version:dkim-signature;
        bh=sW+ic9XX3CwJ5AQydeHBlUS2dBK2ZIztcuY5jL08y64=;
        fh=dRl5MJeON1RwI+/xO4/cP/Y3U38+pgB9/4rd/p1o9tg=;
        b=gFmwk84/kFOCLCcshi0AOiBKWHs3qufBMwFEonlqQMIhiH0L5N2TBMpkjZHrbkzH8U
         fHnwXzb8kIF7uh27/VsXZtTduHMu/43M4n4jiVC6FdDSMNkLruBPcaSj+lb6NlZwV6zF
         15EcMANmgaT8SDIOE6aqiweUwxiI99ZROOb6ohnGIhcvJqJRcBduxRbhH5YI9tsqTwG+
         EfE9vI8SP9hUQpOJthn5IB/y2wS6iDOQqXGmU+GQJFW2Y6bT874W5130VUgmL0FAyROT
         rLukAuUyXXDLEgnez0vYqLo7D7BGPKXV1OG3MR5irGbmEJsjgaGNibUy5gRQD6EZzDha
         7IZA==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@gmail.com header.s=20230601 header.b=jrFHtxtx;
       spf=pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::631 as permitted sender) smtp.mailfrom=eth3rs@gmail.com;
       dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com;
       dara=pass header.i=@googlegroups.com
Received: from mail-ej1-x631.google.com (mail-ej1-x631.google.com. [2a00:1450:4864:20::631])
        by gmr-mx.google.com with ESMTPS id 5b1f17b1804b1-43f20a82897si5562835e9.1.2025.04.14.12.36.10
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128);
        Mon, 14 Apr 2025 12:36:10 -0700 (PDT)
Received-SPF: pass (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::631 as permitted sender) client-ip=2a00:1450:4864:20::631;
Received: by mail-ej1-x631.google.com with SMTP id a640c23a62f3a-ac2dfdf3c38so925569466b.3
        for <bitcoindev@googlegroups.com>; Mon, 14 Apr 2025 12:36:10 -0700 (PDT)
X-Gm-Gg: ASbGncvLIpfqJuze/DuENLLSuMpVbxkym3ni6rd16+QcNQi9LHm4WZpIXfRjioijOEH
	ttK4edmnlxNveCGl17GeDWJ8Ory/Jx3TcSRqoybzZjOsuPL53lM5i85aZYQsdauGWyIcI9IWA9B
	wQDyacYHExHxE6StnwXG7jKb3r+Sy9QGug0PvgkN+lo1AYbk+LbS/6RjbTPwoRcVrrIQQ=
X-Received: by 2002:a17:907:3d92:b0:ac3:bbc8:ecab with SMTP id
 a640c23a62f3a-acad3457ff4mr1125658366b.11.1744659369781; Mon, 14 Apr 2025
 12:36:09 -0700 (PDT)
MIME-Version: 1.0
References: <CAEM=y+XMLuGH-MAfkYanfbU3Ynduw54jDVguKxgO2xEtnSEkZg@mail.gmail.com>
 <p8kWp-qhHYIB-nMWGHI5GJ65j2Ve_apGJXG3QByimJrGHKcyrfZII1OG0I40KJMCyeV-HDuhLfg-29S3nfKu1k9cUbvtJ_N5n2x9jmopRxA=@wuille.net>
In-Reply-To: <p8kWp-qhHYIB-nMWGHI5GJ65j2Ve_apGJXG3QByimJrGHKcyrfZII1OG0I40KJMCyeV-HDuhLfg-29S3nfKu1k9cUbvtJ_N5n2x9jmopRxA=@wuille.net>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Mon, 14 Apr 2025 15:35:33 -0400
X-Gm-Features: ATxdqUGORkJ1qKpV2SCFwl7LJMSsXoiuZXqEU98A4Cv5D5YEz7uTicBw0na36bE
Message-ID: <CAEM=y+VK2VwoTc3VbHFbARm9no6qJivrug+LPuGy_m8+PFELOA@mail.gmail.com>
Subject: Re: [bitcoindev] Post Quantum Signatures and Scaling Bitcoin
To: Pieter Wuille <bitcoin-dev@wuille.net>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Original-Sender: eth3rs@gmail.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@gmail.com header.s=20230601 header.b=jrFHtxtx;       spf=pass
 (google.com: domain of eth3rs@gmail.com designates 2a00:1450:4864:20::631 as
 permitted sender) smtp.mailfrom=eth3rs@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 (/)

> I'm happy to see thinking and discussion in this area.

Getting this discussion going was exactly my intent. I'm not
presenting so much a solution as we might want to do this at some
point what are problems and can we solve them?

> If it turns out to be the case that PQ schemes need more on-chain size, b=
ut have lower per-byte computation cost, a reasonable argument could be mad=
e that a higher discount factor for PQ data is acceptable.

I was focused on size because computation is pretty great for most PQ
signature schemes. PQ signatures are far cheaper to validate per byte
and according to BIP-360 Falcon is cheaper than edDSA per signature
verification.

EdDSA Cycles to verify: 130,000
FALCON-512 Cycles to verify: 81,036

This is one of the reasons I am very optimistic that Bitcoin will move
to post-quantum signatures. If research shows that these signature
schemes are sufficiently JPEG resistant, and I think it will, then a
discount is very attractive.

> I don't think pre-aggregation (beyond a single-transaction-wide one) is r=
ealistic, as it effectively breaks in-mempool transaction replacement, turn=
ing every pre-aggregated group of transactions that is being relayed togeth=
er into an atomic package that must be taken or not as a whole.

In some circumstances it is possible you could aggregate (P+C1, P+C2)
into (P+C1+C2). If you can prove that P is the same in both
transactions thus the balance and authentication properties are
maintained. However I think what you have described is the shape of
the problem we need to solve.

Consider transactions: T1, T1', T2, T3, T4, T5
where T1 and T1' are double spends, i.e., spend the same output to
different outputs. If half the mempool aggregates TA =3D (T1, T2, T3)
and the other half aggregates TB =3D (T1', T4, T5). TA and TB are
mutually exclusive and transactions are needlessly dropped on the
floor. This is a currently existing griefing vector with coinjoins
today and is an issue with mimblewimble aggregation. I don't think we
have seen it abused much, but that doesn't mean we can ignore it.

I believe this is a solvable problem, but it requires careful thought
and I haven't seen a fully baked answer. What follows is my intuition
on how this might be solved.

Approach one: have relay nodes share a map of what UTXOs would be
spent by their mempool prior to performing an aggregation to detect
and resolve doublespends.
Approach two: allow an aggregator to non-interactively aggregate a set
of transactions if they are the sender or receiver of funds in all the
transactions they are aggregating.

My biggest concern here is a conflict between aggregator/relay
incentives and miner incentives that either causes miners to be
aggregators or reduces the profitability of miners. This conflict
arises from the fact that, unless prevented by the protocol, an
aggregator can aggregate high fee transactions with low fee
transactions in such a way as to reduce miner fees and possibility
make fees for themselves.

For the sake of example assume blocksize allows only two transactions per b=
lock:
T1 has a 100 sat/vb fee
T2 has a 100 sat/vb fee
T3 has a 50 sat/vb fee
T4 has a 50 sat/vb fee

If the miner was the aggregator they would aggregate (T1 + T2) and
mine it to get the highest fee.
Instead an aggregator who is not a miner could collect a fee from the
creator of T3 and T4 and aggregate (T1 + T3) and (T2 + T4) thereby
raising the average fee of T3 and T4. The miner loses out on fees.

Approach two makes this less of an issue because the creator of T1,
if they are aware T2 exists, is unlikely to consent to having T1
aggregated with T3 since it lowers the total fee.

This relay vs miner conflict isn't an entirely new issue in Bitcoin.
Miners today could run relay nodes and keep the high fee transactions
for themselves. I assume this isn't done very much in 2025 because the
block subsidy still dominates, but is likely to be a bigger issue when
fees dominate.

On Mon, Apr 14, 2025 at 9:47=E2=80=AFAM Pieter Wuille <bitcoin-dev@wuille.n=
et> wrote:
>
> Hi Ethan,
>
> thank you bringing this up. I'm unconvinced about the practicality, but I=
'm happy to see thinking and discussion in this area.
>
> Two points addressed below:
>
> On Friday, April 4th, 2025 at 12:29 PM, Ethan Heilman <eth3rs@gmail.com> =
wrote:
>
> > 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.
>
> I don't disagree with the overall point raised here, but I do think it's =
worth distinguishing between the "size" (bandwidth/storage) and "computatio=
n" (CPU/IO) aspects of scalability.
>
> If it turns out to be the case that PQ schemes need more on-chain size, b=
ut have lower per-byte computation cost, a reasonable argument could be mad=
e that a higher discount factor for PQ data is acceptable. I don't know wha=
t the trade-off here ought to be, and this does not diminish your "JPEG res=
istance" argument, but I did want to point out that just counting size isn'=
t the only constraint here.
>
> > 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.
>
> I don't think pre-aggregation (beyond a single-transaction-wide one) is r=
ealistic, as it effectively breaks in-mempool transaction replacement, turn=
ing every pre-aggregated group of transactions that is being relayed togeth=
er into an atomic package that must be taken or not as a whole. Consider fo=
r example the case where transactions P, C1, and C2 are relayed, with C1 an=
d C2 depending on P. One node sees P and C1, but not C2, they may pre-aggre=
gate prior to relay. Another node sees P and C2, but not C1, they may pre-a=
ggregate those prior to relay. These two packages (P+C1, P+C2) cannot be co=
mbined, so we've effectively forced the network/miners to choose between on=
e of C1 or C2, unless the individual transactions are still available somew=
here.
>
> I fear this is a very fast way to cause mining without direct-to-miner tr=
ansaction submission from users to become uncompetitive, making entering th=
e mining business permissioned, and effectively removing the point of havin=
g a decentralized consensus mechanism in the first place.
>
> --
> Pieter
>

--=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/=
CAEM%3Dy%2BVK2VwoTc3VbHFbARm9no6qJivrug%2BLPuGy_m8%2BPFELOA%40mail.gmail.co=
m.