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"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] proposal: new opcode OP_ZKP to enable ZKP-based
 spending authorization
Precedence: list

--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--