Appending a path node hashes the root with it
ProvedBitcoinTaproot.merkleRoot_snocFor a well-formed control block (length ) and a 32-byte node: taprootMerkleRoot (control ++ node) leaf = tapbranchHash (taprootMerkleRoot control leaf) node. The merkle root is a left fold of the branch hash along the path.
import Definitions.Def_BitcoinTaproot open BitcoinTaproot BitcoinSer BitcoinSig BitcoinVerify open BitcoinScript hiding Bytes Byte
theorem BitcoinTaproot.merkleRoot_snoc (control node leaf : Bytes)
(hc : BitcoinTaproot.TAPROOT_CONTROL_BASE_SIZE ≤ control.length)
(hm : (control.length - BitcoinTaproot.TAPROOT_CONTROL_BASE_SIZE) % BitcoinTaproot.TAPROOT_CONTROL_NODE_SIZE = 0)
(hn : node.length = BitcoinTaproot.TAPROOT_CONTROL_NODE_SIZE) :
BitcoinTaproot.taprootMerkleRoot (control ++ node) leaf =
BitcoinTaproot.tapbranchHash (BitcoinTaproot.taprootMerkleRoot control leaf) node := 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: BitcoinTaproot.merkleRoot_snoc
Binders. , , : byte strings (finite lists of 8-bit values).
Hypotheses.
- (where is
TAPROOT_CONTROL_BASE_SIZE); - (the subtraction is natural-number subtraction, but by hypothesis 1 it is an ordinary difference here; is
TAPROOT_CONTROL_NODE_SIZE); - .
Conclusion.
Unfolded. is the left fold over the list , where (truncated natural subtraction) and is the -th consecutive -byte chunk of after its first bytes (each chunk is the "take " of the remaining suffix; a trailing partial chunk is never produced because is the floor). if , and otherwise, where is byte-wise lexicographic strict order (empty is less than non-empty, equal strings are not less), and with the UTF-8 bytes of the tag. So the statement says: under the hypotheses, the node list of is the node list of followed by as one more -byte chunk, and the fold over the extended list equals one more step applied to the fold over the original list, with the accumulated hash as first argument and as second.
Edge cases the quantifiers include. (then the inner root is just and the claim is ); of arbitrary length; longer than the -byte maximum used elsewhere (no maximum is assumed here); control bytes otherwise unconstrained.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.