1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
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 E97DCA95
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 1 Nov 2017 08:44:22 +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 A726D1AD
for <bitcoin-dev@lists.linuxfoundation.org>;
Wed, 1 Nov 2017 08:44:20 +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 A574F38ABA97;
Wed, 1 Nov 2017 08:43:50 +0000 (UTC)
X-Hashcash: 1:25:171101:mark@friedenbach.org::6nYVaY+GZZ3aOgjo:aHRlz
X-Hashcash: 1:25:171101:bitcoin-dev@lists.linuxfoundation.org::DX4XskdRzdb/QxlQ:bTk6q
From: Luke Dashjr <luke@dashjr.org>
To: Mark Friedenbach <mark@friedenbach.org>
Date: Wed, 1 Nov 2017 08:43:48 +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>
<3FE16880-868C-40BA-BCC5-954B15478FB2@friedenbach.org>
In-Reply-To: <3FE16880-868C-40BA-BCC5-954B15478FB2@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="utf-8"
Content-Transfer-Encoding: quoted-printable
Message-Id: <201711010843.49771.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: Wed, 01 Nov 2017 08:44:23 -0000
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=20
commitments: first, to the particular "membership-checking script"; and the=
n=20
in that script, to the particular merkle root of possible scripts.
Would there be any harm in, instead of checking membership, *calculating* t=
he=20
root? If not, then we could define that instead of the witness program=20
committing to H(membership-check script), it rather commits to H(membership-
calculation script | data added by an OP_ADDTOSCRIPTHASH). This would, I=20
believe, securely reduce the commitment of both to a single hash.
It also doesn't reduce flexibility, since one could omit OP_ADDTOSCRIPTHASH=
=20
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:
>=20
> * Modified the hashing function fast-SHA256 so that an internal node cann=
ot
> 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=E2=80=99s 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
|
