Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

No opcode lowers the operation count

Proved
BitcoinScript.execOp_opCount

by pitimespi · Oct 26, 2026 · Mathlib 0df444a (Lean v4.33.1)

bitcoinbitcoin-mainnetconsensuscscriptnumformal-verificationinterpreterscript

For every flag setting, oracle, execution flag, opcode ccc and states s,s′s, s's,s′ with execOp(c,s)=some s′\mathrm{execOp}(c, s) = \mathrm{some}\ s'execOp(c,s)=some s′: s.opCount≤s′.opCounts.\mathrm{opCount} \le s'.\mathrm{opCount}s.opCount≤s′.opCount, and either the count is unchanged or (for CHECKMULTISIG, which adds its key count) it is at most 201201201. A case analysis over the whole opcode table.

Preamble
import Definitions.Def_BitcoinScript
Formal statement
theorem BitcoinScript.execOp_opCount (f : Flags) (o : Oracle) (e : Bool) (c : Byte) (s s' : State)
    (h : BitcoinScript.execOp f o e c s = some s') :
    s.opCount ≤ s'.opCount ∧ (s'.opCount = s.opCount ∨ s'.opCount ≤ BitcoinScript.MAX_OPS_PER_SCRIPT) := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: CastToBool (lines 46-59), EvalScript (417-1249), EvalChecksigPreTapscript, VerifyScript (2012-2110), src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CScriptNum (227-382), opcodetype, MAX_SCRIPT_ELEMENT_SIZE, MAX_OPS_PER_SCRIPT, MAX_PUBKEYS_PER_MULTISIG, MAX_STACK_SIZE, src/script/script.h; GetScriptOp, IsPushOnly, IsPayToScriptHash, src/script/script.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/script.h
Read-back

What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)

Read-back: BitcoinScript.execOp_opCount

Binders and hypothesis. Universally quantified: fff, a flags record; ooo, an oracle; eee, a Boolean (the "currently executing" argument of execOp, called fExec\mathit{fExec}fExec in the definition); ccc, a byte (any value 0x00\mathtt{0x00}0x00–0xff\mathtt{0xff}0xff); sss and s′s's′, two machine states (each with a main stack, alt stack, condition stack, and natural-number opCount). One hypothesis, hhh:

execOp(f,o,e,c,s)=some(s′),\mathrm{execOp}(f, o, e, c, s) = \mathrm{some}(s'),execOp(f,o,e,c,s)=some(s′),

i.e. executing the single opcode ccc from state sss (with executing-flag eee) succeeds and produces s′s's′.

Conclusion. A conjunction about the natural numbers s.opCounts.\mathrm{opCount}s.opCount and s′.opCounts'.\mathrm{opCount}s′.opCount:

s.opCount≤s′.opCount∧(s′.opCount=s.opCount ∨ s′.opCount≤201),s.\mathrm{opCount} \le s'.\mathrm{opCount}\quad\wedge\quad\big(s'.\mathrm{opCount} = s.\mathrm{opCount}\ \vee\ s'.\mathrm{opCount} \le 201\big),s.opCount≤s′.opCount∧(s′.opCount=s.opCount ∨ s′.opCount≤201),

with 201=MAX_OPS_PER_SCRIPT201 = \mathrm{MAX\_OPS\_PER\_SCRIPT}201=MAX_OPS_PER_SCRIPT. In words: a successful execOp never decreases the operation count, and either leaves it unchanged or leaves it at a value not exceeding 201201201.

Unfolding execOp. execOp is a chain of cases on ccc. Every branch except one returns a state whose opCount field is copied from sss unchanged (branches that return sss itself, or sss with only the stack, altstack or vfExec fields replaced, including pushNum, which touches only the stack). The single exception is the CHECKMULTISIG / CHECKMULTISIGVERIFY branch (c=0xaec = \mathtt{0xae}c=0xae or 0xaf\mathtt{0xaf}0xaf). There, after reading the key count nKn_KnK​ from the top element with toNum(false,4,⋅)\mathrm{toNum}(\text{false},4,\cdot)toNum(false,4,⋅) and requiring 0≤nK≤200 \le n_K \le 200≤nK​≤20, it sets opCount′:=s.opCount+nK\mathit{opCount}' := s.\mathrm{opCount} + n_KopCount′:=s.opCount+nK​ and fails (none) if 201<opCount′201 < \mathit{opCount}'201<opCount′; if all subsequent checks succeed the returned state has opCount=opCount′\mathrm{opCount} = \mathit{opCount}'opCount=opCount′. The hypothesis hhh rules out the failure, so in that branch s′.opCount=s.opCount+nK≥s.opCounts'.\mathrm{opCount} = s.\mathrm{opCount} + n_K \ge s.\mathrm{opCount}s′.opCount=s.opCount+nK​≥s.opCount and s′.opCount≤201s'.\mathrm{opCount} \le 201s′.opCount≤201; in all other branches s′.opCount=s.opCounts'.\mathrm{opCount} = s.\mathrm{opCount}s′.opCount=s.opCount. The theorem's disjunction mirrors these two situations but does not name them: it only says "unchanged, or at most 201201201".

Scope. eee is unconstrained: the statement covers calls with e=falsee = \text{false}e=false, which step makes only for conditional opcodes but which execOp as a function accepts for any ccc. ccc is unconstrained: for bytes on which execOp always fails (OP_RETURN, unknown bytes, disabled bytes), the hypothesis is unsatisfiable and the theorem holds vacuously for those ccc. The states sss and s′s's′ are unconstrained beyond hhh: in particular s.opCounts.\mathrm{opCount}s.opCount may already exceed 201201201 (then the first disjunct, equality, is what the non-multisig branches provide; the multisig branch cannot succeed from such an sss since s.opCount+nK>201s.\mathrm{opCount} + n_K > 201s.opCount+nK​>201). Flags and oracle are arbitrary; the nulldummy flag and the oracle's checkSig influence whether the multisig branch succeeds but not the arithmetic of the count.

Note on the second disjunct. The conclusion's second conjunct is a disjunction, not a conjunction: it does not assert s′.opCount≤201s'.\mathrm{opCount} \le 201s′.opCount≤201 outright. If s.opCount=500s.\mathrm{opCount} = 500s.opCount=500 and c=OP_NOPc = \mathrm{OP\_NOP}c=OP_NOP, the theorem is satisfied via the equality disjunct even though 500>201500 > 201500>201.

What is not said. The theorem does not say by how much the count can increase (no bound of 202020, no mention of nKn_KnK​). It does not say which opcodes change the count, nor that only CHECKMULTISIG does. It does not concern step, which performs its own +1+1+1 increment and its own 201201201 check before calling execOp — the theorem is about execOp alone, so nothing is said about the total effect of one loop iteration or about opsIn. It does not say anything about the stacks, vfExec, or stack sizes of s′s's′. It does not say that execOp fails when the count would exceed 201201201 (that is the contrapositive-shaped fact one might expect, but the statement only speaks about successful executions). It is not an "iff": no claim that a count ≤201\le 201≤201 implies success.

Human review
  • Endorsed by Shuze Chen · Oct 26, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 26, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me