# Lamport signatures and other CAT tricks **URL:** \ **Category:** Protocol Design\ **Created:** [December 2, 2023, 11:15pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236 "2023-12-02T23:15:49Z")\ **Posts on this page:** 20\ **Page:** 1
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 2, 2023, 11:15pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/1 "2023-12-02T23:15:49Z")
Looking for some feedback on this contract. Is there a way to make it more efficient? What limitations on script might affect it? this would be fed about 4-5KB of “signature” data, including 140x 20 byte hashes merkle control bytes 20 preimages and sighash bytes. Would it be possible to run this on inquisition signet? Does it even make sense to attempt quantum resistant signatures in taproot given how the P2TR output is formed? Could we soft-fork taproot to enable script-only if needed? ```auto // witness script // *** 1 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 1 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 1 push state to alt-stack OP_TOALTSTACK // // *** 2 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 2 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 2 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 3 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 3 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 3 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 4 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 4 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 4 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 5 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 5 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 5 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 6 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 6 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 6 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 7 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 7 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 7 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 8 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 8 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 8 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 9 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 9 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 9 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 10 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 10 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 10 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 11 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 11 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 11 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 12 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 12 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 12 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 13 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 13 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 13 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 14 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 14 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 14 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 15 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 15 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 15 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 16 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 16 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 16 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 17 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 17 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 17 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 18 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 18 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 18 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 19 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 19 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 19 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** 20 byte of OP_DUP OP_TOALTSTACK // OP_CAT OP_HASH160 // 1 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 2 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 3 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 4 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 5 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 6 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 7 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // 8 of 20 merkle verify step OP_IF OP_SWAP OP_ENDIF OP_CAT OP_HASH160 // *** 20 update state on alt-stack OP_FROMALTSTACK // // stack: ... | alt-stack: OP_FROMALTSTACK OP_SWAP OP_FROMALTSTACK OP_CAT OP_TOALTSTACK OP_CAT OP_HASH160 OP_TOALTSTACK // *** finished building the sighash and pubkey OP_FROMALTSTACK // <0x04396be4408229b5097d2092aa74bdf61e245828> OP_EQUALVERIFY OP_FROMALTSTACK // ``` UX notes: The user would have a “private key” (256 bit) which can be generated with a BIP-32 HD wallet, the private key is used as seed for hardened BIP-32 derivation of the preimages for each position and byte value. Then a merkle tree is built for each “sighash” bytes and their roots are hash aggregated in a way that is compatible with this contract. This “root hash” acts as the “public key” as it commits to all of the merkle trees and is deterministically generated from the private key. Some introspection must follow this contract to check the transaction’s conformity to the “sighash” which is the left on top of the stack at the end. ---
**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\ **Post date:** [December 3, 2023, 7:39am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/2 "2023-12-03T07:39:02Z")
This requires separate pushes of `0` or `1` for each level of each merkle tree to decide what branch you want. I don’t think you can do better than that with just CAT, but if you had `DIVMOD` (takes `s1, s2` from the stack, pushes `int(s1/s2)` then `s1%s2` onto the stack; cf elements’ `OP_DIV64`) you could provide a leaf number, and execute something like: `ROT ROT 2 DIVMOD 2SWAP ROT IF SWAP ENDIF CAT HASH160` to combine a path towards the root (starting stack is: `[path, n, hash]`). It’s 6B more script per level, vs 2 bytes less witness data per level, so unlikely to be interesting unless you’re running into stack size limits, or also adding a looping construct You could also consider an `OP_STR_LESSTHAN` that compares two byte vectors, and code it as `STR_LESSTHAN NOTIF SWAP ENDIF CAT HASH160`, and construct the merkle tree with an implicit order. I think your script’s idea is: - to create a single-use pubkey, you generate 20 byte commitments. - for each byte commitment, you create a merkle tree where the leaves are “nonce ++ byte” - the single-use pubkey is then the hash of the concatenation of its commitment roots To verify a signature, you then: - for each byte of the message hash, you reveal the path to the nth commitment for the pubkey - you combine the commitment roots to produce the single use pubkey - you check the pubkey is what you expect - you’re left with the msg hash on the stack, which you might then verify by constructing a signature verification with R=P=G, or could compare directly with the result of ` TXHASH HASH160` or similar. There’s a couple of stack optimisations you could do (you’ve got a TOALT immediately followed by a FROMALT, eg), but I don’t think there’s much else to be done, without some sort of looping construct. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 3, 2023, 10:33am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/3 "2023-12-03T10:33:10Z")
Thank you for the feedback @ajtowns! What do you think about soft-fork restricting G from being used as internal pubkey for taproot (it’s an obvious anyone can spend), to have a quantum resistant script-only P2TR output? Could also be a specific NUMS point used by convention in the meantime, with the promise that it gets protected as needed, if that makes more sense? ---
**Author:** ![ajtowns](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/ajtowns/32/417_2.png) [@ajtowns](https://delvingbitcoin.org/u/ajtowns)\ **Post date:** [December 3, 2023, 12:14pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/4 "2023-12-03T12:14:11Z")
That doesn’t work – if you can solve the discrete log, you just spend via the key path without ever revealing that the internal pubkey was G. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 3, 2023, 2:49pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/5 "2023-12-03T14:49:04Z")
Yes, that’s what I would like to disable (opt-in). My thinking was that for keyspend revealing the preimage `t` of the tweak is required. So then the clients could check if `Q = point_add(G, point_mul(G, t))` and then say NOPE! _But i guess an adversary could just calculate a different_ `(a+b)G = (t+1)G` _, is what you meant._ Is there a way to force script only and retain compatibility with the current address format? ---
**Author:** ![sipa](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/sipa/32/1100_2.png) [@sipa](https://delvingbitcoin.org/u/sipa)\ **Post date:** [December 3, 2023, 3:06pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/6 "2023-12-03T15:06:34Z")
Key path spends don’t reveal the tweak at all. They’re just BIP340 signatures for the key in the output (which is typically the tweaked key), nothing more. If you want to retain security if DL is no longer assumed to be hard, you need to disable key path spends, no way around it. As long as SHA256 remains preimage resistant, script path spends remain secure (obviously only under the assumption the script itself isn’t vulnerable to a DL break). ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 3, 2023, 3:24pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/7 "2023-12-03T15:24:03Z")
Yes, thank you! We were discussing this with @reardencode and figured you could force revealing additional information in the annex maybe, like the script hash and enforcing the tweak and it’s commitment to the pubkey in validation. In general there might be no point in allowing keyspends then. My thinking was, at first it might be prohibitively expensive to go after everyone. Large treasuries and old P2PK coinbase outputs would be the first targets. Of those, treasuries are the one that might prepare a quantum proof ‘exit hatch’ in advance especially if it costs them next to nothing. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 3, 2023, 3:52pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/8 "2023-12-03T15:52:18Z")
So basically this script is not implementable on bitcoin in any meaningful way, even if CAT was soft-forked in… 🥲 ---
**Author:** ![ZmnSCPxj](https://delvingbitcoin.org/letter_avatar_proxy/v4/letter/z/ee7513/32.png) [@ZmnSCPxj](https://delvingbitcoin.org/u/ZmnSCPxj)\ **Post date:** [December 5, 2023, 12:32pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/9 "2023-12-05T12:32:13Z")
If we are willing to softfork something in that allows Lamport and other ttricks and re-enabling of `OP_CAT` (and converting all `OP_NOP` to `OP_SUCCESS`), then maybe we can use a different P2SH-like encoding? i.e. instead of `OP_HASH160 OP_EQUAL` as in P2SH, create a new P2XSH with template `OP_HASH256 OP_EQUAL`. If this template is recognized, then the softfork version expects the script top to be equivalent to a `0xC0`-version script as in tapleaf, including `OP_SUCCESS`. Then you can execute any extensions supported inside `0xC0`-version tapleaves in the P2XSH script, including `OP_CAT` if that is enabled inside tapscript version `0xC0`. This lets you avoid any quantum-non-resistant paths on the way to the script. (Or maybe just make it into a tapleaf so include the version to the front of the script. sort of thing) ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [December 5, 2023, 3:06pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/10 "2023-12-05T15:06:11Z")
It would be nice to have something like P2SH/P2WSH where the script is like tapscript in upgradeability and relaxed limitations. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [February 8, 2024, 4:02pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/11 "2024-02-08T16:02:00Z")
CAT can be used to solve the data availability problem for LN-symmetry ```plaintext # S = 500000000 # IK -> A+B | CTV SHA256 CAT IK CSFSV CLTV ``` before funding sign first state template: ```plaintext # state-n-hash { nLockTime(S+n), out(contract, amount(A)+amount(B)) } # settlement-n-hash { nSequence(2w), out(A, amount(A)), out(B, amount(B)) } # state-n-recovery-data { settlement-n-hash or state-n-balance } # contract for state n < m IF | CTV SHA256 CAT IK CSFSV CLTV ELSE CTV ENDIF ``` `CLTV` ensures only a larger `nLockTime` transaction can spend the current on-chain state, the relative timelock for the last co-signed state’s `CTV` distribution is committed to in the `settlement-hash` to recover the script for state n in case it’s not the final state, `settlement-n-hash` can be abbreviated to 7 bytes `state-n-balance` in cases where the state can be represented as a simple balance (no HTLCs) signing a concatenated string ensures critical data availability, and therefore only the latest state needs to be kept. **edit:** as @JeremyRubin pointed out, the naive implementation is malleable and insecure, because the CTV operation is only defined for 32 byte parameters. by adding an extra SHA256 over the CTV template hash, and then concatenating it for signature check we make the template and the composite message immutable. (alternatively we could use several opcodes for a precise size check) `message = state-m-recovery-data|hash(state-m-hash)` **sidenote:** _a ‘neutered’ version of `OP_CAT` could be limited to producing only 80 byte long strings maximum, which allows for a number of harmless use cases like lamport signatures, 0-conf bonds and other nonce point manipulation schemes, and also for a more vbyte efficient channel closure, without enabling detailed introspection and finite state machines and other possibly undesired or highly contentious MEVil related behaviors without explicit future authorization._ _said restriction can even be temporary (up to a specific block height), and reinforced with a future soft fork if still desired, or left to expire if the concerns become moot._ ---
**Author:** ![harding](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/harding/32/925_2.png) [@harding](https://delvingbitcoin.org/u/harding)\ **Post date:** [February 9, 2024, 3:13am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/12 "2024-02-09T03:13:23Z")
> [@moonsettler](#): > > CAT can be used to solve the data availability problem for LN-symmetry What is the data availability problem for LN-symmetry? (Sorry if it’s something obvious and I’m just blanking on it.) ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [February 9, 2024, 11:15am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/13 "2024-02-09T11:15:55Z")
no, perfectly fair question! my bad for not explaining. so the issue is, when the channel coins are moved by your peer to a new address, and that is not the final state that you recognize, you need to have all the non-deterministic pieces of the script to reconstruct it and be able to spend with the latest state you kept. a lot can be reconstructed from the nLockTime to which CTV commits to so it’s not alterable. that gives you precisely which state are you looking at. but the final settlement hash depends on the balance between the peers and the HTLCs if there are any. so you can boil it down, to having to know the time locked settlement CTV template hash. one goal of LN-symmetry is to have leaner channel state and better backup and recovery assumptions. therefore the critical data for recovery needs to be retrievable from the transaction that spends to an intermediate state. OP\_RETURN output can be used for this, but that is 4x more expensive than SegWit space. **other possible options are:** - CTV committing to the taproot annex, and annex being enabled in relay policy (APO approach) - VECTORCOMMIT opcode, hash(hash(m1)|hash(m2)|…|hash(m16)), where hash is taggedSha256 purposfully made to be incompatible with SIGHASHING to avoid ‘sneaky CAT’ - nCSFS/V where you can optionally commit to multiple messages (integrated VECTORCOMMIT into CSFS/V) … ---
**Author:** ![harding](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/harding/32/925_2.png) [@harding](https://delvingbitcoin.org/u/harding)\ **Post date:** [February 11, 2024, 7:03pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/14 "2024-02-11T19:03:26Z")
Sorry, I’m still confused. > [@moonsettler](#): > > when the channel coins are moved by your peer to a new address, and that is not the final state that you recognize, you need to have all the non-deterministic pieces of the script to reconstruct it and be able to spend with the latest state you kept. Is this about your peer having a later state than you have, so you need to be able to put the settlement transaction onchain in order to be able to spend your outputs? Or is it about you having a later state than your peer has published, so you need to be able to spend their onchain state to your state (i.e., rebinding your state to the state they published)? For settlement tranactions where you’ve lost state, don’t we just assume that the remote peer will put the transaction onchain and that you’ll be able to identify your outputs? For rebinding, isn’t that what APO provides? ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [February 11, 2024, 10:04pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/15 "2024-02-11T22:04:22Z")
> [@harding](#): > > is it about you having a later state than your peer has published, so you need to be able to spend their onchain state to your state (i.e., rebinding your state to the state they published)? yes. it’s about spending an earlier state to the latest you know. presumably you have the settlement transaction details for that. ---
**Author:** ![cguida](https://delvingbitcoin.org/letter_avatar_proxy/v4/letter/c/87869e/32.png) [@cguida](https://delvingbitcoin.org/u/cguida)\ **Post date:** [February 11, 2024, 10:42pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/16 "2024-02-11T22:42:14Z")
@harding See the part of the draft spec [here](https://github.com/instagibbs/bolts/blob/a17b60f42077a785c625430e8f6e8e2828d4d898/XX-eltoo-transactions.md#rationale-1) where instagibbs uses the annex to store the tapleaf for the previous settlement transaction, inside the witness for the invalidated update transaction. Without the tapleaf for the old settlement transaction, there’s no way to spend the old update transaction into the new update transaction, without storing every old settlement transaction’s output amounts and htlcs (or, tapleaves) in the database, which Symmetry tries to avoid. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [February 15, 2024, 10:44am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/17 "2024-02-15T10:44:20Z")
_copy pasta from the CAT github PR for those that don’t follow:_ Some of us have been playing with the idea of neutered CAT: instead of the MAX\_SCRIPT\_ELEMENT\_SIZE (520 bytes) the maximum output size would be 80 bytes. **Rationale:** It explicitly disables open ended second order effects by removing the ability to assemble a SIGHASH or CTV template on the stack for more detailed introspection than intended. If such introspection behavior is desired in the future it can be explicitly enabled by specialized and more efficient opcodes. Combined with CSFS it can be used as a signed datacarrier, for which the ‘standard’ limit is 80 bytes, it also has to be smaller than 84 bytes which is required for building CTV templates on the stack, and larger than 64/65/72 bytes which are respectively needed for: - Merkle inclusion: 2x 20/32 byte hashes - LN-symmetry (LNhance): 2x 32 byte hashes - Separate sig: 64/72 bytes (0-conf bonds, staking contracts) Could be a livable compromise between the conservatives that want to preserve certain characteristics of bitcoin and the prometheans who want to give the developers more practical and useful tools to build with. ---
**Author:** ![salvatoshi](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/salvatoshi/32/72_2.png) [@salvatoshi](https://delvingbitcoin.org/u/salvatoshi)\ **Post date:** [February 16, 2024, 10:27am UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/18 "2024-02-16T10:27:36Z")
I [commented](https://github.com/bitcoin/bitcoin/pull/29247#issuecomment-1948016168) on github on why that does not prevent the CAT tricks. ---
**Author:** ![moonsettler](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/moonsettler/32/38_2.png) [@moonsettler](https://delvingbitcoin.org/u/moonsettler)\ **Post date:** [February 16, 2024, 12:18pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/19 "2024-02-16T12:18:37Z")
interesting! do we have an example script (even just a partial like a single cycle), how this could look like? we are talking abut calculating any 32 bit portion of a SHA256 hash correct? afaik the naive implementation relies on a lot of binary operations not available in bitcoin script. bitwise XOR, ROTR, SHIFTR, NOT, AND… ---
**Author:** ![salvatoshi](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/salvatoshi/32/72_2.png) [@salvatoshi](https://delvingbitcoin.org/u/salvatoshi)\ **Post date:** [February 16, 2024, 12:45pm UTC](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236/20 "2024-02-16T12:45:06Z")
It’s definitely going to be _painful_ to implement, but still it seems _feasible_. Binary operations are going to be the annoying part, but it should be fairly straightforward to obtain them with arithmetic operations working bit-by-bit, and possibly more efficiently with smarter tricks like [lookup tables](https://github.com/coins/bitcoin-scripts/blob/405f3b0dbf64115eab7035482397b322822c6d19/op_lookup.md). [Next page](https://delvingbitcoin.org/t/lamport-signatures-and-other-cat-tricks/236.md?page=2)