Cây băm Merkle (tên tiếng Anh là hash tree) là một cấu trúc dữ liệu dạng cây, dùng phổ biến trong mật mã học và khoa học máy tính. Mỗi lá của cây chứa mã băm của một khối dữ liệu, còn mỗi nút bên trong chứa mã băm của các nút con. Ý tưởng này được nhà khoa học Ralph Merkle đề xuất và đăng ký bằng bằng sáng chế năm 1979. Ngày nay nó là một phần không thể thiếu trong hàng loạt hệ thống phi tập trung, từ mạng chia sẻ tệp đến blockchain.
Điểm cốt lõi của cây băm Merkle nằm ở cách nó gom mã băm từ dưới lên. Giả sử bạn có tám khối dữ liệu, mỗi khối được băm riêng thành tám mã băm lá. Hai mã băm lá liền nhau được nối lại rồi băm một lần nữa, cho ra bốn mã băm ở tầng kế tiếp. Bốn mã băm đó lại được ghép cặp và băm tiếp, tạo ra hai mã băm tầng trên. Cuối cùng, hai mã băm còn lại được băm chung và cho ra một mã băm duy nhất đặt ở đỉnh cây, gọi là mã băm gốc (root hash). Mỗi tầng băm chỉ mất một phép băm, nên tổng số phép băm chỉ tăng tuyến tính theo số khối dữ liệu, thay vì tăng theo bậc hai như cách băm nối tiếp một chuỗi dài.
Mã băm gốc đóng vai trò như một cam kết (commitment) về toàn bộ tập dữ liệu. Khi bạn tải một tệp từ mạng ngang hàng, bạn chỉ cần nhận mã băm gốc từ một nguồn đáng tin cậy, ví dụ từ người bạn hoặc từ trang web có tiếng tăm. Sau đó bạn có thể tải phần dữ liệu còn thiếu từ bất kỳ nguồn nào, kể cả nguồn không đáng tin, rồi tự kiểm tra tính toàn vẹn. Nếu mã băm tính lại từ dữ liệu nhận về khác với mã băm gốc, bạn biết ngay dữ liệu đã bị sai hoặc bị độc hại, và có thể tìm một nguồn khác để thử lại.
Ưu điểm lớn nhất của cây băm nằm ở việc chứng minh một lá thuộc về cây chỉ tốn số phép băm bằng logarithm của tổng số lá. Với một triệu khối dữ liệu, bạn chỉ cần khoảng hai mươi phép băm để chứng minh một khối bất kỳ nằm trong cây. Người nhận chỉ cần một chuỗi mã băm của các nút anh em nằm trên đường đi từ lá lên gốc là có thể tự tính lại và đối chiếu. So với một danh sách băm phẳng, nơi mỗi mục đều phải băm lại từ đầu, cây băm cho phép kiểm tra từng nhánh độc lập ngay khi nhánh đó tải xong, kể cả khi toàn bộ cây chưa có mặt.
Blockchain là nơi cây băm Merkle thể hiện rõ nhất vai trò. Mỗi khối Bitcoin chứa một mã băm gốc tính từ cây băm của toàn bộ giao dịch trong khối đó. Nhờ đó, một ví điện tử chạy trên điện thoại không cần tải về toàn bộ chuỗi khối. Ví chỉ cần tải những khối chứa giao dịch của chính mình cùng một mã băm gốc là có thể xác nhận giao dịch đó hợp lệ, một kỹ thuật gọi là xác minh thanh toán đơn giản (Simplified Payment Verification). Tương tự, cây băm còn được dùng để phát hiện trạng thái khối, kiểm tra tính toàn vẹn của ảnh chụp màn hình, và làm cơ sở cho nhiều giao thức chứng minh khác.
Ngoài blockchain, cây băm Merkle xuất hiện trong nhiều hệ thống khác. Hệ thống tệp ZFS dùng cây băm để phát hiện và sửa lỗi dữ liệu hư hỏng trên ổ đĩa. Git và Mercurial dùng cùng một nguyên lý để lưu lịch sử phiên bản, dù cấu trúc của chúng là đồ thị có hướng chứ không hẳn là cây thuần. Các cơ sở dữ liệu NoSQL như Cassandra, Riak và DynamoDB dùng cây băm để so sánh nhanh hai bản sao dữ liệu và chỉ truyền phần khác biệt. Giao thức IPFS đặt tên cho tệp theo chính mã băm nội dung, nên mỗi cây băm đại diện cho một tệp.
Có một điểm yếu tinh tế đáng lưu tâm. Vì mã băm gốc không cho biết cây sâu bao nhiêu tầng, kẻ tấn công có thể tạo ra một tập dữ liệu hoàn toàn khác nhưng vẫn cho ra cùng một mã băm gốc. Các hệ thống hiện đại khắc phục điều này bằng cách gắn tiền tố khác nhau khi băm: byte 0x00 cho nút lá và byte 0x01 cho nút bên trong, đúng như khung làm việc Certificate Transparency đang áp dụng. Cách gắn tiền tố như vậy phá vỡ khả năng một nút bên trong có thể bị hiểu nhầm thành một lá.
Tóm lại, cây băm Merkle giải quyết một bài toán tưởng chừng đơn giản: làm sao để chứng minh một phần nhỏ dữ liệu là thuộc về một tập dữ liệu rất lớn mà không phải tải về toàn bộ tập dữ liệu đó. Chính nhờ đặc tính đó mà nó trở thành nền tảng của rất nhiều hệ thống phân tán ngày nay.
Bạn có thể đọc thêm bài Merkle tree trên Wikipedia để có định nghĩa chuẩn bằng tiếng Anh, hoặc bài cây băm Merkle tiếng Việt nếu muốn đọc theo cách diễn đạt trong nước.
