Proposal: OP_STARK_VERIFY - Native STARK Proof Verification in Bitcoin Script

This initiative is driven by the potential applications of incorporating zero-knowledge proof verification capabilities directly into Bitcoin, which include Validity rollups, post-quantum signatures, and privacy-preserving transactions. The adoption of vanilla STARKs, particularly highlighted by the Stone prover, is favored due to their transparent, secure assumptions that are resilient against quantum attacks, their poly-logarithmic verification complexity, and their sublinear proof sizes in relation to computation size. These features collectively make STARKs a promising solution for scaling Bitcoin's Layer 1, enabling more efficient signature aggregation, and introducing features for transaction privacy. However, the proposal also acknowledges the existence of significant challenges such as maintaining credible neutrality in the selection of a specific STARK protocol, dealing with the larger proof sizes when compared to other systems like SNARKs, and the technical and consensus risks associated with embedding a specific proof system into Bitcoin's consensus mechanisms. Various alternatives to the proposed opcode are discussed, offering different degrees of efficiency, flexibility, and the extent to which they would be enshrined within the protocol. Despite these considerations, OP_STARK_VERIFY presents itself as a streamlined solution aiming to minimize runtime and policy complexity by standardizing a particular proof system and format. Furthermore, the dialogue extends into the practical aspects of resource usage within proof systems, highlighting the trade-offs between proof sizes and verification times. Proof sizes, which can vary significantly, present a challenge for decentralized block building and relay activities, especially given the unpredictability of mining timings. The discussion underscores the importance of carefully balancing these factors to ensure the feasibility and efficiency of implementing proof systems in decentralized contexts like Bitcoin. The process of optimizing STARK implementation on Bitcoin involves a delicate balance between proving speed, proof size, and verification efficiency, often necessitating a multistage pipeline to fine-tune these parameters. This includes strategies for fast proving, maximizing proof compression, and potentially adopting different proving systems based on the requirements of the settlement layer. The exploration of proof compression pipelines reveals various approaches and their corresponding trade-offs in terms of proof sizes, verification times, and on-chain costs. An alternative approach to modifying the base protocol is suggested, proposing the development of this functionality as a layer on top of Bitcoin. This metaprotocol approach, leveraging existing witness space to embed STARK proofs and relying on open-source indexers to parse and verify the data off-chain, offers several advantages including risk mitigation, market-driven adoption, and flexibility. This model allows for the organic formation of social consensus around specific STARK implementations and provides a pathway for adapting to superior technologies without being constrained by the base protocol. For those interested in exploring this concept further, the document at wtf.rich/w.pdf offers an insightful overview of the possibilities achievable under current protocol rules.