<p>Disclosure: I'm the author of the proposal called <em>MATT</em>.</p>
<p>MATT is an acronym for <em>Merkleize All The Things</em>, and is a research project for an approach to bitcoin smart contracts that only require relatively minimal changes, while allowing very general constructions.</p>
<p>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.</p>
<p><strong>Key concept: Covenants</strong></p>
<p>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 (&quot;Alice can spend&quot;, or &quot;Alice can spend, or Bob can spend after a month&quot;, etc.).</p>
<p>Today, there is no way in Bitcoin to add constraints on <em>where</em> coins can be spent, if the conditions in the Script are satisfied.</p>
<p>A script that adds such restriction is called a <em><a href="https://bitcoinops.org/en/topics/covenants/" rel="noreferrer">covenant</a></em>, 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.</p>
<h2>The covenant introduced in MATT</h2>
<p>The core idea in MATT is to introduce the following capability to be accessible within Script:</p>
<ul>
<li>force an output to have a certain Script (and their amounts)</li>
<li>attach a piece of data to an output</li>
<li>read the data of the current input (or another one)</li>
</ul>
<p>The first is common to many other covenant proposals, for example <a href="https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki" rel="noreferrer">OP_CHECKTEMPLATEVERIFY</a> is a long-discussed proposal that can constrain <em>all the outputs</em> at the same time.</p>
<p>In short, covenants will allow to enforce constraints on <em>the future</em> of those coins!</p>
<p>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 <em>not</em> decided when the UTXO is first created, but it is dynamically computed in Script (and therefore it can depend on &quot;parameters&quot; that are passed by the spender). This is extremely powerful, as it allows to create some sort of &quot;state machines&quot; where the execution can decide:</p>
<ul>
<li>what is the next &quot;state&quot; of the state machine (by constraining the Script of the outputs)</li>
<li>what is the &quot;data&quot; attached to the next state</li>
</ul>
<p>I posted the precise details and implementation of the covenant opcode that allows what's described in this section, <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html" rel="noreferrer">OP_CHECKCONTRACTVERIFY</a>. The exact specs and implementation are still subject to changes at this stage.</p>
<h3>(1) Merkleizing the data</h3>
<p>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 &quot;contracts&quot; that require accessing/storing more data?</p>
<p>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 <a href="https://en.wikipedia.org/wiki/Merkle_tree" rel="noreferrer">Merkle trees</a>, 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.</p>
<p>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.</p>
<h2>(2) Merkleizing the Script</h2>
<p>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.</p>
<p>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.</p>
<p>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 &quot;Alice plays her move&quot;. 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 &quot;state transition&quot; in the node that represents Alice's turn could be &quot;After 1 day, Bob can take the money&quot;.</p>
<p>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.</p>
<h2>(3) Merkleizing the Execution</h2>
<p>This section describes some more advanced applications of the ideas described above; unavoidably, this section will be the hardest to read.</p>
<p>What we said above is already enough to represent some very interesting smart contracts, like <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html" rel="noreferrer">vaults</a>, <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-May/021599.html" rel="noreferrer">Rock-Paper-Scissors</a>, and a lot more.</p>
<p>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!).</p>
<p>Sure, one could decompose the computation in a chain of hundreds, or thousands of little state-machine updates − but this certainly does not scale!</p>
<p>The <a href="https://merkle.fun" rel="noreferrer">full writeup</a> of the MATT proposal drafts an interesting solution to this problem, by using an idea known as <em>fraud proofs</em>.</p>
<p>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!</p>
<p>Therefore, we modify the contract as follows:</p>
<ul>
<li>Alice posts the number x (unconditionally), and the contract moves to a &quot;Challenge phase&quot;</li>
<li>During the challenge phase, if Bob verifies that x is <em>not</em> prime, Bob can challenge the assertion.</li>
<li>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!</li>
</ul>
<p>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!</p>
<p>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 <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021205.html" rel="noreferrer">this post</a> on the bitcoin-dev mailing list.</p>
<p>And yes... there is another Merkle tree involved in this protocol!</p>
<p>Hence the meme <em>Merkleize All The Things</em> that became attached to the proposal.</p>
<h2>Summing up</h2>
<p>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.</p>
<p>I hope this serves as a gentle introduction to the world of Merkle trees and bitcoin smart contracts.</p>

CC BY-SA 4.0
2023-08-12T19:33:22.853Z
Hi Salvatore, many thanks for that lengthy contribution. After you Merklize the UTXO set, what happens next? You end up with a single hash that represents the entire UTXO set, what do you do with this? And how do you get from there to new opcodes?
Eoin
CC BY-SA 4.0
2023-08-12T20:39:52.057Z
Hi Eoin, thanks for asking the question!

Merkleizing the UTXO set is not part of MATT (that's instead what [utreexo](https://github.com/mit-dci/utreexo) does, another project heavily relying on Merkle trees!).

In most cases, a smart contract in MATT would live entirely within one (or a few) UTXOs.

If you have a contract that requires storing multiple pieces of data, then you can use a Merkle tree to represent these different pieces of data as a single 32-byte hash, which is all the opcodes allow to store inside the UTXO.
salvatoshi
CC BY-SA 4.0
2023-08-13T12:22:58.700Z
So you are looking for a new opcode(CCV) which will facilitate the functioning of covenants in Bitcoin?
Eoin
CC BY-SA 4.0
2023-08-13T16:18:01.250Z
Yes, it's a proposal to add a new opcode that adds a covenant to bitcoin Script.
salvatoshi
CC BY-SA 4.0
2023-08-13T18:04:32.477Z
Could covenants be done off-chain, on layer 2?
Eoin
CC BY-SA 4.0
2023-08-13T18:59:38.627Z
As far as I know, not in any way that I would consider interesting; in particular, one of my primary goals in researching covenants in layer 1 is precisely to allow layer 2 constructions that are not possible today.
salvatoshi
CC BY-SA 4.0
2023-08-12T17:03:33.313Z
2023-08-12T17:03:33.313Z
salvatoshi
<p>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</p>
<ul>
<li><p>[1] <a href="https://github.com/Merkleize/bitcoin/tree/checkcontractverify" rel="nofollow noreferrer">https://github.com/Merkleize/bitcoin/tree/checkcontractverify</a></p>
</li>
<li><p>[2] <a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html" rel="nofollow noreferrer">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html</a></p>
</li>
</ul>

CC BY-SA 4.0
2023-08-11T08:22:44.973Z
Also https://merkle.fun/
Antoine Poinsot
CC BY-SA 4.0
2023-08-11T08:20:06.467Z
2023-08-11T08:20:06.467Z
Mani T
<p>MATT stands for &quot;Merklize All The Things&quot; 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.</p>
<p>At the time of writing (August 2023) an opcode proposal (<a href="https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html" rel="nofollow noreferrer">OP_CHECKCONTRACTVERIFY</a>) has been formalized and <a href="https://github.com/Merkleize/bitcoin/tree/checkcontractverify" rel="nofollow noreferrer">implemented</a> but earlier proposals included multiple different opcodes e.g. <code>OP_CHECK{IN,OUT}CONTRACTVERIFY</code>, <code>OP_CHECK{INPUT,OUTPUT}COVENANTVERIFY</code>, <code>OP_PUSH_ANNEX_RECORD</code>.</p>
<p>More information and a collection of links related to these covenant proposals is <a href="https://merkle.fun/" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2023-08-09T16:03:31.470Z
Where in the Bitcoin core github repo can I find usage of these opcodes, or are they just used in the Bitcoin-cli?
Eoin
CC BY-SA 4.0
2023-08-10T09:05:22.677Z
@EoinMcQuinn: They are early soft fork proposals and don't yet have a BIP PR or BIP number. So there is nothing in the Bitcoin Core repo or the bitcoin-cli for them. The implementation is in a fork of bitcoin-inquisition so it is possible they could be merged into the default signet at some point in the future but not the main Core repo.
Michael Folkson
CC BY-SA 4.0
2023-08-10T10:00:16.743Z
So why were the opcodes created in the first place? Who created them? What is Bitcoin Script without opcodes?
Eoin
CC BY-SA 4.0
2023-08-10T10:05:46.107Z
These are new proposed opcodes. Bitcoin Script already has other opcodes
Michael Folkson
CC BY-SA 4.0
2023-08-10T12:16:50.593Z
Where are the existing opcodes of Bitcoin Script used (not the new proposed opcodes)?
Eoin
CC BY-SA 4.0
2023-08-10T13:37:25.810Z
What do you mean by "where"? In pretty much every transaction or in the Bitcoin Core repo
Michael Folkson
CC BY-SA 4.0
2023-08-10T13:45:31.200Z
So opcodes are in the Bitcoin Core source code? Could you give an example of an opcode being used in the source code?
Eoin
CC BY-SA 4.0
2023-08-11T08:59:42.027Z
CHECKLOCKTIMEVERIFY https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L521
Michael Folkson
CC BY-SA 4.0
2023-08-11T18:07:23.643Z
Are MATT opcodes related to MAST (merklized abstract syntax tree)?
Eoin
CC BY-SA 4.0
2023-08-09T13:27:49.263Z
2023-08-09T13:34:07.497Z
2023-08-09T13:34:07.497Z
Michael Folkson
<p>There is plenty of discussion in the Bitcoin-dev mailing list about MATT opcodes, and I would like to know what these are.</p>

<merkle-tree><opcodes><covenants>
What are MATT opcodes?
Eoin
# What are MATT opcodes?

(Asked by: username_0 on 2023-08-09)

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

**Tags:** merkle-tree, opcodes, covenants


---

## 3 answers

### Answer by username_1 on 2023-08-12. Score: 8

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](https://bitcoinops.org/en/topics/covenants/)*, 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](https://github.com/bitcoin/bips/blob/master/bip-0119.mediawiki) 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](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html). 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](https://en.wikipedia.org/wiki/Merkle_tree), 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](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-April/021588.html), [Rock-Paper-Scissors](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-May/021599.html), 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](https://merkle.fun) 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](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2022-November/021205.html) 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.

> **Comments:**
> **username_0**: Hi Salvatore, many thanks for that lengthy contribution. After you Merklize the UTXO set, what happens next? You end up with a single hash that represents the entire UTXO set, what do you do with this? And how do you get from there to new opcodes?  
> **username_1**: Hi username_0, thanks for asking the question!  Merkleizing the UTXO set is not part of MATT (that's instead what [utreexo](https://github.com/mit-dci/utreexo) does, another project heavily relying on Merkle trees!).  In most cases, a smart contract in MATT would live entirely within one (or a few) UTXOs.  If you have a contract that requires storing multiple pieces of data, then you can use a Merkle tree to represent these different pieces of data as a single 32-byte hash, which is all the opcodes allow to store inside the UTXO.  
> **username_0**: So you are looking for a new opcode(CCV) which will facilitate the functioning of covenants in Bitcoin?  
> **username_1**: Yes, it's a proposal to add a new opcode that adds a covenant to bitcoin Script.  
> **username_0**: Could covenants be done off-chain, on layer 2?  
> **username_1**: As far as I know, not in any way that I would consider interesting; in particular, one of my primary goals in researching covenants in layer 1 is precisely to allow layer 2 constructions that are not possible today.  

---

### Answer by username_2 on 2023-08-11. Score: 0

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>

> **Comments:**
> **username_3**: Also https://merkle.fun/  

---

### Answer by username_4 on 2023-08-09. Score: 0

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](https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2023-July/021827.html)) has been formalized and [implemented](https://github.com/Merkleize/bitcoin/tree/checkcontractverify) 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](https://merkle.fun/).

> **Comments:**
> **username_0**: Where in the Bitcoin core github repo can I find usage of these opcodes, or are they just used in the Bitcoin-cli?  
> **username_4**: @EoinMcQuinn: They are early soft fork proposals and don't yet have a BIP PR or BIP number. So there is nothing in the Bitcoin Core repo or the bitcoin-cli for them. The implementation is in a fork of bitcoin-inquisition so it is possible they could be merged into the default signet at some point in the future but not the main Core repo.  
> **username_0**: So why were the opcodes created in the first place? Who created them? What is Bitcoin Script without opcodes?  
> **username_4**: These are new proposed opcodes. Bitcoin Script already has other opcodes  
> **username_0**: Where are the existing opcodes of Bitcoin Script used (not the new proposed opcodes)?  
> **username_4**: What do you mean by "where"? In pretty much every transaction or in the Bitcoin Core repo  
> **username_0**: So opcodes are in the Bitcoin Core source code? Could you give an example of an opcode being used in the source code?  
> **username_4**: CHECKLOCKTIMEVERIFY https://github.com/bitcoin/bitcoin/blob/master/src/script/interpreter.cpp#L521  
> **username_0**: Are MATT opcodes related to MAST (merklized abstract syntax tree)?  

---

