Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Anyone can spend the anchor after the delay: the empty-signature witness under the concrete checker

Proved
BitcoinAnchors.anchor_anyone_concrete

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

anchorsbip112bitcoinbitcoin-mainnetbolt3csvformal-verificationhtlclightningp2wshscript

With the WITNESS and CHECKSEQUENCEVERIFY flags and a funding key of at most 520 bytes: verifyScript tap c [] (witnessBytes 0 (sha256 (anchorBytes k))) [[], anchorBytes k] = true ↔ castToBool (sha256 (anchorBytes k)) = true ∧ checkSequence c.tx c.nIn 16 = true. The empty signature is a clean false under consensus flags (the signature mission's checkSig_empty; no pubkey-encoding hypothesis is needed since WITNESS_PUBKEYTYPE is policy), so the spend reduces to Core's CheckSequence with operand 16.

Preamble
import Definitions.Def_BitcoinAnchors
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 BitcoinAnchors.anchor_anyone_concrete (tap : BitcoinVerify.TaprootHandler) (c : BitcoinVerify.Ctx)
    (hf : c.flags.witness = true) (hcsv : c.flags.csv = true) (fundingKey : Bytes)
    (hfk : fundingKey.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) :
    BitcoinVerify.verifyScript tap c []
        (BitcoinVerify.witnessBytes 0 (BitcoinSer.sha256 (BitcoinAnchors.anchorBytes fundingKey)))
        [[], BitcoinAnchors.anchorBytes fundingKey] = true ↔
      BitcoinScript.castToBool (BitcoinSer.sha256 (BitcoinAnchors.anchorBytes fundingKey)) = true ∧
      BitcoinSig.checkSequence c.tx c.nIn 16 = true := by sorry
Source
BOLT #3 with option_anchors: to_remote Output, Anchor Outputs, Offered/Received HTLC Outputs: https://github.com/lightning/bolts/blob/master/03-transactions.md#to_remote-output; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_CHECKSIGVERIFY, OP_IFDUP, OP_NOTIF, OP_CHECKSEQUENCEVERIFY, OP_CHECKMULTISIG), GenericTransactionSignatureChecker::CheckSequence (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); 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: BitcoinAnchors.anchor_anyone_concrete

Declaration. For every Taproot handler taptaptap (an arbitrary function, unconstrained), every verification context ccc (consisting of a seven-Boolean flag record c.flagsc.\mathrm{flags}c.flags, a transaction c.txc.\mathrm{tx}c.tx, an input index c.nIn∈Nc.\mathrm{nIn}\in\mathbb Nc.nIn∈N and an amount c.amount∈Zc.\mathrm{amount}\in\mathbb Zc.amount∈Z), and every byte string KKK (fundingKey), under the hypotheses

  • c.flags.witness=truec.\mathrm{flags}.\mathrm{witness}=\mathrm{true}c.flags.witness=true (hf),
  • c.flags.csv=truec.\mathrm{flags}.\mathrm{csv}=\mathrm{true}c.flags.csv=true (hcsv),
  • ∣K∣≤520|K|\le 520∣K∣≤520 (hfk),

the following biconditional holds. Let X=anchorBytes(K)=pushBytes(K) ++ [0xac,0x73,0x64,0x60,0xb2,0x68]X=\mathrm{anchorBytes}(K)=\mathrm{pushBytes}(K)\,++\,[0xac,0x73,0x64,0x60,0xb2,0x68]X=anchorBytes(K)=pushBytes(K)++[0xac,0x73,0x64,0x60,0xb2,0x68].

Left. verifyScript(tap, c, [ ], witnessBytes(0,SHA256(X)), [[ ],X])=true\mathrm{verifyScript}\bigl(tap,\,c,\,[\,],\,\mathrm{witnessBytes}(0,\mathrm{SHA256}(X)),\,[[\,],X]\bigr)=\mathrm{true}verifyScript(tap,c,[],witnessBytes(0,SHA256(X)),[[],X])=true: the full script-verification procedure of part B, with an empty scriptSig, the 34-byte scriptPubKey [0x00,0x20] ++ SHA256(X)[0x00,0x20]\,++\,\mathrm{SHA256}(X)[0x00,0x20]++SHA256(X), and a witness list of exactly two elements — the empty byte string followed by XXX — returns true. By the unfolding in part B (with ws=[[ ]]ws=[[\,]]ws=[[]]), this is the same as: castToBool(SHA256(X))=true\mathrm{castToBool}(\mathrm{SHA256}(X))=\mathrm{true}castToBool(SHA256(X))=true, XXX is at most 100001000010000 bytes and parses, and evalScript(scriptFlagsOf(c.flags),oX,[[ ]],parseScript(X))\mathrm{evalScript}(\mathrm{scriptFlagsOf}(c.\mathrm{flags}),o_X,[[\,]],\mathrm{parseScript}(X))evalScript(scriptFlagsOf(c.flags),oX​,[[]],parseScript(X)) is some\mathrm{some}some of a one-element stack whose element is castToBool\mathrm{castToBool}castToBool-true. The stack passed to the script is [[ ]][[\,]][[]]: exactly one element, the empty byte string.

Right. castToBool(SHA256(X))=true\mathrm{castToBool}(\mathrm{SHA256}(X))=\mathrm{true}castToBool(SHA256(X))=true (the 32-byte SHA-256 digest of XXX is not all zero bytes and is not 31 zero bytes followed by 0x800x800x80) and checkSequence(c.tx,c.nIn,16)=true\mathrm{checkSequence}(c.\mathrm{tx},c.\mathrm{nIn},16)=\mathrm{true}checkSequence(c.tx,c.nIn,16)=true, which by part B unfolds to: 2≤c.tx.version2\le c.\mathrm{tx}.\mathrm{version}2≤c.tx.version, bit 31 of τ\tauτ is clear, bit 22 of τ\tauτ is clear, and 16≤τ & 0xffff16\le\tau\,\&\,0xffff16≤τ&0xffff, where τ=inputSequence(c.tx,c.nIn)\tau=\mathrm{inputSequence}(c.\mathrm{tx},c.\mathrm{nIn})τ=inputSequence(c.tx,c.nIn) is the nSequence of input c.nInc.\mathrm{nIn}c.nIn (or 000 if c.nInc.\mathrm{nIn}c.nIn is out of range, in which case the condition is false).

Here SHA256\mathrm{SHA256}SHA256 is the concrete SHA-256 function. The flags c.flags.p2sh,taproot,dersig,cltv,nulldummyc.\mathrm{flags}.\mathrm{p2sh},\mathrm{taproot},\mathrm{dersig},\mathrm{cltv},\mathrm{nulldummy}c.flags.p2sh,taproot,dersig,cltv,nulldummy are unconstrained, as are c.txc.\mathrm{tx}c.tx (its version and nSequence values are unbounded naturals), c.nInc.\mathrm{nIn}c.nIn and c.amountc.\mathrm{amount}c.amount (which may be negative). The signature check on the empty witness element inside the left side is the concrete checkSigPreTapscript\mathrm{checkSigPreTapscript}checkSigPreTapscript of part B, which on [ ][\,][] returns some false\mathrm{some\ false}some false for every key.


Common unfolded definitions, part A: the script interpreter

Everything below is a literal unfolding of the definitions the statement depends on. Nothing here is a claim about the theorem; it only says what the symbols mean.

Bytes and stacks. A byte is an 8-bit word, i.e. a value in {0,…,255}\{0,\dots,255\}{0,…,255}. A byte string is a finite list of bytes; ∣v∣|v|∣v∣ is its length and [ ][\,][] is the empty byte string. A stack is a finite list of byte strings written top first: in [a,b,c][a,b,c][a,b,c] the element aaa is on top. The constants are MAX_SCRIPT_ELEMENT_SIZE=520\mathrm{MAX\_SCRIPT\_ELEMENT\_SIZE}=520MAX_SCRIPT_ELEMENT_SIZE=520, MAX_STACK_SIZE=1000\mathrm{MAX\_STACK\_SIZE}=1000MAX_STACK_SIZE=1000, MAX_OPS_PER_SCRIPT=201\mathrm{MAX\_OPS\_PER\_SCRIPT}=201MAX_OPS_PER_SCRIPT=201, MAX_PUBKEYS_PER_MULTISIG=20\mathrm{MAX\_PUBKEYS\_PER\_MULTISIG}=20MAX_PUBKEYS_PER_MULTISIG=20.

Truth value of a byte string, castToBool(v)\mathrm{castToBool}(v)castToBool(v): [ ][\,][] is false; a one-byte string [b][b][b] is true iff b≠0b\neq 0b=0 and b≠0x80b\neq 0x80b=0x80; a string b::rb::rb::r of length at least two is true iff b≠0b\neq 0b=0 or castToBool(r)\mathrm{castToBool}(r)castToBool(r). Equivalently, vvv is true iff some byte of vvv is nonzero, except that a string consisting of zero bytes followed by a final byte 0x800x800x80 is false.

boolBytes\mathrm{boolBytes}boolBytes: boolBytes(true)=[0x01]\mathrm{boolBytes}(\mathrm{true})=[0x01]boolBytes(true)=[0x01] (the single byte 111) and boolBytes(false)=[ ]\mathrm{boolBytes}(\mathrm{false})=[\,]boolBytes(false)=[] (the empty byte string).

Stack literals used in the statements. [[1]][[1]][[1]] is the stack with exactly one element, the one-byte string 0x010x010x01; [[16]][[16]][[16]] is the stack with exactly one element, the one-byte string 0x100x100x10 (decimal 161616); [[ ]][[\,]][[]] is the stack with exactly one element, the empty byte string; [ ][\,][] is the empty stack. A stack written [σ][\sigma][σ] has exactly one element σ\sigmaσ; [x,σ][x,\sigma][x,σ] has exactly two, xxx on top.

Flags fff: a record of three Booleans f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy. No other verification flag exists in this model. Where fff is a parameter of a theorem, all three values are unconstrained.

Oracle ooo: a record of arbitrary functions with no axioms relating them to each other or to anything else: five byte-string-to-byte-string functions o.ripemd160o.\mathrm{ripemd160}o.ripemd160, o.sha1o.\mathrm{sha1}o.sha1, o.sha256o.\mathrm{sha256}o.sha256, o.hash160o.\mathrm{hash160}o.hash160, o.hash256o.\mathrm{hash256}o.hash256; a function o.checkSig(σ,k)o.\mathrm{checkSig}(\sigma,k)o.checkSig(σ,k) from pairs of byte strings (first the signature, second the key) to the three values none\mathrm{none}none, some true\mathrm{some\ true}some true, some false\mathrm{some\ false}some false; and two functions o.checkLockTime, o.checkSequence:Z→{true,false}o.\mathrm{checkLockTime},\,o.\mathrm{checkSequence}:\mathbb Z\to\{\mathrm{true},\mathrm{false}\}o.checkLockTime,o.checkSequence:Z→{true,false}. In particular, in a theorem that takes ooo as a parameter, o.hash160o.\mathrm{hash160}o.hash160 is an arbitrary function (its outputs need not be 20 bytes long, it need not be injective, and it has no relation to o.sha256o.\mathrm{sha256}o.sha256), and o.checkSigo.\mathrm{checkSig}o.checkSig is an arbitrary three-valued function.

Script numbers. serialize(v)\mathrm{serialize}(v)serialize(v) for v∈Zv\in\mathbb Zv∈Z: [ ][\,][] if v=0v=0v=0; otherwise the little-endian bytes of ∣v∣|v|∣v∣ with no trailing zero byte, after which: if the last byte has its top bit (0x800x800x80) set, one extra byte is appended (0x800x800x80 if v<0v<0v<0, 0x000x000x00 if v>0v>0v>0); otherwise, if v<0v<0v<0, the top bit of the last byte is set. Thus serialize(1)=[0x01]\mathrm{serialize}(1)=[0x01]serialize(1)=[0x01], serialize(2)=[0x02]\mathrm{serialize}(2)=[0x02]serialize(2)=[0x02], serialize(16)=[0x10]\mathrm{serialize}(16)=[0x10]serialize(16)=[0x10], serialize(32)=[0x20]\mathrm{serialize}(32)=[0x20]serialize(32)=[0x20]. The decoding setVch(v)\mathrm{setVch}(v)setVch(v) is 000 for [ ][\,][], and otherwise the little-endian value of vvv with the top bit of the last byte removed and read as a minus sign. toNum(false,m,v)\mathrm{toNum}(\mathrm{false},m,v)toNum(false,m,v) is none\mathrm{none}none if m<∣v∣m<|v|m<∣v∣ and some setVch(v)\mathrm{some}\,\mathrm{setVch}(v)somesetVch(v) otherwise (no minimal-encoding check is made).

Instructions and scripts. An instruction is either a push push(d)\mathrm{push}(d)push(d) of a byte string ddd, or an opcode op(c)\mathrm{op}(c)op(c) for a byte ccc. A script is a finite list of instructions. Opcode bytes that occur: OP_1NEGATE =0x4f=0x4f=0x4f, OP_1 =0x51=0x51=0x51, OP_2 =0x52=0x52=0x52, OP_16 =0x60=0x60=0x60, OP_IF =0x63=0x63=0x63, OP_NOTIF =0x64=0x64=0x64, OP_ELSE =0x67=0x67=0x67, OP_ENDIF =0x68=0x68=0x68, OP_IFDUP =0x73=0x73=0x73, OP_DROP =0x75=0x75=0x75, OP_DUP =0x76=0x76=0x76, OP_SWAP =0x7c=0x7c=0x7c, OP_SIZE =0x82=0x82=0x82, OP_EQUAL =0x87=0x87=0x87, OP_EQUALVERIFY =0x88=0x88=0x88, OP_HASH160 =0xa9=0xa9=0xa9, OP_CHECKSIG =0xac=0xac=0xac, OP_CHECKSIGVERIFY =0xad=0xad=0xad, OP_CHECKMULTISIG =0xae=0xae=0xae, OP_CHECKLOCKTIMEVERIFY =0xb1=0xb1=0xb1, OP_CHECKSEQUENCEVERIFY =0xb2=0xb2=0xb2.

numInstr(n)\mathrm{numInstr}(n)numInstr(n) for n∈Zn\in\mathbb Zn∈Z: if n=−1n=-1n=−1 or 1≤n≤161\le n\le 161≤n≤16, the opcode op(n+0x50)\mathrm{op}(n+0x50)op(n+0x50) (so numInstr(1)=op(OP_1)\mathrm{numInstr}(1)=\mathrm{op}(\mathrm{OP\_1})numInstr(1)=op(OP_1), numInstr(2)=op(OP_2)\mathrm{numInstr}(2)=\mathrm{op}(\mathrm{OP\_2})numInstr(2)=op(OP_2), numInstr(16)=op(OP_16)\mathrm{numInstr}(16)=\mathrm{op}(\mathrm{OP\_16})numInstr(16)=op(OP_16), numInstr(−1)=op(0x4f)\mathrm{numInstr}(-1)=\mathrm{op}(0x4f)numInstr(−1)=op(0x4f)); otherwise the push push(serialize(n))\mathrm{push}(\mathrm{serialize}(n))push(serialize(n)) (so numInstr(32)=push([0x20])\mathrm{numInstr}(32)=\mathrm{push}([0x20])numInstr(32)=push([0x20]) and numInstr(0)=push([ ])\mathrm{numInstr}(0)=\mathrm{push}([\,])numInstr(0)=push([])).

The parsed scripts of the anchors file, for arbitrary byte strings KKK (funding key), RRR (remote key), LLL (local key), HHH (revocation hash), PPP (payment hash) and an integer eee (expiry):

toRemoteScript(R)=[push(R), op(OP_CHECKSIGVERIFY), op(OP_1), op(OP_CHECKSEQUENCEVERIFY)].\mathrm{toRemoteScript}(R)=[\mathrm{push}(R),\ \mathrm{op}(\mathrm{OP\_CHECKSIGVERIFY}),\ \mathrm{op}(\mathrm{OP\_1}),\ \mathrm{op}(\mathrm{OP\_CHECKSEQUENCEVERIFY})].toRemoteScript(R)=[push(R), op(OP_CHECKSIGVERIFY), op(OP_1), op(OP_CHECKSEQUENCEVERIFY)]. anchorScript(K)=[push(K), op(OP_CHECKSIG), op(OP_IFDUP), op(OP_NOTIF), op(OP_16), op(OP_CHECKSEQUENCEVERIFY), op(OP_ENDIF)].\mathrm{anchorScript}(K)=[\mathrm{push}(K),\ \mathrm{op}(\mathrm{OP\_CHECKSIG}),\ \mathrm{op}(\mathrm{OP\_IFDUP}),\ \mathrm{op}(\mathrm{OP\_NOTIF}),\ \mathrm{op}(\mathrm{OP\_16}),\ \mathrm{op}(\mathrm{OP\_CHECKSEQUENCEVERIFY}),\ \mathrm{op}(\mathrm{OP\_ENDIF})].anchorScript(K)=[push(K), op(OP_CHECKSIG), op(OP_IFDUP), op(OP_NOTIF), op(OP_16), op(OP_CHECKSEQUENCEVERIFY), op(OP_ENDIF)].

offeredScript(H,R,L,P)\mathrm{offeredScript}(H,R,L,P)offeredScript(H,R,L,P) is the 30-instruction list: OP_DUP, OP_HASH160, push(H)\mathrm{push}(H)push(H), OP_EQUAL, OP_IF, OP_CHECKSIG, OP_ELSE, push(R)\mathrm{push}(R)push(R), OP_SWAP, OP_SIZE, push([0x20])\mathrm{push}([0x20])push([0x20]), OP_EQUAL, OP_NOTIF, OP_DROP, OP_2, OP_SWAP, push(L)\mathrm{push}(L)push(L), OP_2, OP_CHECKMULTISIG, OP_ELSE, OP_HASH160, push(P)\mathrm{push}(P)push(P), OP_EQUALVERIFY, OP_CHECKSIG, OP_ENDIF, OP_1, OP_CHECKSEQUENCEVERIFY, OP_DROP, OP_ENDIF.

receivedScript(H,R,L,P,e)\mathrm{receivedScript}(H,R,L,P,e)receivedScript(H,R,L,P,e) is the 32-instruction list: OP_DUP, OP_HASH160, push(H)\mathrm{push}(H)push(H), OP_EQUAL, OP_IF, OP_CHECKSIG, OP_ELSE, push(R)\mathrm{push}(R)push(R), OP_SWAP, OP_SIZE, push([0x20])\mathrm{push}([0x20])push([0x20]), OP_EQUAL, OP_IF, OP_HASH160, push(P)\mathrm{push}(P)push(P), OP_EQUALVERIFY, OP_2, OP_SWAP, push(L)\mathrm{push}(L)push(L), OP_2, OP_CHECKMULTISIG, OP_ELSE, OP_DROP, numInstr(e)\mathrm{numInstr}(e)numInstr(e), OP_CHECKLOCKTIMEVERIFY, OP_DROP, OP_CHECKSIG, OP_ENDIF, OP_1, OP_CHECKSEQUENCEVERIFY, OP_DROP, OP_ENDIF.

Execution state: a main stack, an alt stack, a condition stack vfExec\mathrm{vfExec}vfExec (a list of Booleans) and an op counter. The initial state for a stack ststst has main stack ststst, empty alt stack, empty vfExec\mathrm{vfExec}vfExec, counter 000. The machine is executing when every entry of vfExec\mathrm{vfExec}vfExec is true (vacuously, when vfExec\mathrm{vfExec}vfExec is empty).

evalScript(f,o,st,S)\mathrm{evalScript}(f,o,st,S)evalScript(f,o,st,S): starting from the initial state of ststst, apply step\mathrm{step}step to the instructions of SSS in order; if any step returns none\mathrm{none}none the result is none\mathrm{none}none; after the last instruction the result is none\mathrm{none}none if vfExec\mathrm{vfExec}vfExec is non-empty and otherwise some\mathrm{some}some of the final main stack. So the value is either none\mathrm{none}none (script failure) or some st′\mathrm{some}\,st'somest′ for a stack st′st'st′ (the alt stack and the counter are discarded).

step\mathrm{step}step on push(d)\mathrm{push}(d)push(d): none\mathrm{none}none if 520<∣d∣520<|d|520<∣d∣; otherwise, if executing, ddd is placed on top of the main stack (if not executing, nothing changes); then none\mathrm{none}none if the main-stack size plus the alt-stack size exceeds 100010001000, else the new state.

step\mathrm{step}step on op(c)\mathrm{op}(c)op(c): ccc is counted when 0x60<c0x60<c0x60<c; if counted and the counter plus one exceeds 201201201, none\mathrm{none}none; otherwise the counter is incremented when counted; none\mathrm{none}none if ccc is one of the fifteen disabled opcodes (none of the opcodes listed above is disabled); otherwise, if executing or 0x63≤c≤0x680x63\le c\le 0x680x63≤c≤0x68 (the conditionals), execOp\mathrm{execOp}execOp is applied and the result is none\mathrm{none}none if it is none\mathrm{none}none or if the stack-size sum then exceeds 100010001000; otherwise (not executing, not a conditional) the state is unchanged, again subject to the size check.

execOp(f,o,fExec,c,s)\mathrm{execOp}(f,o,\mathrm{fExec},c,s)execOp(f,o,fExec,c,s) for the opcodes that occur ("none\mathrm{none}none" means script failure; "no change" means the state is returned unchanged):

  • OP_1NEGATE, OP_1, …, OP_16: push serialize(c−0x50)\mathrm{serialize}(c-0x50)serialize(c−0x50); so OP_1 pushes [0x01][0x01][0x01], OP_2 pushes [0x02][0x02][0x02], OP_16 pushes [0x10][0x10][0x10]. These bytes are ≤0x60\le 0x60≤0x60, so they are not counted.
  • OP_CHECKLOCKTIMEVERIFY: if f.cltv=falsef.\mathrm{cltv}=\mathrm{false}f.cltv=false, no change. Otherwise none\mathrm{none}none on an empty stack; else with top ttt (not popped): none\mathrm{none}none if ∣t∣>5|t|>5∣t∣>5; with n=setVch(t)n=\mathrm{setVch}(t)n=setVch(t), none\mathrm{none}none if n<0n<0n<0, none\mathrm{none}none if o.checkLockTime(n)=falseo.\mathrm{checkLockTime}(n)=\mathrm{false}o.checkLockTime(n)=false, else no change.
  • OP_CHECKSEQUENCEVERIFY: if f.csv=falsef.\mathrm{csv}=\mathrm{false}f.csv=false, no change. Otherwise none\mathrm{none}none on an empty stack; else with top ttt (not popped): none\mathrm{none}none if ∣t∣>5|t|>5∣t∣>5; with n=setVch(t)n=\mathrm{setVch}(t)n=setVch(t), none\mathrm{none}none if n<0n<0n<0; no change if bit 313131 of nnn is set (precisely: max⁡(n,0) & 231≠0\max(n,0)\,\&\,2^{31}\neq 0max(n,0)&231=0); else none\mathrm{none}none if o.checkSequence(n)=falseo.\mathrm{checkSequence}(n)=\mathrm{false}o.checkSequence(n)=false, else no change.
  • OP_IF / OP_NOTIF: if executing, none\mathrm{none}none on an empty stack; else the top ttt is popped, v=castToBool(t)v=\mathrm{castToBool}(t)v=castToBool(t) (negated for OP_NOTIF) and vvv is pushed onto vfExec\mathrm{vfExec}vfExec. If not executing, false\mathrm{false}false is pushed onto vfExec\mathrm{vfExec}vfExec and the stack is untouched.
  • OP_ELSE: none\mathrm{none}none if vfExec\mathrm{vfExec}vfExec is empty; else its top entry is negated.
  • OP_ENDIF: none\mathrm{none}none if vfExec\mathrm{vfExec}vfExec is empty; else its top entry is removed.
  • OP_IFDUP: none\mathrm{none}none on an empty stack; else if castToBool\mathrm{castToBool}castToBool of the top is true the top is duplicated, otherwise no change.
  • OP_DROP: none\mathrm{none}none on an empty stack; else the top is removed. OP_DUP: none\mathrm{none}none on an empty stack; else the top is duplicated. OP_SWAP: none\mathrm{none}none with fewer than two elements; else the top two are exchanged. OP_SIZE: none\mathrm{none}none on an empty stack; else serialize(∣t∣)\mathrm{serialize}(|t|)serialize(∣t∣) is pushed above the top ttt, which stays.
  • OP_EQUAL / OP_EQUALVERIFY: none\mathrm{none}none with fewer than two elements; else the top aaa and the next bbb are popped and eqeqeq is the proposition "aaa and bbb are the same byte string"; OP_EQUAL pushes boolBytes(eq)\mathrm{boolBytes}(eq)boolBytes(eq); OP_EQUALVERIFY pushes nothing and is none\mathrm{none}none when eqeqeq is false.
  • OP_HASH160: none\mathrm{none}none on an empty stack; else the top ttt is replaced by o.hash160(t)o.\mathrm{hash160}(t)o.hash160(t).
  • OP_CHECKSIG / OP_CHECKSIGVERIFY: none\mathrm{none}none with fewer than two elements; else the top kkk (the key) and the next σ\sigmaσ (the signature) are popped and o.checkSig(σ,k)o.\mathrm{checkSig}(\sigma,k)o.checkSig(σ,k) is consulted: none\mathrm{none}none gives none\mathrm{none}none; some ok\mathrm{some}\,oksomeok: OP_CHECKSIG pushes boolBytes(ok)\mathrm{boolBytes}(ok)boolBytes(ok), while OP_CHECKSIGVERIFY pushes nothing and is none\mathrm{none}none when ok=falseok=\mathrm{false}ok=false.
  • OP_CHECKMULTISIG: none\mathrm{none}none on an empty stack; the top nkn_knk​ is popped and decoded by toNum(false,4,⋅)\mathrm{toNum}(\mathrm{false},4,\cdot)toNum(false,4,⋅) (none\mathrm{none}none if longer than 4 bytes); none\mathrm{none}none if nk<0n_k<0nk​<0 or 20<nk20<n_k20<nk​; the counter becomes counter + nk+\,n_k+nk​, none\mathrm{none}none if that exceeds 201201201; the next nkn_knk​ elements are the keys (none\mathrm{none}none if fewer remain); the next element nsn_sns​ is popped (none\mathrm{none}none if none remains) and decoded likewise, none\mathrm{none}none if ns<0n_s<0ns​<0 or nk<nsn_k<n_snk​<ns​; the next nsn_sns​ elements are the signatures (none\mathrm{none}none if fewer remain); multisigLoop(o,sigs,keys)\mathrm{multisigLoop}(o,\text{sigs},\text{keys})multisigLoop(o,sigs,keys) is computed: none\mathrm{none}none gives none\mathrm{none}none; some ok\mathrm{some}\,oksomeok: none\mathrm{none}none if no element remains, else one more element dummydummydummy is popped, none\mathrm{none}none if f.nulldummy=truef.\mathrm{nulldummy}=\mathrm{true}f.nulldummy=true and dummy≠[ ]dummy\neq[\,]dummy=[], else boolBytes(ok)\mathrm{boolBytes}(ok)boolBytes(ok) is pushed.

multisigLoop(o,sigs,keys)\mathrm{multisigLoop}(o,\text{sigs},\text{keys})multisigLoop(o,sigs,keys) (both lists top first): some true\mathrm{some\ true}some true if sigs is empty; some false\mathrm{some\ false}some false if sigs is non-empty and keys is empty; otherwise, with σ\sigmaσ the first signature and kkk the first key, o.checkSig(σ,k)o.\mathrm{checkSig}(\sigma,k)o.checkSig(σ,k): none\mathrm{none}none gives none\mathrm{none}none; some true\mathrm{some\ true}some true gives some false\mathrm{some\ false}some false if fewer keys than signatures remain after removing both, else the loop on the remaining signatures and remaining keys; some false\mathrm{some\ false}some false gives some false\mathrm{some\ false}some false if the remaining keys are fewer than all the current signatures, else the loop on the same signatures and the remaining keys. For the only instance that occurs, multisigLoop(o,[σL,σR],[L,R])\mathrm{multisigLoop}(o,[\sigma_L,\sigma_R],[L,R])multisigLoop(o,[σL​,σR​],[L,R]) unfolds to: none\mathrm{none}none if o.checkSig(σL,L)=noneo.\mathrm{checkSig}(\sigma_L,L)=\mathrm{none}o.checkSig(σL​,L)=none; some false\mathrm{some\ false}some false if o.checkSig(σL,L)=some falseo.\mathrm{checkSig}(\sigma_L,L)=\mathrm{some\ false}o.checkSig(σL​,L)=some false; and, if o.checkSig(σL,L)=some trueo.\mathrm{checkSig}(\sigma_L,L)=\mathrm{some\ true}o.checkSig(σL​,L)=some true, the value o.checkSig(σR,R)o.\mathrm{checkSig}(\sigma_R,R)o.checkSig(σR​,R) itself. Hence it equals some true\mathrm{some\ true}some true iff o.checkSig(σL,L)=some trueo.\mathrm{checkSig}(\sigma_L,L)=\mathrm{some\ true}o.checkSig(σL​,L)=some true and o.checkSig(σR,R)=some trueo.\mathrm{checkSig}(\sigma_R,R)=\mathrm{some\ true}o.checkSig(σR​,R)=some true; the signature σR\sigma_RσR​ is never checked against LLL, nor σL\sigma_LσL​ against RRR.

CsvPasses(f,o,d)\mathrm{CsvPasses}(f,o,d)CsvPasses(f,o,d) for d∈Zd\in\mathbb Zd∈Z:

f.csv=false  ∨  (0≤d ∧ (max⁡(d,0) & 231≠0 ∨ o.checkSequence(d)=true)).f.\mathrm{csv}=\mathrm{false}\ \ \lor\ \ \bigl(0\le d\ \land\ (\max(d,0)\,\&\,2^{31}\neq 0\ \lor\ o.\mathrm{checkSequence}(d)=\mathrm{true})\bigr).f.csv=false  ∨  (0≤d ∧ (max(d,0)&231=0 ∨ o.checkSequence(d)=true)).

For d=1d=1d=1 and d=16d=16d=16 the bit-31 disjunct is false (1 & 231=01\,\&\,2^{31}=01&231=0 and 16 & 231=016\,\&\,2^{31}=016&231=0), so CsvPasses(f,o,1)  ⟺  f.csv=false∨o.checkSequence(1)=true\mathrm{CsvPasses}(f,o,1)\iff f.\mathrm{csv}=\mathrm{false}\lor o.\mathrm{checkSequence}(1)=\mathrm{true}CsvPasses(f,o,1)⟺f.csv=false∨o.checkSequence(1)=true and CsvPasses(f,o,16)  ⟺  f.csv=false∨o.checkSequence(16)=true\mathrm{CsvPasses}(f,o,16)\iff f.\mathrm{csv}=\mathrm{false}\lor o.\mathrm{checkSequence}(16)=\mathrm{true}CsvPasses(f,o,16)⟺f.csv=false∨o.checkSequence(16)=true. When fff and ooo are arbitrary parameters, o.checkSequenceo.\mathrm{checkSequence}o.checkSequence is an arbitrary function of an integer.

CltvPasses(f,o,e)\mathrm{CltvPasses}(f,o,e)CltvPasses(f,o,e) for e∈Ze\in\mathbb Ze∈Z: f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true)f.\mathrm{cltv}=\mathrm{false}\ \lor\ (0\le e\ \land\ o.\mathrm{checkLockTime}(e)=\mathrm{true})f.cltv=false ∨ (0≤e ∧ o.checkLockTime(e)=true).

topTrue(st)\mathrm{topTrue}(st)topTrue(st): false\mathrm{false}false for the empty stack; castToBool\mathrm{castToBool}castToBool of the top element otherwise.

The spend predicates of the anchors file (all stacks top first; σ,σL,σR,pk,x,d\sigma,\sigma_L,\sigma_R,pk,x,dσ,σL​,σR​,pk,x,d range over byte strings):

ToRemoteSpend(f,o,R,st)\mathrm{ToRemoteSpend}(f,o,R,st)ToRemoteSpend(f,o,R,st): there is σ\sigmaσ with st=[σ]st=[\sigma]st=[σ], o.checkSig(σ,R)=some trueo.\mathrm{checkSig}(\sigma,R)=\mathrm{some\ true}o.checkSig(σ,R)=some true and CsvPasses(f,o,1)\mathrm{CsvPasses}(f,o,1)CsvPasses(f,o,1).

AnchorSpend(f,o,K,st)\mathrm{AnchorSpend}(f,o,K,st)AnchorSpend(f,o,K,st): there is σ\sigmaσ with st=[σ]st=[\sigma]st=[σ] and either o.checkSig(σ,K)=some trueo.\mathrm{checkSig}(\sigma,K)=\mathrm{some\ true}o.checkSig(σ,K)=some true, or both o.checkSig(σ,K)=some falseo.\mathrm{checkSig}(\sigma,K)=\mathrm{some\ false}o.checkSig(σ,K)=some false and CsvPasses(f,o,16)\mathrm{CsvPasses}(f,o,16)CsvPasses(f,o,16).

OfferedSpend(f,o,H,R,L,P,st)\mathrm{OfferedSpend}(f,o,H,R,L,P,st)OfferedSpend(f,o,H,R,L,P,st) is the disjunction of

  1. there are pk,σpk,\sigmapk,σ with st=[pk,σ]st=[pk,\sigma]st=[pk,σ], o.hash160(pk)=Ho.\mathrm{hash160}(pk)=Ho.hash160(pk)=H and o.checkSig(σ,pk)=some trueo.\mathrm{checkSig}(\sigma,pk)=\mathrm{some\ true}o.checkSig(σ,pk)=some true;
  2. there are x,σx,\sigmax,σ with st=[x,σ]st=[x,\sigma]st=[x,σ], o.hash160(x)≠Ho.\mathrm{hash160}(x)\neq Ho.hash160(x)=H, ∣x∣=32|x|=32∣x∣=32, o.hash160(x)=Po.\mathrm{hash160}(x)=Po.hash160(x)=P, o.checkSig(σ,R)=some trueo.\mathrm{checkSig}(\sigma,R)=\mathrm{some\ true}o.checkSig(σ,R)=some true and CsvPasses(f,o,1)\mathrm{CsvPasses}(f,o,1)CsvPasses(f,o,1);
  3. there are x,σL,σR,dx,\sigma_L,\sigma_R,dx,σL​,σR​,d with st=[x,σL,σR,d]st=[x,\sigma_L,\sigma_R,d]st=[x,σL​,σR​,d], o.hash160(x)≠Ho.\mathrm{hash160}(x)\neq Ho.hash160(x)=H, ∣x∣≠32|x|\neq 32∣x∣=32, multisigLoop(o,[σL,σR],[L,R])=some true\mathrm{multisigLoop}(o,[\sigma_L,\sigma_R],[L,R])=\mathrm{some\ true}multisigLoop(o,[σL​,σR​],[L,R])=some true, (f.nulldummy=true⇒d=[ ]f.\mathrm{nulldummy}=\mathrm{true}\Rightarrow d=[\,]f.nulldummy=true⇒d=[]) and CsvPasses(f,o,1)\mathrm{CsvPasses}(f,o,1)CsvPasses(f,o,1).

ReceivedSpend(f,o,H,R,L,P,e,st)\mathrm{ReceivedSpend}(f,o,H,R,L,P,e,st)ReceivedSpend(f,o,H,R,L,P,e,st) is the disjunction of

  1. there are pk,σpk,\sigmapk,σ with st=[pk,σ]st=[pk,\sigma]st=[pk,σ], o.hash160(pk)=Ho.\mathrm{hash160}(pk)=Ho.hash160(pk)=H and o.checkSig(σ,pk)=some trueo.\mathrm{checkSig}(\sigma,pk)=\mathrm{some\ true}o.checkSig(σ,pk)=some true;
  2. there are x,σL,σR,dx,\sigma_L,\sigma_R,dx,σL​,σR​,d with st=[x,σL,σR,d]st=[x,\sigma_L,\sigma_R,d]st=[x,σL​,σR​,d], o.hash160(x)≠Ho.\mathrm{hash160}(x)\neq Ho.hash160(x)=H, ∣x∣=32|x|=32∣x∣=32, o.hash160(x)=Po.\mathrm{hash160}(x)=Po.hash160(x)=P, multisigLoop(o,[σL,σR],[L,R])=some true\mathrm{multisigLoop}(o,[\sigma_L,\sigma_R],[L,R])=\mathrm{some\ true}multisigLoop(o,[σL​,σR​],[L,R])=some true, (f.nulldummy=true⇒d=[ ]f.\mathrm{nulldummy}=\mathrm{true}\Rightarrow d=[\,]f.nulldummy=true⇒d=[]) and CsvPasses(f,o,1)\mathrm{CsvPasses}(f,o,1)CsvPasses(f,o,1);
  3. there are x,σx,\sigmax,σ with st=[x,σ]st=[x,\sigma]st=[x,σ], o.hash160(x)≠Ho.\mathrm{hash160}(x)\neq Ho.hash160(x)=H, ∣x∣≠32|x|\neq 32∣x∣=32, CltvPasses(f,o,e)\mathrm{CltvPasses}(f,o,e)CltvPasses(f,o,e), o.checkSig(σ,R)=some trueo.\mathrm{checkSig}(\sigma,R)=\mathrm{some\ true}o.checkSig(σ,R)=some true and CsvPasses(f,o,1)\mathrm{CsvPasses}(f,o,1)CsvPasses(f,o,1).

Common unfolded definitions, part P: byte-level scripts and parsing

Canonical push, pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d) for a byte string ddd: if ∣d∣<76|d|<76∣d∣<76 (= 0x4c0x4c0x4c), the single byte ∣d∣|d|∣d∣ followed by ddd; else if ∣d∣≤255|d|\le 255∣d∣≤255, the bytes 0x4c0x4c0x4c, ∣d∣|d|∣d∣, then ddd; else if ∣d∣≤65535|d|\le 65535∣d∣≤65535, the byte 0x4d0x4d0x4d, the two little-endian bytes of ∣d∣|d|∣d∣, then ddd; else the byte 0x4e0x4e0x4e, the four little-endian bytes of ∣d∣|d|∣d∣, then ddd.

numBytes(n)\mathrm{numBytes}(n)numBytes(n) for n∈Zn\in\mathbb Zn∈Z: if n=−1n=-1n=−1 or 1≤n≤161\le n\le161≤n≤16, the single byte n+0x50n+0x50n+0x50 (so numBytes(1)=[0x51]\mathrm{numBytes}(1)=[0x51]numBytes(1)=[0x51], numBytes(2)=[0x52]\mathrm{numBytes}(2)=[0x52]numBytes(2)=[0x52], numBytes(16)=[0x60]\mathrm{numBytes}(16)=[0x60]numBytes(16)=[0x60]); otherwise pushBytes(serialize(n))\mathrm{pushBytes}(\mathrm{serialize}(n))pushBytes(serialize(n)) (so numBytes(32)=[0x01,0x20]\mathrm{numBytes}(32)=[0x01,0x20]numBytes(32)=[0x01,0x20] and numBytes(0)=[0x00]\mathrm{numBytes}(0)=[0x00]numBytes(0)=[0x00], the empty push).

The serialized scripts of the anchors file (byte strings, ++++++ is concatenation):

toRemoteBytes(R)=pushBytes(R) ++ [0xad] ++ [0x51] ++ [0xb2]\mathrm{toRemoteBytes}(R)=\mathrm{pushBytes}(R)\,++\,[0xad]\,++\,[0x51]\,++\,[0xb2]toRemoteBytes(R)=pushBytes(R)++[0xad]++[0x51]++[0xb2].

anchorBytes(K)=pushBytes(K) ++ [0xac,0x73,0x64] ++ [0x60] ++ [0xb2,0x68]\mathrm{anchorBytes}(K)=\mathrm{pushBytes}(K)\,++\,[0xac,0x73,0x64]\,++\,[0x60]\,++\,[0xb2,0x68]anchorBytes(K)=pushBytes(K)++[0xac,0x73,0x64]++[0x60]++[0xb2,0x68].

offeredBytes(H,R,L,P)=[0x76,0xa9] ++ pushBytes(H) ++ [0x87,0x63,0xac,0x67] ++ pushBytes(R) ++ [0x7c,0x82] ++ [0x01,0x20] ++ [0x87,0x64,0x75] ++ [0x52] ++ [0x7c] ++ pushBytes(L) ++ [0x52] ++ [0xae,0x67,0xa9] ++ pushBytes(P) ++ [0x88,0xac,0x68] ++ [0x51] ++ [0xb2,0x75,0x68]\mathrm{offeredBytes}(H,R,L,P)=[0x76,0xa9]\,++\,\mathrm{pushBytes}(H)\,++\,[0x87,0x63,0xac,0x67]\,++\,\mathrm{pushBytes}(R)\,++\,[0x7c,0x82]\,++\,[0x01,0x20]\,++\,[0x87,0x64,0x75]\,++\,[0x52]\,++\,[0x7c]\,++\,\mathrm{pushBytes}(L)\,++\,[0x52]\,++\,[0xae,0x67,0xa9]\,++\,\mathrm{pushBytes}(P)\,++\,[0x88,0xac,0x68]\,++\,[0x51]\,++\,[0xb2,0x75,0x68]offeredBytes(H,R,L,P)=[0x76,0xa9]++pushBytes(H)++[0x87,0x63,0xac,0x67]++pushBytes(R)++[0x7c,0x82]++[0x01,0x20]++[0x87,0x64,0x75]++[0x52]++[0x7c]++pushBytes(L)++[0x52]++[0xae,0x67,0xa9]++pushBytes(P)++[0x88,0xac,0x68]++[0x51]++[0xb2,0x75,0x68].

receivedBytes(H,R,L,P,e)=[0x76,0xa9] ++ pushBytes(H) ++ [0x87,0x63,0xac,0x67] ++ pushBytes(R) ++ [0x7c,0x82] ++ [0x01,0x20] ++ [0x87,0x63,0xa9] ++ pushBytes(P) ++ [0x88] ++ [0x52] ++ [0x7c] ++ pushBytes(L) ++ [0x52] ++ [0xae,0x67,0x75] ++ numBytes(e) ++ [0xb1,0x75,0xac,0x68] ++ [0x51] ++ [0xb2,0x75,0x68]\mathrm{receivedBytes}(H,R,L,P,e)=[0x76,0xa9]\,++\,\mathrm{pushBytes}(H)\,++\,[0x87,0x63,0xac,0x67]\,++\,\mathrm{pushBytes}(R)\,++\,[0x7c,0x82]\,++\,[0x01,0x20]\,++\,[0x87,0x63,0xa9]\,++\,\mathrm{pushBytes}(P)\,++\,[0x88]\,++\,[0x52]\,++\,[0x7c]\,++\,\mathrm{pushBytes}(L)\,++\,[0x52]\,++\,[0xae,0x67,0x75]\,++\,\mathrm{numBytes}(e)\,++\,[0xb1,0x75,0xac,0x68]\,++\,[0x51]\,++\,[0xb2,0x75,0x68]receivedBytes(H,R,L,P,e)=[0x76,0xa9]++pushBytes(H)++[0x87,0x63,0xac,0x67]++pushBytes(R)++[0x7c,0x82]++[0x01,0x20]++[0x87,0x63,0xa9]++pushBytes(P)++[0x88]++[0x52]++[0x7c]++pushBytes(L)++[0x52]++[0xae,0x67,0x75]++numBytes(e)++[0xb1,0x75,0xac,0x68]++[0x51]++[0xb2,0x75,0x68].

getOp(s)\mathrm{getOp}(s)getOp(s), one instruction off the front of a byte string: none\mathrm{none}none if sss is empty. Otherwise let ccc be the first byte and rrr the rest. If c≤0x4ec\le 0x4ec≤0x4e: the push size is ccc itself when c<0x4cc<0x4cc<0x4c; the next byte when c=0x4cc=0x4cc=0x4c (none\mathrm{none}none if rrr is empty); the little-endian value of the next two bytes when c=0x4dc=0x4dc=0x4d (none\mathrm{none}none if fewer than two remain); the little-endian value of the next four bytes when c=0x4ec=0x4ec=0x4e (none\mathrm{none}none if fewer than four remain); then, with the size bytes removed from rrr, none\mathrm{none}none if fewer than size bytes remain, else the pair (push\mathrm{push}push of the next size bytes, the remainder). If c>0x4ec>0x4ec>0x4e: the pair (op(c)\mathrm{op}(c)op(c), rrr).

parseScript(s)\mathrm{parseScript}(s)parseScript(s): an auxiliary recursion with fuel ∣s∣|s|∣s∣: on the empty string, some [ ]\mathrm{some}\,[\,]some[]; with fuel 000 and a non-empty string, none\mathrm{none}none; otherwise getOp\mathrm{getOp}getOp (none\mathrm{none}none propagates) and the instruction is prepended to the parse of the remainder with one less fuel. The value is either none\mathrm{none}none or some\mathrm{some}some of a list of instructions.


Common unfolded definitions, part B: the verification layer

Concrete hashes. sha256\mathrm{sha256}sha256 (written here SHA256\mathrm{SHA256}SHA256) is a fixed, concrete implementation of SHA-256 on byte strings, producing a 32-byte string; ripemd160\mathrm{ripemd160}ripemd160 likewise is concrete RIPEMD-160 (20 bytes); hash160=ripemd160∘SHA256\mathrm{hash160}=\mathrm{ripemd160}\circ\mathrm{SHA256}hash160=ripemd160∘SHA256; hash256=SHA256∘SHA256\mathrm{hash256}=\mathrm{SHA256}\circ\mathrm{SHA256}hash256=SHA256∘SHA256. These are the only places where hashing is concrete; nothing is assumed about them beyond their definitions.

Consensus flags c.flagsc.\mathrm{flags}c.flags: a record of seven 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. scriptFlagsOf(F)\mathrm{scriptFlagsOf}(F)scriptFlagsOf(F) is the interpreter flag record ⟨F.cltv,F.csv,F.nulldummy⟩\langle F.\mathrm{cltv},F.\mathrm{csv},F.\mathrm{nulldummy}\rangle⟨F.cltv,F.csv,F.nulldummy⟩; sigFlagsOf(F)\mathrm{sigFlagsOf}(F)sigFlagsOf(F) is the signature-layer flag record ⟨dersig=F.dersig, lowS=false, strictenc=false, witnessPubkeyType=false⟩\langle \mathrm{dersig}=F.\mathrm{dersig},\ \mathrm{lowS}=\mathrm{false},\ \mathrm{strictenc}=\mathrm{false},\ \mathrm{witnessPubkeyType}=\mathrm{false}\rangle⟨dersig=F.dersig, lowS=false, strictenc=false, witnessPubkeyType=false⟩.

Context ccc: a record with c.flagsc.\mathrm{flags}c.flags as above, a transaction c.txc.\mathrm{tx}c.tx, an input index c.nIn∈Nc.\mathrm{nIn}\in\mathbb Nc.nIn∈N and an amount c.amount∈Zc.\mathrm{amount}\in\mathbb Zc.amount∈Z. A transaction txtxtx has tx.version∈Ntx.\mathrm{version}\in\mathbb Ntx.version∈N, a list of inputs tx.vintx.\mathrm{vin}tx.vin, a list of outputs tx.vouttx.\mathrm{vout}tx.vout and tx.nLockTime∈Ntx.\mathrm{nLockTime}\in\mathbb Ntx.nLockTime∈N; an input has a previous outpoint, a scriptSig, nSequence∈N\mathrm{nSequence}\in\mathbb NnSequence∈N and a witness list. No range bounds (e.g. below 2322^{32}232) are imposed on version\mathrm{version}version, nSequence\mathrm{nSequence}nSequence or nLockTime\mathrm{nLockTime}nLockTime unless a hypothesis states one, and c.nInc.\mathrm{nIn}c.nIn may exceed the number of inputs.

inputSequence(tx,n)\mathrm{inputSequence}(tx,n)inputSequence(tx,n): the nSequence\mathrm{nSequence}nSequence of the nnn-th input (0-based) of txtxtx, or 000 when nnn is not a valid index (the default input has nSequence=0\mathrm{nSequence}=0nSequence=0).

Taproot handler taptaptap: an arbitrary function from (context, witness list, program bytes) to Booleans; it is a parameter with no hypotheses.

witnessBytes(0,prog)\mathrm{witnessBytes}(0,prog)witnessBytes(0,prog): the byte 0x000x000x00 followed by pushBytes(prog)\mathrm{pushBytes}(prog)pushBytes(prog). For a 32-byte progprogprog this is the 34-byte string [0x00,0x20] ++ prog[0x00,0x20]\,++\,prog[0x00,0x20]++prog.

checkSequence(tx,n,q)\mathrm{checkSequence}(tx,n,q)checkSequence(tx,n,q) for q∈Zq\in\mathbb Zq∈Z: let τ=inputSequence(tx,n)\tau=\mathrm{inputSequence}(tx,n)τ=inputSequence(tx,n); false\mathrm{false}false if tx.version<2tx.\mathrm{version}<2tx.version<2; false\mathrm{false}false if τ & 231≠0\tau\,\&\,2^{31}\neq0τ&231=0; otherwise with mask m=222 ∣ 0xffffm=2^{22}\,|\,0xffffm=222∣0xffff, τm=τ & m\tau_m=\tau\,\&\,mτm​=τ&m and qm=max⁡(q,0) & mq_m=\max(q,0)\,\&\,mqm​=max(q,0)&m: false\mathrm{false}false unless (τm<222\tau_m<2^{22}τm​<222 and qm<222q_m<2^{22}qm​<222) or (222≤τm2^{22}\le\tau_m222≤τm​ and 222≤qm2^{22}\le q_m222≤qm​); false\mathrm{false}false if τm<qm\tau_m<q_mτm​<qm​; else true\mathrm{true}true. For q=16q=16q=16: qm=16q_m=16qm​=16, so checkSequence(tx,n,16)=true\mathrm{checkSequence}(tx,n,16)=\mathrm{true}checkSequence(tx,n,16)=true iff 2≤tx.version2\le tx.\mathrm{version}2≤tx.version, bit 31 of τ\tauτ is clear, bit 22 of τ\tauτ is clear, and 16≤τ & 0xffff16\le\tau\,\&\,0xffff16≤τ&0xffff. For q=1q=1q=1: likewise with 1≤τ & 0xffff1\le\tau\,\&\,0xffff1≤τ&0xffff.

checkLockTime(tx,n,t)\mathrm{checkLockTime}(tx,n,t)checkLockTime(tx,n,t) for t∈Zt\in\mathbb Zt∈Z: false\mathrm{false}false unless (tx.nLockTime<500000000tx.\mathrm{nLockTime}<500000000tx.nLockTime<500000000 and t<500000000t<500000000t<500000000) or (500000000≤tx.nLockTime500000000\le tx.\mathrm{nLockTime}500000000≤tx.nLockTime and 500000000≤t500000000\le t500000000≤t); false\mathrm{false}false if tx.nLockTime<ttx.\mathrm{nLockTime}<ttx.nLockTime<t; false\mathrm{false}false if inputSequence(tx,n)=0xffffffff\mathrm{inputSequence}(tx,n)=0xffffffffinputSequence(tx,n)=0xffffffff; else true\mathrm{true}true.

Signature check with the flags sigFlagsOf(c.flags)\mathrm{sigFlagsOf}(c.\mathrm{flags})sigFlagsOf(c.flags), version witnessV0, script code XXX: checkSigPreTapscript(σ,k)\mathrm{checkSigPreTapscript}(\sigma,k)checkSigPreTapscript(σ,k) is none\mathrm{none}none iff c.flags.dersig=truec.\mathrm{flags}.\mathrm{dersig}=\mathrm{true}c.flags.dersig=true, σ≠[ ]\sigma\neq[\,]σ=[] and σ\sigmaσ fails the strict-DER test isValidSignatureEncoding\mathrm{isValidSignatureEncoding}isValidSignatureEncoding (the public-key encoding check always passes because strictenc and witnessPubkeyType are off); otherwise it is some\mathrm{some}some of checkECDSASignature(c.tx,c.nIn,c.amount,witnessV0,σ,k,X)\mathrm{checkECDSASignature}(c.\mathrm{tx},c.\mathrm{nIn},c.\mathrm{amount},\mathrm{witnessV0},\sigma,k,X)checkECDSASignature(c.tx,c.nIn,c.amount,witnessV0,σ,k,X), which is: false\mathrm{false}false if kkk is not a public key of valid declared length (first byte 222 or 333 with ∣k∣=33|k|=33∣k∣=33, or 444, 666 or 777 with ∣k∣=65|k|=65∣k∣=65); false\mathrm{false}false if σ=[ ]\sigma=[\,]σ=[]; otherwise, with the last byte of σ\sigmaσ as the hash type and σ′\sigma'σ′ the rest, false\mathrm{false}false if c.amount<0c.\mathrm{amount}<0c.amount<0, else the ECDSA verification (lax DER parse of σ′\sigma'σ′, low-S normalization, secp256k1 verification) of the BIP143 signature hash of c.txc.\mathrm{tx}c.tx at input c.nInc.\mathrm{nIn}c.nIn with script code XXX, amount c.amountc.\mathrm{amount}c.amount and that hash type, under key kkk. In particular the empty signature [ ][\,][] always yields some false\mathrm{some\ false}some false, never none\mathrm{none}none.

legacyOracle(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,witnessV0,X)\mathrm{legacyOracle}(\mathrm{sigFlagsOf}(c.\mathrm{flags}),c.\mathrm{tx},c.\mathrm{nIn},c.\mathrm{amount},\mathrm{witnessV0},X)legacyOracle(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,witnessV0,X): the oracle whose five hash functions are the concrete ripemd160,sha1,SHA256,hash160,hash256\mathrm{ripemd160},\mathrm{sha1},\mathrm{SHA256},\mathrm{hash160},\mathrm{hash256}ripemd160,sha1,SHA256,hash160,hash256, whose checkSig\mathrm{checkSig}checkSig is the function just described (with script code XXX unchanged, no FindAndDelete), whose checkLockTime\mathrm{checkLockTime}checkLockTime is checkLockTime(c.tx,c.nIn,⋅)\mathrm{checkLockTime}(c.\mathrm{tx},c.\mathrm{nIn},\cdot)checkLockTime(c.tx,c.nIn,⋅) and whose checkSequence\mathrm{checkSequence}checkSequence is checkSequence(c.tx,c.nIn,⋅)\mathrm{checkSequence}(c.\mathrm{tx},c.\mathrm{nIn},\cdot)checkSequence(c.tx,c.nIn,⋅). Below this oracle is written oXo_XoX​.

evalBytes(c,v,st,s)\mathrm{evalBytes}(c,v,st,s)evalBytes(c,v,st,s): none\mathrm{none}none if 10000<∣s∣10000<|s|10000<∣s∣; else none\mathrm{none}none if parseScript(s)=none\mathrm{parseScript}(s)=\mathrm{none}parseScript(s)=none; else evalScript(scriptFlagsOf(c.flags), legacyOracle(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s), st, parseScript(s))\mathrm{evalScript}(\mathrm{scriptFlagsOf}(c.\mathrm{flags}),\ \mathrm{legacyOracle}(\mathrm{sigFlagsOf}(c.\mathrm{flags}),c.\mathrm{tx},c.\mathrm{nIn},c.\mathrm{amount},v,s),\ st,\ \mathrm{parseScript}(s))evalScript(scriptFlagsOf(c.flags), legacyOracle(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s), st, parseScript(s)).

isWitnessProgram(s)\mathrm{isWitnessProgram}(s)isWitnessProgram(s): none\mathrm{none}none if ∣s∣<4|s|<4∣s∣<4 or 42<∣s∣42<|s|42<∣s∣; with b0b_0b0​ the first byte, none\mathrm{none}none if b0≠0b_0\neq0b0​=0 and (b0<0x51b_0<0x51b0​<0x51 or 0x60<b00x60<b_00x60<b0​); some(version, s without its first two bytes)\mathrm{some}(\text{version},\ s\text{ without its first two bytes})some(version, s without its first two bytes) if the second byte plus 222 equals ∣s∣|s|∣s∣, where version is 000 for b0=0b_0=0b0​=0 and b0−0x50b_0-0x50b0​−0x50 otherwise; none\mathrm{none}none otherwise.

executeWitnessScriptV0(c,st,X)\mathrm{executeWitnessScriptV0}(c,st,X)executeWitnessScriptV0(c,st,X): false\mathrm{false}false if some element of ststst is longer than 520520520 bytes; else evalBytes(c,witnessV0,st,X)\mathrm{evalBytes}(c,\mathrm{witnessV0},st,X)evalBytes(c,witnessV0,st,X): none\mathrm{none}none gives false\mathrm{false}false; some st′\mathrm{some}\,st'somest′ gives (∣st′∣=1|st'|=1∣st′∣=1 and topTrue(st′)\mathrm{topTrue}(st')topTrue(st′)).

verifyWitnessProgram(tap,c,w,version,prog,isP2sh)\mathrm{verifyWitnessProgram}(tap,c,w,\text{version},prog,\text{isP2sh})verifyWitnessProgram(tap,c,w,version,prog,isP2sh), for version 000 and ∣prog∣=32|prog|=32∣prog∣=32: false\mathrm{false}false if www is empty; else with XXX the last element of www, false\mathrm{false}false if SHA256(X)≠prog\mathrm{SHA256}(X)\neq progSHA256(X)=prog, else executeWitnessScriptV0(c, reverse(w without its last element), X)\mathrm{executeWitnessScriptV0}(c,\ \mathrm{reverse}(w\text{ without its last element}),\ X)executeWitnessScriptV0(c, reverse(w without its last element), X). (Version 0 with a 20-byte program is the P2WPKH case; other version-0 lengths give false\mathrm{false}false; version 1 with a 32-byte non-P2SH program gives true\mathrm{true}true if c.flags.taprootc.\mathrm{flags}.\mathrm{taproot}c.flags.taproot is off and tap(c,w,prog)tap(c,w,prog)tap(c,w,prog) otherwise; everything else gives true\mathrm{true}true.)

verifyScript(tap,c,scriptSig,scriptPubKey,w)\mathrm{verifyScript}(tap,c,\mathrm{scriptSig},\mathrm{scriptPubKey},w)verifyScript(tap,c,scriptSig,scriptPubKey,w): evaluate evalBytes(c,base,[ ],scriptSig)\mathrm{evalBytes}(c,\mathrm{base},[\,],\mathrm{scriptSig})evalBytes(c,base,[],scriptSig) (none\mathrm{none}none gives false\mathrm{false}false) to a stack st1st_1st1​; evaluate evalBytes(c,base,st1,scriptPubKey)\mathrm{evalBytes}(c,\mathrm{base},st_1,\mathrm{scriptPubKey})evalBytes(c,base,st1​,scriptPubKey) (none\mathrm{none}none gives false\mathrm{false}false) to a stack st2st_2st2​; false\mathrm{false}false if topTrue(st2)\mathrm{topTrue}(st_2)topTrue(st2​) is false. Then, if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is true and isWitnessProgram(scriptPubKey)=some(version,prog)\mathrm{isWitnessProgram}(\mathrm{scriptPubKey})=\mathrm{some}(\text{version},prog)isWitnessProgram(scriptPubKey)=some(version,prog): the result is false\mathrm{false}false if scriptSig≠[ ]\mathrm{scriptSig}\neq[\,]scriptSig=[] and otherwise verifyWitnessProgram(tap,c,w,version,prog,false)\mathrm{verifyWitnessProgram}(tap,c,w,\text{version},prog,\mathrm{false})verifyWitnessProgram(tap,c,w,version,prog,false). Otherwise (witness flag off, or not a witness program) the P2SH branch applies: if c.flags.p2shc.\mathrm{flags}.\mathrm{p2sh}c.flags.p2sh and scriptPubKey is 0xa9 ⟨20 bytes⟩ 0x870xa9\ \langle 20\text{ bytes}\rangle\ 0x870xa9 ⟨20 bytes⟩ 0x87, the redeem script is run (details omitted here as they do not arise for the statements' arguments); else false\mathrm{false}false if c.flags.witnessc.\mathrm{flags}.\mathrm{witness}c.flags.witness is on and www is non-empty, else true\mathrm{true}true.

Unfolding on the arguments of this statement (scriptSig =[ ]=[\,]=[], scriptPubKey =witnessBytes(0,SHA256(X))=\mathrm{witnessBytes}(0,\mathrm{SHA256}(X))=witnessBytes(0,SHA256(X)) for a script byte string XXX, witness list w=ws ++ [X]w=ws\,++\,[X]w=ws++[X], and c.flags.witness=truec.\mathrm{flags}.\mathrm{witness}=\mathrm{true}c.flags.witness=true): evalBytes\mathrm{evalBytes}evalBytes of the empty scriptSig yields the empty stack; the scriptPubKey [0x00,0x20] ++ SHA256(X)[0x00,0x20]\,++\,\mathrm{SHA256}(X)[0x00,0x20]++SHA256(X) parses to [push([ ]),push(SHA256(X))][\mathrm{push}([\,]),\mathrm{push}(\mathrm{SHA256}(X))][push([]),push(SHA256(X))] and evaluates to the stack [SHA256(X),[ ]][\mathrm{SHA256}(X),[\,]][SHA256(X),[]], whose topTrue\mathrm{topTrue}topTrue is castToBool(SHA256(X))\mathrm{castToBool}(\mathrm{SHA256}(X))castToBool(SHA256(X)) (true iff the 32-byte digest is not all zero bytes and is not 31 zero bytes followed by 0x800x800x80); isWitnessProgram\mathrm{isWitnessProgram}isWitnessProgram of that 34-byte string is some(0,SHA256(X))\mathrm{some}(0,\mathrm{SHA256}(X))some(0,SHA256(X)); the last element of www is XXX and SHA256(X)=SHA256(X)\mathrm{SHA256}(X)=\mathrm{SHA256}(X)SHA256(X)=SHA256(X), so the verdict is executeWitnessScriptV0(c,reverse(ws),X)\mathrm{executeWitnessScriptV0}(c,\mathrm{reverse}(ws),X)executeWitnessScriptV0(c,reverse(ws),X): false\mathrm{false}false if some element of wswsws exceeds 520520520 bytes, false\mathrm{false}false if ∣X∣>10000|X|>10000∣X∣>10000 or XXX does not parse, and otherwise "evalScript(scriptFlagsOf(c.flags),oX,reverse(ws),parseScript(X))\mathrm{evalScript}(\mathrm{scriptFlagsOf}(c.\mathrm{flags}),o_X,\mathrm{reverse}(ws),\mathrm{parseScript}(X))evalScript(scriptFlagsOf(c.flags),oX​,reverse(ws),parseScript(X)) is some\mathrm{some}some of a one-element stack whose element is castToBool\mathrm{castToBool}castToBool-true".

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