Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

An empty path commits to the leaf

Proved
BitcoinTaproot.merkleRoot_base

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

bip341bip342bitcoinbitcoin-mainnetconsensusformal-verificationschnorrtaproottapscript

For a 33-byte control block (no path nodes), taprootMerkleRoot control leaf = leaf: the merkle root of a single-leaf tree is the leaf hash itself.

Preamble
import Definitions.Def_BitcoinTaproot
open BitcoinTaproot BitcoinSer BitcoinSig BitcoinVerify
open BitcoinScript hiding Bytes Byte
Formal statement
theorem BitcoinTaproot.merkleRoot_base (control leaf : Bytes) (h : control.length = BitcoinTaproot.TAPROOT_CONTROL_BASE_SIZE) :
    BitcoinTaproot.taprootMerkleRoot control leaf = leaf := by sorry
Source
Bitcoin Core a773e1e33b349dc819b5a0edc1c7a4839dc73b48: VerifyWitnessProgram (version 1), ExecuteWitnessScript, EvalScript under SigVersion::TAPSCRIPT, EvalChecksigTapscript, CheckSchnorrSignature, SignatureHashSchnorr, ComputeTapleafHash, ComputeTapbranchHash, ComputeTaprootMerkleRoot, VerifyTaprootCommitment, 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, src/secp256k1/src/modules/extrakeys/main_impl.h; IsOpSuccess, src/script/script.cpp; BIP340, BIP341, BIP342 at bips revision 100ba872c808946155b1eeb8c4568058f2eea0a7
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: BitcoinTaproot.merkleRoot_base

Binders. control\mathrm{control}control, leaf\mathrm{leaf}leaf : byte strings (finite lists of 8-bit values).

Hypothesis. ∣control∣=33|\mathrm{control}| = 33∣control∣=33 (the constant TAPROOT_CONTROL_BASE_SIZE, which is 333333).

Conclusion.

taprootMerkleRoot(control,leaf)=leaf.\mathrm{taprootMerkleRoot}(\mathrm{control}, \mathrm{leaf}) = \mathrm{leaf}.taprootMerkleRoot(control,leaf)=leaf.

Unfolded: taprootMerkleRoot(c,h)\mathrm{taprootMerkleRoot}(c, h)taprootMerkleRoot(c,h) is the left fold of tapbranchHash\mathrm{tapbranchHash}tapbranchHash over the list controlNodes(c)\mathrm{controlNodes}(c)controlNodes(c) starting from hhh, i.e. h0=hh_0 = hh0​=h, hj+1=tapbranchHash(hj,Nj)h_{j+1} = \mathrm{tapbranchHash}(h_j, N_j)hj+1​=tapbranchHash(hj​,Nj​), result hkh_khk​. Here controlNodes(c)\mathrm{controlNodes}(c)controlNodes(c) is built by first computing the node count k=⌊(∣c∣−˙33)/32⌋k = \lfloor (|c| \dot- 33)/32 \rfloork=⌊(∣c∣−˙​33)/32⌋ (natural-number subtraction, truncated at 000), dropping the first 333333 bytes of ccc, and then taking kkk successive chunks of 323232 bytes (each chunk is "take 323232" of what remains, then "drop 323232"). With ∣control∣=33|\mathrm{control}| = 33∣control∣=33 the count is k=0k = 0k=0, the node list is empty, and the fold returns its starting value leaf\mathrm{leaf}leaf unchanged; tapbranchHash\mathrm{tapbranchHash}tapbranchHash (the tagged hash tagged("TapBranch",⋅)\mathrm{tagged}(\texttt{"TapBranch"}, \cdot)tagged("TapBranch",⋅) of the lexicographically ordered concatenation of its two arguments) is never applied.

Edge cases the quantifiers include. leaf\mathrm{leaf}leaf of any length including empty; the contents of the 333333 control bytes are unconstrained (no parity, key, or on-curve condition is involved).

Human review
  • Endorsed by Shuze Chen · Oct 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by pitimespi · Oct 27, 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