BAC-L0-FOUND-106
Merkle trees and inclusion proofs
How to prove a piece of data belongs to a set without transmitting the set. The structure that makes light clients and availability sampling possible.
- Level
- L0 — Foundation
- Duration
- 3 h
- Track
- Foundation
- Maintainer
- Developer Curriculum Architect
Learning objectives
- 01Build a Merkle tree from a set of transactions
- 02Produce and verify an inclusion proof
- 03Compute proof size as a function of leaf count
Guided lab
Implement the tree, proof generation and the verifier, then measure the logarithmic growth.
Independent lab
Extend the implementation to non-inclusion proofs over a sorted tree.
Security angle
The second-preimage extension attack on binary trees without proper domain separation.
Assessment
Proof verifier passing the workshop test suite.