path: root/3e/fe706f16b22072259d316f7efafeaae401b292

Return-Path: <pieter.wuille@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 55146F70
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue,  9 Jan 2018 14:21:11 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-oi0-f47.google.com (mail-oi0-f47.google.com
	[209.85.218.47])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 7618DE3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue,  9 Jan 2018 14:21:10 +0000 (UTC)
Received: by mail-oi0-f47.google.com with SMTP id y141so4217267oia.0
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Tue, 09 Jan 2018 06:21:10 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=mime-version:in-reply-to:references:from:date:message-id:subject:to
	:cc; bh=dB7SlC87sZGVU+z267TjBqX28KpuYQEQKQbyO95+8A0=;
	b=ql5UlNoVdjFigDPokftYujnRUOpkBBNaMEh9ecdlF/y5L4f0ZHHDfwY3kQeeUYQwkD
	9uCK9XB2BSFMhjCvRJUlR+MKRytQIuQswLiy0CknFysgP4mtLOSoZMthN8A1ZIdhLu3Q
	xzVbwTyw7Fox2QyYpYA3tbz1tM4nwtEJu83O99KJWdAvP86hHoL+ZGbgR5pJBuKkv7wX
	/2pTZ6Zj6cSobk5kmkdjuO0KgOayUZ8ow/dVViPKUnORDhLXbG7t/oO4HdnDAToZFiBT
	m3cyY/Ha6bugajvvC4ONm4DO7K0MDP9aw9jrGyuzMf/FqrDz11w+jPtQMd2Ht2PnOqGO
	FjJA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:mime-version:in-reply-to:references:from:date
	:message-id:subject:to:cc;
	bh=dB7SlC87sZGVU+z267TjBqX28KpuYQEQKQbyO95+8A0=;
	b=VQGQlU5ut6vRcoH5CkniepTHC9vNRGWgSL2Q6cHaE1TI/C/wr3ZCxXTYKyBWSGb5At
	gQxEA4Ro4UaQXytCrtYKArQGZUK5qvDAe+YTJIIaQPC7LKmencctKQfgpW2LTpmPu4Km
	NU6A92+q5gs8mxfi5iTCo8LmaPg2MZZNatObMIwSo6EeR4ZDgsIGSFj6QQmwKaGqp405
	+qW9Wr8Nz0ydDPQTEQQx2RLAjh7lrm9/v22Cork94bNU0hlbEfSo0NEvD8EwWug4I7nt
	hLuFaSrtZ+TGCGO3HfOsdyDaJov0eb4FZbHoW7M2qhapqsMck+H+MbguMOVjHZNZtiho
	Z5Kg==
X-Gm-Message-State: AKGB3mLklmX9tBiEOFyO3gcfjqkOFDXPilqK/RCIWPzYlv3ZrTyWLTgD
	0mksnaHYDGUgLLfKbivhdtul52LGQcEH0lMMbhw=
X-Google-Smtp-Source: ACJfBotQTXmPye5WPpJk5weliXN0j+H1SCh9QnmuqS0r3e6sEt1LXQup0urXdqD9hNGISLM2ziIx6C3dAfcdbV30MyM=
X-Received: by 10.202.245.151 with SMTP id t145mr8516080oih.285.1515507669524; 
	Tue, 09 Jan 2018 06:21:09 -0800 (PST)
MIME-Version: 1.0
Received: by 10.74.102.3 with HTTP; Tue, 9 Jan 2018 06:21:08 -0800 (PST)
Received: by 10.74.102.3 with HTTP; Tue, 9 Jan 2018 06:21:08 -0800 (PST)
In-Reply-To: <DB7E57AC-5588-4BBA-9ABC-B9B4F6BAECE2@friedenbach.org>
References: <87608btgyd.fsf@rustcorp.com.au>
	<DB7E57AC-5588-4BBA-9ABC-B9B4F6BAECE2@friedenbach.org>
From: Pieter Wuille <pieter.wuille@gmail.com>
Date: Tue, 9 Jan 2018 06:21:08 -0800
Message-ID: <CAPg+sBgRrqZryiETZYCWiqHNOmN2bCfsvr30znjN-gKiU5Vfjg@mail.gmail.com>
To: Mark Friedenbach <mark@friedenbach.org>, 
	Bitcoin Dev <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="001a113de1a44bebb9056258a094"
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, 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
Cc: Russell O'Connor <roconnor@blockstream.com>,
	Kalle Alm <kalle.alm@gmail.com>
Subject: Re: [bitcoin-dev] BIP 117 Feedback
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: Tue, 09 Jan 2018 14:21:11 -0000

--001a113de1a44bebb9056258a094
Content-Type: text/plain; charset="UTF-8"

On Jan 9, 2018 13:41, "Mark Friedenbach via bitcoin-dev" <
bitcoin-dev@lists.linuxfoundation.org> wrote:

The use of the alt stack is a hack for segwit script version 0 which has
the clean stack rule. Anticipated future improvements here are to switch to
a witness script version, and a new segwit output version which supports
native MAST to save an additional 40 or so witness bytes. Either approach
would allow getting rid of the alt stack hack. They are not part of the
proposal now because it is better to do things incrementally, and because
we anticipate usage of MAST to better inform these less generic changes.


If the goal is to introduce a native MAST output type later, what is gained
by first having the tailcall semantics?

As far as I can see, this proposal does not have any benefits over Johnson
Lau's MAST idea [1]:
* It is more compact, already giving us the space savings a native MAST
version of the tail call semantics would bring.
* It does not need to work around limitations of push size limits or
cleanstack rules.
* The implementation (of code I've seen) is easier to reason about, as it's
just another case in VerifyScript (which you'd need for a native MAST
output later too) without introducing jumps or loops inside EvalScript.
* It can express the same, as even though the MBV opcode supports proving
multiple elements simultaneously, I don't see a way to use that in the tail
call. Every scenario that consists of some logic before deciding what the
tail call is going to be can be rewritten to have that logic inside each of
the branches, I believe.
* It does not interfere with static analysis (see further).
* Tail call semantics may be easier to extend in the future to enable
semantics that are not compactly representable in either proposal right
now, by allowing a single top-level script may invoke multiple subscripts,
or recursion. However, those sound even riskier and harder to analyse to
me, and I don't think there is sufficient evidence they're needed.

Native MAST outputs would need a new witness script version, which your
current proposal does indeed not need. However, I believe a new script
version will be desirable for other reasons regardless (returning invalid
opcodes to the pool of NOPs available for softforks, for example).

I will make a strong assertion: static analyzing the number of opcodes and
sigops gets us absolutely nothing. It is cargo cult safety engineering. No
need to perpetuate it when it is now in the way.


I'm not sure I agree here. While I'd like to see the separate execution
limits go away, removing them entirely and complicating future ability to
introduce unified costing towards weight of execution cost seems the wrong
way to go.

My reasoning is this: perhaps you can currently make an argument that the
current weight limit is sufficient in preventing overly expensive block
validation costs, due to a minimal ratio between script sizes and their
execution cost. But such an argument needs to rely on assumptions about
sighash caching and low per-opcode CPU time, which may change in the
future. In my view, tail call semantics gratuitously remove or complicate
the ability to reason about the executed code.

One suggestion to reduce the impact of this is limiting the per-script
execution to something proportional to the script size. However, I don't
think that addresses all potential concerns about static analysis (for
example, it doesn't easily let you prove all possible execution paths to a
participant in a smart contract).

Another idea that has been suggested on this list is to mark pushes of
potentially executable code on the stack/witness explicitly. This would
retain all ability to analyse, while still leaving the flexibility of
future extensions to tail call execution. If tail call semantics are
adopted, I strongly prefer an approach like that to blindly throwing out
all limits and analysis.

  [1] https://github.com/jl2012/bips/blob/mast/bip-mast.mediawiki

Cheers,

-- 
Pieter

--001a113de1a44bebb9056258a094
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto"><div><div class=3D"gmail_extra"><div class=3D"gmail_quote=
">On Jan 9, 2018 13:41, &quot;Mark Friedenbach via bitcoin-dev&quot; &lt;<a=
 href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@lists.li=
nuxfoundation.org</a>&gt; wrote:<br type=3D"attribution"><blockquote class=
=3D"quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-le=
ft:1ex">The use of the alt stack is a hack for segwit script version 0 whic=
h has the clean stack rule. Anticipated future improvements here are to swi=
tch to a witness script version, and a new segwit output version which supp=
orts native MAST to save an additional 40 or so witness bytes. Either appro=
ach would allow getting rid of the alt stack hack. They are not part of the=
 proposal now because it is better to do things incrementally, and because =
we anticipate usage of MAST to better inform these less generic changes.<br=
></blockquote></div></div></div><div dir=3D"auto"><br></div><div dir=3D"aut=
o">If the goal is to introduce a native MAST output type later, what is gai=
ned by first having the tailcall semantics?</div><div dir=3D"auto"><br></di=
v><div dir=3D"auto">As far as I can see, this proposal does not have any be=
nefits over Johnson Lau&#39;s MAST idea [1]:</div><div dir=3D"auto">* It is=
 more compact, already giving us the space savings a native MAST version of=
 the tail call semantics would bring.</div><div dir=3D"auto">* It does not =
need to work around limitations of push size limits or cleanstack rules.</d=
iv><div dir=3D"auto">* The implementation (of code I&#39;ve seen) is easier=
 to reason about, as it&#39;s just another case in VerifyScript (which you&=
#39;d need for a native MAST output later too) without introducing jumps or=
 loops inside EvalScript.</div><div dir=3D"auto">* It can express the same,=
 as even though the MBV opcode supports proving multiple elements simultane=
ously, I don&#39;t see a way to use that in the tail call. Every scenario t=
hat consists of some logic before deciding what the tail call is going to b=
e can be rewritten to have that logic inside each of the branches, I believ=
e.</div><div dir=3D"auto">* It does not interfere with static analysis (see=
 further).</div><div dir=3D"auto">* Tail call semantics may be easier to ex=
tend in the future to enable semantics that are not compactly representable=
 in either proposal right now, by allowing a single top-level script may in=
voke multiple subscripts, or recursion. However, those sound even riskier a=
nd harder to analyse to me, and I don&#39;t think there is sufficient evide=
nce they&#39;re needed.</div><div dir=3D"auto"><br></div><div dir=3D"auto">=
Native MAST outputs would need a new witness script version, which your cur=
rent proposal does indeed not need. However, I believe a new script version=
 will be desirable for other reasons regardless (returning invalid opcodes =
to the pool of NOPs available for softforks, for example).</div><div dir=3D=
"auto"><br></div><div dir=3D"auto"><div class=3D"gmail_extra"><div class=3D=
"gmail_quote"><blockquote class=3D"quote" style=3D"margin:0 0 0 .8ex;border=
-left:1px #ccc solid;padding-left:1ex">
I will make a strong assertion: static analyzing the number of opcodes and =
sigops gets us absolutely nothing. It is cargo cult safety engineering. No =
need to perpetuate it when it is now in the way.<br></blockquote></div></di=
v></div><div dir=3D"auto"><br></div><div dir=3D"auto">I&#39;m not sure I ag=
ree here. While I&#39;d like to see the separate execution limits go away, =
removing them entirely and complicating future ability to introduce unified=
 costing towards weight of execution cost seems the wrong way to go.</div><=
div dir=3D"auto"><br></div><div dir=3D"auto">My reasoning is this: perhaps =
you can currently make an argument that the current weight limit is suffici=
ent in preventing overly expensive block validation costs, due to a minimal=
 ratio between script sizes and their execution cost. But such an argument =
needs to rely on assumptions about sighash caching and low per-opcode CPU t=
ime, which may change in the future. In my view, tail call semantics gratui=
tously remove or complicate the ability to reason about the executed code.<=
/div><div dir=3D"auto"><br></div><div dir=3D"auto">One suggestion to reduce=
 the impact of this is limiting the per-script execution to something propo=
rtional to the script size. However, I don&#39;t think that addresses all p=
otential concerns about static analysis (for example, it doesn&#39;t easily=
 let you prove all possible execution paths to a participant in a smart con=
tract).</div><div dir=3D"auto"><br></div><div dir=3D"auto">Another idea tha=
t has been suggested on this list is to mark pushes of potentially executab=
le code on the stack/witness explicitly. This would retain all ability to a=
nalyse, while still leaving the flexibility of future extensions to tail ca=
ll execution. If tail call semantics are adopted, I strongly prefer an appr=
oach like that to blindly throwing out all limits and analysis.</div><div d=
ir=3D"auto"><br></div><div dir=3D"auto">=C2=A0 [1]=C2=A0<a href=3D"https://=
github.com/jl2012/bips/blob/mast/bip-mast.mediawiki">https://github.com/jl2=
012/bips/blob/mast/bip-mast.mediawiki</a></div><div dir=3D"auto"><br></div>=
<div dir=3D"auto">Cheers,</div><div dir=3D"auto"><br></div><div dir=3D"auto=
">--=C2=A0</div><div dir=3D"auto">Pieter</div><div dir=3D"auto"><br></div><=
div dir=3D"auto"><div class=3D"gmail_extra"><div class=3D"gmail_quote"><blo=
ckquote class=3D"quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc sol=
id;padding-left:1ex"></blockquote></div></div></div></div>

--001a113de1a44bebb9056258a094--