path: root/bf/ae328f8447889d62d8eb3da5b2e9a54e1f5494

Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id EA5302405
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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 <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 29 May 2019 06:49:42 +0000 (UTC)
Received: by mail-it1-f174.google.com with SMTP id a186so1939480itg.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	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: <CAMZUoK=0YhqxguphmaKsMGZCy_NYVE_i53qGBfPVES=GAYTy1g@mail.gmail.com>
	<20190527072128.lbzeo6h23qgxvhsy@erisian.com.au>
In-Reply-To: <20190527072128.lbzeo6h23qgxvhsy@erisian.com.au>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Wed, 29 May 2019 02:49:29 -0400
Message-ID: <CAMZUoKk3XFsFsQ_UybxQn1NiKWFak4cWLmk7WQyoncVK3Y7S6w@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>
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 <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
	<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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 <aj@erisian.com.au> 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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail=
_attr">On Mon, May 27, 2019 at 3:21 AM Anthony Towns &lt;<a href=3D"mailto:=
aj@erisian.com.au">aj@erisian.com.au</a>&gt; wrote:<br></div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid=
 rgb(204,204,204);padding-left:1ex">On Wed, May 22, 2019 at 05:01:21PM -040=
0, Russell O&#39;Connor via bitcoin-dev wrote:<br>
&gt; Bitcoin Script appears designed to be a flexible programmable system t=
hat<br>
&gt; provides generic features to be composed to achieve various purposes.<=
br>
<br>
Counterpoint: haven&#39;t the flexibly designed parts of script mostly been=
<br>
a failure -- requiring opcodes to be disabled due to DoS vectors or<br>
consensus bugs, and mostly not being useful in practice where they&#39;re<b=
r>
still enabled in BTC or on other chains where they have been re-enabled<br>
(eg, Liquid and BCH)?<br></blockquote><div><br></div><div>You may have a po=
int.=C2=A0 However, I&#39;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=
.<br></div><div><br></div><div>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.</div><div>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.<br></div><div>=C2=A0<br></div><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid=
 rgb(204,204,204);padding-left:1ex">
&gt; Instead, I propose that, for the time being, we simply implement OP_CA=
T and<br>
&gt; OP_CHECKSIGFROMSTACKVERIFY.<br>
<br>
FWIW, I&#39;d like to see CAT enabled, though I&#39;m less convinced about =
a<br>
CHECKSIG that takes the message from the stack. I think CAT&#39;s plausibly=
<br>
useful in practice, but a sig against data from the stack seems more<br>
useful in theory than in practice. Has it actually seen use on BCH or<br>
Liquid, eg?=C2=A0 (Also, I think BCH&#39;s name for that opcode makes more =
sense<br>
than Elements&#39; -- all the CHECKSIG opcodes pull a sig from the stack,<b=
r>
after all)<br>
<br>
&gt; * Transaction introspection including:<br>
&gt; +=C2=A0Simulated SIGHASH_ANYPREVOUT, which are necessarily chaperoned =
simply by the<br>
&gt; nature of the construction.<br>
<br>
I think simulating an ANYPREVOUT sig with a data signature means checking:<=
br>
<br>
=C2=A0 =C2=A0 S1 P CHECKSIG -- to check S1 is a signature for the tx<br>
<br>
=C2=A0 =C2=A0 S1 H_TapSighash(XAB) P CHECKDATASIG<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- to pull out the tx data &quot;X&quot;,=
 &quot;A&quot;, &quot;B&quot;)<br>
<br>
=C2=A0 =C2=A0 S2 H_TapSighash(XCB) Q CHECKDATASIG<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- for the ANYPREVOUT sig, with A changed=
 to C to<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 avoid committing to prevout info<=
br>
<br>
=C2=A0 =C2=A0 X SIZE 42 EQUALVERIFY<br>
=C2=A0 =C2=A0 B SIZE 47 EQUALVERIFY<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-- to make sure only C is replaced from &=
quot;XCB&quot;<br>
<br>
So to get all those conditions checked, I think you could do:<br>
<br>
=C2=A0 =C2=A0P 2DUP TOALT TOALT CHECKSIGVERIFY<br>
=C2=A0 =C2=A0SIZE 42 EQUALVERIFY<br>
=C2=A0 =C2=A0&quot;TapSighash&quot; SHA256 DUP CAT SWAP CAT TOALT<br>
=C2=A0 =C2=A0SIZE 47 EQUALVERIFY TUCK<br>
=C2=A0 =C2=A0CAT FROMALT TUCK SWAP CAT SHA256 FROMALT SWAP FROMALT<br>
=C2=A0 =C2=A0CHECKDATASIGVERIFY<br>
=C2=A0 =C2=A0SWAP TOALT SWAP CAT FROMALT CAT SHA256 Q CHECKDATASIG<br>
<br>
Where the stack elements are, from top to bottom:<br>
<br>
=C2=A0 =C2=A0S1: (65B) signature by P of tx<br>
=C2=A0 =C2=A0X:=C2=A0 (42B) start of TapSighash spec<br>
=C2=A0 =C2=A0B:=C2=A0 (47B) end of TapSighash spec (amount, nSequence, tapl=
eaf_hash,<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0key_version, codesep_pos)<b=
r>
=C2=A0 =C2=A0A:=C2=A0 (73B) middle of TapSighash spec dropped for ANYPREVOU=
T (spend_type,<br>
=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)<br=
>
=C2=A0 =C2=A0S2: (64B) signature of &quot;XCB&quot; by key Q<br>
<br>
So 298B for the witness data, and 119B or so for the script (if I&#39;ve no=
t<br>
made mistakes), versus &quot;P CHECKSIGVERIFY Q CHECKSIG&quot; and S2 and S=
1 on<br>
the stack, for 132B of witness data and 70B of script, or half that if<br>
the chaperone requirement is removed.<br></blockquote><div><br></div><div>I=
 haven&#39;t checked your details but the above looks about correct to me.<=
/div><div><br></div><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.</div><div><br></div><div>However, my proposal CHECKSIGF=
ROMSTACK (aka CHECKDATASIG) proposal was based on my argument that CHECKDAT=
ASIG covenant abilities wouldn&#39;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.</div><d=
iv><br></div><div>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 &quot;an alternative&q=
uot; proposal to ANYPREVOUT or COSHV, and simply &quot;an additional&quot; =
proposal.<br></div><div>=C2=A0</div><blockquote class=3D"gmail_quote" style=
=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding=
-left:1ex">
I think you&#39;d need to complicate it a bit further to do the<br>
ANYPREVOUTANYSCRIPT variant, where you retain the commitment to<br>
amount/nseq but drop the commitment to tapleaf_hash.<br>
<br>
&gt; I feel that this style of generic building blocks truly embodies what =
is meant<br>
&gt; by &quot;programmable money&quot;.<br>
<br>
For practical purposes, this doesn&#39;t seem like a great level of<br>
abstraction to me. It&#39;s certainly better at &quot;permissionless innova=
tion&quot;<br>
though.<br>
<br>
You could make these constructions a little bit simpler by having a<br>
&quot;CHECK_SIG_MSG_VERIFY&quot; opcode that accepts [sig msg key], and doe=
s &quot;sig<br>
key CHECKSIGVERIFY&quot; but also checks the the provided msg was what was<=
br>
passed into bip-schnorr.<br></blockquote><div><br></div><div>The whole poin=
t is to keep the functionality simple and let users program what they want.=
=C2=A0 What we don&#39;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&#39;t have in mind.<br></div></div></div>

--00000000000098513d058a012f9f--