solution

Cây Merkle (Merkle tree) là cấu trúc dùng để xác thực toàn vẹn cho một tập hợp dữ liệu lớn (được dùng trong Bitcoin, Git, IPFS, ...) chỉ bằng một giá trị băm duy nhất gọi là Merkle root.

Cho $n$ lá (leaf) là các chuỗi dữ liệu $L_1, \ldots, L_n$. Xây dựng cây Merkle theo quy tắc sau, dùng SHA-256 (biểu diễn hex, chữ thường):

1. Băm từng lá: $h_i = \text{SHA256}(L_i)$.
2. Ở mỗi tầng, ghép các node thành từng cặp liên tiếp theo đúng thứ tự: node cha $= \text{SHA256}(h_{\text{trái}} \Vert h_{\text{phải}})$ (nối chuỗi hex).
3. Nếu tầng hiện tại có số node lẻ, nhân đôi node cuối cùng (dùng chính nó làm cặp với chính nó) trước khi ghép cặp.
4. Lặp lại cho đến khi chỉ còn một node duy nhất — đó chính là Merkle root.

Trường hợp đặc biệt: nếu $n = 1$, Merkle root chính là $h_1$.

Ví dụ: $n = 3$ với các lá "a", "b", "c": băm 3 lá được $h_1, h_2, h_3$; vì lẻ nên nhân đôi $h_3$ thành $(h_1, h_2, h_3, h_3)$; ghép cặp tầng 1 được 2 node; ghép cặp tiếp được 1 node — đó là kết quả.