Cây Merkle (Merkle Tree)
Tóm lại: Cây Merkle là một cấu trúc dữ liệu được sử dụng trong khoa học máy tính và mật mã học để xác minh tính toàn vẹn của dữ liệu được lưu trữ hoặc truyền đi.
Cây Merkle là một cấu trúc dữ liệu được sử dụng trong khoa học máy tính và mật mã học để xác minh tính toàn vẹn của dữ liệu được lưu trữ hoặc truyền đi. Cây này kết hợp mã băm của nhiều phần dữ liệu theo từng cặp thành một mã băm duy nhất gọi là gốc Merkle (Merkle root).
Tại sao điều này quan trọng
Các blockchain như Bitcoin lưu gốc Merkle của tất cả giao dịch trong tiêu đề của mỗi khối. Vì mỗi mã băm phụ thuộc vào dữ liệu bên dưới nó, chỉ cần thay đổi một giao dịch cũng làm gốc thay đổi, nhờ đó hành vi can thiệp trái phép rất dễ bị phát hiện. Cây Merkle cũng cho phép một ví nhẹ xác nhận rằng một giao dịch nằm trong một khối bằng một bằng chứng ngắn gồm vài mã băm, thay vì phải tải xuống toàn bộ khối. Một số sàn giao dịch sử dụng cây Merkle trong các báo cáo bằng chứng dự trữ (proof of reserves) để người dùng có thể kiểm tra rằng số dư của mình đã được tính vào.
Ví dụ
Xét bốn giao dịch: A, B, C và D. Mỗi giao dịch được băm. Mã băm của A và B được kết hợp rồi băm lại, mã băm của C và D cũng vậy. Cuối cùng, hai kết quả đó được băm cùng nhau để tạo thành gốc. Để chứng minh C đã được đưa vào, bạn chỉ cần mã băm của D, mã băm kết hợp của A và B, và gốc.