From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: 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 To: ZmnSCPxj Message-ID: <20191006091221.pq4utwocwwzqir3h@petertodd.org> References: <20191001155929.e2yznsetqesx2jxo@erisian.com.au> <20191004111536.w7snbgpoe27xutfu@petertodd.org> <20191005154902.ck236q65xha25ore@petertodd.org> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="setj5nm27l6ugmn7" Content-Disposition: inline In-Reply-To: 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 , "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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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--