What the heck is CatVM?

Taproot Wizards released a cartoon yesterday called CatVM. I will not refer to it as a whitepaper, those are real academic documents for adults. In the cartoon, interspersed amongst the absurd childish narratives, were a few valuable technical insights regarding different scaling proposals in the Bitcoin ecosystem. Of course, in true cartoon fashion, buried between wild exaggeration and embellishment.

The end goal of the cartoon was to propose a new mechanism for moving in and out of scaling layers built on top of Bitcoin. To disentangle that actual proposal from the cartoon, we’ll have to break down the two pieces involved.

The Building Blocks

Rijndael’s first OP_CAT experiment was constructing a vault, a scheme that allows a user to create an intermediate “staging” transaction to withdraw their funds from the vault. This kicks off a timelock, during which they can at any time send their funds back to the vault or a secure cold storage wallet, and after the timelock the user can freely withdraw the funds to the destination they chose when beginning the withdrawal process. These are the only two ways bitcoin sent to the vault script can be spent.

Explaining the full mechanics of how this is accomplished is essentially an article in itself, so I’m going to do something I usually don’t and hand waive this away as “magic.” (Explained here by Andrew Poelstra) What this “magic” allows you to do, by creating non-standard Schnorr signatures and with the help of OP_CAT, is to build the transaction the signature check is against on the script stack. This lets you enforce that certain parts of the transaction are exactly as defined ahead of time. It also allows you to put the output from a previous transaction on the stack in the process of building the transaction spending it, meaning you can compare outputs from the spending transaction against outputs from the previous transaction. This allows you to guarantee by comparing them that certain parts of the previous transaction’s outputs match certain parts of the new outputs. I.e. the script, or an amount. So you can “carry forward” parts of the old outputs into the new ones, and enforce that.

Something else you can do with OP_CAT, which did not need Rijndael tinkering and experimenting with to prove, is verify merkle tree branches. Because you can CAT stack items together, and Bitcoin already supports hashing data on the stack, you can slowly build up a merkle tree root from a leaf node with the interior nodes. Hash two pieces together to get one hash, hash that with the pair hash, and so on. Eventually you get the root hash on the stack. You can then compare it with OP_EQUAL against a predefined root hash in the locking script.

Unilateral Withdrawal

These two building blocks are enough to facilitate a unilateral withdrawal mechanism from a group shared UTXO. A merkle root can be embedded in a transaction using OP_RETURN or another mechanism that commits to a leaf node for each user. The UTXO script can be structured so that any user with a balance can attempt to withdraw it. To do so they would provide the merkle branch committing to the amount they are entitled to, the authorization proof such as a public key to check a signature against, and construct the transaction on the stack to verify the appropriate conditions are met.

Similar to Rijndael’s OP_CAT vault, this withdrawal transaction would function as a staging point. User funds would be restricted by a timelock, and they would not be capable of completing the withdrawal until it expires. At any time before the timelock expires, any other user can create a fraud proof to stop the withdrawal and shove funds back into the group UTXO script. They can do this because of OP_CAT’s ability to verify merkle trees. If someone has used a specific merkle branch to withdraw funds from the UTXO before, then that was included in a block somewhere. By constructing a transaction containing the SPV proof of that transaction inside an actual block, which can use OP_LESSTHANOREQUAL to verify the blockheader meets some minimum difficulty, they can prove on the stack that the merkle branch was used before. This allows duplicate withdrawals to be prevented.

In addition to this, because you can use the “CAT on the stack” trick to ensure specific pieces of a previous transaction must be included in the next, you can guarantee that the current merkle root is carried forward into the next transaction after a successful withdrawal. You can also guarantee that change from the withdrawal goes back into the group sharing script. This guarantees that after one user withdraws their funds, the change UTXO is locked with a script that allows any remaining user to withdraw, and so on. Any user can unilaterally withdraw their funds at any time in any order, with the guarantee that the remainder of funds are still accessible to the rest of the users.

The VM Part

Readers should be familiar with the basic idea of BitVM. You can take an arbitrary computation and break it up into each of its constituent pieces and embed them in a large taproot tree, turning that computation into a back and forth challenge/response game. This allows you to lock bitcoin with more complicated conditions than is directly supported by bitcoin script itself. The only real shortcoming is the need to craft a massive amount of pre-signed transactions to facilitate this.

The requirement to use pre-signed transactions is so that in the challenge/response dynamic, you can guarantee that coins are spent back into the large taproot tree encoding it unless an exit condition one way or the other is reached. OP_CAT and the ability to “carry forward” data from previous transactions allows you to guarantee that without needing pre-signed transactions.

So not only does this scheme allow any user to unilaterally exit on their own, it also allows locking conditions supported by a second layer that are not supported by Bitcoin script to actually be enforced in the withdrawal process. I.e. if some coins were encumbered by a smart contract the base layer doesn’t understand, and then withdrawn from the second layer, those more complicated conditions could still be settled correctly on the base layer as the coins are withdrawn.

The Missing Piece

One thing that OP_CAT does not enable is updating a merkle tree root representing user balances off-chain verifiably. It can enable an already committed state to facilitate unilateral withdrawals, but that is because a whole section of the tree is actually put on-chain and verified. To update that root off-chain by definition means you are not putting the data on-chain. This represents a problem. There is no way with just CAT to efficiently verify that all changes to the merkle tree were authorized properly by the relevant users.

Someone(s) has to be trusted, and by the nature of things capable of spending the UTXO however and wherever they want, to efficiently replace an old state root with a new one to represent all off-chain balance changes. A new opcode in addition to OP_CAT, such as OP_ZKVERIFY, would be needed to do this in a trustless manner.

This wouldn’t be the end of the world without OP_ZKVERIFY though. The entity updating the merkle root for off-chain transfers could be an n-of-n multisig, with 100% of the participants required to sign off on any root changes. This boils down to the same trust model as BitVM based pegs, where as long as a single honest participant exists, no one's funds can be stolen. It is a stark improvement over existing BitVM designs however when it comes to the withdrawal process.

In BitVM pegs, users do not have a unilateral withdrawal mechanism. Peg operators must be trusted to fulfill user withdrawals, knowing that they can claim back funds they have spent doing so relatively trustlessly from the BitVM peg. While the incentives of this are very solid, it still does require users essentially getting permission from someone else to exit the system, they cannot do it on their own. With CatVM, users can claim back their funds unilaterally, and an operator is not required to front their own liquidity to process withdrawals.

Wrapping Up

Overall, the design is incomplete in terms of construction. This is not something I would call a Layer 2 in and of itself. It is the core of one, the mechanism and structure for how funds are locked into a Layer 2, and the process for how users can withdraw their funds. It definitely has a lot of flexibility and usefulness to it.

In the worst case scenario, users do not need anyone’s permission to safely claim their funds back on-chain. It also allows more flexible programmability of funds, while still carrying the enforcement of those conditions to the base layer in the event of worst case unilateral exits. If one day we do eventually get something like OP_ZKVERIFY, the off-chain state progression can become an actually trustless process.

I don’t expect any concrete demos in the near future, but it definitely is a sound idea in my opinion, and something worth considering. It also shows that the wizards are doing a little more than just pumping stupid jpegs.