OP_CAT Enables Winternitz Signatures

Jeremy Rubin's work has demonstrated that OP_CAT can enable Lamport signatures, leading to a script pubkey and witness stack with significant size implications when utilizing RMD-160 hashes. Building on this foundation, the discussion moves towards another post-quantum signature algorithm enabled by OP_CAT: Winternitz One Time Signatures (WOTS). Utilizing SHA256 hash chains of length 16 and a checksum compression technique inspired by the SPHINCS+ paper, WOTS offers a way to sign SHA256 hashes of an EC signature verified by OP_CHECKSIG. This method offers a more compact script and witness stack compared to Lamport signatures, even when using 256-bit hashes.

The specifics of the implementation include breaking down a 256-bit hash into 64 words of 4 bits each, followed by script manipulations to concatenate and verify these words against the EC signature's hash. A prototype implementation is available on GitHub (view prototype), demonstrating the potential for further size reductions by exploring different hash chains or optimizing the witness script. The serialized witness stack presented shows a substantial reduction in size, highlighting the efficiency of this approach.

Further discussions suggest possible optimizations, including the use of RMD-160 hash chains for improved compactness at the cost of security or experimenting with shorter Winternitz chains. These suggestions aim at refining the scheme to achieve a balance between security and practicality, especially considering the quantum resistance aspect.

The effectiveness of this approach was tested using a Bitcoin Inquisition regtest node, demonstrating its viability with example transactions provided. This development opens up avenues for testing on signet, although challenges with OP_CAT transactions being mined were noted. The sharing of resources such as the btcdeb debugging tool by kallewoof reflects the collaborative effort within the community to advance these cryptographic solutions.