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
|
Return-Path: <user@petertodd.org>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 99C7EE89;
Sun, 6 Oct 2019 09:12:34 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from outmail148101.authsmtp.com (outmail148101.authsmtp.com
[62.13.148.101])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 92BD527B;
Sun, 6 Oct 2019 09:12:31 +0000 (UTC)
Received: from punt24.authsmtp.com (punt24.authsmtp.com [62.13.128.105])
by punt16.authsmtp.com. (8.15.2/8.15.2) with ESMTP id x969CTKn081868;
Sun, 6 Oct 2019 10:12:29 +0100 (BST)
(envelope-from user@petertodd.org)
Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237])
by punt24.authsmtp.com. (8.15.2/8.15.2) with ESMTP id x969CTXQ010131;
Sun, 6 Oct 2019 10:12:29 +0100 (BST)
(envelope-from user@petertodd.org)
Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com
[52.5.185.120]) (authenticated bits=0)
by mail.authsmtp.com (8.15.2/8.15.2) with ESMTPSA id x969CQC4073814
(version=TLSv1.2 cipher=ECDHE-RSA-AES256-GCM-SHA384 bits=256 verify=NO);
Sun, 6 Oct 2019 10:12:27 +0100 (BST)
(envelope-from user@petertodd.org)
Received: from [127.0.0.1] (localhost [127.0.0.1])
by petertodd.org (Postfix) with ESMTPSA id 627754015C;
Sun, 6 Oct 2019 09:12:26 +0000 (UTC)
Received: by localhost (Postfix, from userid 1000)
id C712E1FF74; Sun, 6 Oct 2019 05:12:21 -0400 (EDT)
Date: Sun, 6 Oct 2019 05:12:21 -0400
From: Peter Todd <pete@petertodd.org>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <20191006091221.pq4utwocwwzqir3h@petertodd.org>
References: <20191001155929.e2yznsetqesx2jxo@erisian.com.au>
<CR-etCjXB-JWkvecjDog4Pkq1SuLUgndtSrZo-V4f4EGcNXzNCeAHRvCZGrxDWw7aHVdDY0pAF92jNLb_Hct0bMb3ew6JEpB9AfIm1tSGaQ=@protonmail.com>
<CAEM=y+XbP3Dn7X8rHu7h0vbX6DkKA0vFK5nQqzcJ_V+D4EVMmw@mail.gmail.com>
<C1OLL5FLxdOgfQ_A15mf88wIyztDapkyXJ2HZ0HxwmQADhRXGRe3le7Veso4tMIlbis6I0qiCd22xug5_GCKtgrjGnBtojWxOCMgn1UldkE=@protonmail.com>
<CAEM=y+WCGSF_=WXpgXJUZCZcGUQhxzXF6Wv1_iX+VwEyYSWypg@mail.gmail.com>
<CAD5xwhi7=5eiv1jjf72-rUezZMfj3caR+PGfZEa8i8rjNjodFg@mail.gmail.com>
<20191004111536.w7snbgpoe27xutfu@petertodd.org>
<CAD5xwhhLd9Ufv50kOi+yaJ5dTX9LhB1dPsK_0bqjz038tChcjw@mail.gmail.com>
<20191005154902.ck236q65xha25ore@petertodd.org>
<g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
protocol="application/pgp-signature"; boundary="setj5nm27l6ugmn7"
Content-Disposition: inline
In-Reply-To: <g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com>
User-Agent: NeoMutt/20170113 (1.7.2)
X-Server-Quench: 6b6d5756-e819-11e9-b106-8434971169dc
X-AuthReport-Spam: If SPAM / abuse - report it at:
http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZIVwkA IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
bgdMdgQUF1YAAgsB Am8bWlReUV97W2s7 bghPaBtcak9QXgdq
T0pMXVMcXAxuCG9g dRoeVRp6dgEIeXZ3 Y04sWCJdCEF9cEBg
F0ZVHHAHZDJpdTIe UEZFfwdXdApNfx5D YwQsGhFYa3VsGiM3
HxM1PjY+eDlSNhEd cQsMMVkVQEBOEjMi clglJQIENHFNWCwo
ZyYreBY3G0ANM0Mv MF0uEU4YPn1aBgxF FFxWGy5eIREITS02
EUtcWk8YCCBBCWAU Cxs5OgVFHDtPRkIA
X-Authentic-SMTP: 61633532353630.1024:706
X-AuthFastPath: 0 (Was 255)
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
anti-virus system.
X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,RCVD_IN_DNSWL_LOW
autolearn=ham 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>,
"lightning-dev@lists.linuxfoundation.org"
<lightning-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the
discussion about noinput / anyprevout
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: Sun, 06 Oct 2019 09:12:34 -0000
--setj5nm27l6ugmn7
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable
On Sun, Oct 06, 2019 at 08:46:59AM +0000, ZmnSCPxj wrote:
> > Obviously with care you can get the computation right. But at that poin=
t what's
> > the actual advantage over OP_CAT?
> >
> > We're limited by the size of the script anyway; if the OP_CAT output si=
ze limit
> > is comparable to that for almost anything you could use SHA256STREAM on=
you
> > could just as easily use OP_CAT, followed by a single OP_SHA256.
>=20
> Theoretically, `OP_CAT` is less efficient.
>=20
> In cases where the memory area used to back the data cannot be resized, n=
ew backing memory must be allocated elsewhere and the existing data copied.
> This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case wh=
ere we add 1 byte per `OP_CAT` and each time find that the memory area curr=
ently in use is exactly fitting the data and cannot be resized in-place).
In even that degenerate case allocators also free memory.
Anyway, every execution step in script evaluation has a maximum output size,
and the number of steps is limited. At worst you can allocate the entire
possible stack up-front for relatively little cost (eg fitting in the MB or=
two
that is a common size for L2 cache).
> Admittedly a sufficiently-limited maximum `OP_CAT` output would be helpf=
ul in reducing the worst-case `OP_CAT` behavior.
> The question is what limit would be reasonable.
> 64 bytes feels too small if one considers Merkle tree proofs, due to ment=
ioned issues of lack of typechecking.
256 bytes is more than enough for even the most complex summed merkle tree =
with
512-byte hashes and full-sized sum commitments. Yet that's still less than =
the
~500byte limit proposed elsewhere.
--=20
https://petertodd.org 'peter'[:-1]@petertodd.org
--setj5nm27l6ugmn7
Content-Type: application/pgp-signature; name="signature.asc"
-----BEGIN PGP SIGNATURE-----
iQIzBAEBCAAdFiEE0RcYcKRzsEwFZ3N5Lly11TVRLzcFAl2Zr/EACgkQLly11TVR
LzdV5RAAkJHnMLZ3v5AfTRoymKnSMbDDSvJQlGx3Yq+LYPG1iLm9ESTFS1F2tUYz
p9HpxYcAr2tB3h6rLaivzrmXJOTDOR3xUEKgroT5nnwteNOHDohp8Q6briGPC042
t/Ame3qEBUzVx6SqGdmBV9UbjhXs4ogAWAvhuVSb40PNdHFlHrav+h5PCthNNrcJ
xYUDDma5oY8iTo7j+QarTcjOSZpNUYiOT2OJXp48UbSGtm4L+QF91oHTFCejtduK
OvJyRsRoglh6lMOZB6J5Vx+OqxweCkhuidDJQXFLUW6NgIBtllxWULXmoh74It/F
zDnEv6wfoinhn1gzCOh0vGarhDDu11ZsoQGMvizjrV73C89nWxydfQjn603L8Oj/
S6NVeAcUOBOIIt2xCLg+RyXj0kI6WoY3co16pt0LZrJ/8Bo5kJOq6S9WeujyyeVD
xnhE6PVAJluPOfcOFyJGNfi3TSo0BEUR7hJ2p4LBaHAeQi2sp2HJ1J3x93q9U6Ig
GYkYPjLdizzQITt3W8EI86Ibfmi1/LA3mINjmGwbQZ4lbTwmKKC8bp0j+IL0rXLx
h3PnhGhGvQ9vXaiQBjqWXmAUDh+fkHBxDMZtg/B6ZqwqAWHGIMqLtBA6vAfB7Gt2
DA/WdxesU4Jw7tZDKQRW9N51gGlS8adF4KX3gpCjAngP9VaCWNs=
=/dbf
-----END PGP SIGNATURE-----
--setj5nm27l6ugmn7--
|
