From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id BCF36978 for ; Fri, 8 Sep 2017 09:21:33 +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 A3DC3E0 for ; Fri, 8 Sep 2017 09:21:31 +0000 (UTC) Received: from [10.7.52.189] (ip-123-255-103-154.wlan.cuhk.edu.hk [123.255.103.154]) by mx.zohomail.com with SMTPS id 1504862486418606.1854238651416; Fri, 8 Sep 2017 02:21:26 -0700 (PDT) From: Johnson Lau Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\)) Date: Fri, 8 Sep 2017 17:21:22 +0800 References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org> To: Mark Friedenbach , bitcoin-dev In-Reply-To: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org> Message-Id: <26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk> X-Mailer: Apple Mail (2.3273) X-ZohoMailClient: External X-Spam-Status: No, score=0.0 required=5.0 tests=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] 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: Fri, 08 Sep 2017 09:21:33 -0000 Some comments with the tail-call execution semantics BIP: Tail-call execution semantics require =E2=80=9Cunclean stake=E2=80=9D, = i.e. final stake with more than one item. However, =E2=80=9Cunclean = stake=E2=80=9D is invalid (not just non-standard) in BIP141, so you = could only use it with legacy P2SH (which is totally pointless=E2=80=A6.).= A different design like OP_EVAL might be needed, or you need a new = witness script version. I think you have also missed the sigOp counting of the executed script. = As you can=E2=80=99t count it without executing the script, the current = static analysability is lost. This was one of the reasons for OP_EVAL = being rejected. Since sigOp is a per-block limit, any OP_EVAL-like = operation means block validity will depend on the precise outcome of = script execution (instead of just pass or fail), which is a layer = violation. (An alternative is to make sigOp a per-input limit instead of per-block = limit, just like the 201 nOp limit. But this is a very different = security model) Witness script versioning is by design fully compatible with P2SH and = BIP173, so there will be no hurdle for existing wallets to pay to = BIP114. Actually it should be completely transparent to them. For code complexity, the minimal BIP114 could be really simple, like <30 = lines of code? It looks complex now because it does much more than = simply hiding scripts in a hash. > On 7 Sep 2017, at 8:38 AM, Mark Friedenbach via bitcoin-dev = wrote: >=20 > I would like to propose two new script features to be added to the > bitcoin protocol by means of soft-fork activation. These features are > a new opcode, MERKLE-BRANCH-VERIFY (MBV) and tail-call execution > semantics. >=20 > In brief summary, MERKLE-BRANCH-VERIFY allows script authors to force > redemption to use values selected from a pre-determined set committed > to in the scriptPubKey, but without requiring revelation of unused > elements in the set for both enhanced privacy and smaller script > sizes. Tail-call execution semantics allows a single level of > recursion into a subscript, providing properties similar to P2SH while > at the same time more flexible. >=20 > These two features together are enough to enable a range of > applications such as tree signatures (minus Schnorr aggregation) as > described by Pieter Wuille [1], and a generalized MAST useful for > constructing private smart contracts. It also brings privacy and > fungibility improvements to users of counter-signing wallet/vault > services as unique redemption policies need only be revealed if/when > exceptional circumstances demand it, leaving most transactions looking > the same as any other MAST-enabled multi-sig script. >=20 > I believe that the implementation of these features is simple enough, > and the use cases compelling enough that we could BIP 8/9 rollout of > these features in relatively short order, perhaps before the end of > the year. >=20 > I have written three BIPs to describe these features, and their > associated implementation, for which I now invite public review and > discussion: >=20 > Fast Merkle Trees > BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a > Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree >=20 > MERKLEBRANCHVERIFY > BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431 > Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify >=20 > Tail-call execution semantics > BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368 > Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics >=20 > Note: I have circulated this idea privately among a few people, and I > will note that there is one piece of feedback which I agree with but > is not incorporated yet: there should be a multi-element MBV opcode > that allows verifying multiple items are extracted from a single > tree. It is not obvious how MBV could be modified to support this > without sacrificing important properties, or whether should be a > separate multi-MBV opcode instead. >=20 > Kind regards, > Mark Friedenbach > _______________________________________________ > bitcoin-dev mailing list > bitcoin-dev@lists.linuxfoundation.org > https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev