Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 27590C91 for ; Wed, 18 Sep 2019 20:51:02 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ot1-f42.google.com (mail-ot1-f42.google.com [209.85.210.42]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 62EA4711 for ; Wed, 18 Sep 2019 20:51:01 +0000 (UTC) Received: by mail-ot1-f42.google.com with SMTP id f21so1064822otl.13 for ; Wed, 18 Sep 2019 13:51:01 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=NPhl1oUcDc59u+vlWJ0VwiNpeQ5GYlyymtIGIi79qZE=; b=l0pmBfQGMCYd7gZcpaWJhkfbFFlxNHzvHhlsg43aF48DHyHZ7ops2pxAXfSploe+jb 0BWangZ3tpOeP7cVcVSQNELUZm+B1cb/Ce73GQ11y1M/lhe/afUgoh3IW1FAzL/Veknw PyOgIkRbSZsSZ+BnSdCtXAzbDbhgFJ+5Ttn2KzZzUiadQM/Npii+tVGtg7zJnREik1wQ 4OnhlcbE4cthHekX70Clg2TC3+7MtUCYyBhKAbICFxhfBBoUTQNDt1k8T+hq1siEtzkV RebLXc/LtP5Cm/7ArCPDUOLQCDZGcZs3l/qqx0e4lYk10X1E2nZiefWK8xQWhRRO2mL2 ELSg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=NPhl1oUcDc59u+vlWJ0VwiNpeQ5GYlyymtIGIi79qZE=; b=czFr45RmCP2hkeJmzNr8ZrvwLFLXRnjuTVkMyF14KWT1xns3eHRp0kkX5QKQ8YE+TU wdEKO0JIlqEfHzItnxug1JcDPUjtFqHnBXSlRpSpoD+vuW9ih0Y6LR6Ez4z1SPfzO4k/ 0L+Xw4VbMyb+SmuniYWbsJXCxUxVbanIIHySCzwAp5DCkHSJHGRDYkQK+hcNByfj0oPT MRrGesRJ7bNOdiH2LDkjbFXFZKlNPgwVBtLVseRSBrVqxwPgShPGZneUne52ugeRhgaC T7DCArr+ITFBjqKurVpyiVjk4x2ieNjdqg+1aykEJT42arTaX8RGJWHgxdIlFCQ1FP53 F2CA== X-Gm-Message-State: APjAAAVZT+Zl+1Lhj5LOFWvQXrCcdfzffxfKrgs6YeAfZ2Lj1/Vuyv/d h1nCLa1rjAOaPOjMIwQwByEWCwTQCZ4xeMnULSDKFLp+ X-Google-Smtp-Source: APXvYqze+DRQX+avLp25PEQljGvxtprh+E+cDJGKXuhOLNiPc8O2zrFYv2J6k7P6VITOWfhV2YGUSRZWbRshZEvdJNQ= X-Received: by 2002:a05:6830:1405:: with SMTP id v5mr4005694otp.99.1568839860272; Wed, 18 Sep 2019 13:51:00 -0700 (PDT) MIME-Version: 1.0 From: Pieter Wuille Date: Wed, 18 Sep 2019 13:50:48 -0700 Message-ID: To: Bitcoin Dev Content-Type: text/plain; charset="UTF-8" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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] bip-tapscript resource limits 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: Wed, 18 Sep 2019 20:51:02 -0000 Hi all, In the draft for bip-tapscript (see [1], current version [2]), we propose removing the per-block sigops limit for tapscript scripts, and replacing it with a "every script gets a budget of sigops based on its witness size (one per 50 WU)". Since signatures (plus pubkeys) take more WU than that, this is not a restriction for anything but pathologically constructed scripts. Simultaneously, it removes the multi-dimensional optimization problem that theoretically needs to be solved to maximize revenue in block template construction. With our recent work on Miniscript (see [3]), we discovered that the variety of other script resource limits also introduce (weaker) complex optimization requirements, but for script constructors instead of miners. An overview: 1) Scripts are limited to 10000 bytes (and 3600 by standardness currently) 2) The total number of non-push opcodes in a script + the number of keys participating in executed OP_CHECKMULTISIG(VERIFY) opcodes must not exceed 201. 3) The size of the stack + altstack combined cannot exceed 1000 elements during execution (and the initial stack is limited to 100 elements by standardness currently) 4) The maximum size of elements on the stack is 520 bytes (and 80 bytes in the initial stack by standardness) In a discussion about this with Andrew Poelstra we wondered whether all these limits are still necessary in bip-tapscript. I believe the only relevant ones are those that reduce total memory usage, or verification CPU usage per witness byte. Total script verification CPU usage isn't relevant I believe, because the same effect can be accomplished by having a transaction (or block) with multiple inputs. So let's go over the above resource limits, and see how they help with limiting memory usage or CPu usage per byte. # Script size limit Memory usage for validation can grow with larger scripts, but only indirectly by constructing extra stack data. Since those are independently limited by (3), we don't need to consider those here. There used to be a way through which larger scripts would cause larger per byte verification cost, but it no longer applies, I believe. Due to the scriptCode being replaced with a pre-hashed tapleaf hash, the per-sigop hashing cost is now easily made independent of the size of the script in implementations. My suggestion is to drop the script size limit in tapscript, and instead have it only be implicitly limited by transaction size limits. # The 201 non-push opcodes limit Ignoring how more opcodes can grow the stack and altstack (which are already restricted by 3), I believe there is only one way that additional (executed) opcodes can increase per-opcode execution time in the current Bitcoin Core implementation [4], namely the "vfExec" stack that keeps track of what sides of IF/NOTIF/ELSE/ENDIF execution is currently passing through. As pointed out by Sergio Demian Lerner [5], an O(1) algorithm can do this just as well (a variant of which is implemented in PR 16902 [6]). Taking such a patch into account, I don't think there are any problems with removing the 201 ops limit for bip-tapscript scripts. Especially given its strange semantics around OP_CHECKMULTISIG(VERIFY) (the keys participating in those are each counted as 1 towards the 201 limit, but only when executed, while all non-push opcodes are counted as 1 even when not executed), I think this is a nice simplification. # The 1000 element limit for stack + altstack A limit for the number of elements on the stack/altstack directly affects memory usage. In a naive implementation without deduplication as is used in Bitcoin Core now, every OP_3DUP can add 120 bytes of memory usage plus the size of the data in the created elements themselves (which can be a multiple of that number), leading to several GB of memory usage for executing a maximal 4 MB script (multiplied by the number of parallel executions). Even when using reference-counting techniques to reduce duplication, 100 MB memory usage is not unreasonable. I don't think those are acceptable numbers. The stack size can also directly affect per-opcode execution time for OP_ROLL, again shown by [5]. A block full of the most tightly packed OP_ROLLS (which I believe is a repetition of OP_3DUP OP_ROLL OP_ROLL OP_ROLL) operating on a stack of 1000 elements for me takes around 4.3 s of CPU time to verify. That's significant, but it's surprisingly close to what a block packed with OP_CHECKSIGs (taking the 1 sigop / 50 WU limit into account) takes to verify on the same machine (3.8 s). Even more remarkably, that time is also very close to how long a block full of most tightly packed OP_HASH256s on 520 byte inputs take to verify when disabling SHA256 hardware acceleration (3.6 s). I believe we should keep this 1000 element stack limit for these reasons. The 100 limit on input stacks can be increased to 1000 for uniformity with the during-execution limit. # The 520 byte stack element size limit Given that there are no known use cases for stack elements larger than 65 bytes (and no opcodes apart from hashes that can even operate on them), plus their impact on memory usage the execution time of pathologically constructed scripts full of hashes (see above), I think we should keep this limit. Note that this limit can be changed using the OP_SUCCESSx mechanism, if need be. # Summary I propose the following changes to resource limits in bip-tapscript (compared to segwit v0 scripts): * Replace the separate sigops counter with a "executed sigops must not exceed (witness size / 50 WU) + 1" rule (already in the BIP). * Drop the 10000 byte limit for script size (and 3600 byte standardness limit) * Drop the 201 non-push ops limit per script. * Drop the 100 input stack elements standardness limit, and replace with a (consensus) 1000 limit. The rules limiting the stack + altstack number of elements during execution to 1000 remains, as well as the 520 byte limit for elements on the stack. # References [1] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-May/016914.html [2] https://github.com/sipa/bips/blob/bip-schnorr/bip-tapscript.mediawiki [3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2019-August/017270.html [4] https://github.com/bitcoin/bitcoin/blob/v0.18.1/src/script/interpreter.cpp#L281L1084 [5] https://bitslog.com/2017/04/17/new-quadratic-delays-in-bitcoin-scripts/ [6] https://github.com/bitcoin/bitcoin/pull/16902 Cheers, -- Pieter