Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

IsWitnessProgram characterized

Proved
BitcoinVerify.isWitnessProgram_iff

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

bip141bitcoinbitcoin-mainnetconsensusformal-verificationp2shsegwitverifyscript

isWitnessProgram s = some (v, program) iff v≤16v \le 16v≤16, 2≤∣program∣≤402 \le |program| \le 402≤∣program∣≤40 and sss is OP_v <program> (a single direct push), i.e. witnessBytes v program.

Preamble
import Definitions.Def_BitcoinVerify
open BitcoinVerify BitcoinSer BitcoinSig
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinVerify.isWitnessProgram_iff (s : Bytes) (v : Nat) (prog : Bytes) :
    BitcoinVerify.isWitnessProgram s = some (v, prog) ↔
      v ≤ 16 ∧ 2 ≤ prog.length ∧ prog.length ≤ 40 ∧ s = BitcoinVerify.witnessBytes v prog := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyScript, VerifyWitnessProgram, ExecuteWitnessScript, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; CScript::IsPayToScriptHash, IsWitnessProgram, IsPushOnly, IsPayToAnchor, DecodeOP_N, src/script/script.cpp and script.h; MAX_SCRIPT_SIZE, WITNESS_V0_SCRIPTHASH_SIZE, WITNESS_V0_KEYHASH_SIZE, WITNESS_V1_TAPROOT_SIZE; BIP16, BIP141, BIP143 at bips revision 100ba872c808946155b1eeb8c4568058f2eea0a7
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: BitcoinVerify.isWitnessProgram_iff

Binders and hypothesis. Three universally quantified variables: sss, a byte string; vvv, a natural number; prog\mathrm{prog}prog, a byte string. There are no hypotheses.

Conclusion. A biconditional:

isWitnessProgram(s)=some(v,prog)  ⟺  v≤16 ∧ 2≤∣prog∣ ∧ ∣prog∣≤40 ∧ s=witnessBytes(v,prog).\mathrm{isWitnessProgram}(s) = \mathrm{some}(v, \mathrm{prog}) \iff v \le 16 \ \wedge\ 2 \le |\mathrm{prog}| \ \wedge\ |\mathrm{prog}| \le 40 \ \wedge\ s = \mathrm{witnessBytes}(v, \mathrm{prog}).isWitnessProgram(s)=some(v,prog)⟺v≤16 ∧ 2≤∣prog∣ ∧ ∣prog∣≤40 ∧ s=witnessBytes(v,prog).

Unfolding the left-hand side. isWitnessProgram s returns nothing unless 4≤∣s∣≤424 \le |s| \le 424≤∣s∣≤42 (it returns nothing when ∣s∣<4|s| < 4∣s∣<4 or 42<∣s∣42 < |s|42<∣s∣). Writing b0b_0b0​ for the first byte of sss (as a natural number), it returns nothing unless b0=0b_0 = 0b0​=0 or 0x51≤b0≤0x60\mathtt{0x51} \le b_0 \le \mathtt{0x60}0x51≤b0​≤0x60. It then requires that the second byte s1s_1s1​, as a natural number, satisfy s1+2=∣s∣s_1 + 2 = |s|s1​+2=∣s∣; if so it returns the pair (decodeOpN(b0), s with the first two bytes dropped)(\mathrm{decodeOpN}(b_0),\ s \text{ with the first two bytes dropped})(decodeOpN(b0​), s with the first two bytes dropped), otherwise nothing. Here decodeOpN(b)=0\mathrm{decodeOpN}(b) = 0decodeOpN(b)=0 if b=0b = 0b=0 and b−0x50b - \mathtt{0x50}b−0x50 (truncated subtraction) otherwise. Consequently the left side holds exactly when: 4≤∣s∣≤424 \le |s| \le 424≤∣s∣≤42; s0=0s_0 = 0s0​=0 and v=0v = 0v=0, or s0=0x50+vs_0 = \mathtt{0x50} + vs0​=0x50+v with 1≤v≤161 \le v \le 161≤v≤16; s1=∣s∣−2s_1 = |s| - 2s1​=∣s∣−2; and prog\mathrm{prog}prog is the suffix of sss after its first two bytes (so ∣prog∣=s1∈[2,40]|\mathrm{prog}| = s_1 \in [2, 40]∣prog∣=s1​∈[2,40]).

Unfolding the right-hand side. witnessBytes v prog is the byte string whose first byte is 000 if v=0v = 0v=0 and (0x50+v) mod 256(\mathtt{0x50} + v) \bmod 256(0x50+v)mod256 otherwise, followed by pushBytes prog. For ∣prog∣≤40<76|\mathrm{prog}| \le 40 < 76∣prog∣≤40<76, pushBytes prog is the single length byte ∣prog∣|\mathrm{prog}|∣prog∣ followed by prog\mathrm{prog}prog. So, under the three bounds on the right, sss must be the (∣prog∣+2)(|\mathrm{prog}| + 2)(∣prog∣+2)-byte string: the version byte (000, or 0x51\mathtt{0x51}0x51 through 0x60\mathtt{0x60}0x60), the length byte ∣prog∣∈[2,40]|\mathrm{prog}| \in [2, 40]∣prog∣∈[2,40], then prog\mathrm{prog}prog.

Logical content. For every sss, vvv, prog\mathrm{prog}prog: the parser recognizes sss as a witness program with exactly this version and this program if and only if vvv is at most 161616, the program has between 222 and 404040 bytes inclusive, and sss is literally the encoding witnessBytes v prog. Note that the right side uses v≤16v \le 16v≤16 with no lower bound (so v=0v = 0v=0 is included) and that the bounds 2≤∣prog∣2 \le |\mathrm{prog}|2≤∣prog∣ and ∣prog∣≤40|\mathrm{prog}| \le 40∣prog∣≤40 are both non-strict.

What is not said. Nothing is claimed about v>16v > 16v>16 except implicitly through the biconditional (for such vvv the left side must be false, since the right side is); nothing is claimed about what isWitnessProgram returns on strings that are not witness programs beyond "not some (v, prog)"; nothing about evaluation, about verifyWitnessProgram, about any flag, or about which versions are "known". The theorem does not say that the version byte of witnessBytes v prog is in range for v>16v > 16v>16 (it is not, and that is consistent with the statement).

Human review
  • Endorsed by Shuze Chen · Oct 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 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