solution

Cây băm Merkle là thành phần cốt lõi của nhiều sơ đồ chữ ký hậu lượng tử dựa trên hàm băm (như XMSS, SPHINCS+): thay vì phải công khai hàng nghìn khoá công khai một lần, người ký chỉ cần công bố một gốc Merkle (Merkle root) duy nhất.

Cho danh sách $m$ giá trị lá $\ell_1, \dots, \ell_m$ (chuỗi ký tự). Băm lá: $h_i = \text{SHA256}(\ell_i)$ (mã hoá UTF-8, kết quả hex thường). Xây cây theo tầng: ở mỗi tầng, nếu số nút đang có là lẻ, nhân đôi nút cuối cùng để số nút thành chẵn; sau đó ghép từng cặp $(h_{2k-1}, h_{2k})$ theo đúng thứ tự và băm chuỗi hex nối liền: $\text{parent} = \text{SHA256}(\text{hex}(h_{2k-1}) \,\Vert\, \text{hex}(h_{2k}))$. Lặp lại cho đến khi chỉ còn một nút — đó là gốc Merkle. Quy ước: nếu $m = 0$, gốc là $\text{SHA256}(\varnothing)$ (băm chuỗi rỗng); nếu $m = 1$, gốc chính là $h_1$.

Ví dụ

Input:

3
tx1
tx2
tx3

Output:

fbf8b59f1ad5a1723f350e130dd75701c2b5c11a44b5ffc4e6ed48b2e1c34d8f