public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Ethan Heilman <eth3rs@gmail.com>
To: Greg Sanders <gsanders87@gmail.com>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Proposed BIP for OP_CAT
Date: Sat, 21 Oct 2023 16:24:29 -0400	[thread overview]
Message-ID: <CAEM=y+XLD2Vkuv1gzkeUj_zQJJqjz1UCKa4dwbA1WXSJBQZueQ@mail.gmail.com> (raw)
In-Reply-To: <CAB3F3DuV8SHc+fKVEpvWBBE0+=tqJX7pr0Xzhmtj=bQfKbx0eg@mail.gmail.com>

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

  reply	other threads:[~2023-10-21 20:25 UTC|newest]

Thread overview: 20+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
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
2023-10-21 20:24   ` Ethan Heilman [this message]
2023-10-22  8:58 ` vjudeu
2023-10-24 19:47   ` Steven Roose
2023-10-26  1:53     ` Ethan Heilman
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
2023-10-24  1:17       ` Andrew Poelstra
2023-10-24  3:45         ` Rusty Russell
2023-10-24 13:05           ` Andrew Poelstra
2023-10-26 21:55 ` Peter Todd
2023-10-27 18:32 ` Anthony Towns
2023-10-23  5:13 vjudeu
2023-10-26 14:30 ` Ryan Grant

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to='CAEM=y+XLD2Vkuv1gzkeUj_zQJJqjz1UCKa4dwbA1WXSJBQZueQ@mail.gmail.com' \
    --to=eth3rs@gmail.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=gsanders87@gmail.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox