What are MATT opcodes?

Question

There is plenty of discussion in the Bitcoin-dev mailing list about MATT opcodes, and I would like to know what these are.

Answer 1

Disclosure: I'm the author of the proposal called MATT.

MATT is an acronym for Merkleize All The Things, and is a research project for an approach to bitcoin smart contracts that only require relatively minimal changes, while allowing very general constructions.

Rather than going into the technicalities of the current proposal, let me try to explain just the core idea, with links for more in-depth reading.

Key concept: Covenants

In Bitcoin, coins are locked in UTXOs (short for Unspent Transaction Outputs). A UTXO contains the Script that specifies the conditions to spend those coins ("Alice can spend", or "Alice can spend, or Bob can spend after a month", etc.).

Today, there is no way in Bitcoin to add constraints on where coins can be spent, if the conditions in the Script are satisfied.

A script that adds such restriction is called a covenant, and that is not possible in Bitcoin today, at least not within the Script language. Adding the capability to do so in Script is an increasingly active area of research.

The covenant introduced in MATT

The core idea in MATT is to introduce the following capability to be accessible within Script:

• force an output to have a certain Script (and their amounts)
• attach a piece of data to an output
• read the data of the current input (or another one)

The first is common to many other covenant proposals, for example OP_CHECKTEMPLATEVERIFY is a long-discussed proposal that can constrain all the outputs at the same time.

In short, covenants will allow to enforce constraints on the future of those coins!

The part relative to the data is more specific: this data can be as short as a 32-byte hash, but the key is that the data of an output is not decided when the UTXO is first created, but it is dynamically computed in Script (and therefore it can depend on "parameters" that are passed by the spender). This is extremely powerful, as it allows to create some sort of "state machines" where the execution can decide:

• what is the next "state" of the state machine (by constraining the Script of the outputs)
• what is the "data" attached to the next state

I posted the precise details and implementation of the covenant opcode that allows what's described in this section, OP_CHECKCONTRACTVERIFY. The exact specs and implementation are still subject to changes at this stage.

(1) Merkleizing the data

Here we come to the second core idea: if we can only attach a single piece of data (32 bytes), how can we execute more complex "contracts" that require accessing/storing more data?

The solution is to use the 32-byte data as a commitment to a larger collection containing all the required data of the contract. This can be done with Merkle trees, which are not currently possible in Script, but become possible by adding a simple opcode like OP_CAT, that takes two stack elements and concatenates them.

It is not difficult to convince oneself that the capabilities of the covenant described above, together with the ability to compress arbitrary data in a single hash, allows chains of transactions to be programmed to perform arbitrary computation. More on this below.

(2) Merkleizing the Script

The concept of this section is not really anything new in MATT, as it was introduced in the Taproot soft fork, which is active in bitcoin since November 2021.

When you represent a contract as a Finite State Machine, you often have situations where a certain state can transition to multiple other states of the FSM.

For example, if the smart contract is encoding a game of Tic-Tac-Toe between Alice and Bob, and it's Alice's turn, one transition encodes "Alice plays her move". However, Alice might stop playing, so you likely want to allow Bob to automatically win the game if Alice doesn't play her move within 1 day. So a second "state transition" in the node that represents Alice's turn could be "After 1 day, Bob can take the money".

More complicated contracts can have many possible transitions from the same node, and taproot makes it possible by using - you guessed it - a Merkle tree of all the possible transition. Each leaf of this Merkle tree contains a bitcoin Script, as usual.

(3) Merkleizing the Execution

This section describes some more advanced applications of the ideas described above; unavoidably, this section will be the hardest to read.

What we said above is already enough to represent some very interesting smart contracts, like vaults, Rock-Paper-Scissors, and a lot more.

However, there are smart contracts that are way too expensive to execute in the way described above, simply because bitcoin Script is not powerful enough to execute complex computations (this is by design, as it helps to keep the validation efficient and cheap, which is crucial for people to be able to run bitcoin full nodes!).

Sure, one could decompose the computation in a chain of hundreds, or thousands of little state-machine updates − but this certainly does not scale!

The full writeup of the MATT proposal drafts an interesting solution to this problem, by using an idea known as fraud proofs.

It goes like this: suppose that a transition from a certain state to another state is only allowed if Alice produces an input x that satisfies a certain complicated condition. For example, x must be a prime number. Script does not have any opcode to check if a number is prime!

Therefore, we modify the contract as follows:

• Alice posts the number x (unconditionally), and the contract moves to a "Challenge phase"
• During the challenge phase, if Bob verifies that x is not prime, Bob can challenge the assertion.
• Otherwise, after some time (say, 1 day), Alice can continue as normal: she produced an x that Bob did not challenge, so it is probably a prime!

What happens if Bob does start a challenge? In that case, the contract enters a different stage: a fraud proof protocol. The protocol involves multiple transaction from both parties, but it guarantees the following: if Alice was lying, she will be exposed and lose her money; vice-versa, if she wasn't lying, Bob will lose his money. Lying is not profitable!

The details are not simple enough to attempt an explanation here, so please refer to the full write-up if interested. A simplified example of a complete fraud proof protocol and how its execution might look like within a series of bitcoin transaction was presented in this post on the bitcoin-dev mailing list.

And yes... there is another Merkle tree involved in this protocol!

Hence the meme Merkleize All The Things that became attached to the proposal.

Summing up

This research aims to find an approach to bitcoin smart contracts that is compatible with bitcoin's ethos and design goals. The new proposed opcodes are quite simple and easy to audit. Yet, they allow to create very expressive smart contracts, in a way that adds little to no additional burden to bitcoin nodes. The structure of the proposal incentivizes the construction of systems where the management of the smart contract, their storage, and (potentially) their execution are generally handled off-chain.

I hope this serves as a gentle introduction to the world of Merkle trees and bitcoin smart contracts.

Answer 2

MATT stands for "Merklize All The Things" referring to the usage of Merkle trees in current and possibly future covenant proposals (opcodes, fraud proofs etc). There are three aspects that could theoretically use Merkle trees: state, state transitions and arbitrary computations.

At the time of writing (August 2023) an opcode proposal (OP_CHECKCONTRACTVERIFY) has been formalized and implemented but earlier proposals included multiple different opcodes e.g. OP_CHECK{IN,OUT}CONTRACTVERIFY, OP_CHECK{INPUT,OUTPUT}COVENANTVERIFY, OP_PUSH_ANNEX_RECORD.

More information and a collection of links related to these covenant proposals is here.

Answer 3

It is from proposal by Salvatore Ingala regarding MATT opcodes and it is not part of the Bitcoin protocol, there are two resoures may be helpful

• [1] https://github.com/Merkleize/bitcoin/tree/checkcontractverify

• [2] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html