Subject: Re: [bitcoin-dev] [Lightning-dev] OP_CAT was Re: Continuing the discussion about noinput / anyprevout

From: ZmnSCPxj <[email-masked]>
Date: Sun, 06 Oct 2019 08:46:59 +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 you
> 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 where we add 1 byte per `OP_CAT` and each time find that the memory area currently 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 in 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 mentioned issues of lack of typechecking.

Regards,
ZmnSCPxj

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