Hi Greg, I didn't mean to imply this limit is a unique feature of tapescript, but rather that:OP_CAT is a tapscript opcode and that tapscript enforces a 520 byte element size thus we don't have to worry about OP_CAT creating very large stack elements.
Thanks for pointing this out, I didn't realize that this limit was added in the same commit that removed OP_CAT. I thought it was more recent than that. Reading through that commit it also appears that it also reduced the size limit on inputs to arithmetic operations (nMaxNumSize) from 2064-bits to 32-bits. I had always assumed it was 32-bits from the beginning. It would have been wild to have math opcodes that support 2064-bit inputs and outputs. Thanks, Ethan On Sat, Oct 21, 2023 at 12:10 PM Greg Sanders <gsander...@gmail.com> wrote: > > This is no > longer an issue in the current age as tapscript enforces a maximum > stack element size of 520 Bytes. > > I don't think there's a new limit related to tapscript? In the very > beginning there was no limit, but a 5k limit was put into place, then 520 > the same commit that OP_CAT was > disabled: 4bd188c4383d6e614e18f79dc337fbabe8464c82 > > On Sat, Oct 21, 2023 at 1:09 AM Ethan Heilman via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> Hi everyone, >> >> We've posted a draft BIP to propose enabling OP_CAT as Tapscript opcode. >> https://github.com/EthanHeilman/op_cat_draft/blob/main/cat.mediawiki >> >> OP_CAT was available in early versions of Bitcoin. It was disabled as >> it allowed the construction of a script whose evaluation could create >> stack elements exponential in the size of the script. This is no >> longer an issue in the current age as tapscript enforces a maximum >> stack element size of 520 Bytes. >> >> Thanks, >> Ethan >> >> ==Abstract== >> >> 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_SUCCESS80. >> >> When evaluated the OP_CAT instruction: >> # Pops the top two values off the stack, >> # concatenate the popped values together, >> # and then pushes the concatenated value on the top of the stack. >> >> 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. >> >> ==Motivation== >> 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. >> >> 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: >> >> * 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. [2] >> * Post-Quantum Lamport Signatures in Bitcoin transactions. Lamport >> signatures merely requires the ability to hash and concatenate values >> on the stack. [3] >> * Non-equivocation contracts [4] 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. >> * Vaults [5] 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. >> * 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. [6] >> >> 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. >> 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. >> >> ==Specification== >> >> Implementation >> <pre> >> 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_INVALID_STACK_OPERATION); >> >> valtype vch3; >> vch3.reserve(vch1.size() + vch2.size()); >> vch3.insert(vch3.end(), vch1.begin(), vch1.end()); >> vch3.insert(vch3.end(), vch2.begin(), vch2.end()); >> >> popstack(stack); >> popstack(stack); >> stack.push_back(vch3); >> </pre> >> >> The value of MAX_SCRIPT_ELEMENT_SIZE is 520 Bytes >> >> == Reference Implementation == >> [Elements]( >> https://github.com/ElementsProject/elements/blob/master/src/script/interpreter.cpp#L1043 >> ) >> >> ==References== >> >> [1]: R. Pike and B. Kernighan, "Program design in the UNIX >> environment", 1983, >> https://harmful.cat-v.org/cat-v/unix_prog_design.pdf >> [2]: P. Wuille, "Multisig on steroids using tree signatures", 2015, >> >> https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html >> [3]: 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 >> [4]: 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 >> [5]: M. Moser, I. Eyal, and E. G. Sirer, Bitcoin Covenants, >> http://fc16.ifca.ai/bitcoin/papers/MES16.pdf >> [6]: R. Linus, "Covenants with CAT and ECDSA", 2023, >> >> https://gist.github.com/RobinLinus/9a69f5552be94d13170ec79bf34d5e85#file-covenants_cat_ecdsa-md >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> >
_______________________________________________ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
