path: root/4f/452427685f443dd03fdf7499f2fa1aeadf55eb

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 AFC45F10
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 23 May 2019 02:32:39 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it1-f181.google.com (mail-it1-f181.google.com
	[209.85.166.181])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 9440A5D0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 23 May 2019 02:32:38 +0000 (UTC)
Received: by mail-it1-f181.google.com with SMTP id h20so7147610itk.4
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Wed, 22 May 2019 19:32:38 -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=nhtqi+DI/hHYeCsWROVMJjK4/KE7QaJ8dx5Gvph47rA=;
	b=J8Xlv9c9qMWT0U1A6LMiWJXfrKlFh474cmgrGPsFFfxOyULMkXbjlTLsH0RqDj9gLU
	xl8cOtfVOFSFggFODAGGm3l4eVDHSxWXqRt3HykJ7+rNkl79cuxrIQwxhhWi//prJNUg
	/qtb0Gc89oEq9rLtgCoiJL8lYv1ktx46/BIrQ=
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=nhtqi+DI/hHYeCsWROVMJjK4/KE7QaJ8dx5Gvph47rA=;
	b=IuXOw4WH3CCwevIT4Z5p/LAQMM0owhYFqex8HSb7dTIm01De384pZNyELO2QI8Qeum
	w+HST40pOGl7t79fet8xb/Z9eWVQ6JEirmlg1L56LYZehoB3Q/ME29Sd8SmyHTr6WXeY
	ogxpL2Kxg3mf8JMHjFTrBHHlD++KpqtCvzwSbTTLuPYQxzf4ZNPqIjXOxW4nlo425QtU
	iUzT2pebi/LGeER1kqhmY7NimKGx+SFSTqTlTkGlEZEIenb9ukUKl9StkzyA/8OcwJ4F
	HcqW8KQt6A8GLu8PZD/a9Ns6p9sdTInkv/dpel8Wucf2ZoC4ULzjFZmVXNh4Kysp77o4
	rp0Q==
X-Gm-Message-State: APjAAAV47NQlB5X6xpCjjSdIk9LLZztD5a5Cy5pF8dfn/eQVbU+SNJGN
	/g2pZxyea09GmnrmaSZ7xh9En5q/DH5nD2NftvvjQg==
X-Google-Smtp-Source: APXvYqyRlxf7La3j4Ro6+X5GFP2HbkmKcBXm6fLu0+YaUm1XImnfLj8nFoTjvrMGQGjrfBS2eEdtshbDuew7OOa7xBA=
X-Received: by 2002:a02:924d:: with SMTP id y13mr59456526jag.24.1558578757732; 
	Wed, 22 May 2019 19:32:37 -0700 (PDT)
MIME-Version: 1.0
References: <CAPg+sBg6Gg8b7hPogC==fehY3ZTHHpQReqym2fb4XXWFpMM-pQ@mail.gmail.com>
	<CAMZUoKkm33U+Rb+x03qUsFDG5CeX2C=nW8vD_8zbiAdsWazofQ@mail.gmail.com>
	<CAPg+sBh=VGiBS6Cof_SBKo2aPGURicTRkuaXWwaW0_u8_nWZ1Q@mail.gmail.com>
In-Reply-To: <CAPg+sBh=VGiBS6Cof_SBKo2aPGURicTRkuaXWwaW0_u8_nWZ1Q@mail.gmail.com>
From: "Russell O'Connor" <roconnor@blockstream.io>
Date: Wed, 22 May 2019 22:32:26 -0400
Message-ID: <CAMZUoKmo8TZvr36Ybp_bXmLDnhDEeHQ9d8rS+ZhYeDeNPrjsdw@mail.gmail.com>
To: Pieter Wuille <pieter.wuille@gmail.com>
Content-Type: multipart/alternative; boundary="00000000000035a7b4058984e565"
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, 23 May 2019 13:31:42 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
	Andrew Poelstra <andrew.poelstra@blockstream.com>
Subject: Re: [bitcoin-dev] Taproot proposal
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: Thu, 23 May 2019 02:32:39 -0000

--00000000000035a7b4058984e565
Content-Type: text/plain; charset="UTF-8"

On Wed, May 22, 2019 at 10:06 PM Pieter Wuille <pieter.wuille@gmail.com>
wrote:

> On Tue, 21 May 2019 at 10:20, Russell O'Connor <roconnor@blockstream.io>
> wrote:
> >
> > Regarding Tapscript, the specification calls for the final value of the
> stack being a single non-false value:
> >
> >> The tapscript is executed according to the rules in the following
> section, with the initial stack as input
> >>     II. If the execution results in anything but exactly one element on
> the stack which evaluates to true with CastToBool(), fail.
> >
> > Perhaps it is worth taking this opportunity here to remove a minor wart
> of the Script language and instead require the stack to be exactly empty
> upon completion.
> >
> > In addition to removing a potential malleability vector, I expect it
> would simplify development of Bitcoin Script.  A rule requiring an empty
> stack means that the conjunction (logical and) of two policies can be
> implemented by the simple concatenation of Bitcoin Scripts.  This combined
> with the taproot ability to form the disjunction (logical or) of policies
> by having multiple Merkle branches, means that the translation of a policy
> written in disjunctive normal form (the logical ors of logical ands of
> primitive policies) can be straightforwardly translated to a taproot of
> tapscript.
> >
> > That said, I think the developers of miniscript <
> http://bitcoin.sipa.be/miniscript/miniscript.html> are in a much better
> position to comment on whether my above intuition is correct given that
> they've had to implement a host of various calling conventions.  I
> understand that at least some of this complexity is due to Bitcoin Script's
> one element stack rule.
>
> IIRC I looked into this a few months ago, and found that the spending
> cost (script size + expected witness size) of the optimal script for
> every Miniscript policy at most changes by 1 WU (in either direction)
> by requiring an empty stack rather than a true value, though in a
> (admittedly very arbitrarily biased) distribution, more policies were
> improved by it than degraded. This is not taking Taproot into account
> (as many of those policies in a Taproot-supporting world should
> optimally make use of the internal key and Merkle tree, rather than
> turning everything into a monolithic script). I expect that this may
> make the impact somewhat larger, but still never more than a 1 WU
> gain.
>
> I don't think the spending cost changes justify this change, so the
> remaining criteria are complexity ones. In my view, the main benefit
> would be to authors of hand-written scripts where the consistency
> benefits matter, but this needs to be weighed against the mental cost
> of learning the new semantics. For Miniscript itself, this doesn't
> make much difference - the top level calling convention would become
> 'V' instead of 'T', but 'T' would still exist as a calling convention
> that may be used internally; it's a few lines change.
>
> So overall this feels like something with marginal costs, but also at
> most marginal benefits. Perhaps other people have stronger opinions.
>

Thanks for the info.  I'm surprised to learn that 'T' would still exist
internally.  That does make my proposed ammendment a somewhat more marginal
than I expected.  I still think it would be an improvement, but I guess it
is acceptable the way it is if that is what other people prefer.


> > Even if we choose not to implement the empty stack rule, we should at
> least require that the last element be 0x01 to remove a potential
> malleability vector and bring it in line with MINIMAL_IF semantics.
>
> This feels like the right thing to do; as we're making MINIMALIF part
> of consensus for Tapscript it would make sense to apply the same rule
> to the "return" value of the script. There is a downside though,
> namely that in some places where you'd use "<n>
> OP_CHECKSEQUENCEVERIFY" or "<n> OP_CHECKLOCKTIMEVERIFY" you now need
> to add an additional OP_0NOTEQUAL to convert the left-over element n
> into an exact 0x01. I also can't come up with any practical benefits
> that this would have; if the top stack element in a particular code
> path comes directly from the input, it's insecure regardless; if there
> isn't, it'll generally be a a boolean (or an intentional non-boolean
> true value) computed by the script.
>

That is a very good argument.  If we were to go with an empty stack we'd
probably also want modify to have CSV and CLTV pop their inputs off the
stack.  But at that point perhaps we'd want to change their opcode values
to avoid confusion with old style script.  I guess I'm getting more
convinced to not touch this stuff just and just bear with the somewhat
unfortunate legacy behaviour.

--00000000000035a7b4058984e565
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 Wed, May 22, 2019 at 10:06 PM Pieter Wuille &lt;<a href=3D"mailto=
:pieter.wuille@gmail.com">pieter.wuille@gmail.com</a>&gt; wrote:<br></div><=
blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-l=
eft:1px solid rgb(204,204,204);padding-left:1ex">On Tue, 21 May 2019 at 10:=
20, Russell O&#39;Connor &lt;<a href=3D"mailto:roconnor@blockstream.io" tar=
get=3D"_blank">roconnor@blockstream.io</a>&gt; wrote:<br>
&gt;<br>
&gt; Regarding Tapscript, the specification calls for the final value of th=
e stack being a single non-false value:<br>
&gt;<br>
&gt;&gt; The tapscript is executed according to the rules in the following =
section, with the initial stack as input<br>
&gt;&gt;=C2=A0 =C2=A0 =C2=A0II. If the execution results in anything but ex=
actly one element on the stack which evaluates to true with CastToBool(), f=
ail.<br>
&gt;<br>
&gt; Perhaps it is worth taking this opportunity here to remove a minor war=
t of the Script language and instead require the stack to be exactly empty =
upon completion.<br>
&gt;<br>
&gt; In addition to removing a potential malleability vector, I expect it w=
ould simplify development of Bitcoin Script.=C2=A0 A rule requiring an empt=
y stack means that the conjunction (logical and) of two policies can be imp=
lemented by the simple concatenation of Bitcoin Scripts.=C2=A0 This combine=
d with the taproot ability to form the disjunction (logical or) of policies=
 by having multiple Merkle branches, means that the translation of a policy=
 written in disjunctive normal form (the logical ors of logical ands of pri=
mitive policies) can be straightforwardly translated to a taproot of tapscr=
ipt.<br>
&gt;<br>
&gt; That said, I think the developers of miniscript &lt;<a href=3D"http://=
bitcoin.sipa.be/miniscript/miniscript.html" rel=3D"noreferrer" target=3D"_b=
lank">http://bitcoin.sipa.be/miniscript/miniscript.html</a>&gt; are in a mu=
ch better position to comment on whether my above intuition is correct give=
n that they&#39;ve had to implement a host of various calling conventions.=
=C2=A0 I understand that at least some of this complexity is due to Bitcoin=
 Script&#39;s one element stack rule.<br>
<br>
IIRC I looked into this a few months ago, and found that the spending<br>
cost (script size + expected witness size) of the optimal script for<br>
every Miniscript policy at most changes by 1 WU (in either direction)<br>
by requiring an empty stack rather than a true value, though in a<br>
(admittedly very arbitrarily biased) distribution, more policies were<br>
improved by it than degraded. This is not taking Taproot into account<br>
(as many of those policies in a Taproot-supporting world should<br>
optimally make use of the internal key and Merkle tree, rather than<br>
turning everything into a monolithic script). I expect that this may<br>
make the impact somewhat larger, but still never more than a 1 WU<br>
gain.<br>
<br>
I don&#39;t think the spending cost changes justify this change, so the<br>
remaining criteria are complexity ones. In my view, the main benefit<br>
would be to authors of hand-written scripts where the consistency<br>
benefits matter, but this needs to be weighed against the mental cost<br>
of learning the new semantics. For Miniscript itself, this doesn&#39;t<br>
make much difference - the top level calling convention would become<br>
&#39;V&#39; instead of &#39;T&#39;, but &#39;T&#39; would still exist as a =
calling convention<br>
that may be used internally; it&#39;s a few lines change.<br>
<br>
So overall this feels like something with marginal costs, but also at<br>
most marginal benefits. Perhaps other people have stronger opinions.<br></b=
lockquote><div><br></div><div>Thanks for the info.=C2=A0 I&#39;m surprised =
to learn that &#39;T&#39; would still exist internally.=C2=A0 That does mak=
e my proposed ammendment a somewhat more marginal than I expected.=C2=A0 I =
still think it would be an improvement, but I guess it is acceptable the wa=
y it is if that is what other people prefer.<br></div><div>=C2=A0</div><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
:1px solid rgb(204,204,204);padding-left:1ex">
&gt; Even if we choose not to implement the empty stack rule, we should at =
least require that the last element be 0x01 to remove a potential malleabil=
ity vector and bring it in line with MINIMAL_IF semantics.<br>
<br>
This feels like the right thing to do; as we&#39;re making MINIMALIF part<b=
r>
of consensus for Tapscript it would make sense to apply the same rule<br>
to the &quot;return&quot; value of the script. There is a downside though,<=
br>
namely that in some places where you&#39;d use &quot;&lt;n&gt;<br>
OP_CHECKSEQUENCEVERIFY&quot; or &quot;&lt;n&gt; OP_CHECKLOCKTIMEVERIFY&quot=
; you now need<br>
to add an additional OP_0NOTEQUAL to convert the left-over element n<br>
into an exact 0x01. I also can&#39;t come up with any practical benefits<br=
>
that this would have; if the top stack element in a particular code<br>
path comes directly from the input, it&#39;s insecure regardless; if there<=
br>
isn&#39;t, it&#39;ll generally be a a boolean (or an intentional non-boolea=
n<br>
true value) computed by the script.<br></blockquote><div><br></div><div>Tha=
t is a very good argument.=C2=A0 If we were to go with an empty stack we&#3=
9;d probably also want modify to have CSV and CLTV pop their inputs off the=
 stack.=C2=A0 But at that point perhaps we&#39;d want to change their opcod=
e values to avoid confusion with old style script.=C2=A0 I guess I&#39;m ge=
tting more convinced to not touch this stuff just and just bear with the so=
mewhat unfortunate legacy behaviour.</div><div><br></div></div></div>

--00000000000035a7b4058984e565--