Proposal: OP_STARK_VERIFY - Native STARK Proof Verification in Bitcoin Script

The discussion revolves around the practical considerations of resource usage within proof systems, specifically focusing on the trade-offs related to proof sizes and verification times. The interest lies in understanding how these factors impact the feasibility and efficiency of implementing such systems in decentralized contexts, like blockchain technology. Proof sizes are highlighted as varying significantly, usually ranging from hundreds of kilobytes to 1 megabyte uncompressed. However, it is noted that compression techniques, such as bzip2, have the potential to substantially reduce these sizes to below 100 kilobytes in many instances.

A critical concern raised involves the implications of adopting a proof system with proof sizes exceeding 400 kilobytes. Specifically, it points out the challenges this could pose for decentralized block building and relay activities due to the unpredictability of mining timings. Moreover, the on-chain verification time is mentioned to be in the order of tens of milliseconds on standard hardware, which could consume a significant portion of the verification "budget" of an entire block, especially when aiming for average block times of around 100 milliseconds. The discussion suggests that establishing a defined target for what constitutes an "average" block size is essential for consistent application across different scenarios.

Additionally, questions are posed regarding the application of Circle STARKs, particularly in terms of their resource demands in both proof sizes and verification times. While Circle STARKs are acknowledged as being feasible and demonstrated, they are also described as highly inefficient and complex, pushing much of this complexity into Script. There's an inquiry about the integration of Circle STARKs within Bitcoin Script using CAT, as well as their compatibility with Simplicity using currently defined JETs. The desire for a more detailed understanding of the benefits derived from making a specific STARK prover into a "JET" beyond general qualitative assessments (i.e., low, medium-high, high) is expressed, underscoring the need for clear, actionable insights into the trade-offs involved in such technological choices.