Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 77100ACD
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun,  6 Oct 2019 08:47:06 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40136.protonmail.ch (mail-40136.protonmail.ch
	[185.70.40.136])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 8982A27B
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Sun,  6 Oct 2019 08:47:04 +0000 (UTC)
Date: Sun, 06 Oct 2019 08:46:59 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
	s=default; t=1570351621;
	bh=Bueb3/oO+DK2pt6F0p29BaQTcY1NUIK/0qtI0cUElQg=;
	h=Date:To:From:Cc:Reply-To:Subject:In-Reply-To:References:
	Feedback-ID:From;
	b=jJMlrWgb7kFbQGNYDgrDPaAwglU0Lce6qTcXK/8nJLhDRQEW0GpYHOFjli31Atxlx
	twGJVvIsMZDSge563nSwd6Ss6853QJ19EohmJpRO7V7NbpCymbH3KNX2V55jr//Pbv
	XkXyqh4Tj6rjlaDv6YD3jknI3HQc9eaonAqZO6dk=
To: Peter Todd <pete@petertodd.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <g0JWqeAd0tg8PbmrwuBRz7VP9h_-63H11oMxWzS8pQE7-awPkLlzSGmhVANp2ssbo19KJU_waNUg846YFbvh0WVSejnOMSoVo-eDl-aytpg=@protonmail.com>
In-Reply-To: <20191005154902.ck236q65xha25ore@petertodd.org>
References: <87wodp7w9f.fsf@gmail.com>
	<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>
Feedback-ID: el4j0RWPRERue64lIQeq9Y2FP-mdB86tFqjmrJyEPR9VAtMovPEo9tvgA0CrTsSHJeeyPXqnoAu6DN-R04uJUg==:Ext:ProtonMail
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
X-Spam-Status: No, score=-2.2 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID, DKIM_VALID_AU, DOS_RCVD_IP_TWICE_B, FREEMAIL_FROM,
	FROM_LOCAL_NOVOWEL, 
	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 08:47:06 -0000

Good morning Peter, Jeremy, and lists,

> On Fri, Oct 04, 2019 at 11:40:53AM -0700, Jeremy wrote:
>
> > Interesting point.
> > The script is under your control, so you should be able to ensure that =
you
> > are always using a correctly constructed midstate, e.g., something like=
:
> > scriptPubKey: <-1> OP_SHA256STREAM DEPTH OP_SHA256STREAM <-2>
> > OP_SHA256STREAM
> > <hash> OP_EQUALVERIFY
> > would hash all the elements on the stack and compare to a known hash.
> > How is that sort of thing weak to midstateattacks?
>
> Obviously with care you can get the computation right. But at that point =
what's
> the actual advantage over OP_CAT?
>
> We're limited by the size of the script anyway; if the OP_CAT output size=
 limit
> is comparable to that for almost anything you could use SHA256STREAM on y=
ou
> could just as easily use OP_CAT, followed by a single OP_SHA256.

Theoretically, `OP_CAT` is less efficient.

In cases where the memory area used to back the data cannot be resized, new=
 backing memory must be allocated elsewhere and the existing data copied.
This leads to possible O( n^2 ) behavior for `OP_CAT` (degenerate case wher=
e we add 1 byte per `OP_CAT` and each time find that the memory area curren=
tly in use is exactly fitting the data and cannot be resized in-place).

`OP_SHASTREAM` would not require new allocations once the stream state is i=
n place and would not require any copying.


This may be relevant in considering the cost of executing `OP_CAT`.

Admittedly a sufficiently-limited  maximum `OP_CAT` output would be helpful=
 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 mentio=
ned issues of lack of typechecking.


Regards,
ZmnSCPxj


>
> -------------------------------------------------------------------------=
---------------------------------------------------------------------------=
---------------------------------------------------------------------------=
---------------------------------------------------------------------------=
----------------------------------------
>
> https://petertodd.org 'peter'[:-1]@petertodd.org
>
> Lightning-dev mailing list
> Lightning-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/lightning-dev