This BIP defines OP_CAT a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS126.
See our implementation PR in bitcoin-inquisition: https://github.com/bitcoin-inquisition/bitcoin/pull/39
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script.
38+For instance a script which pushed an 1 Byte value on the stack then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes.
39+
40+==Specification==
41+
42+OP_CAT pops two elements of the stack, concatenates them together in stack order and pushes the resultant element onto the stack. 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.
0OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. 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.
44+Implementation
45+<pre>
46+case OP_CAT:
47+{
48+ if (stack.size() < 2)
49+ return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0 if (stack.size() < 2) {
1 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
2 }
48+ if (stack.size() < 2)
49+ return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
50+ valtype& vch1 = stacktop(-2);
51+ valtype& vch2 = stacktop(-1);
52+ if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
53+ return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
0 if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE) {
1 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
2 }
54+ vch1.insert(vch1.end(), vch2.begin(), vch2.end());
55+ stack.pop_back();
56+}
57+break;
58+</pre>
59+This implementation is inspired by the original implementation of OP_CAT as shown below. Alternative implementation of OP_CAT can be found in Elements <ref>Roose S., Elements Project, "Re-enable several disabled opcodes", 2019, https://github.com/ElementsProject/elements/commit/13e1103abe3e328c5a4e2039b51a546f8be6c60a#diff-a0337ffd7259e8c7c9a7786d6dbd420c80abfa1afdb34ebae3261109d9ae3c19R740-R759</ref>.
0This implementation is inspired by the original implementation of OP_CAT as shown below. An alternative implementation of OP_CAT can be found in Elements <ref>Roose S., Elements Project, "Re-enable several disabled opcodes", 2019, https://github.com/ElementsProject/elements/commit/13e1103abe3e328c5a4e2039b51a546f8be6c60a#diff-a0337ffd7259e8c7c9a7786d6dbd420c80abfa1afdb34ebae3261109d9ae3c19R740-R759</ref>.
Co-authored-by: kallewoof <kalle.alm@gmail.com>
"If an if only has a single-statement then-clause, it can appear on the same line as the if, without braces. In every other case, braces are required, and the then and else clauses must appear correctly indented on a new line."
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
11+ License: BSD-3-Clause
12+</pre>
13+
14+==Abstract==
15+
16+This BIP defines OP_CAT a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS126.
0This BIP reintroduces OP_CAT in the form of a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS126.
15+
16+This BIP defines OP_CAT a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS126.
17+
18+When evaluated the OP_CAT instruction:
19+# Pops the top two values off the stack,
20+# concatenate the popped values together,
0# concatenates the popped values together,
18+When evaluated the OP_CAT instruction:
19+# Pops the top two values off the stack,
20+# concatenate the popped values together,
21+# and then pushes the concatenated value on the top of the stack.
22+
23+OP_CAT fails if there are less than two values on the stack or if a concatenated value would have a combined size of greater than the maximum script element size of 520 Bytes.
0OP_CAT fails if there are less 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.
21+# and then pushes the concatenated value on the top of the stack.
22+
23+OP_CAT fails if there are less than two values on the stack or if a concatenated value would have a combined size of greater than the maximum script element size of 520 Bytes.
24+
25+==Motivation==
26+Bitcoin tapscript lacks a general purpose way of combining objects on the stack restricting the expressiveness and power of tapscript. For instance 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.
0Bitcoin 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.
(Alternatively, “For instance this prevents the ability to…”. Both “For instance” and “many other things” seem redundant.)
27+
28+OP_CAT aims to expands the toolbox of the tapscript developer with a simple, modular and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
29+
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely requires the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
0* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
29+
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely requires the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
33+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
34+* Vaults <ref> M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
0* Vaults <ref>M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely requires the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
33+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
34+* Vaults <ref> M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
35+* Replicating CheckSigFromStack <ref> A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 </ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
0* Replicating CheckSigFromStack <ref>A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298</ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
33+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
34+* Vaults <ref> M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
35+* Replicating CheckSigFromStack <ref> A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 </ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
36+
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script.
38+For instance a script which pushed an 1 Byte value on the stack then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes.
0For instance a script which pushed a 1 Byte value on the stack and then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes.
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
Co-authored-by: kallewoof <kalle.alm@gmail.com>
TIL that it is "a one" rather than "an one"
Co-authored-by: kallewoof <kalle.alm@gmail.com>
18+When evaluated the OP_CAT instruction:
19+# Pops the top two values off the stack,
20+# concatenates the popped values together,
21+# and then pushes the concatenated value on the top of the stack.
22+
23+OP_CAT fails if there are less 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.
0OP_CAT fails if there are less 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.
21+# and then pushes the concatenated value on the top of the stack.
22+
23+OP_CAT fails if there are less 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.
24+
25+==Motivation==
26+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.
“Bitcoin Script” or just “tapscript” are perfectly normal terms, their combination somewhat less so:
0Tapscript 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.
27+
28+OP_CAT aims to expands the toolbox of the tapscript developer with a simple, modular and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
29+
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
33+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
34+* Vaults <ref>M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
35+* Replicating CheckSigFromStack <ref>A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298</ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
36+
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script.
0The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script whose evaluation could have memory usage exponential in the size of the script.
33+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
34+* Vaults <ref>M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficent to build vaults in Bitcoin.
35+* Replicating CheckSigFromStack <ref>A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298</ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
36+
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script.
38+For instance a script which pushed a 1 Byte value on the stack and then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes.
0For 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 value whose size was greater than 1 terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 bytes.
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script for which an evaluation could have memory usage exponential in the size of the script.
38+For instance a script which pushed a 1 Byte value on the stack and then repeated the opcodes OP_DUP, OP_CAT 40 times would result in a stack value whose size was greater than 1 Terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 Bytes.
39+
40+==Specification==
41+
42+OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. 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.
0OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. 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.
39+
40+==Specification==
41+
42+OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. 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.
43+
44+Implementation
0===Implementation===
58+}
59+break;
60+</pre>
61+This implementation is inspired by the original implementation of OP_CAT as shown below. An alternative implementation of OP_CAT can be found in Elements <ref>Roose S., Elements Project, "Re-enable several disabled opcodes", 2019, https://github.com/ElementsProject/elements/commit/13e1103abe3e328c5a4e2039b51a546f8be6c60a#diff-a0337ffd7259e8c7c9a7786d6dbd420c80abfa1afdb34ebae3261109d9ae3c19R740-R759</ref>.
62+
63+The value of MAX_SCRIPT_ELEMENT_SIZE is 520 Bytes
0The value of <code>MAX_SCRIPT_ELEMENT_SIZE</code> is 520.
62+
63+The value of MAX_SCRIPT_ELEMENT_SIZE is 520 Bytes
64+
65+==Notes==
66+
67+OP_CAT as it existed in the Bitcoin codebase prior to the commit "misc changes" 4bd188c<ref>S. Nakamoto, "misc changes", Aug 25 2010, https://github.com/bitcoin/bitcoin/commit/4bd188c4383d6e614e18f79dc337fbabe8464c82#diff-27496895958ca30c47bbb873299a2ad7a7ea1003a9faa96b317250e3b7aa1fefL381</ref> which disabled it.
0OP_CAT as it existed in the Bitcoin codebase prior to the commit "misc changes" 4bd188c<ref>S. Nakamoto, "misc changes", Aug 25 2010, https://github.com/bitcoin/bitcoin/commit/4bd188c4383d6e614e18f79dc337fbabe8464c82#diff-27496895958ca30c47bbb873299a2ad7a7ea1003a9faa96b317250e3b7aa1fefL381</ref> which disabled it:
Also, perhaps have the link point to line 94 where the disabling happens, as opposed to the unreachable code?
86+==Acknowledgements==
87+
88+We wish to acknowledge Dan Gould for encouraging and helping review this effort.
89+
90+== Copyright ==
91+This document is placed in the public domain.
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
86+==Acknowledgements==
87+
88+We wish to acknowledge Dan Gould for encouraging and helping review this effort.
89+
90+== Copyright ==
91+This document is placed in the public domain.
0This document is licensed under the 3-clause BSD license.
27+
28+OP_CAT aims to expands the toolbox of the tapscript developer with a simple, modular and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
29+
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref>
0* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport Signatures can be preserved when used in a taproot output.
27+
28+OP_CAT aims to expands the toolbox of the tapscript developer with a simple, modular and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
29+
30+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
31+* Tree Signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
32+* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport Signatures can be preserved when used in a taproot output.
0* Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport signatures can be preserved when used in a taproot output.
0* Tree signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
1* Post-Quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport signatures can be preserved when used in a taproot output.
37+The opcode OP_CAT was available in early versions of Bitcoin. However OP_CAT was removed because it enabled the construction of a script whose evaluation could have memory usage exponential in the size of the script.
38+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 value whose size was greater than 1 terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 bytes.
39+
40+==Specification==
41+
42+OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. 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.
If you check the rendered version, the italics aren’t actually showing, it appears '' needs to be used. The brackets also mess with the result and need a nowiki tag. I’ve tested on my branch that this works:
0OP_CAT pops two elements off the stack, concatenates them together in stack order and pushes the resulting element onto the stack. Given the stack ''<nowiki>[x1, x2]</nowiki>'', where ''x2'' is at the top of the stack, OP_CAT will push ''x1 || x2'' onto the stack. By ''||'' we denote concatenation.
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
bip-???-cat.mediawiki. How do we go about numbering this BIP?
62+
63+The value of <code>MAX_SCRIPT_ELEMENT_SIZE</code> is 520.
64+
65+==Notes==
66+
67+OP_CAT as it existed in the Bitcoin codebase prior to the commit "misc changes" 4bd188c<ref>S. Nakamoto, "misc changes", Aug 25 2010, https://github.com/bitcoin/bitcoin/commit/4bd188c4383d6e614e18f79dc337fbabe8464c82#diff-27496895958ca30c47bbb873299a2ad7a7ea1003a9faa96b317250e3b7aa1fefL381</ref> which disabled it:
0[OP_CAT as it existed in the Bitcoin codebase](https://github.com/bitcoin/bitcoin/blob/01cd2fdaf3ac6071304ceb80fb7436ac02b1059e/script.cpp#L381-L393) prior to the commit "misc changes" 4bd188c<ref>S. Nakamoto, "misc changes", Aug 25 2010, https://github.com/bitcoin/bitcoin/commit/4bd188c4383d6e614e18f79dc337fbabe8464c82#diff-27496895958ca30c47bbb873299a2ad7a7ea1003a9faa96b317250e3b7aa1fefR94</ref> which disabled it:
@kallewoof The BIP file is still name
bip-???-cat.mediawiki. How do we go about numbering this BIP?
Once a BP number has been assigned, the authors are expected to fill that in in the right places.
@kallewoof The BIP file is still name
bip-???-cat.mediawiki. How do we go about numbering this BIP?Once a BP number has been assigned, the authors are expected to fill that in in the right places.
Thanks for the reply. Of course, we’ll change and fill the bip number wherever it’s needed. Has this BIP already been assigned a number? I might have missed that comment
Add backwards compatibility section
Missing a section for backward compatibility @luke-jr Added!
11+ License: BSD-3-Clause
12+</pre>
13+
14+==Abstract==
15+
16+This BIP reintroduces OP_CAT in the form of a new tapscript opcode which allows the concatenation of two values on the stack. This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS126.
(0x7e) might help be a bit clearer. Libraries in various languages have small variations on OP code naming.
10+ Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-op-cat
11+ License: BSD-3-Clause
12+</pre>
13+
14+==Abstract==
15+
And some grammar + spelling cleanup
add clarifying note about the current opcode
I would like to propose to replace the per-item size limit with a total stack size limit that is equivalent and can be introduced as a softfork as well. Since we currently allow 1000 items of 520 bytes, I would propose a 520kB (520,000 bytes) size limit for the entire stack + altstack.
This can be implemented as such:
0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
1index 1583b5fadd3..cbe1695bab2 100644
2--- a/src/script/interpreter.cpp
3+++ b/src/script/interpreter.cpp
4@@ -545,8 +545,6 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
5 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
6 valtype& vch1 = stacktop(-2);
7 valtype& vch2 = stacktop(-1);
8- if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
9- return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
10 vch1.insert(vch1.end(), vch2.begin(), vch2.end());
11 stack.pop_back();
12 }
13@@ -1287,8 +1285,17 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript&
14 }
15
16 // Size limits
17+ // limit number of elements in stacks
18 if (stack.size() + altstack.size() > MAX_STACK_SIZE)
19 return set_error(serror, SCRIPT_ERR_STACK_SIZE);
20+ // limit total number of bytes in stacks
21+ unsigned int total_bytes = 0;
22+ for (size_t i = 0; i < stack.size() ; i++)
23+ total_bytes += stack[i].size();
24+ for (size_t i = 0; i < altstack.size() ; i++)
25+ total_bytes += altstack[i].size();
26+ if (total_bytes > MAX_STACK_BYTES)
27+ return set_error(serror, SCRIPT_ERR_STACK_SIZE);
28 }
29 }
30 catch (...)
31diff --git a/src/script/script.h b/src/script/script.h
32index 305919f5ba4..ef40c3672ee 100644
33--- a/src/script/script.h
34+++ b/src/script/script.h
35@@ -38,6 +38,9 @@ static const int MAX_SCRIPT_SIZE = 10000;
36 // Maximum number of values on script interpreter stack
37 static const int MAX_STACK_SIZE = 1000;
38
39+// Maximum number of total bytes on script interpreter stack
40+static const int MAX_STACK_BYTES = 520000; // 520 * 1000
41+
42 // Threshold for nLockTime: below this value it is interpreted as block number,
43 // otherwise as UNIX timestamp.
44 static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
NACK
OP_CAT enables recursion which is computational equivalent to iteration; thus making Script Turing complete.
In case this claim originates with something I’ve said publicly: I am confident that CAT does not introduce recursion to Script and I have never (intentionally) said that it did.
CAT does introduce a form of recursive covenants. But the form of “recursion” here is one that involves a fresh transaction for every iteration, and does not change the computational model at all.
Update OP_CAT implementation code
To stevenroose’s proposal. https://github.com/bitcoin/bips/pull/1525#issuecomment-1979297869
I would like to propose to replace the per-item size limit with a total stack size limit that is equivalent and can be introduced as a softfork as well. Since we currently allow 1000 items of 520 bytes, I would propose a 520kB (520,000 bytes) size limit for the entire stack + altstack.
This can be implemented as such:
0diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp 1index 1583b5fadd3..cbe1695bab2 100644 2--- a/src/script/interpreter.cpp 3+++ b/src/script/interpreter.cpp 4@@ -545,8 +545,6 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& 5 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); 6 valtype& vch1 = stacktop(-2); 7 valtype& vch2 = stacktop(-1); 8- if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE) 9- return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION); 10 vch1.insert(vch1.end(), vch2.begin(), vch2.end()); 11 stack.pop_back(); 12 } 13@@ -1287,8 +1285,17 @@ bool EvalScript(std::vector<std::vector<unsigned char> >& stack, const CScript& 14 } 15 16 // Size limits 17+ // limit number of elements in stacks 18 if (stack.size() + altstack.size() > MAX_STACK_SIZE) 19 return set_error(serror, SCRIPT_ERR_STACK_SIZE); 20+ // limit total number of bytes in stacks 21+ unsigned int total_bytes = 0; 22+ for (size_t i = 0; i < stack.size() ; i++) 23+ total_bytes += stack[i].size(); 24+ for (size_t i = 0; i < altstack.size() ; i++) 25+ total_bytes += altstack[i].size(); 26+ if (total_bytes > MAX_STACK_BYTES) 27+ return set_error(serror, SCRIPT_ERR_STACK_SIZE); 28 } 29 } 30 catch (...) 31diff --git a/src/script/script.h b/src/script/script.h 32index 305919f5ba4..ef40c3672ee 100644 33--- a/src/script/script.h 34+++ b/src/script/script.h 35@@ -38,6 +38,9 @@ static const int MAX_SCRIPT_SIZE = 10000; 36 // Maximum number of values on script interpreter stack 37 static const int MAX_STACK_SIZE = 1000; 38 39+// Maximum number of total bytes on script interpreter stack 40+static const int MAX_STACK_BYTES = 520000; // 520 * 1000 41+ 42 // Threshold for nLockTime: below this value it is interpreted as block number, 43 // otherwise as UNIX timestamp. 44 static const unsigned int LOCKTIME_THRESHOLD = 500000000; // Tue Nov 5 00:53:20 1985 UTC
This seems to require checking the size limit after every opcode is computed, and it might not be scalable. I think this may need to be left to a different PR. Calculating the delta and only updating the delta is possible, but it would need to change the implementation a lot.
I would like to propose to replace the per-item size limit with a total stack size limit that is equivalent and can be introduced as a softfork as well. Since we currently allow 1000 items of 520 bytes, I would propose a 520kB (520,000 bytes) size limit for the entire stack + altstack.
Consider the following script:
0"1234567" DUP CAT 8 CAT
1DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT
2DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT DUP CAT
3
41 SHA256 OVER CAT SHA256
5[ OVER CAT SHA256 ] * 130000
6CAT SHA256
It constructs a ~246kB string on the stack consisting of lots of repeats of “123456712345678”, then repeatedly concatenates that string to a sha256 hash, using the hash of the result as the new sha256 hash. Doing this 130k times means you’re hashing about 32GB of data despite never having more than about 492kB on the stack in total, while still fitting in a standard tx with less than 400k weight units. For comparsion, constraining each stack element to being 520 bytes limits the total amount hashed to under 208MB for any standard transaction.
Bob Summerwill proposed a number of changes to the OP_CAT BIP to better follow BIP-2. This commit makes these changes:
* Using the section order specified in BIP-2
* Adding a Rationale section
* Expand the specification section by moving details from the abstract into the specification
Additionally this commit as rewords some confusing language.
Thanks Bob
34+
35+OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular, and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
36+
37+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
38+* Tree signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with a thousand public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
39+* Post-Quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport signatures can be preserved when used in a taproot output.
nit:
0* Post-quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if the quantum resistance of Lamport signatures can be preserved when used in a taproot output.
It is an open question if the quantum resistance of Lamport signatures can be preserved when used in a taproot output.
I’m not sure if this adds even more confusion. In the most direct sense, taproot outputs are clearly not post-quantum secure because the attacker can perform a key-path spend. Maybe something like: “Putting aside the ability to perform key-path spends, which clearly makes taproot insecure against a quantum attacker, it is an open question if the quantum resistance of Lamport signatures can be preserved when used in a script committed to in a taproot output.”
@real-or-random Thanks for taking a look at this.
There is some history behind the intentional ambiguity in our statement here. we’ve been doing research on the quantum security of tapscript. I agree the script spend commit is probably provably quantum resistant under some assumptions. I had hoped I could find a way to prevent key path spends by constructing the taproot output in such a way that it would break the key spend path, e.g. an output where the only key spend signatures result in an invalid curve point. I haven’t fully thrown in the towel on that attempt but it is looking highly unlikely at this point.
Let me edit this
Yep, great, I think it’s clearer now.
Micro nit in the new paragraph: s/Lamport Signatures/Lamport signatures
@delbonis anybody can propose anything formally, by running through the process of creating a proposal, soliciting input on the mailing list, etc.
But the three opcodes you mention can be fairly-cheaply emulated using CAT, and have fewer direct usecases, so it may not be a productive direction to pursue.
@delbonis @JeremyRubin Re: OP_LEFT/RIGHT/SUBSTR
There are still values in OP_LEFT/RIGHT/SUBSTR. To emulate them with OP_CAT, one needs to provide a hint, and this takes space in the witness stack / input stack. This is inconvenient because the witness stack can have at most 1000 elements.
In our practice with Merkle trees for STARK proof verifier that uses OP_CAT, for each layer, we need to provide a sibling element. A standard transaction only prefers binary Merkle tree. And therefore, there are log_{2} n elements that we need to push in the witness stack. (nonstandard transaction is an easier situation, which allows log_{16} n) OP_LEFT/RIGHT/SUBSTR, if together with a nonstandard transaction, can allow one to pack elements compactly to save stack space.
Here is the related codebase: https://github.com/Bitcoin-Wildlife-Sanctuary/bitcoin-circle-stark?tab=readme-ov-file#performance
But I think people can agree that bringing back OP_SUBSTR is enough. This allows us to save other successful opcodes for other purposes.
That said, this is not related to the OP_CAT BIP discussion, and may be better discussed in other venues.
Adds additional acks
Thanks for your question!
Could you point me toward where i can learn more about the stack size limit referred? @OminousPeace
In the OP_CAT reference implementation in BIP-347:
0case OP_CAT:
1{
2 if (stack.size() < 2)
3 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
4 valtype& vch1 = stacktop(-2);
5 valtype& vch2 = stacktop(-1);
6 if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
7 return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
8 vch1.insert(vch1.end(), vch2.begin(), vch2.end());
9 stack.pop_back();
10}
11break;
We check that their are sufficient elements on the stack:
0 if (stack.size() < 2)
1 return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
Then we check that the CAT operation will not create a stack element larger than the max stack element:
0 if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
1 return set_error(serror, SCRIPT_ERR_PUSH_SIZE);
MAX_SCRIPT_ELEMENT_SIZE is defined as 520 (bytes) in bitcoin-core.
0// Maximum number of bytes pushable to the stack
1static const unsigned int MAX_SCRIPT_ELEMENT_SIZE = 520;
OP_CAT is neutral with regard to the total size of stack because it joins two elements together which were already on the stack. That is, an OP_CAT operation should never increase or decrease the total size of stack in bytes.
For running code see our implementation of OP_CAT in bitcoin-inquisition.
Is it enforced by tapscript?
Both script and tapscript enforce the element stack size limit and the total stack size limit when a OP_PUSH occurs. OP_CAT like any other opcode which pushes data on the stack, must also ensure that it does not violate this limit, which is why returns an error if it would push an element greater than the maximum stack element size (520).
We do provide a rationale for why we don’t alter bitcoin consensus to increase the stack element size limit in the rationale section of the BIP.
Did that answer your question?
6+ Armin Sabouri <arminsdev@gmail.com>
7+ Comments-URI: https://github.com/bitcoin/bips/wiki/Comments:BIP-0347
8+ Status: Draft
9+ Type: Standards Track
10+ Created: 2023-10-21
11+ License: BSD-3-Clause
13+
14+==Abstract==
15+
16+This 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.
17+
18+== Copyright ==
Consistency-nit: Some of your Section Headings are followed by a blank line, while others are not. Please add blank lines under each Heading, or remove them all:
0== Copyright ==
27+
28+Given the stack ''<nowiki>[x1, x2]</nowiki>'', 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.
29+
30+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.
31+
32+==Motivation==
Nit: please use consistent formatting for Section Headings.
0==Motivation==
18+== Copyright ==
19+This document is licensed under the 3-clause BSD license.
20+
21+==Specification==
22+
23+When evaluated the OP_CAT instruction:
0When evaluated, the OP_CAT instruction:
34+
35+OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular, and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
36+
37+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
38+* Tree signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with up to 4,294,967,296 public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
39+* Post-Quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It is an open question if a tapscript commitment would preserve the quantum resistance of Lamport signatures. Beyond this question, the use of Lamport Signatures in taproot outputs is unlikely to be quantum resistant even if the script spend-path is made quantum resistant. This is because taproot outputs can also be spent with a key. An attacker with a sufficiently powerful quantum computer could bypass the taproot script spend-path by finding the discrete log of the taproot output and thus spending the output using the key spend-path. The use of "Nothing Up My Sleeve" (NUMS) points as described in [[bip-0341.mediawiki|BIP341]] to disable the key spend-path does not disable the key spend-path against a quantum attacker as NUMS relies on the hardness of finding discrete logs. We are not aware of any mechanism which could disable the key spend-path in a taproot output without a softfork change to taproot.
Thanks for this comment, I want to be very careful we are not over claiming the quantum security OP_CAT gets you.
Assuming that the script-spend commitment is quantum resistant (there is no published security proof for this assumption), then OP_CAT in tapscript will not enable quantum security unless:
Someone invents a way to construct a taproot output which can not be spent via the key spend path but can be spent via the script spend path. There is no known way to do this and it is probably impossible. However it has not been shown to be impossible.
OR a mechanism is added to bitcoin to disable key-spend paths.
It has been proposed that if ECDSA is broken or a powerful quantum computer was on the horizon, there might be an effort to protect ownership of bitcoins by allowing people to mark their taproot outputs as “script-spend only” and then move their coins into such outputs. Such a mechanism could be used in conjunction with OP_CAT to enable quantum security.
This is a confusing topic to discuss without speculation on future unknowns and security countermeasures that go well beyond the scope of OP_CAT.
What are your thoughts on increasing clarity of this paragraph while staying within the scope of the BIP? Should I just say less?
I see thanks for the explanation. Perhaps another sentence to provide the context of the scenario you are alluding to would help to clarify:
Perhaps:
0* Post-Quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It has been proposed that if ECDSA is broken or a powerful computer was on the horizon, there might be an effort to protect ownership of bitcoins by allowing people to mark their taproot outputs as "script-path only" and then move their coins into such outputs with a leaf in the script tree requiring a Lamport signature. It is an open question if a tapscript commitment would preserve the quantum resistance of Lamport signatures. Beyond this question, the use of Lamport Signatures in taproot outputs is unlikely to be quantum resistant even if the script spend-path is made quantum resistant. This is because taproot outputs can also be spent with a key. An attacker with a sufficiently powerful quantum computer could bypass the taproot script spend-path by finding the discrete log of the taproot output and thus spending the output using the key spend-path. The use of "Nothing Up My Sleeve" (NUMS) points as described in [[bip-0341.mediawiki|BIP341]] to disable the key spend-path does not disable the key spend-path against a quantum attacker as NUMS relies on the hardness of finding discrete logs. We are not aware of any mechanism which could disable the key spend-path in a taproot output without a softfork change to taproot.
52+
53+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.
54+
55+==Backwards Compatibility==
56+
57+OP_CAT usage in an 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 a soft fork that redefines an OP_SUCCESSx opcode (OP_SUCCESS126) to OP_CAT.
0OP_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.
0@@ -0,0 +1,106 @@
1+<pre>
2+ BIP: 347
3+ Layer: Consensus (soft fork)
4+ Title: OP_CAT
Perhaps include in the title that the opcode is only added to Tapscript:
0 Title: Reenable OP_CAT in Tapscript
28+Given the stack ''<nowiki>[x1, x2]</nowiki>'', 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.
29+
30+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.
31+
32+==Motivation==
33+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.
“This prevents among many other things the ability to construct and evaluate merkle trees and other hashed data structures in tapscript.”
This phrasing sounds a bit funny to me. Since there are other ways how such features could be implemented, the absence of OP_CAT does not prevent the implementation of said features. Rather, OP_CAT provides a means to achieve the features.
This isn’t saying that the absence of OP_CAT specifically prevents this, but rather the absence of anyway to combine objects on the stack prevents this*. 256-bit add would let you do this, as would a hash op code that takes two stack elements. There are plenty of other ways to do this, OP_CAT is just a simple solution.
*-Technically you can OP_ADD two 4 byte objects on the stack, but once you hash them, you can’t meaningfully combine that hash output with another hash output.
Okay, I see that you distinguish the general situation from the specific tool and my feedback there is not convincing.
Very nitty, but I would distinguish the Tapscript language (capitalized) from tapscripts (lowercased) appearing in script tree leafs, see e.g. https://bitcoin.stackexchange.com/a/122808/5406.
I also think this sentence would be easier to read by adding a few more commas.
0Bitcoin 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.
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
Co-authored-by: Vojtěch Strnad <43024885+vostrnad@users.noreply.github.com>
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
0@@ -0,0 +1,108 @@
1+<pre>
2+ BIP: 347
3+ Layer: Consensus (soft fork)
4+ Title: Enable OP_CAT in Tapscript
BIP titles normally don’t start with a verb (unlike e.g. commit names):
0 Title: OP_CAT in Tapscript
35+
36+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.
37+
38+OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular, and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
39+
40+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
0* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT, they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
I have left a couple more nits that you may address or ignore freely, I don’t consider any to be blocking.
The BIP described in this PR fulfills the criteria set out in BIP2, it:
and therefore appears to be ready to be merged.¹
ACK 696cc1713b931589d01c544d3016f3cf57be0058
¹ This should be obvious, but to make it explicit: This is a clerical assessment of the completeness of this PR. I am neither endorsing this BIP nor expressing any opinion on whether OP_CAT should be activated.
@luke-jr had previously requested changes:
Missing a section for backward compatibility
which I consider to have been addressed. I will abstain from merging this PR for some time, to give other editors a chance to make their own assessment.
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
This improves readability, thanks!
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
Co-authored-by: Mark "Murch" Erhardt <murch@murch.one>
38+OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modular, and useful opcode in the spirit of Unix <ref>R. Pike and B. Kernighan, "Program design in the UNIX environment", 1983, https://harmful.cat-v.org/cat-v/unix_prog_design.pdf</ref>. To demonstrate the usefulness of OP_CAT below we provide a non-exhaustive list of some usecases that OP_CAT would enable:
39+
40+* Bitstream, a protocol for the atomic swap (fair exchange) of bitcoins for decryption keys, that enables decentralized file hosting systems paid in Bitcoin. While such swaps are currently possible on Bitcoin without OP_CAT, they require the use of complex and computationally expensive Verifiable Computation cryptographic techniques. OP_CAT would remove this requirement on Verifiable Computation, making such protocols far more practical to build in Bitcoin. <ref>R. Linus, "BitStream: Decentralized File Hosting Incentivised via Bitcoin Payments", 2023, https://robinlinus.com/bitstream.pdf</ref>
41+* Tree signatures provide a multisignature script whose size can be logarithmic in the number of public keys and can encode spend conditions beyond n-of-m. For instance a transaction less than 1KB in size could support tree signatures with up to 4,294,967,296 public keys. This also enables generalized logical spend conditions. <ref> P. Wuille, "Multisig on steroids using tree signatures", 2015, https://blog.blockstream.com/en-treesignatures/</ref>
42+* Post-Quantum Lamport signatures in Bitcoin transactions. Lamport signatures merely require the ability to hash and concatenate values on the stack. <ref>J. Rubin, "[bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was CheckSigFromStack for Arithmetic Values]", 2021, https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html</ref> It has been proposed that if ECDSA is broken or a powerful computer was on the horizon, there might be an effort to protect ownership of bitcoins by allowing people to mark their taproot outputs as "script-path only" and then move their coins into such outputs with a leaf in the script tree requiring a Lamport signature. It is an open question if a tapscript commitment would preserve the quantum resistance of Lamport signatures. Beyond this question, the use of Lamport Signatures in taproot outputs is unlikely to be quantum resistant even if the script spend-path is made quantum resistant. This is because taproot outputs can also be spent with a key. An attacker with a sufficiently powerful quantum computer could bypass the taproot script spend-path by finding the discrete log of the taproot output and thus spending the output using the key spend-path. The use of "Nothing Up My Sleeve" (NUMS) points as described in [[bip-0341.mediawiki|BIP341]] to disable the key spend-path does not disable the key spend-path against a quantum attacker as NUMS relies on the hardness of finding discrete logs. We are not aware of any mechanism which could disable the key spend-path in a taproot output without a softfork change to taproot.
43+* Non-equivocation contracts <ref>T. Ruffing, A. Kate, D. Schröder, "Liar, Liar, Coins on Fire: Penalizing Equivocation by Loss of Bitcoins", 2015, https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf</ref> in tapscript provide a mechanism to punish equivocation/double spending in Bitcoin payment channels. OP_CAT enables this by enforcing rules on the spending transaction's nonce. The capability is a useful building block for payment channels and other Bitcoin protocols.
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.727.6262&rep=rep1&type=pdf doesn’t seem to be the correct link for me
It seems useful to use the ACM DOI URI for that paper mentioned above with the nonfunctional link: https://dl.acm.org/doi/10.1145/2810103.2813686
It is very likely to still work for ten more years. Although it is paywalled, people can find free versions online.
It seems useful to use the ACM DOI URI for that paper mentioned above with the nonfunctional link: dl.acm.org/doi/10.1145/2810103.2813686
It is very likely to still work for ten more years. Although it is paywalled, people can find free versions online.
Yep, sorry, we weren’t allowed to upload it to eprint.iacr.org or arXiv due to copyright reasons. (The ACM is evil…)
But it’s lawfully available under https://publications.cispa.saarland/565/1/penalizing.pdf (Web Archive: https://web.archive.org/web/20221023121048/https://publications.cispa.saarland/565/1/penalizing.pdf), and I’ve also just made it available under https://raw.githubusercontent.com/real-or-random/accas/master/paper.pdf (Web Archive: https://web.archive.org/web/20240506104315/https://raw.githubusercontent.com/real-or-random/accas/master/paper.pdf).
43@@ -44,8 +44,12 @@ OP_CAT aims to expand the toolbox of the tapscript developer with a simple, modu
44 * Vaults <ref>M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, http://fc16.ifca.ai/bitcoin/papers/MES16.pdf</ref> which are a specialized covenant that allows a user to block a malicious party who has compromised the user's secret key from stealing the funds in that output. As shown in <ref>A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</ref> OP_CAT is sufficient to build vaults in Bitcoin.
45 * Replicating CheckSigFromStack <ref>A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298</ref> which would allow the creation of simple covenants and other advanced contracts without having to presign spending transactions, possibly reducing complexity and the amount of data that needs to be stored. Originally shown to work with Schnorr signatures, this result has been extended to ECDSA signatures <ref>R. Linus, "Covenants with CAT and ECDSA", 2023, https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md</ref>.
46
47-The opcode OP_CAT was available in early versions of Bitcoin. However, OP_CAT was removed because it enabled the construction of a script whose evaluation could have memory usage exponential in the size of the script.
48-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 value whose size was greater than 1 terabyte. This is no longer an issue because tapscript enforces a maximum stack element size of 520 bytes.
49+OP_CAT was available in early versions of Bitcoin.
50+In 2010, a single commit disabled OP_CAT, along with another 15 opcodes.
51+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.
52+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.
In the new commit cda34eef1c2543ece1205240f27e8d1cfffb336d “As Bitcoin at that time had a maximum stack element size of 5000 bytes”
I’m probably confused, but even in this commit git show 0a61b0df1224a5470bcddab302bc199ca5a9e356 from 2010 it looks like the maximum stack element size of 520 bytes was present, i.e. src/script.cpp#L343 - if (vchPushValue.size() > 520).
@jonatack The same commit that removed the 15 opcodes also reduced the maximum stack element size from 5000 to 520.
When OP_CAT was active in Bitcoin the maximum stack element size was 5000.
The commit you reference 0a61b0df1224a5470bcddab302bc199ca5a9e356 is from Aug 29, 2010. OP_CAT and the maximum element size change was made in commit 4bd188c4383d6e614e18f79dc337fbabe8464c82 two weeks earlier on Aug 15 2010.
ACK 7ad0f821ddc60366e98344a1e3019114ae46c80f
Seems to me that all open review comments have been addressed.
