# M01-L03 — Lab: Merkle tree and inclusion proofs

## Prerequisites
Java 21, terminal, no external dependencies. Complete M01-L02 first if applicable.

## Bài toán → Vấn đề → Giải pháp
- **Bài toán:** How can a client verify transaction inclusion without downloading all transactions?
- **Vấn đề:** Hashing all transactions on every query is wasteful.
- **Giải pháp:** Construct a binary Merkle tree and verify a sibling proof from leaf to root.

## Step-by-step
1. Read `theory.md`, predict the result and write down the invariant.
2. Open `starter/README.md`, create your own `Main.java` in `starter/`.
3. Compile: `javac Main.java` and run `java Main` from your starter directory.
4. Compare your result with `solution/Main.java`; run the solution using `javac Main.java && java Main`.
5. Trigger one negative case and explain why it is rejected.
6. Run `bash test.sh` from this lesson folder to validate the reference solution.
7. Record actual terminal output in your own lab notes. No RPC, wallet, or real funds required.

## Expected output
`All inclusion proofs pass; modified leaf fails.`

## Failure modes
- Invalid or tampered inputs must be rejected rather than silently accepted.
- All tests must be deterministic except the displayed nonce/hash values where explicitly noted.

## Deliverables
Starter implementation, output transcript, explanation of invariant, and comparison with solution.