OP_CAT was Re: Continuing the discussion about noinput / anyprevout

In a recent email exchange on the Lightning-dev mailing list, Jeremy raised the question of whether using OP_SHA256STREAM for constructing midstate in scripts would be an advantage over using OP_CAT. While it is possible to compute using OP_SHA256STREAM and get the computation right with care, there may not be any actual advantage over OP_CAT. In fact, if the output size limit for OP_CAT is comparable to that of almost anything you could use SHA256STREAM on, then using OP_CAT followed by a single OP_SHA256 would be just as easy.However, theoretically, OP_CAT is less efficient than OP_SHASTREAM. In cases where memory areas used for data cannot be resized, new backing memory must be allocated elsewhere and existing data copied. This leads to possible O(n^2) behavior for OP_CAT. On the other hand, once the stream state is in place, OP_SHASTREAM would not require any copying or new allocations. The cost of executing OP_CAT may be reduced by limiting its maximum output. However, 64 bytes is too small when considering Merkle tree proofs due to issues of lack of typechecking. Overall, the discussion highlights the potential advantages and limitations of different options for constructing midstate in scripts.