Script trees, explicit collision witnesses, and honest Taproot outputs (revision 2)
DefinitionBitcoinTapSoundnessV2Names 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 up to the root of 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.
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
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; is the length of . denotes the bundle's own executable function sha256: a total function from byte strings to byte strings that appends the byte , then zero bytes until the length is , 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. is the list of UTF-8 code units of the string , each taken as one byte. The preamble's is .
The file declares the following, in order.
1. Collides
For byte strings and , is the proposition
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 or ; either may be empty. Note that is false for every .
2. taggedPre
For a string and a byte string ,
a byte string of length . This is exactly the string whose SHA-256 the preamble's computes, i.e. by unfolding (the file states this as a comment; the equation itself is a separate theorem).
3. leafMsg
For a byte and a byte string ,
where is the preamble's Bitcoin compact-size encoding of the natural number : if , the single byte ; else if , the byte followed by the 2 little-endian bytes of ; else if , the byte followed by the 4 little-endian bytes of ; otherwise the byte followed by the 8 little-endian bytes of (reduced modulo ). The preamble's is , i.e. by unfolding. No constraint is placed on (any of the 256 byte values) or on .
4. branchMsg
For byte strings and ,
where is the preamble's Boolean strict lexicographic comparison on byte strings, defined recursively: ; ; ; and is true if the byte value of is less than that of , false if the byte value of is less than that of , and otherwise equals . Thus a proper prefix is less than the longer string, and is false for all , so . The preamble's is , i.e. by unfolding. No length constraint is placed on or .
5. TapTree
An inductive type with two constructors: for a byte ("version") and a byte string ("script"); and for two trees and . 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 or ) is imposed.
6. TapTree.hash
The hash of a tree, a byte string, by structural recursion:
with and as unfolded above. Since orders its two arguments lexicographically, by unfolding.
7. TapTree.leaves
The list of leaf hashes of a tree, by structural recursion:
It is a list of hashes (32-byte strings), not of pairs; two distinct leaves with the same hash appear twice. Membership means equals some element of that list.
8. TapTree.subtreesAt
The list of subtrees of at depth , a list of trees, by recursion on and :
- for every tree ;
- (the empty list);
- .
So for greater than the depth of every node of the result is empty, and for a tree whose leaves sit at different depths, lists only the nodes exactly at depth (leaves above depth contribute nothing).
9. walk
A function taking a tree , a list of byte strings ("Merkle path nodes"), and a byte string , and returning either a tree (left result, written ) or a pair of byte strings (right result, written ). It is defined by recursion on the path, case by case:
-
Empty path. , for every and every . No comparison between and is made.
-
Non-empty path . First compute the recursive result , i.e. the walk on the shorter path with the hash replaced by the branch hash of and . Then:
- if for some pair , the result is (the pair is passed up unchanged);
- if , the result is
regardless of whether $h$ or any hash matches anything; this is the case where the walk reached a leaf while path nodes remained;
- if , then: if the result is ; otherwise, if the result is ; otherwise the result is
When $h$ equals both children's hashes, the left child $l$ is chosen.
Unwinding the recursion for a path : writing and , the innermost call is ; then, going outward, the step for compares against the children of , the step for compares against the children of the chosen child, and so on down to the step for , which compares 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 , never checks any lengths, and never checks that a returned pair actually collides: the pair is simply the two 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 ). Each returned pair is an explicit expression in , the path nodes and .
10. scriptPathWitness
For a tree , a byte string , a byte and a byte string , an optional pair of byte strings, defined by cases on
- if , the result is ;
- if for any , the result is (the leaf's own are discarded and not compared with );
- if , the result is
Here is the preamble's function: let , where is truncated natural-number subtraction (so whenever ); the result is the list of byte strings obtained from with its first 33 bytes dropped by repeatedly taking the first 32 bytes and dropping them (each of the chunks is a full 32 bytes, since the dropped string has at least bytes); any trailing bytes beyond the chunks are ignored. In particular, if the path is empty, the walk returns , and the witness is if is a leaf and the pair above (with the root's children) if is a branch. The function performs no check that the folded root equals and no check that a returned pair collides.
11. TweakCollision
For byte strings , a Boolean , and a pair of natural numbers , is the proposition
Here is the preamble's Boolean function: let be the big-endian natural-number value of the byte string (fold from ); if (the secp256k1 group order constant ) the result is false; otherwise compute , where is the secp256k1 base-point constant, is double-and-add scalar multiplication with 257 steps of fuel starting from the point at infinity (so is the point at infinity), and is affine addition on points-or-infinity modulo the field prime (infinity is the identity; two points with give infinity when and otherwise the doubling formula with the field inverse computed by Fermat exponentiation, where inverts to ; otherwise the chord formula); if is infinity the result is false; otherwise, with , the result is , where is the 32-byte big-endian encoding of (reduced modulo ). Nothing in requires to lie on the curve, to have length 32, or to be related to any hash.
12. HonestOutput
For byte strings and , a Boolean , and a tree , is the proposition
where the preamble's is: if is the value is false; otherwise, with , the value is . Here , and is: if ; otherwise let ; if then with the one of and that is even, else . No length constraint is placed on or by this definition itself; of a string of any length is a natural number.
13. controlInternalKey
For a byte string ,
the bytes at positions through (0-based). If has fewer than 33 bytes the result is correspondingly shorter (empty when ).
14. controlParity
For a byte string ,
a Boolean: true exactly when the first byte of is odd, where a missing first byte (empty ) is read as the byte , giving false.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.