Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 62B7BD49
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 Sep 2015 17:18:55 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from s47.web-hosting.com (s47.web-hosting.com [199.188.200.16])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id BEB6926C
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Thu, 10 Sep 2015 17:18:54 +0000 (UTC)
Received: from localhost ([::1]:37634 helo=server47.web-hosting.com)
	by server47.web-hosting.com with esmtpa (Exim 4.85)
	(envelope-from <jl2012@xbt.hk>) id 1Za5Ur-002URR-1K
	for bitcoin-dev@lists.linuxfoundation.org;
	Thu, 10 Sep 2015 13:18:53 -0400
MIME-Version: 1.0
Content-Type: text/plain; charset=US-ASCII;
 format=flowed
Content-Transfer-Encoding: 7bit
Date: Thu, 10 Sep 2015 13:18:52 -0400
From: jl2012@xbt.hk
To: bitcoin-dev@lists.linuxfoundation.org
Message-ID: <282c2912327370d30a0d341dcf1a6499@xbt.hk>
X-Sender: jl2012@xbt.hk
User-Agent: Roundcube Webmail/1.0.5
X-AntiAbuse: This header was added to track abuse,
	please include it with any abuse report
X-AntiAbuse: Primary Hostname - server47.web-hosting.com
X-AntiAbuse: Original Domain - lists.linuxfoundation.org
X-AntiAbuse: Originator/Caller UID/GID - [47 12] / [47 12]
X-AntiAbuse: Sender Address Domain - xbt.hk
X-Get-Message-Sender-Via: server47.web-hosting.com: authenticated_id:
	jl2012@xbt.hk
X-Source: 
X-Source-Args: 
X-Source-Dir: 
X-From-Rewrite: unmodified, already matched
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
	autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Subject: [bitcoin-dev] =?utf-8?q?MAST_with_OP=5FEVAL_and_OP=5FCAT?=
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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, 10 Sep 2015 17:18:55 -0000

Inspired by Pieter's Tree Signatures, I believe Merkleized Abstract 
Syntax Trees (MAST) could be implemented with only OP_CAT and OP_EVAL 
(BIP12).

The idea is very simple. Using a similar example in Pieter's paper,

scriptSig = <sig> <serialized sub-script 10> Z1 0 1 1 X6 1 K9 0 
<serialized script>
scriptPubKey = DUP HASH160 <hash serialized script> EQUALVERIFY EVAL
serialized script = 8 PICK SHA256 (SWAP IF SWAP ENDIF CAT SHA256)*4 <R> 
EQUALVERIFY EVAL

This will run the 10-th sub-script, when there are 11 sub-scripts in the 
MAST

I think this is the easiest way to enable MAST since the reference 
implementation for BIP12 is already there. We could enable OP_CAT only 
inside OP_EVAL so this will be a pure softfork.

Ref:
Tree Signatures: https://blockstream.com/2015/08/24/treesignatures/
BIP12: https://github.com/bitcoin/bips/blob/master/bip-0012.mediawiki