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
192
193
194
195
196
197
198
199
200
201
202
203
204
|
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 1DEADACA
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 08:56:11 +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 40D8C1B3
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 08:56:09 +0000 (UTC)
Received: from [10.7.12.8] (ip-123-255-103-96.wlan.cuhk.edu.hk
[123.255.103.96]) by mx.zohomail.com
with SMTPS id 1505206565817827.3094757402696;
Tue, 12 Sep 2017 01:56:05 -0700 (PDT)
Content-Type: text/plain; charset=utf-8
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Johnson Lau <jl2012@xbt.hk>
In-Reply-To: <2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
Date: Tue, 12 Sep 2017 16:55:59 +0800
Content-Transfer-Encoding: quoted-printable
Message-Id: <DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
<26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
<2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
To: Mark Friedenbach <mark@friedenbach.org>
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
Cc: bitcoin-dev <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: Tue, 12 Sep 2017 08:56:11 -0000
> On 12 Sep 2017, at 10:03 AM, Mark Friedenbach <mark@friedenbach.org> =
wrote:
>=20
> My apologies for a delay in responding to emails on this list; I have
> been fighting a cold.
>=20
> (Also my apologies to Johnson Lau, as I forgot to forward this to the =
list.)
>=20
> On Sep 8, 2017, at 2:21 AM, Johnson Lau <jl2012@xbt.hk> wrote:
>=20
>> Tail-call execution semantics require "unclean stake" , i.e. final
>> stake with more than one item. However, "unclean stake" is invalid
>> (not just non-standard) in BIP141, so you could only use it with
>> legacy P2SH (which is totally pointless....). A different design
>> like OP_EVAL might be needed, or you need a new witness script
>> version.
>=20
> I believe you meant "unclean stack," and you are correct. This was
> also pointed out last tuesday by a participant at the in-person
> CoreDev meetup where the idea was presented.
>=20
> This doesn't kill the idea, it just complicates the implementation
> slightly. A simple fix would be to allow tail-recursion to occur if
> the stack is not clean (as can happen with legacy P2SH as you point
> out, or yet to be defined version 1+ forms of segwit script), OR if
> there is a single item on the stack and the alt-stack is not empty.
> For segwit v0 scripts you then have to move any arguments to the alt
> stack before ending the redeem script, leaving just the policy script
> on the main stack.
This is ugly and actually broken, as different script path may require =
different number of stack items, so you don=E2=80=99t know how many =
OP_TOALTSTACK do you need. Easier to just use a new witness version
>=20
>> I think you have also missed the sigOp counting of the executed
>> script. As you can't 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.
>=20
> I disagree with this design requirement.
>=20
> The SigOp counting method used by bitcoin is flawed. It incorrectly
> limits not the number of signature operations necessary to validate a
> block, but rather the number of CHECKSIGs potentially encountered in
> script execution, even if in an unexecuted branch. (Admitedly MAST
> makes this less of an issue, but there are still useful compact
> scripts that use if/else constructs to elide a CHECKSIG.) Nor will it
> account for aggregation when that feature is added, or properly
> differentiate between signature operations that can be batched and
> those that can not.
>=20
> Additionally there are other resources used by script that should be
> globally limited, such as hash operations, which are not accounted for
> at this time and cannot be statically assessed, even by the flawed
> mechanism by which SigOps are counted. I have maintained for some time
> that bitcoin should move from having multiple separate global limits
> (weight and sigops, hashed bytes in XT/Classic/BCH) to a single linear
> metric that combines all of these factors with appropriate
> coefficients.
>=20
I like the idea to have an unified global limit and suggested a way to =
do it =
(https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2017-January/0134=
72.html). But I think this is off-topic here.
> A better way of handling this problem, which works for both SigOps and
> HashOps, is to have the witness commit to the maximum resources
> consumed by validation of the spend of the coin, to relay this data
> with the transaction and include it in the SigHash, and to use the
> committed maximum for block validation. This could be added in a
> future script version upgrade. This change would also resolve the
> issue that led to the clean stack rule in segwit, allowing future
> versions of script to use tail-call recursion without involving the
> alt-stack.
>=20
> Nevertheless it is constructive feedback that the current draft of the
> BIP and its implementation do not count SigOps, at all. There are a
> couple of ways this can be fixed by evaluating the top-level script
> and then doing static analysis of the resulting policy script, or by
> running the script and counting operations actually performed.
In any case, I think maintaining static analysability for global =
limit(s) is very important. Ethereum had to give up their DAO softfork =
plan at the last minute, exactly due to the lack of this: =
http://hackingdistributed.com/2016/06/28/ethereum-soft-fork-dos-vector/
Otherwise, one could attack relay and mining nodes by sending many small =
size txs with many sigops, forcing them to validate, and discard due to =
insufficient fees.
Technically it might be ok if we commit the total validation cost (sigop =
+ hashop + whatever) as the first witness stack item, but that=E2=80=99d =
take more space and I=E2=80=99m not sure if it is desirable. Anyway, =
giving up static analysability for scripts is a fundamental change to =
our existing model.
>=20
> Additionally, it is possible that we take this time to re-evaluate
> whether we should be counting SigOps other than for legacy consensus
> rule compliance. The speed of verification in secp256k1 has made
> signature operations no longer the chief concern in block validation
> times.
Without the limit I think we would be DoS-ed to dead
>> 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.
>=20
> This is correct. Your feedback will be incorporated.
>=20
>> 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.
>=20
> Is there a repo that contains the latest implementation of BIP 114,
> for comparison purposes?
You can find it here: https://github.com/jl2012/bitcoin/commits/vault
=
https://github.com/jl2012/bitcoin/commit/f3f201d232d3995db38e09b171e4d1dea=
8d04ad2
But this does more than your proposal as it allows users adding extra =
scripts when spending a coin. The rationale is described in the revised =
BIP114:
=
https://github.com/jl2012/bips/blob/vault/bip-0114.mediawiki#Additional_sc=
ripts_in_witness
So to make it functionally comparable with your proposal, the =
IsMSV0Stack() function is not needed. The new 249-254 lines in =
interpreter.cpp could be removed. The new 1480-1519 lines could be =
replaced by a few lines copied from the existing P2WSH code. I can make =
a minimal version if you want to see how it looks like
>=20
> Kind regards,
> Mark Friedenbach
>=20
|
