Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 55146F70 for ; 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 ; Tue, 9 Jan 2018 14:21:10 +0000 (UTC) Received: by mail-oi0-f47.google.com with SMTP id y141so4217267oia.0 for ; 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: References: <87608btgyd.fsf@rustcorp.com.au> From: Pieter Wuille Date: Tue, 9 Jan 2018 06:21:08 -0800 Message-ID: To: Mark Friedenbach , Bitcoin Dev 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 , Kalle Alm 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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
On Jan 9, 2018 13:41, "Mark Friedenbach via bitcoin-dev" <bitcoin-dev@lists.li= nuxfoundation.org> wrote:
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.

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

As far as I can see, this proposal does not have any be= nefits 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&= #39;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 simultane= ously, I don'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.
* It does not interfere with static analysis (see= further).
* 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't think there is sufficient evide= nce they're needed.

= 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).

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 ag= ree 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.
<= 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>

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't think that addresses all p= otential concerns about static analysis (for example, it doesn't easily= let you prove all possible execution paths to a participant in a smart con= tract).

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.


=
Cheers,

--=C2=A0
Pieter

<= div dir=3D"auto">
--001a113de1a44bebb9056258a094--