Script trees, honest Taproot outputs, and the two hardness assumptions of the script path
DefinitionBitcoinTapSoundnessNames over the Taproot mission's BitcoinTaproot; nothing of Core is re-transcribed.
Sha256Collision — there exist two different byte strings with the same sha256.
TapTree — a binary tree whose leaves carry a leaf version byte and a script (the tree the output's creator built, BIP341). TapTree.hash is tapleafHash version script at a leaf and tapbranchHash of the children's hashes at a branch; TapTree.leaves lists the leaf hashes in order; TapTree.subtreesAt T d lists the subtrees at depth (the tree itself at depth 0, nothing below a leaf).
TweakCollision q parity P — two different 32-byte tweak scalars that both pass xonlyTweakAddCheck q parity P (Core's secp256k1_xonly_pubkey_tweak_add_check): both carry the internal point to the output key with the given parity. This is a discrete-logarithm relation ( times is the point at infinity, with below the group order), which the model does not attempt to rule out.
HonestOutput q internal32 parity T — checkTapTweak q internal32 T.hash parity = true: the output key is the internal key tweaked by the root of , with parity parity (XOnlyPubKey::CheckTapTweak).
controlInternalKey control — bytes 1 to 32 of a control block; controlParity control — bit 0 of its first byte. These are the two fields VerifyTaprootCommitment reads from the control block besides the path.
Formalization Note. tagged, tapleafHash, tapbranchHash, controlNodes, taprootMerkleRoot, tapTweakHash, xonlyTweakAddCheck, checkTapTweak, verifyTaprootCommitment are the Taproot mission's; sha256, taggedHash, liftX, beVal the serialization and signature missions'. Only Std is imported.
Deprecated. Superseded by BitcoinTapSoundnessV2 (revision 2, BitcoinTapSoundnessV2): this revision's collision alternatives were closed propositions (Sha256Collision, and TweakCollision without a length constraint), which are provable by counting and so made the statement trivially true; the V2 declarations name the colliding strings and the two 32-byte tweaks explicitly, computed from the inputs.
import Definitions.Def_BitcoinTaproot /-! # Soundness of the Taproot script path A Taproot output commits to a tree of scripts through its tweaked key. A spender opens one leaf by presenting a control block: the internal key, a parity bit, and a Merkle path. The claim behind the design is that nobody can open a leaf the output's creator did not put in the tree. In the model that claim reduces to two hardness assumptions, which this file names so that the theorem can be stated as a reduction: a collision of SHA-256, or two different tweak scalars carrying the same internal key to the same output key (a discrete-logarithm relation on secp256k1). -/ namespace BitcoinTapSoundness open BitcoinSer BitcoinTaproot /-- A collision of SHA-256: two different messages with the same digest. -/ def Sha256Collision : Prop := ∃ x y : Bytes, x ≠ y ∧ sha256 x = sha256 y /-- 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) /-- The hash of a tree: `ComputeTapleafHash` for a leaf, `ComputeTapbranchHash` of the children's hashes for 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 /-- Two different tweak scalars (32-byte strings) 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, outside the model's reach. -/ def TweakCollision (q : Bytes) (parity : Bool) (P : Nat × Nat) : Prop := ∃ t₁ t₂ : Bytes, t₁ ≠ t₂ ∧ 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 BitcoinTapSoundness
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_BitcoinTapSoundness.lean
Throughout, a byte is an 8-bit value, is the set of finite byte strings (any length, including empty), is concatenation, is the bundle's own executable SHA-256 (a total function from to 32-byte strings), is UTF-8 encoding of a string, and . is the compact-size encoding of (one byte if ; + 2 little-endian bytes if ; + 4 bytes if ; + 8 bytes of otherwise). with the byte used as given. is lexicographic order on byte strings (first differing byte decides by numeric value; a proper prefix is smaller; no string is itself) and , which is symmetric.
Sha256Collision
A closed proposition (no parameters):
The two strings may have any lengths (not necessarily equal); "" is inequality of byte strings. Because here is a specific total function from the infinite set to the finite set of 32-byte strings, this proposition's truth value is a fixed mathematical fact (by counting, such a pair exists); it is a definition, not an axiom or assumption, and nothing in the file postulates it to be false.
TapTree
An inductively defined type of finite binary trees: a tap tree is either a leaf carrying a byte (the "version") and a byte string (the "script", any length), or a branch with exactly two ordered subtrees and (both tap trees). There are no other constructors; every internal node has exactly two children; a single leaf is a tap tree. No constraint is placed on or .
TapTree.hash
The hash of a tap tree, a 32-byte string, defined by recursion:
Since orders its two inputs lexicographically before hashing, .
TapTree.leaves
The list of leaf hashes of a tap tree, defined by recursion:
It lists 32-byte hashes (not the pairs ), left to right, keeping repetitions. It is never empty.
TapTree.subtreesAt
The list of subtrees of a tap tree at depth , defined by recursion on and :
So it lists, left to right, exactly the subtrees whose root is at depth below the root of ; it is empty when is larger than the depth of every node reached (e.g. a single leaf at any ).
TweakCollision
For a byte string , a Boolean and a point (a pair of natural numbers, not required to lie on the curve or be reduced mod ):
where is: let be the big-endian value of (any length; empty ; leading zero bytes do not change it); if (with the fixed secp256k1 group-order constant), the result is false; otherwise let , using the file's affine addition formulas modulo (identity ; doubling when the abscissas agree mod and the ordinates do not sum to mod , else ; chord formula otherwise; Fermat inversion with ) and double-and-add scalar multiplication with 257 steps () from the fixed base point ; if , false; otherwise true exactly when the 32-byte big-endian encoding of equals as a byte string (so must have length 32) and ( odd) . The witnesses are required to differ only as byte strings; no length (such as 32) is imposed on them, and since the check reads them only through , if some passes the check then and are two distinct witnesses. Hence holds exactly when at least one byte string passes .
HonestOutput
For byte strings , , a Boolean and a tap tree :
where is: compute — undefined if ; otherwise with and , if it is the point with if is even and otherwise, and undefined if not. If undefined, is false. Otherwise, with that point, it is as defined above. No length is imposed on or by the definition itself; the check can only succeed if is exactly 32 bytes, and enters only through its big-endian value (any length) and through its raw bytes inside the tweak hash input.
controlInternalKey
For a byte string : . If this is exactly the bytes at zero-based positions through ; if it is the bytes after the first; if is empty it is the empty string.
controlParity
For a byte string : if the numeric value of the first byte of is odd, and otherwise; if is empty the first byte defaults to , so the result is .