path: root/94/ca41bcf6ebc63f28b787c9af97110cc87c4b66

Delivery-date: Sat, 27 Sep 2025 06:22:59 -0700
Received: from mail-ot1-f59.google.com ([209.85.210.59])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBAABBKGK37DAMGQENPWAZTA@googlegroups.com>)
	id 1v2Ut8-0007ES-6V
	for bitcoindev@gnusha.org; Sat, 27 Sep 2025 06:22:59 -0700
Received: by mail-ot1-f59.google.com with SMTP id 46e09a7af769-79f473fe211sf1285592a34.1
        for <bitcoindev@gnusha.org>; Sat, 27 Sep 2025 06:22:58 -0700 (PDT)
ARC-Seal: i=2; a=rsa-sha256; t=1758979372; cv=pass;
        d=google.com; s=arc-20240605;
        b=MaCYTlytxd9VRekiuB4+RskHzxwmkitx+XWxmjZzAubxY4Gy6AByJQ2GdfhBqrAFK4
         DpVsKxgTp+fewzV0nD8LMLZnHIVMvk7ygZivLN3Z5COJ9XwXPJ+IINrs2ApgM4EoXmER
         fheIjPMhUrRl6+wN7yBFLfhxjo7Kt7mx2zXFpecRoguy/rr3bFy6udvrqVTensOzalwo
         FgVZ8RyE5nKSnbq6V2LDCAu66a6RGeK5Y7jcQhYBXpFGD16bD1OFQqFHbaOctL3SnI8h
         KeogbqMHMyZb5Th/lKCtJ1j8NraWTL88kPhOhTyXv36+DQbxOh89Vw4HTkysye/A3xDm
         VhVQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:content-transfer-encoding
         :mime-version:message-id:date:in-reply-to:subject:cc:to:from:sender
         :dkim-signature;
        bh=BiKPj5AlUDQ3XHLhOfHwTaORDx0of8yax3TspgcDHXA=;
        fh=UxtxK8tXCcQayWmEk+ZOdBDZtGWEJojut3QZQ1yWboY=;
        b=fyjmRmiUnAyMjnKdW6lbrrtitS/pDV4f/OJ/DUDkyksb3ENUh5Yuucj8BiX9iwDNy9
         IxCgE+fGax6Ejw58wIK+gdX0u3HhBODQeE0zUMZeROQj0ImPY/aQ4TDrW2Z7nmBVk5K1
         SNMImaWZVu0APfit9AJZJ4QtBNeY1ybkITwA+Nlv3i63QAKjSXsxBjVmRjThTUhhiv6W
         jrMvQhDJz0RCEWhjz7Fqo0oETqvdqLjxcmcUEmsfof2GJZyZ54G5m1d4+vpTRkFuX6Jb
         7/FKfd5nY13du732mBT8aM9xN7H03jXwzLXA1zgo0RY1k2wkiiepk20Sp9LdJbOY5O7V
         o9zw==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@rustcorp.com.au header.s=202305 header.b=A1WfqMAi;
       spf=pass (google.com: domain of rusty@gandalf.ozlabs.org designates 2404:9400:2221:ea00::3 as permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1758979372; x=1759584172; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:content-transfer-encoding
         :x-original-authentication-results:x-original-sender:mime-version
         :message-id:date:in-reply-to:subject:cc:to:from:sender:from:to:cc
         :subject:date:message-id:reply-to;
        bh=BiKPj5AlUDQ3XHLhOfHwTaORDx0of8yax3TspgcDHXA=;
        b=FuVQnzk0H18EfRaZUZOPFBki3Lvb8k4H4N7sRxngWLD0I/oI4MW7bYwck/swx/qxJS
         7tRnYqZaQuMoT2twXOooRStuUGibc1jTDlZLROcVnZaPToxDTNFrxmc1PPMS3zqix8eg
         PGmYS3gNsKg3bLURLYg9lbBddxmgwhIJEVTgLSlQzTTdP0RkQye0zRNNjx2UlIA5+MQV
         ZoAidKX/gvuxOHoT3RRKEEyEDpAT2X/MVLjoHrN8qLPyxSQAiyiIE20d4MDlUkeiKu71
         J5pfUd/FplmT1UAMeto+eEz/tlp36y3IOanAxhGumLjHYkq3E0qrKNxkMqT+v/sT4H49
         Y8Pg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1758979372; x=1759584172;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:content-transfer-encoding
         :x-original-authentication-results:x-original-sender:mime-version
         :message-id:date:in-reply-to:subject:cc:to:from:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=BiKPj5AlUDQ3XHLhOfHwTaORDx0of8yax3TspgcDHXA=;
        b=F/W5Y245nZpAP5exWY1xfqGc3R8mlJjEBd++nkGx8eDnokPFA4bQEZfhZy7dwPvIE2
         GtVYA3MSsTEXPqBtUH1IX7+TjtBwUIbn/VGgCPT3FlghAHZXXeVx18OgacSBJFq2qiPL
         EwKVhgfE7xWZJM+C8i/s964N8fpSNPewy7V94fpywY05CZSjfXMK7mMSlcpHlC2pXz5+
         3WiyC5Jwh/FqAFOf05XmX+C7Lyn0wfVBTT5quQSHzjcbCsDnP5Obj33al3A2JJTcl/sU
         bKc+LGfrTcdvv2jAwh3s5a/+Ia60N8BdQ1M8D91amZ4Y/w9M2eGZzr+bJ1XcK4flNu6E
         Nwjw==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCVGsgiIOPl+MplhRzvGna1Gy42krLekpp7xnjVZ0DR/MGobGU0YSut8rphx3ql2G0aI9izJi6s/DSEV@gnusha.org
X-Gm-Message-State: AOJu0YzwodSrbGs8n+UejSsQn/Y1mLc1z9h79JfWc9z/lI1K3If8eiK6
	Y8/xWNzpeWaIHIWZaP1vv90xPfPDBUVN9r2FKgKR35Ky1RThArIe2qyI
X-Google-Smtp-Source: AGHT+IExTE5zD7nVRPXYtFUq8rK8ZTvtSA1WX6BW0P9wIkCk842XOwC70lj/qeR2xy8+SCulnXmFMg==
X-Received: by 2002:a05:6870:e18d:b0:345:d297:f4ff with SMTP id 586e51a60fabf-35ebdfa1e17mr5979389fac.10.1758979371583;
        Sat, 27 Sep 2025 06:22:51 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h="ARHlJd5MKcs8YIx7X1VK2SsFFO17hW7eBujHN/LAH/dg912Lng=="
Received: by 2002:a05:6871:6c09:b0:30b:7ec0:8afb with SMTP id
 586e51a60fabf-35eef8cf667ls1195670fac.2.-pod-prod-04-us; Sat, 27 Sep 2025
 06:22:48 -0700 (PDT)
X-Received: by 2002:a05:6808:21a8:b0:43f:7287:a5b1 with SMTP id 5614622812f47-43f7287acf8mr593964b6e.39.1758979368150;
        Sat, 27 Sep 2025 06:22:48 -0700 (PDT)
Received: by 2002:a05:6808:1a15:b0:43f:5b9f:a4a0 with SMTP id 5614622812f47-43f5e0fa8c5msb6e;
        Sat, 27 Sep 2025 04:29:54 -0700 (PDT)
X-Received: by 2002:a17:902:c945:b0:269:8072:5bda with SMTP id d9443c01a7336-27ed4ec4369mr130884655ad.54.1758972593311;
        Sat, 27 Sep 2025 04:29:53 -0700 (PDT)
ARC-Seal: i=1; a=rsa-sha256; t=1758972593; cv=none;
        d=google.com; s=arc-20240605;
        b=jtxd9apvdRZwaM0W62TyA4vodgsJDA9MxDqyUTTbOC1MFQsSNS1TI7AApa4S5ntSpx
         VqY3E0m4t/WlQaANNEYlDG5WEBSg7pHMiBa05u/hL/u5sPAVmjpOl9sBNBdtwgtEI+75
         fp/8AUdfaCLlP6H5Rfr8FeUR1G3XlImmkoo5A1IlEE44l6FSKaf41Vao7lk50B3WjpMm
         y28CCfqlX064C/UmexYfNDLGYnl/k7i/6nkYKEmYC33+VpIFUqTAcpqZso18naLk42sN
         K6uLovxUNOV3lTXnyuSiGwFGCqDKH8eh2MfvZqzjVMbyYhy3AYCcn8tXVCcy3zVb1GPi
         tTYA==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=mime-version:message-id:date:in-reply-to:subject:cc:to:from
         :dkim-signature;
        bh=dLRX9ukf+rlAKfrPfhuVWzG2mUK8FDoyB+vSulAR5s4=;
        fh=VKRDeyaA3Okg5Ur9YeEuvs3adnjn1Zay82pjgmdy54E=;
        b=E8vSQjsiHRz4az11xISOCimhuCoV57r4eijndr1nQFzp9eyVJ9Q/ocvl82m/2PtRK0
         /jJJFV2Q90mvuoWb6owfTppXXaJ3ykimst6fZ+AR5XoKnbxkLYTk4BwH1OOiGFwWF2f1
         2j4hrxZWhYPAl9wpzDCH+tWXuJ1eK+bE83fOPSB9tlwohwtEuVEv3Nlj8+F7r3EI2kyJ
         +c0iledaR6Ce3lkUTnHN75HDKSD4D2preCc0Fn9O4HbUSzAnKFgUC9TCecf+aHvFzSzw
         720bY5cEp+JqIhyasBigp801+qGJOO+IH22GF0B7SMIgwv/ece/uYVIheIZl/0NG3z6E
         aytQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@rustcorp.com.au header.s=202305 header.b=A1WfqMAi;
       spf=pass (google.com: domain of rusty@gandalf.ozlabs.org designates 2404:9400:2221:ea00::3 as permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
Received: from mail.ozlabs.org (mail.ozlabs.org. [2404:9400:2221:ea00::3])
        by gmr-mx.google.com with ESMTPS id d9443c01a7336-27ed67c7b12si2651595ad.5.2025.09.27.04.29.52
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
        Sat, 27 Sep 2025 04:29:53 -0700 (PDT)
Received-SPF: pass (google.com: domain of rusty@gandalf.ozlabs.org designates 2404:9400:2221:ea00::3 as permitted sender) client-ip=2404:9400:2221:ea00::3;
Received: by gandalf.ozlabs.org (Postfix, from userid 1011)
	id 4cYlby5JjPz4wCT; Sat, 27 Sep 2025 21:29:50 +1000 (AEST)
From: Rusty Russell <bitcoin-dev@rustcorp.com.au>
To: bitcoindev@googlegroups.com
Cc: Julian Moik <julianmoik@gmail.com>
Subject: [bitcoindev] [2/4] Restoration of disabled script functionality
 (Tapscript v2)
In-Reply-To: <874isonniq.fsf@rustcorp.com.au>
Date: Sat, 27 Sep 2025 20:58:26 +0930
Message-ID: <871pnsnnhh.fsf@rustcorp.com.au>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
X-Original-Sender: bitcoin-dev@rustcorp.com.au
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@rustcorp.com.au header.s=202305 header.b=A1WfqMAi;       spf=pass
 (google.com: domain of rusty@gandalf.ozlabs.org designates
 2404:9400:2221:ea00::3 as permitted sender) smtp.mailfrom=rusty@gandalf.ozlabs.org
Content-Transfer-Encoding: quoted-printable
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)

Hi all!

    This BIP is the core restoration.  All the operations come back, and
stack limits are increased (though not infinitely), and integers are not
limited to 31 bits.  The main difference is that all integers are now
unsigned: the combination of variable length and sign bit was a
side-effect of the SSL bignum representation and has proven awkward to
deal with.

    A word on the example implementation which was used to benchmark: it
treats numerical stack objects 64 bits at a time, but does not go so far
as using assembly code.  It also had to implement a proper stack class,
because the time to enforce the new "total stack size limit" naively was
measurable.  I consider it a fair benchmark when considering how a
straightforward implementation would perform.

Thank you for your consideration,
Rusty.

<pre>
  BIP: ?
  Layer: Consensus (soft fork)
  Title: Restoration of disabled script functionality (Tapscript v2)
  Author: Rusty Russell <rusty@rustcorp.com.au>
          Julian Moik <julianmoik@gmail.com>
  Comments-URI: TBA
  Status: Draft
  Type: Standards Track
  Created: 2025-05-16
  License: BSD-3-Clause
</pre>

=3D=3DIntroduction=3D=3D

=3D=3D=3DAbstract=3D=3D=3D

This new BIP introduces a new tapleaf version (0xc2) which restores Bitcoin=
 script to its pre-0.3.1 capability, relying on the Varops Budget in [[bip-=
unknown-varops-budget.mediawiki|BIP-varops]] to prevent the excessive compu=
tational time which caused CVE-2010-5137.

In particular, this BIP:
- Reenables disabled opcodes.
- Increases the maximum stack object size from 520 bytes to 4,000,000 bytes=
.
- Introduces a total stack byte limit of 8,000,000 bytes.
- Increases the maximum total number of stack objects from 1000 to 32768.
- Removes the 32-bit size restriction on numerical values.
- Treats all numerical values as unsigned.

=3D=3D=3DCopyright=3D=3D=3D

This document is licensed under the 3-clause BSD license.

=3D=3D=3DMotivation=3D=3D=3D

Since Bitcoin v0.3.1 (addressing CVE-2010-5137), Bitcoin's scripting capabi=
lities have been significantly restricted to mitigate known vulnerabilities=
 related to excessive computational time and memory usage.  These early saf=
eguards were necessary to prevent denial-of-service attacks and ensure the =
stability and reliability of the Bitcoin network.

Unfortunately, these restrictions removed much of the ability for users to =
control the exact spending conditions of their outputs, which has frustrate=
d the long-held ideal of programmable money without third-party trust.

=3D=3DExecution of Tapscript v2=3D=3D

If a taproot leaf has a version of 0xc2, execution of opcodes is as defined=
 below.  All opcodes not explicitly defined here are treated exactly as def=
ined by [[bip-0342.mediawiki|BIP342]].

Validation of a script fails if:
- It exceeds the remaining varops budget for the transaction.
- Any stack element exceeds 4,000,000 bytes.
- The total size of all stack (and altstack) elements exceeds 8,000,000 byt=
es.
- The number of stack elements (including altstack elements) exceeds 32768.

=3D=3D=3DRationale=3D=3D=3D

There needs to be some limit on memory usage, to avoid a memory-based denia=
l of service.

Putting the entire transaction on the stack is a foreseeable use case, henc=
e using the block size (4MB) as a limit makes sense.  However, allowing 4MB=
 stack elements is a significant increase in memory requirements, so a tota=
l limit of twice that many bytes (8MB) is introduced.  Many stack operation=
s require making at least one copy, so this allows such use.

Putting all outputs or inputs from the transaction on the stack as separate=
 elements requires as much stack capacity as there are inputs or outputs.  =
The smallest possible input is 34 bytes (allowing almost 26411 inputs), and=
 the smallest possible output is 9 bytes (allowing almost 111111 inputs).  =
However, empty outputs are rare and not economically interesting.  Thus we =
consider smallest non-OP_RETURN standard output script, which is P2WPKH at =
22 bytes, giving a minimum output size of 31 bytes, allowing 32258 outputs =
in a maximally-sized transaction.

This makes 32768 a reasonable upper limit for stack elements.

=3D=3D=3DSUCCESS Opcodes=3D=3D=3D

The following opcodes are renamed OP_SUCCESSx, and cause validation to imme=
diately succeed:

* OP_1NEGATE =3D OP_SUCCESS79
* OP_NEGATE =3D OP_SUCCESS143
* OP_ABS =3D OP_SUCCESS144<ref>Anthony Towns suggested this could become an=
 opcode which normalized the value on the top of the stack by truncating an=
y trailing zeroes.</ref>

=3D=3D=3D=3DRationale=3D=3D=3D=3D

Negative numbers are not natively supported in v2 Tapscript.  Arbitrary pre=
cision makes them difficult to manipulate and negative values are not used =
meaningfully in bitcoin transactions.

=3D=3D=3DNon-Arithmetic Opcodes Dealing With Stack Numbers=3D=3D=3D

The following opcodes are redefined in v2 Tapscript to read numbers from th=
e stack as arbitrary-length little-endian values (instead of CScriptNum):

1. OP_CHECKLOCKTIMEVERIFY
2. OP_CHECKSEQUENCEVERIFY
3. OP_VERIFY
4. OP_PICK
5. OP_ROLL
6. OP_IFDUP
7. OP_CHECKSIGADD

These opcodes are redefined in v2 Tapscript to write numbers to the stack a=
s minimal-length little-endian values (instead of CScriptNum):

1. OP_CHECKSIGADD
2. OP_DEPTH
3. OP_SIZE

In addition, the [[bip-0342.mediawiki#specification|BIP-342 success require=
ment]] is modified to require a non-zero variable-length unsigned integer v=
alue (not <code>CastToBool()</code>):

Previously:

    ## If the execution results in anything but exactly one element on the =
stack which evaluates to true with <code>CastToBool()</code>, fail.

Now:

    ## If the execution results in anything but exactly one element on the =
stack which contains one or more non-zero bytes, fail.

=3D=3D=3DEnabled Opcodes=3D=3D=3D

Fifteen opcodes which were removed in v0.3.1 are re-enabled in v2 Tapscript=
.

If there are less than the required number of stack elements, these opcodes=
 fail validation.  Equivalently, a requirement to pop off the stack which c=
annot be satisfied causes the opcode to fail validation.

See [[bip-unknown-varops-budget.mediawiki|BIP-varops]] for the meaning of t=
he annotations in the varops cost field.

=3D=3D=3D=3DSplice Opcodes=3D=3D=3D=3D

{|
! Opcode
! Value
! Required Stack Elements
! Varops Cost
! Varops Reason
! Definition
|-
|OP_CAT
|126
|2
|length(A) + length(B)
|COPYING
|
# Pop B off the stack.
# Pop A off the stack.
# Append B to A.
# Push A onto the stack.
|-
|OP_SUBSTR
|127
|3
|length(LEN) + length(BEGIN) + MIN(Value of LEN, length(A) - Value of BEGIN=
, 0)
|LENGTHCONV + COPYING
|
# Pop LEN off the stack.
# Pop BEGIN off the stack.
# Pop A off the stack.
# Remove BEGIN bytes from the front of A (all bytes if BEGIN greater than l=
ength of A).
# If length(A) is greater than value(LEN), truncate A to length value(LEN).
# Push A onto the stack.
|-
|OP_LEFT
|128
|2
|length(OFFSET)
|LENGTHCONV
|
# Pop OFFSET off the stack.
# Pop A off the stack.
# If length(A) is greater than value(OFFSET), truncate A to length value(OF=
FSET).
# Push A onto the stack.
|-
|OP_RIGHT
|129
|2
|length(OFFSET) + value of OFFSET
|LENGTHCONV + COPYING
|
# Pop OFFSET off the stack.
# Pop A off the stack.
# Copy value(OFFSET) bytes from offset length(A) - value(OFFSET) to offset =
0, if value(OFFSET) is less than length(A).
# Push A onto the stack.
|}

=3D=3D=3D=3D=3DRationale=3D=3D=3D=3D=3D

OP_CAT may require a reallocation of A (hence, COPYING A) before appending =
B.

OP_SUBSTR may have to copy LEN bytes, but also needs to read its two numeri=
c operands.  LEN is limited to the length of the operand minus BEGIN.

OP_LEFT only needs to read its OFFSET operand (truncation is free), whereas=
 OP_RIGHT must copy the bytes, which depends on the OFFSET value.

=3D=3D=3D=3DBit Operation Opcodes=3D=3D=3D=3D

{|
! Opcode
! Value
! Required Stack Elements
! Varops Cost
! Varops Reason
! Definition
|-
|OP_INVERT
|131
|1
|length(A) * 2
|OTHER
|
# Pop A off the stack.
# For each byte in A, replace it with that byte bitwise XOR 0xFF (i.e. inve=
rt the bits)
# Push A onto the stack.
|-
|OP_AND
|132
|2
|length(A) + length(B)
|OTHER + ZEROING
|
# Pop B off the stack.
# Pop A off the stack.
# If B is longer than A, swap B and A.
# For each byte in A (the longer operand): bitwise AND it with the equivale=
nt byte in B (or 0 if past end of B)
# Push A onto the stack.
|-
|OP_OR
|133
|2
|MIN(length(A), length(B)) * 2
|OTHER
|
# Pop B off the stack.
# Pop A off the stack.
# If B is longer than A, swap B and A.
# For each byte in B (the shorter operand): bitwise OR it with the equivale=
nt byte in A.
# Push A onto the stack.
|-
|OP_XOR
|134
|2
|MIN(length(A), length(B)) * 2
|OTHER
|
# Pop B off the stack.
# Pop A off the stack.
# If B is longer than A, swap B and A.
# For each byte in B (the shorter operand): exclusive OR it with the equiva=
lent byte in A.
# Push A onto the stack.
|}

=3D=3D=3D=3D=3DRationale=3D=3D=3D=3D=3D

OP_AND, OP_OR and OP_XOR are assumed to fold the results into the longer of=
 the two operands.  This is an OTHER operation (i.e. cost is 2 per byte), b=
ut OP_AND needs to do this until one operand is exhausted, and then zero th=
e rest (ZEROING, cost 1 per byte).   OP_OR and OP_XOR can stop as soon as t=
he shorter operand is exhausted.

=3D=3D=3D=3DBitshift Opcodes=3D=3D=3D=3D

Note that these are raw bitshifts, unlike the sign-preserving arithmetic sh=
ifts in Bitcoin v0.3.0, and as such they also do not truncate trailing zero=
es from results: they are renamed OP_UPSHIFT (nee OP_LSHIFT) and OP_DOWNSHI=
FT (nee OP_RSHIFT).

{|
! Opcode
! Value
! Required Stack Elements
! Varops Cost
! Varops Reason
! Definition
|-
|OP_UPSHIFT
|152
|2
|length(BITS) + (Value of BITS) / 8 + length(A).  If BITS % 8 !=3D 0, add l=
ength(A) * 2
|LENGTHCONV + ZEROING + COPYING. If BITS % 8 !=3D 0, + OTHER.
|
# Pop BITS off the stack.
# Pop A off the stack.
# If A shifted by value(BITS) would exceed the individual stack limit, fail=
.
# If value(BITS) % 8 =3D=3D 0: simply prepend value(BITS) / 8 zeroes to A.
# Otherwise: prepend (value(BITS) / 8) + 1 zeroes to A, then shift A *down*=
 (8 - (value(BITS) % 8)) bits.
# Push A onto the stack.
|-
|OP_DOWNSHIFT
|153
|2
|length(BITS) + MAX((length(A) - (Value of BITS) / 8), 0) * 2
|LENGTHCONV + OTHER
|
# Pop BITS off the stack.
# Pop A off the stack.
# For BITOFF from 0 to (length(A)-1) * 8 - value(BITS):
    # Copy each bit in A from BITOFF + value(BITS) to BITOFF.
# Truncate A to remove value(OFF) bytes (or all, if value(OFF) > length(A))=
.
# Push A onto the stack.
|}

=3D=3D=3D=3D=3DRationale=3D=3D=3D=3D=3D

DOWNSHIFT needs to read the value of the second operand BITS.  It then need=
s to move the remainder of A (the part after offset BITS/8 bytes).  In prac=
tice this should be implemented in word-size chunks, not bit-by-bit!

UPSHIFT also needs to read BITS.  In general, it may need to reallocate (co=
pying A and zeroing out remaining words).  If not moving an exact number of=
 bytes (BITS % 8 !=3D 0), another pass is needed to perform the bitshift.

OP_UPSHIFT can produce huge results, and so must be checked for limits prio=
r to evaluation.  It is also carefully defined to avoid reallocating twice =
(reallocating to prepend bytes, then again to append a single byte) which h=
as the practical advantage of being able to share the same downward bitshif=
t routine as OP_DOWNSHIFT.

=3D=3D=3D=3DMultiply and Divide Opcodes=3D=3D=3D

{|
! Opcode
! Value
! Required Stack Elements
! Varops Cost
! Varops Reason
! Definition
|-
|OP_2MUL
|141
|1
|length(A) * 3
|OTHER + COPYING
|
# Pop A off the stack.
# Shift each byte in A 1 bit to the left (increasing values, equivalent to =
C's << operator), tracking the last non-zero value.
# If the final byte overflows, append a single 1 byte.
# Otherwise, truncate A at the last non-zero byte.
# Push A onto the stack.
|-
|OP_2DIV
|142
|1
|length(A) * 2
|OTHER
|
# Pop A off the stack.
# Shift each byte 1 bit to the right (decreasing values, equivalent to C's =
>> operator), tracking the last non-zero value.
# Truncate A at the last non-zero byte.
# Push A onto the stack.
|--
|OP_MUL
|149
|2
|length(A) + length(B) + (length(A) + 7) / 8 * length(B) * 6  (BEWARE OVERF=
LOW)
|See Appendix
|
# Pop B off the stack.
# Pop A off the stack.
# Calculate the varops cost of the operation: if it exceeds the remaining b=
udget, fail.
# Allocate an all-zero vector R of length equal to length(A) + length(B).
# For each word in A, multiply it by B and add it into the vector R, offset=
 by the word offset in A.
# Truncate R at the last non-zero byte.
# Push R onto the stack.
|-
|OP_DIV
|150
|2
|length(A) * 9 + length(B) * 2 + length(A)^2 / 3  (BEWARE OVERFLOW)
|See Appendix
|
# Pop B off the stack.
# Pop A off the stack.
# Calculate the varops cost of the operation: if it exceeds the remaining b=
udget, fail.
# If B is empty or all zeroes, fail.
# Perform division as per Knuth's The Art of Computer Programming v2 page 2=
72, Algorithm D "Division of non-negative integers".
# Trim trailing zeroes off the quotient.
# Push the quotient onto the stack.
|-
|OP_MOD
|151
|2
|length(A) * 9 + length(B) * 2 + length(A)^2 / 3  (BEWARE OVERFLOW)
|See Appendix
|
# Calculate the varops cost of the operation: if it exceeds the remaining b=
udget, fail.
# If B is empty or all zeroes, fail.
# Perform division as per Knuth's The Art of Computer Programming v2 page 2=
72, Algorithm D "Division of non-negative integers".
# Trim trailing zeroes off the remainder.
# Push the remainder onto the stack.
|}

=3D=3D=3D=3D=3DRationale=3D=3D=3D=3D=3D

These opcodes can be computationally intensive, which is why the varops bud=
get must be checked before operations.  OP_2MUL and OP_2DIV are far simpler=
, equivalent to OP_UPSHIFT and OP_DOWNSHIFT by 1 bit, except truncating the=
 most-significant zero bytes.

The detailed rationale for these costs can be found in Appendix A.

=3D=3D=3DLimited Hashing Opcodes=3D=3D=3D

OP_RIPEMD160 and OP_SHA1 are now defined to FAIL validation if their operan=
ds exceed 520 bytes.<ref>There seems little reason to allow large hashing w=
ith SHA1 and RIPEMD, and they are not as optimized as SHA256, so we restric=
t their usage to the older byte limit.</ref>

=3D=3D=3DExtended Opcodes=3D=3D=3D

The opcodes OP_ADD, OP_SUB, OP_1ADD and OP_1SUB are redefined in v2 Tapscri=
pt to operate on variable-length unsigned integers.  These always produce m=
inimal values (no trailing zero bytes).

{|
! Opcode
! Value
! Required Stack Elements
! Varops Cost
! Varops Reason
! Definition
|-
|OP_ADD
|147
|2
|MAX(length(A), length(B)) * 4
|ARITH + COPYING
|
# Pop B off the stack.
# Pop A off the stack.
# Option 1: trim trailing zeroes off A and B.
# If B is longer than A, swap A and B.
# For each byte in B, add it and previous overflow into the equivalent byte=
 in A, remembering next overflow.
# If there was final overflow, append a 1 byte to A.
# Option 2: If there was no final overflow, remember last non-zero byte wri=
tten into A, and truncate A after that point.
# Either Option 1 or Option 2 MUST be implemented.
|-
|OP_1ADD
|139
|1
|MAX(1, length(A)) * 4
|ARITH + COPYING
|
# Pop A off the stack.
# Let B =3D 1, and continue as OP_ADD.
|-
|OP_SUB
|148
|2
|MAX(length(A), length(B)) * 3
|ARITH
|
# Pop B off the stack.
# Pop A off the stack.
# For each byte in B, subtract it and previous underflow from the equivalen=
t byte in A, remembering next underflow.
# If there was final overflow, fail validation.
# Remember last non-zero byte written into A, and truncate A after that poi=
nt.
|-
|OP_1SUB
|140=09
|1
|MAX(1, length(A)) * 3
|ARITH
|
# Pop A off the stack.
# Let B =3D 1, and continue as OP_SUB.
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

Note the basic cost for ADD is three times the maximum operand length, but =
then considers the case where a reallocation and copy needs to occur to app=
end the final carry byte (COPYING, which costs 1 unit per byte).

Subtraction is cheaper because underflow does not occur: that is a validati=
on failure, as mathematicians agree the result would not be natural.

=3D=3D=3DMisc Operators=3D=3D=3D

The following opcodes have costs below:

{|
! Opcode
! Varops Budget Cost
! Varops Reason
|-
| OP_CHECKLOCKTIMEVERIFY
| Length of operand
| LENGTHCONV
|-
| OP_CHECKSEQUENCEVERIFY
| Length of operand
| LENGTHCONV
|-
| OP_CHECKSIGADD
| MAX(1, length(number operand)) * 4 + 26000
| ARITH + COPYING + SIGCHECK
|-
| OP_CHECKSIG
| 26000
| SIGCHECK
|-
| OP_CHECKSIGVERIFY
| 26000
| SIGCHECK
|}

=3D=3D=3D=3DRationale=3D=3D=3D=3D

OP_CHECKSIGADD does an OP_1ADD on success, so we use the same cost as that.=
  For simplicity, this is charged whether the OP_CHECKSIGADD succeeds or no=
t.

=3D=3D=3DOther Operators=3D=3D=3D

The varops costs of the following opcodes are defined in [[bip-unknown-varo=
ps-budget.mediawiki|BIP-varops]]:

* OP_VERIFY
* OP_NOT
* OP_0NOTEQUAL
* OP_EQUAL
* OP_EQUALVERIFY
* OP_2DUP
* OP_3DUP
* OP_2OVER
* OP_IFDUP
* OP_DUP
* OP_OVER
* OP_PICK
* OP_TUCK
* OP_ROLL
* OP_BOOLOR
* OP_NUMEQUAL
* OP_NUMEQUALVERIFY
* OP_NUMNOTEQUAL
* OP_LESSTHAN
* OP_GREATERTHAN
* OP_LESSTHANOREQUAL
* OP_GREATERTHANOREQUAL
* OP_MIN
* OP_MAX
* OP_WITHIN
* OP_SHA256
* OP_HASH160
* OP_HASH256

Those with costs not defined here have a cost of 0 (they do not operate on =
variable-length stack objects).

=3D=3D=3DNormalization of Results=3D=3D=3D

Note that only arithmetic operations (those which treat operands as numbers=
) normalize their results: bit operations do not.  Thus operations such as =
"0 OP_ADD" and "2 OP_MUL" will never result in a top stack entry with a tra=
iling zero byte, but "0 OP_OR" and "1 OP_UPSHIFT" may.

To be clear, the following operations are arithmetic and will normalize the=
ir results:

* OP_1ADD
* OP_1SUB
* OP_2MUL
* OP_2DIV
* OP_ADD
* OP_SUB
* OP_MUL
* OP_DIV
* OP_MOD
* OP_MIN
* OP_MAX

=3D=3DBackwards compatibility=3D=3D

This BIP defines a previous unused (and thus, always-successful) tapscript =
version, for backwards compatibility.

=3D=3DReference Implementation=3D=3D

Work in progress:

	https://github.com/jmoik/bitcoin/tree/gsr

=3D=3DThanks=3D=3D

This BIP would not exist without the thoughtful contributions of coders who=
 considered all the facets carefully and thoroughly, and also my inspiratio=
nal wife Alex and my kids who have been tirelessly supportive of my esoteri=
c-seeming endeavors such as this!

In alphabetical order:
- Anthony Towns
- Brandon Black (aka Reardencode)
- John Light
- Jonas Nick
- Rijndael (aka rot13maxi)
- Steven Roose
- FIXME: your name here!

=3D=3DAppendix A: Cost Model Calculations for Multiply and Divide=3D=3D

Multiplication and division require multiple passes over the operands, mean=
ing a cost proportional to the square of the lengths involved, and the word=
 size used for that iteration makes a difference.  We assume 8 bytes (64 bi=
ts) at a time are evaluated, and the ability to multiply two 64-bit numbers=
 and receive a 128-bit result, and divide a 128-bit number by a 64 bit numb=
er to receive a 128 bit quotient and remainder.  This is true on modern 64-=
bit CPUs (sometimes using multiple instructions).

=3D=3D=3DMultiplication Cost=3D=3D=3D=3D

For multiplication, the steps break down like so:
1. Allocate and zero the result: cost =3D length(A) + length(B) (ZEROING)
2. For each word in A:
  * Multiply by each word in B, into a scratch vector: cost =3D 3 * length(=
B) (ARITH)
  * Sum scratch vector at the word offset into the result: cost =3D 3 * len=
gth(B) (ARITH)

Note: we do not assume Karatsuba, Tom-Cooke or other optimizations.

This results in a cost of: length(A) + length(B) + (length(A) + 7) / 8 * le=
ngth(B) * 6.

This is slightly asymmetric: in practice an implementation usually finds th=
at CPU pipelining means choosing B as the larger operand is optimal.

=3D=3D=3DDivision Cost=3D=3D=3D=3D

For division, the steps break down like so:

1. Bit shift both operands to set top bit of B (OP_UPSHIFT, without overflo=
w for B): cost =3D length(A) * 3 + length(B) * 2

2. Trim trailing bytes.  This costs according to the number of byte removed=
, but since that is subtractive on future costs, we ignore it.

3. If B is longer, the answer is 0 already.  So assume A is longer from now=
 on (or equal length).

4. Compare: cost =3D length(A) (COMPARING)

5. Subtract: cost =3D length(A) * 3 (ARITH)

6. for (length(A) - NormalizedLength(B)) in words:
   1. Multiply word by B -> scratch: cost =3D NormalizedLength(B) * 3 (ARIT=
H)
   2. Subtract scratch from A: cost =3D length(A) * 3 (ARITH)
   3. Add B into A (no overflow): cost =3D length(A) * 3 (ARITH)
   4. Shrink A by 1 word.

7. OP_MOD: shift A down, trim trailing zeros: cost =3D length(A) * 2

8. OP_DIV: trim trailing zeros: cost =3D length(A) * 2

Note that the loop at step 6 shrinks A every time, so the *average* cost of=
 each iteration is (NormalizedLength(B) * 3 + length(A) * 6) / 2.  The cost=
 of step 6 is:

	(length(A) - NormalizedLength(B)) / 8 * (NormalizedLength(B) * 3 + length(=
A) * 6) / 2

The worst case here is when NormalizedLength(B) is 0: length(A) * length(A)=
 / 3.

The cost for all the steps in either case is: length(A) * 9 + length(B) * 2=
 + length(A) * length(A) / 3.


--=20
You received this message because you are subscribed to the Google Groups "=
Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/=
871pnsnnhh.fsf%40rustcorp.com.au.