Proposal: OP_STARK_VERIFY - Native STARK Proof Verification in Bitcoin Script

This move is driven by the desire to support applications such as Validity rollups, post-quantum signatures, and privacy-preserving transactions with efficient on-chain verification capabilities. The choice of vanilla STARKs, particularly showcased by the Stone prover, is due to their transparent, post-quantum-secure assumptions and poly-logarithmic verification complexity which offers an attractive solution for scaling Bitcoin's L1, enabling signature aggregation, and enhancing transaction privacy without the need for off-chain computation or on-chain challenge mechanisms. However, the adoption of this specific STARK protocol raises concerns about credible neutrality, proof sizes, and the technical risks of embedding a particular proof system into Bitcoin’s consensus mechanism.

Alternatives to OP_STARK_VERIFY include OP_CAT-based verifiers and arithmetic opcodes, presenting various efficiencies, flexibility, and levels of protocol enshrinement. Despite their potential, these alternatives carry complexities and inefficiencies of their own. Implementing the Stone verifier, a univariate STARK verifier in C++, into Bitcoin Core requires careful consideration of DoS safety, predictable runtime, and policy limits to manage resource usage effectively. While the OP_STARK_VERIFY opcode promises simplicity and efficiency, it also poses challenges in maintaining credible neutrality and the implications of embedding a specific proof system into Bitcoin consensus.

The discussion extends into the practical aspects of proof systems in decentralized contexts, highlighting the trade-offs between proof size, verification times, and the impact on blockchain technology's feasibility and efficiency. Compression techniques can significantly reduce proof sizes, although concerns persist regarding large proof sizes' effect on block building and relay activities. The exploration of implementing STARK on Bitcoin involves optimizing proving speed, proof size, and verification efficiency, with different compression pipelines offering varied outcomes in terms of proof size and verification times.

An alternative approach using a metaprotocol layered over Bitcoin is presented, avoiding direct modifications to the base protocol and allowing market-driven adoption and flexibility for evolving proof systems. This method reduces risk by keeping complex cryptographic primitives off the consensus-critical layer and enables organic consensus formation around specific STARK implementations.

Critics of integrating STARK technology directly into Bitcoin raise concerns about violating the principles of simplicity, security, and stability, citing the risk of introducing a complex "black box" into the consensus mechanism. They argue that the rapid evolution of zero-knowledge cryptography could render the network obsolete if a specific iteration of STARKs were cemented into the protocol. Opponents suggest maintaining complexity at higher layers or exploring generic, adaptable primitives instead.

The inquiry into Zero-Knowledge Virtual Machines (ZKVMs) expresses skepticism about their ability to undergo formal proofs and addresses the necessity of upgrade mechanisms for addressing bugs, comparing Cairo and STARK proofs' methodologies against ZKVM limitations. The discussion also compares Cairo and RISC-V architectures for zkVMs, highlighting Cairo's suitability for executing zero-knowledge proofs within blockchain technologies.

Starkware's potential role in experimenting with secure bridging to side systems before a soft fork is considered, suggesting a public service that allows for transparent script cosigning. The discussion touches on simplifying the transition mechanism during a soft fork and reducing external approval dependency.

In summary, the integration of STARK technology into Bitcoin presents a blend of innovation and controversy. While it promises enhanced functionality with native ZK proof verification, it also prompts critical debates on security, neutrality, and the long-term implications for Bitcoin's fundamental principles.