diff options
| author | Weiji Guo <weiji.g@gmail.com> | 2023-05-06 07:06:51 +0800 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2023-05-05 23:07:04 +0000 |
| commit | a9a1fcd3ffd5c6dcdbb66da018edf3f58b62eff0 (patch) | |
| tree | 39400f8f2a457e6f9979a50f603fa9cc285b4759 | |
| parent | ef2f609308d26e2213db3cb962b0d06e4b5b9214 (diff) | |
| download | pi-bitcoindev-a9a1fcd3ffd5c6dcdbb66da018edf3f58b62eff0.tar.gz pi-bitcoindev-a9a1fcd3ffd5c6dcdbb66da018edf3f58b62eff0.zip | |
Re: [bitcoin-dev] proposal: new opcode OP_ZKP to enable ZKP-based spending authorization
| -rw-r--r-- | 0f/655b0552d627372d75a0921fbaa8ccfa4f240a | 311 |
1 files changed, 311 insertions, 0 deletions
diff --git a/0f/655b0552d627372d75a0921fbaa8ccfa4f240a b/0f/655b0552d627372d75a0921fbaa8ccfa4f240a new file mode 100644 index 000000000..6482c6a87 --- /dev/null +++ b/0f/655b0552d627372d75a0921fbaa8ccfa4f240a @@ -0,0 +1,311 @@ +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>> 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'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'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'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 <= +;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a>>= + 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-- + |