diff options
author | Johnson Lau <jl2012@xbt.hk> | 2018-02-16 17:49:17 -0500 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2018-02-16 23:04:40 +0000 |
commit | dc2e389b29292a6ff6b18e34ab9617ae0caf3518 (patch) | |
tree | cfa15e3a59687adfb6f96816f9cf41dc8593478d | |
parent | e9c92e9187f53094c1dd0439a3af6a06df2e0420 (diff) | |
download | pi-bitcoindev-dc2e389b29292a6ff6b18e34ab9617ae0caf3518.tar.gz pi-bitcoindev-dc2e389b29292a6ff6b18e34ab9617ae0caf3518.zip |
[bitcoin-dev] Alternative way to count sigops
-rw-r--r-- | 40/44a0660923f7b3c3340b58f5f4561c8b37ff84 | 244 |
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) >=3D (actual_sigop * 50). This is a per-input = +limit, as script validation is parallel. </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-- + + |