Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

K fragments leave a key and a signature

Proved
BitcoinMiniscript.sem_K_shape

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

bitcoinbitcoin-mainnetcompiler-correctnessformal-verificationminiscriptpolicyscripttype-system

For m : K, Sem f o m w out implies out = [key, sig] for some key, sig.

Preamble
import Definitions.Def_BitcoinMiniscript
import Definitions.Def_BitcoinScript
open BitcoinMiniscript BitcoinToLocal BitcoinHtlc BitcoinScript BitcoinSig BitcoinVerify
Formal statement
theorem BitcoinMiniscript.sem_K_shape (f : BitcoinScript.Flags) (o : BitcoinScript.Oracle) (m : BitcoinMiniscript.Ms)
    (ht : BitcoinMiniscript.HasType m .K) (w out : List BitcoinScript.Bytes)
    (h : BitcoinMiniscript.Sem f o m w out) : ∃ key sig, out = [key, sig] := by sorry
Source
Miniscript reference (P. Wuille, A. Poelstra, S. Kanjalkar): translation table, type system and correctness/malleability properties, https://bitcoin.sipa.be/miniscript/; Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: src/script/miniscript.h, src/script/miniscript.cpp (https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/miniscript.h); EvalScript (src/script/interpreter.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: BitcoinMiniscript.sem_K_shape

Statement. For any flags fff, any oracle ooo (arbitrary functions, see below), any fragment mmm with HasType(m,K)\mathrm{HasType}(m, \mathsf{K})HasType(m,K), and any lists w,outw, \mathit{out}w,out of byte strings: if Semf,o(m,w,out)\mathrm{Sem}_{f,o}(m, w, \mathit{out})Semf,o​(m,w,out), then out\mathit{out}out has exactly two elements:

∃ κ,sig:out=[κ,sig].\exists\, \kappa, \mathit{sig}:\quad \mathit{out} = [\kappa, \mathit{sig}].∃κ,sig:out=[κ,sig].

Nothing further is said about κ\kappaκ or sig\mathit{sig}sig (e.g. their relation to the keys in mmm or to www). No resource hypotheses.

Definitions used in the statement, unfolded

Basic data (from the script-interpreter preamble)

Byte strings, stacks, witnesses. A byte string is a finite list of 8-bit bytes (values 0x00\mathtt{0x00}0x00–0xff\mathtt{0xff}0xff); [ ][\,][] is the empty byte string and ∣b∣|b|∣b∣ the length of bbb. Stacks, witnesses and outputs are finite lists of byte strings written top element first. For such lists, x::lx :: lx::l is the list with xxx placed on top of lll, l1+ ⁣ ⁣+l2l_1 \mathbin{+\!\!+} l_2l1​++l2​ is concatenation (in w+ ⁣ ⁣+restw \mathbin{+\!\!+} \mathit{rest}w++rest all elements of www lie above all elements of rest\mathit{rest}rest, the first element of www being the top of the stack), and ∣l∣|l|∣l∣ is the number of elements.

Constants.

MAX_SCRIPT_ELEMENT_SIZE=520,MAX_OPS_PER_SCRIPT=201,MAX_PUBKEYS_PER_MULTISIG=20,MAX_STACK_SIZE=1000.\mathrm{MAX\_SCRIPT\_ELEMENT\_SIZE}=520,\quad \mathrm{MAX\_OPS\_PER\_SCRIPT}=201,\quad \mathrm{MAX\_PUBKEYS\_PER\_MULTISIG}=20,\quad \mathrm{MAX\_STACK\_SIZE}=1000.MAX_SCRIPT_ELEMENT_SIZE=520,MAX_OPS_PER_SCRIPT=201,MAX_PUBKEYS_PER_MULTISIG=20,MAX_STACK_SIZE=1000.

castToBool\mathrm{castToBool}castToBool. For a byte string: castToBool([ ])=false\mathrm{castToBool}([\,])=\text{false}castToBool([])=false; castToBool([b0])=(b0≠0x00∧b0≠0x80)\mathrm{castToBool}([b_0]) = (b_0\neq \mathtt{0x00} \wedge b_0 \neq \mathtt{0x80})castToBool([b0​])=(b0​=0x00∧b0​=0x80); for a string with at least two bytes, castToBool(b0::r)=(b0≠0)∨castToBool(r)\mathrm{castToBool}(b_0 :: r) = (b_0 \neq 0) \vee \mathrm{castToBool}(r)castToBool(b0​::r)=(b0​=0)∨castToBool(r). So it is true exactly when some byte other than the last is nonzero, or the last byte is neither 0x00\mathtt{0x00}0x00 nor 0x80\mathtt{0x80}0x80; the empty string, all-zero strings, and strings of zero bytes followed by a final 0x80\mathtt{0x80}0x80 are false.

boolBytes\mathrm{boolBytes}boolBytes. boolBytes(true)=[0x01]\mathrm{boolBytes}(\text{true}) = [\mathtt{0x01}]boolBytes(true)=[0x01], boolBytes(false)=[ ]\mathrm{boolBytes}(\text{false}) = [\,]boolBytes(false)=[].

serialize\mathrm{serialize}serialize (script-number encoding of an integer nnn). serialize(0)=[ ]\mathrm{serialize}(0) = [\,]serialize(0)=[]. For n≠0n\neq 0n=0, let mag\mathit{mag}mag be the little-endian base-256 digits of ∣n∣|n|∣n∣ with no most-significant zero bytes. If the last (most significant) byte of mag\mathit{mag}mag has bit 0x80\mathtt{0x80}0x80 set, the result is mag\mathit{mag}mag followed by one extra byte, 0x80\mathtt{0x80}0x80 if n<0n<0n<0 and 0x00\mathtt{0x00}0x00 if n>0n>0n>0; otherwise the result is mag\mathit{mag}mag with bit 0x80\mathtt{0x80}0x80 of its last byte set if n<0n<0n<0, and mag\mathit{mag}mag itself if n>0n>0n>0. Examples: serialize(1)=[0x01]\mathrm{serialize}(1)=[\mathtt{0x01}]serialize(1)=[0x01], serialize(−1)=[0x81]\mathrm{serialize}(-1)=[\mathtt{0x81}]serialize(−1)=[0x81], serialize(32)=[0x20]\mathrm{serialize}(32)=[\mathtt{0x20}]serialize(32)=[0x20], serialize(128)=[0x80,0x00]\mathrm{serialize}(128)=[\mathtt{0x80},\mathtt{0x00}]serialize(128)=[0x80,0x00], serialize(231−1)=[0xff,0xff,0xff,0x7f]\mathrm{serialize}(2^{31}-1)=[\mathtt{0xff},\mathtt{0xff},\mathtt{0xff},\mathtt{0x7f}]serialize(231−1)=[0xff,0xff,0xff,0x7f].

Flags fff. A record of three independent booleans f.cltvf.\mathrm{cltv}f.cltv, f.csvf.\mathrm{csv}f.csv, f.nulldummyf.\mathrm{nulldummy}f.nulldummy; every combination is allowed.

Oracle ooo. A record of completely arbitrary functions, with no property assumed of any of them (they are not required to be the real hash functions or a real signature check, need not produce outputs of any particular length, and need not be injective or collision resistant):

  • o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256o.\mathrm{ripemd160},\ o.\mathrm{sha1},\ o.\mathrm{sha256},\ o.\mathrm{hash160},\ o.\mathrm{hash256}o.ripemd160, o.sha1, o.sha256, o.hash160, o.hash256: byte strings →\to→ byte strings;
  • o.checkSig(sig,pubkey)∈{none,some(true),some(false)}o.\mathrm{checkSig}(\mathit{sig}, \mathit{pubkey}) \in \{\text{none}, \text{some}(\text{true}), \text{some}(\text{false})\}o.checkSig(sig,pubkey)∈{none,some(true),some(false)}, an arbitrary function of a signature and a public key ("none" means the script fails);
  • o.checkLockTime, o.checkSequenceo.\mathrm{checkLockTime},\ o.\mathrm{checkSequence}o.checkLockTime, o.checkSequence: integers →\to→ booleans.

multisigLoopo(sigs,keys)\mathrm{multisigLoop}_o(\mathit{sigs}, \mathit{keys})multisigLoopo​(sigs,keys) (both lists top-first), with result none, some(true) or some(false):

  • if sigs=[ ]\mathit{sigs} = [\,]sigs=[]: some(true);
  • if sigs\mathit{sigs}sigs is nonempty and keys=[ ]\mathit{keys} = [\,]keys=[]: some(false);
  • if sigs=s::S\mathit{sigs} = s :: Ssigs=s::S and keys=k::K\mathit{keys} = k :: Kkeys=k::K: compute o.checkSig(s,k)o.\mathrm{checkSig}(s, k)o.checkSig(s,k). If none, the result is none. If some(true): the result is some(false) when ∣K∣<∣S∣|K| < |S|∣K∣<∣S∣, and otherwise multisigLoopo(S,K)\mathrm{multisigLoop}_o(S, K)multisigLoopo​(S,K). If some(false): the result is some(false) when ∣K∣<∣S∣+1|K| < |S| + 1∣K∣<∣S∣+1, and otherwise multisigLoopo(s::S,K)\mathrm{multisigLoop}_o(s :: S, K)multisigLoopo​(s::S,K).

Miniscript definitions used

Miniscript fragments Ms\mathrm{Ms}Ms. The set of finite syntax trees built from exactly the following 23 constructors (byte-string, integer, natural-number and list parameters are arbitrary; no well-formedness is built in):

  1. pk_k(κ)\mathrm{pk\_k}(\kappa)pk_k(κ), κ\kappaκ a byte string (a key);
  2. pk_h(h)\mathrm{pk\_h}(h)pk_h(h), hhh a byte string (a key hash);
  3. older(n)\mathrm{older}(n)older(n), n∈Zn \in \mathbb{Z}n∈Z;
  4. after(n)\mathrm{after}(n)after(n), n∈Zn \in \mathbb{Z}n∈Z;
  5. sha256(h)\mathrm{sha256}(h)sha256(h), 6. hash256(h)\mathrm{hash256}(h)hash256(h), 7. ripemd160(h)\mathrm{ripemd160}(h)ripemd160(h), 8. hash160(h)\mathrm{hash160}(h)hash160(h), each with hhh a byte string;
  6. and_v(x,y)\mathrm{and\_v}(x, y)and_v(x,y), 10. and_b(x,y)\mathrm{and\_b}(x, y)and_b(x,y), with x,yx, yx,y fragments;
  7. or_b(x,z)\mathrm{or\_b}(x, z)or_b(x,z), 12. or_c(x,z)\mathrm{or\_c}(x, z)or_c(x,z), 13. or_d(x,z)\mathrm{or\_d}(x, z)or_d(x,z), 14. or_i(x,z)\mathrm{or\_i}(x, z)or_i(x,z), with x,zx, zx,z fragments;
  8. andor(x,y,z)\mathrm{andor}(x, y, z)andor(x,y,z), with x,y,zx, y, zx,y,z fragments;
  9. multi(k,keys)\mathrm{multi}(k, \mathit{keys})multi(k,keys), k∈Nk \in \mathbb{N}k∈N and keys\mathit{keys}keys a finite list of byte strings; 17.–23. the wrappers wrap_a(x)\mathrm{wrap\_a}(x)wrap_a(x), wrap_s(x)\mathrm{wrap\_s}(x)wrap_s(x), wrap_c(x)\mathrm{wrap\_c}(x)wrap_c(x), wrap_d(x)\mathrm{wrap\_d}(x)wrap_d(x), wrap_v(x)\mathrm{wrap\_v}(x)wrap_v(x), wrap_j(x)\mathrm{wrap\_j}(x)wrap_j(x), wrap_n(x)\mathrm{wrap\_n}(x)wrap_n(x), with xxx a fragment.

Two fragments are equal exactly when they are built identically.

Correctness types Ty\mathrm{Ty}Ty. A four-element set {B,V,K,W}\{\mathsf{B}, \mathsf{V}, \mathsf{K}, \mathsf{W}\}{B,V,K,W} of distinct labels (no meaning is attached to them other than through the rules below).

Modifier records Props\mathrm{Props}Props. A record of five booleans (z,o,n,d,u)(z, o, n, d, u)(z,o,n,d,u).

props(m)=(z,o,n,d,u)\mathrm{props}(m) = (z, o, n, d, u)props(m)=(z,o,n,d,u), computed syntactically. Write zx,ox,nx,dx,uxz_x, o_x, n_x, d_x, u_xzx​,ox​,nx​,dx​,ux​ for the components of props(x)\mathrm{props}(x)props(x) (similarly for yyy, zzz), ∧,∨\wedge,\vee∧,∨ for boolean and/or, T/F for true/false. (The modifier letter ooo is unrelated to the oracle ooo, and the modifier letter zzz is unrelated to a sub-fragment named zzz; e.g. zzz_zzz​ is the zzz-modifier of the sub-fragment zzz.)

fragmentzzzooonnnddduuu
pk_k(κ)\mathrm{pk\_k}(\kappa)pk_k(κ)FTTTT
pk_h(h)\mathrm{pk\_h}(h)pk_h(h)FFTTT
older(n)\mathrm{older}(n)older(n), after(n)\mathrm{after}(n)after(n)TFFFF
sha256\mathrm{sha256}sha256, hash256\mathrm{hash256}hash256, ripemd160\mathrm{ripemd160}ripemd160, hash160\mathrm{hash160}hash160FTTTT
and_v(x,y)\mathrm{and\_v}(x,y)and_v(x,y)zx∧zyz_x\wedge z_yzx​∧zy​(zx∧oy)∨(ox∧zy)(z_x\wedge o_y)\vee(o_x\wedge z_y)(zx​∧oy​)∨(ox​∧zy​)nx∨(zx∧ny)n_x\vee(z_x\wedge n_y)nx​∨(zx​∧ny​)Fuyu_yuy​
and_b(x,y)\mathrm{and\_b}(x,y)and_b(x,y)zx∧zyz_x\wedge z_yzx​∧zy​(zx∧oy)∨(ox∧zy)(z_x\wedge o_y)\vee(o_x\wedge z_y)(zx​∧oy​)∨(ox​∧zy​)nx∨(zx∧ny)n_x\vee(z_x\wedge n_y)nx​∨(zx​∧ny​)dx∧dyd_x\wedge d_ydx​∧dy​T
or_b(x,z)\mathrm{or\_b}(x,z)or_b(x,z)zx∧zzz_x\wedge z_zzx​∧zz​(zx∧oz)∨(ox∧zz)(z_x\wedge o_z)\vee(o_x\wedge z_z)(zx​∧oz​)∨(ox​∧zz​)FTT
or_c(x,z)\mathrm{or\_c}(x,z)or_c(x,z)zx∧zzz_x\wedge z_zzx​∧zz​ox∧zzo_x\wedge z_zox​∧zz​FFF
or_d(x,z)\mathrm{or\_d}(x,z)or_d(x,z)zx∧zzz_x\wedge z_zzx​∧zz​ox∧zzo_x\wedge z_zox​∧zz​Fdzd_zdz​uzu_zuz​
or_i(x,z)\mathrm{or\_i}(x,z)or_i(x,z)Fzx∧zzz_x\wedge z_zzx​∧zz​Fdx∨dzd_x\vee d_zdx​∨dz​ux∧uzu_x\wedge u_zux​∧uz​
andor(x,y,z)\mathrm{andor}(x,y,z)andor(x,y,z)zx∧zy∧zzz_x\wedge z_y\wedge z_zzx​∧zy​∧zz​(zx∧oy∧oz)∨(ox∧zy∧zz)(z_x\wedge o_y\wedge o_z)\vee(o_x\wedge z_y\wedge z_z)(zx​∧oy​∧oz​)∨(ox​∧zy​∧zz​)Fdzd_zdz​uy∧uzu_y\wedge u_zuy​∧uz​
multi(k,keys)\mathrm{multi}(k,\mathit{keys})multi(k,keys)FFTTT
wrap_a(x)\mathrm{wrap\_a}(x)wrap_a(x)FFFdxd_xdx​uxu_xux​
wrap_s(x)\mathrm{wrap\_s}(x)wrap_s(x)Foxo_xox​Fdxd_xdx​uxu_xux​
wrap_c(x)\mathrm{wrap\_c}(x)wrap_c(x)Foxo_xox​nxn_xnx​dxd_xdx​T
wrap_d(x)\mathrm{wrap\_d}(x)wrap_d(x)FTTTF
wrap_v(x)\mathrm{wrap\_v}(x)wrap_v(x)zxz_xzx​oxo_xox​nxn_xnx​FF
wrap_j(x)\mathrm{wrap\_j}(x)wrap_j(x)Foxo_xox​TTuxu_xux​
wrap_n(x)\mathrm{wrap\_n}(x)wrap_n(x)zxz_xzx​oxo_xox​nxn_xnx​dxd_xdx​T

(The components do not depend on the byte-string, integer or list parameters of the leaves.)

HasType(m,t)\mathrm{HasType}(m, t)HasType(m,t), "mmm has type ttt", is the smallest relation closed under the following 23 rules (one per constructor; there is no other way to derive it). Throughout, 520=MAX_SCRIPT_ELEMENT_SIZE520 = \mathrm{MAX\_SCRIPT\_ELEMENT\_SIZE}520=MAX_SCRIPT_ELEMENT_SIZE and 20=MAX_PUBKEYS_PER_MULTISIG20 = \mathrm{MAX\_PUBKEYS\_PER\_MULTISIG}20=MAX_PUBKEYS_PER_MULTISIG.

  1. pk_k(κ):K\mathrm{pk\_k}(\kappa) : \mathsf{K}pk_k(κ):K if ∣κ∣≤520|\kappa| \le 520∣κ∣≤520.
  2. pk_h(h):K\mathrm{pk\_h}(h) : \mathsf{K}pk_h(h):K if ∣h∣≤520|h| \le 520∣h∣≤520.
  3. older(n):B\mathrm{older}(n) : \mathsf{B}older(n):B if 1≤n<2311 \le n < 2^{31}1≤n<231.
  4. after(n):B\mathrm{after}(n) : \mathsf{B}after(n):B if 1≤n<2311 \le n < 2^{31}1≤n<231. 5.–8. sha256(h)\mathrm{sha256}(h)sha256(h), hash256(h)\mathrm{hash256}(h)hash256(h), ripemd160(h)\mathrm{ripemd160}(h)ripemd160(h), hash160(h)\mathrm{hash160}(h)hash160(h) :B: \mathsf{B}:B if ∣h∣≤520|h| \le 520∣h∣≤520 (no condition on ∣h∣|h|∣h∣ being any particular hash length).
  5. and_v(x,y):t\mathrm{and\_v}(x,y) : tand_v(x,y):t if x:Vx : \mathsf{V}x:V, y:ty : ty:t and t≠Wt \neq \mathsf{W}t=W.
  6. and_b(x,y):B\mathrm{and\_b}(x,y) : \mathsf{B}and_b(x,y):B if x:Bx : \mathsf{B}x:B and y:Wy : \mathsf{W}y:W.
  7. or_b(x,z):B\mathrm{or\_b}(x,z) : \mathsf{B}or_b(x,z):B if x:Bx : \mathsf{B}x:B, dxd_xdx​, z:Wz : \mathsf{W}z:W, dzd_zdz​.
  8. or_c(x,z):V\mathrm{or\_c}(x,z) : \mathsf{V}or_c(x,z):V if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, z:Vz : \mathsf{V}z:V.
  9. or_d(x,z):B\mathrm{or\_d}(x,z) : \mathsf{B}or_d(x,z):B if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, z:Bz : \mathsf{B}z:B.
  10. or_i(x,z):t\mathrm{or\_i}(x,z) : tor_i(x,z):t if x:tx : tx:t, z:tz : tz:t and t≠Wt \ne \mathsf{W}t=W.
  11. andor(x,y,z):t\mathrm{andor}(x,y,z) : tandor(x,y,z):t if x:Bx : \mathsf{B}x:B, dxd_xdx​, uxu_xux​, y:ty : ty:t, z:tz : tz:t and t≠Wt \ne \mathsf{W}t=W.
  12. multi(k,keys):B\mathrm{multi}(k, \mathit{keys}) : \mathsf{B}multi(k,keys):B if 1≤k≤∣keys∣≤201 \le k \le |\mathit{keys}| \le 201≤k≤∣keys∣≤20 and every key in keys\mathit{keys}keys has length ≤520\le 520≤520.
  13. wrap_a(x):W\mathrm{wrap\_a}(x) : \mathsf{W}wrap_a(x):W if x:Bx : \mathsf{B}x:B.
  14. wrap_s(x):W\mathrm{wrap\_s}(x) : \mathsf{W}wrap_s(x):W if x:Bx : \mathsf{B}x:B and oxo_xox​.
  15. wrap_c(x):B\mathrm{wrap\_c}(x) : \mathsf{B}wrap_c(x):B if x:Kx : \mathsf{K}x:K.
  16. wrap_d(x):B\mathrm{wrap\_d}(x) : \mathsf{B}wrap_d(x):B if x:Vx : \mathsf{V}x:V and zxz_xzx​.
  17. wrap_v(x):V\mathrm{wrap\_v}(x) : \mathsf{V}wrap_v(x):V if x:Bx : \mathsf{B}x:B.
  18. wrap_j(x):B\mathrm{wrap\_j}(x) : \mathsf{B}wrap_j(x):B if x:Bx : \mathsf{B}x:B and nxn_xnx​.
  19. wrap_n(x):B\mathrm{wrap\_n}(x) : \mathsf{B}wrap_n(x):B if x:Bx : \mathsf{B}x:B.

Here dxd_xdx​, uxu_xux​, oxo_xox​, zxz_xzx​, nxn_xnx​ mean the corresponding component of props(x)\mathrm{props}(x)props(x) is true. Read off the rules: type W\mathsf{W}W is concluded only by rules 17–18 (wrap_a\mathrm{wrap\_a}wrap_a, wrap_s\mathrm{wrap\_s}wrap_s); type K\mathsf{K}K only by rules 1, 2, 9 (with y:Ky : \mathsf{K}y:K), 14 and 15 (with both branches K\mathsf{K}K); type V\mathsf{V}V only by rules 9, 12, 14, 15, 21. No rule constrains the modifiers o,n,z,uo, n, z, uo,n,z,u of yyy or zzz beyond those listed, and no rule bounds the depth or total size of the fragment.

CsvPassesf,o(n)\mathrm{CsvPasses}_{f,o}(n)CsvPassesf,o​(n) (from the to_local preamble), for n∈Zn\in\mathbb{Z}n∈Z: f.csv=falsef.\mathrm{csv} = \text{false}f.csv=false, or (n≥0n \ge 0n≥0 and (bit 2312^{31}231 of nnn is set, or o.checkSequence(n)=trueo.\mathrm{checkSequence}(n) = \text{true}o.checkSequence(n)=true)).

CltvPassesf,o(n)\mathrm{CltvPasses}_{f,o}(n)CltvPassesf,o​(n) (from the HTLC preamble), for n∈Zn\in\mathbb{Z}n∈Z: f.cltv=falsef.\mathrm{cltv} = \text{false}f.cltv=false, or (n≥0n \ge 0n≥0 and o.checkLockTime(n)=trueo.\mathrm{checkLockTime}(n) = \text{true}o.checkLockTime(n)=true).

Semf,o(m,w,out)\mathrm{Sem}_{f,o}(m, w, \mathit{out})Semf,o​(m,w,out) — a relation between a fragment mmm, a witness www and an output out\mathit{out}out (both lists of byte strings, top first), for fixed flags fff and oracle ooo; it is defined by recursion on mmm, and nothing in it refers to the type of mmm or to any size or operation-count limit except where stated. "∃\exists∃" ranges over arbitrary byte strings / lists of byte strings / booleans as appropriate.

  1. pk_k(κ)\mathrm{pk\_k}(\kappa)pk_k(κ): ∃ sig\exists\, \mathit{sig}∃sig with w=[sig]w = [\mathit{sig}]w=[sig] and out=[κ,sig]\mathit{out} = [\kappa, \mathit{sig}]out=[κ,sig].
  2. pk_h(h)\mathrm{pk\_h}(h)pk_h(h): ∃ κ,sig\exists\, \kappa, \mathit{sig}∃κ,sig with w=[κ,sig]w = [\kappa, \mathit{sig}]w=[κ,sig], o.hash160(κ)=ho.\mathrm{hash160}(\kappa) = ho.hash160(κ)=h and out=[κ,sig]\mathit{out} = [\kappa, \mathit{sig}]out=[κ,sig].
  3. older(n)\mathrm{older}(n)older(n): w=[ ]w = [\,]w=[], CsvPassesf,o(n)\mathrm{CsvPasses}_{f,o}(n)CsvPassesf,o​(n) and out=[serialize(n)]\mathit{out} = [\mathrm{serialize}(n)]out=[serialize(n)].
  4. after(n)\mathrm{after}(n)after(n): w=[ ]w = [\,]w=[], CltvPassesf,o(n)\mathrm{CltvPasses}_{f,o}(n)CltvPassesf,o​(n) and out=[serialize(n)]\mathit{out} = [\mathrm{serialize}(n)]out=[serialize(n)].
  5. sha256(h)\mathrm{sha256}(h)sha256(h): ∃ p\exists\, p∃p with w=[p]w = [p]w=[p], ∣p∣=32|p| = 32∣p∣=32 and out=[boolBytes(o.sha256(p)=h)]\mathit{out} = [\mathrm{boolBytes}(o.\mathrm{sha256}(p) = h)]out=[boolBytes(o.sha256(p)=h)] — so out=[[0x01]]\mathit{out} = [[\mathtt{0x01}]]out=[[0x01]] if the oracle hash of ppp equals hhh and out=[[ ]]\mathit{out} = [[\,]]out=[[]] otherwise (any 32-byte ppp is accepted either way). 6.–8. hash256(h)\mathrm{hash256}(h)hash256(h), ripemd160(h)\mathrm{ripemd160}(h)ripemd160(h), hash160(h)\mathrm{hash160}(h)hash160(h): the same with o.hash256o.\mathrm{hash256}o.hash256, o.ripemd160o.\mathrm{ripemd160}o.ripemd160, o.hash160o.\mathrm{hash160}o.hash160 respectively (and still ∣p∣=32|p| = 32∣p∣=32).
  6. and_v(x,y)\mathrm{and\_v}(x,y)and_v(x,y): ∃ wx,wy\exists\, w_x, w_y∃wx​,wy​ with w=wx+ ⁣ ⁣+wyw = w_x \mathbin{+\!\!+} w_yw=wx​++wy​, Sem(x,wx,[ ])\mathrm{Sem}(x, w_x, [\,])Sem(x,wx​,[]) and Sem(y,wy,out)\mathrm{Sem}(y, w_y, \mathit{out})Sem(y,wy​,out).
  7. and_b(x,y)\mathrm{and\_b}(x,y)and_b(x,y): ∃ wx,wy,vx,vy\exists\, w_x, w_y, v_x, v_y∃wx​,wy​,vx​,vy​ with w=wx+ ⁣ ⁣+wyw = w_x \mathbin{+\!\!+} w_yw=wx​++wy​, Sem(x,wx,[vx])\mathrm{Sem}(x, w_x, [v_x])Sem(x,wx​,[vx​]), Sem(y,wy,[vy])\mathrm{Sem}(y, w_y, [v_y])Sem(y,wy​,[vy​]) and out=[boolBytes(castToBool(vx)∧castToBool(vy))]\mathit{out} = [\mathrm{boolBytes}(\mathrm{castToBool}(v_x) \wedge \mathrm{castToBool}(v_y))]out=[boolBytes(castToBool(vx​)∧castToBool(vy​))].
  8. or_b(x,z)\mathrm{or\_b}(x,z)or_b(x,z): ∃ wx,wz,vx,vz\exists\, w_x, w_z, v_x, v_z∃wx​,wz​,vx​,vz​ with w=wx+ ⁣ ⁣+wzw = w_x \mathbin{+\!\!+} w_zw=wx​++wz​, Sem(x,wx,[vx])\mathrm{Sem}(x, w_x, [v_x])Sem(x,wx​,[vx​]), Sem(z,wz,[vz])\mathrm{Sem}(z, w_z, [v_z])Sem(z,wz​,[vz​]) and out=[boolBytes(castToBool(vx)∨castToBool(vz))]\mathit{out} = [\mathrm{boolBytes}(\mathrm{castToBool}(v_x) \vee \mathrm{castToBool}(v_z))]out=[boolBytes(castToBool(vx​)∨castToBool(vz​))] (both sides may be true simultaneously).
  9. or_c(x,z)\mathrm{or\_c}(x,z)or_c(x,z): out=[ ]\mathit{out} = [\,]out=[] and ∃ wx,vx\exists\, w_x, v_x∃wx​,vx​ with Sem(x,wx,[vx])\mathrm{Sem}(x, w_x, [v_x])Sem(x,wx​,[vx​]) and either (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) true and w=wxw = w_xw=wx​) or (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) false and ∃ wz\exists\, w_z∃wz​ with w=wx+ ⁣ ⁣+wzw = w_x \mathbin{+\!\!+} w_zw=wx​++wz​ and Sem(z,wz,[ ])\mathrm{Sem}(z, w_z, [\,])Sem(z,wz​,[])). (vxv_xvx​ in the second alternative is any value with castToBool\mathrm{castToBool}castToBool false, not necessarily [ ][\,][].)
  10. or_d(x,z)\mathrm{or\_d}(x,z)or_d(x,z): ∃ wx,vx\exists\, w_x, v_x∃wx​,vx​ with Sem(x,wx,[vx])\mathrm{Sem}(x, w_x, [v_x])Sem(x,wx​,[vx​]) and either (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) true, w=wxw = w_xw=wx​ and out=[vx]\mathit{out} = [v_x]out=[vx​]) or (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) false and ∃ wz\exists\, w_z∃wz​ with w=wx+ ⁣ ⁣+wzw = w_x \mathbin{+\!\!+} w_zw=wx​++wz​ and Sem(z,wz,out)\mathrm{Sem}(z, w_z, \mathit{out})Sem(z,wz​,out)).
  11. or_i(x,z)\mathrm{or\_i}(x,z)or_i(x,z): ∃ b,w′\exists\, b, w'∃b,w′ with w=b::w′w = b :: w'w=b::w′ and either (castToBool(b)\mathrm{castToBool}(b)castToBool(b) true and Sem(x,w′,out)\mathrm{Sem}(x, w', \mathit{out})Sem(x,w′,out)) or (castToBool(b)\mathrm{castToBool}(b)castToBool(b) false and Sem(z,w′,out)\mathrm{Sem}(z, w', \mathit{out})Sem(z,w′,out)). The selector bbb is any byte string (not only [0x01][\mathtt{0x01}][0x01] / [ ][\,][]), with no length bound.
  12. andor(x,y,z)\mathrm{andor}(x,y,z)andor(x,y,z): ∃ wx,vx\exists\, w_x, v_x∃wx​,vx​ with Sem(x,wx,[vx])\mathrm{Sem}(x, w_x, [v_x])Sem(x,wx​,[vx​]) and either (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) true and ∃ wy\exists\, w_y∃wy​ with w=wx+ ⁣ ⁣+wyw = w_x \mathbin{+\!\!+} w_yw=wx​++wy​ and Sem(y,wy,out)\mathrm{Sem}(y, w_y, \mathit{out})Sem(y,wy​,out)) or (castToBool(vx)\mathrm{castToBool}(v_x)castToBool(vx​) false and ∃ wz\exists\, w_z∃wz​ with w=wx+ ⁣ ⁣+wzw = w_x \mathbin{+\!\!+} w_zw=wx​++wz​ and Sem(z,wz,out)\mathrm{Sem}(z, w_z, \mathit{out})Sem(z,wz​,out)).
  13. multi(k,keys)\mathrm{multi}(k, \mathit{keys})multi(k,keys): ∃\exists∃ a list sigs\mathit{sigs}sigs, a byte string dummy\mathit{dummy}dummy and a boolean ok\mathit{ok}ok with w=sigs+ ⁣ ⁣+[dummy]w = \mathit{sigs} \mathbin{+\!\!+} [\mathit{dummy}]w=sigs++[dummy] (the dummy is the deepest witness element), ∣sigs∣=k|\mathit{sigs}| = k∣sigs∣=k, multisigLoopo(sigs,reverse(keys))=some(ok)\mathrm{multisigLoop}_o(\mathit{sigs}, \mathrm{reverse}(\mathit{keys})) = \text{some}(\mathit{ok})multisigLoopo​(sigs,reverse(keys))=some(ok) (keys taken last-listed first), (f.nulldummyf.\mathrm{nulldummy}f.nulldummy true ⇒dummy=[ ]\Rightarrow \mathit{dummy} = [\,]⇒dummy=[]), and out=[boolBytes(ok)]\mathit{out} = [\mathrm{boolBytes}(\mathit{ok})]out=[boolBytes(ok)]. Both ok\mathit{ok}ok true and false are allowed.
  14. wrap_a(x)\mathrm{wrap\_a}(x)wrap_a(x): Sem(x,w,out)\mathrm{Sem}(x, w, \mathit{out})Sem(x,w,out).
  15. wrap_s(x)\mathrm{wrap\_s}(x)wrap_s(x): Sem(x,w,out)\mathrm{Sem}(x, w, \mathit{out})Sem(x,w,out).
  16. wrap_c(x)\mathrm{wrap\_c}(x)wrap_c(x): ∃ κ,sig,ok\exists\, \kappa, \mathit{sig}, \mathit{ok}∃κ,sig,ok with Sem(x,w,[κ,sig])\mathrm{Sem}(x, w, [\kappa, \mathit{sig}])Sem(x,w,[κ,sig]), o.checkSig(sig,κ)=some(ok)o.\mathrm{checkSig}(\mathit{sig}, \kappa) = \text{some}(\mathit{ok})o.checkSig(sig,κ)=some(ok) and out=[boolBytes(ok)]\mathit{out} = [\mathrm{boolBytes}(\mathit{ok})]out=[boolBytes(ok)] (ok\mathit{ok}ok may be false).
  17. wrap_d(x)\mathrm{wrap\_d}(x)wrap_d(x): either (w=[[0x01]]w = [[\mathtt{0x01}]]w=[[0x01]], Sem(x,[ ],[ ])\mathrm{Sem}(x, [\,], [\,])Sem(x,[],[]) and out=[[0x01]]\mathit{out} = [[\mathtt{0x01}]]out=[[0x01]]) or (w=[[ ]]w = [[\,]]w=[[]] and out=[[ ]]\mathit{out} = [[\,]]out=[[]]). The selector must be exactly the one-byte string [0x01][\mathtt{0x01}][0x01] or exactly the empty string.
  18. wrap_v(x)\mathrm{wrap\_v}(x)wrap_v(x): ∃ v\exists\, v∃v with Sem(x,w,[v])\mathrm{Sem}(x, w, [v])Sem(x,w,[v]), castToBool(v)\mathrm{castToBool}(v)castToBool(v) true, and out=[ ]\mathit{out} = [\,]out=[].
  19. wrap_j(x)\mathrm{wrap\_j}(x)wrap_j(x): either (w=e::w′w = e :: w'w=e::w′ for some e,w′e, w'e,w′ with e≠[ ]e \ne [\,]e=[], ∣e∣≤520|e| \le 520∣e∣≤520, and Sem(x,w,out)\mathrm{Sem}(x, w, \mathit{out})Sem(x,w,out) — note xxx receives the whole www, including eee) or (w=[[ ]]w = [[\,]]w=[[]] and out=[[ ]]\mathit{out} = [[\,]]out=[[]]).
  20. wrap_n(x)\mathrm{wrap\_n}(x)wrap_n(x): ∃ v\exists\, v∃v with Sem(x,w,[v])\mathrm{Sem}(x, w, [v])Sem(x,w,[v]) and out=[boolBytes(castToBool(v))]\mathit{out} = [\mathrm{boolBytes}(\mathrm{castToBool}(v))]out=[boolBytes(castToBool(v))].
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