solution

Trong các sơ đồ chữ ký hậu lượng tử dựa trên hàm băm như XMSS/SPHINCS+, để chứng minh một lá thuộc cây Merkle mà không cần gửi toàn bộ cây, người ký gửi kèm đường dẫn xác thực (authentication path) — dãy các nút anh em (sibling) từ lá lên gốc.

Cho giá trị lá $\ell$, một dãy $k$ cặp $(\text{dir}_j, \text{sib}_j)$ theo thứ tự từ lá lên gốc, và một gốc được công bố $R$. Đặt $cur = \text{SHA256}(\ell)$. Với mỗi cặp theo thứ tự $j = 1, \dots, k$:

• Nếu $\text{dir}_j =$ L (nút anh em là con trái): $cur \leftarrow \text{SHA256}(\text{hex}(\text{sib}_j) \,\Vert\, \text{hex}(cur))$
• Nếu $\text{dir}_j =$ R (nút anh em là con phải): $cur \leftarrow \text{SHA256}(\text{hex}(cur) \,\Vert\, \text{hex}(\text{sib}_j))$

Sau khi xử lý hết $k$ cặp, so sánh $cur$ với $R$: nếu bằng nhau in MATCH (lá thực sự thuộc cây có gốc $R$), ngược lại in MISMATCH.

Có $T$ trường hợp kiểm tra độc lập; với mỗi trường hợp in ra một dòng kết quả.

Ví dụ

Input:

1
L0
2
R dffe8596427fc50e8f64654a609af134d45552f18bbecef90b31135a9e7acaa0
R 4eeebd7c6fdb7a3f5340e0f678822a5bac4960de3ab4b2129f2eea7d458bf8d1
e2f0294810f8b6dfa366d7711616479fb32bea7133e5f75db677b9f0b3461225

Output:

MATCH