CAT, Scripts and Lamport Sigs
In 2021, Jeremy Rubin showed that it is possible to do 32-bit Lamport signatures in Bitcoin Script, without any changes to the network. This development, while independently interesting for some oracle applications, has really shown its value by its use in BitVM, an aggressively ambitious project by Robin Linus to do arbitrary computations in Script by splitting them across dozens of transactions indexing billion-entry Merkle trees. The core idea is that we can think of Lamport signatures as indexing a sort of "global key-value store" supporting single writes and erasures, where each entry has an owner. We discuss this idea, as well as how it generalizes using OP_CAT beyond 32-bit values to "real" signatures, commitments to Merkle trees, and more.
