Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The received HTLC output under VerifyScript

Proved
BitcoinHtlc.received_p2wsh_spend

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

bip65bitcoinbitcoin-mainnetbolt3checkmultisigcltvformal-verificationhtlclightningp2wshscript

As offered_p2wsh_spend for the received script with ∣expiry∣<232|{\rm expiry}| < 2^{32}∣expiry∣<232: the output is spent only by the revocation key, by both HTLC keys with the payment preimage on the success transaction, or by the remote key after the lock time. Together with the to_local mission this covers every script of a BOLT #3 commitment transaction (non-anchor form).

Preamble
import Definitions.Def_BitcoinHtlc
import Definitions.Def_BitcoinVerify
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinSig
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinHtlc.received_p2wsh_spend (tap : BitcoinVerify.TaprootHandler) (c : BitcoinVerify.Ctx)
    (hf : c.flags.witness = true) (revHash remoteKey localKey payHash : Bytes) (expiry : Int) (ws : List Bytes)
    (hrev : revHash.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hrem : remoteKey.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hloc : localKey.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hpay : payHash.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hd : expiry.natAbs < 2 ^ 32) :
    BitcoinVerify.verifyScript tap c []
        (BitcoinVerify.witnessBytes 0 (BitcoinSer.sha256 (BitcoinHtlc.receivedBytes revHash remoteKey localKey payHash expiry)))
        (ws ++ [BitcoinHtlc.receivedBytes revHash remoteKey localKey payHash expiry]) = true ↔
      BitcoinScript.castToBool (BitcoinSer.sha256 (BitcoinHtlc.receivedBytes revHash remoteKey localKey payHash expiry)) = true ∧
      (∀ e ∈ ws, e.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) ∧
      BitcoinHtlc.ReceivedSpend (BitcoinVerify.scriptFlagsOf c.flags)
        (BitcoinSig.legacyOracle (BitcoinVerify.sigFlagsOf c.flags) c.tx c.nIn c.amount .witnessV0
          (BitcoinHtlc.receivedBytes revHash remoteKey localKey payHash expiry))
        revHash remoteKey localKey payHash expiry ws.reverse := by sorry
Source
BOLT #3, Bitcoin Transaction and Script Formats, 'Offered HTLC Outputs' and 'Received HTLC Outputs': https://github.com/lightning/bolts/blob/master/03-transactions.md#offered-htlc-outputs; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_DUP, OP_HASH160, OP_EQUAL, OP_IF/OP_NOTIF, OP_SWAP, OP_SIZE, OP_CHECKMULTISIG, OP_CHECKLOCKTIMEVERIFY, OP_CHECKSIG), GenericTransactionSignatureChecker::CheckLockTime (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); BIP65, 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: BitcoinHtlc.received_p2wsh_spend

Statement. Let tap\mathit{tap}tap be any Taproot handler (any function from a context, a list of byte strings and a byte string to a Boolean), ccc any verification context (a consensus flag set c.flagsc.\mathrm{flags}c.flags, a transaction c.txc.\mathit{tx}c.tx, an input index c.nInc.\mathit{nIn}c.nIn and an amount c.amount∈Zc.\mathit{amount} \in \mathbb{Z}c.amount∈Z) with the hypothesis c.flags.witness=truec.\mathrm{flags}.\mathrm{witness} = \mathrm{true}c.flags.witness=true, r,Kr,Kl,hr, K_r, K_l, hr,Kr​,Kl​,h any four byte strings with ∣r∣≤520|r| \le 520∣r∣≤520, ∣Kr∣≤520|K_r| \le 520∣Kr​∣≤520, ∣Kl∣≤520|K_l| \le 520∣Kl​∣≤520, ∣h∣≤520|h| \le 520∣h∣≤520, eee any integer with ∣e∣<232|e| < 2^{32}∣e∣<232 (absolute value; eee may be zero or negative), and ws\mathit{ws}ws any list of byte strings (possibly empty; its elements are not bounded by any hypothesis). Write B=RecB(r,Kr,Kl,h,e)B = \mathrm{RecB}(r, K_r, K_l, h, e)B=RecB(r,Kr​,Kl​,h,e) for the serialized received script and H=SHA256(B)H = \mathrm{SHA256}(B)H=SHA256(B) for its concrete SHA-256 digest (32 bytes). The theorem asserts

verifyScript(tap, c, [], witnessBytes(0,H), ws+ ⁣ ⁣+[B])=true  ⟺  castToBool(H)=true ∧ (∀ x∈ws, ∣x∣≤520) ∧ ReceivedSpend(F,OB,r,Kr,Kl,h,e,reverse(ws)),\mathrm{verifyScript}\bigl(\mathit{tap},\ c,\ [],\ \mathrm{witnessBytes}(0, H),\ \mathit{ws} \mathbin{+\!\!+} [B]\bigr) = \mathrm{true} \iff \mathrm{castToBool}(H) = \mathrm{true}\ \land\ \bigl(\forall\, x \in \mathit{ws},\ |x| \le 520\bigr)\ \land\ \mathrm{ReceivedSpend}\bigl(F, \mathcal{O}_B, r, K_r, K_l, h, e, \mathrm{reverse}(\mathit{ws})\bigr),verifyScript(tap, c, [], witnessBytes(0,H), ws++[B])=true⟺castToBool(H)=true ∧ (∀x∈ws, ∣x∣≤520) ∧ ReceivedSpend(F,OB​,r,Kr​,Kl​,h,e,reverse(ws)),

where: the scriptSig is the empty byte string; the scriptPubKey is witnessBytes(0,H)=[0x00,0x20]+ ⁣ ⁣+H\mathrm{witnessBytes}(0, H) = [0\mathrm{x}00, 0\mathrm{x}20] \mathbin{+\!\!+} HwitnessBytes(0,H)=[0x00,0x20]++H; the witness list is ws\mathit{ws}ws followed by the script bytes BBB as last element (never empty; just [B][B][B] when ws=[]\mathit{ws} = []ws=[]); F=scriptFlagsOf(c.flags)=(c.flags.cltv,c.flags.csv,c.flags.nulldummy)F = \mathrm{scriptFlagsOf}(c.\mathrm{flags}) = (c.\mathrm{flags}.\mathrm{cltv}, c.\mathrm{flags}.\mathrm{csv}, c.\mathrm{flags}.\mathrm{nulldummy})F=scriptFlagsOf(c.flags)=(c.flags.cltv,c.flags.csv,c.flags.nulldummy); and OB=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,witnessV0,B)\mathcal{O}_B = \mathcal{O}(\mathrm{sigFlagsOf}(c.\mathrm{flags}), c.\mathit{tx}, c.\mathit{nIn}, c.\mathit{amount}, \mathrm{witnessV0}, B)OB​=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,witnessV0,B) is the concrete legacy oracle with signature flags (c.flags.dersig,false,false,false)(c.\mathrm{flags}.\mathrm{dersig}, \mathrm{false}, \mathrm{false}, \mathrm{false})(c.flags.dersig,false,false,false), signature version witnessV0\mathrm{witnessV0}witnessV0 and script code BBB, so that in the right-hand side OB.hash160\mathcal{O}_B.\mathrm{hash160}OB​.hash160 is the concrete RIPEMD160∘SHA256\mathrm{RIPEMD160}\circ\mathrm{SHA256}RIPEMD160∘SHA256, OB.checkSig\mathcal{O}_B.\mathrm{checkSig}OB​.checkSig is the concrete BIP143 ECDSA check and OB.checkLockTime\mathcal{O}_B.\mathrm{checkLockTime}OB​.checkLockTime is CLT(c.tx,c.nIn,⋅)\mathrm{CLT}(c.\mathit{tx}, c.\mathit{nIn}, \cdot)CLT(c.tx,c.nIn,⋅), all described below; in particular the CltvPasses\mathrm{CltvPasses}CltvPasses conjunct of the timeout disjunct becomes F.cltv=false∨(0≤e∧CLT(c.tx,c.nIn,e)=true)F.\mathrm{cltv} = \mathrm{false} \lor (0 \le e \land \mathrm{CLT}(c.\mathit{tx}, c.\mathit{nIn}, e) = \mathrm{true})F.cltv=false∨(0≤e∧CLT(c.tx,c.nIn,e)=true). The stack handed to ReceivedSpend\mathrm{ReceivedSpend}ReceivedSpend is reverse(ws)\mathrm{reverse}(\mathit{ws})reverse(ws) (last element of ws\mathit{ws}ws on top), empty when ws\mathit{ws}ws is empty, in which case ReceivedSpend\mathrm{ReceivedSpend}ReceivedSpend is false since every disjunct requires a stack of length 222 or 444. The conjunct castToBool(H)=true\mathrm{castToBool}(H) = \mathrm{true}castToBool(H)=true says the digest is not all zero bytes and not all zero bytes with last byte 0x800\mathrm{x}800x80. Nothing requires rrr or hhh to be 20 bytes or to be hashes of anything.


Definitions unfolded

Basic notions used throughout. A byte is an 8-bit word and a byte string (written Bytes\mathrm{Bytes}Bytes) is a finite list of bytes; ∣b∣|b|∣b∣ denotes the length of a byte string bbb. The constant Lmax⁡=520L_{\max} = 520Lmax​=520 is the interpreter's maximum size of one stack element. A flag set fff consists of three Booleans f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy. An oracle ooo is an arbitrary structure supplying eight functions with no constraints whatsoever on their behaviour: 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} : \mathrm{Bytes}\to\mathrm{Bytes}o.ripemd160,o.sha1,o.sha256,o.hash160,o.hash256:Bytes→Bytes (so in particular o.hash160o.\mathrm{hash160}o.hash160 is any function from byte strings to byte strings, not necessarily RIPEMD160∘\circ∘SHA256, not necessarily 20-byte-valued), o.checkSig:Bytes→Bytes→Option Boolo.\mathrm{checkSig} : \mathrm{Bytes}\to\mathrm{Bytes}\to \mathrm{Option}\,\mathrm{Bool}o.checkSig:Bytes→Bytes→OptionBool (first argument the signature, second the public key; the value none\mathrm{none}none represents a script-aborting failure, some b\mathrm{some}\,bsomeb a verdict bbb), o.checkLockTime:Z→Boolo.\mathrm{checkLockTime} : \mathbb{Z}\to\mathrm{Bool}o.checkLockTime:Z→Bool and o.checkSequence:Z→Boolo.\mathrm{checkSequence} : \mathbb{Z}\to\mathrm{Bool}o.checkSequence:Z→Bool. Stacks are lists written top element first. castToBool(b)\mathrm{castToBool}(b)castToBool(b) is: false for the empty string; for a one-byte string [x][x][x], true iff x≠0x\neq 0x=0 and x≠0x80x \neq 0\mathrm{x}80x=0x80; for x::rx :: rx::r with rrr non-empty, true iff x≠0x\neq 0x=0 or castToBool(r)\mathrm{castToBool}(r)castToBool(r) (so a string of zero bytes whose last byte is 0x800\mathrm{x}800x80 is false). boolBytes(true)=[0x01]\mathrm{boolBytes}(\mathrm{true}) = [0\mathrm{x}01]boolBytes(true)=[0x01] and boolBytes(false)=[]\mathrm{boolBytes}(\mathrm{false}) = []boolBytes(false)=[] (the empty string). The script-number encoding ser(v)\mathrm{ser}(v)ser(v) of an integer vvv is: [][][] if v=0v = 0v=0; otherwise the little-endian bytes of ∣v∣|v|∣v∣ with no trailing zero byte, then, if the last of those bytes has its top bit (0x800\mathrm{x}800x80) set, an extra byte 0x800\mathrm{x}800x80 (for v<0v<0v<0) or 0x000\mathrm{x}000x00 (for v>0v>0v>0) is appended, and otherwise, for v<0v<0v<0, the top bit of the last byte is set. For example ser(2)=[0x02]\mathrm{ser}(2) = [0\mathrm{x}02]ser(2)=[0x02] and ser(32)=[0x20]\mathrm{ser}(32) = [0\mathrm{x}20]ser(32)=[0x20]. The decoding numk(b)\mathrm{num}_k(b)numk​(b) ("script number of at most kkk bytes, non-minimal encodings allowed") is none\mathrm{none}none if ∣b∣>k|b| > k∣b∣>k, and otherwise some\mathrm{some}some of the little-endian value of bbb with the top bit of the last byte read as a sign (the empty string decodes to 000).

The number push numInstr(n)\mathrm{numInstr}(n)numInstr(n) / numBytes(n)\mathrm{numBytes}(n)numBytes(n). For an integer nnn, numInstr(n)\mathrm{numInstr}(n)numInstr(n) is the single opcode with byte value n+0x50n + 0\mathrm{x}50n+0x50 when n=−1n = -1n=−1 or 1≤n≤161 \le n \le 161≤n≤16 (so numInstr(−1)\mathrm{numInstr}(-1)numInstr(−1) is the opcode 0x4f0\mathrm{x}4\mathrm{f}0x4f, numInstr(2)\mathrm{numInstr}(2)numInstr(2) is the opcode 0x520\mathrm{x}520x52, i.e. OP_2), and otherwise it is the data push of ser(n)\mathrm{ser}(n)ser(n) (so numInstr(32)\mathrm{numInstr}(32)numInstr(32) is the push of the one-byte string [0x20][0\mathrm{x}20][0x20], and numInstr(0)\mathrm{numInstr}(0)numInstr(0) is the push of the empty string). numBytes(n)\mathrm{numBytes}(n)numBytes(n) is the byte-level form: the one opcode byte n+0x50n + 0\mathrm{x}50n+0x50 in the first case, and pushBytes(ser(n))\mathrm{pushBytes}(\mathrm{ser}(n))pushBytes(ser(n)) otherwise, where pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d) is the canonical push encoding of a byte string ddd: [ ∣d∣ ]+ ⁣ ⁣+d[\,|d|\,] \mathbin{+\!\!+} d[∣d∣]++d if ∣d∣<0x4c|d| < 0\mathrm{x}4\mathrm{c}∣d∣<0x4c; [0x4c,∣d∣]+ ⁣ ⁣+d[0\mathrm{x}4\mathrm{c}, |d|] \mathbin{+\!\!+} d[0x4c,∣d∣]++d if ∣d∣≤0xff|d| \le 0\mathrm{xff}∣d∣≤0xff; [0x4d]+ ⁣ ⁣+(2 little-endian bytes of ∣d∣)+ ⁣ ⁣+d[0\mathrm{x}4\mathrm{d}] \mathbin{+\!\!+} (\text{2 little-endian bytes of } |d|) \mathbin{+\!\!+} d[0x4d]++(2 little-endian bytes of ∣d∣)++d if ∣d∣≤0xffff|d| \le 0\mathrm{xffff}∣d∣≤0xffff; and [0x4e]+ ⁣ ⁣+(4 little-endian bytes of ∣d∣)+ ⁣ ⁣+d[0\mathrm{x}4\mathrm{e}] \mathbin{+\!\!+} (\text{4 little-endian bytes of } |d|) \mathbin{+\!\!+} d[0x4e]++(4 little-endian bytes of ∣d∣)++d otherwise.

The two witness scripts as byte strings. OffB(r,Kr,Kl,h)\mathrm{OffB}(r, K_r, K_l, h)OffB(r,Kr​,Kl​,h) is the byte string

[0x76,0xa9]+ ⁣ ⁣+pushBytes(r)+ ⁣ ⁣+[0x87,0x63,0xac,0x67]+ ⁣ ⁣+pushBytes(Kr)+ ⁣ ⁣+[0x7c,0x82]+ ⁣ ⁣+numBytes(32)+ ⁣ ⁣+[0x87,0x64,0x75]+ ⁣ ⁣+numBytes(2)+ ⁣ ⁣+[0x7c]+ ⁣ ⁣+pushBytes(Kl)+ ⁣ ⁣+numBytes(2)+ ⁣ ⁣+[0xae,0x67,0xa9]+ ⁣ ⁣+pushBytes(h)+ ⁣ ⁣+[0x88,0xac,0x68,0x68][0\mathrm{x}76, 0\mathrm{xa}9] \mathbin{+\!\!+} \mathrm{pushBytes}(r) \mathbin{+\!\!+} [0\mathrm{x}87, 0\mathrm{x}63, 0\mathrm{xac}, 0\mathrm{x}67] \mathbin{+\!\!+} \mathrm{pushBytes}(K_r) \mathbin{+\!\!+} [0\mathrm{x}7\mathrm{c}, 0\mathrm{x}82] \mathbin{+\!\!+} \mathrm{numBytes}(32) \mathbin{+\!\!+} [0\mathrm{x}87, 0\mathrm{x}64, 0\mathrm{x}75] \mathbin{+\!\!+} \mathrm{numBytes}(2) \mathbin{+\!\!+} [0\mathrm{x}7\mathrm{c}] \mathbin{+\!\!+} \mathrm{pushBytes}(K_l) \mathbin{+\!\!+} \mathrm{numBytes}(2) \mathbin{+\!\!+} [0\mathrm{xae}, 0\mathrm{x}67, 0\mathrm{xa}9] \mathbin{+\!\!+} \mathrm{pushBytes}(h) \mathbin{+\!\!+} [0\mathrm{x}88, 0\mathrm{xac}, 0\mathrm{x}68, 0\mathrm{x}68][0x76,0xa9]++pushBytes(r)++[0x87,0x63,0xac,0x67]++pushBytes(Kr​)++[0x7c,0x82]++numBytes(32)++[0x87,0x64,0x75]++numBytes(2)++[0x7c]++pushBytes(Kl​)++numBytes(2)++[0xae,0x67,0xa9]++pushBytes(h)++[0x88,0xac,0x68,0x68]

(the opcode bytes are OP_DUP OP_HASH160 … OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE … OP_SWAP OP_SIZE … OP_EQUAL OP_NOTIF OP_DROP … OP_SWAP … OP_CHECKMULTISIG OP_ELSE OP_HASH160 … OP_EQUALVERIFY OP_CHECKSIG OP_ENDIF OP_ENDIF; numBytes(32)=[0x01,0x20]\mathrm{numBytes}(32) = [0\mathrm{x}01, 0\mathrm{x}20]numBytes(32)=[0x01,0x20] and numBytes(2)=[0x52]\mathrm{numBytes}(2) = [0\mathrm{x}52]numBytes(2)=[0x52]). RecB(r,Kr,Kl,h,e)\mathrm{RecB}(r, K_r, K_l, h, e)RecB(r,Kr​,Kl​,h,e) is the byte string

[0x76,0xa9]+ ⁣ ⁣+pushBytes(r)+ ⁣ ⁣+[0x87,0x63,0xac,0x67]+ ⁣ ⁣+pushBytes(Kr)+ ⁣ ⁣+[0x7c,0x82]+ ⁣ ⁣+numBytes(32)+ ⁣ ⁣+[0x87,0x63,0xa9]+ ⁣ ⁣+pushBytes(h)+ ⁣ ⁣+[0x88]+ ⁣ ⁣+numBytes(2)+ ⁣ ⁣+[0x7c]+ ⁣ ⁣+pushBytes(Kl)+ ⁣ ⁣+numBytes(2)+ ⁣ ⁣+[0xae,0x67,0x75]+ ⁣ ⁣+numBytes(e)+ ⁣ ⁣+[0xb1,0x75,0xac,0x68,0x68][0\mathrm{x}76, 0\mathrm{xa}9] \mathbin{+\!\!+} \mathrm{pushBytes}(r) \mathbin{+\!\!+} [0\mathrm{x}87, 0\mathrm{x}63, 0\mathrm{xac}, 0\mathrm{x}67] \mathbin{+\!\!+} \mathrm{pushBytes}(K_r) \mathbin{+\!\!+} [0\mathrm{x}7\mathrm{c}, 0\mathrm{x}82] \mathbin{+\!\!+} \mathrm{numBytes}(32) \mathbin{+\!\!+} [0\mathrm{x}87, 0\mathrm{x}63, 0\mathrm{xa}9] \mathbin{+\!\!+} \mathrm{pushBytes}(h) \mathbin{+\!\!+} [0\mathrm{x}88] \mathbin{+\!\!+} \mathrm{numBytes}(2) \mathbin{+\!\!+} [0\mathrm{x}7\mathrm{c}] \mathbin{+\!\!+} \mathrm{pushBytes}(K_l) \mathbin{+\!\!+} \mathrm{numBytes}(2) \mathbin{+\!\!+} [0\mathrm{xae}, 0\mathrm{x}67, 0\mathrm{x}75] \mathbin{+\!\!+} \mathrm{numBytes}(e) \mathbin{+\!\!+} [0\mathrm{xb}1, 0\mathrm{x}75, 0\mathrm{xac}, 0\mathrm{x}68, 0\mathrm{x}68][0x76,0xa9]++pushBytes(r)++[0x87,0x63,0xac,0x67]++pushBytes(Kr​)++[0x7c,0x82]++numBytes(32)++[0x87,0x63,0xa9]++pushBytes(h)++[0x88]++numBytes(2)++[0x7c]++pushBytes(Kl​)++numBytes(2)++[0xae,0x67,0x75]++numBytes(e)++[0xb1,0x75,0xac,0x68,0x68]

(… OP_EQUAL OP_IF OP_HASH160 … OP_EQUALVERIFY … OP_SWAP … OP_CHECKMULTISIG OP_ELSE OP_DROP <e> OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG OP_ENDIF OP_ENDIF), where numBytes(e)\mathrm{numBytes}(e)numBytes(e) is the single byte e+0x50e + 0\mathrm{x}50e+0x50 if e=−1e = -1e=−1 or 1≤e≤161 \le e \le 161≤e≤16 and pushBytes(ser(e))\mathrm{pushBytes}(\mathrm{ser}(e))pushBytes(ser(e)) otherwise.

Byte-level parsing parse(s)\mathrm{parse}(s)parse(s). parse\mathrm{parse}parse reads a byte string instruction by instruction with a fuel of ∣s∣|s|∣s∣ steps and yields none\mathrm{none}none on any malformed push and some\mathrm{some}some of the instruction list otherwise. One instruction is read from a first byte bbb as follows: if b≤0x4eb \le 0\mathrm{x}4\mathrm{e}b≤0x4e it is a data push, whose length is bbb itself when b<0x4cb < 0\mathrm{x}4\mathrm{c}b<0x4c, the next one byte when b=0x4cb = 0\mathrm{x}4\mathrm{c}b=0x4c, the next two bytes little-endian when b=0x4db = 0\mathrm{x}4\mathrm{d}b=0x4d, and the next four bytes little-endian when b=0x4eb = 0\mathrm{x}4\mathrm{e}b=0x4e (failing if those length bytes are missing), and the push fails if fewer bytes than the announced length remain; otherwise (b>0x4eb > 0\mathrm{x}4\mathrm{e}b>0x4e) it is the non-push opcode bbb. The empty string parses to the empty instruction list.

The two witness scripts as instruction lists. Writing ⟨d⟩\langle d\rangle⟨d⟩ for the data push of the byte string ddd, the offered script Off(r,Kr,Kl,h)\mathrm{Off}(r, K_r, K_l, h)Off(r,Kr​,Kl​,h), for byte strings rrr (the "revocation hash"), KrK_rKr​ (the "remote key"), KlK_lKl​ (the "local key") and hhh (the "payment hash"), all four being completely unconstrained parameters (any byte strings, not necessarily 20 bytes, not necessarily hashes of anything), is the 26-instruction list

OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_NOTIF OP_DROP OP_2 OP_SWAP ⟨Kl⟩ OP_2 OP_CHECKMULTISIG OP_ELSE OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_CHECKSIG OP_ENDIF OP_ENDIF,\begin{aligned}&\texttt{OP\_DUP}\ \texttt{OP\_HASH160}\ \langle r\rangle\ \texttt{OP\_EQUAL}\ \texttt{OP\_IF}\ \texttt{OP\_CHECKSIG}\ \texttt{OP\_ELSE}\ \langle K_r\rangle\ \texttt{OP\_SWAP}\ \texttt{OP\_SIZE}\ \langle[0\mathrm{x}20]\rangle\ \texttt{OP\_EQUAL}\\ &\texttt{OP\_NOTIF}\ \texttt{OP\_DROP}\ \texttt{OP\_2}\ \texttt{OP\_SWAP}\ \langle K_l\rangle\ \texttt{OP\_2}\ \texttt{OP\_CHECKMULTISIG}\ \texttt{OP\_ELSE}\ \texttt{OP\_HASH160}\ \langle h\rangle\ \texttt{OP\_EQUALVERIFY}\ \texttt{OP\_CHECKSIG}\ \texttt{OP\_ENDIF}\ \texttt{OP\_ENDIF},\end{aligned}​OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr​⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_NOTIF OP_DROP OP_2 OP_SWAP ⟨Kl​⟩ OP_2 OP_CHECKMULTISIG OP_ELSE OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_CHECKSIG OP_ENDIF OP_ENDIF,​

where ⟨[0x20]⟩\langle[0\mathrm{x}20]\rangle⟨[0x20]⟩ is numInstr(32)\mathrm{numInstr}(32)numInstr(32) and OP_2 is numInstr(2)\mathrm{numInstr}(2)numInstr(2), the opcode byte 0x520\mathrm{x}520x52. The received script Rec(r,Kr,Kl,h,e)\mathrm{Rec}(r, K_r, K_l, h, e)Rec(r,Kr​,Kl​,h,e) additionally takes an integer eee (the "expiry", any integer, possibly negative or zero) and is the 28-instruction list

OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_IF OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_2 OP_SWAP ⟨Kl⟩ OP_2 OP_CHECKMULTISIGOP_ELSE OP_DROP numInstr(e) OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG OP_ENDIF OP_ENDIF,\begin{aligned}&\texttt{OP\_DUP}\ \texttt{OP\_HASH160}\ \langle r\rangle\ \texttt{OP\_EQUAL}\ \texttt{OP\_IF}\ \texttt{OP\_CHECKSIG}\ \texttt{OP\_ELSE}\ \langle K_r\rangle\ \texttt{OP\_SWAP}\ \texttt{OP\_SIZE}\ \langle[0\mathrm{x}20]\rangle\ \texttt{OP\_EQUAL}\\ &\texttt{OP\_IF}\ \texttt{OP\_HASH160}\ \langle h\rangle\ \texttt{OP\_EQUALVERIFY}\ \texttt{OP\_2}\ \texttt{OP\_SWAP}\ \langle K_l\rangle\ \texttt{OP\_2}\ \texttt{OP\_CHECKMULTISIG}\\ &\texttt{OP\_ELSE}\ \texttt{OP\_DROP}\ \mathrm{numInstr}(e)\ \texttt{OP\_CHECKLOCKTIMEVERIFY}\ \texttt{OP\_DROP}\ \texttt{OP\_CHECKSIG}\ \texttt{OP\_ENDIF}\ \texttt{OP\_ENDIF},\end{aligned}​OP_DUP OP_HASH160 ⟨r⟩ OP_EQUAL OP_IF OP_CHECKSIG OP_ELSE ⟨Kr​⟩ OP_SWAP OP_SIZE ⟨[0x20]⟩ OP_EQUALOP_IF OP_HASH160 ⟨h⟩ OP_EQUALVERIFY OP_2 OP_SWAP ⟨Kl​⟩ OP_2 OP_CHECKMULTISIGOP_ELSE OP_DROP numInstr(e) OP_CHECKLOCKTIMEVERIFY OP_DROP OP_CHECKSIG OP_ENDIF OP_ENDIF,​

where numInstr(e)\mathrm{numInstr}(e)numInstr(e) is the opcode e+0x50e + 0\mathrm{x}50e+0x50 if e=−1e = -1e=−1 or 1≤e≤161\le e\le 161≤e≤16, and the data push of ser(e)\mathrm{ser}(e)ser(e) otherwise (the empty push when e=0e = 0e=0; a push carrying a sign bit when e<−1e < -1e<−1).

The interpreter evalf,o(st,script)\mathrm{eval}_{f,o}(\mathit{st}, \mathit{script})evalf,o​(st,script). This is the transcription of Bitcoin Core's legacy EvalScript: starting from the state (main stack st\mathit{st}st, empty alt stack, empty condition stack, operation count 000), it processes the instructions of script\mathit{script}script in order and returns none\mathrm{none}none ("script failure") or some\mathrm{some}some of the final main stack. One instruction is processed as follows. A data push of ddd fails if ∣d∣>520|d| > 520∣d∣>520; otherwise ddd is pushed onto the main stack when every entry of the condition stack is true (otherwise the state is unchanged), and the step fails if the main and alt stacks then hold more than 100010001000 elements together. An opcode ccc is "counted" when c>0x60c > 0\mathrm{x}60c>0x60 (OP_16); a counted opcode fails if the count already equals 201201201, and otherwise increments the count; any of the fifteen disabled opcodes (OP_CAT, OP_SUBSTR, OP_LEFT, OP_RIGHT, OP_INVERT, OP_AND, OP_OR, OP_XOR, OP_2MUL, OP_2DIV, OP_MUL, OP_DIV, OP_MOD, OP_LSHIFT, OP_RSHIFT) fails even when not executed; then, if every entry of the condition stack is true ("executing") or ccc is one of OP_IF, OP_NOTIF, OP_ELSE, OP_ENDIF (any byte from 0x630\mathrm{x}630x63 to 0x680\mathrm{x}680x68 inclusive, which also includes the bytes 0x650\mathrm{x}650x65 and 0x660\mathrm{x}660x66, for which execution fails), the opcode is executed and the 1000-element stack bound re-checked; an unexecuted opcode leaves the state alone. After the last instruction the run fails if the condition stack is non-empty. The executed opcodes relevant here behave as follows (with "fail" meaning none\mathrm{none}none): OP_1…OP_16 push ser(c−0x50)\mathrm{ser}(c - 0\mathrm{x}50)ser(c−0x50) (so OP_2 pushes [0x02][0\mathrm{x}02][0x02]; these are not counted); OP_DUP fails on an empty stack and otherwise duplicates the top; OP_DROP fails on an empty stack and otherwise removes the top; OP_SWAP fails with fewer than two elements and otherwise exchanges the top two; OP_SIZE fails on an empty stack and otherwise pushes ser(∣top∣)\mathrm{ser}(|\mathrm{top}|)ser(∣top∣) above the unchanged top; OP_HASH160 fails on an empty stack and otherwise replaces the top ttt by o.hash160(t)o.\mathrm{hash160}(t)o.hash160(t); OP_EQUAL fails with fewer than two elements and otherwise pops the top two aaa (top) and bbb and pushes boolBytes(b=a)\mathrm{boolBytes}(b = a)boolBytes(b=a) (byte-string equality), while OP_EQUALVERIFY pops them and fails unless b=ab = ab=a; OP_IF (resp. OP_NOTIF), when executing, fails on an empty stack and otherwise pops the top ttt and pushes castToBool(t)\mathrm{castToBool}(t)castToBool(t) (resp. its negation) onto the condition stack, and when not executing pushes false onto the condition stack without touching the main stack; OP_ELSE fails on an empty condition stack and otherwise negates its top; OP_ENDIF fails on an empty condition stack and otherwise pops it; OP_CHECKSIG fails with fewer than two elements and otherwise pops pk\mathit{pk}pk (top) and sig\mathit{sig}sig, fails if o.checkSig(sig,pk)=noneo.\mathrm{checkSig}(\mathit{sig}, \mathit{pk}) = \mathrm{none}o.checkSig(sig,pk)=none, and pushes boolBytes(b)\mathrm{boolBytes}(b)boolBytes(b) if it is some b\mathrm{some}\,bsomeb; OP_CHECKLOCKTIMEVERIFY is a no-op if f.cltvf.\mathrm{cltv}f.cltv is false, and otherwise fails on an empty stack, decodes the top as num5\mathrm{num}_5num5​ (failing if it has more than 555 bytes), fails if the value nnn is negative or o.checkLockTime(n)o.\mathrm{checkLockTime}(n)o.checkLockTime(n) is false, and otherwise leaves the state unchanged (the operand stays on the stack); OP_CHECKMULTISIG fails on an empty stack and otherwise pops nkn_knk​ decoded as num4\mathrm{num}_4num4​ (failing if undecodable, negative or >20> 20>20), adds the value to the operation count (failing if that exceeds 201201201), takes exactly that many keys from the stack (failing if too few), pops nsn_sns​ decoded as num4\mathrm{num}_4num4​ (failing if undecodable, negative or >nk> n_k>nk​), takes exactly that many signatures (failing if too few), computes msLoopo(sigs,keys)\mathrm{msLoop}_o(\mathit{sigs}, \mathit{keys})msLoopo​(sigs,keys) (failing if it is none\mathrm{none}none), then pops one more element dummy\mathit{dummy}dummy (failing if the stack is empty), fails if f.nulldummyf.\mathrm{nulldummy}f.nulldummy is true and dummy\mathit{dummy}dummy is non-empty, and finally pushes boolBytes\mathrm{boolBytes}boolBytes of the loop's verdict.

The multisignature matching loop. msLoopo(sigs,keys)\mathrm{msLoop}_o(\mathit{sigs}, \mathit{keys})msLoopo​(sigs,keys), for lists of signatures and keys (top first), is defined by recursion: it is some true\mathrm{some}\,\mathrm{true}sometrue when sigs\mathit{sigs}sigs is empty; some false\mathrm{some}\,\mathrm{false}somefalse when sigs\mathit{sigs}sigs is non-empty and keys\mathit{keys}keys is empty; and for sigs=s::S\mathit{sigs} = s :: Ssigs=s::S, keys=k::K\mathit{keys} = k :: Kkeys=k::K it evaluates o.checkSig(s,k)o.\mathrm{checkSig}(s, k)o.checkSig(s,k): if that is none\mathrm{none}none the loop is none\mathrm{none}none; if it is some true\mathrm{some}\,\mathrm{true}sometrue the loop is some false\mathrm{some}\,\mathrm{false}somefalse when ∣K∣<∣S∣|K| < |S|∣K∣<∣S∣ and otherwise msLoopo(S,K)\mathrm{msLoop}_o(S, K)msLoopo​(S,K); if it is some false\mathrm{some}\,\mathrm{false}somefalse the loop is some false\mathrm{some}\,\mathrm{false}somefalse when ∣K∣<∣S∣+1|K| < |S| + 1∣K∣<∣S∣+1 and otherwise msLoopo(s::S,K)\mathrm{msLoop}_o(s :: S, K)msLoopo​(s::S,K). Unfolded on exactly two signatures and two keys, msLoopo([s1,s2],[k1,k2])\mathrm{msLoop}_o([s_1, s_2], [k_1, k_2])msLoopo​([s1​,s2​],[k1​,k2​]) is: none\mathrm{none}none if o.checkSig(s1,k1)=noneo.\mathrm{checkSig}(s_1, k_1) = \mathrm{none}o.checkSig(s1​,k1​)=none; some false\mathrm{some}\,\mathrm{false}somefalse if o.checkSig(s1,k1)=some falseo.\mathrm{checkSig}(s_1, k_1) = \mathrm{some}\,\mathrm{false}o.checkSig(s1​,k1​)=somefalse (since 1<21 < 21<2; the second signature is then never checked); and if 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, some true\mathrm{some}\,\mathrm{true}sometrue or some false\mathrm{some}\,\mathrm{false}somefalse according as o.checkSig(s2,k2)o.\mathrm{checkSig}(s_2, k_2)o.checkSig(s2​,k2​) is none\mathrm{none}none, some true\mathrm{some}\,\mathrm{true}sometrue or some false\mathrm{some}\,\mathrm{false}somefalse.

The lock-time predicate. CltvPasses(f,o,e)\mathrm{CltvPasses}(f, o, e)CltvPasses(f,o,e), for a flag set fff, an oracle ooo and an integer eee, is the proposition

f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true),f.\mathrm{cltv} = \mathrm{false}\ \lor\ \bigl(0 \le e\ \land\ o.\mathrm{checkLockTime}(e) = \mathrm{true}\bigr),f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true),

so it holds unconditionally when the cltv flag is off, and otherwise requires eee non-negative and the oracle's lock-time check to accept eee.

The spend predicates. OfferedSpend(f,o,r,Kr,Kl,h,st)\mathrm{OfferedSpend}(f, o, r, K_r, K_l, h, \mathit{st})OfferedSpend(f,o,r,Kr​,Kl​,h,st), for a flag set fff, an oracle ooo, byte strings r,Kr,Kl,hr, K_r, K_l, hr,Kr​,Kl​,h and a list of byte strings st\mathit{st}st (a stack, top first), is the disjunction of the following three propositions:

  1. (revocation form) there exist byte strings pk,sig\mathit{pk}, \mathit{sig}pk,sig with st=[pk,sig]\mathit{st} = [\mathit{pk}, \mathit{sig}]st=[pk,sig], o.hash160(pk)=ro.\mathrm{hash160}(\mathit{pk}) = ro.hash160(pk)=r and o.checkSig(sig,pk)=some trueo.\mathrm{checkSig}(\mathit{sig}, \mathit{pk}) = \mathrm{some}\,\mathrm{true}o.checkSig(sig,pk)=sometrue;
  2. (preimage form) there exist byte strings pre,sig\mathit{pre}, \mathit{sig}pre,sig with st=[pre,sig]\mathit{st} = [\mathit{pre}, \mathit{sig}]st=[pre,sig], o.hash160(pre)≠ro.\mathrm{hash160}(\mathit{pre}) \ne ro.hash160(pre)=r, ∣pre∣=32|\mathit{pre}| = 32∣pre∣=32, o.hash160(pre)=ho.\mathrm{hash160}(\mathit{pre}) = ho.hash160(pre)=h and o.checkSig(sig,Kr)=some trueo.\mathrm{checkSig}(\mathit{sig}, K_r) = \mathrm{some}\,\mathrm{true}o.checkSig(sig,Kr​)=sometrue;
  3. (timeout form) there exist byte strings x,σl,σr,dx, \sigma_l, \sigma_r, dx,σl​,σr​,d with st=[x,σl,σr,d]\mathit{st} = [x, \sigma_l, \sigma_r, d]st=[x,σl​,σr​,d], o.hash160(x)≠ro.\mathrm{hash160}(x) \ne ro.hash160(x)=r, ∣x∣≠32|x| \ne 32∣x∣=32, msLoopo([σl,σr],[Kl,Kr])=some true\mathrm{msLoop}_o([\sigma_l, \sigma_r], [K_l, K_r]) = \mathrm{some}\,\mathrm{true}msLoopo​([σl​,σr​],[Kl​,Kr​])=sometrue, and (f.nulldummy=truef.\mathrm{nulldummy} = \mathrm{true}f.nulldummy=true implies d=[]d = []d=[]).

In particular the predicate is false whenever st\mathit{st}st has a length other than 222 or 444 (e.g. the empty stack), and no size bound is placed on pk,sig,pre,x,σl,σr,d\mathit{pk}, \mathit{sig}, \mathit{pre}, x, \sigma_l, \sigma_r, dpk,sig,pre,x,σl​,σr​,d by the predicate itself. ReceivedSpend(f,o,r,Kr,Kl,h,e,st)\mathrm{ReceivedSpend}(f, o, r, K_r, K_l, h, e, \mathit{st})ReceivedSpend(f,o,r,Kr​,Kl​,h,e,st), with additionally an integer eee, is the disjunction of:

  1. (revocation form) there exist pk,sig\mathit{pk}, \mathit{sig}pk,sig with st=[pk,sig]\mathit{st} = [\mathit{pk}, \mathit{sig}]st=[pk,sig], o.hash160(pk)=ro.\mathrm{hash160}(\mathit{pk}) = ro.hash160(pk)=r and o.checkSig(sig,pk)=some trueo.\mathrm{checkSig}(\mathit{sig}, \mathit{pk}) = \mathrm{some}\,\mathrm{true}o.checkSig(sig,pk)=sometrue;
  2. (success form) there exist pre,σl,σr,d\mathit{pre}, \sigma_l, \sigma_r, dpre,σl​,σr​,d with st=[pre,σl,σr,d]\mathit{st} = [\mathit{pre}, \sigma_l, \sigma_r, d]st=[pre,σl​,σr​,d], o.hash160(pre)≠ro.\mathrm{hash160}(\mathit{pre}) \ne ro.hash160(pre)=r, ∣pre∣=32|\mathit{pre}| = 32∣pre∣=32, o.hash160(pre)=ho.\mathrm{hash160}(\mathit{pre}) = ho.hash160(pre)=h, msLoopo([σl,σr],[Kl,Kr])=some true\mathrm{msLoop}_o([\sigma_l, \sigma_r], [K_l, K_r]) = \mathrm{some}\,\mathrm{true}msLoopo​([σl​,σr​],[Kl​,Kr​])=sometrue, and (f.nulldummy=truef.\mathrm{nulldummy} = \mathrm{true}f.nulldummy=true implies d=[]d = []d=[]);
  3. (timeout form) there exist x,sigx, \mathit{sig}x,sig with st=[x,sig]\mathit{st} = [x, \mathit{sig}]st=[x,sig], o.hash160(x)≠ro.\mathrm{hash160}(x) \ne ro.hash160(x)=r, ∣x∣≠32|x| \ne 32∣x∣=32, CltvPasses(f,o,e)\mathrm{CltvPasses}(f, o, e)CltvPasses(f,o,e) and o.checkSig(sig,Kr)=some trueo.\mathrm{checkSig}(\mathit{sig}, K_r) = \mathrm{some}\,\mathrm{true}o.checkSig(sig,Kr​)=sometrue.

The concrete oracle O(sf,tx,n,a,v,sc)\mathcal{O}(\mathit{sf}, \mathit{tx}, n, a, v, \mathit{sc})O(sf,tx,n,a,v,sc) ("legacy oracle") for signature-layer flags sf\mathit{sf}sf, a transaction tx\mathit{tx}tx, an input index nnn, an amount a∈Za \in \mathbb{Z}a∈Z, a signature version v∈{base,witnessV0}v \in \{\mathrm{base}, \mathrm{witnessV0}\}v∈{base,witnessV0} and a script-code byte string sc\mathit{sc}sc is the oracle whose five hash functions are the concrete transcriptions of SHA-1, SHA-256, RIPEMD-160, hash256=SHA256∘SHA256\mathrm{hash256} = \mathrm{SHA256}\circ\mathrm{SHA256}hash256=SHA256∘SHA256 and hash160=RIPEMD160∘SHA256\mathrm{hash160} = \mathrm{RIPEMD160}\circ\mathrm{SHA256}hash160=RIPEMD160∘SHA256; whose checkLockTime\mathrm{checkLockTime}checkLockTime is CLT(tx,n,⋅)\mathrm{CLT}(\mathit{tx}, n, \cdot)CLT(tx,n,⋅) and checkSequence\mathrm{checkSequence}checkSequence the analogous transcription of CheckSequence; and whose checkSig(sig,pk)\mathrm{checkSig}(\mathit{sig}, \mathit{pk})checkSig(sig,pk) is the pre-tapscript check: for v=witnessV0v = \mathrm{witnessV0}v=witnessV0 the script code is used as is (for v=basev = \mathrm{base}v=base every push of sig\mathit{sig}sig is first deleted from it); it is none\mathrm{none}none if the signature-encoding check or the public-key-encoding check under sf\mathit{sf}sf fails, and otherwise some\mathrm{some}some of the ECDSA verdict. The signature-layer flags are four Booleans dersig,lowS,strictenc,witnessPubkeyType\mathrm{dersig}, \mathrm{lowS}, \mathrm{strictenc}, \mathrm{witnessPubkeyType}dersig,lowS,strictenc,witnessPubkeyType; the signature-encoding check accepts an empty signature, otherwise rejects a non-strict-DER encoding when any of dersig,lowS,strictenc\mathrm{dersig}, \mathrm{lowS}, \mathrm{strictenc}dersig,lowS,strictenc is set, rejects a high-S signature when lowS\mathrm{lowS}lowS is set, and rejects an undefined hash-type byte when strictenc\mathrm{strictenc}strictenc is set; the public-key-encoding check rejects a key that is neither compressed nor uncompressed when strictenc\mathrm{strictenc}strictenc is set and a non-compressed key under witnessV0\mathrm{witnessV0}witnessV0 when witnessPubkeyType\mathrm{witnessPubkeyType}witnessPubkeyType is set. The ECDSA verdict is false when the key's header byte does not announce its length (0x02/0x030\mathrm{x}02/0\mathrm{x}030x02/0x03 for 33 bytes, 0x04/0x06/0x070\mathrm{x}04/0\mathrm{x}06/0\mathrm{x}070x04/0x06/0x07 for 65 bytes, anything else invalid), when the signature is empty, or when v=witnessV0v = \mathrm{witnessV0}v=witnessV0 and a<0a < 0a<0; otherwise the last byte of the signature is the hash type, the signature hash is the BIP143 digest (for witnessV0\mathrm{witnessV0}witnessV0, over tx\mathit{tx}tx, input nnn, the script code, the amount aaa and the hash type) or the legacy digest (for base\mathrm{base}base), and the verdict is secp256k1 ECDSA verification of the remaining signature bytes (lax DER parsing, S normalised to the low half, the digest reduced modulo the group order) against the parsed key. CLT(tx,n,t)\mathrm{CLT}(\mathit{tx}, n, t)CLT(tx,n,t), for t∈Zt \in \mathbb{Z}t∈Z, is: false unless either both tx.nLockTime<500 000 000\mathit{tx}.\mathrm{nLockTime} < 500\,000\,000tx.nLockTime<500000000 and t<500 000 000t < 500\,000\,000t<500000000, or both tx.nLockTime≥500 000 000\mathit{tx}.\mathrm{nLockTime} \ge 500\,000\,000tx.nLockTime≥500000000 and t≥500 000 000t \ge 500\,000\,000t≥500000000; then false if tx.nLockTime<t\mathit{tx}.\mathrm{nLockTime} < ttx.nLockTime<t; then false if the nSequence of input nnn of tx\mathit{tx}tx equals 0xffffffff0\mathrm{xffffffff}0xffffffff, where, if nnn is not a valid input index, a default input with nSequence 000 is used; and true otherwise. When the oracle comes from a consensus flag set FFF (Booleans p2sh,witness,taproot,dersig,cltv,csv,nulldummy\mathrm{p2sh}, \mathrm{witness}, \mathrm{taproot}, \mathrm{dersig}, \mathrm{cltv}, \mathrm{csv}, \mathrm{nulldummy}p2sh,witness,taproot,dersig,cltv,csv,nulldummy), the interpreter flags are scriptFlagsOf(F)=(F.cltv,F.csv,F.nulldummy)\mathrm{scriptFlagsOf}(F) = (F.\mathrm{cltv}, F.\mathrm{csv}, F.\mathrm{nulldummy})scriptFlagsOf(F)=(F.cltv,F.csv,F.nulldummy) and the signature-layer flags are sigFlagsOf(F)=(F.dersig,false,false,false)\mathrm{sigFlagsOf}(F) = (F.\mathrm{dersig}, \mathrm{false}, \mathrm{false}, \mathrm{false})sigFlagsOf(F)=(F.dersig,false,false,false), so under sigFlagsOf(F)\mathrm{sigFlagsOf}(F)sigFlagsOf(F) the public-key-encoding check always passes and the signature-encoding check only rejects non-empty, non-strict-DER signatures when F.dersigF.\mathrm{dersig}F.dersig is set.

Script verification verifyScript(tap,c,ss,spk,w)\mathrm{verifyScript}(\mathit{tap}, c, \mathit{ss}, \mathit{spk}, w)verifyScript(tap,c,ss,spk,w). A verification context ccc consists of a consensus flag set c.flagsc.\mathrm{flags}c.flags (Booleans p2sh,witness,taproot,dersig,cltv,csv,nulldummy\mathrm{p2sh}, \mathrm{witness}, \mathrm{taproot}, \mathrm{dersig}, \mathrm{cltv}, \mathrm{csv}, \mathrm{nulldummy}p2sh,witness,taproot,dersig,cltv,csv,nulldummy), a transaction c.txc.\mathit{tx}c.tx, an input index c.nInc.\mathit{nIn}c.nIn and an amount c.amount∈Zc.\mathit{amount} \in \mathbb{Z}c.amount∈Z; tap\mathit{tap}tap is an arbitrary function (a "Taproot handler") from a context, a witness stack and a program to a Boolean. evalBytes(c,v,st,s)\mathrm{evalBytes}(c, v, \mathit{st}, s)evalBytes(c,v,st,s) for a byte-level script sss is none\mathrm{none}none if ∣s∣>10 000|s| > 10\,000∣s∣>10000 or sss does not parse, and otherwise evalf,o(st,parse(s))\mathrm{eval}_{f,o}(\mathit{st}, \mathrm{parse}(s))evalf,o​(st,parse(s)) with f=scriptFlagsOf(c.flags)f = \mathrm{scriptFlagsOf}(c.\mathrm{flags})f=scriptFlagsOf(c.flags) and o=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s)o = \mathcal{O}(\mathrm{sigFlagsOf}(c.\mathrm{flags}), c.\mathit{tx}, c.\mathit{nIn}, c.\mathit{amount}, v, s)o=O(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s). verifyScript\mathrm{verifyScript}verifyScript with scriptSig ss\mathit{ss}ss, scriptPubKey spk\mathit{spk}spk and witness list www (in transaction order, last element on top) is the Boolean computed as: run evalBytes(c,base,[],ss)\mathrm{evalBytes}(c, \mathrm{base}, [], \mathit{ss})evalBytes(c,base,[],ss), false on failure; run evalBytes(c,base,⋅,spk)\mathrm{evalBytes}(c, \mathrm{base}, \cdot, \mathit{spk})evalBytes(c,base,⋅,spk) on the resulting stack, false on failure; false if the resulting stack is empty or its top is not castToBool\mathrm{castToBool}castToBool-true; then, if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is set and spk\mathit{spk}spk is a witness program (length between 4 and 42, first byte 000 or in 0x51..0x600\mathrm{x}51..0\mathrm{x}600x51..0x60, second byte plus 2 equal to the length; version 000 for first byte 000, else first byte minus 0x500\mathrm{x}500x50; program the bytes after the second), the verdict is false if ss≠[]\mathit{ss} \ne []ss=[] and otherwise verifyWitnessProgram(tap,c,w,version,program,false)\mathrm{verifyWitnessProgram}(\mathit{tap}, c, w, \mathit{version}, \mathit{program}, \mathrm{false})verifyWitnessProgram(tap,c,w,version,program,false); if spk\mathit{spk}spk is not a witness program the P2SH and bare-script branches follow (not reached by the statements here). verifyWitnessProgram\mathrm{verifyWitnessProgram}verifyWitnessProgram at version 000 with a 32-byte program is: false if www is empty; otherwise, with script\mathit{script}script the last element of www, false if SHA256(script)≠program\mathrm{SHA256}(\mathit{script}) \ne \mathit{program}SHA256(script)=program, and otherwise execV0(c,reverse(w without its last element),script)\mathrm{execV0}(c, \mathrm{reverse}(w \text{ without its last element}), \mathit{script})execV0(c,reverse(w without its last element),script); at version 000 with a 20-byte program it is the P2WPKH case, at version 1 with a 32-byte non-P2SH program it is true if c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot is off and tap(c,w,program)\mathit{tap}(c, w, \mathit{program})tap(c,w,program) otherwise, and every other version is true. execV0(c,st,s)\mathrm{execV0}(c, \mathit{st}, s)execV0(c,st,s) is false if some element of st\mathit{st}st is longer than 520520520 bytes, false if evalBytes(c,witnessV0,st,s)\mathrm{evalBytes}(c, \mathrm{witnessV0}, \mathit{st}, s)evalBytes(c,witnessV0,st,s) fails, and otherwise true iff the final stack has exactly one element and topTrue\mathrm{topTrue}topTrue of it, where topTrue(st)\mathrm{topTrue}(\mathit{st})topTrue(st) is false for an empty stack and castToBool\mathrm{castToBool}castToBool of the top element otherwise. The output script witnessBytes(0,p)\mathrm{witnessBytes}(0, p)witnessBytes(0,p) is the byte string [0x00]+ ⁣ ⁣+pushBytes(p)[0\mathrm{x}00] \mathbin{+\!\!+} \mathrm{pushBytes}(p)[0x00]++pushBytes(p) (for a 32-byte ppp: [0x00,0x20]+ ⁣ ⁣+p[0\mathrm{x}00, 0\mathrm{x}20] \mathbin{+\!\!+} p[0x00,0x20]++p).

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