Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST

From: Mark Friedenbach <mark@friedenbach•org>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: Re: [bitcoin-dev] Merkle branch verification & tail-call semantics for generalized MAST
Date: Mon, 18 Sep 2017 17:46:30 -0700	[thread overview]
Message-ID: <C623794E-F061-4C7A-B05D-378798ED2BF7@friedenbach.org> (raw)
In-Reply-To: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>

As some of you may know, the MAST proposal I sent to the mailing list
on September 6th was discussed that the in-person CoreDev meetup in
San Francisco. In this email I hope to summarize the outcome of that
discussion. As chatham house rules were in effect, I will refrain from
attributing names to this summary..

* An introductory overview of the BIPs was presented, for the purpose
  of familiarizing the audience with what they are attempting to
  accomplish and how they do so.

* There was a discussion of a single vs multi-element MBV opcode. It
  was put forward that there should perhaps be different opcodes for
  the sake of script analysis, since a multi-element MBV will
  necessarily consume a variable number of inputs. However it was
  countered that if the script encodes the number of elements as an
  integer push to the top of the stack immediately before the opcode,
  then static analyzability is maintained in such instances. I took
  the action item to investigate what an ideal serialization format
  would be for a multi-element proof, which is the only thing holding
  back a multi-element MBV proposal.

* It was pointed out that the non-clean-stack tail-call semantics is
  not compatible with segwit's consensus-enforcement of the clean
  stack rule. Some alternatives were suggested, such as changing
  deployment mechanisms. 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. I
  will be updating the BIP and example implementation accordingly.

* The observation was made that single-layer tail-call semantics can
  be thought of as really being P2SH with user-specified hashing. If
  the P2SH script template had been constructed slightly differently
  such as to not consume the script, it would even have been fully
  compatible with tail-call semantics.

* It was mentioned that using script versioning to deploy a MAST
  template allows for saving 32 bytes of witness per input, as the
  root hash is contained directly in the output being spent. The
  downside however is losing the permissionless innovation that comes
  with a programmable hashing mechanism.

* The discussion generally drifted into a wider discussion about
  script version upgrades and related issues, such as whether script
  versions should exist in the witness as well, and the difference in
  meaning between the two. This is an important subject, but only of
  relevance in far as using a script version upgrade to deploy MAST
  would add significant delay from having to sort through these issues
  first.

This feedback led to some minor tweaks to the proposal, which I will
be making, as well as the major feature request of a multi-element
MERKLE-BLOCK-VERIFY opcode which requires a little bit more effort to
accomplish. I will report back to this list again when that work is
done.

Sincerely,
Mark Friedenbach