path: root/0f/655b0552d627372d75a0921fbaa8ccfa4f240a

Return-Path: <weiji.g@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id F1C63C002A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  5 May 2023 23:07:04 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id BB6824049F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  5 May 2023 23:07:04 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org BB6824049F
Authentication-Results: smtp2.osuosl.org;
 dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
 header.a=rsa-sha256 header.s=20221208 header.b=ZYAdAAIN
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level: 
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id BkgohDDwU_WW
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  5 May 2023 23:07:03 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 983F5400EC
Received: from mail-vk1-xa2c.google.com (mail-vk1-xa2c.google.com
 [IPv6:2607:f8b0:4864:20::a2c])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 983F5400EC
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  5 May 2023 23:07:03 +0000 (UTC)
Received: by mail-vk1-xa2c.google.com with SMTP id
 71dfb90a1353d-45046c21e55so30475e0c.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 05 May 2023 16:07:03 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=gmail.com; s=20221208; t=1683328022; x=1685920022;
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:from:to:cc:subject:date:message-id:reply-to;
 bh=sz7HzfH0S3JHQlA7tkNmOIwt2jqIGUkWEgjnkla+jak=;
 b=ZYAdAAINP2Tq59HsveOBaG8C2v34q5hP0KgIEiwCtDYcfvaJYZel6WHI5IaqRexn20
 spJhDnNQbnqQvt4WoFBh1yvukxk7d4nD/wUnmQrG2uHVXxB9t1el5c+gpdSzlaqPBXE8
 1GqDxAR0omRu8YubUbcuhRkU7kcM8LNbV7O0yC16a+hiMuOyHgrCZ4isJvdwF0eacqmt
 NoiEwCJW2E3ZfwFB04PW7UdjHBcu/f9HvoS7r5Pv5HvikycVU0j1NIz9LsQewZVDBtji
 BBx3WydzKcmbQU16r0qdvdo7dsGyz5Q0h52Ovqi87gON9+G7+wucWQPZUxtbqZUdCX87
 GTjQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20221208; t=1683328022; x=1685920022;
 h=cc:to:subject:message-id:date:from:in-reply-to:references
 :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id
 :reply-to;
 bh=sz7HzfH0S3JHQlA7tkNmOIwt2jqIGUkWEgjnkla+jak=;
 b=CHCnM1w0VAqRMCTPU+7I3JzkwYnrbM26zQYfJBZTKiLFEueS+pOGZUEfDDxkCCmYn8
 wJrGjs50AsDb8A0GeX7VzRZm4kufR9eAZq8XXYbTdo4JNvPmDTO7bBHueNtfJFBjMhbc
 RkmW/YjSUly1bggejOXvo9/MerzeuK7QruJU1mjIJtxdtdHMty3DWq6ksx69bLXS4tRV
 zMpVA4M/t/sodntTVOF2H9pt56DP/nQjXbcRQv8xs9uRNModFqAawyiW+IqQBtv1XFLF
 FU8h0GyNfPD5EbYlsIbCMsQJj5h+A/4S3M0gl1+4lbHOGtLql+od4Tc9OPROmYSTvxZ7
 b19w==
X-Gm-Message-State: AC+VfDwVumcGCU6bEEQstAe4W1KytN2EIKyKEM/gYtjk2x8ou7nNKjx2
 3jXJ9b55d/Ze2to2PufnXo5ce/Ye6fskxzMH5xw=
X-Google-Smtp-Source: ACHHUZ5MJD3KBYNVoXJAPpli9g3hMxOqc6Rd94nolXnZRaxuZPYtEpDSvhOF2K9Qp0jqEwqZc010JcpqhzofkzAbQSQ=
X-Received: by 2002:a1f:4144:0:b0:43c:5b5a:6c22 with SMTP id
 o65-20020a1f4144000000b0043c5b5a6c22mr992267vka.13.1683328022220; Fri, 05 May
 2023 16:07:02 -0700 (PDT)
MIME-Version: 1.0
References: <CA+ydi=LtskFh89TW75=CBwbdZzWR-ZjWS77TnrF4G+xUfm8z+Q@mail.gmail.com>
 <xNzSDtvj-BH4EW9eJMqn_yAiVUEiggnS3WIrvLml6gGAZ6CPADO9pbPV4B30txzSY9laEmX3ckXX8L2Hu18ZrWMUjMH23csL-YK-mDse6DY=@protonmail.com>
 <CA+ydi=K7kePFPXbTP6S63SdddORnc6nVoHqR4gDVoeX3uY-S-Q@mail.gmail.com>
 <s3urNahBotY-aYGaQyY7wz2Sh8UXbqHX2PvZyRcyaMJF6MjUrabv0p_ytE3m1Cu9r79MY649RoulaBPuqGLrSD8qwOfCS-n-HymOEyih5yQ=@protonmail.com>
 <CA+ydi=+6oSQ2oEeuBDQs7fzWL75h4CYb3k4_SS3VbFgxJwDGiA@mail.gmail.com>
 <O8340coA0WBuYzHgkZ6ov7Yp3aqvnGeCeFKHh9bqZdkQTS3xtjEDlW4Hjhc7UgD1XltJyYDOFzDN4JthXq1pdCrMM8cYNfVBIOvLbR8tro8=@protonmail.com>
In-Reply-To: <O8340coA0WBuYzHgkZ6ov7Yp3aqvnGeCeFKHh9bqZdkQTS3xtjEDlW4Hjhc7UgD1XltJyYDOFzDN4JthXq1pdCrMM8cYNfVBIOvLbR8tro8=@protonmail.com>
From: Weiji Guo <weiji.g@gmail.com>
Date: Sat, 6 May 2023 07:06:51 +0800
Message-ID: <CA+ydi=KMm6LW7W+NAUfRDESaJCg+smkiGS2WHKtYRWVGmM_0YA@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000ce165d05fafa5885"
X-Mailman-Approved-At: Sat, 06 May 2023 09:38:04 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] proposal: new opcode OP_ZKP to enable ZKP-based
 spending authorization
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 05 May 2023 23:07:05 -0000

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

Hi ZmnSCPxy,

> As the network is pseudonymous, an anonymous attacker can flood the
fullnode mempool network with large numbers of non-aggregated transactions,
then in cooperation with a miner confirm a single aggregated transaction
with lower feerate than what it put in the several non-aggregated
transactions.

Arguably this is hardly a feasible attack. Let's suppose the attacker
creates 1000 such transactions, and attaches each transaction with a small
amount of transaction fee X. The total fee will be 1000*X collectible by
the aggregation vendor, who pays the miner a fee Y. We can reasonably
assume that 1000*X is much larger than Y, yet X is much smaller than Y.
Note that Y is already much larger than the regular fee for other
transactions as the aggregated transaction should contain many inputs and
many outputs, thus very large in size.

Now, the attacker will have to generate proofs for these 1000 transactions,
which is non-trivial; and pay for 1000*X upfront. The aggregation vendor
has to spend more computing power doing the aggregation (or recursive
verification) and take (1000*X - Y) as profit. Miner gets Y.

Miners are unlikely to collude with the attacker. I don't think the vendor
would, given profit of 1000*X - Y. Or the attacker could play the vendor,
however, it is still not a trivial attack after spending lots of computing
power generating all the proofs and aggregation/recursion, and paying at
least Y, which is also non-trivial given the size.

All that being said, let's focus on the OP_ZKP for now and leave
aggregation or recursive verification for future discussion. I brought up
the scalability issue just to stress that there is potential room for
further improvements. The research and implementation might take much
longer. As far as I know, CISA (cross input signature aggregation) is still
experimental. Again, thank you very much for detailed analysis and replies.

Regards,
Weiji

On Fri, May 5, 2023 at 1:13=E2=80=AFAM ZmnSCPxj <ZmnSCPxj@protonmail.com> w=
rote:

> Good morning Weiji,
>
> The issue here is that non-aggregated transaction are a potential attack
> vector.
>
> As the network is pseudonymous, an anonymous attacker can flood the
> fullnode mempool network with large numbers of non-aggregated transaction=
s,
> then in cooperation with a miner confirm a single aggregated transaction
> with lower feerate than what it put in the several non-aggregated
> transactions.
> The attacker ends up paying lower for the single confirmed transaction,
> even though it cost the fullnode network a significant amount of CPU to
> process and validate all the non-aggregated transactions.
>
> Once the single aggregate transaction is confirmed, the fullnodes will
> remove the non-aggregated transactions from the mempool, clearing out the=
ir
> mempool limit.
> Then the attacker can once again flood the fullnode mempool network with
> more non-aggregated transactions, and again repeat with an aggregated
> transaction that pays below the total of the non-aggregated transactions,
> repeatedly increasing the load on the mempool.
>
> Thus, we should really make transactions that could appear in the mempool
> non-aggregatable with other transactions in the mempool.
> You should arrange for aggregation before the blockchain-level transactio=
n
> hits the mempool.
>
> One can compare cross-input signature aggregation designs.
> Signature aggregation is only allowed within a single blockchain-level
> transaction, not across transactions, precisely so that a transaction tha=
t
> appears in the mempool cannot have its signatures aggregated with other
> transactions, and preventing the above attack.
> Anyone trying to take advantage of signature aggregation needs to
> cooperatively construct the blockchain-level transaction outside of the
> mempool with other cooperating actors, all of which perform the validatio=
n
> themselves before anything hits the mempool.
>
> Similarly I can imagine that cross-input ZKP aggregation would be
> acceptable, but not cross-transaction ZKP aggregation.
> (And if you want to push for ZKP aggregation, you should probably push fo=
r
> cross-input signature aggregation first, as you would probably need to
> solve similar problems in detail and I imagine signature aggregation is
> simpler than general ZKP aggregation.)
>
> Always expect that the blockchain and its supporting network is attackabl=
e.
> Do ***NOT*** focus on blocks --- focus on the load on the mempool (the
> block weight limit is a limit on the mempool load, not a limit on the blo=
ck
> CPU load!).
> The mempool is a free service, we should take care not to make it abusabl=
e.
> On the other hand, blockspace is a paid service, so load on it is less
> important; it is already paid for.
> I strongly recommend **DISALLOWING** aggregation of ZKPs once a
> transaction is in a form that could potentially hit the mempool, and to
> require paid services for aggregation, outside of the unpaid, free mempoo=
l.
>
> Regards,
> ZmnSCPxj
>

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

<div dir=3D"ltr">Hi ZmnSCPxy,<span class=3D"gmail-im" style=3D"color:rgb(80=
,0,80)"><div><br></div><div>&gt; As the network is pseudonymous, an anonymo=
us attacker can flood the fullnode mempool network with large numbers of no=
n-aggregated transactions, then in cooperation with a miner confirm a singl=
e aggregated transaction with lower feerate than what it put in the several=
 non-aggregated transactions.</div><div><br></div></span><div>Arguably this=
 is hardly a feasible attack. Let&#39;s suppose the attacker creates 1000 s=
uch transactions, and attaches=C2=A0each transaction with a small amount of=
 transaction fee X. The total fee will be 1000*X collectible by the aggrega=
tion vendor, who pays the miner a fee Y. We can reasonably assume that 1000=
*X is much larger than Y, yet X is much smaller than=C2=A0Y. Note that Y is=
 already much larger than the regular fee for other transactions as the agg=
regated transaction should contain many inputs and many outputs, thus very =
large in size.=C2=A0</div><div><br></div><div>Now, the attacker will have t=
o generate proofs for these 1000 transactions, which is non-trivial; and pa=
y for 1000*X upfront. The aggregation vendor has to spend more computing po=
wer doing the aggregation (or recursive verification) and take (1000*X - Y)=
 as profit. Miner gets Y.=C2=A0</div><div><br></div><div>Miners are unlikel=
y to collude with the attacker. I don&#39;t think the vendor would, given p=
rofit of 1000*X - Y. Or the attacker could play the vendor, however, it is =
still not a trivial attack after spending lots of computing power generatin=
g all the proofs and aggregation/recursion, and paying at least Y, which is=
 also non-trivial given the size.</div><div><br></div><div>All that being s=
aid, let&#39;s focus on the OP_ZKP for now and leave aggregation or recursi=
ve verification for future discussion. I brought up the scalability issue j=
ust to stress that there is potential room for further improvements. The re=
search and implementation might take much longer. As far as I know, CISA (c=
ross input signature aggregation) is still experimental. Again, thank you v=
ery much for detailed analysis and replies.</div><div><br></div><div>Regard=
s,</div><div>Weiji</div></div><br><div class=3D"gmail_quote"><div dir=3D"lt=
r" class=3D"gmail_attr">On Fri, May 5, 2023 at 1:13=E2=80=AFAM ZmnSCPxj &lt=
;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.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">Good mor=
ning Weiji,<br>
<br>
The issue here is that non-aggregated transaction are a potential attack ve=
ctor.<br>
<br>
As the network is pseudonymous, an anonymous attacker can flood the fullnod=
e mempool network with large numbers of non-aggregated transactions, then i=
n cooperation with a miner confirm a single aggregated transaction with low=
er feerate than what it put in the several non-aggregated transactions.<br>
The attacker ends up paying lower for the single confirmed transaction, eve=
n though it cost the fullnode network a significant amount of CPU to proces=
s and validate all the non-aggregated transactions.<br>
<br>
Once the single aggregate transaction is confirmed, the fullnodes will remo=
ve the non-aggregated transactions from the mempool, clearing out their mem=
pool limit.<br>
Then the attacker can once again flood the fullnode mempool network with mo=
re non-aggregated transactions, and again repeat with an aggregated transac=
tion that pays below the total of the non-aggregated transactions, repeated=
ly increasing the load on the mempool.<br>
<br>
Thus, we should really make transactions that could appear in the mempool n=
on-aggregatable with other transactions in the mempool.<br>
You should arrange for aggregation before the blockchain-level transaction =
hits the mempool.<br>
<br>
One can compare cross-input signature aggregation designs.<br>
Signature aggregation is only allowed within a single blockchain-level tran=
saction, not across transactions, precisely so that a transaction that appe=
ars in the mempool cannot have its signatures aggregated with other transac=
tions, and preventing the above attack.<br>
Anyone trying to take advantage of signature aggregation needs to cooperati=
vely construct the blockchain-level transaction outside of the mempool with=
 other cooperating actors, all of which perform the validation themselves b=
efore anything hits the mempool.<br>
<br>
Similarly I can imagine that cross-input ZKP aggregation would be acceptabl=
e, but not cross-transaction ZKP aggregation.<br>
(And if you want to push for ZKP aggregation, you should probably push for =
cross-input signature aggregation first, as you would probably need to solv=
e similar problems in detail and I imagine signature aggregation is simpler=
 than general ZKP aggregation.)<br>
<br>
Always expect that the blockchain and its supporting network is attackable.=
<br>
Do ***NOT*** focus on blocks --- focus on the load on the mempool (the bloc=
k weight limit is a limit on the mempool load, not a limit on the block CPU=
 load!).<br>
The mempool is a free service, we should take care not to make it abusable.=
<br>
On the other hand, blockspace is a paid service, so load on it is less impo=
rtant; it is already paid for.<br>
I strongly recommend **DISALLOWING** aggregation of ZKPs once a transaction=
 is in a form that could potentially hit the mempool, and to require paid s=
ervices for aggregation, outside of the unpaid, free mempool.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--000000000000ce165d05fafa5885--