What the Lean code literally says, in plain math · claude-fable-5-1 (independent sub-agent, blind: Lean code + auditor instructions only)
Read-back: BitcoinScriptV2.annotate_parse
Statement. For every byte string s,
mapL↦π1(L)(annotate(s))=parseScript(s),
where for a list L=[(i1,r1),…,(in,rn)] of pairs, π1(L)=[i1,…,in] is the list of first components. Spelled out, this is the conjunction of:
- annotate(s)=none if and only if parseScript(s)=none;
- whenever annotate(s)=some(L), parseScript(s)=some(π1(L)), i.e. the annotated parse and the plain parse produce the same instructions in the same order.
There are no hypotheses; it is asserted for every s, including s=ε (both sides some([])) and malformed scripts (both sides none).
Unfolded definitions used above
Basic objects and notation
- A byte is an 8-bit word, identified with its value in {0,…,255} and written in hexadecimal (e.g. 0xab). B∗ is the set of finite byte strings (lists of bytes); ∣x∣ is the length, x++y concatenation, ε the empty string.
- takek(x) is the first min(k,∣x∣) entries of a list x; dropk(x) is what is left after removing the first k entries, which is the empty list when k≥∣x∣.
- For a 0-based index p, the statement "x[p]=c" means: p<∣x∣ and the entry of x at index p is c. Indexing out of range yields no value, so such an equation can only hold with p<∣x∣.
- A partial result is either none or some(y). Applying a function g "under some" (mapg) sends none↦none and some(y)↦some(g(y)).
- An instruction is either push(d), carrying a data string d∈B∗, or op(c), carrying an opcode byte c. A script (parsed) is a finite list of instructions.
- Opcode bytes named below: OP_16=0x60, OP_IF=0x63, OP_ENDIF=0x68, OP_CODESEPARATOR=0xab, OP_CHECKSIG=0xac, OP_CHECKSIGVERIFY=0xad, OP_CHECKMULTISIG=0xae, OP_CHECKMULTISIGVERIFY=0xaf.
- A signature version v is one of exactly two values: base (legacy) or witnessV0.
Reading one instruction from bytes: getOp
getOp(x) returns either none or some(i,y) with i an instruction and y the remaining bytes:
- x=ε: none.
- Otherwise let b be the first byte and y0 the rest.
- If b≤0x4e (a push opcode), a data length n and a position are determined: if b<0x4c, n=b and the data starts right after b; if b=0x4c, n is the next byte (none if there is none); if b=0x4d, n is the little-endian value of the next 2 bytes (none if fewer than 2 remain); if b=0x4e, n is the little-endian value of the next 4 bytes (none if fewer than 4 remain). Then, if fewer than n bytes remain, none; otherwise some(push(next n bytes), the bytes after them). (So b=0x00 gives push(ε).)
- If b>0x4e: some(op(b),y0).
On success the remainder is a suffix of x that is at least one byte shorter than x. getOp never returns op(c) with c≤0x4e.
The annotated parse: annotate
annotate(s)=annotateAux(∣s∣,s), where, with a fuel counter n:
- annotateAux(n,ε)=some([]) for every n;
- annotateAux(0,x)=none for x=ε;
- annotateAux(n+1,x) for x=ε: if getOp(x)=none then none; if getOp(x)=some(i,r) then, if annotateAux(n,r)=none the result is none, and if it is some(L) the result is some([(i,r)]++L).
So on success annotate(s)=some([(i1,r1),…,(in,rn)]), where i1 is read from s leaving r1, ij+1 is read from rj leaving rj+1, and rn=ε: each instruction is paired with the bytes that follow it in s. annotate(ε)=some([]). Since every successful getOp consumes at least one byte, the fuel ∣s∣ never runs out while input remains; hence annotate(s)=none exactly when getOp fails at some instruction boundary, i.e. on a malformed push (a truncated length field, or fewer data bytes than announced).
The plain parse: parseScript
parseScript(s)=parseScriptAux(∣s∣,s) follows exactly the same recursion as annotateAux (empty input gives some([]); fuel 0 on non-empty input gives none; a failing getOp gives none), but on success records only the instructions: some([i1,…,in]).
Confirmed by the moderator at approval.