Script-path soundness at the commitment level: VerifyTaprootCommitment opens only committed leaves, up to a hash collision or a tweak collision
ProvedBitcoinTapSoundness.commitment_soundnessFor an output key , internal key internal32, parity bit and tree with HonestOutput q internal32 parity T, and any control block of length whose internal-key bytes are internal32 and whose parity bit is parity, and any leaf : if verifyTaprootCommitment control q (tapleafHash v s) = true then
tapleafHash v s ∈ T.leaves, or Sha256Collision, or there is a point with liftX (beVal internal32) = some P and TweakCollision q parity P.
If the control block's Merkle root equals the tree's root, script_path_soundness applies. Otherwise the two roots give two tweak hashes tapTweakHash internal32 ·; equal tweak hashes of different roots are a collision (tagged_collision, the internal key being a fixed 32-byte prefix), and different tweak hashes that both pass xonlyTweakAddCheck are a TweakCollision. This is the BIP341 claim that a spender cannot open a leaf the output's creator did not commit to, stated as a reduction to SHA-256 collision resistance and to the hardness of finding two tweaks for one output key.
Deprecated. Superseded by BitcoinTapSoundnessV2.commitment_soundness (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_BitcoinTapSoundness import Definitions.Def_BitcoinSer import Definitions.Def_BitcoinTaproot import Definitions.Def_BitcoinSig open BitcoinTapSoundness BitcoinSer BitcoinTaproot
theorem BitcoinTapSoundness.commitment_soundness (q internal32 : BitcoinSer.Bytes) (parity : Bool)
(T : BitcoinTapSoundness.TapTree) (hT : BitcoinTapSoundness.HonestOutput q internal32 parity T)
(control : BitcoinSer.Bytes) (k : Nat)
(hc : control.length = BitcoinTaproot.TAPROOT_CONTROL_BASE_SIZE + BitcoinTaproot.TAPROOT_CONTROL_NODE_SIZE * k)
(hkey : BitcoinTapSoundness.controlInternalKey control = internal32) (hpar : BitcoinTapSoundness.controlParity control = parity)
(v : BitcoinSer.Byte) (s : BitcoinSer.Bytes)
(h : BitcoinTaproot.verifyTaprootCommitment control q (BitcoinTaproot.tapleafHash v s) = true) :
BitcoinTaproot.tapleafHash v s ∈ T.leaves ∨ BitcoinTapSoundness.Sha256Collision ∨
∃ P, BitcoinSig.liftX (BitcoinSig.beVal internal32) = some P ∧ BitcoinTapSoundness.TweakCollision q parity P := by sorryRead-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: BitcoinTapSoundness.commitment_soundness
Statement. Let and ("internal32") be byte strings (finite sequences of 8-bit values; no length hypothesis is stated for either), ("parity") a Boolean, and a tap tree (a finite binary tree in which every internal node has exactly two ordered children and every leaf carries a byte and a byte string). Let ("control") be a byte string and a natural number (possibly ). Let be a byte and a byte string (any length). Assume all of the following:
- (hT) , i.e. ;
- (hc) ;
- (hkey) the 32 bytes of at positions through (zero-based; i.e. drop the first byte, then take 32) equal as byte strings — so under (hc), ;
- (hpar) exactly when the first byte of is odd (i.e. ; if were empty the first byte would default to , but (hc) rules this out);
- (h) .
Then at least one of the following three holds:
- is an element of the list of leaf hashes of ; or
- : there exist byte strings (any lengths, unrelated to the theorem's variables) with ; or
- there exists a point (a pair of natural numbers) such that (the lift succeeds and yields ) and holds, i.e. there exist byte strings with and .
Unfolded notions (hashing).
- is the bundle's own executable implementation of SHA-256, a total function from all finite byte strings to 32-byte strings. is UTF-8 encoding, and for a tag string ,
- is the compact-size encoding of (one byte if ; + 2 little-endian bytes if ; + 4 bytes if ; + 8 bytes of otherwise).
- ( used as given, no masking).
- is lexicographic order on byte strings (first differing byte decides; a proper prefix is smaller; no string is itself) and (symmetric in ).
- ; . ; (leaf hashes left to right, with repetitions). Disjunct (1) is membership of a 32-byte string in this list, not an assertion that the pair occurs in .
- Path nodes of : with ( truncated subtraction), drop the first 33 bytes of and cut the rest into consecutive 32-byte blocks , ignoring any leftover. Under (hc), exactly. The Merkle root from and a start hash is the left fold , equal to when .
- .
Unfolded notions (curve arithmetic).
- ; ; is the fixed secp256k1 base point given by two 256-bit constants.
- is the big-endian natural-number value of a byte string of any length (; leading zero bytes do not change the value). is the 32-byte big-endian encoding of .
- Points are either or pairs of natural numbers (not required to be reduced mod or to lie on the curve). Addition : is the identity; for , if then the result is when and otherwise the doubling formula with slope ; otherwise the chord formula with slope ; in both cases and . Inverses are computed by Fermat exponentiation, with the "inverse" of being . Scalar multiplication is double-and-add on the binary digits of with a fuel of 257 steps (exact for ), with .
- : if , undefined (none). Otherwise let ; if , the result is with if is even and otherwise (the even- point with abscissa ); if not, undefined.
- for byte strings (any lengths), Boolean , and point : let . If , false. Otherwise compute . If , false. Otherwise true exactly when as byte strings (so must be exactly 32 bytes) and ( is odd) .
- : if is undefined, false; otherwise, with its value, .
- , where is "drop one byte, take 32" (shorter if is short) and is the first byte of (default if empty). Under (hkey) and (hpar) this is .
- . The inequality is inequality of byte strings; no length is imposed on , and the check reads them only through , which ignores leading zero bytes. Consequently, whenever some passes the check, the strings and are two distinct witnesses; in particular, under (h), (hkey), (hpar), the tweak passes the check for the point .
- is the closed proposition ; since it concerns a fixed total function from infinitely many inputs to finitely many 32-byte outputs, its truth value is a fixed mathematical fact (such a pair exists by counting), not an assumption.
Edge cases made explicit. Hypotheses (hT) and (h) can only be true when is exactly 32 bytes and with succeeding; otherwise the theorem's hypotheses are unsatisfiable and it holds vacuously. is allowed (no path nodes; root ); no upper bound on is imposed. Under (hT), the same point is used with tweak ; under (h), with tweak . The conclusion's disjunct (3) quantifies over but fixes it to be the value of .
Sha256Collision can be proved, so this holds without any Taproot content