From: Mark Friedenbach <mark@friedenbach.org>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Message-Id: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
Date: Wed, 6 Sep 2017 17:38:55 -0700
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: [bitcoin-dev] Merkle branch verification & tail-call semantics for
	generalized MAST
Precedence: list

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.

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.

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.

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.

I have written three BIPs to describe these features, and their
associated implementation, for which I now invite public review and
discussion:

Fast Merkle Trees
BIP: https://gist.github.com/maaku/41b0054de0731321d23e9da90ba4ee0a
Code: https://github.com/maaku/bitcoin/tree/fast-merkle-tree

MERKLEBRANCHVERIFY
BIP: https://gist.github.com/maaku/bcf63a208880bbf8135e453994c0e431
Code: https://github.com/maaku/bitcoin/tree/merkle-branch-verify

Tail-call execution semantics
BIP: https://gist.github.com/maaku/f7b2e710c53f601279549aa74eeb5368
Code: https://github.com/maaku/bitcoin/tree/tail-call-semantics

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.

Kind regards,
Mark Friedenbach