Return-Path: <luke@dashjr.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 9FBA140C
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat,  4 Nov 2017 08:00:24 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from zinan.dashjr.org (zinan.dashjr.org [192.3.11.21])
	by smtp1.linuxfoundation.org (Postfix) with ESMTP id C918447A
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sat,  4 Nov 2017 08:00:22 +0000 (UTC)
Received: from ishibashi.localnet (unknown [IPv6:2001:470:5:265::71])
	(Authenticated sender: luke-jr)
	by zinan.dashjr.org (Postfix) with ESMTPSA id 6559838ABA72;
	Sat,  4 Nov 2017 07:59:11 +0000 (UTC)
X-Hashcash: 1:25:171104:mark@friedenbach.org::bEnADdl5eJxXjiFm:aCkhn
X-Hashcash: 1:25:171104:bitcoin-dev@lists.linuxfoundation.org::JierrdSjaHOSAMak:iH6eu
From: Luke Dashjr <luke@dashjr.org>
To: Mark Friedenbach <mark@friedenbach.org>
Date: Sat, 4 Nov 2017 07:59:07 +0000
User-Agent: KMail/1.13.7 (Linux/4.12.12-gentoo; KDE/4.14.34; x86_64; ; )
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
	<201711010843.49771.luke@dashjr.org>
	<4F328120-94E0-4EFF-A76D-99E6007FA906@friedenbach.org>
In-Reply-To: <4F328120-94E0-4EFF-A76D-99E6007FA906@friedenbach.org>
X-PGP-Key-Fingerprint: E463 A93F 5F31 17EE DE6C 7316 BD02 9424 21F4 889F
X-PGP-Key-ID: BD02942421F4889F
X-PGP-Keyserver: hkp://pgp.mit.edu
MIME-Version: 1.0
Content-Type: Text/Plain;
  charset="gb18030"
Content-Transfer-Encoding: quoted-printable
Message-Id: <201711040759.09710.luke@dashjr.org>
X-Spam-Status: No, score=-2.3 required=5.0 tests=RCVD_IN_DNSWL_MED,
	RP_MATCHES_RCVD autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.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 <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: Sat, 04 Nov 2017 08:00:24 -0000

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

OTOH, OP_ADDTOSCRIPTHASH may be fatally incompatible with script versioning=
=2E..=20
Old nodes won't know how to check the witness program, which means an=20
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.
>=20
> 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.
>=20
> > On Nov 1, 2017, at 1:43 AM, Luke Dashjr <luke@dashjr.org> wrote:
> >=20
> > Mark,
> >=20
> > I think I have found an improvement that can be made.
> >=20
> > 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.
> >=20
> > Would there be any harm in, instead of checking membership, *calculatin=
g*
> > 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.
> >=20
> > 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.
> >=20
> > What do you think?
> >=20
> > Luke
> >=20
> >> 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:
> >>=20
> >> * 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=A1=AFs 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.
> >>=20
> >> There were a bunch of other small modifications, typo fixes, and
> >> optimizations that were made as well.
> >>=20
> >> 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.
> >>=20
> >> Thank you,
> >> Mark Friedenbach
> >>=20
> >>> On Sep 6, 2017, at 5:38 PM, Mark Friedenbach <mark@friedenbach.org>
> >>> 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