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_p2wsh_spend
A byte is an 8-bit word; a byte string (Bytes) is a finite list of bytes; a stack is a finite list of byte strings whose first entry is the top, except where a list is explicitly said to be in "witness order" (last entry on top).
The quantified data and hypotheses
The theorem quantifies over:
- tap: an arbitrary function Ctx×(list of byte strings)×Bytes→Bool (a "Taproot handler"); nothing is assumed about it;
- c: a verification context, a record with fields
- c.flags: a record of seven booleans p2sh, witness, taproot, dersig, cltv, csv, nulldummy;
- c.tx: a transaction, a record (version∈N, vin, vout, nLockTime∈N) where vin is a list of inputs, each (prevout=(hash∈Bytes, n∈N), scriptSig∈Bytes, nSequence∈N, witness:list of byte strings), and vout is a list of outputs, each (nValue∈Z, scriptPubKey∈Bytes);
- c.nIn∈N (an input index; it may exceed the number of inputs);
- c.amount∈Z (it may be negative);
- the hypothesis hf: c.flags.witness=true (the other six flags are unconstrained);
- two byte strings k1,k2 (
pubkey1, pubkey2), unconstrained in content, with the hypotheses ∣k1∣≤520 and ∣k2∣≤520;
- ws: an arbitrary list of byte strings (possibly empty; element sizes are not bounded by any hypothesis).
Write B:=fundingBytes(k1,k2), H:=SHA256(B), and P:=witnessBytes(0,H).
Statement
verifyScript(tap, c, [], P, ws∥[B])=true⟺castToBool(H)=true ∧ (∀e∈ws, ∣e∣≤520) ∧ FundingSpend(F, O, k1, k2, reverse(ws)),
where
- [] in the third argument is the empty scriptSig (an empty byte string), P is the scriptPubKey, and ws∥[B] is the witness: the list ws with B appended as its last element (so the witness is never empty, even when ws is);
- F:=scriptFlagsOf(c.flags)=(cltv:=c.flags.cltv, csv:=c.flags.csv, nulldummy:=c.flags.nulldummy);
- O:=legacyOracle(sigFlagsOf(c.flags), c.tx, c.nIn, c.amount, witnessV0, B) with sigFlagsOf(c.flags)=(dersig:=c.flags.dersig, lowS:=false, strictenc:=false, witnessPubkeyType:=false);
- reverse(ws) is ws in reverse order.
Each piece is unfolded below.
The byte strings B, H, P
B=fundingBytes(k1,k2)=[0x52] ∥ pushBytes(k1) ∥ pushBytes(k2) ∥ [0x52,0xae], where pushBytes(d) for ℓ=∣d∣ is: [ℓ]∥d if ℓ<76; [0x4c,ℓ]∥d if ℓ≤255; [0x4d]∥(ℓ as 2 LE bytes)∥d if ℓ≤65535; else [0x4e]∥(ℓ as 4 LE bytes)∥d.
SHA256 is the serialization file's own transcription of SHA-256 (Merkle–Damgård padding with a big-endian 64-bit bit-length, 64-round compression with the standard constants, output the eight 32-bit state words big-endian); its output always has 32 bytes.
witnessBytes(v,prog) is the byte 0x00 if v=0 (else 0x50+v) followed by pushBytes(prog). Hence P=[0x00,0x20]∥H, a 34-byte string.
Right-hand side, first conjunct: castToBool(H)=true
castToBool(b): false for b=[]; for one byte [x], true iff x=0x00 and x=0x80; for x::rest with rest=[], true iff x=0x00 or castToBool(rest). For the 32-byte H: true iff one of its first 31 bytes is non-zero, or its last byte is neither 0x00 nor 0x80.
Right-hand side, second conjunct
Every element of ws has length at most 520. This is vacuously true when ws=[]. (Note this is a conjunct of the right-hand side, not a hypothesis of the theorem.)
Right-hand side, third conjunct: FundingSpend(F,O,k1,k2,reverse(ws))
By definition this is
∃s1,s2,d∈Bytes: reverse(ws)=[s2,s1,d] ∧ O.checkSig(s1,k1)=sometrue ∧ O.checkSig(s2,k2)=sometrue ∧ (F.nulldummy=true⇒d=[]).
Since reverse(ws)=[s2,s1,d] iff ws=[d,s1,s2]: ws must have exactly three elements, in the order d (first), s1, s2 (last); if ws has any other length (including 0) the conjunct is false. F.nulldummy is c.flags.nulldummy; when it is true, d must be empty; otherwise d is arbitrary. The sizes of s1,s2,d are constrained only by the second conjunct.
The oracle O. legacyOracle(sf,tx,nIn,amt,v,sc) is the oracle whose hash fields are the concrete RIPEMD-160, SHA-1, SHA-256, Hash160=RIPEMD160∘SHA256 and Hash256=SHA256∘SHA256 of the serialization file; whose lock-time fields are the transaction lock-time/sequence checks for (tx,nIn) (not consulted by FundingSpend); and whose checkSig(σ,π) is checkSigPreTapscript(sf,tx,nIn,amt,v,sc,σ,π). Here sf=sigFlagsOf(c.flags), tx=c.tx, nIn=c.nIn, amt=c.amount, v=witnessV0, sc=B.
checkSigPreTapscript(sf,tx,nIn,amt,v,sc,σ,π). Since v=witnessV0, the script code used is sc=B itself (no FindAndDelete). The result is none if checkSignatureEncoding(sf,σ) is false or checkPubKeyEncoding(sf,v,π) is false; otherwise some(checkECDSASignature(tx,nIn,amt,v,σ,π,sc)).
- checkSignatureEncoding(sf,σ): true if σ=[]; else false if (sf.dersig∨sf.lowS∨sf.strictenc) and ¬isValidSignatureEncoding(σ); else false if sf.lowS and not low-S DER; else false if sf.strictenc and the hash type is not defined; else true. With sf=sigFlagsOf(c.flags) this reduces to: true if σ=[]; false if c.flags.dersig=true and ¬isValidSignatureEncoding(σ); true otherwise.
- isValidSignatureEncoding(σ), with ℓ=∣σ∣ and out-of-range indices reading as 0: false if ℓ<9 or ℓ>73; requires σ[0]=0x30, σ[1]=ℓ−3; let ℓR=σ[3], require ℓ>5+ℓR; let ℓS=σ[5+ℓR], require ℓR+ℓS+7=ℓ; σ[2]=0x02; ℓR=0; σ[4]<0x80; not (ℓR>1 and σ[4]=0 and σ[5]<0x80); σ[ℓR+4]=0x02; ℓS=0; σ[ℓR+6]<0x80; not (ℓS>1 and σ[ℓR+6]=0 and σ[ℓR+7]<0x80); true if all hold.
- checkPubKeyEncoding(sf,v,π): false if sf.strictenc and π is not a 33-byte (02/03) or 65-byte (04) key; false if sf.witnessPubkeyType and v=witnessV0 and π is not a 33-byte compressed key; else true. With sf=sigFlagsOf(c.flags) both flags are false, so this is always true: no public-key string is rejected at this stage.
Consequently, in this theorem, O.checkSig(σ,π)=none iff c.flags.dersig=true, σ=[] and σ fails isValidSignatureEncoding; and O.checkSig(σ,π)=sometrue iff that is not the case and checkECDSASignature(c.tx,c.nIn,c.amount,witnessV0,σ,π,B)=true.
checkECDSASignature(tx,nIn,amt,v,σ,π,sc). False if ¬pubkeyValid(π), where pubkeyValid(π) holds iff π=[] and ∣π∣ equals 33 when the first byte is 2 or 3, 65 when it is 4, 6 or 7, and 0 otherwise (so any other first byte gives false). False if σ=[]. Otherwise let ht be the last byte of σ (as a natural number, the hash type) and σ′ be σ without its last byte; let digest=sigHashWitnessV0(sc,tx,nIn,ht,amt) (since v=witnessV0); false if amt<0; otherwise pubkeyVerify(π,digest,σ′).
sigHashWitnessV0(sc,tx,nIn,ht,amt). Let acp:=(ht&0x80=0), single:=(ht&0x1f=3), none:=(ht&0x1f=2); 0 the 32-byte zero string; ser32(x) the 4 little-endian bytes of x modulo 232; serInt64(x) the 8 little-endian bytes of xmod264; serBytes(b) a CompactSize encoding of ∣b∣ followed by b; serOutPoint(h,n)=h∥ser32(n); serTxOut(o)=serInt64(o.nValue)∥serBytes(o.scriptPubKey); Hash256=SHA256∘SHA256.
- hashPrevouts:=Hash256 of the concatenation over all inputs of serOutPoint(prevout) if ¬acp, else 0;
- hashSequence:=Hash256 of the concatenation over all inputs of ser32(nSequence) if ¬acp∧¬single∧¬none, else 0;
- hashOutputs:=Hash256 of the concatenation of serTxOut over all outputs if ¬single∧¬none; else Hash256(serTxOut(vout[nIn])) if single and nIn<∣vout∣; else 0;
- i:=vin[nIn], or the default input (prevout=([],0), scriptSig=[], nSequence=0, witness=[]) when nIn≥∣vin∣;
- the digest is Hash256(ser32(version)∥hashPrevouts∥hashSequence∥serOutPoint(i.prevout)∥serBytes(sc)∥serInt64(amt)∥ser32(i.nSequence)∥hashOutputs∥ser32(nLockTime)∥ser32(ht)).
pubkeyVerify(π,h,σ′). False if ¬pubkeyValid(π). Let Q:=parsePubkey(π); false if none. Let (r,s):=parseDerLax(σ′); false if none. Otherwise ecdsaVerifyRaw(Q, beVal(h)modn, r, normalizeS(s)), where beVal is the big-endian value of a byte string and n is the secp256k1 group order.
- parsePubkey(π): for a 33-byte string with first byte 2 or 3, x:= big-endian value of the remaining 32 bytes; none if x≥p (the field prime 2256−232−977); else, with y0:=(x3+7)(p+1)/4modp, the point (x,y) with y∈{y0,p−y0} chosen so that y is odd iff the first byte is 3, provided y02≡x3+7(modp), else none. For a 65-byte string with first byte 4, 6 or 7: x,y:= big-endian values of bytes 1–32 and 33–64; the point (x,y) iff x<p, y<p, y2≡x3+7(modp), and (if the first byte is 6 or 7) y is odd iff the byte is 7; else none. Any other string: none.
- parseDerLax(σ′): a lax DER parse (sequence tag 0x30, length byte possibly long-form, two integers each with tag 0x02 and short- or long-form length with leading zero length bytes stripped and at most 3 length bytes); none where the parser fails (empty input, wrong tags, lengths overrunning the input); after stripping leading zero bytes of each integer, the pair (0,0) if either integer has more than 32 significant bytes or if r≥n or s≥n; otherwise (r,s). Bytes after the second integer are ignored.
- normalizeS(s)=n−s if s>⌊n/2⌋, else s.
- ecdsaVerifyRaw(Q,e,r,s): false if r=0 or s=0 or r≥n or s≥n; else with w:=sn−2modn, u1:=ewmodn, u2:=rwmodn, and R:=u1G+u2Q computed by the file's affine secp256k1 formulas (double-and-add with 257 iterations of fuel, field inversion by Fermat exponentiation with 0↦0), false if R is the point at infinity, and otherwise true iff x(R)modn=r. G is the standard secp256k1 generator given by its coordinates.
Left-hand side: verifyScript
verifyScript(tap,c,scriptSig,scriptPubKey,witness), in general:
- st1:=evalBytes(c,base,[],scriptSig); result false if none.
- st2:=evalBytes(c,base,st1,scriptPubKey); false if none.
- false if ¬topTrue(st2), where topTrue of an empty stack is false and otherwise is castToBool of the top element.
- If c.flags.witness (true here by hf): compute isWitnessProgram(scriptPubKey); if it is some(v,prog) then the result is false if scriptSig=[], else verifyWitnessProgram(tap,c,witness,v,prog,false); if it is none, continue.
- (Only reached when the scriptPubKey is not a witness program.) If c.flags.p2sh and scriptPubKey is 23 bytes of the form 0xa9,0x14,…,0x87: the pay-to-script-hash branch (push-only scriptSig, redeem script taken from the top of st1, re-evaluation, a nested witness-program check); otherwise false if c.flags.witness and witness=[], else true.
evalBytes(c,v,st,s): none if ∣s∣>10000; none if parseScript(s)=none; otherwise evalScript(scriptFlagsOf(c.flags), legacyOracle(sigFlagsOf(c.flags),c.tx,c.nIn,c.amount,v,s), st, parsed(s)) — note the oracle's script code is the byte string s being evaluated, and the signature version v is as passed.
parseScript(s): splits s into instructions left to right: a byte o≤0x4e starts a push (size o if o<0x4c; the next 1, 2 or 4 little-endian bytes for 0x4c,0x4d,0x4e), none if the size or the data run past the end; a byte >0x4e is a non-push opcode op(o). The empty string parses to the empty script.
isWitnessProgram(s): none if ∣s∣<4 or ∣s∣>42; with b0:=s[0], none if b0=0 and (b0<0x51 or b0>0x60); some(decodeOpN(b0), s without its first two bytes) if s[1]+2=∣s∣, else none; decodeOpN(0)=0 and decodeOpN(b)=b−0x50 otherwise.
verifyWitnessProgram(tap,c,W,v,prog,isP2sh), with W in witness order (last element on top):
- v=0 and ∣prog∣=32: false if W=[]; else let ς be the last element of W; false if SHA256(ς)=prog; else executeWitnessScriptV0(c, reverse(W without its last element), ς).
- v=0 and ∣prog∣=20: false unless ∣W∣=2, then the pay-to-witness-public-key-hash execution. v=0 with any other program length: false.
- v=1, ∣prog∣=32, ¬isP2sh: true if ¬c.flags.taproot, else tap(c,W,prog) (the only place tap is consulted).
- otherwise true (unknown versions and pay-to-anchor).
executeWitnessScriptV0(c,st,exec): false if some element of st has length >520; else evalBytes(c,witnessV0,st,exec): false if none; if some(st′), the result is ∣st′∣=1 and topTrue(st′).
Specialized to the theorem's arguments (by the definitions above, on the concrete syntactic inputs): the scriptSig is [], which parses to the empty script and evaluates on the empty stack to some[]; the scriptPubKey P=[0x00,0x20]∥H parses to the two pushes push([]), push(H), evaluated under base with the legacy oracle for script code P; isWitnessProgram(P) is some(0,H) (since ∣P∣=34∈[4,42], b0=0, and 0x20+2=34); the scriptSig is empty, so step 4 yields verifyWitnessProgram(tap,c, ws∥[B], 0, H, false); there ∣H∣=32, the last element of ws∥[B] is B, and removing it and reversing gives reverse(ws), so this is: false if SHA256(B)=H (which is the definition of H), else executeWitnessScriptV0(c,reverse(ws),B), i.e. the 520-byte check on every element of ws, then evalBytes(c,witnessV0,reverse(ws),B) — which, if ∣B∣≤10000 and B parses, is the interpreter evalScript with flags F and oracle O (the same F and O as on the right-hand side, since the script code is B and the version is witnessV0) on the initial stack reverse(ws) over the parsed B — and finally the requirement that the resulting stack have exactly one element whose castToBool is true.
The interpreter evalScript (as invoked above)
evalScript(f,o,st0,S) is none or some(st). State: (main stack, alternate stack, condition stack vfExec, opcode counter), initially (st0,[],[],0); instructions of S are run in order, any failure giving none; after the last instruction the run fails if vfExec=[], else returns the main stack.
- push(x): fail if ∣x∣>520; if all of vfExec is true (vacuous when empty) push x; fail if ∣main∣+∣alt∣>1000.
- op(γ): counted iff γ>0x60; if counted and counter+1>201 fail, else increment if counted; fail if γ is one of the fifteen disabled opcodes; if all of vfExec is true or 0x63≤γ≤0x68, run the one-opcode executor (fail on failure) and then the 1000 check; else skip with the 1000 check.
One-opcode executor on the opcodes that the parsed B can contain, 0x52 and 0xae (the keys k1,k2 appear only as push data; if parsing of B yields other opcodes, their branches are not reproduced here):
- γ=0x52 (branch for 0x4f or 0x51–0x60; not counted): push the script-number encoding of γ−0x50, i.e. [0x02].
- γ=0xae (counted), with main stack st and counter κ: fail if st=[]; st=nk::r; Nk:= signed little-endian value of nk (fail if ∣nk∣>4; sign = top bit of last byte; empty =0); fail if Nk<0 or Nk>20; κ′:=κ+Nk, fail if κ′>201; keys:= first Nk of r, r:= rest, fail if fewer were available; fail if r=[]; r=ns::r; Ns:= value of ns likewise (fail if ∣ns∣>4); fail if Ns<0 or Ns>Nk; sigs:= first Ns of r, r:= rest, fail if fewer were available; multisigLoop(o,sigs,keys): fail if none, else ok; fail if r=[]; r=d′::r′; fail if f.nulldummy and d′=[]; new main stack boolBytes(ok)::r′ ([0x01] for true, [] for false), counter κ′.
multisigLoop(o,sigs,keys) (top-first): sigs=[]⇒sometrue; sigs=[],keys=[]⇒somefalse; sigs=s::sigs′, keys=k::keys′: o.checkSig(s,k) is none⇒none; sometrue⇒ if ∣keys′∣<∣sigs′∣ then somefalse else recurse on (sigs′,keys′); somefalse⇒ if ∣keys′∣<∣sigs∣ then somefalse else recurse on (sigs,keys′) (same signature, next key). The top signature is tried against the top key first.
What the quantification silently includes
- ws may be empty or of any length; its elements may be of any size. On the right-hand side, a ws of length =3 makes FundingSpend false; on the left, reverse(ws) is the initial witness stack.
- The hypotheses ∣k1∣,∣k2∣≤520 bound only the two keys; the keys are arbitrary byte strings (no public-key format is assumed; the encoding check on keys is vacuous under sigFlagsOf, and format only enters through pubkeyValid/parsePubkey inside checkECDSASignature).
- c.amount may be negative (then checkECDSASignature is false for every signature/key pair); c.nIn may be out of range (then the default input is used in the digest); c.flags.p2sh,taproot,dersig,cltv,csv,nulldummy are unconstrained; c.flags.witness is fixed to true by hf.
- tap is arbitrary and enters only through the version-1 branch of verifyWitnessProgram.
- The equivalence relates a boolean equal to true on the left with a conjunction of a boolean equation, a universally quantified bound, and an existential proposition on the right.
Confirmed by the moderator at approval.