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
|
Return-Path: <jl2012@xbt.hk>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id BCF36978
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Sep 2017 09:21:33 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from sender-of-o52.zoho.com (sender-of-o52.zoho.com [135.84.80.217])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id A3DC3E0
for <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 8 Sep 2017 09:21:31 +0000 (UTC)
Received: from [10.7.52.189] (ip-123-255-103-154.wlan.cuhk.edu.hk
[123.255.103.154]) by mx.zohomail.com
with SMTPS id 1504862486418606.1854238651416;
Fri, 8 Sep 2017 02:21:26 -0700 (PDT)
From: Johnson Lau <jl2012@xbt.hk>
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Date: Fri, 8 Sep 2017 17:21:22 +0800
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
To: Mark Friedenbach <mark@friedenbach.org>,
bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
Message-Id: <26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
X-Mailer: Apple Mail (2.3273)
X-ZohoMailClient: External
X-Spam-Status: No, score=0.0 required=5.0 tests=RCVD_IN_DNSWL_NONE
autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.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: Fri, 08 Sep 2017 09:21:33 -0000
Some comments with the tail-call execution semantics BIP:
Tail-call execution semantics require =E2=80=9Cunclean stake=E2=80=9D, =
i.e. final stake with more than one item. However, =E2=80=9Cunclean =
stake=E2=80=9D is invalid (not just non-standard) in BIP141, so you =
could only use it with legacy P2SH (which is totally pointless=E2=80=A6.).=
A different design like OP_EVAL might be needed, or you need a new =
witness script version.
I think you have also missed the sigOp counting of the executed script. =
As you can=E2=80=99t count it without executing the script, the current =
static analysability is lost. This was one of the reasons for OP_EVAL =
being rejected. Since sigOp is a per-block limit, any OP_EVAL-like =
operation means block validity will depend on the precise outcome of =
script execution (instead of just pass or fail), which is a layer =
violation.
(An alternative is to make sigOp a per-input limit instead of per-block =
limit, just like the 201 nOp limit. But this is a very different =
security model)
Witness script versioning is by design fully compatible with P2SH and =
BIP173, so there will be no hurdle for existing wallets to pay to =
BIP114. Actually it should be completely transparent to them.
For code complexity, the minimal BIP114 could be really simple, like <30 =
lines of code? It looks complex now because it does much more than =
simply hiding scripts in a hash.
> On 7 Sep 2017, at 8:38 AM, Mark Friedenbach via bitcoin-dev =
<bitcoin-dev@lists.linuxfoundation.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
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
|
