Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Sat, Oct 21, 2023 at 01:08:03AM -0400, Ethan Heilman via bitcoin-dev wrote: > 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 If you're interested in making this available via inquisition, here's a set of 3 patches that should allow it to be messed with on regtest: https://github.com/ajtowns/bitcoin/commits/202310-inq25-cat Tests need updating and adding, however. You might wish to compare with similar commits from the APO/CTV PRs at https://github.com/bitcoin-inquisition/bitcoin/pull/33 https://github.com/bitcoin-inquisition/bitcoin/pull/34 It may be worth adding support for CSFS as well, if experimenting with that is desirable, rather than having them as separate script-verify flags and deployments. > [1]: R. Pike and B. Kernighan, "Program design in the UNIX > environment", 1983, > https://harmful.cat-v.org/cat-v/unix_prog_design.pdf "harmful cat", you say? Cheers, aj ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Sat, Oct 21, 2023 at 01:08:03AM -0400, Ethan Heilman via bitcoin-dev wrote: > 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. Note that if OP_CAT immediately _succeeds_ if the combined size is >= 520 bytes, reverting to the behavior of OP_SUCCESSx, the maximum size can be increased in a subsequent soft fork. Of course, this would often require extra opcodes to validate the size of non-const arguments. But you'd only need another five or six bytes in many cases: SIZE LESSTHAN VERIFY CAT -- https://petertodd.org 'peter'[:-1]@petertodd.org signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
I have to admit - I'm somewhat baffled at the enthusiasm for a "just CAT" softfork, since I can't see that it would achieve much. It's indicative to me that there isn't a compelling example to date that (i) actually has working code and (ii) only relies upon CAT. I'm not averse to CAT, just confused that there's a lot of enthusiasm for a CAT-only fork. To do actually-interesting covenants, afacit you'd need "introspection" opcodes and/or CHECKSIGFROMSTACK - and even then, for almost all applications I'm familiar with, that kind of CAT-based approach would be much more circuitous than the alternatives that have been discussed for years on this list. > Vaults I don't think this is actually a use-case that CAT materially helps with. Andrew's posts, while well written and certainly foundational, do not sketch a design for vaults that someone would actually use. I don't see how CAT alone (without many auxiliary introspection opcodes) facilitates vaults that clear the usability hurdles I describe in this paper: https://jameso.be/vaults.pdf. For example, batched withdrawals and partial unvaultings don't seem possible. Even with introspection opcodes, Burak's ( https://brqgoo.medium.com/emulating-op-vault-with-elements-opcodes-bdc7d8b0fe71) prototype wasn't able to handle revaulting - an important feature for usability (https://twitter.com/jamesob/status/1636546085186412544). > Tree signatures To what extent does Taproot obviate this use? ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
I support OP_CAT, along with reasonable resource-consumption limiters. Implementation as a UASF would help build confidence in that method. I also support moving forward on other opcodes as soon as they are known to be safe and maintainable; whether for introspection, tx unpinning, or vaults. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
If there is sufficient interest in enabling OP_CAT on Bitcoin and there is a strong desire in the community for using OP_SUCCESS126 rather than OP_SUCCESS80 then I'd be happy to switch to OP_SUCCESS126. I don't have any particular affinity for OP_SUCCESS80. Is there anyone who objects to using OP_SUCCESS126 rather than OP_SUCCESS80? On Tue, Oct 24, 2023 at 4:12 PM Steven Roose via bitcoin-dev wrote: > > I agree that there is no reason not to use OP_SUCCESS126, i.e. the original > OP_CAT opcode 0x7e. In many codebases, for example in Core, there might be > two OP_CAT constants than which might be confusing. > > On 10/22/23 09:58, vjudeu via bitcoin-dev wrote: > > > This opcode would be activated via a soft fork by redefining the opcode > > OP_SUCCESS80. > > Why OP_SUCCESS80, and not OP_SUCCESS126? When there is some existing opcode, > it should be reused. And if OP_RESERVED will ever be re-enabled, I think it > should behave in the same way, as in pre-Taproot, so it should "Mark > transaction as invalid unless occuring in an unexecuted OP_IF branch". Which > means, " OP_VERIFY" should be equivalent to " OP_NOTIF > OP_RESERVED OP_ENDIF". > > > > On 2023-10-21 07:09:13 user Ethan Heilman via bitcoin-dev > 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 A. Poelstra, "CAT > and Schnorr Tricks II", 2021, > https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html > OP_CAT is sufficent to build vaults in Bitcoin. > * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr > Tricks I", 2021, > https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 > 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
Re: [bitcoin-dev] Proposed BIP for OP_CAT
I agree that there is no reason not to use OP_SUCCESS126, i.e. the original OP_CAT opcode 0x7e. In many codebases, for example in Core, there might be two OP_CAT constants than which might be confusing. On 10/22/23 09:58, vjudeu via bitcoin-dev wrote: > This opcode would be activated via a soft fork by redefining the opcode OP_SUCCESS80. Why OP_SUCCESS80, and not OP_SUCCESS126? When there is some existing opcode, it should be reused. And if OP_RESERVED will ever be re-enabled, I think it should behave in the same way, as in pre-Taproot, so it should "Mark transaction as invalid unless occuring in an unexecuted OP_IF branch". Which means, " OP_VERIFY" should be equivalent to " OP_NOTIF OP_RESERVED OP_ENDIF". On 2023-10-21 07:09:13 user Ethan Heilman via bitcoin-dev 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 A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html OP_CAT is sufficent to build vaults in Bitcoin. * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 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 if (stack.size() <
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Tue, Oct 24, 2023 at 02:15:49PM +1030, Rusty Russell wrote: > Andrew Poelstra writes: > > I had a similar thought. But my feeling is that replacing the stack > > interpreter data structure is still too invasive to justify the benefit. > > > > Also, one of my favorite things about this BIP is the tiny diff. > > To be fair, this diff is even smaller than the OP_CAT diff :) > Oh, look at that :). For some reason I had it in my head that looping like this would mess up the asymptotics and meaningfully harm performance. But no, it just involves adding (at most) 1000 numbers. Which is unlikely to even be measurable. > Though I had to strongly resist refactoring, that interpreter code > needs a good shake! Using a class for the stack is worth doing anyway > (macros, really??). > Hah, agreed, but it still makes my hands sweat to think about refactoring that file. -- Andrew Poelstra Director of Research, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
Andrew Poelstra writes:
> I had a similar thought. But my feeling is that replacing the stack
> interpreter data structure is still too invasive to justify the benefit.
>
> Also, one of my favorite things about this BIP is the tiny diff.
To be fair, this diff is even smaller than the OP_CAT diff :)
Though I had to strongly resist refactoring, that interpreter code
needs a good shake! Using a class for the stack is worth doing anyway
(macros, really??).
diff --git a/src/script/interpreter.cpp b/src/script/interpreter.cpp
index dcaf28c2472..2ee2034115f 100644
--- a/src/script/interpreter.cpp
+++ b/src/script/interpreter.cpp
@@ -403,6 +403,19 @@ static bool EvalChecksig(const valtype& sig, const
valtype& pubkey, CScript::con
assert(false);
}
+// First 520 bytes is free, after than you consume an extra slot!
+static size_t effective_size(const std::vector >&
stack)
+{
+size_t esize = stack.size();
+
+for (const auto& v : stack)
+{
+if (v.size() > MAX_SCRIPT_ELEMENT_SIZE)
+esize += (v.size() - 1) / MAX_SCRIPT_ELEMENT_SIZE;
+}
+return esize;
+}
+
bool EvalScript(std::vector >& stack, const
CScript& script, unsigned int flags, const BaseSignatureChecker& checker,
SigVersion sigversion, ScriptExecutionData& execdata, ScriptError* serror)
{
static const CScriptNum bnZero(0);
@@ -1239,7 +1252,7 @@ bool EvalScript(std::vector >&
stack, const CScript&
}
// Size limits
-if (stack.size() + altstack.size() > MAX_STACK_SIZE)
+if (effective_size(stack) + effective_size(altstack) >
MAX_STACK_SIZE)
return set_error(serror, SCRIPT_ERR_STACK_SIZE);
}
}
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Tue, Oct 24, 2023 at 11:18:24AM +1030, Rusty Russell wrote: > Andrew Poelstra writes: > >> 3. Should we restrict elsewhere instead? After all, OP_CAT doesn't > >>change total stack size, which is arguably the real limit? > >> > > > > Interesting thought. Right now the stack size is limited to 1000 > > elements of 520 bytes each, which theoretically means a limit of 520k. > > Bitcoin Core doesn't explicitly count the "total stack size" in the > > sense that you're suggesting; it just enforces these two limits > > separately. > > BTW, I'm just learning of the 1000 element limit; I couldn't see it on > scanning BIP-141. > This limit is very old and predates segwit. It might predate P2SH. > > I think trying to add a "total stack size limit" (which would have to > > live alongside the two existing limits; we can't replace them without > > a whole new Tapscript version) would add a fair bit of accounting > > complextiy and wind up touching almost every other opcode...probably > > not worth the added consensus logic. > > Simplest thing I can come up with: > > - instead of counting simple stack depth, count each stack entry as > (1 + /520) entries? You can still only push 520 bytes, so you > can only make these with OP_CAT. > > Looking in interpreter.cpp, `stack` and `altstack` now need to be > objects to count entries differently (not vectors), but it seems like > it'd be simple enough, and the logic could be enabled unconditionally > since it Cannot Be Violated prior to OP_CAT. > I had a similar thought. But my feeling is that replacing the stack interpreter data structure is still too invasive to justify the benefit. Also, one of my favorite things about this BIP is the tiny diff. -- Andrew Poelstra Director of Research, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
Andrew Poelstra writes: > On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote: >> Ethan Heilman via bitcoin-dev writes: >> > 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 >> >> 520 feels quite small for script templates (mainly because OP_CAT itself >> makes Script more interesting!). For example, using OP_TXHASH and >> OP_CAT to enforce that two input amounts are equal to one output amount >> takes about 250 bytes of Script[2] :( >> >> So I have to ask: >> >> 1. Do other uses feel like 520 is too limiting? > > In my view, 520 feels limiting provided that we lack rolling sha2 > opcodes. If we had those, then arguably 65 bytes is enough. Without > them, I'm not sure that any value is "enough". For CHECKSIGFROMSTACK > emulation purposes ideally we'd want the ability to construct a full > transaction on the stack, which in principle would necessitate a 4M > limit. I haven't yet found a desire for rolling sha2: an `OP_MULTISHA256` has been sufficient for my templating investigations w/ OP_TXHASH. In fact, I prefer it to OP_CAT, but OP_CAT does allow your Schnorr sig trick :) >> 2. Was there a concrete rationale for maintaining 520 bytes? 10k is the >> current >>script limit, can we get closer to that? :) > > But as others have said, 520 bytes is the existing stack element limit > and minimizing changes seems like a good strategy to get consensus. (On > the other hand, it's been a few days without any opposition so maybe we > should be more agressive :)). It's probably worth *thinking* about, yes. >> 3. Should we restrict elsewhere instead? After all, OP_CAT doesn't >>change total stack size, which is arguably the real limit? >> > > Interesting thought. Right now the stack size is limited to 1000 > elements of 520 bytes each, which theoretically means a limit of 520k. > Bitcoin Core doesn't explicitly count the "total stack size" in the > sense that you're suggesting; it just enforces these two limits > separately. BTW, I'm just learning of the 1000 element limit; I couldn't see it on scanning BIP-141. > I think trying to add a "total stack size limit" (which would have to > live alongside the two existing limits; we can't replace them without > a whole new Tapscript version) would add a fair bit of accounting > complextiy and wind up touching almost every other opcode...probably > not worth the added consensus logic. Simplest thing I can come up with: - instead of counting simple stack depth, count each stack entry as (1 + /520) entries? You can still only push 520 bytes, so you can only make these with OP_CAT. Looking in interpreter.cpp, `stack` and `altstack` now need to be objects to count entries differently (not vectors), but it seems like it'd be simple enough, and the logic could be enabled unconditionally since it Cannot Be Violated prior to OP_CAT. Cheers, Rusty. ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote: > Ethan Heilman via bitcoin-dev writes: > > 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 > > This is really nice to see! > > AFAICT you don't define the order of concatenation, except in the > implementation[1]. I think if A is top of stack, we get BA, not AB? > > 520 feels quite small for script templates (mainly because OP_CAT itself > makes Script more interesting!). For example, using OP_TXHASH and > OP_CAT to enforce that two input amounts are equal to one output amount > takes about 250 bytes of Script[2] :( > > So I have to ask: > > 1. Do other uses feel like 520 is too limiting? In my view, 520 feels limiting provided that we lack rolling sha2 opcodes. If we had those, then arguably 65 bytes is enough. Without them, I'm not sure that any value is "enough". For CHECKSIGFROMSTACK emulation purposes ideally we'd want the ability to construct a full transaction on the stack, which in principle would necessitate a 4M limit. > 2. Was there a concrete rationale for maintaining 520 bytes? 10k is the > current >script limit, can we get closer to that? :) But as others have said, 520 bytes is the existing stack element limit and minimizing changes seems like a good strategy to get consensus. (On the other hand, it's been a few days without any opposition so maybe we should be more agressive :)). > 3. Should we restrict elsewhere instead? After all, OP_CAT doesn't >change total stack size, which is arguably the real limit? > Interesting thought. Right now the stack size is limited to 1000 elements of 520 bytes each, which theoretically means a limit of 520k. Bitcoin Core doesn't explicitly count the "total stack size" in the sense that you're suggesting; it just enforces these two limits separately. I think trying to add a "total stack size limit" (which would have to live alongside the two existing limits; we can't replace them without a whole new Tapscript version) would add a fair bit of accounting complextiy and wind up touching almost every other opcode...probably not worth the added consensus logic. > Of course, we can increase this limit in future tapscript versions, too, > so it's not completely set in stone. > -- Andrew Poelstra Director of Research, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote:
> 2. Was there a concrete rationale for maintaining 520 bytes?
Without a limit of 520 bytes, then you can construct a script:
CHECKSIGVERIFY
{DUP CAT}x10
(we know have a string that is the second witness repeated 1024 times
on the stack; if it was 9 bytes, call it 9216B total)
{DUP} x 990
(we now have 1000 strings each of length 9216B bytes, for ~9.2MB total)
SHA256SUM {CAT SHA256SUM}x999
(we now have a single 32B field on the stack)
EQUAL
(and can do a hardcoded check to make sure there weren't any
shortcuts taken)
That raises the max memory to verify a single script from ~520kB (1000
stack elements by 520 bytes each) to ~10MB (1000 stack elements by
10kB each).
> 10k is the current script limit, can we get closer to that? :)
The 10k limit applies to scriptPubKey, scriptSig and segwit v0 scripts.
There's plenty of examples of larger tapscripts, eg:
https://mempool.space/tx/0301e0480b374b32851a9462db29dc19fe830a7f7d7a88b81612b9d42099c0ae
(3,938,182 bytes of script, non-standard due to being an oversized tx)
https://mempool.space/tx/2d4ad78073f1187c689c693bde62094abe6992193795f838e8be0db898800434
(360,543 bytes of script, standard, I believe)
Cheers,
aj
___
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
> I think if A is top of stack, we get BA, not AB? Good question. I always thought "0x01234567 0x89abcdef OP_CAT 0x0123456789abcdef OP_EQUAL" is correct, but it could be reversed as well. If we want to stay backward-compatible, we can dig into the past, and test the old implementation of OP_CAT, before it was disabled. But anyway, any of those two choices will lead to similar consequences. Because you can always turn the former into the latter by using "OP_SWAP OP_CAT", instead of "OP_CAT". > 520 feels quite small for script templates It will be easier to start with that, when it comes to reaching consensus for a new soft-fork. But yes, I am very surprised, because I thought we will never see things like that, and I assumed the path to OP_CAT is just permanently closed. So, I am surprised this BIP reached a positive reaction, but well, that kind of proposal was not battle-tested, so maybe it could succeed. > 10k is the current script limit, can we get closer to that? We will get there anyway. Even if OP_CAT would allow concatenating up to 520-bit Schnorr signature (not to confuse 520-bit with 520-byte), people would chain it, to reach arbitrary size. If you can concatenate secp256k1 public keys with signatures, you can create a chain of OP_CATs, that will handle arbitrary size. The only limitation is then blockchain speed, which is something around 4 MB/10 min, and that is your only limit in this case. And yes, if I can see that some people try to build logical gates like NAND with Bitcoin Script, then I guess all paths will be explored anyway. Which means, even if we will take more conservative approach, and switch from 520-byte proposal into 520-bit proposal, then still, people will do exactly the same things. Now, it is all about the cost of pushing data, because some people noticed, that everything can be executed on Script. I knew we will get there, but I expected it would just happen later than it happened. > Of course, we can increase this limit in future tapscript versions, too, so > it's not completely set in stone. Judging by the last misuse of Ordinals, I think it may happen before anyone will propose some official future version. Which means, nothing is really set in stone anymore, because now people know, how to activate new features, without any soft-fork, and some no-forks will probably be done by newbies, without careful designing and testing, as it is done here.___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
Ethan Heilman via bitcoin-dev writes: > 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 This is really nice to see! AFAICT you don't define the order of concatenation, except in the implementation[1]. I think if A is top of stack, we get BA, not AB? 520 feels quite small for script templates (mainly because OP_CAT itself makes Script more interesting!). For example, using OP_TXHASH and OP_CAT to enforce that two input amounts are equal to one output amount takes about 250 bytes of Script[2] :( So I have to ask: 1. Do other uses feel like 520 is too limiting? 2. Was there a concrete rationale for maintaining 520 bytes? 10k is the current script limit, can we get closer to that? :) 3. Should we restrict elsewhere instead? After all, OP_CAT doesn't change total stack size, which is arguably the real limit? Of course, we can increase this limit in future tapscript versions, too, so it's not completely set in stone. Thanks! Rusty. [1] Maybe others are Bitcoin Core fluent, but I found it weird that it's not simply `valtype vch1 = popstack(stack);`, and `vch3.reserve(vch1.size() + vch2.size());` was just a weird detail. [2] https://rusty.ozlabs.org/2023/10/22/amounts-in-script.html ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
> This opcode would be activated via a soft fork by redefining the opcode > OP_SUCCESS80. Why OP_SUCCESS80, and not OP_SUCCESS126? When there is some existing opcode, it should be reused. And if OP_RESERVED will ever be re-enabled, I think it should behave in the same way, as in pre-Taproot, so it should "Mark transaction as invalid unless occuring in an unexecuted OP_IF branch". Which means, " OP_VERIFY" should be equivalent to " OP_NOTIF OP_RESERVED OP_ENDIF". On 2023-10-21 07:09:13 user Ethan Heilman via bitcoin-dev 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 A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html OP_CAT is sufficent to build vaults in Bitcoin. * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 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 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); The value of MAX_SCRIPT_ELEMENT_SIZE is 520
Re: [bitcoin-dev] Proposed BIP for OP_CAT
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 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 A. Poelstra, "CAT >> and Schnorr Tricks II", 2021, >> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html >> >> OP_CAT is sufficent to build vaults in Bitcoin. >> * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr >> Tricks I", 2021, >> https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 >> 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
Re: [bitcoin-dev] Proposed BIP for OP_CAT
> 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 A. Poelstra, "CAT > and Schnorr Tricks II", 2021, > https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html > > OP_CAT is sufficent to build vaults in Bitcoin. > * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr > Tricks I", 2021, > https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 > 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 > > 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); >
Re: [bitcoin-dev] Proposed BIP for OP_CAT
On Sat, Oct 21, 2023 at 01:08:03AM -0400, Ethan Heilman via bitcoin-dev 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! This is really great, thank you for pushing forward and writing up the BIP text. In addition to the usecases listed in the text, I think CAT would open up a wide range of Bitcoin script research and let us test nontrivial things, in perhaps inefficient ways, in real life, befoer proposing dedicated opcodes. When spitballing about ways to do cool stuff with Bitcoin Script, I'd say about 90% of the time it ends with "we could do this if only we had CAT". And the remaining 10% usually don't need much more. As evidenced by the short text and short implementation code, CAT is very simple but provides a ton of value. There is a temptation to try to bundle other opcodes in with this (for example, rolling SHA256 opcodes to allow hashing more than 520 bytes of data) but I think: * There is no logical end to the list of opcodes we'd like to add, so this will invite an interminable amount of bikeshedding. * No single opcode comes close to the power of CAT (except super general-purpose opcodes like OP_ZKP_VERIFY :)) * Most everything is more controversial than we expect. You can find Matt's "consensus cleanup" BIP from a couple years ago which did 4 small things and I think that all 4 got a bunch of pushback. So I think we should stick with "just CAT" :). -- Andrew Poelstra Director of Research, Blockstream Email: apoelstra at wpsoftware.net Web: https://www.wpsoftware.net/andrew The sun is always shining in space -Justin Lewis-Webster signature.asc Description: PGP signature ___ bitcoin-dev mailing list bitcoin-dev@lists.linuxfoundation.org https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Re: [bitcoin-dev] Proposed BIP for OP_CAT
Hi Ethan, > [2]: P. Wuille, "Multisig on steroids using tree signatures", 2015, > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.html Correct link for "Multisig on steroids using tree signatures": https://blog.blockstream.com/en-treesignatures/ /dev/fd0 floppy disk guy Sent with Proton Mail secure email. --- Original Message --- On Saturday, October 21st, 2023 at 10:38 AM, Ethan Heilman via bitcoin-dev 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 A. Poelstra, "CAT > > and Schnorr Tricks II", 2021, > https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html > > OP_CAT is sufficent to build vaults in Bitcoin. > * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr > > Tricks I", 2021, > https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 > 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 > > > 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()); > >
[bitcoin-dev] Proposed BIP for OP_CAT
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 A. Poelstra, "CAT and Schnorr Tricks II", 2021, https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html OP_CAT is sufficent to build vaults in Bitcoin. * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr Tricks I", 2021, https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 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 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); 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,
