* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
@ 2023-10-21 5:49 ` alicexbt
2023-10-21 15:03 ` Andrew Poelstra
` (5 subsequent siblings)
6 siblings, 0 replies; 20+ messages in thread
From: alicexbt @ 2023-10-21 5:49 UTC (permalink / raw)
To: Ethan Heilman; +Cc: Bitcoin Dev
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 <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
>
> ==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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
2023-10-21 5:49 ` alicexbt
@ 2023-10-21 15:03 ` Andrew Poelstra
2023-10-26 16:04 ` James O'Beirne
2023-10-21 16:10 ` Greg Sanders
` (4 subsequent siblings)
6 siblings, 1 reply; 20+ messages in thread
From: Andrew Poelstra @ 2023-10-21 15:03 UTC (permalink / raw)
To: Ethan Heilman, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 2101 bytes --]
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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 15:03 ` Andrew Poelstra
@ 2023-10-26 16:04 ` James O'Beirne
0 siblings, 0 replies; 20+ messages in thread
From: James O'Beirne @ 2023-10-26 16:04 UTC (permalink / raw)
To: Andrew Poelstra, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1461 bytes --]
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?
[-- Attachment #2: Type: text/html, Size: 1935 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
2023-10-21 5:49 ` alicexbt
2023-10-21 15:03 ` Andrew Poelstra
@ 2023-10-21 16:10 ` Greg Sanders
2023-10-21 20:24 ` Ethan Heilman
2023-10-22 8:58 ` vjudeu
` (3 subsequent siblings)
6 siblings, 1 reply; 20+ messages in thread
From: Greg Sanders @ 2023-10-21 16:10 UTC (permalink / raw)
To: Ethan Heilman, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 6602 bytes --]
> 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
>
[-- Attachment #2: Type: text/html, Size: 8722 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 16:10 ` Greg Sanders
@ 2023-10-21 20:24 ` Ethan Heilman
0 siblings, 0 replies; 20+ messages in thread
From: Ethan Heilman @ 2023-10-21 20:24 UTC (permalink / raw)
To: Greg Sanders; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 7586 bytes --]
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 <gsanders87@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
>>
>
[-- Attachment #2: Type: text/html, Size: 9880 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
` (2 preceding siblings ...)
2023-10-21 16:10 ` Greg Sanders
@ 2023-10-22 8:58 ` vjudeu
2023-10-24 19:47 ` Steven Roose
2023-10-23 2:13 ` Rusty Russell
` (2 subsequent siblings)
6 siblings, 1 reply; 20+ messages in thread
From: vjudeu @ 2023-10-22 8:58 UTC (permalink / raw)
To: Ethan Heilman <eth3rs@gmail•com>,
Bitcoin Protocol Discussion, Bitcoin Dev
[-- Attachment #1: Type: text/plain, Size: 6256 bytes --]
> 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, "<condition> OP_VERIFY" should be equivalent to "<condition> OP_NOTIF OP_RESERVED OP_ENDIF".
On 2023-10-21 07:09:13 user 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); 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, 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
[-- Attachment #2: Type: text/html, Size: 6694 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-22 8:58 ` vjudeu
@ 2023-10-24 19:47 ` Steven Roose
2023-10-26 1:53 ` Ethan Heilman
0 siblings, 1 reply; 20+ messages in thread
From: Steven Roose @ 2023-10-24 19:47 UTC (permalink / raw)
To: vjudeu via bitcoin-dev
[-- Attachment #1: Type: text/plain, Size: 7441 bytes --]
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, "<condition> OP_VERIFY"
> should be equivalent to "<condition> OP_NOTIF OP_RESERVED OP_ENDIF".
>
>
> On 2023-10-21 07:09:13 user 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);
> 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,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 listbitcoin-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
[-- Attachment #2: Type: text/html, Size: 9532 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-24 19:47 ` Steven Roose
@ 2023-10-26 1:53 ` Ethan Heilman
0 siblings, 0 replies; 20+ messages in thread
From: Ethan Heilman @ 2023-10-26 1:53 UTC (permalink / raw)
To: Steven Roose, Bitcoin Protocol Discussion
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
<bitcoin-dev@lists•linuxfoundation.org> 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, "<condition> OP_VERIFY" should be equivalent to "<condition> OP_NOTIF OP_RESERVED OP_ENDIF".
>
>
>
> On 2023-10-21 07:09:13 user 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);
> 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, 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
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists•linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
` (3 preceding siblings ...)
2023-10-22 8:58 ` vjudeu
@ 2023-10-23 2:13 ` Rusty Russell
2023-10-23 12:26 ` Anthony Towns
2023-10-23 13:41 ` Andrew Poelstra
2023-10-26 21:55 ` Peter Todd
2023-10-27 18:32 ` Anthony Towns
6 siblings, 2 replies; 20+ messages in thread
From: Rusty Russell @ 2023-10-23 2:13 UTC (permalink / raw)
To: Ethan Heilman, Bitcoin Protocol Discussion, Bitcoin Dev
Ethan Heilman via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> 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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-23 2:13 ` Rusty Russell
@ 2023-10-23 12:26 ` Anthony Towns
2023-10-23 13:41 ` Andrew Poelstra
1 sibling, 0 replies; 20+ messages in thread
From: Anthony Towns @ 2023-10-23 12:26 UTC (permalink / raw)
To: Rusty Russell, Bitcoin Protocol Discussion
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:
<p> 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)
<h> 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
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-23 2:13 ` Rusty Russell
2023-10-23 12:26 ` Anthony Towns
@ 2023-10-23 13:41 ` Andrew Poelstra
2023-10-24 0:48 ` Rusty Russell
1 sibling, 1 reply; 20+ messages in thread
From: Andrew Poelstra @ 2023-10-23 13:41 UTC (permalink / raw)
To: Rusty Russell, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 2678 bytes --]
On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote:
> Ethan Heilman via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> 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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-23 13:41 ` Andrew Poelstra
@ 2023-10-24 0:48 ` Rusty Russell
2023-10-24 1:17 ` Andrew Poelstra
0 siblings, 1 reply; 20+ messages in thread
From: Rusty Russell @ 2023-10-24 0:48 UTC (permalink / raw)
To: Andrew Poelstra, Bitcoin Protocol Discussion
Andrew Poelstra <apoelstra@wpsoftware•net> writes:
> On Mon, Oct 23, 2023 at 12:43:10PM +1030, Rusty Russell via bitcoin-dev wrote:
>> Ethan Heilman via bitcoin-dev <bitcoin-dev@lists•linuxfoundation.org> 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 + <size>/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.
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-24 0:48 ` Rusty Russell
@ 2023-10-24 1:17 ` Andrew Poelstra
2023-10-24 3:45 ` Rusty Russell
0 siblings, 1 reply; 20+ messages in thread
From: Andrew Poelstra @ 2023-10-24 1:17 UTC (permalink / raw)
To: Rusty Russell; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 2004 bytes --]
On Tue, Oct 24, 2023 at 11:18:24AM +1030, Rusty Russell wrote:
> Andrew Poelstra <apoelstra@wpsoftware•net> 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 + <size>/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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-24 1:17 ` Andrew Poelstra
@ 2023-10-24 3:45 ` Rusty Russell
2023-10-24 13:05 ` Andrew Poelstra
0 siblings, 1 reply; 20+ messages in thread
From: Rusty Russell @ 2023-10-24 3:45 UTC (permalink / raw)
To: Andrew Poelstra; +Cc: Bitcoin Protocol Discussion
Andrew Poelstra <apoelstra@wpsoftware•net> 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<std::vector<unsigned char> >& 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<std::vector<unsigned char> >& 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<std::vector<unsigned char> >& 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);
}
}
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-24 3:45 ` Rusty Russell
@ 2023-10-24 13:05 ` Andrew Poelstra
0 siblings, 0 replies; 20+ messages in thread
From: Andrew Poelstra @ 2023-10-24 13:05 UTC (permalink / raw)
To: Rusty Russell; +Cc: Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 1129 bytes --]
On Tue, Oct 24, 2023 at 02:15:49PM +1030, Rusty Russell wrote:
> Andrew Poelstra <apoelstra@wpsoftware•net> 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
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 488 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread
* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
` (4 preceding siblings ...)
2023-10-23 2:13 ` Rusty Russell
@ 2023-10-26 21:55 ` Peter Todd
2023-10-27 18:32 ` Anthony Towns
6 siblings, 0 replies; 20+ messages in thread
From: Peter Todd @ 2023-10-26 21:55 UTC (permalink / raw)
To: Ethan Heilman, Bitcoin Protocol Discussion
[-- Attachment #1: Type: text/plain, Size: 731 bytes --]
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 <n> LESSTHAN VERIFY
<fixed data>
CAT
--
https://petertodd.org 'peter'[:-1]@petertodd.org
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 20+ messages in thread* Re: [bitcoin-dev] Proposed BIP for OP_CAT
2023-10-21 5:08 [bitcoin-dev] Proposed BIP for OP_CAT Ethan Heilman
` (5 preceding siblings ...)
2023-10-26 21:55 ` Peter Todd
@ 2023-10-27 18:32 ` Anthony Towns
6 siblings, 0 replies; 20+ messages in thread
From: Anthony Towns @ 2023-10-27 18:32 UTC (permalink / raw)
To: Ethan Heilman, Bitcoin Protocol Discussion
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
^ permalink raw reply [flat|nested] 20+ messages in thread