MATT: [demo] Optimistic execution of arbitrary programs

Johan clarifies that the variable P, representing the size of the program, does not matter in this context because the program is never put entirely on-chain. Instead, it is broken down into n steps. The commitment only denotes how to create the commitment, while the node scripts enforce consistency with the commitment when traversing the tree. Johan explains that participants agree upfront on the exact length of the trace or the depth of the tree. If the actual execution is shorter, the remaining steps are filled with no-ops. This allows them to know the transactions that will be played when the challenge protocol starts. If a participant creates a trace from a non-balanced state tree, it will be rejected by the script at that level. Deterministic construction of the state tree is crucial, and Johan thanks aj for pointing out a fix.

Aj questions whether "O(n log n)" is correct and suggests that it should be "O(P + log(N))" where P represents the size of the program and N is the number of steps rounded up to a power of 2. Aj also mentions the importance of knowing h(sub_node1) and h(sub_node2) directly to compare them with the results obtained from running the computation. Without direct knowledge, there is a 50/50 chance of choosing the correct subnode, resulting in odds of proving a mistake with only 1/2**N probability. Aj proposes a slight modification to the code snippet, making it 32B longer but removing some h()s. Aj raises concerns about the prover's obligation to come up with a balanced state tree, as it could allow hiding errors in places where the challenger cannot find them. Adding "start_stepcount" and "end_stepcount" might resolve this issue. Aj also points out an error in the diagram illustrating what it would look like for 4 state transitions, suggesting a correction to the second node. Lastly, Aj assumes that the counterparty verifies their knowledge of the program (all leaves in the contract taptree) before agreeing to the contract.

Overall, this email exchange focuses on clarifying the correct notation for complexity analysis, discussing the importance of knowing subnodes directly, addressing concerns about balanced state trees, and identifying errors in the diagram. Both parties provide valuable insights and propose potential solutions.