BLOCKCHAIN & WEB3 FUNDAMENTALS - Chapter 3, Exercise 1 Solution
==========================================================
Counting Sibling Hashes in an 8-Transaction Merkle Proof

PROBLEM
-------
A block contains 8 transactions, arranged in a Merkle tree exactly
like the diagram in this chapter but one level deeper. If you wanted
to prove transaction #5 (out of 8) is included in the block, how many
sibling hashes would you need, and why is that number so much smaller
than handing over all 8 transactions?

SOLUTION
--------
With 8 leaf transactions, the tree has one extra level compared to the
chapter's own 4-leaf diagram:

Level 0 (leaves):      8 transaction hashes
Level 1:                4 pair hashes
Level 2:                2 hashes
Level 3 (root):         1 Merkle root

To prove transaction #5 belongs to this tree, you walk up from leaf #5
to the root, and at each level you need exactly one sibling hash (the
hash of the node paired with the one on your own path) - never the
whole rest of that level.

- At the leaf level: you need the hash of transaction #6 (#5's pair),
  so the pair hash covering #5 and #6 can be recomputed.
- At the next level: you need the sibling pair-hash covering
  transactions #7-#8, so the level-2 hash covering #5-#8 can be
  recomputed.
- At the next level: you need the sibling hash covering transactions
  #1-#4, so the final Merkle root can be recomputed.

That's 3 sibling hashes total, to prove membership among 8
transactions - matching log base 2 of 8, which is exactly 3.

Compare that to handing over all 8 full transactions (and re-hashing
every one of them) to prove the same thing: as the number of
transactions in a block grows into the thousands, log2(n) stays small
(log2(1000) is under 10), while handing over every transaction grows
linearly and becomes genuinely impractical for a lightweight client to
download and check.

ANSWER: 3 sibling hashes are needed (one per level of the tree), not
all 8 transactions - because a Merkle proof only ever needs one hash
per level on the path from your leaf up to the root, so proof size
grows with the logarithm of the transaction count rather than growing
in direct proportion to it.

----
WHY THIS WORKS AS AN ANSWER

This directly extends the chapter's own 4-leaf worked example to a
concrete 8-leaf case, correctly applying the "one sibling per level"
rule and the log2(n) scaling claim the chapter makes, rather than just
restating the claim abstractly.