[bitcoin-dev] Proposed BIP for OP_CAT

[bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[alicexbt]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Andrew Poelstra]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Greg Sanders]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[vjudeu]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Rusty Russell]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Anthony Towns]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Andrew Poelstra]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Rusty Russell]

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.

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Andrew Poelstra]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Rusty Russell]

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);
         }
     }

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Andrew Poelstra]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Steven Roose]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Ethan Heilman]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[James O'Beirne]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Peter Todd]

[-- 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 --]

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Anthony Towns]

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

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[Ryan Grant]

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.

Re: [bitcoin-dev] Proposed BIP for OP_CAT

[vjudeu]

[-- Attachment #1: Type: text/plain, Size: 2459 bytes --]

> 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.

[-- Attachment #2: Type: text/html, Size: 2707 bytes --]