solution

Cây Merkle (Merkle Tree) tổng hợp mã băm của các giao dịch trong một khối thành một Merkle root duy nhất, phục vụ xác minh tính toàn vẹn dữ liệu. Thuật toán xây dựng (mô phỏng kiểu Bitcoin, dùng một lớp SHA-256 để đơn giản hóa — khác Bitcoin double-SHA256):

1. Bắt đầu với danh sách mã băm giao dịch theo đúng thứ tự cho trước (tầng lá).
2. Ở mỗi tầng, nếu số lượng nút hiện tại là số lẻ và lớn hơn 1, nhân đôi nút cuối cùng (thêm một bản sao vào cuối danh sách).
3. Ghép cặp liên tiếp $(node_{2i}, node_{2i+1})$: chuyển mỗi hash hex về dạng byte thô, nối byte trái với byte phải, băm SHA-256 kết quả nối đó để tạo 1 nút ở tầng trên.
4. Lặp lại bước 2–3 cho đến khi chỉ còn đúng 1 nút — đó chính là Merkle root.

Quy ước đặc biệt: nếu $n=0$ (không có giao dịch), Merkle root là chuỗi gồm 64 ký tự 0. Nếu $n=1$, Merkle root chính là mã băm giao dịch đó (không băm thêm lần nào).

Ví dụ: với 2 giao dịch có hash lần lượt là 95cd603f...511f6 (SHA-256 của chuỗi tx0) và 709b55bd...9a201b (SHA-256 của chuỗi tx1), Merkle root là:

9db4d4c69f3d7236f4de569987d746845d8d85250703351226c5a3cdaf1f66ea