Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Script trees, explicit collision witnesses, and honest Taproot outputs (revision 2)

Definition
BitcoinTapSoundnessV2

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

bip341bitcoinbitcoin-mainnetcollisionformal-verificationmerklesoundnesstagged-hashtaproot

Names over the Taproot mission's BitcoinTaproot; nothing of Core is re-transcribed. Revision 2 of BitcoinTapSoundness: the closed propositions "some SHA-256 collision exists" and "some pair of tweaks collides" of the first revision are provable by counting and said nothing; here every collision is a pair of explicit byte strings computed from the inputs.

Collides x y — the two given byte strings differ and have the same sha256. taggedPre t m === sha256 (ascii t) ++ sha256 (ascii t) ++ m, the preimage of the tagged hash, so tagged t m = sha256 (taggedPre t m). leafMsg v s and branchMsg a b — the messages of ComputeTapleafHash (version, compact-size length, script) and ComputeTapbranchHash (the two children in lexicographic order).

TapTree — a binary tree of leaves (version byte, script); TapTree.hash, TapTree.leaves, TapTree.subtreesAt T d as in revision 1.

walk T nodes h — follows a Merkle path from the hash hhh up to the root of TTT while descending the tree in step with the path, returning either the subtree the path lands on or a pair of candidate colliding strings: where the hash below is neither child of the current branch, the two TapBranch preimages; where a leaf is met before the path ends, the TapLeaf and TapBranch preimages. scriptPathWitness T control v s — the pair walk finds on the control block's path from tapleafHash v s, or, if the walk lands on a branch, that branch's TapBranch preimage against the leaf's TapLeaf preimage; none when the walk lands on a leaf.

TweakCollision q parity P t₁ t₂ — the two given tweak scalars differ, are both 32 bytes, and both pass xonlyTweakAddCheck q parity P (Core's secp256k1_xonly_pubkey_tweak_add_check): a discrete-logarithm relation on secp256k1.

HonestOutput q internal32 parity T, controlInternalKey, controlParity — as in revision 1 (XOnlyPubKey::CheckTapTweak with the tree's root; bytes 1–32 and bit 0 of the control block).

Formalization Note. tagged, tapleafHash, tapbranchHash, lexLt, controlNodes, taprootMerkleRoot, tapTweakHash, xonlyTweakAddCheck, checkTapTweak, verifyTaprootCommitment are the Taproot mission's; sha256, writeCompactSize, taggedHash, ascii, liftX, beVal the serialization and signature missions'. Only Std is imported.

Definition code
import Definitions.Def_BitcoinTaproot

/-!
# Soundness of the Taproot script path, revision 2

A Taproot output commits to a tree of scripts through its tweaked key; a spender opens one leaf
with a control block (internal key, parity bit, Merkle path). The claim behind the design is that
nobody can open a leaf the creator did not put in the tree. This file states that claim as a
*constructive* reduction: whenever a control block passes verification for a leaf outside the tree,
the statement names two different byte strings with the same SHA-256, computed from the inputs, or
two different 32-byte tweak scalars, computed from the inputs, that both carry the internal key to
the output key.

Revision 2 replaces the first revision's closed propositions ("some collision exists"), which are
provable by counting and therefore said nothing, by explicit witnesses.
-/

namespace BitcoinTapSoundnessV2

open BitcoinSer BitcoinTaproot

/-- Two different byte strings with the same SHA-256. -/
def Collides (x y : Bytes) : Prop := x ≠ y ∧ sha256 x = sha256 y

/-- The preimage of a tagged hash: `SHA256(tag) ‖ SHA256(tag) ‖ m`, so that
`tagged t m = sha256 (taggedPre t m)`. -/
def taggedPre (t : String) (m : Bytes) : Bytes :=
  sha256 (BitcoinSig.ascii t) ++ sha256 (BitcoinSig.ascii t) ++ m

/-- The message of `ComputeTapleafHash`: the leaf version, the compact-size length, the script. -/
def leafMsg (v : Byte) (s : Bytes) : Bytes := [v] ++ BitcoinSer.writeCompactSize s.length ++ s

/-- The message of `ComputeTapbranchHash`: the two children in lexicographic order. -/
def branchMsg (a b : Bytes) : Bytes := if lexLt a b then a ++ b else b ++ a

/-- A tree of tapscript leaves as the output's creator built it (BIP341). -/
inductive TapTree where
  | leaf (version : Byte) (script : Bytes)
  | branch (l r : TapTree)
  deriving DecidableEq, Repr

/-- The hash of a tree: `ComputeTapleafHash` at a leaf, `ComputeTapbranchHash` at a branch. -/
def TapTree.hash : TapTree → Bytes
  | .leaf v s => tapleafHash v s
  | .branch l r => tapbranchHash l.hash r.hash

/-- The leaf hashes committed in a tree. -/
def TapTree.leaves : TapTree → List Bytes
  | .leaf v s => [tapleafHash v s]
  | .branch l r => l.leaves ++ r.leaves

/-- The subtrees at depth `d`. -/
def TapTree.subtreesAt : TapTree → Nat → List TapTree
  | T, 0 => [T]
  | .leaf _ _, _ + 1 => []
  | .branch l r, d + 1 => l.subtreesAt d ++ r.subtreesAt d

/-- Walk a Merkle path from the hash `h` up to the root of `T`, descending the tree in step with the
path: the result is the subtree the path lands on, or a candidate pair of colliding strings found
where the tree and the path disagree. At each level the hash below is either one of the two
children (continue into that child) or neither (two different `TapBranch` preimages with the same
hash); a leaf met before the path is exhausted gives a `TapLeaf` and a `TapBranch` preimage with
the same hash. -/
def walk : TapTree → List Bytes → Bytes → TapTree ⊕ (Bytes × Bytes)
  | T, [], _ => .inl T
  | T, n :: rest, h =>
    match walk T rest (tapbranchHash h n) with
    | .inr c => .inr c
    | .inl (.leaf v s) => .inr (taggedPre "TapLeaf" (leafMsg v s), taggedPre "TapBranch" (branchMsg h n))
    | .inl (.branch l r) =>
      if h = l.hash then .inl l
      else if h = r.hash then .inl r
      else .inr (taggedPre "TapBranch" (branchMsg l.hash r.hash), taggedPre "TapBranch" (branchMsg h n))

/-- The colliding pair a control block exhibits, if any, when its path carries the leaf hash of
`(v, s)` to the root of `T`: the pair found by `walk`, or, when the walk lands on a branch whose hash
is the leaf hash, that branch's `TapBranch` preimage against the leaf's `TapLeaf` preimage. `none`
means the walk landed on a leaf, which is then a leaf of `T`. -/
def scriptPathWitness (T : TapTree) (control : Bytes) (v : Byte) (s : Bytes) : Option (Bytes × Bytes) :=
  match walk T (controlNodes control) (tapleafHash v s) with
  | .inr c => some c
  | .inl (.leaf _ _) => none
  | .inl (.branch l r) => some (taggedPre "TapLeaf" (leafMsg v s), taggedPre "TapBranch" (branchMsg l.hash r.hash))

/-- Two different 32-byte tweak scalars that both carry the internal point `P` to the output key
`q` with parity `parity` under `secp256k1_xonly_pubkey_tweak_add_check`: a discrete-logarithm
relation on secp256k1. -/
def TweakCollision (q : Bytes) (parity : Bool) (P : Nat × Nat) (t₁ t₂ : Bytes) : Prop :=
  t₁ ≠ t₂ ∧ t₁.length = 32 ∧ t₂.length = 32 ∧
    xonlyTweakAddCheck q parity P t₁ = true ∧ xonlyTweakAddCheck q parity P t₂ = true

/-- An honestly constructed Taproot output: `q` is the tweak of the internal key `internal32` by the
tree's root, with the given parity (`XOnlyPubKey::CheckTapTweak`). -/
def HonestOutput (q internal32 : Bytes) (parity : Bool) (T : TapTree) : Prop :=
  checkTapTweak q internal32 T.hash parity = true

/-- The internal key of a control block (bytes 1 to 32). -/
def controlInternalKey (control : Bytes) : Bytes := (control.drop 1).take 32

/-- The parity bit of a control block (bit 0 of its first byte). -/
def controlParity (control : Bytes) : Bool := decide ((control.getD 0 0).toNat % 2 = 1)

end BitcoinTapSoundnessV2
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyTaprootCommitment, ComputeTaprootMerkleRoot, ComputeTapleafHash, ComputeTapbranchHash (src/script/interpreter.cpp: https://github.com/bitcoin/bitcoin/blob/a773e1e33b349dc819b5a0edc1c7a4839dc73b48/src/script/interpreter.cpp); XOnlyPubKey::CheckTapTweak, ComputeTapTweakHash (src/pubkey.cpp); secp256k1_xonly_pubkey_tweak_add_check; BIP341
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_BitcoinTapSoundnessV2.lean

Conventions used throughout this read-back. A byte is an 8-bit vector; a byte string is a finite list of bytes (possibly empty); ∥\|∥ is concatenation of byte strings; ∣x∣|x|∣x∣ is the length of xxx. SHA256\mathrm{SHA256}SHA256 denotes the bundle's own executable function sha256: a total function from byte strings to byte strings that appends the byte 0x80\mathtt{0x80}0x80, then zero bytes until the length is ≡56(mod64)\equiv 56 \pmod{64}≡56(mod64), then the bit-length of the original message as 8 big-endian bytes; splits the padded string into 64-byte chunks; folds the SHA-256 compression function over the chunks from the standard initial state; and emits the eight 32-bit state words as big-endian 4-byte groups (a 32-byte string). It is defined on every byte string. ascii(t)\mathrm{ascii}(t)ascii(t) is the list of UTF-8 code units of the string ttt, each taken as one byte. The preamble's tagged(t,m)\mathrm{tagged}(t, m)tagged(t,m) is SHA256(SHA256(ascii(t)) ∥ SHA256(ascii(t)) ∥ m)\mathrm{SHA256}\big(\mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, \mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, m\big)SHA256(SHA256(ascii(t))∥SHA256(ascii(t))∥m).

The file declares the following, in order.


1. Collides

For byte strings xxx and yyy, Collides(x,y)\mathrm{Collides}(x, y)Collides(x,y) is the proposition

x≠y  ∧  SHA256(x)=SHA256(y).x \neq y \;\wedge\; \mathrm{SHA256}(x) = \mathrm{SHA256}(y).x=y∧SHA256(x)=SHA256(y).

It requires both conjuncts: the two strings must be different byte strings (as lists, so differing in length or in some byte) and have identical 32-byte SHA-256 output. No length constraint is placed on xxx or yyy; either may be empty. Note that Collides(x,x)\mathrm{Collides}(x, x)Collides(x,x) is false for every xxx.

2. taggedPre

For a string ttt and a byte string mmm,

taggedPre(t,m)  =  SHA256(ascii(t)) ∥ SHA256(ascii(t)) ∥ m,\mathrm{taggedPre}(t, m) \;=\; \mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, \mathrm{SHA256}(\mathrm{ascii}(t)) \,\|\, m,taggedPre(t,m)=SHA256(ascii(t))∥SHA256(ascii(t))∥m,

a byte string of length 64+∣m∣64 + |m|64+∣m∣. This is exactly the string whose SHA-256 the preamble's tagged(t,m)\mathrm{tagged}(t,m)tagged(t,m) computes, i.e. tagged(t,m)=SHA256(taggedPre(t,m))\mathrm{tagged}(t, m) = \mathrm{SHA256}(\mathrm{taggedPre}(t, m))tagged(t,m)=SHA256(taggedPre(t,m)) by unfolding (the file states this as a comment; the equation itself is a separate theorem).

3. leafMsg

For a byte vvv and a byte string sss,

leafMsg(v,s)  =  [v] ∥ writeCompactSize(∣s∣) ∥ s,\mathrm{leafMsg}(v, s) \;=\; [v] \,\|\, \mathrm{writeCompactSize}(|s|) \,\|\, s,leafMsg(v,s)=[v]∥writeCompactSize(∣s∣)∥s,

where writeCompactSize(n)\mathrm{writeCompactSize}(n)writeCompactSize(n) is the preamble's Bitcoin compact-size encoding of the natural number nnn: if n<253n < 253n<253, the single byte nnn; else if n≤0xffffn \le \mathtt{0xffff}n≤0xffff, the byte 253253253 followed by the 2 little-endian bytes of nnn; else if n≤0xffffffffn \le \mathtt{0xffffffff}n≤0xffffffff, the byte 254254254 followed by the 4 little-endian bytes of nnn; otherwise the byte 255255255 followed by the 8 little-endian bytes of nnn (reduced modulo 2642^{64}264). The preamble's tapleafHash(v,s)\mathrm{tapleafHash}(v, s)tapleafHash(v,s) is tagged("TapLeaf",[v]∥writeCompactSize(∣s∣)∥s)\mathrm{tagged}(\text{"TapLeaf"}, [v] \| \mathrm{writeCompactSize}(|s|) \| s)tagged("TapLeaf",[v]∥writeCompactSize(∣s∣)∥s), i.e. tagged("TapLeaf",leafMsg(v,s))\mathrm{tagged}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s))tagged("TapLeaf",leafMsg(v,s)) by unfolding. No constraint is placed on vvv (any of the 256 byte values) or on ∣s∣|s|∣s∣.

4. branchMsg

For byte strings aaa and bbb,

branchMsg(a,b)  =  {a ∥ bif lexLt(a,b)b ∥ aotherwise,\mathrm{branchMsg}(a, b) \;=\; \begin{cases} a \,\|\, b & \text{if } \mathrm{lexLt}(a, b) \\ b \,\|\, a & \text{otherwise,} \end{cases}branchMsg(a,b)={a∥bb∥a​if lexLt(a,b)otherwise,​

where lexLt\mathrm{lexLt}lexLt is the preamble's Boolean strict lexicographic comparison on byte strings, defined recursively: lexLt([],[])=false\mathrm{lexLt}([], []) = \mathrm{false}lexLt([],[])=false; lexLt([],b::bs)=true\mathrm{lexLt}([], b{::}bs) = \mathrm{true}lexLt([],b::bs)=true; lexLt(a::as,[])=false\mathrm{lexLt}(a{::}as, []) = \mathrm{false}lexLt(a::as,[])=false; and lexLt(a::as,b::bs)\mathrm{lexLt}(a{::}as, b{::}bs)lexLt(a::as,b::bs) is true if the byte value of aaa is less than that of bbb, false if the byte value of bbb is less than that of aaa, and otherwise equals lexLt(as,bs)\mathrm{lexLt}(as, bs)lexLt(as,bs). Thus a proper prefix is less than the longer string, and lexLt(x,x)\mathrm{lexLt}(x, x)lexLt(x,x) is false for all xxx, so branchMsg(x,x)=x∥x\mathrm{branchMsg}(x, x) = x \| xbranchMsg(x,x)=x∥x. The preamble's tapbranchHash(a,b)\mathrm{tapbranchHash}(a, b)tapbranchHash(a,b) is tagged("TapBranch",if lexLt(a,b) then a∥b else b∥a)\mathrm{tagged}(\text{"TapBranch"}, \text{if } \mathrm{lexLt}(a,b) \text{ then } a\|b \text{ else } b\|a)tagged("TapBranch",if lexLt(a,b) then a∥b else b∥a), i.e. tagged("TapBranch",branchMsg(a,b))\mathrm{tagged}(\text{"TapBranch"}, \mathrm{branchMsg}(a,b))tagged("TapBranch",branchMsg(a,b)) by unfolding. No length constraint is placed on aaa or bbb.

5. TapTree

An inductive type with two constructors: leaf(v,s)\mathrm{leaf}(v, s)leaf(v,s) for a byte vvv ("version") and a byte string sss ("script"); and branch(l,r)\mathrm{branch}(l, r)branch(l,r) for two trees lll and rrr. Every tree is finite, and every tree has at least one leaf. Equality of trees is decidable and the type has a printer; nothing else (no ordering, no balance, no depth bound, no constraint on vvv or sss) is imposed.

6. TapTree.hash

The hash of a tree, a byte string, by structural recursion:

hash(leaf(v,s))=tapleafHash(v,s),hash(branch(l,r))=tapbranchHash(hash(l),hash(r)),\mathrm{hash}(\mathrm{leaf}(v, s)) = \mathrm{tapleafHash}(v, s), \qquad \mathrm{hash}(\mathrm{branch}(l, r)) = \mathrm{tapbranchHash}(\mathrm{hash}(l), \mathrm{hash}(r)),hash(leaf(v,s))=tapleafHash(v,s),hash(branch(l,r))=tapbranchHash(hash(l),hash(r)),

with tapleafHash\mathrm{tapleafHash}tapleafHash and tapbranchHash\mathrm{tapbranchHash}tapbranchHash as unfolded above. Since tapbranchHash\mathrm{tapbranchHash}tapbranchHash orders its two arguments lexicographically, hash(branch(l,r))=hash(branch(r,l))\mathrm{hash}(\mathrm{branch}(l, r)) = \mathrm{hash}(\mathrm{branch}(r, l))hash(branch(l,r))=hash(branch(r,l)) by unfolding.

7. TapTree.leaves

The list of leaf hashes of a tree, by structural recursion:

leaves(leaf(v,s))=[tapleafHash(v,s)],leaves(branch(l,r))=leaves(l) ∥ leaves(r).\mathrm{leaves}(\mathrm{leaf}(v, s)) = [\mathrm{tapleafHash}(v, s)], \qquad \mathrm{leaves}(\mathrm{branch}(l, r)) = \mathrm{leaves}(l) \,\|\, \mathrm{leaves}(r).leaves(leaf(v,s))=[tapleafHash(v,s)],leaves(branch(l,r))=leaves(l)∥leaves(r).

It is a list of hashes (32-byte strings), not of (v,s)(v, s)(v,s) pairs; two distinct leaves with the same hash appear twice. Membership h∈leaves(T)h \in \mathrm{leaves}(T)h∈leaves(T) means hhh equals some element of that list.

8. TapTree.subtreesAt

The list of subtrees of TTT at depth ddd, a list of trees, by recursion on TTT and ddd:

  • subtreesAt(T,0)=[T]\mathrm{subtreesAt}(T, 0) = [T]subtreesAt(T,0)=[T] for every tree TTT;
  • subtreesAt(leaf(v,s),d+1)=[]\mathrm{subtreesAt}(\mathrm{leaf}(v, s), d+1) = []subtreesAt(leaf(v,s),d+1)=[] (the empty list);
  • subtreesAt(branch(l,r),d+1)=subtreesAt(l,d) ∥ subtreesAt(r,d)\mathrm{subtreesAt}(\mathrm{branch}(l, r), d+1) = \mathrm{subtreesAt}(l, d) \,\|\, \mathrm{subtreesAt}(r, d)subtreesAt(branch(l,r),d+1)=subtreesAt(l,d)∥subtreesAt(r,d).

So for ddd greater than the depth of every node of TTT the result is empty, and for a tree whose leaves sit at different depths, subtreesAt(T,d)\mathrm{subtreesAt}(T, d)subtreesAt(T,d) lists only the nodes exactly at depth ddd (leaves above depth ddd contribute nothing).

9. walk

A function taking a tree TTT, a list of byte strings path\mathit{path}path ("Merkle path nodes"), and a byte string hhh, and returning either a tree (left result, written inl(U)\mathrm{inl}(U)inl(U)) or a pair of byte strings (right result, written inr(x,y)\mathrm{inr}(x, y)inr(x,y)). It is defined by recursion on the path, case by case:

  • Empty path. walk(T,[],h)=inl(T)\mathrm{walk}(T, [], h) = \mathrm{inl}(T)walk(T,[],h)=inl(T), for every TTT and every hhh. No comparison between hhh and hash(T)\mathrm{hash}(T)hash(T) is made.

  • Non-empty path n::restn :: \mathit{rest}n::rest. First compute the recursive result R=walk(T,rest,tapbranchHash(h,n))R = \mathrm{walk}(T, \mathit{rest}, \mathrm{tapbranchHash}(h, n))R=walk(T,rest,tapbranchHash(h,n)), i.e. the walk on the shorter path with the hash replaced by the branch hash of hhh and nnn. Then:

    • if R=inr(c)R = \mathrm{inr}(c)R=inr(c) for some pair ccc, the result is inr(c)\mathrm{inr}(c)inr(c) (the pair is passed up unchanged);
    • if R=inl(leaf(v,s))R = \mathrm{inl}(\mathrm{leaf}(v, s))R=inl(leaf(v,s)), the result is
inr(taggedPre("TapLeaf",leafMsg(v,s)),  taggedPre("TapBranch",branchMsg(h,n))),\mathrm{inr}\big(\mathrm{taggedPre}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s)),\; \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(h, n))\big),inr(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(h,n))),
regardless of whether $h$ or any hash matches anything; this is the case where the walk reached a leaf while path nodes remained;
  • if R=inl(branch(l,r))R = \mathrm{inl}(\mathrm{branch}(l, r))R=inl(branch(l,r)), then: if h=hash(l)h = \mathrm{hash}(l)h=hash(l) the result is inl(l)\mathrm{inl}(l)inl(l); otherwise, if h=hash(r)h = \mathrm{hash}(r)h=hash(r) the result is inl(r)\mathrm{inl}(r)inl(r); otherwise the result is
inr(taggedPre("TapBranch",branchMsg(hash(l),hash(r))),  taggedPre("TapBranch",branchMsg(h,n))).\mathrm{inr}\big(\mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(\mathrm{hash}(l), \mathrm{hash}(r))),\; \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(h, n))\big).inr(taggedPre("TapBranch",branchMsg(hash(l),hash(r))),taggedPre("TapBranch",branchMsg(h,n))).
When $h$ equals both children's hashes, the left child $l$ is chosen.

Unwinding the recursion for a path [n1,…,nk][n_1, \dots, n_k][n1​,…,nk​]: writing h0=hh_0 = hh0​=h and hi=tapbranchHash(hi−1,ni)h_i = \mathrm{tapbranchHash}(h_{i-1}, n_i)hi​=tapbranchHash(hi−1​,ni​), the innermost call is walk(T,[],hk)=inl(T)\mathrm{walk}(T, [], h_k) = \mathrm{inl}(T)walk(T,[],hk​)=inl(T); then, going outward, the step for nkn_knk​ compares hk−1h_{k-1}hk−1​ against the children of TTT, the step for nk−1n_{k-1}nk−1​ compares hk−2h_{k-2}hk−2​ against the children of the chosen child, and so on down to the step for n1n_1n1​, which compares h0=hh_0 = hh0​=h against the children of the node reached. Thus the path is listed leaf-end first and the tree is descended from the root. The function never checks that hk=hash(T)h_k = \mathrm{hash}(T)hk​=hash(T), never checks any lengths, and never checks that a returned pair actually collides: the pair is simply the two taggedPre\mathrm{taggedPre}taggedPre strings written above. If the path is longer than the depth at which a leaf is reached, the leaf case fires and the remaining path nodes are not inspected (except that they have already been folded into the hih_ihi​). Each returned pair is an explicit expression in TTT, the path nodes and hhh.

10. scriptPathWitness

For a tree TTT, a byte string control\mathit{control}control, a byte vvv and a byte string sss, an optional pair of byte strings, defined by cases on

W=walk(T,  controlNodes(control),  tapleafHash(v,s)):W = \mathrm{walk}\big(T,\; \mathrm{controlNodes}(\mathit{control}),\; \mathrm{tapleafHash}(v, s)\big):W=walk(T,controlNodes(control),tapleafHash(v,s)):
  • if W=inr(c)W = \mathrm{inr}(c)W=inr(c), the result is some(c)\mathrm{some}(c)some(c);
  • if W=inl(leaf(v′,s′))W = \mathrm{inl}(\mathrm{leaf}(v', s'))W=inl(leaf(v′,s′)) for any v′,s′v', s'v′,s′, the result is none\mathrm{none}none (the leaf's own v′,s′v', s'v′,s′ are discarded and not compared with v,sv, sv,s);
  • if W=inl(branch(l,r))W = \mathrm{inl}(\mathrm{branch}(l, r))W=inl(branch(l,r)), the result is
some(taggedPre("TapLeaf",leafMsg(v,s)),  taggedPre("TapBranch",branchMsg(hash(l),hash(r)))).\mathrm{some}\big(\mathrm{taggedPre}(\text{"TapLeaf"}, \mathrm{leafMsg}(v, s)),\; \mathrm{taggedPre}(\text{"TapBranch"}, \mathrm{branchMsg}(\mathrm{hash}(l), \mathrm{hash}(r)))\big).some(taggedPre("TapLeaf",leafMsg(v,s)),taggedPre("TapBranch",branchMsg(hash(l),hash(r)))).

Here controlNodes(control)\mathrm{controlNodes}(\mathit{control})controlNodes(control) is the preamble's function: let m=⌊(∣control∣−˙33)/32⌋m = \lfloor (|\mathit{control}| \dot{-} 33) / 32 \rfloorm=⌊(∣control∣−˙​33)/32⌋, where −˙\dot{-}−˙​ is truncated natural-number subtraction (so m=0m = 0m=0 whenever ∣control∣<33+32|\mathit{control}| < 33 + 32∣control∣<33+32); the result is the list of mmm byte strings obtained from control\mathit{control}control with its first 33 bytes dropped by repeatedly taking the first 32 bytes and dropping them (each of the mmm chunks is a full 32 bytes, since the dropped string has at least 32m32m32m bytes); any trailing bytes beyond the mmm chunks are ignored. In particular, if ∣control∣<65|\mathit{control}| < 65∣control∣<65 the path is empty, the walk returns inl(T)\mathrm{inl}(T)inl(T), and the witness is none\mathrm{none}none if TTT is a leaf and the pair above (with l,rl, rl,r the root's children) if TTT is a branch. The function performs no check that the folded root equals hash(T)\mathrm{hash}(T)hash(T) and no check that a returned pair collides.

11. TweakCollision

For byte strings q,t1,t2q, t_1, t_2q,t1​,t2​, a Boolean parity\mathit{parity}parity, and a pair of natural numbers P=(Px,Py)P = (P_x, P_y)P=(Px​,Py​), TweakCollision(q,parity,P,t1,t2)\mathrm{TweakCollision}(q, \mathit{parity}, P, t_1, t_2)TweakCollision(q,parity,P,t1​,t2​) is the proposition

t1≠t2  ∧  ∣t1∣=32  ∧  ∣t2∣=32  ∧  xonlyTweakAddCheck(q,parity,P,t1)=true  ∧  xonlyTweakAddCheck(q,parity,P,t2)=true.t_1 \neq t_2 \;\wedge\; |t_1| = 32 \;\wedge\; |t_2| = 32 \;\wedge\; \mathrm{xonlyTweakAddCheck}(q, \mathit{parity}, P, t_1) = \mathrm{true} \;\wedge\; \mathrm{xonlyTweakAddCheck}(q, \mathit{parity}, P, t_2) = \mathrm{true}.t1​=t2​∧∣t1​∣=32∧∣t2​∣=32∧xonlyTweakAddCheck(q,parity,P,t1​)=true∧xonlyTweakAddCheck(q,parity,P,t2​)=true.

Here xonlyTweakAddCheck(out,parity,P,tw)\mathrm{xonlyTweakAddCheck}(\mathit{out}, \mathit{parity}, P, \mathit{tw})xonlyTweakAddCheck(out,parity,P,tw) is the preamble's Boolean function: let t=beVal(tw)t = \mathrm{beVal}(\mathit{tw})t=beVal(tw) be the big-endian natural-number value of the byte string tw\mathit{tw}tw (fold acc↦256 acc+byte\mathit{acc} \mapsto 256\,\mathit{acc} + \text{byte}acc↦256acc+byte from 000); if t≥nt \ge nt≥n (the secp256k1 group order constant n=0xFFFFFFFF…BFD25E8CD0364141n = \mathtt{0xFFFFFFFF\ldots BFD25E8CD0364141}n=0xFFFFFFFF…BFD25E8CD0364141) the result is false; otherwise compute Q=padd(some(P),pmul(t,G))Q = \mathrm{padd}(\mathrm{some}(P), \mathrm{pmul}(t, G))Q=padd(some(P),pmul(t,G)), where G=(Gx,Gy)G = (G_x, G_y)G=(Gx​,Gy​) is the secp256k1 base-point constant, pmul\mathrm{pmul}pmul is double-and-add scalar multiplication with 257 steps of fuel starting from the point at infinity (so pmul(0,G)\mathrm{pmul}(0, G)pmul(0,G) is the point at infinity), and padd\mathrm{padd}padd is affine addition on points-or-infinity modulo the field prime p=2256−232−977p = 2^{256} - 2^{32} - 977p=2256−232−977 (infinity is the identity; two points with x1≡x2(modp)x_1 \equiv x_2 \pmod px1​≡x2​(modp) give infinity when y1+y2≡0(modp)y_1 + y_2 \equiv 0 \pmod py1​+y2​≡0(modp) and otherwise the doubling formula with the field inverse computed by Fermat exponentiation, where 000 inverts to 000; otherwise the chord formula); if QQQ is infinity the result is false; otherwise, with Q=(qx,qy)Q = (q_x, q_y)Q=(qx​,qy​), the result is [be32(qx)=out]∧[(qy mod 2=1)=parity]\big[\mathrm{be32}(q_x) = \mathit{out}\big] \wedge \big[(q_y \bmod 2 = 1) = \mathit{parity}\big][be32(qx​)=out]∧[(qy​mod2=1)=parity], where be32(x)\mathrm{be32}(x)be32(x) is the 32-byte big-endian encoding of xxx (reduced modulo 22562^{256}2256). Nothing in TweakCollision\mathrm{TweakCollision}TweakCollision requires PPP to lie on the curve, qqq to have length 32, or t1,t2t_1, t_2t1​,t2​ to be related to any hash.

12. HonestOutput

For byte strings qqq and internal32\mathit{internal32}internal32, a Boolean parity\mathit{parity}parity, and a tree TTT, HonestOutput(q,internal32,parity,T)\mathrm{HonestOutput}(q, \mathit{internal32}, \mathit{parity}, T)HonestOutput(q,internal32,parity,T) is the proposition

checkTapTweak(q,internal32,hash(T),parity)=true,\mathrm{checkTapTweak}(q, \mathit{internal32}, \mathrm{hash}(T), \mathit{parity}) = \mathrm{true},checkTapTweak(q,internal32,hash(T),parity)=true,

where the preamble's checkTapTweak(q,i,root,parity)\mathrm{checkTapTweak}(q, i, \mathit{root}, \mathit{parity})checkTapTweak(q,i,root,parity) is: if liftX(beVal(i))\mathrm{liftX}(\mathrm{beVal}(i))liftX(beVal(i)) is none\mathrm{none}none the value is false; otherwise, with liftX(beVal(i))=some(P)\mathrm{liftX}(\mathrm{beVal}(i)) = \mathrm{some}(P)liftX(beVal(i))=some(P), the value is xonlyTweakAddCheck(q,parity,P,tapTweakHash(i,root))\mathrm{xonlyTweakAddCheck}(q, \mathit{parity}, P, \mathrm{tapTweakHash}(i, \mathit{root}))xonlyTweakAddCheck(q,parity,P,tapTweakHash(i,root)). Here tapTweakHash(i,root)=tagged("TapTweak",i ∥ root)\mathrm{tapTweakHash}(i, \mathit{root}) = \mathrm{tagged}(\text{"TapTweak"}, i \,\|\, \mathit{root})tapTweakHash(i,root)=tagged("TapTweak",i∥root), and liftX(x)\mathrm{liftX}(x)liftX(x) is: none\mathrm{none}none if x≥px \ge px≥p; otherwise let y=(x3+7)(p+1)/4 mod py = (x^3 + 7)^{(p+1)/4} \bmod py=(x3+7)(p+1)/4modp; if y2≡x3+7(modp)y^2 \equiv x^3 + 7 \pmod py2≡x3+7(modp) then some(x,y′)\mathrm{some}(x, y')some(x,y′) with y′y'y′ the one of yyy and (p−y) mod p(p - y) \bmod p(p−y)modp that is even, else none\mathrm{none}none. No length constraint is placed on qqq or internal32\mathit{internal32}internal32 by this definition itself; beVal\mathrm{beVal}beVal of a string of any length is a natural number.

13. controlInternalKey

For a byte string control\mathit{control}control,

controlInternalKey(control)=take32(drop1(control)),\mathrm{controlInternalKey}(\mathit{control}) = \mathrm{take}_{32}(\mathrm{drop}_1(\mathit{control})),controlInternalKey(control)=take32​(drop1​(control)),

the bytes at positions 111 through 323232 (0-based). If control\mathit{control}control has fewer than 33 bytes the result is correspondingly shorter (empty when ∣control∣≤1|\mathit{control}| \le 1∣control∣≤1).

14. controlParity

For a byte string control\mathit{control}control,

controlParity(control)=[ (control[0] with default 0) mod 2=1 ],\mathrm{controlParity}(\mathit{control}) = \big[\, (\mathit{control}[0] \text{ with default } 0)\bmod 2 = 1 \,\big],controlParity(control)=[(control[0] with default 0)mod2=1],

a Boolean: true exactly when the first byte of control\mathit{control}control is odd, where a missing first byte (empty control\mathit{control}control) is read as the byte 000, giving false.

Human review
  • Endorsed by Shuze Chen · Nov 20, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Nov 20, 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