MATT: [demo] Optimistic execution of arbitrary programs

The email discusses the misconception about the time complexity notation "O(n log n)" and suggests an alternative notation "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. The sender argues that directly knowing the values of h(sub_node1) and h(sub_node2), which are required for comparison during computation, is necessary to avoid a 50/50 chance of choosing the incorrect subnode. Additionally, it is mentioned that this change would only result in an increase of 32B in size and remove some instances of the h() function.

The sender raises a concern about the requirement for a balanced state tree in the prover's proof. Without enforcing balance, there could be multiple possible trees for the same execution trace, making it easier to hide errors. To address this, the suggestion is made to include "start_stepcount" and "end_stepcount" parameters, which would ensure a balanced tree structure.

A correction is pointed out in the diagram illustrating the scenario with 4 state transitions. The second node should show "0|0|2 -> 0|1|4," combining its two children, instead of "0|0|2 -> 1|0|2," matching its left child.

It is assumed that the counterparty verifies their knowledge of the program (i.e., all the leaves in the contract taptree) before agreeing to the contract. This verification step is considered acceptable.

Overall, the email addresses various concerns related to time complexity notation, tree balance, and verification processes in programming contracts.