0347 - Draft - Standards - Dec. 11, 2023 (2 years, 7 months ago)
11
2023
BIP: 347
Layer: Consensus (soft fork)
Title: OP_CAT in Tapscript
Author: Ethan Heilman <[email protected]>
Armin Sabouri <[email protected]>
Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP 347
Status: Draft
Type: Standards Track
Created: 2023-12-11
License: BSD-3-Clause
Post-History: 2023-10-21: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-October/022049.html [bitcoin-dev] Proposed BIP for OP_CATThis BIP introduces OP_CAT as a tapscript opcode which allows the concatenation of two values on the stack. OP_CAT would be activated via a soft fork by redefining the opcode OP_SUCCESS126 (126 in decimal and 0x7e in hexadecimal). This is the same opcode value used by the original OP_CAT.
This document is licensed under the 3-clause BSD license.
When evaluated, the OP_CAT instruction:
Given the stack [x1, x2] , where x2 is at the top of the stack, OP_CAT will push x1 || x2 onto the stack. By || we denote concatenation. OP_CAT fails if there are fewer than two values on the stack or if a concatenated value would have a combined size greater than the maximum script element size of 520 bytes.
This opcode would be activated via a soft fork by redefining the tapscript opcode OP_SUCCESS126 (126 in decimal and 0x7e in hexadecimal) to OP_CAT.
Bitcoin Tapscript lacks a general purpose way of combining objects on the stack, restricting the expressiveness and power of Tapscript. This prevents, among many other things, the ability to construct and evaluate merkle trees and other hashed data structures in Tapscript. OP_CAT, by adding a general purpose way to concatenate stack values, would overcome this limitation and greatly increase the functionality of Tapscript.
OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular, and useful opcode in the spirit of Unix 1 . To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
OP_CAT was available in early versions of Bitcoin. In 2010, a single commit disabled OP_CAT, along with another 15 opcodes. Folklore states that OP_CAT was removed in this commit because it enabled the construction of a script whose evaluation could have memory usage exponential in the size of the script. For example, a script that pushed a 1-byte value on the stack and then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack element whose size was greater than 1 terabyte assuming no maximum stack element size. As Bitcoin at that time had a maximum stack element size of 5000 bytes, the effect of this expansion was limited to 5000 bytes. This is no longer an issue because tapscript enforces a maximum stack element size of 520 bytes.
Our decision to reenable OP_CAT by redefining a tapscript OP_SUCCESSx opcode to OP_CAT was motivated to leverage the tapscript softfork opcode upgrade path introduced in BIP 342 .
We specifically choose to use OP_SUCCESS126 rather than another OP_SUCCESSx as OP_SUCCESS126 uses the same opcode value (126 in decimal and 0x7e in hexadecimal) that was used for OP_CAT prior to it being disabled in Bitcoin. This removes a potential source of confusion that would exist if we had a opcode value different from the one used in the original OP_CAT opcode.
While the OP_SUCCESSx opcode upgrade path could enable us to increase the stack element size while reenabling OP_CAT, we wanted to separate the decision to change the stack element size limit from the decision to reenable OP_CAT. This BIP takes no position in favor or against increasing the stack element size limit.
OP_CAT usage in a non-tapscript script will continue to trigger the SCRIPT_ERR_DISABLED_OPCODE. The only change would be to OP_CAT usage in tapscript. This change to tapscript would be activated as a soft fork that redefines an OP_SUCCESSx opcode (OP_SUCCESS126) to OP_CAT.
case OP_CAT:
{
if (stack.size() < 2)
return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
valtype& vch1 = stacktop(-2);
valtype& vch2 = stacktop(-1);
if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
vch1.insert(vch1.end(), vch2.begin(), vch2.end());
stack.pop_back();
}
break;
The value of
MAX_SCRIPT_ELEMENT_SIZE
is 520.
This implementation is inspired by the original implementation of OP_CAT as it existed in the Bitcoin codebase prior to the commit "misc changes" 4bd188c 10 which disabled it:
case OP_CAT:
{
// (x1 x2 -- out)
if (stack.size() < 2)
return false;
valtype& vch1 = stacktop(-2);
valtype& vch2 = stacktop(-1);
vch1.insert(vch1.end(), vch2.begin(), vch2.end());
stack.pop_back();
if (stacktop(-1).size() > 5000)
return false;
}
break;An alternative implementation of OP_CAT can be found in Elements 11 .
We wish to acknowledge Dan Gould for encouraging and helping review this effort. We also want to thank Madars Virza, Jeremy Rubin, Andrew Poelstra, Bob Summerwill, Tim Ruffing and Johan T. Halseth for their feedback, review and helpful comments.