Author: Peter Todd 2019-10-06 09:12:21
Published on: 2019-10-06T09:12:21+00:00
In a discussion about the advantages of using SHA256STREAM over OP_CAT in script evaluation, ZmnSCPxj argued that theoretically, OP_CAT is less efficient. This is because new backing memory must be allocated elsewhere and the existing data copied if the memory area used to back the data cannot be resized, leading to possible behavior that is O(n^2). However, even in that degenerate case, allocators also free memory. The number of steps in script evaluation has a maximum output size, and the worst-case scenario is when the entire possible stack is allocated up-front for relatively little cost. A sufficiently-limited maximum OP_CAT output would be helpful in reducing the worst-case behavior, but the question of what limit would be reasonable arises. A 64-byte limit feels too small for Merkle tree proofs due to issues of lack of typechecking, whereas 256 bytes is more than enough for even the most complex summed merkle tree with 512-byte hashes and full-sized sum commitments. Yet this is still less than the ~500byte limit proposed elsewhere.
Updated on: 2023-06-13T21:42:54.974074+00:00