Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BC18FC46 for ; Wed, 20 Sep 2017 05:13:14 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sender-of-o52.zoho.com (sender-of-o52.zoho.com [135.84.80.217]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id C6109D3 for ; Wed, 20 Sep 2017 05:13:13 +0000 (UTC) Received: from [192.168.1.139] (137.189.135.167 [137.189.135.167]) by mx.zohomail.com with SMTPS id 1505884390337715.7435394716991; Tue, 19 Sep 2017 22:13:10 -0700 (PDT) From: Johnson Lau Message-Id: Content-Type: multipart/alternative; boundary="Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658" Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\)) Date: Wed, 20 Sep 2017 13:13:04 +0800 In-Reply-To: <201709190309.08669.luke@dashjr.org> To: Luke Dashjr , bitcoin-dev References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org> <201709190309.08669.luke@dashjr.org> X-Mailer: Apple Mail (2.3273) X-ZohoMailClient: External X-Spam-Status: No, score=0.0 required=5.0 tests=HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Subject: Re: [bitcoin-dev] cleanstack alt stack & softfork improvements (Was: Merkle branch verification & tail-call semantics for generalized MAST) 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, 20 Sep 2017 05:13:14 -0000 --Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 > On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev = wrote: >=20 > On Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via = bitcoin-dev=20 > wrote: >> After the main discussion session it was observed that tail-call = semantics >> could still be maintained if the alt stack is used for transferring >> arguments to the policy script. >=20 > Isn't this a bug in the cleanstack rule? >=20 > (Unrelated...) >=20 > Another thing that came up during the discussion was the idea of = replacing all=20 > the NOPs and otherwise-unallocated opcodes with a new OP_RETURNTRUE=20 > implementation, in future versions of Script. This would immediately = exit the=20 > program (perhaps performing some semantic checks on the remainder of = the=20 > Script) with a successful outcome. >=20 > This is similar to CVE-2010-5141 in a sense, but since signatures are = no=20 > longer Scripts themselves, it shouldn't be exploitable. >=20 > The benefit of this is that it allows softforking in ANY new opcode, = not only=20 > the -VERIFY opcode variants we've been doing. That is, instead of = merely=20 > terminating the Script with a failure, the new opcode can also remove = or push=20 > stack items. This is because old nodes, upon encountering the = undefined=20 > opcode, will always succeed immediately, allowing the new opcode to do=20= > literally anything from that point onward. >=20 > Luke > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev I have implemented OP_RETURNTRUE in an earlier version of MAST (BIP114) = but have given up the idea, for 2 reasons: 1. I=E2=80=99ve updated BIP114 to allow inclusion of scripts in witness, = and require them to be signed. In this way users could add additional = conditions for the validity of a signature. For example, with = OP_CHECKBLOCKHASH, it is possible to make the transaction valid only in = the specified chain. (More discussion in = https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_sc= ripts_in_witness = ) 2. OP_RETURNTRUE does not work well with signature aggregation. = Signature aggregation will collect (pubkey, message) pairs in a tx, = combine them, and verify with one signature. However, consider the = following case: OP_RETURNTRUE OP_IF OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE For old nodes, the script terminates at OP_RETURNTRUE, and it will not = collect the (pubkey, message) pair. If we use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the = number 17 to the stack), new nodes will collect the (pubkey, message) = pair and try to aggregate with other pairs. This becomes a hardfork. -------- Technically, we could create ANY op code with an OP_NOP. For example, if = we want OP_MUL, we could have OP_MULVERIFY, which verifies if the 3rd = stack item is the product of the top 2 stack items. Therefore, = OP_MULVERIFY OP_2DROP is functionally same as OP_MUL, which removes the = top 2 items and returns the product. The problem is it takes more = witness space. If we don=E2=80=99t want this ugliness, we could use a new script = version for every new op code we add. In the new BIP114 (see link = above), I suggest to move the script version to the witness, which is = cheaper. --Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8
On 19 Sep 2017, at 11:09 AM, Luke Dashjr via bitcoin-dev = <bitcoin-dev@lists.linuxfoundation.org> wrote:

On = Tuesday 19 September 2017 12:46:30 AM Mark Friedenbach via bitcoin-dev =
wrote:
After the main discussion session it was observed that = tail-call semantics
could still be maintained if the alt = stack is used for transferring
arguments to the policy = script.

Isn't this a bug in = the cleanstack rule?

(Unrelated...)

Another thing that came up during the = discussion was the idea of replacing all
the NOPs and = otherwise-unallocated opcodes with a new OP_RETURNTRUE
implementation, in future versions of Script. This would = immediately exit the
program (perhaps performing some = semantic checks on the remainder of the
Script) with a = successful outcome.

This is similar to = CVE-2010-5141 in a sense, but since signatures are no
longer Scripts themselves, it shouldn't be exploitable.

The benefit of this is that it allows = softforking in ANY new opcode, not only
the -VERIFY = opcode variants we've been doing. That is, instead of merely
terminating the Script with a failure, the new opcode can = also remove or push
stack items. This is because old = nodes, upon encountering the undefined
opcode, will = always succeed immediately, allowing the new opcode to do
literally anything from that point onward.

Luke
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev<= br class=3D"">

I have implemented OP_RETURNTRUE in an earlier version of = MAST (BIP114) but have given up the idea, for 2 reasons:

1. I=E2=80=99ve updated = BIP114 to allow inclusion of scripts in witness, and require them to be = signed. In this way users could add additional conditions for the = validity of a signature. For example, with OP_CHECKBLOCKHASH, it is = possible to make the transaction valid only in the specified chain. = (More discussion in https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Ad= ditional_scripts_in_witness )

2. OP_RETURNTRUE does not work well = with signature aggregation. Signature aggregation will collect (pubkey, = message) pairs in a tx, combine them, and verify with one signature. = However, consider the following case:

OP_RETURNTRUE OP_IF <pubkey> = OP_CHECKSIGVERIFY OP_ENDIF OP_TRUE

For old nodes, the script terminates at = OP_RETURNTRUE, and it will not collect the (pubkey, message) = pair.

If we = use a softfork to transform OP_RETURNTRUE into OP_17 (pushing the number = 17 to the stack), new nodes will collect the (pubkey, message) pair and = try to aggregate with other pairs. This becomes a hardfork.

--------
Technically, we could create ANY op code with an OP_NOP. For = example, if we want OP_MUL, we could have OP_MULVERIFY, which verifies = if the 3rd stack item is the product of the top 2 stack items. = Therefore, OP_MULVERIFY OP_2DROP is functionally same as OP_MUL, which = removes the top 2 items and returns the product. The problem is it takes = more witness space.

If we don=E2=80=99t want this ugliness, we could use a new = script version for every new op code we add. In the new BIP114 (see link = above), I suggest to move the script version to the witness, which is = cheaper.


= --Apple-Mail=_013F33CA-53D0-4676-A454-6798ABC1E658--