Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6FA2011CD for ; 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 ; 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 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 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 = ). 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 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-Ma= y/014272.html). 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-- --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--