lightning-dev
OP_CAT was Re: Continuing the discussion about noinput / anyprevout
Posted on: October 6, 2019 09:12 UTC
In an email conversation, ZmnSCPxj and Peter Todd discussed the efficiency of OP_CAT compared to SHA256STREAM.
ZmnSCPxj stated that theoretically OP_CAT is less efficient as it can have a degenerate case where new backing memory must be allocated elsewhere and the existing data copied resulting in possible O(n^2) behavior. However, every execution step in script evaluation has a maximum output size, and the number of steps is limited, so even in the worst-case scenario, the entire possible stack can be allocated upfront at relatively little cost. ZmnSCPxj also suggested that a sufficiently-limited maximum OP_CAT output would be helpful in reducing the worst-case behavior. However, 64 bytes feels too small for Merkle tree proofs due to the lack of typechecking. Instead, 256 bytes should be more than enough for even the most complex summed merkle tree with 512-byte hashes and full-sized sum commitments. This limit is still less than the proposed ~500byte limit.