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
|
Return-Path: <mark@friedenbach.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id D1B56B5D
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 02:03:45 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pg0-f46.google.com (mail-pg0-f46.google.com [74.125.83.46])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1D90B180
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 02:03:44 +0000 (UTC)
Received: by mail-pg0-f46.google.com with SMTP id u18so2050893pgo.0
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 11 Sep 2017 19:03:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=friedenbach-org.20150623.gappssmtp.com; s=20150623;
h=mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=5YL7yr+6JdmusgCXeN+6enCVVNajFQfxeKxSA6cuzGI=;
b=JNh9H7jEhFJPpICDd6O5P+u8L+9v7hRYWxC1SozBzyxMhSogeECUdnqYLF8RocUFag
iLUJdRoLeTYYDV+Fn5BeOsCYsFEW4h2dSpZyosOFlbuNy4OArNb9NP8jVraZSQsZaS8d
TfdND6zwi9IZluzNW0L2i40lIIrJaRqGK01/4h7ERYq5PRjza4LCgiO4t7sMdFHisPEa
fCY86Sb6sYWO5AJt+rKHL8JVxzZK8ys/qboJZgWfZFuRmVY3Hpd1mHgKeKEAhJmOlYE6
2Uoc7sreYNG6k4vw59V8NckV1dXog/bwNoxZ5efvu80gRUUBaLO35pmGY6SkZ9Qx4kOc
7uYQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc
:content-transfer-encoding:message-id:references:to;
bh=5YL7yr+6JdmusgCXeN+6enCVVNajFQfxeKxSA6cuzGI=;
b=SO45IDggOmFtwWiBcAB6XzZX3gFWaBK7KPICbDr07Zrw3gtI+Uj/a8Pq/EFI930Tk7
qF2OSBBFtYflHevJmi1MeeQQqHcTAinqWqig80nJOacDM1KmITLQEh5Be3QaDDGsjEWU
8s2ySIEJSN2XVv+sTTgLE5NFQtg3CeKx0B7/s1294fkovT4sMngwkEH345YU9TeVyYzM
kxbCo0eicjZtX+tEHpaDbGkOiaPKaIqLErFkg2GdIHINESb3jWrrDROiaS2upiIWyC6g
AialjL2uKE8lXiCgj4X3Kh9UWZ/Tq2RnoXqEJWrh0F0VpvpcCJCWyi8jJ5XGQ89PANrg
WX9w==
X-Gm-Message-State: AHPjjUj0wEEo/kYEADwbGTzllo7227eyLfgCcfZ8N6xkSH5h6cyPm0Ar
MuKvI1bQ9wb0aJhFoE5UAQ==
X-Google-Smtp-Source: AOwi7QCqNbiBpzTE0foQjKLZde/SjQr0ubXcztwZJcs/pdmeCgcJFCPI6zCY8bq3Yhm1tBUF1Yfb6w==
X-Received: by 10.84.211.36 with SMTP id b33mr2061359pli.47.1505181824306;
Mon, 11 Sep 2017 19:03:44 -0700 (PDT)
Received: from ?IPv6:2601:646:8080:1291:6d2f:4f34:9a36:6fff?
([2601:646:8080:1291:6d2f:4f34:9a36:6fff])
by smtp.gmail.com with ESMTPSA id
l27sm17341910pfg.172.2017.09.11.19.03.43
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Mon, 11 Sep 2017 19:03:43 -0700 (PDT)
Content-Type: text/plain; charset=us-ascii
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
From: Mark Friedenbach <mark@friedenbach.org>
In-Reply-To: <26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
Date: Mon, 11 Sep 2017 19:03:42 -0700
Content-Transfer-Encoding: 7bit
Message-Id: <2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
<26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
To: Johnson Lau <jl2012@xbt.hk>
X-Mailer: Apple Mail (2.3273)
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
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
X-Mailman-Approved-At: Tue, 12 Sep 2017 02:07:56 +0000
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 02:03:45 -0000
My apologies for a delay in responding to emails on this list; I have
been fighting a cold.
(Also my apologies to Johnson Lau, as I forgot to forward this to the list.)
On Sep 8, 2017, at 2:21 AM, Johnson Lau <jl2012@xbt.hk> wrote:
> 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.
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.
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.
> 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.
I disagree with this design requirement.
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.
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.
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.
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.
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.
> 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.
This is correct. Your feedback will be incorporated.
> 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.
Is there a repo that contains the latest implementation of BIP 114,
for comparison purposes?
Kind regards,
Mark Friedenbach
|
