solution

Một Merkle Proof (đường dẫn xác minh) cho phép chứng minh một giao dịch (lá) thuộc về một Merkle root đã biết mà không cần biết toàn bộ cây. Proof gồm một dãy các hash anh em (sibling) kèm vị trí tương đối (trái L hoặc phải R so với nút hiện tại), đi từ lá lên gốc.

Xuất phát từ current = leaf (mã băm giao dịch cần xác minh). Với mỗi bước $(sibling, pos)$ theo thứ tự cho trước:

• Nếu $pos = L$: current $\leftarrow$ SHA256(bytes(sibling) $\parallel$ bytes(current))
• Nếu $pos = R$: current $\leftarrow$ SHA256(bytes(current) $\parallel$ bytes(sibling))

trong đó bytes($\cdot$) là chuyển chuỗi hex về dạng byte thô trước khi nối và băm. Sau khi xử lý hết các bước, so sánh current với root đã cho: nếu trùng khớp thì proof hợp lệ, ngược lại không hợp lệ.

Ví dụ: với cây Merkle 4 lá, để chứng minh lá thứ 3 (chỉ số 2, hash $L_2$) thuộc cây, proof gồm 2 bước: $(L_3, R)$ rồi $(N_{01}, L)$ — với $N_{01}$ là nút cha của $L_0, L_1$. Nếu kết quả cuối trùng với root đã cho, in VALID.