Proposal: OP_STARK_VERIFY - Native STARK Proof Verification in Bitcoin Script

This blog post delves into the recent proposal to introduce a new opcode, OP_STARK_VERIFY, into Tapscript for the direct on-chain verification of STARK (Scalable Transparent ARgument of Knowledge) proofs within Bitcoin Script. This initiative stems from a growing interest in integrating zero-knowledge proof verification capabilities directly into Bitcoin to support various applications like Validity rollups, post-quantum signatures, and privacy-preserving transactions. The proposed OP_STARK_VERIFY aims to enable efficient verification without the complexities associated with off-chain computation or the need for on-chain challenge mechanisms that current methods like BitVM-style optimistic fraud proofs with ZK verification entail.

The focus is on vanilla STARKs as exhibited by the Stone prover due to their transparent, post-quantum-secure assumptions, poly-logarithmic verification complexity, and sublinear proof sizes relative to computation size. These characteristics make STARKs an attractive option for scaling Bitcoin L1 through Validity rollups, enabling post-quantum signature aggregation, and introducing privacy features like shielded transactions. However, the proposal acknowledges significant challenges such as credible neutrality in choosing a specific STARK protocol, the large proof sizes compared to other systems like SNARKs, and the technical and consensus risks involved in enshrining a specific proof system into Bitcoin.

Alternatives to OP_STARK_VERIFY are discussed, including OP_CAT-based verifiers and arithmetic opcodes for building a verifier within Script. These methods offer varying degrees of efficiency, flexibility, and protocol enshrinement but come with their own sets of complexities and inefficiencies. The proposed OP_STARK_VERIFY opcode represents a clean and efficient solution with a high level of protocol enshrinement, aiming to simplify runtime and policy by pinning a concrete proof system and format.

The exploratory implementation would see the integration of the Stone verifier, a univariate STARK verifier implemented in C++, into Bitcoin Core. Key considerations for this opcode include strict bounds on proof size to ensure DoS safety, predictable runtime through fixed verifier parameter sets, and policy limits to manage resource usage effectively. Despite the potential benefits, the proposal highlights several risks such as the complexity of the verifier's C++ code, the challenge of maintaining credible neutrality, and the implications of enshrining a specific proof system into Bitcoin consensus.

In conclusion, while the proposal for OP_STARK_VERIFY presents a forward-thinking approach to enhancing Bitcoin's functionality with native ZK proof verification, it also raises important questions about flexibility, security, and neutrality that must be carefully considered. Further discussion and feedback are sought on scope, parameter bounding, pricing, alternatives, and the technical challenges ahead.