summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJohnson Lau <jl2012@xbt.hk>2018-02-16 17:49:17 -0500
committerbitcoindev <bitcoindev@gnusha.org>2018-02-16 23:04:40 +0000
commitdc2e389b29292a6ff6b18e34ab9617ae0caf3518 (patch)
treecfa15e3a59687adfb6f96816f9cf41dc8593478d
parente9c92e9187f53094c1dd0439a3af6a06df2e0420 (diff)
downloadpi-bitcoindev-dc2e389b29292a6ff6b18e34ab9617ae0caf3518.tar.gz
pi-bitcoindev-dc2e389b29292a6ff6b18e34ab9617ae0caf3518.zip
[bitcoin-dev] Alternative way to count sigops
-rw-r--r--40/44a0660923f7b3c3340b58f5f4561c8b37ff84244
1 files changed, 244 insertions, 0 deletions
diff --git a/40/44a0660923f7b3c3340b58f5f4561c8b37ff84 b/40/44a0660923f7b3c3340b58f5f4561c8b37ff84
new file mode 100644
index 000000000..90f89d86a
--- /dev/null
+++ b/40/44a0660923f7b3c3340b58f5f4561c8b37ff84
@@ -0,0 +1,244 @@
+Return-Path: <jl2012@xbt.hk>
+Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
+ [172.17.192.35])
+ by mail.linuxfoundation.org (Postfix) with ESMTPS id 6FA2011CD
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Fri, 16 Feb 2018 23:04:40 +0000 (UTC)
+X-Greylist: delayed 00:15:03 by SQLgrey-1.7.6
+Received: from sender-of-o51.zoho.com (sender-of-o51.zoho.com [135.84.80.216])
+ by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 84DD6124
+ for <bitcoin-dev@lists.linuxfoundation.org>;
+ Fri, 16 Feb 2018 23:04:39 +0000 (UTC)
+Received: from pn-206-101.itsc.cuhk.edu.hk (pn-206-101.itsc.cuhk.edu.hk
+ [137.189.206.101]) by mx.zohomail.com
+ with SMTPS id 1518821373199540.8463776892784;
+ Fri, 16 Feb 2018 14:49:33 -0800 (PST)
+From: Johnson Lau <jl2012@xbt.hk>
+Content-Type: multipart/signed;
+ boundary="Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541";
+ protocol="application/pgp-signature"; micalg=pgp-sha512
+Mime-Version: 1.0 (Mac OS X Mail 11.2 \(3445.5.20\))
+Message-Id: <0213B102-7595-4177-A76C-FE4E8D7F0EDF@xbt.hk>
+Date: Fri, 16 Feb 2018 17:49:17 -0500
+To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
+X-Mailer: Apple Mail (2.3445.5.20)
+X-Zoho-Virus-Status: 1
+X-ZohoMailClient: External
+X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,HTML_MESSAGE,
+ RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
+X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
+ smtp1.linux-foundation.org
+Subject: [bitcoin-dev] Alternative way to count sigops
+X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
+X-Mailman-Version: 2.1.12
+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, 16 Feb 2018 23:04:40 -0000
+
+
+--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541
+Content-Type: multipart/alternative;
+ boundary="Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15"
+
+
+--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15
+Content-Transfer-Encoding: quoted-printable
+Content-Type: text/plain;
+ charset=utf-8
+
+Short history
+----------------
+
+Satoshi introduced sigops counting as a softfork to limit the number of =
+signature operation in a block. He statically counted all =
+OP_CHECK(MULTI)SIG(VERIFY) in both scriptSig and scriptPubKey, assumed a =
+OP_CHECKMULTISIG is equivalent to 20 OP_CHECKSIG, and enforced a block =
+limit of 20000 sigop. The counting is not contextual, i.e. one doesn=E2=80=
+=99t need the UTXO set to determine the number of sigop. The counting =
+was also static so one doesn=E2=80=99t need to execute a script in order =
+to count sigop. However, this is completely wrong for few reasons: a) =
+opcodes in scriptPubKey are not executed; b) scriptPubKey of spent UTXO, =
+which are actually executed, are not counted at all; c) it greatly =
+overestimate the cost of multi-sig; d) it counts sigop in unexecuted =
+branch.
+
+As P2SH was introduced, sigop counting also covered the sigop =
+redeemScript. This is good because redeemScript is what being executed. =
+It also improved the counting of OP_CHECKMULTISIG. If it is in certain =
+canonical form, it would count the number of public keys instead of =
+assuming it as 20. On the other hand, counting sigop becomes not =
+possible without the UTXO set, since one needs UTXO to identify P2SH =
+inputs. Also, the canonical OP_CHECKMULTISIG counting is not quite =
+elegant and created more special cases in the code.
+
+Segwit (BIP141) scaled the legacy sigop limit by 4x. So every legacy =
+sigop becomes 4 new sigop, with a block limit of 80000 new sigop. P2WPKH =
+is counted as 1 new sigop, and P2WSH is counted in the same way as P2SH.
+
+
+
+Problem
+------------
+
+We now have multiple 2nd generation script proposals, such as BIP114, =
+BIP117, taproot, etc. BIP114 and taproot allows static sigop counting, =
+but not BIP117 as it requires execution to determine what would be run =
+as script (like OP_EVAL). As we want to allow more complicated script =
+functions, static sigop counting might not be easy. However, we still =
+want to have a limit to avoid unexpected DoS attack.
+
+
+
+
+Proposal
+------------
+
+Since we have a block weight limit of 4,000,000 and sigop limit of =
+80,000, each sigop could not use more than 50 weight unit on average. =
+For new script proposals we could count the actual number of sigop at =
+execution (i.e. skip unexecuted sigop, skip 0-size signature, count the =
+actual checksig operations in multi-sig), and make sure the number of =
+executed sigop * 50 is not greater than the size of the input.
+
+The minimal size of each input is 32 (prevout.hash) + 4 (prevout.n) + 4 =
+(nSequence) + 1 (empty scriptSig) =3D 41 bytes or 164 weight unit. So =
+the new rule would require that (164 + input witness size) >=3D =
+(actual_sigop * 50). This is a per-input limit, as script validation is =
+parallel.
+
+Since a compressed key is 33 bytes and a normal compact signature is 64 =
+bytes, the 1:50 ratio should be more than enough to allow any normal use =
+of CHECKSIG, unless people are doing weird things like 2DUP 2DUP =
+2DUP=E2=80=A6=E2=80=A6..CHECKSIG CHECKSIG CHECKSIG CHECKSIG , which =
+would have many sigop with a relatively small witness. Interactive =
+per-tx signature aggregation allows 64bytes/tx signature, and per-block =
+non-interatcitve signature aggregation allows 32bytes/signature =
+(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.h=
+tml =
+<https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/014272.h=
+tml>). In such cases, the 1:50 ratio might not be enough if many =
+signatures are aggregated. Depends on the number of sigop we could =
+tolerate, the 1:50 ratio might be reduced to 1:32 or lower to make sure =
+legitimate use would never hit the limit. I think 32 is reasonable as it =
+is about the size of a public key, which would guarantee each pubkey =
+must get a sigop slot.
+
+So a relay node could be certain that a tx won=E2=80=99t spend excessive =
+CPU power by just looking at its size. If it spends too much, it is =
+invalid and script execution could be terminated early.
+
+--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15
+Content-Transfer-Encoding: quoted-printable
+Content-Type: text/html;
+ charset=utf-8
+
+<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
+charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
+-webkit-nbsp-mode: space; line-break: after-white-space;" class=3D"">Short=
+ history<div class=3D"">----------------</div><div class=3D""><br =
+class=3D""></div><div class=3D"">Satoshi introduced sigops counting as a =
+softfork to limit the number of signature operation in a block. He =
+statically counted all OP_CHECK(MULTI)SIG(VERIFY) in both scriptSig and =
+scriptPubKey, assumed a OP_CHECKMULTISIG is equivalent to 20 =
+OP_CHECKSIG, and enforced a block limit of 20000 sigop. The counting is =
+not contextual, i.e. one doesn=E2=80=99t need the UTXO set to determine =
+the number of sigop. The counting was also static so one doesn=E2=80=99t =
+need to execute a script in order to count sigop. However, this is =
+completely wrong for few reasons: a) opcodes in scriptPubKey are not =
+executed; b) scriptPubKey of spent UTXO, which are actually executed, =
+are not counted at all; c) it greatly overestimate the cost of =
+multi-sig; d) it counts sigop in unexecuted branch.<div class=3D""><br =
+class=3D""></div><div class=3D"">As P2SH was introduced, sigop counting =
+also covered the sigop redeemScript. This is good because redeemScript =
+is what being executed. It also improved the counting of =
+OP_CHECKMULTISIG. If it is in certain canonical form, it would count the =
+number of public keys instead of assuming it as 20. On the other hand, =
+counting sigop becomes not possible without the UTXO set, since one =
+needs UTXO to identify P2SH inputs. Also, the canonical OP_CHECKMULTISIG =
+counting is not quite elegant and created more special cases in the =
+code.</div><div class=3D""><br class=3D""></div><div class=3D"">Segwit =
+(BIP141) scaled the legacy sigop limit by 4x. So every legacy sigop =
+becomes 4 new sigop, with a block limit of 80000 new sigop. P2WPKH is =
+counted as 1 new sigop, and P2WSH is counted in the same way as =
+P2SH.</div><div class=3D""><br class=3D""></div><div class=3D""><br =
+class=3D""></div></div><div class=3D""><br class=3D""></div><div =
+class=3D"">Problem</div><div class=3D"">------------</div><div =
+class=3D""><br class=3D""></div><div class=3D"">We now have multiple 2nd =
+generation script proposals, such as BIP114, BIP117, taproot, etc. =
+BIP114 and taproot allows static sigop counting, but not BIP117 as it =
+requires execution to determine what would be run as script (like =
+OP_EVAL). As we want to allow more complicated script functions, static =
+sigop counting might not be easy. However, we still want to have a limit =
+to avoid unexpected DoS attack.</div><div class=3D""><br =
+class=3D""></div><div class=3D""><br class=3D""></div><div class=3D""><br =
+class=3D""></div><div class=3D""><br class=3D""></div><div =
+class=3D"">Proposal</div><div class=3D"">------------</div><div =
+class=3D""><br class=3D""></div><div class=3D"">Since we have a block =
+weight limit of 4,000,000 and sigop limit of 80,000, each sigop could =
+not use more than 50 weight unit on average. For new script proposals we =
+could count the actual number of sigop at execution (i.e. skip =
+unexecuted sigop, skip 0-size signature, count the actual checksig =
+operations in multi-sig), and make sure the number of executed sigop * =
+50 is not greater than the size of the input.</div><div class=3D""><br =
+class=3D""></div><div class=3D"">The minimal size of each input is 32 =
+(prevout.hash) + 4 (prevout.n) + 4 (nSequence) + 1 (empty scriptSig) =3D =
+41 bytes or 164 weight unit. So the new rule would require that (164 + =
+input witness size) &gt;=3D (actual_sigop * 50). This is a per-input =
+limit, as script validation is parallel.&nbsp;</div><div class=3D""><br =
+class=3D""></div><div class=3D"">Since a compressed key is 33 bytes and =
+a normal compact signature is 64 bytes, the 1:50 ratio should be more =
+than enough to allow any normal use of CHECKSIG, unless people are doing =
+weird things like 2DUP 2DUP 2DUP=E2=80=A6=E2=80=A6..CHECKSIG CHECKSIG =
+CHECKSIG CHECKSIG , which would have many sigop with a relatively small =
+witness. Interactive per-tx signature aggregation allows 64bytes/tx =
+signature, and per-block non-interatcitve signature aggregation allows =
+32bytes/signature (<a =
+href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-May/0=
+14272.html" =
+class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-Ma=
+y/014272.html</a>). In such cases, the 1:50 ratio might not be enough if =
+many signatures are aggregated. Depends on the number of sigop we could =
+tolerate, the 1:50 ratio might be reduced to 1:32 or lower to make sure =
+legitimate use would never hit the limit. I think 32 is reasonable as it =
+is about the size of a public key, which would guarantee each pubkey =
+must get a sigop slot.</div><div class=3D""><br class=3D""></div><div =
+class=3D"">So a relay node could be certain that a tx won=E2=80=99t =
+spend excessive CPU power by just looking at its size. If it spends too =
+much, it is invalid and script execution could be terminated =
+early.</div></body></html>=
+
+--Apple-Mail=_DF2AB362-599C-4E50-BFC2-15CF49534B15--
+
+--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541
+Content-Transfer-Encoding: 7bit
+Content-Disposition: attachment;
+ filename=signature.asc
+Content-Type: application/pgp-signature;
+ name=signature.asc
+Content-Description: Message signed with OpenPGP
+
+-----BEGIN PGP SIGNATURE-----
+
+iQGzBAEBCgAdFiEEKLhz7vf0beYGEpDt7p5VIDS+JNIFAlqHX+0ACgkQ7p5VIDS+
+JNKc5wv/WfkEhNUxPAM9XmYGZeoBeF+SQM/tXl7PM7wkYRZ3WAyjS3rMg6HXryPc
+SiRd80a/GDRnRHAOQY/9+xS+ITVgsmybFwWchxj+zJnzK7UI0knqjIYP6E1ATNOX
+IhM2bJvzCWBp97CB/wBtbUYhUhlW/EhQkOCtiVqdVj49u97Up2QSWnQ07dGpajua
+cVVnvYVG86bWTzWQc6gZuDEfvCatyIMnbmvToyc2cjGGBRvXdQKKI14PX0fC91Ln
+yEVLI1STkABWu6BzeFZQhvMbBIv2EsZX7YlNffwb4Cq0/t9zSnoPH86knlsvGga7
+2D8FI87jMPvtL4K61q8PB2lDgV0EdBLnY1emCxai/zzjlxk2VhPs+tRReYFiGEK2
+i/sj6HT1b0ctj2VsEz8umVJPijYb9w4UjeQnSPD6LWdlUWU61Z+dv/3i68tTEtA7
+lkbexBXzz6MK2U7mhsssKhega0P7JBZLAUBwgep58jwV++AlyreVa3bTTNoegUBE
+MM53vvup
+=5OT2
+-----END PGP SIGNATURE-----
+
+--Apple-Mail=_706C79CD-9C79-4844-A116-6E31D4402541--
+
+