From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id AA7BEC0032 for ; Sat, 21 Oct 2023 05:50:19 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 7FE92404EF for ; Sat, 21 Oct 2023 05:50:19 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 7FE92404EF Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com header.a=rsa-sha256 header.s=protonmail3 header.b=jpdp1Xqa X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URI_DOTEDU=0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5H-1waB4uWY1 for ; Sat, 21 Oct 2023 05:50:14 +0000 (UTC) Received: from mail-0201.mail-europe.com (mail-0201.mail-europe.com [51.77.79.158]) by smtp4.osuosl.org (Postfix) with ESMTPS id C250F4048F for ; Sat, 21 Oct 2023 05:50:13 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org C250F4048F DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com; s=protonmail3; t=1697867406; x=1698126606; bh=NHdStIMcZM4HZE9RkCjEFuc9v11AAx4l7QFnl7ty1qw=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=jpdp1XqaYo4LaDThFKP+oeWIc02hqAghl4diWyunGEJzL7PSN+CHN7lIdlwBy1cdn olhACEbZPg2JUfpXOpotZglaeDHiI97gpKcw3TXx427V6v4r3AcGk5oDIPdncJel2C h3GmyyKC1a2iPIJXrlUef7T1NG2k8kFsgoOsbzXr4WKpH2Zdwp5V9Mf/2egS+Usll/ MYbFxu4Kb3L6uPpmb7qpVjVLZFb6KoYgX14NcV4/KXjtKKugP6HGjPJ1wgsEe37scQ 5/pbSnzvGDqJpszR1rabyBDd4vdUreiRnGxtH6rOorgIym0TVvqGEUgnWNpGvTOPDD 4PS29jPjqU0ew== Date: Sat, 21 Oct 2023 05:49:59 +0000 To: Ethan Heilman From: alicexbt Message-ID: In-Reply-To: References: Feedback-ID: 40602938:user:proton MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Mailman-Approved-At: Sat, 21 Oct 2023 12:04:52 +0000 Cc: Bitcoin Dev Subject: Re: [bitcoin-dev] Proposed BIP for OP_CAT X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 21 Oct 2023 05:50:19 -0000 Hi Ethan, > [2]: P. Wuille, "Multisig on steroids using tree signatures", 2015, > https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2021-July/019233.= html Correct link for "Multisig on steroids using tree signatures": https://blog= .blockstream.com/en-treesignatures/ /dev/fd0 floppy disk guy Sent with Proton Mail secure email. ------- Original Message ------- On Saturday, October 21st, 2023 at 10:38 AM, Ethan Heilman via bitcoin-dev = wrote: > Hi everyone, >=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 A. Poelstra, "CAT >=20 > and Schnorr Tricks II", 2021, > https://www.wpsoftware.net/andrew/blog/cat-and-schnorr-tricks-ii.html >=20 > OP_CAT is sufficent to build vaults in Bitcoin. > * Replicating CheckSigFromStack A. Poelstra, "CAT and Schnorr >=20 > Tricks I", 2021, > https://medium.com/blockstream/cat-and-schnorr-tricks-i-faf1b59bd298 > 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 > 
>=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);
>
>=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