Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id EA5302405 for ; Wed, 29 May 2019 06:49:43 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it1-f174.google.com (mail-it1-f174.google.com [209.85.166.174]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A28D889B for ; Wed, 29 May 2019 06:49:42 +0000 (UTC) Received: by mail-it1-f174.google.com with SMTP id a186so1939480itg.0 for ; Tue, 28 May 2019 23:49:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream.io; s=google; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=7MjhUAUYB8OuS7baIRjXuILgDPEcbdmo0l+wshRLjy0=; b=lPZ3IX7I1yGOrN+asAoOaS6JG7MsO0S6ByauLGl4eRunIX6szDKRGwhekj8BUn7f10 m19f/N9thUevbECkeZ/MaR/gVq2Tm89RykSHs9aOZboKBj3v+8zHxO0cD/WjYHspsS/B STJ3NOmgSzMNQYA2Dh1v/v1mfwekHU+/Z8h7A= X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=7MjhUAUYB8OuS7baIRjXuILgDPEcbdmo0l+wshRLjy0=; b=gTPqFL3x7GbUaIvABd3Ta7bjNR7T8gj7ryG3adXtgfBC/7lJm/QcFDaSrAoIFE+P+l 5VIf+WRkupvkXdBD6xWp1pGpDpyCH0+7tGmmW5YABVKsB7A7a9iWL589QW8CUegMsBHr R4PiFE+rNZcir/3LH4QKdhOGMzWHcpbOGUn0QWJmQYzjdIe+b4EEdI4jTUkISDzDGPux iSMbVIiMxPj7IcnJRYFTx6mF5HD9jyDONh79Rtkpf2oZUyetkE7AsSX8aUMU56Pofd1A CoVrS2MTgdkj8OwL1ziELAxFSIsaioOE8fYd89PKIsLOZsEYbHGPkZw9YRqMTtMyVJpm 76pg== X-Gm-Message-State: APjAAAXhZFTmbdbccXwJcP2C7R3PVKxtMRpZnskjrm+8po+SmVQxBBN9 ARQUtYE1FPLoLNehPKJqH/LPiFPN4zqrPuZCMYVFaSHiEm9g5g== X-Google-Smtp-Source: APXvYqz24sLX5Fq0y1AYkmlA1BubZPovM3Ato4VBcY8Uxa7iYU/V3g2OzisgrHY8o6al/ftbvKywgvxKCcOGczLFqQs= X-Received: by 2002:a24:64d:: with SMTP id 74mr5813692itv.170.1559112581658; Tue, 28 May 2019 23:49:41 -0700 (PDT) MIME-Version: 1.0 References: <20190527072128.lbzeo6h23qgxvhsy@erisian.com.au> In-Reply-To: <20190527072128.lbzeo6h23qgxvhsy@erisian.com.au> From: "Russell O'Connor" Date: Wed, 29 May 2019 02:49:29 -0400 Message-ID: To: Anthony Towns Content-Type: multipart/alternative; boundary="00000000000098513d058a012f9f" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Thu, 30 May 2019 16:35:33 +0000 Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] An alternative: OP_CAT & OP_CHECKSIGFROMSTACK X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 29 May 2019 06:49:44 -0000 --00000000000098513d058a012f9f Content-Type: text/plain; charset="UTF-8" On Mon, May 27, 2019 at 3:21 AM Anthony Towns wrote: > On Wed, May 22, 2019 at 05:01:21PM -0400, Russell O'Connor via bitcoin-dev > wrote: > > Bitcoin Script appears designed to be a flexible programmable system that > > provides generic features to be composed to achieve various purposes. > > Counterpoint: haven't the flexibly designed parts of script mostly been > a failure -- requiring opcodes to be disabled due to DoS vectors or > consensus bugs, and mostly not being useful in practice where they're > still enabled in BTC or on other chains where they have been re-enabled > (eg, Liquid and BCH)? > You may have a point. However, I'm still inclined to think that problem is that you want some subset of concatenation, arithmetic, CHECKDATASIG, transaction reflection and/or covenants in order to create particularly useful programs. A while ago, I was designing a moderately sophisticated Script for Elements Alpha to see if I could implement a toy game, but ultimately I was thwarted due to the fact that Elements Alpha didn't support multiplication. I did briefly consider using repeated additions and nested if statements to implement multiplication since I was expecting my numbers to be 11 or less, but ultimately I decided to just continue my work on an alternative to Script rather than trying to work around the missing multiplication. > > Instead, I propose that, for the time being, we simply implement OP_CAT > and > > OP_CHECKSIGFROMSTACKVERIFY. > > FWIW, I'd like to see CAT enabled, though I'm less convinced about a > CHECKSIG that takes the message from the stack. I think CAT's plausibly > useful in practice, but a sig against data from the stack seems more > useful in theory than in practice. Has it actually seen use on BCH or > Liquid, eg? (Also, I think BCH's name for that opcode makes more sense > than Elements' -- all the CHECKSIG opcodes pull a sig from the stack, > after all) > > > * Transaction introspection including: > > + Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned simply > by the > > nature of the construction. > > I think simulating an ANYPREVOUT sig with a data signature means checking: > > S1 P CHECKSIG -- to check S1 is a signature for the tx > > S1 H_TapSighash(XAB) P CHECKDATASIG > -- to pull out the tx data "X", "A", "B") > > S2 H_TapSighash(XCB) Q CHECKDATASIG > -- for the ANYPREVOUT sig, with A changed to C to > avoid committing to prevout info > > X SIZE 42 EQUALVERIFY > B SIZE 47 EQUALVERIFY > -- to make sure only C is replaced from "XCB" > > So to get all those conditions checked, I think you could do: > > P 2DUP TOALT TOALT CHECKSIGVERIFY > SIZE 42 EQUALVERIFY > "TapSighash" SHA256 DUP CAT SWAP CAT TOALT > SIZE 47 EQUALVERIFY TUCK > CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT > CHECKDATASIGVERIFY > SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG > > Where the stack elements are, from top to bottom: > > S1: (65B) signature by P of tx > X: (42B) start of TapSighash spec > B: (47B) end of TapSighash spec (amount, nSequence, tapleaf_hash, > key_version, codesep_pos) > A: (73B) middle of TapSighash spec dropped for ANYPREVOUT (spend_type, > scriptPubKey and outpoint) > C: (1B) alternate middle (different spend_type) > S2: (64B) signature of "XCB" by key Q > > So 298B for the witness data, and 119B or so for the script (if I've not > made mistakes), versus "P CHECKSIGVERIFY Q CHECKSIG" and S2 and S1 on > the stack, for 132B of witness data and 70B of script, or half that if > the chaperone requirement is removed. > I haven't checked your details but the above looks about correct to me. So what I was thinking is that we could add CHECKDATASIG first, and then people could get started on actually using ANYPREVOUT in practice and we can take our time to debate the merits of the chaperone vs non-chaperone, and possibly learn something about actual use before making a decision. There is no doubt that using ANYPREVOUT directly uses less weight, but they seem close enough to that it the simulation is usable, though perhaps far enough apart that we would want to eventually add ANYPREVOUT. However, do keep in mind that our goal is not to minimize the weight of specific redemption policies. The weight of implementing any particular redemption policy in Script is somewhat arbitrary to begin with anyways, being dependent on the choices made for the Script language operations and its encoding. Again, if our goal were to minimize weight for specific redemption policies we should abandon SCRIPT and directly use a language similar to Miniscript, and/or just directly implement an enumeration of policies. However, my proposal CHECKSIGFROMSTACK (aka CHECKDATASIG) proposal was based on my argument that CHECKDATASIG covenant abilities wouldn't be controversial since it was limited to self-recursion and had less than 64-bits of state space. But ZmnSCPxj has shown that my conclusions were hasty and that self-recursion has access to arbitrarily large amounts of state space. In light of this, it would appear that self-recursive covenants is nearly as powerful as arbitrary recursive covenants, and therefore is nearly as controversial. So, while I do think that we should add support for recursive covenants to Bitcoin, we probably not ready to add it yet given the controversy around the far more innocent ANYPREVOUT. I do think it would be useful to add support for CAT and CHECKDATASIG in order to implement MPC with penalties, but perhaps we should support that via a HASH_tapdata digest function rather than SHA256, in order to avoid any accidental covenants. Of course doing so would no longer count as "an alternative" proposal to ANYPREVOUT or COSHV, and simply "an additional" proposal. > I think you'd need to complicate it a bit further to do the > ANYPREVOUTANYSCRIPT variant, where you retain the commitment to > amount/nseq but drop the commitment to tapleaf_hash. > > > I feel that this style of generic building blocks truly embodies what is > meant > > by "programmable money". > > For practical purposes, this doesn't seem like a great level of > abstraction to me. It's certainly better at "permissionless innovation" > though. > > You could make these constructions a little bit simpler by having a > "CHECK_SIG_MSG_VERIFY" opcode that accepts [sig msg key], and does "sig > key CHECKSIGVERIFY" but also checks the the provided msg was what was > passed into bip-schnorr. > The whole point is to keep the functionality simple and let users program what they want. What we don't want to do is tailor an opcode for the specific use case we have in mind, because that just comes at the expense of all the use cases we don't have in mind. --00000000000098513d058a012f9f Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
On Mon, May 27, 2019 at 3:21 AM Anthony Towns <aj@erisian.com.au> wrote:
On Wed, May 22, 2019 at 05:01:21PM -040= 0, Russell O'Connor via bitcoin-dev wrote:
> Bitcoin Script appears designed to be a flexible programmable system t= hat
> provides generic features to be composed to achieve various purposes.<= br>
Counterpoint: haven't the flexibly designed parts of script mostly been=
a failure -- requiring opcodes to be disabled due to DoS vectors or
consensus bugs, and mostly not being useful in practice where they're still enabled in BTC or on other chains where they have been re-enabled
(eg, Liquid and BCH)?

You may have a po= int.=C2=A0 However, I'm still inclined to think that problem is that yo= u want some subset of concatenation, arithmetic, CHECKDATASIG, transaction = reflection and/or covenants in order to create particularly useful programs= .

A while ago, I was designing a moderately so= phisticated Script for Elements Alpha to see if I could implement a toy gam= e, but ultimately I was thwarted due to the fact that Elements Alpha didn&#= 39;t support multiplication.
I did briefly consider using repeate= d additions and nested if statements to implement multiplication since I wa= s expecting my numbers to be 11 or less, but ultimately I decided to just c= ontinue my work on an alternative to Script rather than trying to work arou= nd the missing multiplication.
=C2=A0
> Instead, I propose that, for the time being, we simply implement OP_CA= T and
> OP_CHECKSIGFROMSTACKVERIFY.

FWIW, I'd like to see CAT enabled, though I'm less convinced about = a
CHECKSIG that takes the message from the stack. I think CAT's plausibly=
useful in practice, but a sig against data from the stack seems more
useful in theory than in practice. Has it actually seen use on BCH or
Liquid, eg?=C2=A0 (Also, I think BCH's name for that opcode makes more = sense
than Elements' -- all the CHECKSIG opcodes pull a sig from the stack, after all)

> * Transaction introspection including:
> +=C2=A0Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned = simply by the
> nature of the construction.

I think simulating an ANYPREVOUT sig with a data signature means checking:<= br>
=C2=A0 =C2=A0 S1 P CHECKSIG -- to check S1 is a signature for the tx

=C2=A0 =C2=A0 S1 H_TapSighash(XAB) P CHECKDATASIG
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- to pull out the tx data "X",= "A", "B")

=C2=A0 =C2=A0 S2 H_TapSighash(XCB) Q CHECKDATASIG
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- for the ANYPREVOUT sig, with A changed= to C to
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 avoid committing to prevout info<= br>
=C2=A0 =C2=A0 X SIZE 42 EQUALVERIFY
=C2=A0 =C2=A0 B SIZE 47 EQUALVERIFY
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- to make sure only C is replaced from &= quot;XCB"

So to get all those conditions checked, I think you could do:

=C2=A0 =C2=A0P 2DUP TOALT TOALT CHECKSIGVERIFY
=C2=A0 =C2=A0SIZE 42 EQUALVERIFY
=C2=A0 =C2=A0"TapSighash" SHA256 DUP CAT SWAP CAT TOALT
=C2=A0 =C2=A0SIZE 47 EQUALVERIFY TUCK
=C2=A0 =C2=A0CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT
=C2=A0 =C2=A0CHECKDATASIGVERIFY
=C2=A0 =C2=A0SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG

Where the stack elements are, from top to bottom:

=C2=A0 =C2=A0S1: (65B) signature by P of tx
=C2=A0 =C2=A0X:=C2=A0 (42B) start of TapSighash spec
=C2=A0 =C2=A0B:=C2=A0 (47B) end of TapSighash spec (amount, nSequence, tapl= eaf_hash,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0key_version, codesep_pos) =C2=A0 =C2=A0A:=C2=A0 (73B) middle of TapSighash spec dropped for ANYPREVOU= T (spend_type,
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0scriptPubKey and outpoint)<= br> =C2=A0 =C2=A0C:=C2=A0 =C2=A0(1B) alternate middle (different spend_type) =C2=A0 =C2=A0S2: (64B) signature of "XCB" by key Q

So 298B for the witness data, and 119B or so for the script (if I've no= t
made mistakes), versus "P CHECKSIGVERIFY Q CHECKSIG" and S2 and S= 1 on
the stack, for 132B of witness data and 70B of script, or half that if
the chaperone requirement is removed.

I= haven't checked your details but the above looks about correct to me.<= /div>

So what I was thinking is that we could add CHECKD= ATASIG first, and then people could get started on actually using ANYPREVOU= T in practice and we can take our time to debate the merits of the chaperon= e vs non-chaperone, and possibly learn something about actual use before ma= king a decision.=C2=A0 There is no doubt that using ANYPREVOUT directly use= s less weight, but they seem close enough to that it the simulation is usab= le, though perhaps far enough apart that we would want to eventually add AN= YPREVOUT.=C2=A0 However, do keep in mind that our goal is not to minimize t= he weight of specific redemption policies.=C2=A0 The weight of implementing= any particular redemption policy in Script is somewhat arbitrary to begin = with anyways, being dependent on the choices made for the Script language o= perations and its encoding.=C2=A0 Again, if our goal were to minimize weigh= t for specific redemption policies we should abandon SCRIPT and directly us= e a language similar to Miniscript, and/or just directly implement an enume= ration of policies.

However, my proposal CHECKSIGF= ROMSTACK (aka CHECKDATASIG) proposal was based on my argument that CHECKDAT= ASIG covenant abilities wouldn't be controversial since it was limited = to self-recursion and had less than 64-bits of state space.=C2=A0 But ZmnSC= Pxj has shown that my conclusions were hasty and that self-recursion has ac= cess to arbitrarily large amounts of state space.=C2=A0 In light of this, i= t would appear that self-recursive covenants is nearly as powerful as arbit= rary recursive covenants, and therefore is nearly as controversial.

So, while I do think that we should add support for recur= sive covenants to Bitcoin, we probably not ready to add it yet given the co= ntroversy around the far more innocent ANYPREVOUT.=C2=A0 I do think it woul= d be useful to add support for CAT and CHECKDATASIG in order to implement M= PC with penalties, but perhaps we should support that via a HASH_tapdata di= gest function rather than SHA256, in order to avoid any accidental covenant= s.=C2=A0 Of course doing so would no longer count as "an alternative&q= uot; proposal to ANYPREVOUT or COSHV, and simply "an additional" = proposal.
=C2=A0
I think you'd need to complicate it a bit further to do the
ANYPREVOUTANYSCRIPT variant, where you retain the commitment to
amount/nseq but drop the commitment to tapleaf_hash.

> I feel that this style of generic building blocks truly embodies what = is meant
> by "programmable money".

For practical purposes, this doesn't seem like a great level of
abstraction to me. It's certainly better at "permissionless innova= tion"
though.

You could make these constructions a little bit simpler by having a
"CHECK_SIG_MSG_VERIFY" opcode that accepts [sig msg key], and doe= s "sig
key CHECKSIGVERIFY" but also checks the the provided msg was what was<= br> passed into bip-schnorr.

The whole poin= t is to keep the functionality simple and let users program what they want.= =C2=A0 What we don't want to do is tailor an opcode for the specific us= e case we have in mind, because that just comes at the expense of all the u= se cases we don't have in mind.
--00000000000098513d058a012f9f--