Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The byte form parses to the instruction form

Proved
BitcoinToLocal.parseScript_toLocal

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

bip112bitcoinbitcoin-mainnetbolt3csvformal-verificationlightningp2wshscript

For keys of at most 520 bytes and ∣delay∣<232|{\rm delay}| < 2^{32}∣delay∣<232: parseScript (toLocalBytes rev delay dpk) = some (toLocalScript rev delay dpk), through GetOp on the canonical pushes and CScript's small-integer encoding.

Preamble
import Definitions.Def_BitcoinToLocal
import Definitions.Def_BitcoinScript
import Definitions.Def_BitcoinSig
open BitcoinToLocal BitcoinSig BitcoinVerify
open BitcoinScript
Formal statement
theorem BitcoinToLocal.parseScript_toLocal (rev dpk : Bytes) (delay : Int)
    (hrev : rev.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE) (hdpk : dpk.length ≤ BitcoinScript.MAX_SCRIPT_ELEMENT_SIZE)
    (hd : delay.natAbs < 2 ^ 32) :
    BitcoinSig.parseScript (BitcoinToLocal.toLocalBytes rev delay dpk) = some (BitcoinToLocal.toLocalScript rev delay dpk) := by sorry
Source
BOLT #3, Bitcoin Transaction and Script Formats, 'to_local Output': https://github.com/lightning/bolts/blob/master/03-transactions.md#to_local-output; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (OP_IF/OP_ELSE/OP_ENDIF, OP_CHECKSEQUENCEVERIFY, OP_CHECKSIG), GenericTransactionSignatureChecker::CheckSequence, ExecuteWitnessScript, VerifyWitnessProgram (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); CScript::operator<<(int64_t) (script/script.h); 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: BitcoinToLocal.parseScript_toLocal

Statement. For all byte strings RRR (named rev) and DDD (named dpk) and every integer δ\deltaδ (named delay), under the hypotheses

∣R∣≤520,∣D∣≤520,∣δ∣<232|R| \le 520, \qquad |D| \le 520, \qquad |\delta| < 2^{32}∣R∣≤520,∣D∣≤520,∣δ∣<232

(520520520 is the preamble's MAX_SCRIPT_ELEMENT_SIZE; ∣δ∣|\delta|∣δ∣ is the absolute value as a natural),

parseScript(toLocalBytes(R,δ,D))  =  some(toLocalScript(R,δ,D)).\mathrm{parseScript}\big(\mathrm{toLocalBytes}(R, \delta, D)\big) \;=\; \mathrm{some}\big(\mathrm{toLocalScript}(R, \delta, D)\big).parseScript(toLocalBytes(R,δ,D))=some(toLocalScript(R,δ,D)).

That is, byte-level parsing of the serialized script succeeds (does not return "none") and yields exactly the nine-instruction parsed script.

The two sides.

toLocalBytes(R,δ,D)\mathrm{toLocalBytes}(R, \delta, D)toLocalBytes(R,δ,D) is the byte string

[0x63]+ ⁣ ⁣+pushBytes(R)+ ⁣ ⁣+[0x67]+ ⁣ ⁣+numBytes(δ)+ ⁣ ⁣+[0xb2,0x75]+ ⁣ ⁣+pushBytes(D)+ ⁣ ⁣+[0x68,0xac],[\mathtt{0x63}] \mathbin{+\!\!+} \mathrm{pushBytes}(R) \mathbin{+\!\!+} [\mathtt{0x67}] \mathbin{+\!\!+} \mathrm{numBytes}(\delta) \mathbin{+\!\!+} [\mathtt{0xb2}, \mathtt{0x75}] \mathbin{+\!\!+} \mathrm{pushBytes}(D) \mathbin{+\!\!+} [\mathtt{0x68}, \mathtt{0xac}],[0x63]++pushBytes(R)++[0x67]++numBytes(δ)++[0xb2,0x75]++pushBytes(D)++[0x68,0xac],

where pushBytes(d)\mathrm{pushBytes}(d)pushBytes(d) is: for ∣d∣<76|d| < 76∣d∣<76, the byte ∣d∣|d|∣d∣ then ddd; for 76≤∣d∣≤25576 \le |d| \le 25576≤∣d∣≤255, bytes 0x4c,∣d∣\mathtt{0x4c}, |d|0x4c,∣d∣ then ddd; for 256≤∣d∣≤65535256 \le |d| \le 65535256≤∣d∣≤65535, byte 0x4d\mathtt{0x4d}0x4d, the 2-byte little-endian ∣d∣|d|∣d∣, then ddd; otherwise 0x4e\mathtt{0x4e}0x4e, the 4-byte little-endian ∣d∣|d|∣d∣, then ddd. And numBytes(δ)\mathrm{numBytes}(\delta)numBytes(δ) is the single byte δ+80\delta + 80δ+80 (i.e. 0x4f\mathtt{0x4f}0x4f for δ=−1\delta = -1δ=−1, 0x51…0x60\mathtt{0x51}\ldots\mathtt{0x60}0x51…0x60 for δ=1,…,16\delta = 1,\ldots,16δ=1,…,16) when δ=−1\delta = -1δ=−1 or 1≤δ≤161 \le \delta \le 161≤δ≤16, and pushBytes(serialize(δ))\mathrm{pushBytes}(\mathrm{serialize}(\delta))pushBytes(serialize(δ)) otherwise, with serialize\mathrm{serialize}serialize the script-number encoding (serialize(0)=[ ]\mathrm{serialize}(0) = [\,]serialize(0)=[], so numBytes(0)=[0x00]\mathrm{numBytes}(0) = [\mathtt{0x00}]numBytes(0)=[0x00]; for δ≠0\delta \ne 0δ=0 the little-endian magnitude bytes of ∣δ∣|\delta|∣δ∣ without trailing zeros, with an appended 0x80\mathtt{0x80}0x80/0x00\mathtt{0x00}0x00 byte if the top bit of the last byte is set, else the top bit set on the last byte when δ<0\delta<0δ<0).

toLocalScript(R,δ,D)\mathrm{toLocalScript}(R, \delta, D)toLocalScript(R,δ,D) is the instruction list

[ op 0x63, push R, op 0x67, numInstr(δ), op 0xb2, op 0x75, push D, op 0x68, op 0xac ],[\ \mathrm{op}\,\mathtt{0x63},\ \mathrm{push}\,R,\ \mathrm{op}\,\mathtt{0x67},\ \mathrm{numInstr}(\delta),\ \mathrm{op}\,\mathtt{0xb2},\ \mathrm{op}\,\mathtt{0x75},\ \mathrm{push}\,D,\ \mathrm{op}\,\mathtt{0x68},\ \mathrm{op}\,\mathtt{0xac}\ ],[ op0x63, pushR, op0x67, numInstr(δ), op0xb2, op0x75, pushD, op0x68, op0xac ],

where numInstr(δ)\mathrm{numInstr}(\delta)numInstr(δ) is the opcode with byte δ+80\delta + 80δ+80 when δ=−1\delta = -1δ=−1 or 1≤δ≤161 \le \delta \le 161≤δ≤16, and the data push of serialize(δ)\mathrm{serialize}(\delta)serialize(δ) otherwise (the empty push for δ=0\delta = 0δ=0).

The parser. parseScript(s)\mathrm{parseScript}(s)parseScript(s) runs a fuel-bounded loop (fuel =∣s∣= |s|=∣s∣) that repeatedly applies getOp\mathrm{getOp}getOp and collects the instructions: on the empty string it returns some [ ]\mathrm{some}\,[\,]some[]; if the fuel is exhausted on a non-empty string it returns none\mathrm{none}none; if getOp\mathrm{getOp}getOp fails it returns none\mathrm{none}none; otherwise it prepends the instruction and continues on the remainder. getOp(s)\mathrm{getOp}(s)getOp(s) on the empty string is none\mathrm{none}none; on c::rc :: rc::r with ccc read as a natural: if c≤0x4ec \le \mathtt{0x4e}c≤0x4e (=78=78=78) it is a push whose size is ccc itself when c<0x4cc < \mathtt{0x4c}c<0x4c; the next byte when c=0x4cc = \mathtt{0x4c}c=0x4c (none\mathrm{none}none if rrr is empty); the little-endian value of the next two bytes when c=0x4dc = \mathtt{0x4d}c=0x4d (none\mathrm{none}none if fewer than two); the little-endian value of the next four bytes when c=0x4ec = \mathtt{0x4e}c=0x4e (none\mathrm{none}none if fewer than four); then, with the size bytes consumed, if fewer than that many bytes remain the result is none\mathrm{none}none, else the instruction is the push of exactly that many bytes and the remainder follows. If c>0x4ec > \mathtt{0x4e}c>0x4e the instruction is the opcode ccc with remainder rrr (any such byte, including 0x4f\mathtt{0x4f}0x4f and 0x51\mathtt{0x51}0x51–0x60\mathtt{0x60}0x60, is returned as an opcode instruction).

Hypotheses. The size bounds on RRR and DDD and the magnitude bound on δ\deltaδ are the only assumptions; nothing else about the contents of RRR, DDD is assumed, and δ\deltaδ may be negative or zero.

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