Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The multisig signatures are read off the stack layout

Proved
BitcoinScriptV2.multisigSigs_eq

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

bitcoinbitcoin-mainnetcheckmultisigcodeseparatorconsensusfindanddeleteformal-verificationinterpreterscriptsighash

For a stack nk :: keys ++ ns :: sigs ++ rest with nk, ns decoding to the lengths of keys and sigs: multisigSigs … = sigs.

Preamble
import Definitions.Def_BitcoinScriptV2
import Definitions.Def_BitcoinScript
open BitcoinScriptV2 BitcoinScript BitcoinSig BitcoinVerify
Formal statement
theorem BitcoinScriptV2.multisigSigs_eq (nk ns : BitcoinScript.Bytes) (keys sigs rest : List BitcoinScript.Bytes)
    (nKeys nSigs : Int) (hk : BitcoinScript.toNum false BitcoinScript.nDefaultMaxNumSize nk = some nKeys)
    (hkl : keys.length = nKeys.toNat) (hn : BitcoinScript.toNum false BitcoinScript.nDefaultMaxNumSize ns = some nSigs)
    (hsl : sigs.length = nSigs.toNat) :
    BitcoinScriptV2.multisigSigs (nk :: (keys ++ ns :: (sigs ++ rest))) = sigs := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: EvalScript (pbegincodehash, OP_CODESEPARATOR at interpreter.cpp:1058-1066, OP_CHECKSIG's scriptCode and FindAndDelete at :339-343 / the CHECKSIG case, OP_CHECKMULTISIG's deletion of every signature at :1152-1159), SignatureHash (SigVersion::BASE), VerifyScript (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); Core's script_tests.json, tx_valid.json, tx_invalid.json at the same revision
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: BitcoinScriptV2.multisigSigs_eq

Statement. Let nk,nsn_k, n_snk​,ns​ be byte strings, KKK, Sg\mathit{Sg}Sg, RRR lists of byte strings, and NK,NSN_K, N_SNK​,NS​ integers. Assume

  1. toNum(nk)=some(NK)\mathrm{toNum}(n_k) = \mathsf{some}(N_K)toNum(nk​)=some(NK​);
  2. ∣K∣=NK+=max⁡(NK,0)|K| = N_K^{+} = \max(N_K, 0)∣K∣=NK+​=max(NK​,0);
  3. toNum(ns)=some(NS)\mathrm{toNum}(n_s) = \mathsf{some}(N_S)toNum(ns​)=some(NS​);
  4. ∣Sg∣=NS+=max⁡(NS,0)|\mathit{Sg}| = N_S^{+} = \max(N_S, 0)∣Sg∣=NS+​=max(NS​,0).

Then

multisigSigs([nk]+ ⁣ ⁣+K+ ⁣ ⁣+[ns]+ ⁣ ⁣+Sg+ ⁣ ⁣+R)=Sg,\mathrm{multisigSigs}\big([n_k] \mathbin{+\!\!+} K \mathbin{+\!\!+} [n_s] \mathbin{+\!\!+} \mathit{Sg} \mathbin{+\!\!+} R\big) = \mathit{Sg},multisigSigs([nk​]++K++[ns​]++Sg++R)=Sg,

where the stack is listed top first: nkn_knk​ on top, then the elements of KKK, then nsn_sns​, then the elements of Sg\mathit{Sg}Sg, then those of RRR.

Notes on the literal content: NKN_KNK​ and NSN_SNS​ are not required to be non-negative, at most 202020, or to satisfy NS≤NKN_S \le N_KNS​≤NK​; a negative count forces the corresponding list (KKK or Sg\mathit{Sg}Sg) to be empty. RRR is arbitrary (it may be empty, i.e. no dummy element is required). Hypotheses 1 and 3 require ∣nk∣≤4|n_k| \le 4∣nk​∣≤4 and ∣ns∣≤4|n_s| \le 4∣ns​∣≤4, with the values read as described below (no minimal-encoding requirement).


Unfolded definitions used above

Basic objects and notation

  • A byte is an 8-bit word, identified with its value in {0,…,255}\{0,\dots,255\}{0,…,255} and written in hexadecimal (e.g. 0xab\texttt{0xab}0xab). B∗\mathcal B^*B∗ is the set of finite byte strings (lists of bytes); ∣x∣|x|∣x∣ is the length, x+ ⁣ ⁣+yx \mathbin{+\!\!+} yx++y concatenation, ε\varepsilonε the empty string.
  • takek(x)\mathrm{take}_k(x)takek​(x) is the first min⁡(k,∣x∣)\min(k,|x|)min(k,∣x∣) entries of a list xxx; dropk(x)\mathrm{drop}_k(x)dropk​(x) is what is left after removing the first kkk entries, which is the empty list when k≥∣x∣k \ge |x|k≥∣x∣.
  • For a 0-based index ppp, the statement "x[p]=cx[p] = cx[p]=c" means: p<∣x∣p < |x|p<∣x∣ and the entry of xxx at index ppp is ccc. Indexing out of range yields no value, so such an equation can only hold with p<∣x∣p<|x|p<∣x∣.
  • A partial result is either none\mathsf{none}none or some(y)\mathsf{some}(y)some(y). Applying a function ggg "under some\mathsf{some}some" (mapg\mathrm{map}_gmapg​) sends none↦none\mathsf{none}\mapsto\mathsf{none}none↦none and some(y)↦some(g(y))\mathsf{some}(y)\mapsto\mathsf{some}(g(y))some(y)↦some(g(y)).
  • An instruction is either push(d)\mathrm{push}(d)push(d), carrying a data string d∈B∗d\in\mathcal B^*d∈B∗, or op(c)\mathrm{op}(c)op(c), carrying an opcode byte ccc. A script (parsed) is a finite list of instructions.
  • Opcode bytes named below: OP_16=0x60\texttt{OP\_16}=\texttt{0x60}OP_16=0x60, OP_IF=0x63\texttt{OP\_IF}=\texttt{0x63}OP_IF=0x63, OP_ENDIF=0x68\texttt{OP\_ENDIF}=\texttt{0x68}OP_ENDIF=0x68, OP_CODESEPARATOR=0xab\texttt{OP\_CODESEPARATOR}=\texttt{0xab}OP_CODESEPARATOR=0xab, OP_CHECKSIG=0xac\texttt{OP\_CHECKSIG}=\texttt{0xac}OP_CHECKSIG=0xac, OP_CHECKSIGVERIFY=0xad\texttt{OP\_CHECKSIGVERIFY}=\texttt{0xad}OP_CHECKSIGVERIFY=0xad, OP_CHECKMULTISIG=0xae\texttt{OP\_CHECKMULTISIG}=\texttt{0xae}OP_CHECKMULTISIG=0xae, OP_CHECKMULTISIGVERIFY=0xaf\texttt{OP\_CHECKMULTISIGVERIFY}=\texttt{0xaf}OP_CHECKMULTISIGVERIFY=0xaf.
  • A signature version vvv is one of exactly two values: base\mathsf{base}base (legacy) or witnessV0\mathsf{witnessV0}witnessV0.

Script numbers and multisigSigs\mathrm{multisigSigs}multisigSigs

  • toNum(x)\mathrm{toNum}(x)toNum(x) (the call with "minimal encoding not required" and maximum size 444): none\mathsf{none}none if ∣x∣>4|x| > 4∣x∣>4; otherwise some(z)\mathsf{some}(z)some(z) with z∈Zz \in \mathbb Zz∈Z obtained by reading xxx little-endian, the bit 0x80\texttt{0x80}0x80 of the last byte being a sign bit: if it is set, zzz is minus the little-endian value of xxx with that bit cleared; else zzz is the little-endian value of xxx. toNum(ε)=some(0)\mathrm{toNum}(\varepsilon) = \mathsf{some}(0)toNum(ε)=some(0). No minimality check is performed.

  • For an integer zzz, z+:=max⁡(z,0)z^{+} := \max(z, 0)z+:=max(z,0) (negative integers convert to the natural number 000).

  • multisigSigs(Σ)\mathrm{multisigSigs}(\Sigma)multisigSigs(Σ), for a stack Σ\SigmaΣ listed top first, is a list of byte strings:

    • Σ\SigmaΣ empty: [ ][\,][].
    • Σ=[nk]+ ⁣ ⁣+R\Sigma = [n_k] \mathbin{+\!\!+} RΣ=[nk​]++R: if toNum(nk)=none\mathrm{toNum}(n_k) = \mathsf{none}toNum(nk​)=none, [ ][\,][]. If toNum(nk)=some(NK)\mathrm{toNum}(n_k) = \mathsf{some}(N_K)toNum(nk​)=some(NK​), let R′=dropNK+(R)R' = \mathrm{drop}_{N_K^{+}}(R)R′=dropNK+​​(R). If R′R'R′ is empty, [ ][\,][]. If R′=[ns]+ ⁣ ⁣+R′′R' = [n_s] \mathbin{+\!\!+} R''R′=[ns​]++R′′: if toNum(ns)=none\mathrm{toNum}(n_s) = \mathsf{none}toNum(ns​)=none, [ ][\,][]; if toNum(ns)=some(NS)\mathrm{toNum}(n_s) = \mathsf{some}(N_S)toNum(ns​)=some(NS​), the result is takeNS+(R′′)\mathrm{take}_{N_S^{+}}(R'')takeNS+​​(R′′) (all of R′′R''R′′ if it has fewer than NS+N_S^{+}NS+​ elements).

    No range checks are made on NKN_KNK​, NSN_SNS​ (e.g. NS>NKN_S > N_KNS​>NK​, or negative counts, are accepted).

Human review
  • Endorsed by Shuze Chen · Oct 30, 2026

    Confirmed by the moderator at approval.

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