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)
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
Precedence: list


--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--