Lesson 16 · Proofs and the odd-node rule

Proofs and the odd-node rule

In an odd tree a promoted leaf skips the level where it had no partner, so its proof is shorter. Today you handle proofs under the odd-node rule.

The goal

Generate and verify a proof for a promoted leaf in an odd-sized tree.

Start here - the target

TO DO

Scenario: A promoted leaf has a shorter proof that still verifies

Giventhe tree Build(["alice", "bob", "carol"]) with root 0xb019c95a

WhenProve is called for leaf index 2 ("carol"), which was promoted

Thenthe proof is a single step - sibling 0xebb8e925 on the left

AndVerifyProof of "carol" with that one-step proof against root 0xb019c95a returns true

Background

The Prove walk you already wrote handles this correctly, but it is worth seeing why. In the three-leaf tree, carol at index 2 is the odd node at level 0: it has no sibling, so it is promoted to level 1 with no proof step recorded. Up at level 1 it finally has a partner - the HashNode(alice, bob) subtree on its left - which becomes its single proof step. So its proof is one hash, not two.

Verification does not care that the proof is shorter. It hashes carol, sees one step with the sibling on the left, computes HashNode(0xebb8e925, HashLeaf("carol")), and lands exactly on the root 0xb019c95a. The promote rule stays invisible to the verifier because a promoted node contributes nothing at its lonely level - the path just has one fewer rung. Odd trees prove membership just as cleanly as even ones.

Make it work

// three leaves: level 0 = [La, Lb, Lc], level 1 = [HashNode(La,Lb), Lc]
// leaf 2 (Lc) has no sibling at level 0 -> promoted, no step recorded.
// at level 1 it pairs (on the right) with HashNode(La,Lb)=0xebb8e925 on the left.
proof := tree.Prove(2) // [{0xebb8e925, false}]

CheckpointDONE

A promoted leaf produces a shorter proof that still recomputes the root. Commit and stop here.