Cây Merkle

Cây Merkle là một cây nhị phân có thứ tự được xây dựng từ một dãy các đối tượng dữ liệu (d1, d2,...,dn) sử dụng hàm băm h. Các "lá" của cây là các giá trị băm h(di) đối với 1 ≤ i ≤ n. Các nốt là h(l||r), ở đó các cây con left (l) và right (r) được nối lại với nhau bằng (||).

Cây Merkle có thể được sử dụng để kiểm tra xem một đối tượng dữ liệu có phải là một thành viên ở một vị trí đúng đắn trong mô hình cây hay không. Gốc của cây đóng vai trò là một bản băm đối với toàn bộ cây. Việc kiểm tra được thực hiện bằng cách xây dựng lại đường đi từ lá đến gốc cây, sử dụng đường xác thực bao gồm các nhánh đồng hạng của các nốt trên đường.

Cây Merkle được ứng dụng vào công nghệ blockchain của Bitcoin để xác minh và lưu trữ dữ liệu giao dịch.