Hypothetical thought experiments and design ideas
Introduction
Verifying STARK proofs on Bitcoin is notoriously challenging due to the limitations of Bitcoin Script.
This article explores a more direct solution: introducing new arithmetic opcodes tailored to the M31 Mersenne prime field ($2^{31}-1$). These hypothetical opcodes (e.g., OP_M31ADD, OP_M31SUB, OP_M31MUL, OP_M31INV) would enable direct addition, subtraction, multiplication, and inversion modulo $2^{31}-1$ within script. The primary motivation, in such a scenario, could be to facilitate on-chain verification of STARK proofs (a type of zero-knowledge proof) by providing native field operations. By focusing on a specific prime field, this approach would aim to avoid the broad complexity of a more generic opcode, potentially reducing risks. The following sections outline the rationale for specialized M31 opcodes, describe their possible semantics, and consider both security and feasibility concerns in a hypothetical, backward-compatible soft fork upgrade that extends Bitcoin’s scripting capabilities in a targeted and safe manner.
STARKs (Scalable Transparent Argument of Knowledge) allow a prover to demonstrate the validity of a computation without revealing some details (the formal ZK part of it is not granted by default and require some additional work, i.e STARKs can be used for scaling only), offering both scalability and privacy advantages. Enabling Bitcoin Script to verify a STARK proof efficiently would let developers build trustless bridges to Layer-2 systems or run complex off-chain computations with minimal on-chain data. However, STARK verification commonly requires extensive finite field arithmetic, and many STARK constructions rely on prime fields. A compelling choice might be the Mersenne prime $2^{31} - 1$ (denoted M31), which research shows is especially efficient on standard hardware. This prime fits into a single 32-bit word, making addition and multiplication faster on modern CPUs.
By introducing dedicated M31 field opcodes, one might directly support the arithmetic needed for STARKs, making on-chain verification practical and efficient.