Date: Sat, 21 Oct 2023 05:49:59 +0000
To: Ethan Heilman <eth3rs@gmail.com>
From: alicexbt <alicexbt@protonmail.com>
Message-ID: <FyACu9CRVXwjOFUA4w_4I884yIFerThlYDDiXYVKfBbAyF5H8DQP6ZzqbNpaMpDt9RZN2fQqaJfk20Zp-R660l6cQZ6l8ZdylTDI8X40H50=@protonmail.com>
In-Reply-To: <CAEM=y+XDB7GGa5BTAWrQHqTqQHBE2VRyd7VWjEb+zCOMzRP+Lg@mail.gmail.com>
References: <CAEM=y+XDB7GGa5BTAWrQHqTqQHBE2VRyd7VWjEb+zCOMzRP+Lg@mail.gmail.com>
Feedback-ID: 40602938:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Proposed BIP for OP_CAT
Precedence: list

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,
>=20
> 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
>=20
> 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.
>=20
> Thanks,
> Ethan
>=20
> =3D=3DAbstract=3D=3D
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> =3D=3DMotivation=3D=3D
> 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.
>=20
> 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:
>=20
> * 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
>=20
> and Schnorr Tricks II", 2021,
> https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html</re=
f>
>=20
> OP_CAT is sufficent to build vaults in Bitcoin.
> * Replicating CheckSigFromStack <ref> A. Poelstra, "CAT and Schnorr
>=20
> Tricks I", 2021,
> https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298
> </ref> which would allow the creation of simple covenants and other
>=20
> 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]
>=20
> 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.
>=20
> =3D=3DSpecification=3D=3D
>=20
> Implementation
> <pre>
>=20
> if (stack.size() < 2)
> return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
> valtype vch1 =3D stacktop(-2);
> valtype vch2 =3D stacktop(-1);
>=20
> if (vch1.size() + vch2.size() > MAX_SCRIPT_ELEMENT_SIZE)
>=20
> return set_error(serror, SCRIPT_ERR_INVALID_STACK_OPERATION);
>=20
> valtype vch3;
> vch3.reserve(vch1.size() + vch2.size());
> vch3.insert(vch3.end(), vch1.begin(), vch1.end());
> vch3.insert(vch3.end(), vch2.begin(), vch2.end());
>=20
> popstack(stack);
> popstack(stack);
> stack.push_back(vch3);
> </pre>
>=20
>=20
> The value of MAX_SCRIPT_ELEMENT_SIZE is 520 Bytes
>=20
> =3D=3D Reference Implementation =3D=3D
> Elements
>=20
> =3D=3DReferences=3D=3D
>=20
> [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=C3=B6der, "Liar, Liar, Coins on Fire:
> Penalizing Equivocation by Loss of Bitcoins", 2015,
> https://citeseerx.ist.psu.edu/viewdoc/download?doi=3D10.1.1.727.6262&rep=
=3Drep1&type=3Dpdf
> [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