# Optimistic ZK verification using MATT

**URL:** <https://delvingbitcoin.org/t/optimistic-zk-verification-using-matt/1050>\
**Category:** Protocol Design\
**Created:** [July 31, 2024, 12:49pm UTC](https://delvingbitcoin.org/t/optimistic-zk-verification-using-matt/1050 "2024-07-31T12:49:50Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![halseth](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/halseth/32/198_2.png) [@halseth](https://delvingbitcoin.org/u/halseth)\
**Post date:** [July 31, 2024, 12:49pm UTC](https://delvingbitcoin.org/t/optimistic-zk-verification-using-matt/1050/1 "2024-07-31T12:49:50Z")

</div>

Earlier I posted about [Elftrace](https://github.com/halseth/elftrace), a tool for creating Bitcoin Scripts to verify RISC-V execution: [Verification of RISC-V execution using OP\_CCV](https://delvingbitcoin.org/t/verification-of-risc-v-execution-using-op-ccv/313)

Since then it has had some updates, and I wanted to share that the toolchain has had some additions making it easier to compile Rust without having to write custom assembly for every new program. It now also support doing input/output to the program using standard IO.

With this in place we are able to compile the **Winterfell STARK library** as a dependency, making it possible to _verify-the-verification_ of ZK proofs in Bitcoin Script (this still requires CAT and a covenant).

A more detailed writeup is here, with example code: [elftrace/docs/zk\_verifier.md at 831f537bc1509bd45c350e103f7fc73aa818f7dd · halseth/elftrace · GitHub](https://github.com/halseth/elftrace/blob/831f537bc1509bd45c350e103f7fc73aa818f7dd/docs/zk_verifier.md)

---

<div class="post-metadata">

**Author:** ![AdamISZ](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/adamisz/32/418_2.png) [@AdamISZ](https://delvingbitcoin.org/u/AdamISZ)\
**Post date:** [December 15, 2024, 4:06pm UTC](https://delvingbitcoin.org/t/optimistic-zk-verification-using-matt/1050/2 "2024-12-15T16:06:16Z")

</div>

From a very high level view and a quick read, this seems like an extremely promising direction. Can you expand a bit on the necessity for OP\_CAT and covenants? At the end of the writeup it notes

> " and use Bitcoin Script to verify its execution. In order to achieve this we need a covenant like `OP_CHECKCONTRACTVERIFY` to carry state across transactions."

Why is that needed? Is it needed in a model using fraud proofs? (I’m vaguely remembering the basic idea of bitvm and earlier optimistic rollups etc). Apologies for the slightly uneducated question 🙂

---

<div class="post-metadata">

**Author:** ![salvatoshi](https://delvingbitcoin.org/user_avatar/delvingbitcoin.org/salvatoshi/32/72_2.png) [@salvatoshi](https://delvingbitcoin.org/u/salvatoshi)\
**Post date:** [December 16, 2024, 1:09pm UTC](https://delvingbitcoin.org/t/optimistic-zk-verification-using-matt/1050/3 "2024-12-16T13:09:21Z")

</div>

In MATT, `OP_CAT` is only used for the purpose of creating vector commitments, as that enables checking Merkle proofs; other opcodes like [`OP_PAIRCOMMIT`/`VECTORCOMMIT`](https://github.com/bitcoin/bips/pull/1699) would do the job, too.

About the need for a covenant: it is used in order to execute a protocol as an arbitrary state machine across multiple UTXOs, where each ‘transition’ can do some computation on the _state_ committed in it (if any), and dynamically compute the state for the ‘next step’ (which corresponds to a different node in the state machine of the protocol). Fraud proofs for any computation are a use case. Notably, no presigned transaction is needed for such protocols, as all the possible futures are directly preprogrammed in Script thanks to the covenant.

I sketched the fraud proofs in the [initial post about MATT](https://gnusha.org/pi/bitcoindev/CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com/) (starting from _Commitments to computation and fraud challenges_), with a toy example [here](https://gnusha.org/pi/bitcoindev/CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com/). There’s also a [python implementation](https://github.com/Merkleize/pymatt/blob/55c9239288ae9b4900a251bfe5d8fc0f99308491/matt/hub/fraud.py) of the bisection protocol, which contains a formal description in the comments.

I collect all the resources related to MATT at [https://merkle.fun](https://merkle.fun), if you’re interested to go more in-depth on any of these topics, or check the existing code. Please don’t hesitate to reach out if you have any question.