Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The script on a stack b :: tl: it needs exactly one more element, and leaves the chosen signature check

Proved
BitcoinToLocal.eval_cons

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

bip112bitcoinbitcoin-mainnetbolt3csvformal-verificationlightningp2wshscript

For keys of at most 520 bytes, ∣delay∣<232|{\rm delay}| < 2^{32}∣delay∣<232 and tl.length + 1 ≤ 1000: evalScript f o (b :: tl) (toLocalScript rev delay dpk) is none when tl is empty, and for tl = sig :: rest it is (o.checkSig sig rev).map (fun ok => boolBytes ok :: rest) when castToBool b, else (o.checkSig sig dpk).map (…) when CsvPasses f o delay, else none. The whole interpreter run, instruction by instruction, with the skipped branch's pushes and opcodes accounted for.

Preamble
import Definitions.Def_BitcoinToLocal
import Definitions.Def_BitcoinScript
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinToLocal.eval_cons (f : Flags) (o : Oracle) (rev dpk b : Bytes) (delay : Int) (tl : List Bytes)
    (hrev : rev.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hdpk : dpk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hd : delay.natAbs < 2 ^ 32) (htl : tl.length + 1 ≤ BitcoinScript.MAX_STACK_SIZE) :
    BitcoinScript.evalScript f o (b :: tl) (BitcoinToLocal.toLocalScript rev delay dpk) =
      match tl with
      | [] => none
      | sig :: rest =>
        if BitcoinScript.castToBool b then (o.checkSig sig rev).map (fun ok => BitcoinScript.boolBytes ok :: rest)
        else if BitcoinToLocal.CsvPasses f o delay then (o.checkSig sig dpk).map (fun ok => BitcoinScript.boolBytes ok :: rest)
        else none := by sorry
Source
BOLT #3, Bitcoin Transaction and Script Formats, 'to_local Output': https://github.com/lightning/bolts/blob/master/03-transactions.md#to_local-output; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_IF/OP_ELSE/OP_ENDIF, OP_CHECKSEQUENCEVERIFY, OP_CHECKSIG), GenericTransactionSignatureChecker::CheckSequence, ExecuteWitnessScript, VerifyWitnessProgram (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); CScript::operator<<(int64_t) (script/script.h); BIP68, BIP112, BIP141
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: BitcoinToLocal.eval_cons

Statement. Let fff be a script flag record (booleans f.cltv,f.csv,f.nulldummyf.\mathrm{cltv}, f.\mathrm{csv}, f.\mathrm{nulldummy}f.cltv,f.csv,f.nulldummy), ooo an oracle (a record of five arbitrary hash functions on byte strings, an arbitrary o.checkSig:bytes×bytes→Option Boolo.\mathrm{checkSig} : \text{bytes} \times \text{bytes} \to \mathrm{Option}\,\mathrm{Bool}o.checkSig:bytes×bytes→OptionBool taking the signature first and the key second, and arbitrary o.checkLockTime,o.checkSequence:Z→Boolo.\mathrm{checkLockTime}, o.\mathrm{checkSequence} : \mathbb{Z} \to \mathrm{Bool}o.checkLockTime,o.checkSequence:Z→Bool; nothing is assumed about them), RRR (rev), DDD (dpk) and bbb byte strings, δ∈Z\delta \in \mathbb{Z}δ∈Z (delay), and tl\mathrm{tl}tl a list of byte strings. Assume

∣R∣≤520,∣D∣≤520,∣δ∣<232,∣tl∣+1≤1000.|R| \le 520, \qquad |D| \le 520, \qquad |\delta| < 2^{32}, \qquad |\mathrm{tl}| + 1 \le 1000 .∣R∣≤520,∣D∣≤520,∣δ∣<232,∣tl∣+1≤1000.

(520520520 and 100010001000 are the preamble's MAX_SCRIPT_ELEMENT_SIZE and MAX_STACK_SIZE; ∣δ∣|\delta|∣δ∣ is the absolute value as a natural.) Then the result of evaluating the to_local script on the initial stack b::tlb :: \mathrm{tl}b::tl (top-first, so bbb is on top) is

evalScript(f,o, b::tl, toLocalScript(R,δ,D))={noneif tl=[ ],map(ok↦boolBytes(ok)::rest)(o.checkSig(sig,R))if tl=sig::rest and castToBool(b)=true,map(ok↦boolBytes(ok)::rest)(o.checkSig(sig,D))if tl=sig::rest, castToBool(b)=false, and CsvPasses(f,o,δ),noneif tl=sig::rest, castToBool(b)=false, and not CsvPasses(f,o,δ).\mathrm{evalScript}\big(f, o,\ b :: \mathrm{tl},\ \mathrm{toLocalScript}(R, \delta, D)\big) = \begin{cases} \mathrm{none} & \text{if } \mathrm{tl} = [\,],\\[4pt] \mathrm{map}\big(\mathrm{ok} \mapsto \mathrm{boolBytes}(\mathrm{ok}) :: \mathrm{rest}\big)\big(o.\mathrm{checkSig}(\mathrm{sig}, R)\big) & \text{if } \mathrm{tl} = \mathrm{sig} :: \mathrm{rest} \text{ and } \mathrm{castToBool}(b) = \mathrm{true},\\[4pt] \mathrm{map}\big(\mathrm{ok} \mapsto \mathrm{boolBytes}(\mathrm{ok}) :: \mathrm{rest}\big)\big(o.\mathrm{checkSig}(\mathrm{sig}, D)\big) & \text{if } \mathrm{tl} = \mathrm{sig} :: \mathrm{rest},\ \mathrm{castToBool}(b) = \mathrm{false},\ \text{and } \mathrm{CsvPasses}(f, o, \delta),\\[4pt] \mathrm{none} & \text{if } \mathrm{tl} = \mathrm{sig} :: \mathrm{rest},\ \mathrm{castToBool}(b) = \mathrm{false},\ \text{and not } \mathrm{CsvPasses}(f, o, \delta). \end{cases}evalScript(f,o, b::tl, toLocalScript(R,δ,D))=⎩⎨⎧​nonemap(ok↦boolBytes(ok)::rest)(o.checkSig(sig,R))map(ok↦boolBytes(ok)::rest)(o.checkSig(sig,D))none​if tl=[],if tl=sig::rest and castToBool(b)=true,if tl=sig::rest, castToBool(b)=false, and CsvPasses(f,o,δ),if tl=sig::rest, castToBool(b)=false, and not CsvPasses(f,o,δ).​

Here "map(g)\mathrm{map}(g)map(g)" applied to an optional value sends none\mathrm{none}none to none\mathrm{none}none and some ok\mathrm{some}\,\mathrm{ok}someok to some (g(ok))\mathrm{some}\,(g(\mathrm{ok}))some(g(ok)); so in the second and third cases the result is none\mathrm{none}none when the oracle's signature check returns none\mathrm{none}none, and otherwise the stack boolBytes(ok)::rest\mathrm{boolBytes}(\mathrm{ok}) :: \mathrm{rest}boolBytes(ok)::rest, where boolBytes(true)=[0x01]\mathrm{boolBytes}(\mathrm{true}) = [\mathtt{0x01}]boolBytes(true)=[0x01] and boolBytes(false)=[ ]\mathrm{boolBytes}(\mathrm{false}) = [\,]boolBytes(false)=[]. Note that rest\mathrm{rest}rest (everything below the second element) is preserved untouched, and the result is some\mathrm{some}some of a stack of length ∣rest∣+1=∣tl∣|\mathrm{rest}| + 1 = |\mathrm{tl}|∣rest∣+1=∣tl∣ in the successful cases. Note also that no hypothesis bounds ∣b∣|b|∣b∣ or the lengths of the elements of tl\mathrm{tl}tl; only the count ∣tl∣+1≤1000|\mathrm{tl}| + 1 \le 1000∣tl∣+1≤1000 of initial stack elements is assumed.

Unfolded notions.

  • castToBool(x)\mathrm{castToBool}(x)castToBool(x): false\mathrm{false}false for x=[ ]x = [\,]x=[]; for x=[y]x = [y]x=[y], true iff y≠0y \ne 0y=0 and y≠0x80y \ne \mathtt{0x80}y=0x80; for x=y::restx = y :: \mathrm{rest}x=y::rest with rest≠[ ]\mathrm{rest} \ne [\,]rest=[], true iff y≠0y \ne 0y=0 or castToBool(rest)\mathrm{castToBool}(\mathrm{rest})castToBool(rest).
  • CsvPasses(f,o,δ)\mathrm{CsvPasses}(f, o, \delta)CsvPasses(f,o,δ) is f.csv=false∨(0≤δ∧((toNat⁡(δ)&231)≠0∨o.checkSequence(δ)=true))f.\mathrm{csv} = \mathrm{false} \lor \big(0 \le \delta \land ((\operatorname{toNat}(\delta) \mathbin{\&} 2^{31}) \ne 0 \lor o.\mathrm{checkSequence}(\delta) = \mathrm{true})\big)f.csv=false∨(0≤δ∧((toNat(δ)&231)=0∨o.checkSequence(δ)=true)), with toNat⁡\operatorname{toNat}toNat truncating negatives to 000 and &\mathbin{\&}& bitwise AND on naturals.
  • toLocalScript(R,δ,D)\mathrm{toLocalScript}(R, \delta, D)toLocalScript(R,δ,D) is the nine-instruction list [op 0x63, push R, op 0x67, numInstr(δ), op 0xb2, op 0x75, push D, op 0x68, op 0xac][\mathrm{op}\,\mathtt{0x63},\ \mathrm{push}\,R,\ \mathrm{op}\,\mathtt{0x67},\ \mathrm{numInstr}(\delta),\ \mathrm{op}\,\mathtt{0xb2},\ \mathrm{op}\,\mathtt{0x75},\ \mathrm{push}\,D,\ \mathrm{op}\,\mathtt{0x68},\ \mathrm{op}\,\mathtt{0xac}][op0x63, pushR, op0x67, numInstr(δ), op0xb2, op0x75, pushD, op0x68, op0xac], where numInstr(δ)\mathrm{numInstr}(\delta)numInstr(δ) is the opcode with byte δ+80\delta + 80δ+80 if δ=−1\delta = -1δ=−1 or 1≤δ≤161 \le \delta \le 161≤δ≤16 (bytes 0x4f\mathtt{0x4f}0x4f, 0x51\mathtt{0x51}0x51–0x60\mathtt{0x60}0x60), and otherwise the data push of serialize(δ)\mathrm{serialize}(\delta)serialize(δ) (serialize(0)=[ ]\mathrm{serialize}(0) = [\,]serialize(0)=[]; for δ≠0\delta \ne 0δ=0, the little-endian magnitude bytes of ∣δ∣|\delta|∣δ∣ without trailing zeros, with an appended 0x80\mathtt{0x80}0x80 or 0x00\mathtt{0x00}0x00 byte when the top bit of the last byte is set, otherwise the top bit set on the last byte when δ<0\delta < 0δ<0).

The interpreter evalScript. evalScript(f,o,S,P)\mathrm{evalScript}(f, o, S, P)evalScript(f,o,S,P) starts from the state (main stack =S= S=S, alt-stack =[ ]= [\,]=[], condition stack vfExec=[ ]\mathrm{vfExec} = [\,]vfExec=[], opCount=0\mathrm{opCount} = 0opCount=0), applies one step per instruction of PPP in order, and, if every step succeeds and the condition stack is empty at the end, returns some\mathrm{some}some of the final main stack; any step failure, or a non-empty condition stack at the end, gives none\mathrm{none}none. A step is:

  • Push of data xxx. Fail if ∣x∣>520|x| > 520∣x∣>520. Otherwise, if every entry of vfExec\mathrm{vfExec}vfExec is true, place xxx on top of the main stack; if some entry is false, leave the state unchanged. Then fail if ∣stack∣+∣alt-stack∣>1000|\text{stack}| + |\text{alt-stack}| > 1000∣stack∣+∣alt-stack∣>1000.
  • Opcode ccc. Let eee be "every entry of vfExec\mathrm{vfExec}vfExec is true". If c>0x60c > \mathtt{0x60}c>0x60, the opcode is counted: fail if opCount+1>201\mathrm{opCount} + 1 > 201opCount+1>201, else increment opCount\mathrm{opCount}opCount. Fail if ccc is one of the fifteen disabled opcodes (0x7e\mathtt{0x7e}0x7e–0x81\mathtt{0x81}0x81, 0x83\mathtt{0x83}0x83–0x86\mathtt{0x86}0x86, 0x8d\mathtt{0x8d}0x8d, 0x8e\mathtt{0x8e}0x8e, 0x95\mathtt{0x95}0x95–0x99\mathtt{0x99}0x99; none occur here). If eee holds or 0x63≤c≤0x68\mathtt{0x63} \le c \le \mathtt{0x68}0x63≤c≤0x68, apply execOp\mathrm{execOp}execOp below with flag eee, then fail if ∣stack∣+∣alt-stack∣>1000|\text{stack}| + |\text{alt-stack}| > 1000∣stack∣+∣alt-stack∣>1000. Otherwise leave the state unchanged apart from that same size check.

execOp\mathrm{execOp}execOp for the opcodes that can occur in this script:

  • 0x4f\mathtt{0x4f}0x4f, 0x51\mathtt{0x51}0x51–0x60\mathtt{0x60}0x60 (the opcode form of numInstr(δ)\mathrm{numInstr}(\delta)numInstr(δ)): push serialize(c−80)\mathrm{serialize}(c - 80)serialize(c−80) onto the main stack.
  • 0x63\mathtt{0x63}0x63 (OP_IF): if eee is true, fail on an empty main stack, else pop the top xxx and push castToBool(x)\mathrm{castToBool}(x)castToBool(x) onto vfExec\mathrm{vfExec}vfExec; if eee is false, push false\mathrm{false}false onto vfExec\mathrm{vfExec}vfExec without touching the main stack.
  • 0x67\mathtt{0x67}0x67 (OP_ELSE): fail if vfExec\mathrm{vfExec}vfExec is empty, else negate its head.
  • 0x68\mathtt{0x68}0x68 (OP_ENDIF): fail if vfExec\mathrm{vfExec}vfExec is empty, else remove its head.
  • 0xb2\mathtt{0xb2}0xb2 (OP_CHECKSEQUENCEVERIFY): if f.csv=falsef.\mathrm{csv} = \mathrm{false}f.csv=false, unchanged. Else fail on an empty main stack; let xxx be the top (not removed); fail if ∣x∣>5|x| > 5∣x∣>5; let nnn be the signed little-endian value of xxx (top bit of the last byte is the sign; the empty string is 000); fail if n<0n < 0n<0; if (toNat⁡(n)&231)≠0(\operatorname{toNat}(n) \mathbin{\&} 2^{31}) \ne 0(toNat(n)&231)=0, unchanged; else fail if o.checkSequence(n)=falseo.\mathrm{checkSequence}(n) = \mathrm{false}o.checkSequence(n)=false; else unchanged.
  • 0x75\mathtt{0x75}0x75 (OP_DROP): fail on an empty main stack, else remove the top.
  • 0xac\mathtt{0xac}0xac (OP_CHECKSIG): the main stack must have the form pk::sg::rest\mathrm{pk} :: \mathrm{sg} :: \mathrm{rest}pk::sg::rest (pk\mathrm{pk}pk on top), else fail; then o.checkSig(sg,pk)o.\mathrm{checkSig}(\mathrm{sg}, \mathrm{pk})o.checkSig(sg,pk): none\mathrm{none}none gives failure, some ok\mathrm{some}\,\mathrm{ok}someok replaces the two elements by boolBytes(ok)\mathrm{boolBytes}(\mathrm{ok})boolBytes(ok), giving boolBytes(ok)::rest\mathrm{boolBytes}(\mathrm{ok}) :: \mathrm{rest}boolBytes(ok)::rest.

The theorem thus equates the outcome of this nine-step run on b::tlb :: \mathrm{tl}b::tl with the four-case expression displayed above.

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

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 29, 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