Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The funding script on the BOLT #3 witness

Proved
BitcoinFunding.funding_witness

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

bip147bitcoinbitcoin-mainnetbolt3checkmultisigformal-verificationfundinglightningmultisigp2wsh

For keys of at most 520 bytes: evalScript f o [sig2, sig1, dummy] (fundingScript pubkey1 pubkey2) is the 2-of-2 loop's verdict multisigLoop o [sig2, sig1] [pubkey2, pubkey1] as a single stack element, none if the loop errors or if NULLDUMMY is on and the dummy is nonempty.

Preamble
import Definitions.Def_BitcoinFunding
import Definitions.Def_BitcoinScript
open BitcoinFunding BitcoinHtlc
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinFunding.funding_witness (f : Flags) (o : Oracle) (pubkey1 pubkey2 sig1 sig2 dummy : Bytes)
    (h1 : pubkey1.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (h2 : pubkey2.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) :
    BitcoinScript.evalScript f o [sig2, sig1, dummy] (BitcoinFunding.fundingScript pubkey1 pubkey2) =
      match BitcoinScript.multisigLoop o [sig2, sig1] [pubkey2, pubkey1] with
      | none => none
      | some ok => if f.nulldummy && !dummy.isEmpty then none else some [BitcoinScript.boolBytes ok] := by sorry
Source
BOLT #3, Funding Transaction Output: https://github.com/lightning/bolts/blob/master/03-transactions.md#funding-transaction-output; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_CHECKMULTISIG), ExecuteWitnessScript, VerifyWitnessProgram (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); BIP141, BIP147
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: BitcoinFunding.funding_witness

A byte is an 8-bit word; a byte string (Bytes\mathsf{Bytes}Bytes) is a finite list of bytes; a stack is a finite list of byte strings whose first entry is the top.

Statement

The theorem quantifies over:

  • a flag record fff with exactly three boolean fields f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy;
  • an oracle ooo: a record of abstract functions o.ripemd160,o.sha1,o.sha256,o.hash160,o.hash256:Bytes→Byteso.\mathrm{ripemd160}, o.\mathrm{sha1}, o.\mathrm{sha256}, o.\mathrm{hash160}, o.\mathrm{hash256} : \mathsf{Bytes}\to\mathsf{Bytes}o.ripemd160,o.sha1,o.sha256,o.hash160,o.hash256:Bytes→Bytes; o.checkSig:Bytes×Bytes→Option(Bool)o.\mathrm{checkSig} : \mathsf{Bytes}\times\mathsf{Bytes}\to\mathrm{Option}(\mathrm{Bool})o.checkSig:Bytes×Bytes→Option(Bool) (first argument "signature", second "public key"; value none\mathrm{none}none, some true\mathrm{some}\,\mathrm{true}sometrue or some false\mathrm{some}\,\mathrm{false}somefalse); 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 any of these functions;
  • five byte strings k1,k2,s1,s2,dk_1, k_2, s_1, s_2, dk1​,k2​,s1​,s2​,d (pubkey1, pubkey2, sig1, sig2, dummy), unconstrained in content;

and assumes the two hypotheses ∣k1∣≤520|k_1|\le 520∣k1​∣≤520 and ∣k2∣≤520|k_2|\le 520∣k2​∣≤520 (520520520 = MAX_SCRIPT_ELEMENT_SIZE). No bound is placed on ∣s1∣|s_1|∣s1​∣, ∣s2∣|s_2|∣s2​∣ or ∣d∣|d|∣d∣.

Under these, the theorem asserts an equality of two values in Option(stack)\mathrm{Option}(\text{stack})Option(stack):

evalScript(f, o, [ s2, s1, d ], fundingScript(k1,k2))  =  {noneif multisigLoop(o,[s2,s1],[k2,k1])=none,noneif multisigLoop(o,[s2,s1],[k2,k1])=some(ok) and f.nulldummy=true and d≠[ ],some [ boolBytes(ok) ]if multisigLoop(o,[s2,s1],[k2,k1])=some(ok) otherwise,\mathrm{evalScript}\big(f,\ o,\ [\,s_2,\ s_1,\ d\,],\ \mathrm{fundingScript}(k_1,k_2)\big) \;=\; \begin{cases} \mathrm{none} & \text{if } \mathrm{multisigLoop}(o,[s_2,s_1],[k_2,k_1]) = \mathrm{none},\\[2pt] \mathrm{none} & \text{if } \mathrm{multisigLoop}(o,[s_2,s_1],[k_2,k_1]) = \mathrm{some}(ok) \text{ and } f.\mathrm{nulldummy}=\mathrm{true} \text{ and } d\neq[\,],\\[2pt] \mathrm{some}\,[\,\mathrm{boolBytes}(ok)\,] & \text{if } \mathrm{multisigLoop}(o,[s_2,s_1],[k_2,k_1]) = \mathrm{some}(ok) \text{ otherwise,} \end{cases}evalScript(f, o, [s2​, s1​, d], fundingScript(k1​,k2​))=⎩⎨⎧​nonenonesome[boolBytes(ok)]​if multisigLoop(o,[s2​,s1​],[k2​,k1​])=none,if multisigLoop(o,[s2​,s1​],[k2​,k1​])=some(ok) and f.nulldummy=true and d=[],if multisigLoop(o,[s2​,s1​],[k2​,k1​])=some(ok) otherwise,​

where boolBytes(true)=[0x01]\mathrm{boolBytes}(\mathrm{true}) = [\mathtt{0x01}]boolBytes(true)=[0x01] and boolBytes(false)=[ ]\mathrm{boolBytes}(\mathrm{false}) = [\,]boolBytes(false)=[] (the empty byte string). The initial stack on the left has s2s_2s2​ on top, s1s_1s1​ beneath it, and ddd at the bottom. On the right, the result stack (when not none\mathrm{none}none) has exactly one element, either [0x01][\mathtt{0x01}][0x01] or [ ][\,][].

The script

fundingScript(k1,k2)=[ op(0x52), push(k1), push(k2), op(0x52), op(0xae) ],\mathrm{fundingScript}(k_1,k_2) = \big[\ \mathrm{op}(\mathtt{0x52}),\ \mathrm{push}(k_1),\ \mathrm{push}(k_2),\ \mathrm{op}(\mathtt{0x52}),\ \mathrm{op}(\mathtt{0xae})\ \big],fundingScript(k1​,k2​)=[ op(0x52), push(k1​), push(k2​), op(0x52), op(0xae) ],

where op(0x52)\mathrm{op}(\mathtt{0x52})op(0x52) is numInstr(2)\mathrm{numInstr}(2)numInstr(2) (for n=−1n=-1n=−1 or 1≤n≤161\le n\le161≤n≤16, numInstr(n)=op(n+0x50)\mathrm{numInstr}(n)=\mathrm{op}(n+\mathtt{0x50})numInstr(n)=op(n+0x50); otherwise a push of the script-number encoding of nnn) and 0xae\mathtt{0xae}0xae is OP_CHECKMULTISIG.

The right-hand side: multisigLoop

multisigLoop(o,sigs,keys)\mathrm{multisigLoop}(o, \mathit{sigs}, \mathit{keys})multisigLoop(o,sigs,keys), with both lists top-first, is defined by:

  • sigs=[ ]\mathit{sigs}=[\,]sigs=[]: some true\mathrm{some}\,\mathrm{true}sometrue (whatever keys\mathit{keys}keys is).
  • sigs≠[ ]\mathit{sigs}\ne[\,]sigs=[] and keys=[ ]\mathit{keys}=[\,]keys=[]: some false\mathrm{some}\,\mathrm{false}somefalse.
  • sigs=s::sigs′\mathit{sigs}=s::\mathit{sigs}'sigs=s::sigs′ and keys=k::keys′\mathit{keys}=k::\mathit{keys}'keys=k::keys′: compute o.checkSig(s,k)o.\mathrm{checkSig}(s,k)o.checkSig(s,k):
    • none\mathrm{none}none ⇒\Rightarrow⇒ result none\mathrm{none}none;
    • some true\mathrm{some}\,\mathrm{true}sometrue ⇒\Rightarrow⇒ if ∣keys′∣<∣sigs′∣|\mathit{keys}'|<|\mathit{sigs}'|∣keys′∣<∣sigs′∣ then some false\mathrm{some}\,\mathrm{false}somefalse, else multisigLoop(o,sigs′,keys′)\mathrm{multisigLoop}(o,\mathit{sigs}',\mathit{keys}')multisigLoop(o,sigs′,keys′) (both the signature and the key are consumed);
    • some false\mathrm{some}\,\mathrm{false}somefalse ⇒\Rightarrow⇒ if ∣keys′∣<∣sigs∣|\mathit{keys}'|<|\mathit{sigs}|∣keys′∣<∣sigs∣ then some false\mathrm{some}\,\mathrm{false}somefalse, else multisigLoop(o,sigs,keys′)\mathrm{multisigLoop}(o,\mathit{sigs},\mathit{keys}')multisigLoop(o,sigs,keys′) (only the key is consumed; the same signature is retried against the next key).

Applied to sigs=[s2,s1]\mathit{sigs}=[s_2,s_1]sigs=[s2​,s1​] and keys=[k2,k1]\mathit{keys}=[k_2,k_1]keys=[k2​,k1​], the definition unrolls as follows. First o.checkSig(s2,k2)o.\mathrm{checkSig}(s_2,k_2)o.checkSig(s2​,k2​) is evaluated:

  • if none\mathrm{none}none: the loop returns none\mathrm{none}none;
  • if some false\mathrm{some}\,\mathrm{false}somefalse: the remaining keys [k1][k_1][k1​] number 1<2=∣[s2,s1]∣1 < 2 = |[s_2,s_1]|1<2=∣[s2​,s1​]∣, so the loop returns some false\mathrm{some}\,\mathrm{false}somefalse — s2s_2s2​ is not retried against k1k_1k1​, and s1s_1s1​ is never examined;
  • if some true\mathrm{some}\,\mathrm{true}sometrue: since ∣[k1]∣=1≮1=∣[s1]∣|[k_1]| = 1 \not< 1 = |[s_1]|∣[k1​]∣=1<1=∣[s1​]∣, the loop continues with ([s1],[k1])([s_1],[k_1])([s1​],[k1​]) and evaluates o.checkSig(s1,k1)o.\mathrm{checkSig}(s_1,k_1)o.checkSig(s1​,k1​): none⇒none\mathrm{none}\Rightarrow\mathrm{none}none⇒none; some false⇒\mathrm{some}\,\mathrm{false}\Rightarrowsomefalse⇒ (0<10<10<1) some false\mathrm{some}\,\mathrm{false}somefalse; some true⇒\mathrm{some}\,\mathrm{true}\Rightarrowsometrue⇒ (0≮00\not<00<0) continue with ([ ],[ ])([\,],[\,])([],[]), which is some true\mathrm{some}\,\mathrm{true}sometrue.

So the loop is some true\mathrm{some}\,\mathrm{true}sometrue iff o.checkSig(s2,k2)=some trueo.\mathrm{checkSig}(s_2,k_2)=\mathrm{some}\,\mathrm{true}o.checkSig(s2​,k2​)=sometrue and o.checkSig(s1,k1)=some trueo.\mathrm{checkSig}(s_1,k_1)=\mathrm{some}\,\mathrm{true}o.checkSig(s1​,k1​)=sometrue; it is none\mathrm{none}none iff o.checkSig(s2,k2)=noneo.\mathrm{checkSig}(s_2,k_2)=\mathrm{none}o.checkSig(s2​,k2​)=none, or o.checkSig(s2,k2)=some trueo.\mathrm{checkSig}(s_2,k_2)=\mathrm{some}\,\mathrm{true}o.checkSig(s2​,k2​)=sometrue and o.checkSig(s1,k1)=noneo.\mathrm{checkSig}(s_1,k_1)=\mathrm{none}o.checkSig(s1​,k1​)=none; and some false\mathrm{some}\,\mathrm{false}somefalse in the remaining cases. The pairing is: the top signature s2s_2s2​ with the top key k2k_2k2​; the second signature s1s_1s1​ with the second key k1k_1k1​. The order of evaluation is s2s_2s2​ against k2k_2k2​ first.

The outer match on the right-hand side then returns none\mathrm{none}none when the loop is none\mathrm{none}none; otherwise, with the loop's boolean okokok, it returns none\mathrm{none}none if f.nulldummyf.\mathrm{nulldummy}f.nulldummy is true and ddd is non-empty, and some [boolBytes(ok)]\mathrm{some}\,[\mathrm{boolBytes}(ok)]some[boolBytes(ok)] otherwise. When f.nulldummyf.\mathrm{nulldummy}f.nulldummy is false, ddd is never inspected on the right-hand side; when it is true, a non-empty ddd yields none\mathrm{none}none even if ok=falseok=\mathrm{false}ok=false.

The left-hand side: the interpreter evalScript

evalScript(f,o,st0,S)\mathrm{evalScript}(f,o,st_0,S)evalScript(f,o,st0​,S) is none\mathrm{none}none (failure) or some(st)\mathrm{some}(st)some(st) for a stack ststst. The machine state is a tuple (main stack, alternate stack, condition stack vfExec\mathit{vfExec}vfExec — a list of booleans — , opcode counter), initially (st0,[ ],[ ],0)(st_0,[\,],[\,],0)(st0​,[],[],0). The instructions of SSS are run in order by the one-step rule below; any failure makes the whole result none\mathrm{none}none. After the last instruction, the run fails if vfExec\mathit{vfExec}vfExec is non-empty; otherwise the result is some\mathrm{some}some of the final main stack (the alternate stack and counter are discarded).

One step:

  • push(x)\mathrm{push}(x)push(x): fail if ∣x∣>520|x|>520∣x∣>520. Otherwise, if every entry of vfExec\mathit{vfExec}vfExec is true\mathrm{true}true (vacuously true when vfExec\mathit{vfExec}vfExec is empty), xxx is placed on top of the main stack; else the state is unchanged. Then fail if ∣main∣+∣alt∣>1000|\text{main}|+|\text{alt}|>1000∣main∣+∣alt∣>1000.
  • op(c)\mathrm{op}(c)op(c): the opcode is counted iff c>0x60c>\mathtt{0x60}c>0x60. If counted and counter+1>201+1>201+1>201: fail; else if counted, the counter is incremented. 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). Then, if every entry of vfExec\mathit{vfExec}vfExec is true or 0x63≤c≤0x68\mathtt{0x63}\le c\le\mathtt{0x68}0x63≤c≤0x68: apply the one-opcode executor execOp\mathrm{execOp}execOp (fail if it fails), then fail if ∣main∣+∣alt∣>1000|\text{main}|+|\text{alt}|>1000∣main∣+∣alt∣>1000; otherwise skip the opcode (same size check).

The one-opcode executor on the two opcodes occurring in the funding script (its branches for other opcodes are not reproduced):

  • c=0x52c=\mathtt{0x52}c=0x52 (branch for c=0x4fc=\mathtt{0x4f}c=0x4f or 0x51≤c≤0x60\mathtt{0x51}\le c\le\mathtt{0x60}0x51≤c≤0x60; not counted): push serialize(c−0x50)\mathrm{serialize}(c-\mathtt{0x50})serialize(c−0x50) onto the main stack, where serialize(n)\mathrm{serialize}(n)serialize(n) is [ ][\,][] for n=0n=0n=0, and otherwise the little-endian bytes of ∣n∣|n|∣n∣ without trailing zero bytes, followed by an extra byte 0x80\mathtt{0x80}0x80 (if n<0n<0n<0) or 0x00\mathtt{0x00}0x00 (if n>0n>0n>0) when the top bit of the last magnitude byte is set, or else with the top bit of the last byte set when n<0n<0n<0. For 0x52\mathtt{0x52}0x52 this pushes [0x02][\mathtt{0x02}][0x02].
  • c=0xaec=\mathtt{0xae}c=0xae (OP_CHECKMULTISIG; counted). With main stack ststst and the already-incremented counter κ\kappaκ:
    1. Fail if st=[ ]st=[\,]st=[]. Else st=nk::rst=n_k::rst=nk​::r.
    2. Nk:=toNum(nk)N_k:=\mathrm{toNum}(n_k)Nk​:=toNum(nk​): fail if ∣nk∣>4|n_k|>4∣nk​∣>4; otherwise NkN_kNk​ is the signed little-endian value of nkn_knk​ (sign bit = top bit of the last byte; magnitude = little-endian value with that bit cleared; the empty string is 000). Fail if Nk<0N_k<0Nk​<0 or Nk>20N_k>20Nk​>20.
    3. κ′:=κ+Nk\kappa':=\kappa+N_kκ′:=κ+Nk​; fail if κ′>201\kappa'>201κ′>201.
    4. keys:=\mathit{keys}:=keys:= the first NkN_kNk​ entries of rrr, r:=r:=r:= the rest; fail if fewer than NkN_kNk​ entries were available.
    5. Fail if r=[ ]r=[\,]r=[]; else r=ns::rr=n_s::rr=ns​::r. Ns:=toNum(ns)N_s:=\mathrm{toNum}(n_s)Ns​:=toNum(ns​) (fail if ∣ns∣>4|n_s|>4∣ns​∣>4); fail if Ns<0N_s<0Ns​<0 or Ns>NkN_s>N_kNs​>Nk​.
    6. sigs:=\mathit{sigs}:=sigs:= the first NsN_sNs​ entries of rrr, r:=r:=r:= the rest; fail if fewer than NsN_sNs​ were available.
    7. Compute multisigLoop(o,sigs,keys)\mathrm{multisigLoop}(o,\mathit{sigs},\mathit{keys})multisigLoop(o,sigs,keys) (defined above): fail if none\mathrm{none}none; else let okokok be its boolean.
    8. Fail if r=[ ]r=[\,]r=[]; else r=d′::r′r=d'::r'r=d′::r′. Fail if f.nulldummy=truef.\mathrm{nulldummy}=\mathrm{true}f.nulldummy=true and d′≠[ ]d'\ne[\,]d′=[].
    9. New main stack boolBytes(ok)::r′\mathrm{boolBytes}(ok)::r'boolBytes(ok)::r′, counter κ′\kappa'κ′.

The left-hand side of the theorem is this interpreter run on the initial main stack [s2,s1,d][s_2,s_1,d][s2​,s1​,d] over the five instructions op(0x52), push(k1), push(k2), op(0x52), op(0xae)\mathrm{op}(\mathtt{0x52}),\ \mathrm{push}(k_1),\ \mathrm{push}(k_2),\ \mathrm{op}(\mathtt{0x52}),\ \mathrm{op}(\mathtt{0xae})op(0x52), push(k1​), push(k2​), op(0x52), op(0xae), with the flags fff and the oracle ooo. Note that the interpreter imposes the 520520520-byte bound only on pushed data (here k1,k2k_1,k_2k1​,k2​, which the hypotheses already bound) and not on the elements s2,s1,ds_2,s_1,ds2​,s1​,d of the initial stack; that only f.nulldummyf.\mathrm{nulldummy}f.nulldummy among the flags is consulted by these opcodes; and that only o.checkSigo.\mathrm{checkSig}o.checkSig among the oracle's fields is consulted by them.

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