Proposal: OP_STARK_VERIFY - Native STARK Proof Verification in Bitcoin Script

The discussion centers around the efficiency and structure of cryptographic verifiers and provers, particularly focusing on a Simplicity rewrite of Stwo, which is highlighted as a lean and compact program. Despite common perceptions that codebases for these functions are bulky due to the inclusion of both prover and verifier components, a pure Simplicity implementation demonstrates a significantly streamlined approach. The mentioned Simplicity rewrite comprises 3,000 lines of code, reducing to merely 1,000 when excluding tests, comments, and empty lines. This size is noted to be comparable to or even smaller than other cryptography primitives like ECDSA/Schnorr, with sha2 as the sole dependency, aligning well with Bitcoin core's requirements.

The conversation further elaborates on the operational dynamics of verifiers, emphasizing their primary tasks of checking Merkle proofs and performing arithmetic within specific groups. The workload of a verifier is influenced by the proof's structure, which varies logarithmically with the trace length and linearly with the trace width. These dimensions are critical since they affect the number of Merkle openings and the extent of arithmetic computation needed, respectively. To mitigate potential Denial of Service (DoS) attacks, the introduction of hard limits on trace length and width is proposed. A heuristic based on the cost of a recursive verification circuit suggests a practical limit to computational requirements, ensuring a balance between security and efficiency.

The dialogue also touches upon the development trajectory of cryptographic optimizations, referencing an opinion that suggests most significant advancements in STARKs have already been achieved. Future improvements are expected to focus on arithmetization levels, which would not impact the final step of verification. However, further enhancements in this area would necessitate the reintroduction or addition of more opcodes, potentially increasing costs despite the benefits. The writer expresses a personal preference for Simplicity, indicating an appreciation for its streamlined nature and efficiency within cryptographic applications.