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
|
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 024C0AC9
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 19:57:15 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-it0-f49.google.com (mail-it0-f49.google.com
[209.85.214.49])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 07630E0
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 19:57:13 +0000 (UTC)
Received: by mail-it0-f49.google.com with SMTP id 6so1186433itl.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 12 Sep 2017 12:57:13 -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=9+7w6hbTrd2G0rZYOu8ZumhcO4GSOO1U8ie6KD4IbOM=;
b=gFaL/ZX1AbItXbiXtnt9aE3Xrrm9LfA1UIefIeR3VQ4WfzWwRIt/NsQxr1jNFDD7pE
zDkBHJzbLfw9hGNRj8lTK6/0Zs6M4t8uTnbKKfZOS/YPFtJ4mmuzTQb9KwQFkA6MtipA
wESe0NyBAz58r485QkwMLyyIvdG4AdG88Zda3gqv3+Jpu/ydM0Y/2iY31/dF4fOMjph4
HYVUo9NJOpDDgSY1BFVbPL5koYOhTpuUFX4TNQ2Gnuuo30+wC6RpvddiyoX+6BVOJqHb
th28XQyc/NTQLHjp/KGEb0q56vba7U1wo01JQ2s5WZh/ytHdGfUwyi8s4K9HAjdD/3bi
AhMg==
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=9+7w6hbTrd2G0rZYOu8ZumhcO4GSOO1U8ie6KD4IbOM=;
b=tG3kyZpjc+aRXKygS+ZfNI/h7U2x0fdRld0bkqraDuHESIlERYVDkoeqB17DL06u0K
mTM8TFBhEBTYVoGp0Pz0ewh1BdPf+wjmwJhx+psMREL7NSgu7vSIwORLlV2XWep8MXE0
DZoBA0AfHQnyA4lQHrB0x+GD+ZpWQW+iyLcKX9k01J2zPQ3guicL0NFuvANy3pwckcET
CiyCN5B2scE47UoJp0Z6JN3GlbZWSGj+XJS+k3RDzpk5V+/k0RBdjTG+/cOzRAd0QjnL
vOEgp75O3My1CbxYLVizQw5ipB9wPMpX/g0RiyvUQIAsCiBKqJpiKSeOZbLN1v75zMO3
bhDw==
X-Gm-Message-State: AHPjjUhmHd+78en5E5RiZeqirCNqkKbuopxvq5AJprHNchYEwgRM+aJi
LXqGa/J8m6+Pfki7L9Taic3/FNOnUlc=
X-Google-Smtp-Source: AOwi7QCYpeITe/GNCOMsUSHbQ/F0nwPAIIEaMEPluzEp09QpV+lWFnh/Wow6Cmui1ZZUWjIMJ68+ZA==
X-Received: by 10.36.23.88 with SMTP id 85mr1098337ith.86.1505246233303;
Tue, 12 Sep 2017 12:57:13 -0700 (PDT)
Received: from ?IPv6:2601:646:8080:1291:1d3f:a13:2924:858a?
([2601:646:8080:1291:1d3f:a13:2924:858a])
by smtp.gmail.com with ESMTPSA id
g133sm6287606iof.41.2017.09.12.12.57.10
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Tue, 12 Sep 2017 12:57:11 -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: <DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
Date: Tue, 12 Sep 2017 12:57:10 -0700
Content-Transfer-Encoding: 7bit
Message-Id: <61D84B62-0F3F-48E1-B749-F628AD91BC12@friedenbach.org>
References: <5B6756D0-6BEF-4A01-BDB8-52C646916E29@friedenbach.org>
<26AD157C-A5A9-48C3-8D29-0AD1ED35EDDD@xbt.hk>
<2419914E-E196-44B4-8663-599AF616A897@friedenbach.org>
<DA22C531-2FAE-4332-B158-A3F96BF34002@xbt.hk>
To: Johnson Lau <jl2012@xbt.hk>
X-Mailer: Apple Mail (2.3273)
X-Spam-Status: No, score=0.5 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
RCVD_IN_DNSWL_NONE, RCVD_IN_SORBS_SPAM 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 19:57:42 +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 19:57:15 -0000
On Sep 12, 2017, at 1:55 AM, Johnson Lau <jl2012@xbt.hk> wrote:
> This is ugly and actually broken, as different script path may
> require different number of stack items, so you don't know how many
> OP_TOALTSTACK do you need. Easier to just use a new witness version
DEPTH makes this relatively easy to do. Just repeat the following for
the maximum number of stack elements that might be used:
DEPTH 1SUB IF SWAP TOALTSTACK ENDIF
There are probably more compact alternatives.
Using a new script version is easier, but not faster. There's a number
of things that might be fixed in a v1 upgrade, and various design
decisions to sort out regarding specification of a witness version
(version in the witness rather than the scriptPubKey).
Tree signatures and MAST are immediately useful to many services,
however, and I would hate to delay usage by six months to a year or
more by serializing dependencies instead of doing them in parallel.
> 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
That is what I'm suggesting. And yes, there are changes that would
have to be made to the p2p layer and transaction processing to handle
this safely. I'm arguing that the cost of doing so is worth it, and a
better path forward.
> Without the limit I think we would be DoS-ed to dead
4MB of secp256k1 signatures takes 10s to validate on my 5 year old
laptop (125,000 signatures, ignoring public keys and other things that
would consume space). That's much less than bad blocks that can be
constructed using other vulnerabilities.
> 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
That's alright, I don't think it's necessary to purposefully restrict
one to compare them head to head with the same features. They are
different proposals with different pros and cons.
Kind regards,
Mark Friedenbach
|
