MATT: [demo] Optimistic execution of arbitrary programs

The sender proposes that it should be denoted as "O(P + log(N))" where P represents the size of the program and N represents the number of steps (rounded up to a power of 2). However, the recipient disagrees with this suggestion and explains that it is necessary to directly know the values of h(sub_node1) and h(sub_node2) in order to compare them to the results obtained from running the computation. Without this direct knowledge, there is a 50/50 chance of choosing the incorrect subnode, making it difficult to prove a mistake with odds of only 1/2**N.The sender suggests an alternative representation of the nodes and leaves in the program, which would make it 32B longer but would eliminate the need for h() calculations. The proposed representation includes the start_pc, start_i, start_x, end_pc, end_i, end_x, h(sub_node1), and h(sub_node2) for nodes, and start_pc, start_i, start_x, end_pc, end_i, end_x, and null for leaves.The sender also raises a concern regarding the requirement for a balanced state tree. They argue that if a balanced tree is not mandatory, then there could be multiple possible trees for the same execution trace, making it easy to hide errors where the challenger cannot find them. To address this concern, the sender suggests adding a "start_stepcount" and "end_stepcount" to enforce a balanced state tree.Additionally, the recipient points out an error in a diagram illustrating the concept of state transitions. They clarify that the second node in the diagram should read "0|0|2 -> 0|1|4" instead of "0|0|2 -> 1|0|2", matching its left child.Lastly, the sender mentions that it is presumed that the counterparty verifies their knowledge of the program, i.e., all the leaves in the contract taptree, before agreeing to the contract. The recipient agrees with this assumption and concludes the email with a casual farewell.This email provides an introduction to the implementation of the original MATT challenge protocol. It includes a link to a write-up that provides a detailed description of how to transform a "high-level arbitrary program" into something that can be verified on-chain in Bitcoin Script. The write-up also contains instructions on running the code and inspecting the transactions using a local block explorer.The implementation utilizes the proposed opcode OP_CHECKCONTRACTVERIFY and OP_CAT. These opcodes are used to trace the execution of a program called multiply. The goal is to challenge the computation of this program in O(n logn) on-chain transactions.Unfortunately, the email does not provide any further details about the implementation or the specific challenges faced during the process. It mainly serves as an introduction to the topic and directs readers to the write-up for more information.[0] - Link to the original MATT challenge protocol: [insert link][1] - Link to the code for the multiply program: [insert link]