Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The two spending conditions, for any witness stack

Proved
BitcoinToLocal.spends_iff

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

bip112bitcoinbitcoin-mainnetbolt3csvformal-verificationlightningp2wshscript

For keys of at most 520 bytes and ∣delay∣<232|{\rm delay}| < 2^{32}∣delay∣<232, and any stack st: there is a result of evalScript f o st (toLocalScript rev delay dpk) with exactly one element that is true, if and only if st = [b, sig] for some bbb, sig with SpendCondition f o rev delay dpk b sig. Stacks of any other shape fail: empty, one element, more than two (the extra elements remain below the result), or beyond the 1000-element limit.

Preamble
import Definitions.Def_BitcoinToLocal
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinVerify
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinToLocal.spends_iff (f : Flags) (o : Oracle) (rev dpk : Bytes) (delay : Int) (st : List Bytes)
    (hrev : rev.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hdpk : dpk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hd : delay.natAbs < 2 ^ 32) :
    (∃ res, BitcoinScript.evalScript f o st (BitcoinToLocal.toLocalScript rev delay dpk) = some res ∧
        res.length = 1 ∧ BitcoinVerify.topTrue res = true) ↔
      ∃ b sig, st = [b, sig] ∧ BitcoinToLocal.SpendCondition f o rev delay dpk b sig := 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.spends_iff

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; no properties assumed), RRR (rev) and DDD (dpk) byte strings, δ∈Z\delta \in \mathbb{Z}δ∈Z (delay), and st\mathrm{st}st an arbitrary list of byte strings (an initial stack, top-first). Assume

∣R∣≤520,∣D∣≤520,∣δ∣<232|R| \le 520, \qquad |D| \le 520, \qquad |\delta| < 2^{32}∣R∣≤520,∣D∣≤520,∣δ∣<232

(520520520 is MAX_SCRIPT_ELEMENT_SIZE; ∣δ∣|\delta|∣δ∣ the absolute value as a natural). Then

(∃ res.  evalScript(f,o,st,toLocalScript(R,δ,D))=some res ∧ ∣res∣=1 ∧ topTrue(res)=true)  ⟺  (∃ b sig.  st=[b,sig] ∧ SpendCondition(f,o,R,δ,D,b,sig)).\Big( \exists\, \mathrm{res}.\ \ \mathrm{evalScript}\big(f, o, \mathrm{st}, \mathrm{toLocalScript}(R, \delta, D)\big) = \mathrm{some}\ \mathrm{res}\ \land\ |\mathrm{res}| = 1\ \land\ \mathrm{topTrue}(\mathrm{res}) = \mathrm{true} \Big) \iff \Big( \exists\, b\ \mathrm{sig}.\ \ \mathrm{st} = [b, \mathrm{sig}]\ \land\ \mathrm{SpendCondition}(f, o, R, \delta, D, b, \mathrm{sig}) \Big).(∃res.  evalScript(f,o,st,toLocalScript(R,δ,D))=some res ∧ ∣res∣=1 ∧ topTrue(res)=true)⟺(∃b sig.  st=[b,sig] ∧ SpendCondition(f,o,R,δ,D,b,sig)).

On the left, res\mathrm{res}res ranges over lists of byte strings; topTrue(res)\mathrm{topTrue}(\mathrm{res})topTrue(res) is false\mathrm{false}false for the empty list and castToBool\mathrm{castToBool}castToBool of the first (top) element otherwise, so with ∣res∣=1|\mathrm{res}| = 1∣res∣=1 the left side says: evaluation succeeds with a one-element stack [x][x][x] and castToBool(x)=true\mathrm{castToBool}(x) = \mathrm{true}castToBool(x)=true. On the right, bbb and sig\mathrm{sig}sig range over byte strings; st=[b,sig]\mathrm{st} = [b, \mathrm{sig}]st=[b,sig] means the initial stack has exactly two elements, bbb on top and sig\mathrm{sig}sig beneath. No hypothesis constrains st\mathrm{st}st (its length or element sizes) — the two-element shape is part of the conclusion, not an assumption.

Unfolded notions.

  • castToBool(x)\mathrm{castToBool}(x)castToBool(x): false\mathrm{false}false for x=[ ]x = [\,]x=[]; for [y][y][y], true iff y≠0y \ne 0y=0 and y≠0x80y \ne \mathtt{0x80}y=0x80; for y::resty :: \mathrm{rest}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)), where toNat⁡\operatorname{toNat}toNat truncates negatives to 000 and &\mathbin{\&}& is bitwise AND on naturals.
  • SpendCondition(f,o,R,δ,D,b,sig)\mathrm{SpendCondition}(f, o, R, \delta, D, b, \mathrm{sig})SpendCondition(f,o,R,δ,D,b,sig) is
(castToBool(b)=true∧o.checkSig(sig,R)=some true) ∨ (castToBool(b)=false∧CsvPasses(f,o,δ)∧o.checkSig(sig,D)=some true);\big(\mathrm{castToBool}(b) = \mathrm{true} \land o.\mathrm{checkSig}(\mathrm{sig}, R) = \mathrm{some}\,\mathrm{true}\big)\ \lor\ \big(\mathrm{castToBool}(b) = \mathrm{false} \land \mathrm{CsvPasses}(f, o, \delta) \land o.\mathrm{checkSig}(\mathrm{sig}, D) = \mathrm{some}\,\mathrm{true}\big);(castToBool(b)=true∧o.checkSig(sig,R)=sometrue) ∨ (castToBool(b)=false∧CsvPasses(f,o,δ)∧o.checkSig(sig,D)=sometrue);

in each disjunct the oracle's verdict must be exactly some true\mathrm{some}\,\mathrm{true}sometrue (none\mathrm{none}none and some false\mathrm{some}\,\mathrm{false}somefalse both fail).

  • 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 when δ=−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, plus an appended 0x80\mathtt{0x80}0x80/0x00\mathtt{0x00}0x00 byte when the top bit of the last byte is set, else 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 SSS, alt-stack [ ][\,][], condition stack vfExec=[ ]\mathrm{vfExec} = [\,]vfExec=[], opCount=0\mathrm{opCount} = 0opCount=0), applies one step per instruction of PPP in order, and returns some\mathrm{some}some of the final main stack if every step succeeds and vfExec\mathrm{vfExec}vfExec is empty at the end; otherwise 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, put xxx on top of the main stack (else 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: 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 (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 with flag eee and 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 size check.

execOp\mathrm{execOp}execOp for the opcodes of this script:

  • 0x4f\mathtt{0x4f}0x4f, 0x51\mathtt{0x51}0x51–0x60\mathtt{0x60}0x60 (opcode form of numInstr(δ)\mathrm{numInstr}(\delta)numInstr(δ)): push serialize(c−80)\mathrm{serialize}(c - 80)serialize(c−80).
  • 0x63\mathtt{0x63}0x63 (OP_IF): if eee, 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 not eee, push false\mathrm{false}false onto vfExec\mathrm{vfExec}vfExec without popping.
  • 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 last byte is the sign; empty 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 be 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 fails, some ok\mathrm{some}\,\mathrm{ok}someok yields the stack boolBytes(ok)::rest\mathrm{boolBytes}(\mathrm{ok}) :: \mathrm{rest}boolBytes(ok)::rest with boolBytes(true)=[0x01]\mathrm{boolBytes}(\mathrm{true}) = [\mathtt{0x01}]boolBytes(true)=[0x01], boolBytes(false)=[ ]\mathrm{boolBytes}(\mathrm{false}) = [\,]boolBytes(false)=[].

The theorem is a two-sided equivalence: a successful run of this script from st\mathrm{st}st ending with exactly one element that casts to true happens precisely when st\mathrm{st}st is a two-element stack [b,sig][b, \mathrm{sig}][b,sig] satisfying SpendCondition\mathrm{SpendCondition}SpendCondition.

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