Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Serialization (CompactSize, transactions, headers, blocks), SHA-256d, Hash160, weights, and the genesis block

Definition
BitcoinSer

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

bitcoinbitcoin-mainnetconsensusformal-verificationgenesismerkleserializationsha256

Integers. leBytes(k,n)\mathrm{leBytes}(k, n)leBytes(k,n) is the kkk-byte little-endian encoding of nnn modulo 28k2^{8k}28k; leVal\mathrm{leVal}leVal reads a byte list little-endian; readLE(k)\mathrm{readLE}(k)readLE(k) consumes kkk bytes (none if fewer remain). ser8/16/32/64 are the fixed-width writers; signed 64/32-bit values are written two's-complement and read back with the sign restored. MAX_SIZE=225\mathrm{MAX\_SIZE} = 2^{25}MAX_SIZE=225.

CompactSize. writeCompactSize\mathrm{writeCompactSize}writeCompactSize is WriteCompactSize: one byte below 253253253, else a marker 253/254/255253/254/255253/254/255 followed by 2/4/82/4/82/4/8 little-endian bytes. readCompactSize(rangeCheck)\mathrm{readCompactSize}(\text{rangeCheck})readCompactSize(rangeCheck) is ReadCompactSize: none on a short read, on a non-canonical encoding (a 222-byte value below 253253253, a 444-byte value below 2162^{16}216, an 888-byte value below 2322^{32}232), or, when range-checked, on a value above MAX_SIZE\mathrm{MAX\_SIZE}MAX_SIZE.

Vectors and byte strings. A vector is its CompactSize length followed by its elements; a byte string (CScript, witness element) is its length then its bytes; uint256 is 32 raw bytes. Readers use the range-checked CompactSize, as the source's vector reader does.

Transactions. OutPoint (32-byte hash, n), TxIn (prevout, scriptSig, nSequence, witness stack), TxOut (nValue : Int, scriptPubKey), Tx (version, vin, vout, nLockTime). serTx(allowWitness)\mathrm{serTx}(\text{allowWitness})serTx(allowWitness) is SerializeTransaction: the basic format version vin vout nLockTime, or, when witnesses are allowed and present (hasWitness), the BIP144 extended format with the dummy empty vin and flag byte 111 before the real vin, and one witness stack per input before nLockTime. readTx(allowWitness)\mathrm{readTx}(\text{allowWitness})readTx(allowWitness) is UnserializeTransaction with its exact control flow: an empty vin with witnesses allowed is reinterpreted as the dummy, a flag byte is read, flag bit 111 reads the witnesses and rejects an all-empty witness record, any remaining flag bit rejects. stripWitness\mathrm{stripWitness}stripWitness clears every witness stack.

Headers and blocks. Header is the 80-byte CBlockHeader (int32 nVersion, two 32-byte hashes, nTime, nBits, nNonce); Block is a header and a transaction vector; serBlock/readBlock take the same witness flag. The wf predicates state the field ranges under which serialization is faithful: 32-bit fields below 2322^{32}232, hashes of 32 bytes, amounts in [−263,263)[-2^{63}, 2^{63})[−263,263), lengths at most MAX_SIZE\mathrm{MAX\_SIZE}MAX_SIZE, and for a block every transaction has an input or a witness.

Hashes. sha256\mathrm{sha256}sha256, ripemd160\mathrm{ripemd160}ripemd160 and sha1\mathrm{sha1}sha1 are the full compression-function algorithms of crypto/ (Merkle–Damgård padding, 64-byte chunks, 32-bit word arithmetic); hash256=sha256∘sha256\mathrm{hash256} = \mathrm{sha256} \circ \mathrm{sha256}hash256=sha256∘sha256 is Hash, hash160=ripemd160∘sha256\mathrm{hash160} = \mathrm{ripemd160} \circ \mathrm{sha256}hash160=ripemd160∘sha256 is Hash160; txid is hash256 of the witness-stripped serialization, wtxid of the full one (equal to txid without witness), headerHash is CBlockHeader::GetHash.

Weights and genesis. txWeight/blockWeight are GetTransactionWeight/GetBlockWeight (3⋅∣stripped∣+∣full∣3 \cdot |\text{stripped}| + |\text{full}|3⋅∣stripped∣+∣full∣); MAX_BLOCK_WEIGHT =4,000,000= 4{,}000{,}000=4,000,000. genesisCoinbase, genesisHeader, genesisBlock transcribe CreateGenesisBlock(1231006505, 2083236893, 0x1d00ffff, 1, 50 COIN) with the literal scriptSig and output script; genesisHash and genesisMerkleRoot are the hashes recorded in chainparams.cpp in serialized byte order.

Formalization Note. Byte lists and natural numbers replace streams and fixed-width C++ types; truncation modulo 28k2^{8k}28k models the writers on out-of-range values, which the wf predicates exclude. Only Std is imported.

Definition code
import Std

namespace BitcoinSer

/-! Transcription of Bitcoin Core's serialization and hashing at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: `serialize.h` (little-endian integers,
`WriteCompactSize`/`ReadCompactSize`, vectors), `primitives/transaction.h`
(`SerializeTransaction`/`UnserializeTransaction`, BIP144 extended format), `primitives/block.h`
(`CBlockHeader`, `CBlock`), `hash.h` (SHA-256d, Hash160), `crypto/sha256.cpp`,
`crypto/ripemd160.cpp`, `crypto/sha1.cpp`, `consensus/validation.h` (weights), and the mainnet
genesis block of `kernel/chainparams.cpp`. Readers return `none` where the source throws. -/

abbrev Byte := BitVec 8
abbrev Bytes := List Byte

/-- `serialize.h`: `MAX_SIZE = 0x02000000`, the bound `ReadCompactSize` enforces by default. -/
def MAX_SIZE : Nat := 0x02000000

/-! ### Little-endian fixed-width integers -/

/-- `k` little-endian bytes of `n` (truncated modulo `2^(8k)`). -/
def leBytes : Nat → Nat → Bytes
  | 0, _ => []
  | k + 1, n => BitVec.ofNat 8 (n % 256) :: leBytes k (n / 256)

/-- The little-endian value of a byte list. -/
def leVal : Bytes → Nat
  | [] => 0
  | b :: rest => b.toNat + 256 * leVal rest

/-- Read `k` bytes as a little-endian number. -/
def readLE (k : Nat) (s : Bytes) : Option (Nat × Bytes) :=
  if s.length < k then none else some (leVal (s.take k), s.drop k)

/-- `k` big-endian bytes of `n`. -/
def beBytes (k n : Nat) : Bytes := (leBytes k n).reverse

/-- `ser_writedata8/16/32/64`. -/
def ser8 (n : Nat) : Bytes := leBytes 1 n
def ser16 (n : Nat) : Bytes := leBytes 2 n
def ser32 (n : Nat) : Bytes := leBytes 4 n
def ser64 (n : Nat) : Bytes := leBytes 8 n

/-- Signed 64-bit (`CAmount`) as two's complement little-endian. -/
def serInt64 (n : Int) : Bytes := leBytes 8 (n % 2 ^ 64).toNat
/-- Signed 32-bit (`int32_t nVersion`). -/
def serInt32 (n : Int) : Bytes := leBytes 4 (n % 2 ^ 32).toNat

def readInt64 (s : Bytes) : Option (Int × Bytes) :=
  (readLE 8 s).map fun (v, r) => (if v < 2 ^ 63 then (v : Int) else (v : Int) - 2 ^ 64, r)
def readInt32 (s : Bytes) : Option (Int × Bytes) :=
  (readLE 4 s).map fun (v, r) => (if v < 2 ^ 31 then (v : Int) else (v : Int) - 2 ^ 32, r)

/-! ### CompactSize -/

/-- `WriteCompactSize`. -/
def writeCompactSize (n : Nat) : Bytes :=
  if n < 253 then ser8 n
  else if n ≤ 0xffff then ser8 253 ++ ser16 n
  else if n ≤ 0xffffffff then ser8 254 ++ ser32 n
  else ser8 255 ++ ser64 n

/-- `ReadCompactSize(is, range_check)`: `none` on a short read, a non-canonical encoding, or
(with `rangeCheck`) a value above `MAX_SIZE`. -/
def readCompactSize (rangeCheck : Bool) (s : Bytes) : Option (Nat × Bytes) :=
  match s with
  | [] => none
  | ch :: rest =>
    let r : Option (Nat × Bytes) :=
      if ch.toNat < 253 then some (ch.toNat, rest)
      else if ch.toNat = 253 then
        match readLE 2 rest with
        | some (v, r) => if v < 253 then none else some (v, r)
        | none => none
      else if ch.toNat = 254 then
        match readLE 4 rest with
        | some (v, r) => if v < 0x10000 then none else some (v, r)
        | none => none
      else
        match readLE 8 rest with
        | some (v, r) => if v < 0x100000000 then none else some (v, r)
        | none => none
    match r with
    | some (v, r) => if rangeCheck && decide (MAX_SIZE < v) then none else some (v, r)
    | none => none

/-! ### Vectors and byte strings -/

/-- `Serialize(vector<T>)`: `WriteCompactSize(size)` then the elements. -/
def serList {α : Type} (f : α → Bytes) (l : List α) : Bytes :=
  writeCompactSize l.length ++ l.flatMap f

/-- Read exactly `n` elements with `f`. -/
def readN {α : Type} (f : Bytes → Option (α × Bytes)) : Nat → Bytes → Option (List α × Bytes)
  | 0, s => some ([], s)
  | n + 1, s =>
    match f s with
    | none => none
    | some (x, s') =>
      match readN f n s' with
      | none => none
      | some (xs, s'') => some (x :: xs, s'')

/-- `Unserialize(vector<T>)`: a range-checked `ReadCompactSize`, then that many elements. -/
def readList {α : Type} (f : Bytes → Option (α × Bytes)) (s : Bytes) : Option (List α × Bytes) :=
  match readCompactSize true s with
  | none => none
  | some (n, s') => readN f n s'

/-- A byte vector (`CScript`, a witness stack element, `prevector`): length then raw bytes. -/
def serBytes (b : Bytes) : Bytes := writeCompactSize b.length ++ b

def readBytes (s : Bytes) : Option (Bytes × Bytes) :=
  match readCompactSize true s with
  | none => none
  | some (n, s') => if s'.length < n then none else some (s'.take n, s'.drop n)

/-- `uint256`: 32 raw bytes. -/
def readHash (s : Bytes) : Option (Bytes × Bytes) :=
  if s.length < 32 then none else some (s.take 32, s.drop 32)

/-! ### Transactions (`primitives/transaction.h`) -/

/-- `COutPoint { uint256 hash; uint32_t n; }`. -/
structure OutPoint where
  hash : Bytes
  n : Nat
  deriving DecidableEq, Repr

/-- `CTxIn`; `witness` is `scriptWitness.stack`, serialized only through the transaction. -/
structure TxIn where
  prevout : OutPoint
  scriptSig : Bytes
  nSequence : Nat
  witness : List Bytes
  deriving DecidableEq, Repr

/-- `CTxOut { CAmount nValue; CScript scriptPubKey; }`. -/
structure TxOut where
  nValue : Int
  scriptPubKey : Bytes
  deriving DecidableEq, Repr

/-- `CTransaction` data: `uint32_t version`, `vin`, `vout`, `uint32_t nLockTime`. -/
structure Tx where
  version : Nat
  vin : List TxIn
  vout : List TxOut
  nLockTime : Nat
  deriving DecidableEq, Repr

/-- `CTransaction::HasWitness`: some input has a non-empty witness stack. -/
def Tx.hasWitness (tx : Tx) : Bool := tx.vin.any fun i => !i.witness.isEmpty

/-- The transaction with every witness stack cleared (what `TX_NO_WITNESS` reading yields). -/
def Tx.stripWitness (tx : Tx) : Tx :=
  { tx with vin := tx.vin.map fun i => { i with witness := [] } }

def serOutPoint (o : OutPoint) : Bytes := o.hash ++ ser32 o.n
def serTxIn (i : TxIn) : Bytes := serOutPoint i.prevout ++ serBytes i.scriptSig ++ ser32 i.nSequence
def serTxOut (o : TxOut) : Bytes := serInt64 o.nValue ++ serBytes o.scriptPubKey

/-- `SerializeTransaction(tx, s, params)` with `params.allow_witness = allowWitness`. -/
def serTx (allowWitness : Bool) (tx : Tx) : Bytes :=
  let flags : Nat := if allowWitness && tx.hasWitness then 1 else 0
  ser32 tx.version ++
  (if flags ≠ 0 then writeCompactSize 0 ++ ser8 flags else []) ++
  serList serTxIn tx.vin ++ serList serTxOut tx.vout ++
  (if flags ≠ 0 then tx.vin.flatMap (fun i => serList serBytes i.witness) else []) ++
  ser32 tx.nLockTime

def readOutPoint (s : Bytes) : Option (OutPoint × Bytes) :=
  match readHash s with
  | none => none
  | some (h, s) =>
    match readLE 4 s with
    | none => none
    | some (n, s) => some (⟨h, n⟩, s)

def readTxIn (s : Bytes) : Option (TxIn × Bytes) :=
  match readOutPoint s with
  | none => none
  | some (p, s) =>
    match readBytes s with
    | none => none
    | some (sig, s) =>
      match readLE 4 s with
      | none => none
      | some (q, s) => some (⟨p, sig, q, []⟩, s)

def readTxOut (s : Bytes) : Option (TxOut × Bytes) :=
  match readInt64 s with
  | none => none
  | some (v, s) =>
    match readBytes s with
    | none => none
    | some (spk, s) => some (⟨v, spk⟩, s)

/-- Attach witness stacks to inputs, in order. -/
def attachWitness : List TxIn → List (List Bytes) → List TxIn
  | i :: is, w :: ws => { i with witness := w } :: attachWitness is ws
  | is, _ => is

/-- Read one witness stack per input. -/
def readWitnesses : Nat → Bytes → Option (List (List Bytes) × Bytes) :=
  readN (readList readBytes)

/-- `UnserializeTransaction(tx, s, params)` with `params.allow_witness = allowWitness`. -/
def readTx (allowWitness : Bool) (s : Bytes) : Option (Tx × Bytes) :=
  match readLE 4 s with
  | none => none
  | some (version, s) =>
    match readList readTxIn s with
    | none => none
    | some (vin0, s) =>
      -- `if (tx.vin.size() == 0 && fAllowWitness)`: read the flags byte and, if non-zero, vin/vout
      let step2 : Option (Nat × List TxIn × List TxOut × Bytes) :=
        if vin0.isEmpty && allowWitness then
          match s with
          | [] => none
          | fl :: s =>
            if fl.toNat ≠ 0 then
              match readList readTxIn s with
              | none => none
              | some (vin, s) =>
                match readList readTxOut s with
                | none => none
                | some (vout, s) => some (fl.toNat, vin, vout, s)
            else some (0, vin0, [], s)
        else
          match readList readTxOut s with
          | none => none
          | some (vout, s) => some (0, vin0, vout, s)
      match step2 with
      | none => none
      | some (flags, vin, vout, s) =>
        let step3 : Option (Nat × List TxIn × Bytes) :=
          if flags % 2 = 1 && allowWitness then
            match readWitnesses vin.length s with
            | none => none
            | some (ws, s) =>
              let vin' := attachWitness vin ws
              -- "Superfluous witness record"
              if (Tx.hasWitness ⟨0, vin', [], 0⟩) then some (flags - 1, vin', s) else none
          else some (flags, vin, s)
        match step3 with
        | none => none
        | some (flags, vin, s) =>
          -- "Unknown transaction optional data"
          if flags ≠ 0 then none
          else
            match readLE 4 s with
            | none => none
            | some (lock, s) => some (⟨version, vin, vout, lock⟩, s)

/-! ### Headers and blocks (`primitives/block.h`) -/

/-- `CBlockHeader`: `int32_t nVersion`, `uint256 hashPrevBlock`, `uint256 hashMerkleRoot`,
`uint32_t nTime`, `uint32_t nBits`, `uint32_t nNonce`. -/
structure Header where
  version : Int
  prevBlock : Bytes
  merkleRoot : Bytes
  time : Nat
  bits : Nat
  nonce : Nat
  deriving DecidableEq, Repr

def serHeader (h : Header) : Bytes :=
  serInt32 h.version ++ h.prevBlock ++ h.merkleRoot ++ ser32 h.time ++ ser32 h.bits ++ ser32 h.nonce

def readHeader (s : Bytes) : Option (Header × Bytes) :=
  match readInt32 s with
  | none => none
  | some (v, s) =>
    match readHash s with
    | none => none
    | some (p, s) =>
      match readHash s with
      | none => none
      | some (m, s) =>
        match readLE 4 s with
        | none => none
        | some (t, s) =>
          match readLE 4 s with
          | none => none
          | some (b, s) =>
            match readLE 4 s with
            | none => none
            | some (n, s) => some (⟨v, p, m, t, b, n⟩, s)

/-- `CBlock`: the header followed by `vtx`. -/
structure Block where
  header : Header
  vtx : List Tx
  deriving DecidableEq, Repr

def serBlock (allowWitness : Bool) (b : Block) : Bytes :=
  serHeader b.header ++ serList (serTx allowWitness) b.vtx

def readBlock (allowWitness : Bool) (s : Bytes) : Option (Block × Bytes) :=
  match readHeader s with
  | none => none
  | some (h, s) =>
    match readList (readTx allowWitness) s with
    | none => none
    | some (vtx, s) => some (⟨h, vtx⟩, s)

/-! ### Well-formedness: the field ranges under which serialization is faithful -/

def OutPoint.wf (o : OutPoint) : Prop := o.hash.length = 32 ∧ o.n < 2 ^ 32
def TxIn.wf (i : TxIn) : Prop :=
  i.prevout.wf ∧ i.scriptSig.length ≤ MAX_SIZE ∧ i.nSequence < 2 ^ 32 ∧
  i.witness.length ≤ MAX_SIZE ∧ ∀ w ∈ i.witness, w.length ≤ MAX_SIZE
def TxOut.wf (o : TxOut) : Prop :=
  -(2 ^ 63) ≤ o.nValue ∧ o.nValue < 2 ^ 63 ∧ o.scriptPubKey.length ≤ MAX_SIZE
def Tx.wf (tx : Tx) : Prop :=
  tx.version < 2 ^ 32 ∧ tx.nLockTime < 2 ^ 32 ∧ tx.vin.length ≤ MAX_SIZE ∧ tx.vout.length ≤ MAX_SIZE ∧
  (∀ i ∈ tx.vin, i.wf) ∧ (∀ o ∈ tx.vout, o.wf)
def Header.wf (h : Header) : Prop :=
  -(2 ^ 31) ≤ h.version ∧ h.version < 2 ^ 31 ∧ h.prevBlock.length = 32 ∧ h.merkleRoot.length = 32 ∧
  h.time < 2 ^ 32 ∧ h.bits < 2 ^ 32 ∧ h.nonce < 2 ^ 32
def Block.wf (b : Block) : Prop :=
  b.header.wf ∧ b.vtx.length ≤ MAX_SIZE ∧ ∀ tx ∈ b.vtx, tx.wf ∧ (tx.vin ≠ [] ∨ tx.hasWitness = true)

/-! ### SHA-256 (`crypto/sha256.cpp`, generic `Transform`) -/

def rotr (x : UInt32) (n : UInt32) : UInt32 := (x >>> n) ||| (x <<< (32 - n))
def Ch (x y z : UInt32) : UInt32 := z ^^^ (x &&& (y ^^^ z))
def Maj (x y z : UInt32) : UInt32 := (x &&& y) ||| (z &&& (x ||| y))
def Sigma0 (x : UInt32) : UInt32 := rotr x 2 ^^^ rotr x 13 ^^^ rotr x 22
def Sigma1 (x : UInt32) : UInt32 := rotr x 6 ^^^ rotr x 11 ^^^ rotr x 25
def sigma0 (x : UInt32) : UInt32 := rotr x 7 ^^^ rotr x 18 ^^^ (x >>> 3)
def sigma1 (x : UInt32) : UInt32 := rotr x 17 ^^^ rotr x 19 ^^^ (x >>> 10)

def sha256K : List UInt32 := [1116352408, 1899447441, 3049323471, 3921009573, 961987163, 1508970993, 2453635748, 2870763221, 3624381080, 310598401, 607225278, 1426881987, 1925078388, 2162078206, 2614888103, 3248222580, 3835390401, 4022224774, 264347078, 604807628, 770255983, 1249150122, 1555081692, 1996064986, 2554220882, 2821834349, 2952996808, 3210313671, 3336571891, 3584528711, 113926993, 338241895, 666307205, 773529912, 1294757372, 1396182291, 1695183700, 1986661051, 2177026350, 2456956037, 2730485921, 2820302411, 3259730800, 3345764771, 3516065817, 3600352804, 4094571909, 275423344, 430227734, 506948616, 659060556, 883997877, 958139571, 1322822218, 1537002063, 1747873779, 1955562222, 2024104815, 2227730452, 2361852424, 2428436474, 2756734187, 3204031479, 3329325298]

structure Sha256State where
  a : UInt32
  b : UInt32
  c : UInt32
  d : UInt32
  e : UInt32
  f : UInt32
  g : UInt32
  h : UInt32

def sha256Init : Sha256State :=
  ⟨0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19⟩

/-- One round: `t1 = h + Σ1(e) + Ch(e,f,g) + k + w`, `t2 = Σ0(a) + Maj(a,b,c)`. -/
def sha256Round (s : Sha256State) (kw : UInt32) : Sha256State :=
  let t1 := s.h + Sigma1 s.e + Ch s.e s.f s.g + kw
  let t2 := Sigma0 s.a + Maj s.a s.b s.c
  ⟨t1 + t2, s.a, s.b, s.c, s.d + t1, s.e, s.f, s.g⟩

/-- Big-endian 32-bit words of a byte list (4 bytes each). -/
def be32Words : Bytes → List UInt32
  | b0 :: b1 :: b2 :: b3 :: rest =>
    UInt32.ofNat (b0.toNat * 2 ^ 24 + b1.toNat * 2 ^ 16 + b2.toNat * 2 ^ 8 + b3.toNat) :: be32Words rest
  | _ => []

/-- Message schedule: `w[t] = σ1(w[t-2]) + w[t-7] + σ0(w[t-15]) + w[t-16]` for `16 ≤ t < 64`. -/
def sha256Schedule (w : List UInt32) : List UInt32 :=
  let rec go (w : List UInt32) : Nat → List UInt32
    | 0 => w
    | n + 1 =>
      let t := w.length
      let nw := sigma1 (w.getD (t - 2) 0) + w.getD (t - 7) 0 + sigma0 (w.getD (t - 15) 0) + w.getD (t - 16) 0
      go (w ++ [nw]) n
  go w 48

def sha256Compress (s : Sha256State) (chunk : Bytes) : Sha256State :=
  let w := sha256Schedule (be32Words chunk)
  let r := (sha256K.zipWith (· + ·) w).foldl sha256Round s
  ⟨s.a + r.a, s.b + r.b, s.c + r.c, s.d + r.d, s.e + r.e, s.f + r.f, s.g + r.g, s.h + r.h⟩

/-- Split into 64-byte chunks (the input length is a multiple of 64); `fuel` bounds the recursion. -/
def chunks64Aux : Nat → Bytes → List Bytes
  | 0, _ => []
  | fuel + 1, s => if s.length < 64 then [] else s.take 64 :: chunks64Aux fuel (s.drop 64)

def chunks64 (s : Bytes) : List Bytes := chunks64Aux (s.length / 64) s

/-- MD padding: `0x80`, zeros to 56 mod 64, then the bit length as 8 bytes (big-endian for
SHA-256/SHA-1, little-endian for RIPEMD-160). -/
def mdPad (bigEndianLen : Bool) (msg : Bytes) : Bytes :=
  let zeros := (119 - msg.length % 64) % 64
  msg ++ [0x80] ++ List.replicate zeros 0 ++
    (if bigEndianLen then beBytes 8 (msg.length * 8) else leBytes 8 (msg.length * 8))

def be32Bytes (x : UInt32) : Bytes := beBytes 4 x.toNat
def le32Bytes (x : UInt32) : Bytes := leBytes 4 x.toNat

/-- `CSHA256().Write(msg).Finalize()`. -/
def sha256 (msg : Bytes) : Bytes :=
  let s := (chunks64 (mdPad true msg)).foldl sha256Compress sha256Init
  be32Bytes s.a ++ be32Bytes s.b ++ be32Bytes s.c ++ be32Bytes s.d ++
  be32Bytes s.e ++ be32Bytes s.f ++ be32Bytes s.g ++ be32Bytes s.h

/-! ### RIPEMD-160 (`crypto/ripemd160.cpp`) -/

def rol (x : UInt32) (n : UInt32) : UInt32 := (x <<< n) ||| (x >>> (32 - n))
def rf1 (x y z : UInt32) : UInt32 := x ^^^ y ^^^ z
def rf2 (x y z : UInt32) : UInt32 := (x &&& y) ||| (~~~x &&& z)
def rf3 (x y z : UInt32) : UInt32 := (x ||| ~~~y) ^^^ z
def rf4 (x y z : UInt32) : UInt32 := (x &&& z) ||| (y &&& ~~~z)
def rf5 (x y z : UInt32) : UInt32 := x ^^^ (y ||| ~~~z)

/-- Little-endian 32-bit words of a byte list. -/
def le32Words : Bytes → List UInt32
  | b0 :: b1 :: b2 :: b3 :: rest =>
    UInt32.ofNat (b0.toNat + b1.toNat * 2 ^ 8 + b2.toNat * 2 ^ 16 + b3.toNat * 2 ^ 24) :: le32Words rest
  | _ => []

/-- Message-word selection and rotation amounts of the left and right lines. -/
def ripemdRL : List Nat := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 7, 4, 13, 1, 10, 6, 15, 3, 12, 0, 9, 5, 2, 14, 11, 8, 3, 10, 14, 4, 9, 15, 8, 1, 2, 7, 0, 6, 13, 11, 5, 12, 1, 9, 11, 10, 0, 8, 12, 4, 13, 3, 7, 15, 14, 5, 6, 2, 4, 0, 5, 9, 7, 12, 2, 10, 14, 1, 3, 8, 11, 6, 15, 13]
def ripemdRR : List Nat := [5, 14, 7, 0, 9, 2, 11, 4, 13, 6, 15, 8, 1, 10, 3, 12, 6, 11, 3, 7, 0, 13, 5, 10, 14, 15, 8, 12, 4, 9, 1, 2, 15, 5, 1, 3, 7, 14, 6, 9, 11, 8, 12, 2, 10, 0, 4, 13, 8, 6, 4, 1, 3, 11, 15, 0, 5, 12, 2, 13, 9, 7, 10, 14, 12, 15, 10, 4, 1, 5, 8, 7, 6, 2, 13, 14, 0, 3, 9, 11]
def ripemdSL : List Nat := [11, 14, 15, 12, 5, 8, 7, 9, 11, 13, 14, 15, 6, 7, 9, 8, 7, 6, 8, 13, 11, 9, 7, 15, 7, 12, 15, 9, 11, 7, 13, 12, 11, 13, 6, 7, 14, 9, 13, 15, 14, 8, 13, 6, 5, 12, 7, 5, 11, 12, 14, 15, 14, 15, 9, 8, 9, 14, 5, 6, 8, 6, 5, 12, 9, 15, 5, 11, 6, 8, 13, 12, 5, 12, 13, 14, 11, 8, 5, 6]
def ripemdSR : List Nat := [8, 9, 9, 11, 13, 15, 15, 5, 7, 7, 8, 11, 14, 14, 12, 6, 9, 13, 15, 7, 12, 8, 9, 11, 7, 7, 12, 7, 6, 15, 13, 11, 9, 7, 15, 11, 8, 6, 6, 14, 12, 13, 5, 14, 13, 13, 7, 5, 15, 5, 8, 11, 14, 14, 6, 14, 6, 9, 12, 9, 12, 5, 15, 8, 8, 5, 12, 9, 12, 5, 14, 6, 8, 13, 6, 5, 15, 13, 11, 11]

structure R5 where
  a : UInt32
  b : UInt32
  c : UInt32
  d : UInt32
  e : UInt32

def ripemdInit : R5 := ⟨0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0⟩

/-- Left line: `f1..f5` with constants `0, 5A827999, 6ED9EBA1, 8F1BBCDC, A953FD4E`. -/
def ripemdFL (j : Nat) (x y z : UInt32) : UInt32 :=
  if j < 16 then rf1 x y z else if j < 32 then rf2 x y z else if j < 48 then rf3 x y z
  else if j < 64 then rf4 x y z else rf5 x y z
def ripemdKL (j : Nat) : UInt32 :=
  if j < 16 then 0 else if j < 32 then 0x5A827999 else if j < 48 then 0x6ED9EBA1
  else if j < 64 then 0x8F1BBCDC else 0xA953FD4E
/-- Right line: `f5..f1` with constants `50A28BE6, 5C4DD124, 6D703EF3, 7A6D76E9, 0`. -/
def ripemdFR (j : Nat) (x y z : UInt32) : UInt32 :=
  if j < 16 then rf5 x y z else if j < 32 then rf4 x y z else if j < 48 then rf3 x y z
  else if j < 64 then rf2 x y z else rf1 x y z
def ripemdKR (j : Nat) : UInt32 :=
  if j < 16 then 0x50A28BE6 else if j < 32 then 0x5C4DD124 else if j < 48 then 0x6D703EF3
  else if j < 64 then 0x7A6D76E9 else 0

/-- `Round`: `a = rol(a + f + x + k, r) + e; c = rol(c, 10)`, then the register rotation. -/
def ripemdStep (s : R5) (f : UInt32) (x k : UInt32) (r : Nat) : R5 :=
  let a := rol (s.a + f + x + k) (UInt32.ofNat r) + s.e
  let c := rol s.c 10
  ⟨s.e, a, s.b, c, s.d⟩

def ripemdLine (w : List UInt32) (fsel : Nat → UInt32 → UInt32 → UInt32 → UInt32) (ksel : Nat → UInt32)
    (rsel ssel : List Nat) (s : R5) : R5 :=
  (List.range 80).foldl (fun s j =>
    ripemdStep s (fsel j s.b s.c s.d) (w.getD (rsel.getD j 0) 0) (ksel j) (ssel.getD j 0)) s

def ripemdCompress (s : R5) (chunk : Bytes) : R5 :=
  let w := le32Words chunk
  let l := ripemdLine w ripemdFL ripemdKL ripemdRL ripemdSL s
  let r := ripemdLine w ripemdFR ripemdKR ripemdRR ripemdSR s
  ⟨s.b + l.c + r.d, s.c + l.d + r.e, s.d + l.e + r.a, s.e + l.a + r.b, s.a + l.b + r.c⟩

/-- `CRIPEMD160().Write(msg).Finalize()`. -/
def ripemd160 (msg : Bytes) : Bytes :=
  let s := (chunks64 (mdPad false msg)).foldl ripemdCompress ripemdInit
  le32Bytes s.a ++ le32Bytes s.b ++ le32Bytes s.c ++ le32Bytes s.d ++ le32Bytes s.e

/-! ### SHA-1 (`crypto/sha1.cpp`) -/

def sha1F (t : Nat) (b c d : UInt32) : UInt32 :=
  if t < 20 then d ^^^ (b &&& (c ^^^ d)) else if t < 40 then b ^^^ c ^^^ d
  else if t < 60 then (b &&& c) ||| (d &&& (b ||| c)) else b ^^^ c ^^^ d
def sha1K (t : Nat) : UInt32 :=
  if t < 20 then 0x5A827999 else if t < 40 then 0x6ED9EBA1 else if t < 60 then 0x8F1BBCDC else 0xCA62C1D6

def sha1Schedule (w : List UInt32) : List UInt32 :=
  let rec go (w : List UInt32) : Nat → List UInt32
    | 0 => w
    | n + 1 =>
      let t := w.length
      let nw := rol (w.getD (t - 3) 0 ^^^ w.getD (t - 8) 0 ^^^ w.getD (t - 14) 0 ^^^ w.getD (t - 16) 0) 1
      go (w ++ [nw]) n
  go w 64

def sha1Compress (s : R5) (chunk : Bytes) : R5 :=
  let w := sha1Schedule (be32Words chunk)
  let r := (List.range 80).foldl (fun (s : R5) t =>
    let temp := rol s.a 5 + sha1F t s.b s.c s.d + s.e + sha1K t + w.getD t 0
    ⟨temp, s.a, rol s.b 30, s.c, s.d⟩) s
  ⟨s.a + r.a, s.b + r.b, s.c + r.c, s.d + r.d, s.e + r.e⟩

def sha1 (msg : Bytes) : Bytes :=
  let s := (chunks64 (mdPad true msg)).foldl sha1Compress ripemdInit
  be32Bytes s.a ++ be32Bytes s.b ++ be32Bytes s.c ++ be32Bytes s.d ++ be32Bytes s.e

/-! ### Hashes of Bitcoin objects (`hash.h`, `primitives`) -/

/-- `Hash(x)` = SHA-256d. -/
def hash256 (m : Bytes) : Bytes := sha256 (sha256 m)
/-- `Hash160(x)` = RIPEMD-160 ∘ SHA-256. -/
def hash160 (m : Bytes) : Bytes := ripemd160 (sha256 m)

/-- `CTransaction::ComputeHash`: SHA-256d of the witness-stripped serialization. -/
def txid (tx : Tx) : Bytes := hash256 (serTx false tx)
/-- `CTransaction::ComputeWitnessHash`: equals `txid` when there is no witness. -/
def wtxid (tx : Tx) : Bytes := if tx.hasWitness then hash256 (serTx true tx) else txid tx
/-- `CBlockHeader::GetHash`. -/
def headerHash (h : Header) : Bytes := hash256 (serHeader h)

/-! ### Weights (`consensus/consensus.h`, `consensus/validation.h`) -/

def WITNESS_SCALE_FACTOR : Nat := 4
def MAX_BLOCK_WEIGHT : Nat := 4000000
def MAX_BLOCK_SERIALIZED_SIZE : Nat := 4000000

/-- `GetTransactionWeight`: `|TX_NO_WITNESS| * 3 + |TX_WITH_WITNESS|`. -/
def txWeight (tx : Tx) : Nat := (serTx false tx).length * (WITNESS_SCALE_FACTOR - 1) + (serTx true tx).length
/-- `GetBlockWeight`. -/
def blockWeight (b : Block) : Nat :=
  (serBlock false b).length * (WITNESS_SCALE_FACTOR - 1) + (serBlock true b).length

/-! ### The mainnet genesis block (`kernel/chainparams.cpp`, `CreateGenesisBlock`) -/

/-- `CScript() << 486604799 << CScriptNum(4) << "The Times 03/Jan/2009 Chancellor on brink of
second bailout for banks"`. -/
def genesisScriptSig : Bytes := [0x04, 0xff, 0xff, 0x00, 0x1d, 0x01, 0x04, 0x45, 0x54, 0x68, 0x65, 0x20, 0x54, 0x69, 0x6d, 0x65, 0x73, 0x20, 0x30, 0x33, 0x2f, 0x4a, 0x61, 0x6e, 0x2f, 0x32, 0x30, 0x30, 0x39, 0x20, 0x43, 0x68, 0x61, 0x6e, 0x63, 0x65, 0x6c, 0x6c, 0x6f, 0x72, 0x20, 0x6f, 0x6e, 0x20, 0x62, 0x72, 0x69, 0x6e, 0x6b, 0x20, 0x6f, 0x66, 0x20, 0x73, 0x65, 0x63, 0x6f, 0x6e, 0x64, 0x20, 0x62, 0x61, 0x69, 0x6c, 0x6f, 0x75, 0x74, 0x20, 0x66, 0x6f, 0x72, 0x20, 0x62, 0x61, 0x6e, 0x6b, 0x73]

/-- `CScript() << 04678afd…11d5f << OP_CHECKSIG`. -/
def genesisOutputScript : Bytes := [0x41, 0x04, 0x67, 0x8a, 0xfd, 0xb0, 0xfe, 0x55, 0x48, 0x27, 0x19, 0x67, 0xf1, 0xa6, 0x71, 0x30, 0xb7, 0x10, 0x5c, 0xd6, 0xa8, 0x28, 0xe0, 0x39, 0x09, 0xa6, 0x79, 0x62, 0xe0, 0xea, 0x1f, 0x61, 0xde, 0xb6, 0x49, 0xf6, 0xbc, 0x3f, 0x4c, 0xef, 0x38, 0xc4, 0xf3, 0x55, 0x04, 0xe5, 0x1e, 0xc1, 0x12, 0xde, 0x5c, 0x38, 0x4d, 0xf7, 0xba, 0x0b, 0x8d, 0x57, 0x8a, 0x4c, 0x70, 0x2b, 0x6b, 0xf1, 0x1d, 0x5f, 0xac]

def genesisCoinbase : Tx :=
  ⟨1, [⟨⟨List.replicate 32 0, 0xffffffff⟩, genesisScriptSig, 0xffffffff, []⟩],
      [⟨5000000000, genesisOutputScript⟩], 0⟩

/-- `CreateGenesisBlock(1231006505, 2083236893, 0x1d00ffff, 1, 50 * COIN)`; the merkle root of a
single-transaction block is that transaction's txid. -/
def genesisHeader : Header :=
  ⟨1, List.replicate 32 0, txid genesisCoinbase, 1231006505, 0x1d00ffff, 2083236893⟩

def genesisBlock : Block := ⟨genesisHeader, [genesisCoinbase]⟩

/-- `consensus.hashGenesisBlock = 000000000019d6689c085ae165831e934ff763ae46a2a6c172b3f1b60a8ce26f`
(byte order as serialized, i.e. reversed display order). -/
def genesisHash : Bytes := [0x6f, 0xe2, 0x8c, 0x0a, 0xb6, 0xf1, 0xb3, 0x72, 0xc1, 0xa6, 0xa2, 0x46, 0xae, 0x63, 0xf7, 0x4f, 0x93, 0x1e, 0x83, 0x65, 0xe1, 0x5a, 0x08, 0x9c, 0x68, 0xd6, 0x19, 0x00, 0x00, 0x00, 0x00, 0x00]

/-- `genesis.hashMerkleRoot == 4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b`. -/
def genesisMerkleRoot : Bytes := [0x3b, 0xa3, 0xed, 0xfd, 0x7a, 0x7b, 0x12, 0xb2, 0x7a, 0xc7, 0x2c, 0x3e, 0x67, 0x76, 0x8f, 0x61, 0x7f, 0xc8, 0x1b, 0xc3, 0x88, 0x8a, 0x51, 0x32, 0x3a, 0x9f, 0xb8, 0xaa, 0x4b, 0x1e, 0x5e, 0x4a]

end BitcoinSer
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: WriteCompactSize/ReadCompactSize and vector serialization, src/serialize.h: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/serialize.h; SerializeTransaction/UnserializeTransaction, COutPoint, CTxIn, CTxOut, ComputeHash, ComputeWitnessHash, src/primitives/transaction.h and transaction.cpp; CBlockHeader, CBlock, GetHash, src/primitives/block.h and block.cpp; Hash, Hash160, src/hash.h; CSHA256, src/crypto/sha256.cpp; CRIPEMD160, src/crypto/ripemd160.cpp; CSHA1, src/crypto/sha1.cpp; GetTransactionWeight/GetBlockWeight, src/consensus/validation.h; WITNESS_SCALE_FACTOR, MAX_BLOCK_WEIGHT, src/consensus/consensus.h; CreateGenesisBlock and hashGenesisBlock, src/kernel/chainparams.cpp
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: Def_BitcoinSer

Scope. This file imports only the standard library and opens a single namespace. Everything below lives in that namespace. It introduces byte types, little-endian integer encoders and decoders, a variable-length integer ("CompactSize") encoder and decoder, list and byte-string encoders and decoders, record types for transactions, headers and blocks together with their serializers and deserializers, "well-formedness" predicates on those records, three hash functions (SHA-256, RIPEMD-160, SHA-1), composite hashes, weight functions, and a handful of concrete constants (a coinbase transaction, a header, a block, two 32-byte strings). Every decoder is a partial function, returning "no result" (written ⊥\bot⊥ below) instead of raising an error. I go through the declarations in file order.


Byte types and the size bound

Byte, Bytes. A byte is a bit-vector of width 8 (so an integer in [0,255][0, 255][0,255]); a byte string is a finite list of bytes. Lists may be empty. Throughout, ∣s∣|s|∣s∣ denotes the length of a list sss, s[:k]s[{:}k]s[:k] its first kkk elements (or all of sss if it has fewer), and s[k:]s[k{:}]s[k:] the remainder after dropping kkk elements (empty if sss has at most kkk).

MAX_SIZE. The natural number MAX_SIZE=0x02000000=33 554 432=225\texttt{MAX\_SIZE} = \mathrm{0x02000000} = 33\,554\,432 = 2^{25}MAX_SIZE=0x02000000=33554432=225.


Little-endian fixed-width integers

leBytes k n (k,n∈Nk, n \in \mathbb{N}k,n∈N). Defined by recursion on kkk: for k=0k = 0k=0 the result is the empty list; for k+1k+1k+1 it is the byte n mod 256n \bmod 256nmod256 followed by leBytes  k  ⌊n/256⌋\texttt{leBytes}\;k\;\lfloor n/256\rfloorleBytesk⌊n/256⌋. So the result always has exactly kkk bytes, the least-significant byte first, and it encodes n mod 28kn \bmod 2^{8k}nmod28k: any higher bits of nnn are silently discarded (truncation, not failure). For k=0k = 0k=0 every nnn gives the empty list.

leVal s. The little-endian value of a byte list: leVal([ ])=0\texttt{leVal}([\,]) = 0leVal([])=0 and leVal(b::r)=b+256⋅leVal(r)\texttt{leVal}(b :: r) = b + 256\cdot\texttt{leVal}(r)leVal(b::r)=b+256⋅leVal(r). The empty list has value 000; a list of kkk bytes has value in [0,28k)[0, 2^{8k})[0,28k).

readLE k s. If ∣s∣<k|s| < k∣s∣<k the result is ⊥\bot⊥; otherwise it is the pair (leVal(s[:k]), s[k:])(\texttt{leVal}(s[{:}k]),\, s[k{:}])(leVal(s[:k]),s[k:]). Note the boundary: exactly kkk bytes available is a success. For k=0k = 0k=0 the result is always (0,s)(0, s)(0,s), even on the empty string.

beBytes k n. The reversal of leBytes  k  n\texttt{leBytes}\;k\;nleByteskn: kkk bytes, most-significant first, encoding n mod 28kn \bmod 2^{8k}nmod28k.

ser8, ser16, ser32, ser64. Abbreviations for leBytes\texttt{leBytes}leBytes with k=1,2,4,8k = 1, 2, 4, 8k=1,2,4,8 respectively. Inputs are unrestricted natural numbers; values ≥28k\ge 2^{8k}≥28k are truncated modulo 28k2^{8k}28k.

serInt64 n (n∈Zn \in \mathbb{Z}n∈Z). The 8 little-endian bytes of the natural number (n mod 264)(n \bmod 2^{64})(nmod264), where  mod \bmodmod on integers here always yields a result in [0,264)[0, 2^{64})[0,264) (Euclidean remainder with positive divisor). Hence n∈[−263,263)n \in [-2^{63}, 2^{63})n∈[−263,263) is encoded in two's complement; an nnn outside [−264,264)[-2^{64}, 2^{64})[−264,264) wraps around.

serInt32 n. The same with 4 bytes and modulus 2322^{32}232.

readInt64 s. Apply readLE  8\texttt{readLE}\;8readLE8; if that gives (v,r)(v, r)(v,r) then return (v,r)(v, r)(v,r) if v<263v < 2^{63}v<263 and (v−264,r)(v - 2^{64}, r)(v−264,r) otherwise, as integers. So the decoded value always lies in [−263,263)[-2^{63}, 2^{63})[−263,263). ⊥\bot⊥ if fewer than 8 bytes.

readInt32 s. Likewise with 4 bytes, thresholds 2312^{31}231 and 2322^{32}232; decoded value in [−231,231)[-2^{31}, 2^{31})[−231,231).


CompactSize

writeCompactSize n (n∈Nn \in \mathbb{N}n∈N). A case split on nnn:

  • n<253n < 253n<253: the single byte nnn;
  • 253≤n≤0xffff253 \le n \le \mathrm{0xffff}253≤n≤0xffff: the byte 253253253 followed by ser16  n\texttt{ser16}\;nser16n;
  • 0xffff<n≤0xffffffff\mathrm{0xffff} < n \le \mathrm{0xffffffff}0xffff<n≤0xffffffff: the byte 254254254 followed by ser32  n\texttt{ser32}\;nser32n;
  • otherwise: the byte 255255255 followed by ser64  n\texttt{ser64}\;nser64n.

For n≥264n \ge 2^{64}n≥264 the last case still applies and the 8 bytes hold n mod 264n \bmod 2^{64}nmod264 (truncation).

readCompactSize rc s (rcrcrc a Boolean, sss a byte string). If sss is empty: ⊥\bot⊥. Otherwise let ccc be the first byte and rrr the rest, and compute a provisional result:

  • c<253c < 253c<253: (c,r)(c, r)(c,r);
  • c=253c = 253c=253: read 2 bytes little-endian from rrr to get (v,r′)(v, r')(v,r′); if that read fails, ⊥\bot⊥; if v<253v < 253v<253, ⊥\bot⊥ (non-canonical); else (v,r′)(v, r')(v,r′);
  • c=254c = 254c=254: read 4 bytes; ⊥\bot⊥ on short read; ⊥\bot⊥ if v<0x10000v < \mathrm{0x10000}v<0x10000; else (v,r′)(v, r')(v,r′);
  • c=255c = 255c=255 (the only remaining case): read 8 bytes; ⊥\bot⊥ on short read; ⊥\bot⊥ if v<0x100000000v < \mathrm{0x100000000}v<0x100000000; else (v,r′)(v, r')(v,r′).

Then, if the provisional result is (v,r′)(v, r')(v,r′): return ⊥\bot⊥ when rcrcrc is true and MAX_SIZE<v\texttt{MAX\_SIZE} < vMAX_SIZE<v; otherwise return (v,r′)(v, r')(v,r′). Thus with rcrcrc true the accepted values are exactly those with v≤MAX_SIZEv \le \texttt{MAX\_SIZE}v≤MAX_SIZE (equality allowed); with rcrcrc false there is no upper bound beyond the 2642^{64}264 implied by 8 bytes. The canonicality rejections are strict: in the 2-byte form v=253v = 253v=253 is accepted and v=252v = 252v=252 rejected; in the 4-byte form v=0x10000v = \mathrm{0x10000}v=0x10000 accepted; in the 8-byte form v=232v = 2^{32}v=232 accepted.


Vectors and byte strings

serList f l. writeCompactSize(∣l∣)\texttt{writeCompactSize}(|l|)writeCompactSize(∣l∣) followed by the concatenation of f(x)f(x)f(x) over the elements xxx of lll in order. The empty list serializes as the single byte 000.

readN f n s. Read exactly nnn items with the reader fff, threading the remainder: for n=0n = 0n=0 return ([ ],s)([\,], s)([],s) without consuming anything; for n+1n+1n+1, apply fff to sss; if it fails, ⊥\bot⊥; otherwise recurse on the remainder for nnn more items; if that fails, ⊥\bot⊥; otherwise prepend the item. There is no bound on nnn inside readN itself.

readList f s. Apply readCompactSize\texttt{readCompactSize}readCompactSize with range check on to get a count nnn (so n≤MAX_SIZEn \le \texttt{MAX\_SIZE}n≤MAX_SIZE or ⊥\bot⊥), then readN  f  n\texttt{readN}\;f\;nreadNfn on the remainder.

serBytes b. writeCompactSize(∣b∣)\texttt{writeCompactSize}(|b|)writeCompactSize(∣b∣) followed by the raw bytes of bbb.

readBytes s. Range-checked readCompactSize\texttt{readCompactSize}readCompactSize to get (n,s′)(n, s')(n,s′) (so n≤MAX_SIZEn \le \texttt{MAX\_SIZE}n≤MAX_SIZE); then if ∣s′∣<n|s'| < n∣s′∣<n, ⊥\bot⊥; else (s′[:n],s′[n:])(s'[{:}n], s'[n{:}])(s′[:n],s′[n:]). Exactly nnn bytes remaining is a success.

readHash s. If ∣s∣<32|s| < 32∣s∣<32, ⊥\bot⊥; else (s[:32],s[32:])(s[{:}32], s[32{:}])(s[:32],s[32:]). No interpretation of the bytes.


Transaction record types

OutPoint. A record with fields hash\texttt{hash}hash (a byte string of unrestricted length) and n\texttt{n}n (a natural number, unrestricted).

TxIn. Fields prevout\texttt{prevout}prevout (an OutPoint), scriptSig\texttt{scriptSig}scriptSig (bytes), nSequence\texttt{nSequence}nSequence (natural number), witness\texttt{witness}witness (a list of byte strings).

TxOut. Fields nValue\texttt{nValue}nValue (an integer, possibly negative or huge) and scriptPubKey\texttt{scriptPubKey}scriptPubKey (bytes).

Tx. Fields version\texttt{version}version (a natural number, not an integer), vin\texttt{vin}vin (list of TxIn), vout\texttt{vout}vout (list of TxOut), nLockTime\texttt{nLockTime}nLockTime (natural number). All four record types have decidable equality (equality is field-wise).

Tx.hasWitness tx. Boolean: true iff some input of tx\texttt{tx}tx has a non-empty witness list. A transaction with no inputs has no witness.

Tx.stripWitness tx. The same transaction with every input's witness list replaced by the empty list; all other fields unchanged. It is idempotent, and hasWitness(stripWitness  tx)\texttt{hasWitness}(\texttt{stripWitness}\;tx)hasWitness(stripWitnesstx) is false.

serOutPoint o. The raw bytes o.hasho.\texttt{hash}o.hash (whatever their length, with no length prefix) followed by ser32(o.n)\texttt{ser32}(o.\texttt{n})ser32(o.n).

serTxIn i. serOutPoint(i.prevout)+ ⁣ ⁣+serBytes(i.scriptSig)+ ⁣ ⁣+ser32(i.nSequence)\texttt{serOutPoint}(i.\texttt{prevout}) \mathbin{+\!\!+} \texttt{serBytes}(i.\texttt{scriptSig}) \mathbin{+\!\!+} \texttt{ser32}(i.\texttt{nSequence})serOutPoint(i.prevout)++serBytes(i.scriptSig)++ser32(i.nSequence). The witness field is not included.

serTxOut o. serInt64(o.nValue)+ ⁣ ⁣+serBytes(o.scriptPubKey)\texttt{serInt64}(o.\texttt{nValue}) \mathbin{+\!\!+} \texttt{serBytes}(o.\texttt{scriptPubKey})serInt64(o.nValue)++serBytes(o.scriptPubKey).

serTx aw tx (awawaw a Boolean "allow witness"). Let ϕ=1\phi = 1ϕ=1 if awawaw is true and hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx) is true, else ϕ=0\phi = 0ϕ=0. The output is the concatenation of:

  1. ser32(tx.version)\texttt{ser32}(tx.\texttt{version})ser32(tx.version) (4 bytes, unsigned, truncated mod 2322^{32}232);
  2. if ϕ≠0\phi \ne 0ϕ=0: the two bytes [ 0 , ϕ ][\,0\,,\,\phi\,][0,ϕ] (i.e. writeCompactSize  0\texttt{writeCompactSize}\;0writeCompactSize0 then ser8  ϕ\texttt{ser8}\;\phiser8ϕ), otherwise nothing;
  3. serList  serTxIn  tx.vin\texttt{serList}\;\texttt{serTxIn}\;tx.\texttt{vin}serListserTxIntx.vin;
  4. serList  serTxOut  tx.vout\texttt{serList}\;\texttt{serTxOut}\;tx.\texttt{vout}serListserTxOuttx.vout;
  5. if ϕ≠0\phi \ne 0ϕ=0: for each input in order, serList  serBytes\texttt{serList}\;\texttt{serBytes}serListserBytes of its witness list (a count then the length-prefixed stack items), otherwise nothing;
  6. ser32(tx.nLockTime)\texttt{ser32}(tx.\texttt{nLockTime})ser32(tx.nLockTime).

Since ϕ∈{0,1}\phi \in \{0,1\}ϕ∈{0,1}, item 2 is either absent or exactly [0x00,0x01][\mathrm{0x00}, \mathrm{0x01}][0x00,0x01]. With awawaw false the output never depends on any witness; with awawaw true and no non-empty witness it is byte-for-byte the same as with awawaw false.

readOutPoint s. readHash\texttt{readHash}readHash (32 bytes) then readLE  4\texttt{readLE}\;4readLE4; ⊥\bot⊥ if either fails.

readTxIn s. readOutPoint\texttt{readOutPoint}readOutPoint, then readBytes\texttt{readBytes}readBytes (range-checked script), then readLE  4\texttt{readLE}\;4readLE4; the resulting input has witness [ ][\,][]. ⊥\bot⊥ if any step fails.

readTxOut s. readInt64\texttt{readInt64}readInt64 then readBytes\texttt{readBytes}readBytes; ⊥\bot⊥ on failure.

attachWitness ins ws. Walk the two lists in parallel, replacing the witness of the iii-th input by the iii-th element of wswsws. When either list runs out, the remaining inputs are returned unchanged (keeping whatever witness they had) and any remaining elements of wswsws are discarded.

readWitnesses n s. readN\texttt{readN}readN with the item reader readList  readBytes\texttt{readList}\;\texttt{readBytes}readListreadBytes: reads exactly nnn witness stacks, each a range-checked count followed by that many range-checked length-prefixed byte strings.

readTx aw s. The control flow is:

  1. readLE  4\texttt{readLE}\;4readLE4 to get an unsigned version\texttt{version}version; ⊥\bot⊥ if fewer than 4 bytes.

  2. readList  readTxIn\texttt{readList}\;\texttt{readTxIn}readListreadTxIn to get vin0\texttt{vin}_0vin0​; ⊥\bot⊥ on failure.

  3. Step 2. If vin0\texttt{vin}_0vin0​ is empty and awawaw is true:

    • if no bytes remain, ⊥\bot⊥;
    • otherwise consume one byte flflfl (the "flags" byte);
    • if fl≠0fl \ne 0fl=0: readList  readTxIn\texttt{readList}\;\texttt{readTxIn}readListreadTxIn again to get vin\texttt{vin}vin, then readList  readTxOut\texttt{readList}\;\texttt{readTxOut}readListreadTxOut to get vout\texttt{vout}vout; ⊥\bot⊥ if either fails; carry (fl,vin,vout)(fl, \texttt{vin}, \texttt{vout})(fl,vin,vout);
    • if fl=0fl = 0fl=0: carry (0,vin0=[ ],vout=[ ])(0, \texttt{vin}_0 = [\,], \texttt{vout} = [\,])(0,vin0​=[],vout=[]) without reading an output list; the byte flflfl has been consumed.

    Otherwise (vin0\texttt{vin}_0vin0​ non-empty, or awawaw false): readList  readTxOut\texttt{readList}\;\texttt{readTxOut}readListreadTxOut to get vout\texttt{vout}vout; ⊥\bot⊥ on failure; carry (0,vin0,vout)(0, \texttt{vin}_0, \texttt{vout})(0,vin0​,vout).

  4. Step 3. With flags ϕ\phiϕ and inputs vin\texttt{vin}vin from step 2: if ϕ\phiϕ is odd and awawaw is true, read ∣vin∣|\texttt{vin}|∣vin∣ witness stacks with readWitnesses\texttt{readWitnesses}readWitnesses (⊥\bot⊥ on failure), attach them to the inputs in order, and then require that the resulting input list has at least one non-empty witness stack — if it does not, ⊥\bot⊥ ("superfluous witness record"); on success carry (ϕ−1,vin′)(\phi - 1, \texttt{vin}')(ϕ−1,vin′). Otherwise carry (ϕ,vin)(\phi, \texttt{vin})(ϕ,vin) unchanged. (Note: ϕ≠0\phi \ne 0ϕ=0 can only arise in the branch where awawaw is true, so the extra "awawaw true" test here never changes the outcome.)

  5. If the carried flags value is ≠0\ne 0=0, ⊥\bot⊥ ("unknown optional data"). Consequently the only flags byte that can lead to success is fl=1fl = 1fl=1 (odd, and 1−1=01 - 1 = 01−1=0); any even non-zero byte, or any odd byte other than 1, yields ⊥\bot⊥.

  6. readLE  4\texttt{readLE}\;4readLE4 for nLockTime\texttt{nLockTime}nLockTime; ⊥\bot⊥ if short. Return ⟨version,vin,vout,lock⟩\langle \texttt{version}, \texttt{vin}, \texttt{vout}, \texttt{lock}\rangle⟨version,vin,vout,lock⟩ with the remaining bytes.

Failure cases worth listing explicitly: any short read; any non-canonical or over-MAX_SIZE\texttt{MAX\_SIZE}MAX_SIZE count; awawaw true, empty first input list and no further byte; fl=1fl = 1fl=1 but zero inputs in the re-read list (then there are zero witness stacks, nothing is non-empty, and the superfluous-witness test fails); fl=1fl = 1fl=1 but all witness stacks empty; fl∉{0,1}fl \notin \{0, 1\}fl∈/{0,1}. Also note the consequence of the fl=0fl = 0fl=0 branch: a byte string of the form ser32(v)+ ⁣ ⁣+[0]+ ⁣ ⁣+writeCompactSize(m)+ ⁣ ⁣+⋯\texttt{ser32}(v) \mathbin{+\!\!+} [0] \mathbin{+\!\!+} \texttt{writeCompactSize}(m) \mathbin{+\!\!+} \cdotsser32(v)++[0]++writeCompactSize(m)++⋯ (a witness-free transaction with no inputs and mmm outputs) is, under awawaw true, read with mmm in the role of the flags byte, so for m≥1m \ge 1m≥1 the input list is re-read from the bytes of the first output, and for m=0m = 0m=0 the outputs are set to [ ][\,][] and parsing continues at the lock time. A reader might expect the output count to be read here; the code does not do so.


Headers and blocks

Header. Fields version\texttt{version}version (an integer, in contrast to Tx.version), prevBlock\texttt{prevBlock}prevBlock (bytes, unrestricted length), merkleRoot\texttt{merkleRoot}merkleRoot (bytes, unrestricted length), time\texttt{time}time, bits\texttt{bits}bits, nonce\texttt{nonce}nonce (natural numbers).

serHeader h. serInt32(h.version)+ ⁣ ⁣+h.prevBlock+ ⁣ ⁣+h.merkleRoot+ ⁣ ⁣+ser32(h.time)+ ⁣ ⁣+ser32(h.bits)+ ⁣ ⁣+ser32(h.nonce)\texttt{serInt32}(h.\texttt{version}) \mathbin{+\!\!+} h.\texttt{prevBlock} \mathbin{+\!\!+} h.\texttt{merkleRoot} \mathbin{+\!\!+} \texttt{ser32}(h.\texttt{time}) \mathbin{+\!\!+} \texttt{ser32}(h.\texttt{bits}) \mathbin{+\!\!+} \texttt{ser32}(h.\texttt{nonce})serInt32(h.version)++h.prevBlock++h.merkleRoot++ser32(h.time)++ser32(h.bits)++ser32(h.nonce). The two hash fields are emitted raw, with no length prefix and no length check; the length of the result is 16+∣h.prevBlock∣+∣h.merkleRoot∣16 + |h.\texttt{prevBlock}| + |h.\texttt{merkleRoot}|16+∣h.prevBlock∣+∣h.merkleRoot∣.

readHeader s. readInt32\texttt{readInt32}readInt32 (signed), readHash\texttt{readHash}readHash, readHash\texttt{readHash}readHash, then three readLE  4\texttt{readLE}\;4readLE4; ⊥\bot⊥ if any fails. Requires at least 80 bytes.

Block. Fields header\texttt{header}header and vtx\texttt{vtx}vtx (a list of Tx).

serBlock aw b. serHeader(b.header)+ ⁣ ⁣+serList  (serTx  aw)  b.vtx\texttt{serHeader}(b.\texttt{header}) \mathbin{+\!\!+} \texttt{serList}\;(\texttt{serTx}\;aw)\;b.\texttt{vtx}serHeader(b.header)++serList(serTxaw)b.vtx.

readBlock aw s. readHeader\texttt{readHeader}readHeader then readList  (readTx  aw)\texttt{readList}\;(\texttt{readTx}\;aw)readList(readTxaw); ⊥\bot⊥ on failure.


Well-formedness predicates

All are propositions (not Booleans).

OutPoint.wf o. ∣o.hash∣=32|o.\texttt{hash}| = 32∣o.hash∣=32 and o.n<232o.\texttt{n} < 2^{32}o.n<232.

TxIn.wf i. i.prevouti.\texttt{prevout}i.prevout is well-formed, and ∣i.scriptSig∣≤MAX_SIZE|i.\texttt{scriptSig}| \le \texttt{MAX\_SIZE}∣i.scriptSig∣≤MAX_SIZE, and i.nSequence<232i.\texttt{nSequence} < 2^{32}i.nSequence<232, and ∣i.witness∣≤MAX_SIZE|i.\texttt{witness}| \le \texttt{MAX\_SIZE}∣i.witness∣≤MAX_SIZE, and every element www of i.witnessi.\texttt{witness}i.witness has ∣w∣≤MAX_SIZE|w| \le \texttt{MAX\_SIZE}∣w∣≤MAX_SIZE. (Each "≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE" matches the reader's acceptance of counts equal to MAX_SIZE\texttt{MAX\_SIZE}MAX_SIZE.)

TxOut.wf o. −263≤o.nValue<263-2^{63} \le o.\texttt{nValue} < 2^{63}−263≤o.nValue<263 and ∣o.scriptPubKey∣≤MAX_SIZE|o.\texttt{scriptPubKey}| \le \texttt{MAX\_SIZE}∣o.scriptPubKey∣≤MAX_SIZE.

Tx.wf tx. tx.version<232tx.\texttt{version} < 2^{32}tx.version<232, tx.nLockTime<232tx.\texttt{nLockTime} < 2^{32}tx.nLockTime<232, ∣tx.vin∣≤MAX_SIZE|tx.\texttt{vin}| \le \texttt{MAX\_SIZE}∣tx.vin∣≤MAX_SIZE, ∣tx.vout∣≤MAX_SIZE|tx.\texttt{vout}| \le \texttt{MAX\_SIZE}∣tx.vout∣≤MAX_SIZE, every input well-formed, every output well-formed. Nothing is required of the number of inputs (it may be zero) or of the witness/no-witness status.

Header.wf h. −231≤h.version<231-2^{31} \le h.\texttt{version} < 2^{31}−231≤h.version<231, ∣h.prevBlock∣=32|h.\texttt{prevBlock}| = 32∣h.prevBlock∣=32, ∣h.merkleRoot∣=32|h.\texttt{merkleRoot}| = 32∣h.merkleRoot∣=32, and h.time,h.bits,h.nonce<232h.\texttt{time}, h.\texttt{bits}, h.\texttt{nonce} < 2^{32}h.time,h.bits,h.nonce<232.

Block.wf b. b.headerb.\texttt{header}b.header well-formed, ∣b.vtx∣≤MAX_SIZE|b.\texttt{vtx}| \le \texttt{MAX\_SIZE}∣b.vtx∣≤MAX_SIZE, and for every transaction txtxtx in b.vtxb.\texttt{vtx}b.vtx: txtxtx is well-formed and (tx.vin≠[ ]tx.\texttt{vin} \ne [\,]tx.vin=[] or hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx) is true). Since a transaction with a non-empty witness necessarily has at least one input, the second disjunct implies the first, and the parenthesised condition is equivalent to "txtxtx has at least one input". This condition is imposed regardless of which serialization mode a theorem later uses.


SHA-256

Primitive word operations. All on 32-bit unsigned words with wrap-around addition. rotr(x,n)=(x≫n) ∣ (x≪(32−n))\texttt{rotr}(x, n) = (x \gg n) \,|\, (x \ll (32 - n))rotr(x,n)=(x≫n)∣(x≪(32−n)) (a right rotation for 1≤n≤311 \le n \le 311≤n≤31; shift amounts in this word type are taken modulo 32, which is only relevant for n=0n = 0n=0, never used). Ch(x,y,z)=z⊕(x∧(y⊕z))\texttt{Ch}(x,y,z) = z \oplus (x \wedge (y \oplus z))Ch(x,y,z)=z⊕(x∧(y⊕z)); Maj(x,y,z)=(x∧y) ∣ (z∧(x ∣ y))\texttt{Maj}(x,y,z) = (x \wedge y) \,|\, (z \wedge (x \,|\, y))Maj(x,y,z)=(x∧y)∣(z∧(x∣y)); Σ0(x)=rotr(x,2)⊕rotr(x,13)⊕rotr(x,22)\Sigma_0(x) = \texttt{rotr}(x,2) \oplus \texttt{rotr}(x,13) \oplus \texttt{rotr}(x,22)Σ0​(x)=rotr(x,2)⊕rotr(x,13)⊕rotr(x,22); Σ1(x)=rotr(x,6)⊕rotr(x,11)⊕rotr(x,25)\Sigma_1(x) = \texttt{rotr}(x,6) \oplus \texttt{rotr}(x,11) \oplus \texttt{rotr}(x,25)Σ1​(x)=rotr(x,6)⊕rotr(x,11)⊕rotr(x,25); σ0(x)=rotr(x,7)⊕rotr(x,18)⊕(x≫3)\sigma_0(x) = \texttt{rotr}(x,7) \oplus \texttt{rotr}(x,18) \oplus (x \gg 3)σ0​(x)=rotr(x,7)⊕rotr(x,18)⊕(x≫3); σ1(x)=rotr(x,17)⊕rotr(x,19)⊕(x≫10)\sigma_1(x) = \texttt{rotr}(x,17) \oplus \texttt{rotr}(x,19) \oplus (x \gg 10)σ1​(x)=rotr(x,17)⊕rotr(x,19)⊕(x≫10).

sha256K. A list of 64 32-bit words written in decimal; the first is 0x428a2f98\mathrm{0x428a2f98}0x428a2f98 and the last 0xc67178f2\mathrm{0xc67178f2}0xc67178f2; all entries are below 2322^{32}232.

Sha256State, sha256Init. An 8-word state (a,…,h)(a,\dots,h)(a,…,h) with initial value (0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19)(\mathrm{0x6a09e667}, \mathrm{0xbb67ae85}, \mathrm{0x3c6ef372}, \mathrm{0xa54ff53a}, \mathrm{0x510e527f}, \mathrm{0x9b05688c}, \mathrm{0x1f83d9ab}, \mathrm{0x5be0cd19})(0x6a09e667,0xbb67ae85,0x3c6ef372,0xa54ff53a,0x510e527f,0x9b05688c,0x1f83d9ab,0x5be0cd19) — eight values.

sha256Round s kw. With t1=h+Σ1(e)+Ch(e,f,g)+kwt_1 = h + \Sigma_1(e) + \texttt{Ch}(e,f,g) + kwt1​=h+Σ1​(e)+Ch(e,f,g)+kw and t2=Σ0(a)+Maj(a,b,c)t_2 = \Sigma_0(a) + \texttt{Maj}(a,b,c)t2​=Σ0​(a)+Maj(a,b,c), the new state is (t1+t2, a, b, c, d+t1, e, f, g)(t_1 + t_2,\, a,\, b,\, c,\, d + t_1,\, e,\, f,\, g)(t1​+t2​,a,b,c,d+t1​,e,f,g). The single argument kwkwkw is expected to be the already-summed round constant plus schedule word.

be32Words s. Groups the byte list into consecutive 4-byte big-endian words; a trailing group of fewer than 4 bytes is dropped.

sha256Schedule w. Starting from www, appends 48 words; each new word, at position t=t = t= current length, is σ1(wt−2)+wt−7+σ0(wt−15)+wt−16\sigma_1(w_{t-2}) + w_{t-7} + \sigma_0(w_{t-15}) + w_{t-16}σ1​(wt−2​)+wt−7​+σ0​(wt−15​)+wt−16​, where an out-of-range index reads as 000 and the subtractions are truncated at 000. On a 16-word input this yields 64 words.

sha256Compress s chunk. Form the 64-word schedule from the big-endian words of the chunk; pair it element-wise with sha256K by addition (the pairing stops at the shorter list, 64 here); fold sha256Round over these 64 sums starting from sss; return the word-wise sum of sss and the folded state.

chunks64Aux fuel s, chunks64 s. Cuts sss into successive 64-byte pieces as long as at least 64 bytes remain, with a recursion budget of ⌊∣s∣/64⌋\lfloor |s|/64 \rfloor⌊∣s∣/64⌋; any trailing partial piece is silently dropped. On the padded inputs below the length is always a multiple of 64.

mdPad be msg. Appends the byte 0x80\mathrm{0x80}0x80, then z=(119−(∣msg∣ mod 64)) mod 64z = (119 - (|msg| \bmod 64)) \bmod 64z=(119−(∣msg∣mod64))mod64 zero bytes, then 8 bytes holding 8⋅∣msg∣8\cdot|msg|8⋅∣msg∣ (big-endian if bebebe, little-endian otherwise; truncated mod 2642^{64}264). One checks that ∣msg∣+1+z+8|msg| + 1 + z + 8∣msg∣+1+z+8 is always a multiple of 64, and that the length field ends the final 64-byte block.

be32Bytes, le32Bytes. A 32-bit word as 4 big-endian, resp. little-endian, bytes.

sha256 msg. Fold sha256Compress over the 64-byte chunks of mdPad  true  msg\texttt{mdPad}\;\mathrm{true}\;msgmdPadtruemsg starting from sha256Init; output the 8 state words each as 4 big-endian bytes (32 bytes). Defined for every byte string including the empty one (one chunk).


RIPEMD-160

Primitives. rol(x,n)=(x≪n) ∣ (x≫(32−n))\texttt{rol}(x,n) = (x \ll n)\,|\,(x \gg (32-n))rol(x,n)=(x≪n)∣(x≫(32−n)); f1=x⊕y⊕zf_1 = x \oplus y \oplus zf1​=x⊕y⊕z; f2=(x∧y) ∣ (¬x∧z)f_2 = (x \wedge y)\,|\,(\neg x \wedge z)f2​=(x∧y)∣(¬x∧z); f3=(x ∣ ¬y)⊕zf_3 = (x \,|\, \neg y) \oplus zf3​=(x∣¬y)⊕z; f4=(x∧z) ∣ (y∧¬z)f_4 = (x \wedge z)\,|\,(y \wedge \neg z)f4​=(x∧z)∣(y∧¬z); f5=x⊕(y ∣ ¬z)f_5 = x \oplus (y \,|\, \neg z)f5​=x⊕(y∣¬z).

le32Words. Like be32Words but little-endian within each 4-byte group; trailing partial group dropped.

Tables. ripemdRL, ripemdRR (message-word indices) and ripemdSL, ripemdSR (rotation amounts) are each lists of 80 natural numbers. The index tables take values in [0,15][0,15][0,15] (the left one begins 0,1,…,150,1,\dots,150,1,…,15); the rotation tables take values in [5,15][5,15][5,15].

R5, ripemdInit. A 5-word state with initial value (0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0)(\mathrm{0x67452301}, \mathrm{0xEFCDAB89}, \mathrm{0x98BADCFE}, \mathrm{0x10325476}, \mathrm{0xC3D2E1F0})(0x67452301,0xEFCDAB89,0x98BADCFE,0x10325476,0xC3D2E1F0).

Selectors. By round index j∈[0,80)j \in [0,80)j∈[0,80) in blocks of 16: the left line uses f1,f2,f3,f4,f5f_1, f_2, f_3, f_4, f_5f1​,f2​,f3​,f4​,f5​ with constants 0,0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xA953FD4E0, \mathrm{0x5A827999}, \mathrm{0x6ED9EBA1}, \mathrm{0x8F1BBCDC}, \mathrm{0xA953FD4E}0,0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xA953FD4E; the right line uses f5,f4,f3,f2,f1f_5, f_4, f_3, f_2, f_1f5​,f4​,f3​,f2​,f1​ with constants 0x50A28BE6,0x5C4DD124,0x6D703EF3,0x7A6D76E9,0\mathrm{0x50A28BE6}, \mathrm{0x5C4DD124}, \mathrm{0x6D703EF3}, \mathrm{0x7A6D76E9}, 00x50A28BE6,0x5C4DD124,0x6D703EF3,0x7A6D76E9,0. The branches are "j<16j < 16j<16, j<32j < 32j<32, j<48j < 48j<48, j<64j < 64j<64, else", so j≥80j \ge 80j≥80 would fall in the last group (never reached).

ripemdStep s f x k r. a′=rol(a+f+x+k,r)+ea' = \texttt{rol}(a + f + x + k, r) + ea′=rol(a+f+x+k,r)+e, c′=rol(c,10)c' = \texttt{rol}(c, 10)c′=rol(c,10), new state (e, a′, b, c′, d)(e,\, a',\, b,\, c',\, d)(e,a′,b,c′,d).

ripemdLine. Fold ripemdStep over j=0,…,79j = 0, \dots, 79j=0,…,79, with f=fsel(j,b,c,d)f = f_{\mathrm{sel}}(j, b, c, d)f=fsel​(j,b,c,d) evaluated on the current state, message word w[idx[j]]w[\texttt{idx}[j]]w[idx[j]] (missing entries read as 000), constant k(j)k(j)k(j) and rotation s[j]\texttt{s}[j]s[j].

ripemdCompress s chunk. Run the left line and the right line independently from the same sss on the little-endian words of the chunk, giving LLL and RRR; return (b+Lc+Rd,  c+Ld+Re,  d+Le+Ra,  e+La+Rb,  a+Lb+Rc)(b + L_c + R_d,\; c + L_d + R_e,\; d + L_e + R_a,\; e + L_a + R_b,\; a + L_b + R_c)(b+Lc​+Rd​,c+Ld​+Re​,d+Le​+Ra​,e+La​+Rb​,a+Lb​+Rc​).

ripemd160 msg. Fold ripemdCompress over the chunks of mdPad  false  msg\texttt{mdPad}\;\mathrm{false}\;msgmdPadfalsemsg (little-endian length) from ripemdInit; output the 5 words as little-endian bytes (20 bytes).


SHA-1

sha1F t, sha1K t. By ttt in blocks of 20: d⊕(b∧(c⊕d))d \oplus (b \wedge (c \oplus d))d⊕(b∧(c⊕d)), then b⊕c⊕db \oplus c \oplus db⊕c⊕d, then (b∧c) ∣ (d∧(b ∣ c))(b \wedge c)\,|\,(d \wedge (b\,|\,c))(b∧c)∣(d∧(b∣c)), then b⊕c⊕db \oplus c \oplus db⊕c⊕d; constants 0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6\mathrm{0x5A827999}, \mathrm{0x6ED9EBA1}, \mathrm{0x8F1BBCDC}, \mathrm{0xCA62C1D6}0x5A827999,0x6ED9EBA1,0x8F1BBCDC,0xCA62C1D6.

sha1Schedule. Appends 64 words, each rol(wt−3⊕wt−8⊕wt−14⊕wt−16,1)\texttt{rol}(w_{t-3} \oplus w_{t-8} \oplus w_{t-14} \oplus w_{t-16}, 1)rol(wt−3​⊕wt−8​⊕wt−14​⊕wt−16​,1) with the same out-of-range convention as SHA-256.

sha1Compress. 80 rounds of temp=rol(a,5)+sha1F(t,b,c,d)+e+sha1K(t)+wt\texttt{temp} = \texttt{rol}(a,5) + \texttt{sha1F}(t,b,c,d) + e + \texttt{sha1K}(t) + w_ttemp=rol(a,5)+sha1F(t,b,c,d)+e+sha1K(t)+wt​, new state (temp,a,rol(b,30),c,d)(\texttt{temp}, a, \texttt{rol}(b,30), c, d)(temp,a,rol(b,30),c,d); then word-wise addition to the input state.

sha1 msg. Fold over the chunks of mdPad  true  msg\texttt{mdPad}\;\mathrm{true}\;msgmdPadtruemsg starting from ripemdInit (the RIPEMD-160 initial-value constant is reused as the SHA-1 initial state; the five values are the same numbers); output 5 words big-endian (20 bytes). No other declaration in the file refers to sha1.


Composite hashes

hash256 m =sha256(sha256(m))= \texttt{sha256}(\texttt{sha256}(m))=sha256(sha256(m)) (32 bytes). hash160 m =ripemd160(sha256(m))= \texttt{ripemd160}(\texttt{sha256}(m))=ripemd160(sha256(m)) (20 bytes). txid tx =hash256(serTx  false  tx)= \texttt{hash256}(\texttt{serTx}\;\mathrm{false}\;tx)=hash256(serTxfalsetx) — the witness-free serialization is hashed whether or not the transaction has witnesses. wtxid tx =hash256(serTx  true  tx)= \texttt{hash256}(\texttt{serTx}\;\mathrm{true}\;tx)=hash256(serTxtruetx) if hasWitness(tx)\texttt{hasWitness}(tx)hasWitness(tx), else txid(tx)\texttt{txid}(tx)txid(tx). headerHash h =hash256(serHeader  h)= \texttt{hash256}(\texttt{serHeader}\;h)=hash256(serHeaderh).


Weights

Constants. WITNESS_SCALE_FACTOR=4\texttt{WITNESS\_SCALE\_FACTOR} = 4WITNESS_SCALE_FACTOR=4; MAX_BLOCK_WEIGHT=MAX_BLOCK_SERIALIZED_SIZE=4 000 000\texttt{MAX\_BLOCK\_WEIGHT} = \texttt{MAX\_BLOCK\_SERIALIZED\_SIZE} = 4\,000\,000MAX_BLOCK_WEIGHT=MAX_BLOCK_SERIALIZED_SIZE=4000000 (the latter two are not used elsewhere in the file).

txWeight tx =3⋅∣serTx  false  tx∣+∣serTx  true  tx∣= 3\cdot|\texttt{serTx}\;\mathrm{false}\;tx| + |\texttt{serTx}\;\mathrm{true}\;tx|=3⋅∣serTxfalsetx∣+∣serTxtruetx∣ (the factor is WITNESS_SCALE_FACTOR−1\texttt{WITNESS\_SCALE\_FACTOR} - 1WITNESS_SCALE_FACTOR−1 in natural-number subtraction, i.e. 333). blockWeight b is the same with serBlock.


Genesis constants

genesisScriptSig. A literal list of 77 bytes: 04 ff ff 00 1d 01 04 45\mathrm{04\,ff\,ff\,00\,1d\,01\,04\,45}04ffff001d010445 followed by the 69 ASCII bytes of the text "The Times 03/Jan/2009 Chancellor on brink of second bailout for banks".

genesisOutputScript. A literal list of 67 bytes: 0x41\mathrm{0x41}0x41, then 65 bytes beginning 0x04\mathrm{0x04}0x04, then 0xac\mathrm{0xac}0xac.

genesisCoinbase. The transaction with version 111; one input whose previous outpoint is (32 zero bytes, 0xffffffff\mathrm{0xffffffff}0xffffffff), whose script is genesisScriptSig, sequence 0xffffffff\mathrm{0xffffffff}0xffffffff, witness [ ][\,][]; one output with value 5 000 000 0005\,000\,000\,0005000000000 and script genesisOutputScript; lock time 000. Its witness-free serialization has 4+1+(32+4+1+77+4)+1+(8+1+67)+4=2044 + 1 + (32+4+1+77+4) + 1 + (8+1+67) + 4 = 2044+1+(32+4+1+77+4)+1+(8+1+67)+4=204 bytes.

genesisHeader. Version 111; previous block 32 zero bytes; merkle root defined as txid(genesisCoinbase)\texttt{txid}(\texttt{genesisCoinbase})txid(genesisCoinbase) (a computed value, not the literal genesisMerkleRoot below); time 123100650512310065051231006505; bits 0x1d00ffff\mathrm{0x1d00ffff}0x1d00ffff; nonce 208323689320832368932083236893.

genesisBlock. The block with genesisHeader and the single transaction genesisCoinbase.

genesisHash. A literal list of 32 bytes beginning 6f e2 8c 0a\mathrm{6f\,e2\,8c\,0a}6fe28c0a and ending with five zero bytes.

genesisMerkleRoot. A literal list of 32 bytes beginning 3b a3 ed fd\mathrm{3b\,a3\,ed\,fd}3ba3edfd and ending 1e 5e 4a\mathrm{1e\,5e\,4a}1e5e4a.


Points a reader may wish to note

  • Range-checked counts accept v=MAX_SIZEv = \texttt{MAX\_SIZE}v=MAX_SIZE (the test is strict MAX_SIZE<v\texttt{MAX\_SIZE} < vMAX_SIZE<v), and the well-formedness predicates use ≤MAX_SIZE\le \texttt{MAX\_SIZE}≤MAX_SIZE accordingly.
  • In readTx, when the first input list is empty and awawaw is true, the next byte is always consumed as a flags byte; if it is 000 the output list is set to [ ][\,][] without being read.
  • Block.wf requires every transaction to have an input (the disjunct about witnesses is implied by the other), in both serialization modes.
  • Tx.version is unsigned and read unsigned; Header.version is signed and read signed.
  • Hash fields of outpoints and headers are serialized raw with no length check; only wf ties them to 32 bytes.
  • All fixed-width encoders truncate rather than fail; serInt64/serInt32 wrap outside the signed range.
  • sha1 uses ripemdInit as its initial value and is not referenced by anything else.
  • chunks64 and be32Words/le32Words drop trailing partial groups silently; mdPad always produces a multiple of 64 bytes, so this never triggers inside the hash functions.
Human review
  • Endorsed by Shuze Chen · Oct 26, 2026

    Confirmed by the moderator at approval.

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