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
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
|
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
|
