BIP34 height pushes are prefix-free
ProvedBitcoinUniqueness.heightScript_prefixFor heights : if CScript() << a is a prefix of CScript() << b then . The single-byte forms (OP_0, OP_1..OP_16) never prefix a data push and vice versa, and data pushes are prefix-free with CScriptNum::serialize injective.
import Definitions.Def_BitcoinUniqueness open BitcoinUniqueness BitcoinSer BitcoinBlockV2
theorem BitcoinUniqueness.heightScript_prefix (a b : Nat) (ha : a < 2 ^ 31) (hb : b < 2 ^ 31)
(h : (BitcoinBlockV2.heightScript a).isPrefixOf (BitcoinBlockV2.heightScript b) = true) : a = b := by sorryRead-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: BitcoinUniqueness.heightScript_prefix
Statement. For all natural numbers and such that
- and
- ,
if the byte string is a prefix (initial segment, possibly the whole string) of the byte string , then .
Formally:
where means for some byte string (the Boolean prefix test returning true).
What heightScript says
For a natural number , is the byte string
where, for (so is positive and takes its non-negative branch): is the little-endian base-256 digit string of with no trailing zero byte (the "magnitude"), followed by an extra byte if and only if the top bit () of the magnitude's last byte is set; and , for a byte string , is (one length byte then the data) when , is when , is when , and is otherwise. For the magnitude has between 1 and 4 bytes, so has between 1 and 5 bytes and is one length byte (value 1 to 5) followed by those bytes.
Edge cases and scope
- : , a one-byte string; the claim then says no below has a height script beginning with the byte .
- : a single byte ; for the first byte is a length byte between and .
- The prefix relation is reflexive, so trivially satisfies the hypothesis; the content is the converse direction only.
- The bounds are hypotheses restricting the claim's scope; itself is defined for every natural number, and within the bounds the data pushed is at most 5 bytes, so only the first branch of (one length byte followed by the data) is exercised. The theorem says nothing about or .
- Nothing about blocks, chain states, or validation appears in this statement; it is a statement about two byte strings computed from two natural numbers.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.