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

Luke Dashjr luke at dashjr.org
Sat Nov 4 07:59:07 UTC 2017


How about using for the first stage, `<...> OP_CALCMERKLEROOT <root> OP_EQUAL` 
instead of `<root...> OP_CHECKMERKLEBRANCH`? There's maybe 1 or 2 bytes extra, 
but it seems more future-proof (since there could more easily be alternatives 
to `<root> OP_EQUAL` in future script versions).

OTOH, OP_ADDTOSCRIPTHASH may be fatally incompatible with script versioning... 
Old nodes won't know how to check the witness program, which means an 
undefined version could be used to bypass the correct script entirely.
Need to think more on this still.

Luke


On Wednesday 01 November 2017 3:08:46 PM Mark Friedenbach wrote:
> Yes, if you use a witness script version you can save about 40 witness
> bytes by templating the MBV script, which I think is equivalent to what
> you are suggesting. 32 bytes from the saved hash, plus another 8 bytes or
> so from script templates and more efficient serialization.
> 
> I believe the conservatively correct approach is to do this in stages,
> however. First roll out MBV and tail call to witness v0. Then once there
> is experience with people using it in production, design and deploy a
> hashing template for script v1. It might be that we learn more and think
> of something better in the meantime.
> 
> > On Nov 1, 2017, at 1:43 AM, Luke Dashjr <luke at dashjr.org> wrote:
> > 
> > Mark,
> > 
> > I think I have found an improvement that can be made.
> > 
> > As you recall, a downside to this approach is that one must make two
> > commitments: first, to the particular "membership-checking script"; and
> > then in that script, to the particular merkle root of possible scripts.
> > 
> > Would there be any harm in, instead of checking membership, *calculating*
> > the root? If not, then we could define that instead of the witness
> > program committing to H(membership-check script), it rather commits to
> > H(membership- calculation script | data added by an OP_ADDTOSCRIPTHASH).
> > This would, I believe, securely reduce the commitment of both to a
> > single hash.
> > 
> > It also doesn't reduce flexibility, since one could omit
> > OP_ADDTOSCRIPTHASH from their "membership-calculation" script to get the
> > previous membership- check behaviour, and use <hash> OP_EQUAL in its
> > place.
> > 
> > What do you think?
> > 
> > Luke
> > 
> >> On Saturday 28 October 2017 4:40:01 AM Mark Friedenbach wrote:
> >> I have completed updating the three BIPs with all the feedback that I
> >> have received so far. In short summary, here is an incomplete list of
> >> the changes that were made:
> >> 
> >> * Modified the hashing function fast-SHA256 so that an internal node
> >> cannot be interpreted simultaneously as a leaf. * Changed
> >> MERKLEBRANCHVERIFY to verify a configurable number of elements from the
> >> tree, instead of just one. * Changed MERKLEBRANCHVERIFY to have two
> >> modes: one where the inputs are assumed to be hashes, and one where
> >> they are run through double-SHA256 first. * Made tail-call eval
> >> compatible with BIP141’s CLEANSTACK consensus rule by allowing
> >> parameters to be passed on the alt-stack. * Restricted tail-call eval
> >> to segwit scripts only, so that checking sigop and opcode limits of the
> >> policy script would not be necessary.
> >> 
> >> There were a bunch of other small modifications, typo fixes, and
> >> optimizations that were made as well.
> >> 
> >> I am now ready to submit these BIPs as a PR against the bitcoin/bips
> >> repo, and I request that the BIP editor assign numbers.
> >> 
> >> Thank you,
> >> Mark Friedenbach
> >> 
> >>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark at friedenbach.org>
> >>> wrote:
> >>> 
> >>> 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


More information about the bitcoin-dev mailing list