Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Signature encodings, signature hashes, secp256k1 ECDSA and Schnorr verification, and the transaction signature checker

Definition
BitcoinSig

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

bitcoinbitcoin-mainnetconsensusderecdsaformal-verificationschnorrsecp256k1sighash

secp256k1. p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977, the order nnn, the generator GGG; powMod is square-and-multiply with explicit fuel, finv/ninv are Fermat inverses; a Point is an affine pair or infinity; padd is affine addition with the doubling and inverse cases; pmul is double-and-add. liftXParity is secp256k1_ge_set_xo_var (square root by (p+1)/4(p+1)/4(p+1)/4, parity selection); parsePubkey is secp256k1_eckey_pubkey_parse (33-byte 02/03, 65-byte 04/06/07 with coordinates below ppp, on-curve and, for hybrid, parity check); pubkeyValid is CPubKey::IsValid (the header byte announces the length). isHighS is s>n/2s > n/2s>n/2, normalizeS replaces a high sss by n−sn - sn−s.

Signatures. parseDerLax is ecdsa_signature_parse_der_lax with its exact control flow: none where it returns 000 (missing tags, length overruns, a long-form length of 4 or more significant bytes), some (0,0) where an integer has more than 32 significant bytes or a value at or above nnn (the "correctly parsed but invalid" signature), trailing bytes ignored. ecdsaVerifyRaw is secp256k1_ecdsa_sig_verify: r,s∈[1,n)r, s \in [1, n)r,s∈[1,n), u1=es−1u_1 = e s^{-1}u1​=es−1, u2=rs−1u_2 = r s^{-1}u2​=rs−1, R=u1G+u2Q≠∞R = u_1 G + u_2 Q \ne \inftyR=u1​G+u2​Q=∞ and Rx mod n=rR_x \bmod n = rRx​modn=r. pubkeyVerify is CPubKey::Verify: valid and parsable key, lax-parsed signature, sss normalized, message reduced modulo nnn. checkLowS is CPubKey::CheckLowS. schnorrVerify is BIP340 / secp256k1_schnorrsig_verify with taggedHash.

Byte-level scripts. getOp is GetScriptOp (direct pushes, PUSHDATA1/2/4, none on a truncated push); parseScript parses a whole script; pushBytes is CScript() << vch; findAndDelete is FindAndDelete (occurrences removed at instruction boundaries, count returned); serScriptCode is SerializeScriptCode (OP_CODESEPARATORs dropped, length-prefixed).

Signature hashes. serSigTx is CTransactionSignatureSerializer (ANYONECANPAY keeps only the signed input, other inputs' scripts blanked, their sequences zeroed under SINGLE/NONE, outputs truncated under SINGLE, dropped under NONE); sigHashLegacy is SignatureHash for SigVersion::BASE with the SIGHASH_SINGLE bug returning uint256::ONE; sigHashWitnessV0 is the BIP143 algorithm (hashPrevouts, hashSequence, hashOutputs under the same flags, the amount, the script code).

Encoding checks and the checker. isValidSignatureEncoding is the strict-DER test (BIP66) byte for byte; isLowDERSignature, isCompressedOrUncompressedPubKey, isCompressedPubKey, isDefinedHashtypeSignature, checkSignatureEncoding, checkPubKeyEncoding under SigFlags (dersig is the only mainnet consensus flag; lowS, strictenc, witnessPubkeyType are policy and carried for fidelity). checkECDSASignature is the checker's method (hash type = last byte, witness v0 needs a non-negative amount); checkSigPreTapscript is EvalChecksigPreTapscript (FindAndDelete of the signature push for legacy scripts, encoding checks as none, verdict as some). checkLockTime/checkSequence are the checker's lock-time methods (LOCKTIME_THRESHOLD, SEQUENCE_FINAL, BIP68 masks). legacyOracle assembles Core's hashes, the checker and the lock-time checks into the BitcoinScript.Oracle of the legacy interpreter for a given script code.

Auxiliary. p2pkhBytes is the P2PKH output script as bytes; sameSkeleton relates transactions differing only in scriptSigs and witnesses; minimalInt and derEncode describe the DER layout.

Formalization Note. The script code handed to the oracle is the executed script, which is exact for scripts without OP_CODESEPARATOR. Field and scalar arithmetic are on Nat modulo ppp and nnn; no claim about libsecp256k1's constant-time implementation is made, only about its mathematical semantics. Only Std is imported.

Definition code
import Std
import Definitions.Def_BitcoinSer
import Definitions.Def_BitcoinScript

namespace BitcoinSig

/-! Transcription of Bitcoin Core's signature layer at revision
`a773e1e33b349dc819b5a0edc1c7a4839dc73b48`: `GetScriptOp` (`script/script.cpp`), `FindAndDelete`,
`IsValidSignatureEncoding`, `IsLowDERSignature`, `IsCompressedOrUncompressedPubKey`,
`IsCompressedPubKey`, `IsDefinedHashtypeSignature`, `CheckSignatureEncoding`, `CheckPubKeyEncoding`,
`CTransactionSignatureSerializer`, `SignatureHash` (legacy and BIP143), `EvalChecksigPreTapscript`,
`GenericTransactionSignatureChecker::{CheckECDSASignature, CheckLockTime, CheckSequence}`
(`script/interpreter.cpp`); `CPubKey::{IsValid, Verify, CheckLowS}` and `ecdsa_signature_parse_der_lax`
(`pubkey.cpp`); and the secp256k1 semantics of `secp256k1_eckey_pubkey_parse`, `secp256k1_ecdsa_verify`
with signature normalization, and `secp256k1_schnorrsig_verify` (BIP340). -/

open BitcoinSer (Byte Bytes Tx TxIn TxOut OutPoint)

/-! ### secp256k1 -/

/-- The field prime `p = 2^256 - 2^32 - 977`. -/
def p : Nat := 2 ^ 256 - 2 ^ 32 - 977
/-- The group order `n`. -/
def n : Nat := 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
def Gx : Nat := 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
def Gy : Nat := 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8

/-- Square-and-multiply modular exponentiation with explicit fuel. -/
def powModAux (m : Nat) : Nat → Nat → Nat → Nat → Nat
  | 0, _, _, acc => acc
  | fuel + 1, b, e, acc =>
    if e = 0 then acc
    else powModAux m fuel (b * b % m) (e / 2) (if e % 2 = 1 then acc * b % m else acc)

def powMod (b e m : Nat) : Nat := powModAux m (e + 1) (b % m) e (1 % m)

/-- Field inverse by Fermat (`0` maps to `0`). -/
def finv (a : Nat) : Nat := powMod a (p - 2) p
/-- Scalar inverse modulo the group order. -/
def ninv (a : Nat) : Nat := powMod a (n - 2) n

/-- An affine point, or the point at infinity. -/
abbrev Point := Option (Nat × Nat)

def onCurve (P : Nat × Nat) : Bool := (P.2 * P.2) % p = (P.1 * P.1 * P.1 + 7) % p

/-- Affine addition on secp256k1 (`y^2 = x^3 + 7`). -/
def padd (P Q : Point) : Point :=
  match P, Q with
  | none, q => q
  | q, none => q
  | some (x1, y1), some (x2, y2) =>
    if x1 % p = x2 % p then
      if (y1 + y2) % p = 0 then none
      else
        -- doubling
        let l := (3 * x1 * x1) * finv (2 * y1 % p) % p
        let x3 := (l * l + 2 * (p - x1 % p)) % p
        let y3 := (l * ((x1 + p - x3) % p) + (p - y1 % p)) % p
        some (x3, y3)
    else
      let l := ((y2 + p - y1 % p) % p) * finv ((x2 + p - x1 % p) % p) % p
      let x3 := (l * l + (p - x1 % p) + (p - x2 % p)) % p
      let y3 := (l * ((x1 + p - x3) % p) + (p - y1 % p)) % p
      some (x3, y3)

/-- Double-and-add scalar multiplication with explicit fuel. -/
def pmulAux : Nat → Nat → Point → Point → Point
  | 0, _, _, acc => acc
  | fuel + 1, k, P, acc =>
    if k = 0 then acc
    else pmulAux fuel (k / 2) (padd P P) (if k % 2 = 1 then padd acc P else acc)

def pmul (k : Nat) (P : Point) : Point := pmulAux 257 k P none

def G : Point := some (Gx, Gy)

def beVal (b : Bytes) : Nat := b.foldl (fun acc x => acc * 256 + x.toNat) 0

/-- `secp256k1_ge_set_xo_var`: the point with abscissa `x` and the given parity of `y`, if any. -/
def liftXParity (x : Nat) (odd : Bool) : Point :=
  let y := powMod (x * x * x + 7) ((p + 1) / 4) p
  if y * y % p = (x * x * x + 7) % p then
    some (x, if (y % 2 = 1) = odd then y else (p - y) % p)
  else none

/-- `secp256k1_eckey_pubkey_parse`: compressed (`02`/`03`, 33 bytes), uncompressed (`04`) and hybrid
(`06`/`07`, 65 bytes, parity of `y` must match). Coordinates must be below `p` and on the curve. -/
def parsePubkey (pk : Bytes) : Point :=
  match pk with
  | tag :: rest =>
    if pk.length = 33 ∧ (tag.toNat = 2 ∨ tag.toNat = 3) then
      let x := beVal rest
      if x < p then liftXParity x (tag.toNat = 3) else none
    else if pk.length = 65 ∧ (tag.toNat = 4 ∨ tag.toNat = 6 ∨ tag.toNat = 7) then
      let x := beVal (rest.take 32); let y := beVal (rest.drop 32)
      if x < p ∧ y < p ∧ ((tag.toNat = 6 ∨ tag.toNat = 7) → ((y % 2 = 1) = (tag.toNat = 7))) ∧ onCurve (x, y) = true
      then some (x, y) else none
    else none
  | [] => none

/-- `CPubKey::GetLen` and `CPubKey::IsValid`: the header byte announces the length. -/
def pubkeyLen (header : Nat) : Nat :=
  if header = 2 ∨ header = 3 then 33 else if header = 4 ∨ header = 6 ∨ header = 7 then 65 else 0
def pubkeyValid (pk : Bytes) : Bool :=
  match pk with
  | [] => false
  | h :: _ => decide (pubkeyLen h.toNat = pk.length)

/-- `secp256k1_scalar_is_high`: `s > n/2`. -/
def isHighS (s : Nat) : Bool := decide (n / 2 < s)
/-- `secp256k1_ecdsa_signature_normalize`: replace a high `s` by `n - s`. -/
def normalizeS (s : Nat) : Nat := if isHighS s then n - s else s

/-- The scalar read of a big-endian value (`secp256k1_scalar_set_b32`, overflow flagged). -/
def scalarOf (b : Bytes) : Option Nat := let v := beVal b; if v < n then some v else none

/-- `ecdsa_signature_parse_der_lax`: `none` where the parser returns `0`; `some (0, 0)` where an
integer overflows (the "correctly-parsed but invalid" signature); trailing bytes are ignored. -/
def parseDerLax (input : Bytes) : Option (Nat × Nat) :=
  let len := input.length
  let at_ (i : Nat) : Nat := (input.getD i 0).toNat
  -- sequence tag
  if len = 0 ∨ at_ 0 ≠ 0x30 then none else
  let pos := 1
  if pos = len then none else
  let lenbyte := at_ pos
  let pos := pos + 1
  -- sequence length (long form: skip the length bytes)
  let pos? : Option Nat :=
    if 0x80 ≤ lenbyte then
      let lb := lenbyte - 0x80
      if len - pos < lb then none else some (pos + lb)
    else some pos
  match pos? with
  | none => none
  | some pos =>
  -- an integer: tag, length (short or long form with leading zeros stripped, at most 3 bytes)
  let readInt (pos : Nat) : Option (Nat × Nat × Nat) :=  -- (start, length, position after)
    if pos = len ∨ at_ pos ≠ 0x02 then none else
    let pos := pos + 1
    if pos = len then none else
    let lenbyte := at_ pos
    let pos := pos + 1
    if 0x80 ≤ lenbyte then
      let lb := lenbyte - 0x80
      if len - pos < lb then none else
      -- skip leading zero length bytes
      let rec skipZeros (pos lb : Nat) (fuel : Nat) : Nat × Nat :=
        match fuel with
        | 0 => (pos, lb)
        | f + 1 => if 0 < lb ∧ at_ pos = 0 then skipZeros (pos + 1) (lb - 1) f else (pos, lb)
      let (pos, lb) := skipZeros pos lb lb
      if 4 ≤ lb then none else
      let rlen := (List.range lb).foldl (fun acc i => acc * 256 + at_ (pos + i)) 0
      let pos := pos + lb
      if len - pos < rlen then none else some (pos, rlen, pos + rlen)
    else
      if len - pos < lenbyte then none else some (pos, lenbyte, pos + lenbyte)
  match readInt pos with
  | none => none
  | some (rpos, rlen, pos) =>
  match readInt pos with
  | none => none
  | some (spos, slen, _) =>
  -- strip leading zeros, reject more than 32 significant bytes
  let strip (pos len : Nat) : Nat × Nat :=
    let rec go (pos len : Nat) (fuel : Nat) : Nat × Nat :=
      match fuel with
      | 0 => (pos, len)
      | f + 1 => if 0 < len ∧ at_ pos = 0 then go (pos + 1) (len - 1) f else (pos, len)
    go pos len len
  let (rpos, rlen) := strip rpos rlen
  let (spos, slen) := strip spos slen
  if 32 < rlen ∨ 32 < slen then some (0, 0) else
  let r := beVal ((input.drop rpos).take rlen)
  let s := beVal ((input.drop spos).take slen)
  -- `secp256k1_ecdsa_signature_parse_compact`: a scalar at or above `n` is an overflow
  if r < n ∧ s < n then some (r, s) else some (0, 0)

/-- `secp256k1_ecdsa_sig_verify` on a parsed key, a message scalar and a (normalized) signature. -/
def ecdsaVerifyRaw (Q : Point) (e r s : Nat) : Bool :=
  if r = 0 ∨ s = 0 ∨ n ≤ r ∨ n ≤ s then false
  else
    let w := ninv s
    let u1 := e * w % n
    let u2 := r * w % n
    match padd (pmul u1 G) (pmul u2 Q) with
    | none => false
    | some (x, _) => decide (x % n = r)

/-- `CPubKey::Verify(hash, vchSig)`: key validity and parsing, lax DER parsing, S normalization,
then `secp256k1_ecdsa_verify` with the message reduced modulo `n`. -/
def pubkeyVerify (pk : Bytes) (hash : Bytes) (sig : Bytes) : Bool :=
  if !pubkeyValid pk then false
  else match parsePubkey pk with
    | none => false
    | some Q =>
      match parseDerLax sig with
      | none => false
      | some (r, s) => ecdsaVerifyRaw (some Q) (beVal hash % n) r (normalizeS s)

/-- `CPubKey::CheckLowS`. -/
def checkLowS (sig : Bytes) : Bool :=
  match parseDerLax sig with
  | none => false
  | some (_, s) => !isHighS s

/-! ### BIP340 Schnorr -/

/-- `tagged_hash(tag, m) = SHA256(SHA256(tag) || SHA256(tag) || m)`. -/
def taggedHash (tag : Bytes) (m : Bytes) : Bytes :=
  let th := BitcoinSer.sha256 tag
  BitcoinSer.sha256 (th ++ th ++ m)

def ascii (s : String) : Bytes := s.toUTF8.toList.map fun c => BitVec.ofNat 8 c.toNat

/-- `lift_x` of BIP340: the point with abscissa `x` and even `y`. -/
def liftX (x : Nat) : Point := if x < p then liftXParity x false else none

/-- `secp256k1_schnorrsig_verify(sig64, msg, pk32)`. -/
def schnorrVerify (pk32 : Bytes) (msg : Bytes) (sig64 : Bytes) : Bool :=
  if pk32.length ≠ 32 ∨ sig64.length ≠ 64 then false
  else
    let r := beVal (sig64.take 32)
    let s := beVal (sig64.drop 32)
    if p ≤ r ∨ n ≤ s then false
    else match liftX (beVal pk32) with
      | none => false
      | some P =>
        let e := beVal (taggedHash (ascii "BIP0340/challenge") (sig64.take 32 ++ pk32 ++ msg)) % n
        match padd (pmul s G) (pmul ((n - e) % n) (some P)) with
        | none => false
        | some (rx, ry) => decide (ry % 2 = 0 ∧ rx = r)

/-! ### Byte-level scripts (`script/script.cpp`) -/

open BitcoinScript (Instr Script)

def OP_PUSHDATA1 : Nat := 0x4c
def OP_PUSHDATA2 : Nat := 0x4d
def OP_PUSHDATA4 : Nat := 0x4e

/-- `GetScriptOp`: one instruction and the remaining bytes, `none` where it returns `false`. -/
def getOp (s : Bytes) : Option (Instr × Bytes) :=
  match s with
  | [] => none
  | op :: rest =>
    let o := op.toNat
    if o ≤ OP_PUSHDATA4 then
      let sz? : Option (Nat × Bytes) :=
        if o < OP_PUSHDATA1 then some (o, rest)
        else if o = OP_PUSHDATA1 then
          match rest with
          | b :: r => some (b.toNat, r)
          | [] => none
        else if o = OP_PUSHDATA2 then
          if rest.length < 2 then none else some (BitcoinSer.leVal (rest.take 2), rest.drop 2)
        else
          if rest.length < 4 then none else some (BitcoinSer.leVal (rest.take 4), rest.drop 4)
      match sz? with
      | none => none
      | some (sz, r) => if r.length < sz then none else some (.push (r.take sz), r.drop sz)
    else some (.op op, rest)

/-- Parse a whole script; `none` on a malformed push (`SCRIPT_ERR_BAD_OPCODE`). -/
def parseScriptAux : Nat → Bytes → Option Script
  | _, [] => some []
  | 0, _ => none
  | fuel + 1, s =>
    match getOp s with
    | none => none
    | some (i, r) =>
      match parseScriptAux fuel r with
      | none => none
      | some is => some (i :: is)

def parseScript (s : Bytes) : Option Script := parseScriptAux s.length s

/-- `CScript() << vch`: the canonical push of a byte string. -/
def pushBytes (d : Bytes) : Bytes :=
  if d.length < OP_PUSHDATA1 then BitVec.ofNat 8 d.length :: d
  else if d.length ≤ 0xff then [BitVec.ofNat 8 OP_PUSHDATA1, BitVec.ofNat 8 d.length] ++ d
  else if d.length ≤ 0xffff then BitVec.ofNat 8 OP_PUSHDATA2 :: BitcoinSer.leBytes 2 d.length ++ d
  else BitVec.ofNat 8 OP_PUSHDATA4 :: BitcoinSer.leBytes 4 d.length ++ d

/-- `FindAndDelete(script, b)`: at every instruction boundary remove every occurrence of `b`;
returns the result and the number found. -/
def findAndDeleteAux (b : Bytes) : Nat → Bytes → Bytes → Nat → Bytes × Nat
  | 0, s, acc, found => (acc ++ s, found)
  | fuel + 1, s, acc, found =>
    -- strip repeated occurrences at the current position
    let rec strip (s : Bytes) (found : Nat) (f : Nat) : Bytes × Nat :=
      match f with
      | 0 => (s, found)
      | f + 1 => if b.length ≤ s.length ∧ s.take b.length = b then strip (s.drop b.length) (found + 1) f else (s, found)
    let (s, found) := strip s found (s.length + 1)
    match getOp s with
    | none => (acc ++ s, found)
    | some (_, r) =>
      let consumed := s.take (s.length - r.length)
      findAndDeleteAux b fuel r (acc ++ consumed) found

def findAndDelete (script b : Bytes) : Bytes × Nat :=
  if b.isEmpty then (script, 0) else findAndDeleteAux b (script.length + 1) script [] 0

/-- `SerializeScriptCode`: the script code with every `OP_CODESEPARATOR` instruction removed,
written as a byte string. -/
def scriptCodeBytesAux : Nat → Bytes → Bytes
  | 0, s => s
  | fuel + 1, s =>
    match getOp s with
    | none => s
    | some (i, r) =>
      let consumed := s.take (s.length - r.length)
      (if i = .op BitcoinScript.OP_CODESEPARATOR then [] else consumed) ++ scriptCodeBytesAux fuel r

def serScriptCode (sc : Bytes) : Bytes :=
  let body := scriptCodeBytesAux (sc.length + 1) sc
  BitcoinSer.writeCompactSize body.length ++ body

/-! ### Signature hashes (`SignatureHash`) -/

def SIGHASH_ALL : Nat := 1
def SIGHASH_NONE : Nat := 2
def SIGHASH_SINGLE : Nat := 3
def SIGHASH_ANYONECANPAY : Nat := 0x80

/-- `uint256::ONE` in serialized byte order. -/
def uint256One : Bytes := 1 :: List.replicate 31 0

/-- `CTransactionSignatureSerializer::SerializeInput`. -/
def serSigInput (tx : Tx) (scriptCode : Bytes) (nIn : Nat) (anyoneCanPay single none_ : Bool) (nInput : Nat) : Bytes :=
  let nInput := if anyoneCanPay then nIn else nInput
  let i := tx.vin.getD nInput ⟨⟨[], 0⟩, [], 0, []⟩
  BitcoinSer.serOutPoint i.prevout ++
  (if nInput ≠ nIn then BitcoinSer.serBytes [] else serScriptCode scriptCode) ++
  (if nInput ≠ nIn ∧ (single ∨ none_) then BitcoinSer.ser32 0 else BitcoinSer.ser32 i.nSequence)

/-- `CTransactionSignatureSerializer::SerializeOutput`. -/
def serSigOutput (tx : Tx) (nIn : Nat) (single : Bool) (nOutput : Nat) : Bytes :=
  if single ∧ nOutput ≠ nIn then BitcoinSer.serTxOut ⟨-1, []⟩
  else BitcoinSer.serTxOut (tx.vout.getD nOutput ⟨-1, []⟩)

/-- `CTransactionSignatureSerializer::Serialize`. -/
def serSigTx (tx : Tx) (scriptCode : Bytes) (nIn : Nat) (hashType : Nat) : Bytes :=
  let anyoneCanPay := decide (hashType &&& SIGHASH_ANYONECANPAY ≠ 0)
  let single := decide (hashType &&& 0x1f = SIGHASH_SINGLE)
  let none_ := decide (hashType &&& 0x1f = SIGHASH_NONE)
  let nInputs := if anyoneCanPay then 1 else tx.vin.length
  let nOutputs := if none_ then 0 else if single then nIn + 1 else tx.vout.length
  BitcoinSer.ser32 tx.version ++
  BitcoinSer.writeCompactSize nInputs ++
  (List.range nInputs).flatMap (serSigInput tx scriptCode nIn anyoneCanPay single none_) ++
  BitcoinSer.writeCompactSize nOutputs ++
  (List.range nOutputs).flatMap (serSigOutput tx nIn single) ++
  BitcoinSer.ser32 tx.nLockTime

/-- `SignatureHash(scriptCode, tx, nIn, nHashType, amount, SigVersion::BASE)`: the SIGHASH_SINGLE
bug returns `uint256::ONE`; otherwise SHA-256d of the serializer output and the 4-byte hash type. -/
def sigHashLegacy (scriptCode : Bytes) (tx : Tx) (nIn : Nat) (hashType : Nat) : Bytes :=
  if hashType &&& 0x1f = SIGHASH_SINGLE ∧ tx.vout.length ≤ nIn then uint256One
  else BitcoinSer.hash256 (serSigTx tx scriptCode nIn hashType ++ BitcoinSer.ser32 hashType)

/-- `SignatureHash(..., SigVersion::WITNESS_V0)` (BIP143). -/
def sigHashWitnessV0 (scriptCode : Bytes) (tx : Tx) (nIn : Nat) (hashType : Nat) (amount : Int) : Bytes :=
  let anyoneCanPay := hashType &&& SIGHASH_ANYONECANPAY ≠ 0
  let single := hashType &&& 0x1f = SIGHASH_SINGLE
  let none_ := hashType &&& 0x1f = SIGHASH_NONE
  let zero : Bytes := List.replicate 32 0
  let hashPrevouts := if ¬ anyoneCanPay then BitcoinSer.hash256 (tx.vin.flatMap fun i => BitcoinSer.serOutPoint i.prevout) else zero
  let hashSequence := if ¬ anyoneCanPay ∧ ¬ single ∧ ¬ none_ then BitcoinSer.hash256 (tx.vin.flatMap fun i => BitcoinSer.ser32 i.nSequence) else zero
  let hashOutputs :=
    if ¬ single ∧ ¬ none_ then BitcoinSer.hash256 (tx.vout.flatMap BitcoinSer.serTxOut)
    else if single ∧ nIn < tx.vout.length then BitcoinSer.hash256 (BitcoinSer.serTxOut (tx.vout.getD nIn ⟨-1, []⟩))
    else zero
  let i := tx.vin.getD nIn ⟨⟨[], 0⟩, [], 0, []⟩
  BitcoinSer.hash256 (
    BitcoinSer.ser32 tx.version ++ hashPrevouts ++ hashSequence ++
    BitcoinSer.serOutPoint i.prevout ++ BitcoinSer.serBytes scriptCode ++ BitcoinSer.serInt64 amount ++
    BitcoinSer.ser32 i.nSequence ++ hashOutputs ++ BitcoinSer.ser32 tx.nLockTime ++ BitcoinSer.ser32 hashType)

/-! ### Encoding checks (`interpreter.cpp`) -/

/-- `IsValidSignatureEncoding` (strict DER with a trailing hash-type byte). -/
def isValidSignatureEncoding (sig : Bytes) : Bool :=
  let at_ (i : Nat) : Nat := (sig.getD i 0).toNat
  let len := sig.length
  if len < 9 then false
  else if 73 < len then false
  else if at_ 0 ≠ 0x30 then false
  else if at_ 1 ≠ len - 3 then false
  else
    let lenR := at_ 3
    if len ≤ 5 + lenR then false
    else
      let lenS := at_ (5 + lenR)
      if lenR + lenS + 7 ≠ len then false
      else if at_ 2 ≠ 0x02 then false
      else if lenR = 0 then false
      else if 0x80 ≤ at_ 4 then false
      else if 1 < lenR ∧ at_ 4 = 0 ∧ at_ 5 < 0x80 then false
      else if at_ (lenR + 4) ≠ 0x02 then false
      else if lenS = 0 then false
      else if 0x80 ≤ at_ (lenR + 6) then false
      else if 1 < lenS ∧ at_ (lenR + 6) = 0 ∧ at_ (lenR + 7) < 0x80 then false
      else true

/-- `IsLowDERSignature`: strict DER and low S (of the signature without the hash-type byte). -/
def isLowDERSignature (sig : Bytes) : Bool :=
  isValidSignatureEncoding sig && checkLowS sig.dropLast

def isCompressedOrUncompressedPubKey (pk : Bytes) : Bool :=
  match pk with
  | [] => false
  | h :: _ =>
    if pk.length < 33 then false
    else if h.toNat = 4 then decide (pk.length = 65)
    else if h.toNat = 2 ∨ h.toNat = 3 then decide (pk.length = 33)
    else false

def isCompressedPubKey (pk : Bytes) : Bool :=
  match pk with
  | [] => false
  | h :: _ => decide (pk.length = 33) && decide (h.toNat = 2 ∨ h.toNat = 3)

def isDefinedHashtypeSignature (sig : Bytes) : Bool :=
  match sig.getLast? with
  | none => false
  | some b => let t := b.toNat &&& (0xff ^^^ SIGHASH_ANYONECANPAY); decide (SIGHASH_ALL ≤ t ∧ t ≤ SIGHASH_SINGLE)

/-- The `script_verify_flags` consulted by the signature layer. Only `dersig` is a consensus flag on
mainnet; the others are relay policy and are carried for fidelity. -/
structure SigFlags where
  dersig : Bool
  lowS : Bool
  strictenc : Bool
  witnessPubkeyType : Bool
  deriving DecidableEq, Repr

/-- `CheckSignatureEncoding`: `true` where the source returns `true`, `false` where it sets an error. -/
def checkSignatureEncoding (f : SigFlags) (sig : Bytes) : Bool :=
  if sig.isEmpty then true
  else if (f.dersig || f.lowS || f.strictenc) && !isValidSignatureEncoding sig then false
  else if f.lowS && !isLowDERSignature sig then false
  else if f.strictenc && !isDefinedHashtypeSignature sig then false
  else true

inductive SigVersion where
  | base
  | witnessV0
  deriving DecidableEq, Repr

/-- `CheckPubKeyEncoding`. -/
def checkPubKeyEncoding (f : SigFlags) (v : SigVersion) (pk : Bytes) : Bool :=
  if f.strictenc && !isCompressedOrUncompressedPubKey pk then false
  else if f.witnessPubkeyType && v = .witnessV0 && !isCompressedPubKey pk then false
  else true

/-! ### The transaction signature checker -/

/-- `GenericTransactionSignatureChecker::CheckECDSASignature`. -/
def checkECDSASignature (tx : Tx) (nIn : Nat) (amount : Int) (v : SigVersion) (sig pk scriptCode : Bytes) : Bool :=
  if !pubkeyValid pk then false
  else match sig.getLast? with
    | none => false
    | some ht =>
      let sig' := sig.dropLast
      let hashType := ht.toNat
      let sighash := match v with
        | .base => sigHashLegacy scriptCode tx nIn hashType
        | .witnessV0 => sigHashWitnessV0 scriptCode tx nIn hashType amount
      if v = .witnessV0 ∧ amount < 0 then false
      else pubkeyVerify pk sighash sig'

/-- `EvalChecksigPreTapscript`: `FindAndDelete` of the signature push (legacy only), the two encoding
checks (`none` = script error), then the checker's verdict. -/
def checkSigPreTapscript (f : SigFlags) (tx : Tx) (nIn : Nat) (amount : Int) (v : SigVersion)
    (scriptCode : Bytes) (sig pk : Bytes) : Option Bool :=
  let sc := match v with
    | .base => (findAndDelete scriptCode (pushBytes sig)).1
    | .witnessV0 => scriptCode
  if !checkSignatureEncoding f sig ∨ !checkPubKeyEncoding f v pk then none
  else some (checkECDSASignature tx nIn amount v sig pk sc)

def LOCKTIME_THRESHOLD : Nat := 500000000
def SEQUENCE_FINAL : Nat := 0xffffffff
def SEQUENCE_LOCKTIME_DISABLE_FLAG : Nat := 2 ^ 31
def SEQUENCE_LOCKTIME_TYPE_FLAG : Nat := 2 ^ 22
def SEQUENCE_LOCKTIME_MASK : Nat := 0xffff

/-- `GenericTransactionSignatureChecker::CheckLockTime(nLockTime)`. -/
def checkLockTime (tx : Tx) (nIn : Nat) (lockTime : Int) : Bool :=
  if ¬ ((tx.nLockTime < LOCKTIME_THRESHOLD ∧ lockTime < LOCKTIME_THRESHOLD) ∨
        (LOCKTIME_THRESHOLD ≤ tx.nLockTime ∧ (LOCKTIME_THRESHOLD : Int) ≤ lockTime)) then false
  else if (tx.nLockTime : Int) < lockTime then false
  else if (tx.vin.getD nIn ⟨⟨[], 0⟩, [], 0, []⟩).nSequence = SEQUENCE_FINAL then false
  else true

/-- `GenericTransactionSignatureChecker::CheckSequence(nSequence)`. -/
def checkSequence (tx : Tx) (nIn : Nat) (sequence : Int) : Bool :=
  let txToSequence := (tx.vin.getD nIn ⟨⟨[], 0⟩, [], 0, []⟩).nSequence
  if tx.version < 2 then false
  else if txToSequence &&& SEQUENCE_LOCKTIME_DISABLE_FLAG ≠ 0 then false
  else
    let mask := SEQUENCE_LOCKTIME_TYPE_FLAG ||| SEQUENCE_LOCKTIME_MASK
    let txMasked := txToSequence &&& mask
    -- `CScriptNum & mask` on a 5-byte script number: the operand is non-negative here, since
    -- `OP_CHECKSEQUENCEVERIFY` rejects negative values before calling the checker
    let seqMasked := sequence.toNat &&& mask
    if ¬ ((txMasked < SEQUENCE_LOCKTIME_TYPE_FLAG ∧ seqMasked < SEQUENCE_LOCKTIME_TYPE_FLAG) ∨
          (SEQUENCE_LOCKTIME_TYPE_FLAG ≤ txMasked ∧ SEQUENCE_LOCKTIME_TYPE_FLAG ≤ seqMasked)) then false
    else if txMasked < seqMasked then false
    else true

/-- The concrete oracle for the legacy interpreter: Core's hashes, the pre-tapscript signature check
on `scriptCode` (the script being executed, for scripts without `OP_CODESEPARATOR`), and the
lock-time checks of the transaction being validated. -/
def legacyOracle (f : SigFlags) (tx : Tx) (nIn : Nat) (amount : Int) (v : SigVersion) (scriptCode : Bytes) :
    BitcoinScript.Oracle where
  ripemd160 := BitcoinSer.ripemd160
  sha1 := BitcoinSer.sha1
  sha256 := BitcoinSer.sha256
  hash160 := BitcoinSer.hash160
  hash256 := BitcoinSer.hash256
  checkSig := checkSigPreTapscript f tx nIn amount v scriptCode
  checkLockTime := checkLockTime tx nIn
  checkSequence := checkSequence tx nIn

/-- The P2PKH output script as bytes: `OP_DUP OP_HASH160 <h> OP_EQUALVERIFY OP_CHECKSIG`. -/
def p2pkhBytes (h : Bytes) : Bytes := [0x76, 0xa9] ++ pushBytes h ++ [0x88, 0xac]

/-- Two transactions with the same version, outputs, lock time, and the same prevouts and sequence
numbers in order (scriptSigs and witnesses may differ): what the signature hashes may depend on. -/
def sameSkeleton (tx tx' : Tx) : Prop :=
  tx'.version = tx.version ∧ tx'.vout = tx.vout ∧ tx'.nLockTime = tx.nLockTime ∧
  tx'.vin.map (fun i => (i.prevout, i.nSequence)) = tx.vin.map (fun i => (i.prevout, i.nSequence))

/-- The minimal big-endian positive integer encoding DER requires. -/
def minimalInt (v : Bytes) : Prop :=
  v ≠ [] ∧ (v.getD 0 0).toNat < 0x80 ∧ (1 < v.length → (v.getD 0 0).toNat = 0 → 0x80 ≤ (v.getD 1 0).toNat)

/-- The DER layout `30 len 02 |r| r 02 |s| s ht`. -/
def derEncode (r s : Bytes) (ht : Byte) : Bytes :=
  [0x30, BitVec.ofNat 8 (r.length + s.length + 4), 0x02, BitVec.ofNat 8 r.length] ++ r ++
  [0x02, BitVec.ofNat 8 s.length] ++ s ++ [ht]

end BitcoinSig
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: IsValidSignatureEncoding, IsLowDERSignature, IsCompressedOrUncompressedPubKey, IsCompressedPubKey, IsDefinedHashtypeSignature, CheckSignatureEncoding, CheckPubKeyEncoding, FindAndDelete, CTransactionSignatureSerializer, SignatureHash (BASE and WITNESS_V0), EvalChecksigPreTapscript, GenericTransactionSignatureChecker::CheckECDSASignature/CheckLockTime/CheckSequence, src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp; GetScriptOp, src/script/script.cpp; CPubKey::IsValid/Verify/CheckLowS and ecdsa_signature_parse_der_lax, src/pubkey.cpp and pubkey.h; secp256k1_eckey_pubkey_parse (src/secp256k1/src/eckey_impl.h), secp256k1_ecdsa_sig_verify (ecdsa_impl.h), secp256k1_schnorrsig_verify (modules/schnorrsig/main_impl.h); BIP66, BIP143, BIP340 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: Def_BitcoinSig

Scope and ambient types. This file defines, inside a namespace BitcoinSig, a collection of total functions and a few predicates over byte strings and transactions. Throughout, a byte is an 8-bit vector (so a byte's numeric value is an integer in [0,255][0,255][0,255]) and a byte string is a finite list of bytes. Transactions come from the serialization file: a transaction txtxtx has a natural-number field version, a list of inputs vin, a list of outputs vout, and a natural-number field nLockTime; an input has a prevout (an outpoint: a byte string hash and a natural number n), a byte string scriptSig, a natural number nSequence, and a witness (list of byte strings); an output has an integer nValue and a byte string scriptPubKey. None of these fields is bounded by the types: a version or sequence number may be any natural number, an outpoint hash may have any length. Wherever a list is indexed by a possibly out-of-range index, the code uses "get with default", so a default input ⟨⟨[],0⟩,[],0,[]⟩\langle\langle[],0\rangle,[],0,[]\rangle⟨⟨[],0⟩,[],0,[]⟩ (empty prevout hash, prevout index 0, empty scriptSig, sequence 0, no witness) and a default output ⟨−1,[]⟩\langle -1,[]\rangle⟨−1,[]⟩ (value −1-1−1, empty script) silently stand in. The serializers used are: ser32 kkk = the four little-endian bytes of k mod 232k \bmod 2^{32}kmod232; serInt64 zzz = the eight little-endian bytes of z mod 264z \bmod 2^{64}zmod264 (two's complement); writeCompactSize kkk = Bitcoin's compact-size prefix; serBytes bbb = compact size of ∣b∣|b|∣b∣ followed by bbb; serOutPoint ooo = o.hasho.\text{hash}o.hash followed by ser32 o.no.no.n (so a default outpoint serializes to only four zero bytes, not 36); serTxOut ooo = serInt64 of the value followed by serBytes of the script; hash256 = SHA-256 applied twice; leVal reads a byte string as a little-endian number.

Constants p, n, Gx, Gy. p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 (a natural number computed by truncated subtraction, which here is an honest subtraction). nnn is the literal hexadecimal FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141. GxG_xGx​ and GyG_yGy​ are the literal hexadecimals 79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798 and 483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8. Nothing in the file proves these are prime, that (Gx,Gy)(G_x,G_y)(Gx​,Gy​) is on the curve, or that nnn is the order of anything; they are bare numbers.

powModAux and powMod. powModAux mmm is a four-argument recursion on a fuel counter: with fuel 000 it returns the accumulator; with fuel f+1f+1f+1, base bbb, exponent eee, accumulator aaa: if e=0e = 0e=0 it returns aaa; otherwise it recurses with fuel fff, base b2 mod mb^2 \bmod mb2modm, exponent ⌊e/2⌋\lfloor e/2 \rfloor⌊e/2⌋, and accumulator a⋅b mod ma\cdot b \bmod ma⋅bmodm if eee is odd, else aaa. powMod b e mb\,e\,mbem = powModAux mmm with fuel e+1e+1e+1, base b mod mb \bmod mbmodm, exponent eee, accumulator 1 mod m1 \bmod m1modm. Since the exponent halves each step, fuel e+1e+1e+1 is never exhausted before eee reaches 000, so this computes be mod mb^e \bmod mbemodm for m≥1m \geq 1m≥1. For m=0m = 0m=0, Lean's x mod 0=xx \bmod 0 = xxmod0=x, so the function would compute an unreduced power; no caller passes m=0m=0m=0.

finv and ninv. finv aaa = powMod a (p−2) pa\,(p-2)\,pa(p−2)p, i.e. ap−2 mod pa^{p-2} \bmod pap−2modp. For a=0a = 0a=0 this is 000 (the accumulator is multiplied by 000 at the first odd bit, since p−2p-2p−2 is odd). ninv aaa = an−2 mod na^{n-2} \bmod nan−2modn, likewise with ninv 0=00 = 00=0. No reduction of aaa is required beforehand; powMod reduces the base. These are inverses only when ppp, nnn are prime and a≢0a \not\equiv 0a≡0; the file does not state this.

Point, onCurve. A point is either "none" (the point at infinity) or "some (x,y)(x,y)(x,y)" with x,yx, yx,y arbitrary natural numbers, not required to be below ppp or on the curve. onCurve (x,y)(x,y)(x,y) is the Boolean y2 mod p=(x3+7) mod py^2 \bmod p = (x^3 + 7) \bmod py2modp=(x3+7)modp.

padd (affine addition). For points P,QP, QP,Q: if PPP is none the result is QQQ; if QQQ is none the result is PPP (so none +++ none === none). Otherwise, with P=(x1,y1)P = (x_1,y_1)P=(x1​,y1​) and Q=(x2,y2)Q = (x_2,y_2)Q=(x2​,y2​):

  • if x1≡x2(modp)x_1 \equiv x_2 \pmod px1​≡x2​(modp): if y1+y2≡0(modp)y_1 + y_2 \equiv 0 \pmod py1​+y2​≡0(modp) the result is none; otherwise the doubling formulas are used with the coordinates of PPP only: λ=3x12⋅finv(2y1 mod p) mod p\lambda = 3x_1^2 \cdot \mathrm{finv}(2y_1 \bmod p) \bmod pλ=3x12​⋅finv(2y1​modp)modp, x3=(λ2+2(p−(x1 mod p))) mod px_3 = (\lambda^2 + 2(p - (x_1 \bmod p))) \bmod px3​=(λ2+2(p−(x1​modp)))modp, y3=(λ ((x1+p−x3) mod p)+(p−(y1 mod p))) mod py_3 = (\lambda\,((x_1 + p - x_3) \bmod p) + (p - (y_1 \bmod p))) \bmod py3​=(λ((x1​+p−x3​)modp)+(p−(y1​modp)))modp, result (x3,y3)(x_3,y_3)(x3​,y3​). Note the doubling branch is taken whenever the abscissae agree and the ordinates are not negatives mod ppp, even if y1≢y2y_1 \not\equiv y_2y1​≡y2​ (which can only happen for inputs that are not both on the curve); QQQ's ordinate is then ignored. If 2y1≡02y_1 \equiv 02y1​≡0, finv returns 000 and λ=0\lambda = 0λ=0.
  • otherwise (distinct abscissae mod ppp): λ=((y2+p−(y1 mod p)) mod p)⋅finv((x2+p−(x1 mod p)) mod p) mod p\lambda = ((y_2 + p - (y_1 \bmod p)) \bmod p)\cdot \mathrm{finv}((x_2 + p - (x_1 \bmod p)) \bmod p) \bmod pλ=((y2​+p−(y1​modp))modp)⋅finv((x2​+p−(x1​modp))modp)modp, x3=(λ2+(p−(x1 mod p))+(p−(x2 mod p))) mod px_3 = (\lambda^2 + (p - (x_1 \bmod p)) + (p - (x_2 \bmod p))) \bmod px3​=(λ2+(p−(x1​modp))+(p−(x2​modp)))modp, y3=(λ ((x1+p−x3) mod p)+(p−(y1 mod p))) mod py_3 = (\lambda\,((x_1 + p - x_3) \bmod p) + (p - (y_1 \bmod p))) \bmod py3​=(λ((x1​+p−x3​)modp)+(p−(y1​modp)))modp. All outputs have coordinates below ppp; inputs may be unreduced. No on-curve check is performed.

pmulAux, pmul, G. pmulAux with fuel 000 returns the accumulator; with fuel f+1f+1f+1, scalar kkk, point PPP, accumulator AAA: if k=0k = 0k=0 returns AAA, else recurses with fuel fff, scalar ⌊k/2⌋\lfloor k/2\rfloor⌊k/2⌋, point padd P PP\,PPP, accumulator padd A PA\,PAP if kkk odd else AAA. pmul k Pk\,PkP = pmulAux with fuel 257257257, scalar kkk, point PPP, accumulator none: right-to-left double-and-add. With fuel 257 any k<2257k < 2^{257}k<2257 is processed completely; for larger kkk the high bits are silently dropped. GGG = some (Gx,Gy)(G_x, G_y)(Gx​,Gy​).

beVal. The big-endian value of a byte string: fold a↦256a+bytea \mapsto 256a + \text{byte}a↦256a+byte from 000. The empty string has value 000. No length limit.

liftXParity xxx odd. Computes y=(x3+7)(p+1)/4 mod py = (x^3+7)^{(p+1)/4} \bmod py=(x3+7)(p+1)/4modp (integer division for the exponent). If y2 mod p=(x3+7) mod py^2 \bmod p = (x^3+7) \bmod py2modp=(x3+7)modp, returns some (x,y′)(x, y')(x,y′) where y′=yy' = yy′=y if the parity of yyy (as a natural number, i.e. y mod 2=1y \bmod 2 = 1ymod2=1) equals the requested Boolean odd, and y′=(p−y) mod py' = (p - y) \bmod py′=(p−y)modp otherwise; else returns none. Note xxx is not reduced or range-checked here, and the returned abscissa is xxx exactly as given. Edge: if y=0y = 0y=0 (i.e. x3+7≡0x^3+7 \equiv 0x3+7≡0) and odd is true, the returned ordinate is (p−0) mod p=0(p-0) \bmod p = 0(p−0)modp=0, which is even.

parsePubkey. On the empty string: none. On t::restt :: restt::rest (first byte ttt): if the total length is 333333 and t∈{2,3}t \in \{2,3\}t∈{2,3}, let xxx = beVal restrestrest; if x<px < px<p return liftXParity x (t=3)x\,(t = 3)x(t=3) (odd ordinate exactly when t=3t = 3t=3), else none. Else if the total length is 656565 and t∈{4,6,7}t \in \{4,6,7\}t∈{4,6,7}: xxx = beVal of the first 32 bytes of restrestrest, yyy = beVal of the remaining 32; return some (x,y)(x,y)(x,y) if x<px < px<p and y<py < py<p and (if t∈{6,7}t \in \{6,7\}t∈{6,7} then "yyy is odd" iff t=7t = 7t=7) and onCurve (x,y)(x,y)(x,y); else none. In every other case (wrong length for the tag, tag outside {2,3,4,6,7}\{2,3,4,6,7\}{2,3,4,6,7}) none. The tag-444 case has no parity requirement.

pubkeyLen, pubkeyValid. pubkeyLen hhh is 333333 for h∈{2,3}h \in \{2,3\}h∈{2,3}, 656565 for h∈{4,6,7}h \in \{4,6,7\}h∈{4,6,7}, and 000 otherwise. pubkeyValid pkpkpk is false on the empty string and otherwise decides whether pubkeyLen (first byte) equals the actual length. Since a non-empty string has length ≥1≠0\geq 1 \neq 0≥1=0, an unrecognized header always yields false. This is a header/length check only: no curve membership.

isHighS, normalizeS. isHighS sss decides ⌊n/2⌋<s\lfloor n/2 \rfloor < s⌊n/2⌋<s. normalizeS sss = n−sn - sn−s (truncated natural subtraction) if isHighS sss, else sss. For s≥ns \geq ns≥n (high), n−sn - sn−s truncates to 000.

scalarOf. Reads bbb big-endian; returns some vvv if v<nv < nv<n, else none. This definition is not used anywhere else in the file.

parseDerLax (lax DER parser). Input: a byte string of length ℓ\ellℓ; at(i)(i)(i) denotes the byte at index iii or 000 if out of range. Control flow, in order:

  1. If ℓ=0\ell = 0ℓ=0 or at(0)≠(0) \neq(0)= 0x30: none.
  2. Set pos=1pos = 1pos=1. If pos=ℓpos = \ellpos=ℓ: none. Read lenbytelenbytelenbyte = at(1)(1)(1); pos=2pos = 2pos=2.
  3. Sequence length: if lenbyte≥lenbyte \geqlenbyte≥ 0x80, let lb=lenbyte−lb = lenbyte - lb=lenbyte− 0x80; if ℓ−pos<lb\ell - pos < lbℓ−pos<lb (natural subtraction; ℓ≥2\ell \geq 2ℓ≥2 here) then none, else pos=2+lbpos = 2 + lbpos=2+lb — the lblblb length bytes are skipped, their value is never read. If lenbyte<lenbyte <lenbyte< 0x80, pospospos stays 222 and the short-form length value is ignored entirely. (Note lenbyte=lenbyte =lenbyte= 0x80 gives lb=0lb = 0lb=0 and is accepted.)
  4. readInt(pos)(pos)(pos), used twice: if pos=ℓpos = \ellpos=ℓ or at(pos)≠(pos) \neq(pos)= 0x02: none. pos++pos{+}{+}pos++; if pos=ℓpos = \ellpos=ℓ: none. lenbytelenbytelenbyte = at(pos)(pos)(pos); pos++pos{+}{+}pos++. If lenbyte≥lenbyte \geqlenbyte≥ 0x80: lb=lenbyte−lb = lenbyte - lb=lenbyte− 0x80; if ℓ−pos<lb\ell - pos < lbℓ−pos<lb: none; then skip up to lblblb leading zero bytes among the length bytes (each skip increments pospospos and decrements lblblb); if the remaining lb≥4lb \geq 4lb≥4: none; the integer's length rlenrlenrlen is the big-endian value of the remaining lblblb bytes (zero if lb=0lb = 0lb=0); pospospos advances past them; if ℓ−pos<rlen\ell - pos < rlenℓ−pos<rlen: none; else return (start =pos= pos=pos, length =rlen= rlen=rlen, end =pos+rlen= pos + rlen=pos+rlen). If lenbyte<lenbyte <lenbyte< 0x80: if ℓ−pos<lenbyte\ell - pos < lenbyteℓ−pos<lenbyte: none; else return (pospospos, lenbytelenbytelenbyte, pos+lenbytepos + lenbytepos+lenbyte).
  5. First readInt at pospospos gives (rpos,rlen,pos′)(rpos, rlen, pos')(rpos,rlen,pos′) or none ⇒\Rightarrow⇒ none. Second readInt at pos′pos'pos′ gives (spos,slen,_)(spos, slen, \_)(spos,slen,_) or none ⇒\Rightarrow⇒ none; the end position of the second integer is discarded, so any trailing bytes after SSS are ignored.
  6. Strip leading zero bytes from each of RRR and SSS (advancing the start, shrinking the length, fuel = the length).
  7. If the stripped rlen>32rlen > 32rlen>32 or slen>32slen > 32slen>32: some (0,0)(0,0)(0,0).
  8. rrr = beVal of the rlenrlenrlen bytes at rposrposrpos, sss likewise. If r<nr < nr<n and s<ns < ns<n: some (r,s)(r,s)(r,s); otherwise some (0,0)(0,0)(0,0). So none is returned only for structural failures (tags, lengths running past the end, a length-of-length of 4 or more bytes); a zero-length integer parses as 000; an all-zero or too-long or ≥n\geq n≥n integer yields the pair (0,0)(0,0)(0,0), indistinguishable from a signature that genuinely encodes r=s=0r = s = 0r=s=0.

ecdsaVerifyRaw Q e r sQ\,e\,r\,sQers. QQQ is a point (possibly none), e,r,se, r, se,r,s natural numbers. If r=0r = 0r=0 or s=0s = 0s=0 or r≥nr \geq nr≥n or s≥ns \geq ns≥n: false. Else w=w = w= ninv sss, u1=ew mod nu_1 = e w \bmod nu1​=ewmodn, u2=rw mod nu_2 = r w \bmod nu2​=rwmodn, and R=R = R= padd (pmul u1 Gu_1\,Gu1​G) (pmul u2 Qu_2\,Qu2​Q). If RRR is none: false; if R=(x,_)R = (x, \_)R=(x,_): the Boolean x mod n=rx \bmod n = rxmodn=r. eee is used as given (not reduced here). If QQQ is none, R=u1GR = u_1 GR=u1​G.

pubkeyVerify pk hash sigpk\,hash\,sigpkhashsig. If not pubkeyValid pkpkpk: false. Else if parsePubkey pkpkpk is none: false. Else with QQQ the parsed point: if parseDerLax sigsigsig is none: false; else with (r,s)(r,s)(r,s): ecdsaVerifyRaw (some QQQ) (beVal hash mod nhash \bmod nhashmodn) rrr (normalizeS sss). The message is the big-endian value of the byte string hashhashhash reduced mod nnn; hashhashhash has no length requirement. In particular the constant uint256One below, read this way, is 25631=2248256^{31} = 2^{248}25631=2248, not 111. The SSS value is always normalized to the low half before verification, so a high-SSS signature verifies iff its low-SSS twin does.

checkLowS sigsigsig. If parseDerLax sigsigsig is none: false; else true iff the parsed sss is not high. Note that the overflow result (0,0)(0,0)(0,0) has s=0s = 0s=0, so a signature with an overflowing or over-long SSS (or RRR) passes checkLowS.

taggedHash, ascii, liftX. taggedHash tag mtag\,mtagm = SHA-256(h ∥ h ∥ m)(h \,\|\, h \,\|\, m)(h∥h∥m) with hhh = SHA-256(tag)(tag)(tag). ascii sss = the UTF-8 bytes of the string sss, each truncated to 8 bits. liftX xxx = liftXParity xxx false (even ordinate) if x<px < px<p, else none.

schnorrVerify pk32 msg sig64pk_{32}\,msg\,sig_{64}pk32​msgsig64​. If ∣pk32∣≠32|pk_{32}| \neq 32∣pk32​∣=32 or ∣sig64∣≠64|sig_{64}| \neq 64∣sig64​∣=64: false. rrr = big-endian value of the first 32 bytes of the signature, sss = of the last 32. If r≥pr \geq pr≥p or s≥ns \geq ns≥n: false. PPP = liftX(big-endian pk32pk_{32}pk32​); none ⇒\Rightarrow⇒ false. eee = big-endian value of taggedHash(ascii "BIP0340/challenge") (first 32 signature bytes ∥\|∥ pk32pk_{32}pk32​ ∥\|∥ msgmsgmsg), reduced mod nnn. RRR = padd (pmul s Gs\,GsG) (pmul ((n−e) mod n)((n - e) \bmod n)((n−e)modn) (some PPP)). If RRR is none: false; if R=(rx,ry)R = (r_x, r_y)R=(rx​,ry​): the Boolean (ryr_yry​ even and rx=rr_x = rrx​=r). msgmsgmsg has no length constraint.

OP_PUSHDATA1/2/4. The numbers 0x4c, 0x4d, 0x4e.

getOp sss. On the empty string: none. On op::restop :: restop::rest with ooo the value of opopop: if o≤o \leqo≤ 0x4e, determine a size and remainder: o<o <o< 0x4c ⇒\Rightarrow⇒ size ooo, remainder restrestrest; o=o =o= 0x4c ⇒\Rightarrow⇒ size = next byte, remainder after it, none if restrestrest is empty; o=o =o= 0x4d ⇒\Rightarrow⇒ size = little-endian value of the next 2 bytes, none if fewer than 2; otherwise (o=o =o= 0x4e) size = little-endian value of the next 4 bytes, none if fewer than 4. Then if the remainder is shorter than the size: none; else some (push of the first size bytes, the rest). If o>o >o> 0x4e: some (op opopop, restrestrest). So byte 0x00 is a push of the empty string.

parseScriptAux, parseScript. parseScriptAux with any fuel and empty input: some [][][]. Fuel 000 and non-empty input: none. Fuel f+1f+1f+1: getOp; none ⇒\Rightarrow⇒ none; else parse the remainder with fuel fff and prepend the instruction. parseScript sss = parseScriptAux with fuel ∣s∣|s|∣s∣. Since every getOp consumes at least one byte, the fuel is sufficient; the result is none exactly when some push runs past the end of the data.

pushBytes ddd. If ∣d∣<|d| <∣d∣< 0x4c: the byte ∣d∣|d|∣d∣ followed by ddd (so pushBytes [][][] = [[[0x00]]]). Else if ∣d∣≤255|d| \leq 255∣d∣≤255: 0x4c, byte ∣d∣|d|∣d∣, ddd. Else if ∣d∣≤65535|d| \leq 65535∣d∣≤65535: 0x4d, two little-endian length bytes, ddd. Else 0x4e, four little-endian length bytes, ddd (length bytes are truncated mod 2322^{32}232 for absurdly long ddd).

findAndDeleteAux, findAndDelete. findAndDelete script bscript\,bscriptb: if bbb is empty, (script,0)(script, 0)(script,0); else findAndDeleteAux bbb with fuel ∣script∣+1|script| + 1∣script∣+1, remaining =script= script=script, accumulator [][][], count 000. findAndDeleteAux: with fuel 000 returns (accumulator ∥\|∥ remaining, count). With fuel f+1f+1f+1: first strip: as long as bbb is a byte-prefix of the remaining string (and ∣b∣≤|b| \leq∣b∣≤ remaining length), drop ∣b∣|b|∣b∣ bytes and increment the count (fuel for this inner loop = remaining length +1+1+1, which suffices). Then getOp on what remains: none ⇒\Rightarrow⇒ (accumulator ∥\|∥ remaining, count) — a malformed tail is appended verbatim; some (_,r)(\_, r)(_,r) ⇒\Rightarrow⇒ the consumed bytes (those before rrr) are appended to the accumulator and the recursion continues on rrr with fuel fff. So bbb is matched as raw bytes at each instruction boundary (including immediately after a previous deletion), not as a parsed instruction. Each round removes or consumes at least one byte, so the outer fuel suffices.

scriptCodeBytesAux, serScriptCode. scriptCodeBytesAux with fuel 000 returns the input unchanged; otherwise getOp; none ⇒\Rightarrow⇒ the input unchanged (malformed tail kept verbatim); some (i,r)(i, r)(i,r) ⇒\Rightarrow⇒ (the consumed bytes, or [][][] if iii is the opcode instruction with byte 0xab, i.e. OP_CODESEPARATOR) ∥\|∥ recursion on rrr. serScriptCode scscsc = compact size of the length of the stripped body, followed by the body (fuel ∣sc∣+1|sc|+1∣sc∣+1).

SIGHASH_* constants and uint256One. SIGHASH_ALL =1= 1=1, SIGHASH_NONE =2= 2=2, SIGHASH_SINGLE =3= 3=3, SIGHASH_ANYONECANPAY =128= 128=128. uint256One = the byte 111 followed by 31 zero bytes.

serSigInput tx scriptCode nIn acp single none nInputtx\,scriptCode\,nIn\,acp\,single\,none\,nInputtxscriptCodenInacpsinglenonenInput. First, if acpacpacp then nInput:=nInnInput := nInnInput:=nIn. Let iii = the nInputnInputnInput-th input of txtxtx or the default input. Output: serOutPoint i.prevouti.\text{prevout}i.prevout ∥\|∥ (if nInput≠nInnInput \neq nInnInput=nIn then serBytes [][][] =[= [=[0x00]]] else serScriptCode scriptCodescriptCodescriptCode) ∥\|∥ (if nInput≠nInnInput \neq nInnInput=nIn and (singlesinglesingle or nonenonenone) then ser32 000 else ser32 i.nSequencei.\text{nSequence}i.nSequence). The input's own scriptSig and witness are never serialized.

serSigOutput tx nIn single nOutputtx\,nIn\,single\,nOutputtxnInsinglenOutput. If singlesinglesingle and nOutput≠nInnOutput \neq nInnOutput=nIn: serTxOut ⟨−1,[]⟩\langle -1, [] \rangle⟨−1,[]⟩ (eight 0xff bytes then 0x00); else serTxOut of the nOutputnOutputnOutput-th output, or of the default ⟨−1,[]⟩\langle -1,[]\rangle⟨−1,[]⟩ if out of range.

serSigTx tx scriptCode nIn hashTypetx\,scriptCode\,nIn\,hashTypetxscriptCodenInhashType. acpacpacp := (hashType&128≠0hashType \mathbin{\&} 128 \neq 0hashType&128=0); singlesinglesingle := (hashType&31=3hashType \mathbin{\&} 31 = 3hashType&31=3); nonenonenone := (hashType&31=2hashType \mathbin{\&} 31 = 2hashType&31=2). nInputsnInputsnInputs = 111 if acpacpacp else ∣vin∣|vin|∣vin∣. nOutputsnOutputsnOutputs = 000 if nonenonenone, else nIn+1nIn + 1nIn+1 if singlesinglesingle, else ∣vout∣|vout|∣vout∣. Output, in order: ser32 tx.versiontx.\text{version}tx.version ∥\|∥ compact size nInputsnInputsnInputs ∥\|∥ concatenation of serSigInput for nInput=0,…,nInputs−1nInput = 0,\dots,nInputs-1nInput=0,…,nInputs−1 ∥\|∥ compact size nOutputsnOutputsnOutputs ∥\|∥ concatenation of serSigOutput for nOutput=0,…,nOutputs−1nOutput = 0, \dots, nOutputs - 1nOutput=0,…,nOutputs−1 ∥\|∥ ser32 tx.nLockTimetx.\text{nLockTime}tx.nLockTime. The hash type is not appended here. If nIn≥∣vin∣nIn \geq |vin|nIn≥∣vin∣ and not acpacpacp, no input ever receives the script code; if acpacpacp, the single serialized input is the default input (4-byte outpoint). Hash types whose low five bits are not 222 or 333 (e.g. 000, 111, or 444–313131) all serialize as "all outputs".

sigHashLegacy scriptCode tx nIn hashTypescriptCode\,tx\,nIn\,hashTypescriptCodetxnInhashType. If hashType&31=3hashType \mathbin{\&} 31 = 3hashType&31=3 and ∣vout∣≤nIn|vout| \leq nIn∣vout∣≤nIn: uint256One. Otherwise hash256(serSigTx tx scriptCode nIn hashTypetx\,scriptCode\,nIn\,hashTypetxscriptCodenInhashType ∥\|∥ ser32 hashTypehashTypehashType). Fields serialized: version; input count; per input: prevout, script code (or empty), sequence (or zero); output count; per output: value and script (or −1-1−1/empty); lock time; then the 4-byte hash type. hashTypehashTypehashType is an unbounded natural number here; ser32 truncates it.

sigHashWitnessV0 scriptCode tx nIn hashType amountscriptCode\,tx\,nIn\,hashType\,amountscriptCodetxnInhashTypeamount. With acpacpacp, singlesinglesingle, nonenonenone as above and zerozerozero = 32 zero bytes: hashPrevoutshashPrevoutshashPrevouts = hash256 of the concatenation of serOutPoint over all inputs if not acpacpacp, else zerozerozero. hashSequencehashSequencehashSequence = hash256 of the concatenation of ser32 of every input's sequence if not acpacpacp and not singlesinglesingle and not nonenonenone, else zerozerozero. hashOutputshashOutputshashOutputs = hash256 of the concatenation of serTxOut over all outputs if neither singlesinglesingle nor nonenonenone; else if singlesinglesingle and nIn<∣vout∣nIn < |vout|nIn<∣vout∣ (strict): hash256(serTxOut of output nInnInnIn); else zerozerozero. Let iii = input nInnInnIn or the default. Result: hash256(ser32 version ∥\|∥ hashPrevoutshashPrevoutshashPrevouts ∥\|∥ hashSequencehashSequencehashSequence ∥\|∥ serOutPoint i.prevouti.\text{prevout}i.prevout ∥\|∥ serBytes scriptCodescriptCodescriptCode ∥\|∥ serInt64 amountamountamount ∥\|∥ ser32 i.nSequencei.\text{nSequence}i.nSequence ∥\|∥ hashOutputshashOutputshashOutputs ∥\|∥ ser32 nLockTime ∥\|∥ ser32 hashTypehashTypehashType). Here the script code is serialized verbatim with serBytes (no OP_CODESEPARATOR removal, unlike the legacy path), there is no uint256One special case, and a negative amountamountamount is serialized in two's complement without complaint.

isValidSignatureEncoding sigsigsig. With ℓ=∣sig∣\ell = |sig|ℓ=∣sig∣ and at as before: false if ℓ<9\ell < 9ℓ<9; false if ℓ>73\ell > 73ℓ>73; false if at(0)≠(0) \neq(0)= 0x30; false if at(1)≠ℓ−3(1) \neq \ell - 3(1)=ℓ−3; let lenRlenRlenR = at(3)(3)(3); false if ℓ≤5+lenR\ell \leq 5 + lenRℓ≤5+lenR; let lenSlenSlenS = at(5+lenR)(5 + lenR)(5+lenR); false if lenR+lenS+7≠ℓlenR + lenS + 7 \neq \elllenR+lenS+7=ℓ; false if at(2)≠(2) \neq(2)= 0x02; false if lenR=0lenR = 0lenR=0; false if at(4)≥(4) \geq(4)≥ 0x80; false if lenR>1lenR > 1lenR>1 and at(4)=0(4) = 0(4)=0 and at(5)<(5) <(5)< 0x80; false if at(lenR+4)≠(lenR + 4) \neq(lenR+4)= 0x02; false if lenS=0lenS = 0lenS=0; false if at(lenR+6)≥(lenR+6) \geq(lenR+6)≥ 0x80; false if lenS>1lenS > 1lenS>1 and at(lenR+6)=0(lenR+6) = 0(lenR+6)=0 and at(lenR+7)<(lenR+7) <(lenR+7)< 0x80; otherwise true. The final byte (hash type) is never examined. Note that the ℓ≤73\ell \leq 73ℓ≤73 bound forces lenR+lenS≤66lenR + lenS \leq 66lenR+lenS≤66.

isLowDERSignature sigsigsig. isValidSignatureEncoding sigsigsig and checkLowS (sigsigsig with its last byte removed). Both conjuncts are evaluated on the same sigsigsig argument; only the second drops the hash-type byte.

isCompressedOrUncompressedPubKey pkpkpk. Empty: false. Otherwise with first byte hhh: false if ∣pk∣<33|pk| < 33∣pk∣<33; if h=4h = 4h=4: ∣pk∣=65|pk| = 65∣pk∣=65; if h∈{2,3}h \in \{2,3\}h∈{2,3}: ∣pk∣=33|pk| = 33∣pk∣=33; else false (so hybrid 666/777 keys are rejected here even though parsePubkey accepts them).

isCompressedPubKey pkpkpk. Non-empty, length 333333, and first byte in {2,3}\{2,3\}{2,3}.

isDefinedHashtypeSignature sigsigsig. Empty: false. Otherwise with bbb the last byte: t=b&(t = b \mathbin{\&} (t=b&(0xff ⊕128)=b&127\oplus 128) = b \mathbin{\&} 127⊕128)=b&127; true iff 1≤t≤31 \leq t \leq 31≤t≤3.

SigFlags. A record of four Booleans: dersig, lowS, strictenc, witnessPubkeyType.

checkSignatureEncoding f sigf\,sigfsig. If sigsigsig is empty: true. Else if (fff.dersig or fff.lowS or fff.strictenc) and not isValidSignatureEncoding sigsigsig: false. Else if fff.lowS and not isLowDERSignature sigsigsig: false. Else if fff.strictenc and not isDefinedHashtypeSignature sigsigsig: false. Else true. With all four flags false every signature passes.

SigVersion. Two constructors: base and witnessV0.

checkPubKeyEncoding f v pkf\,v\,pkfvpk. If fff.strictenc and not isCompressedOrUncompressedPubKey pkpkpk: false. Else if fff.witnessPubkeyType and vvv = witnessV0 and not isCompressedPubKey pkpkpk: false. Else true. With both relevant flags false, even the empty key passes.

checkECDSASignature tx nIn amount v sig pk scriptCodetx\,nIn\,amount\,v\,sig\,pk\,scriptCodetxnInamountvsigpkscriptCode. (Note the argument order: signature, then key, then script code.) If not pubkeyValid pkpkpk: false. If sigsigsig is empty: false. Otherwise let hththt be the last byte of sigsigsig, sig′sig'sig′ = sigsigsig without its last byte, hashType=hthashType = hthashType=ht (a number in [0,255][0,255][0,255]), and sighashsighashsighash = sigHashLegacy scriptCode tx nIn hashTypescriptCode\,tx\,nIn\,hashTypescriptCodetxnInhashType if vvv = base, or sigHashWitnessV0 scriptCode tx nIn hashType amountscriptCode\,tx\,nIn\,hashType\,amountscriptCodetxnInhashTypeamount if vvv = witnessV0. If vvv = witnessV0 and amount<0amount < 0amount<0: false. Else pubkeyVerify pk sighash sig′pk\,sighash\,sig'pksighashsig′. The amount is ignored entirely in the base case; pubkeyValid is checked here and again inside pubkeyVerify.

checkSigPreTapscript f tx nIn amount v scriptCode sig pkf\,tx\,nIn\,amount\,v\,scriptCode\,sig\,pkftxnInamountvscriptCodesigpk. Let scscsc = the first component of findAndDelete scriptCodescriptCodescriptCode (pushBytes sigsigsig) if vvv = base, or scriptCodescriptCodescriptCode unchanged if vvv = witnessV0. If checkSignatureEncoding f sigf\,sigfsig is false or checkPubKeyEncoding f v pkf\,v\,pkfvpk is false: none. Otherwise some (checkECDSASignature tx nIn amount v sig pk sctx\,nIn\,amount\,v\,sig\,pk\,sctxnInamountvsigpksc). Note that for the empty signature in base mode, pushBytes [][][] = [[[0x00]]], so every OP_0 byte at an instruction boundary of scriptCodescriptCodescriptCode is deleted before (the inevitably false) verification.

Lock-time constants. LOCKTIME_THRESHOLD =500 000 000= 500\,000\,000=500000000, SEQUENCE_FINAL =232−1= 2^{32}-1=232−1, SEQUENCE_LOCKTIME_DISABLE_FLAG =231= 2^{31}=231, SEQUENCE_LOCKTIME_TYPE_FLAG =222= 2^{22}=222, SEQUENCE_LOCKTIME_MASK =65535= 65535=65535.

checkLockTime tx nIn lockTimetx\,nIn\,lockTimetxnInlockTime (with lockTimelockTimelockTime an integer, TTT the threshold). False unless (nLockTime <T< T<T and lockTime<TlockTime < TlockTime<T) or (nLockTime ≥T\geq T≥T and lockTime≥TlockTime \geq TlockTime≥T). Then false if nLockTime <lockTime< lockTime<lockTime (comparison in the integers). Then false if the sequence of input nInnInnIn (or 000 for the default input, which is therefore never "final") equals SEQUENCE_FINAL. Else true. A negative lockTimelockTimelockTime is simply "below the threshold" and, being ≤\leq≤ nLockTime, passes the second test.

checkSequence tx nIn sequencetx\,nIn\,sequencetxnInsequence. Let txSeqtxSeqtxSeq = the sequence of input nInnInnIn (or 000). False if tx.version<2tx.\text{version} < 2tx.version<2 (version is an unbounded natural number, so e.g. 232−12^{32}-1232−1 counts as ≥2\geq 2≥2). False if txSeq&231≠0txSeq \mathbin{\&} 2^{31} \neq 0txSeq&231=0. Let mask=222∣65535mask = 2^{22} \mathbin{|} 65535mask=222∣65535, txMasked=txSeq&masktxMasked = txSeq \mathbin{\&} masktxMasked=txSeq&mask, seqMasked=(toNat sequence)&maskseqMasked = (\text{toNat}\ sequence) \mathbin{\&} maskseqMasked=(toNat sequence)&mask where a negative sequencesequencesequence becomes 000. False unless both masked values are <222< 2^{22}<222 or both are ≥222\geq 2^{22}≥222. False if txMasked<seqMaskedtxMasked < seqMaskedtxMasked<seqMasked. Else true. The disable flag of the argument sequencesequencesequence is not consulted (a comment defers this to the caller).

legacyOracle f tx nIn amount v scriptCodef\,tx\,nIn\,amount\,v\,scriptCodeftxnInamountvscriptCode. A record whose hash fields are the serialization file's RIPEMD-160, SHA-1, SHA-256, Hash160, Hash256; whose checkSig is checkSigPreTapscript f tx nIn amount v scriptCodef\,tx\,nIn\,amount\,v\,scriptCodeftxnInamountvscriptCode awaiting the two remaining arguments (signature, key); whose checkLockTime is checkLockTime tx nIntx\,nIntxnIn; and whose checkSequence is checkSequence tx nIntx\,nIntxnIn.

p2pkhBytes hhh. [[[0x76, 0xa9]]] ∥\|∥ pushBytes hhh ∥\|∥ [[[0x88, 0xac]]].

sameSkeleton tx tx′tx\,tx'txtx′ (a proposition). tx′.version=tx.versiontx'.\text{version} = tx.\text{version}tx′.version=tx.version, tx′.vout=tx.vouttx'.\text{vout} = tx.\text{vout}tx′.vout=tx.vout, tx′.nLockTime=tx.nLockTimetx'.\text{nLockTime} = tx.\text{nLockTime}tx′.nLockTime=tx.nLockTime, and the lists obtained by mapping each input to the pair (prevout, nSequence) are equal — hence the input counts agree; scriptSigs and witnesses are unconstrained.

minimalInt vvv (a proposition). v≠[]v \neq []v=[], the first byte is <128< 128<128, and if ∣v∣>1|v| > 1∣v∣>1 and the first byte is 000 then the second byte is ≥128\geq 128≥128. The single byte [0][0][0] satisfies it; there is no upper bound on ∣v∣|v|∣v∣.

derEncode r s htr\,s\,htrsht. [[[0x30, (∣r∣+∣s∣+4) mod 256(|r|+|s|+4) \bmod 256(∣r∣+∣s∣+4)mod256, 0x02, ∣r∣ mod 256]|r| \bmod 256]∣r∣mod256] ∥\|∥ rrr ∥\|∥ [[[0x02, ∣s∣ mod 256]|s| \bmod 256]∣s∣mod256] ∥\|∥ sss ∥\|∥ [ht][ht][ht]; total length ∣r∣+∣s∣+7|r| + |s| + 7∣r∣+∣s∣+7.

Observations the auditor may wish to weigh (descriptive only). (i) scalarOf is dead code. (ii) checkLowS returns true on the (0,0)(0,0)(0,0) overflow pair. (iii) The lax parser never reads the sequence-length value and ignores trailing bytes after SSS. (iv) uint256One read by pubkeyVerify is the scalar 2248 mod n2^{248} \bmod n2248modn. (v) The legacy sighash strips OP_CODESEPARATOR from the script code; the witness-v0 sighash does not. (vi) isCompressedOrUncompressedPubKey rejects hybrid keys that parsePubkey accepts. (vii) The default input serializes to a 4-byte outpoint. (viii) checkSequence ignores the disable flag of its argument and maps negative arguments to 000. (ix) padd's doubling branch ignores QQQ's ordinate. (x) sigHashWitnessV0 uses a strict < for the SINGLE output index, while sigHashLegacy uses ≤ for its special case; the two are complementary.

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