Cây băm Merkle là gì? Cách Bitcoin xác thực dữ liệu bằng hàm băm
Cây băm Merkle (Merkle tree) là cấu trúc dữ liệu cho phép kiểm tra toàn vẹn của một tập dữ liệu lớn chỉ bằng cách so sánh một giá trị băm duy nhất. Mỗi nút lá mang hash của một khối dữ liệu, còn mỗi nút nội bộ mang hash của các nút con. Hash ở đỉnh cây gọi là Merkle root, đóng vai trò như một lời cam kết (commitment) gói trọn toàn bộ dữ liệu bên dưới.
Khái niệm này do Ralph Merkle phát minh năm 1979 và được ứng dụng rộng rãi: Bitcoin, Ethereum, IPFS, BitTorrent, Git, ZFS, hệ thống Certificate Transparency và nhiều cơ sở dữ liệu NoSQL.
Cách xây dựng cây băm Merkle
Quy trình xây dựng cây băm Merkle nhị phân gồm bốn bước lặp:
- Tính hash của từng khối dữ liệu để tạo ra hàng lá. Trong Bitcoin, mỗi giao dịch đã có sẵn txid là kết quả băm của nó.
- Ghép cặp hai hash liên tiếp, nối chuỗi rồi băm lại, tạo thành tầng kế tiếp.
- Nếu số hash ở một tầng là số lẻ, hash cuối cùng được băm với chính nó để đủ cặp.
- Lặp lại cho tới khi chỉ còn đúng một hash duy nhất: Merkle root.
Toàn bộ phép tính chỉ là hàm băm mật mã như SHA-256, không cần lưu trữ cả cây. Chính vì thế Merkle tree là cấu trúc logic, không phải cấu trúc vật lý đòi hỏi bộ nhớ riêng.
Vì sao cây băm nhanh hơn danh sách băm
Đây là khác biệt cốt lõi. Với một danh sách băm (hash list), muốn chứng minh một phần tử nằm trong danh sách, bạn phải băm lại toàn bộ danh sách — số phép băm tỉ lệ với số phần tử. Với cây băm, chỉ cần đi ngược lên từ lá lên root, mỗi bước băm một cặp, nên số phép băm chỉ tỉ lệ với logarit của số lá.
Nói cách khác, với một triệu giao dịch, chứng minh một giao dịch cụ thể chỉ cần khoảng 20 phép băm thay vì hơn một triệu. Đây chính là lý do cây băm trở thành nền tảng của mọi giao thức xác thực dữ liệu phân tán.
Merkle root trong Bitcoin
Mỗi block header của Bitcoin chứa trường Tx_root chính là Merkle root của toàn bộ giao dịch trong block đó. Theo Bitcoin Developer Guide, các txid được ghép cặp rồi băm lặp lên cho đến khi còn một giá trị duy nhất. Nếu số giao dịch là số lẻ, txid cuối cùng được băm với bản sao của chính nó.
Ý nghĩa bảo mật nằm ở chỗ khác. Merkle root nằm trong block header, mà block header lại là thứ thợ đào phải băm để tạo bằng chứng công việc. Chỉ cần thay đổi một byte trong bất kỳ giao dịch nào, Merkle root thay đổi theo, kéo theo block header thay đổi, và bằng chứng công việc cũng không còn hợp lệ. Chính Bitcoin Developer Guide cũng lưu ý rằng Merkle tree không phải là cơ chế chống va chạm hoàn hảo vì cách dựng cây lệch có thể tạo ra trùng lặp với các txid giống nhau.
Simplified Payment Verification: ứng dụng quan trọng nhất
Ví điện tử chạy trên điện thoại không tải được cả chuỗi khối Bitcoin, vốn có thể vượt nhiều trăm gigabyte. Cơ chế Simplified Payment Verification (SPV) giải quyết bằng chính Merkle tree: ví chỉ tải block header và một đường đi hẹp (merkle path) chứng minh giao dịch của mình nằm trong block đó.
Quy trình kiểm tra gồm ba bước:
- Lấy Merkle root từ block header mà node đầy đủ cung cấp.
- Lấy chuỗi hash trung gian từ giao dịch mục tiêu đến gần root.
- Tự tính lại bằng cách băm từ lá lên, rồi so sánh kết quả với root trong header.
Con số nói lên tất cả. Nếu block chứa năm giao dịch, mỗi giao dịch ở kích thước tối đa, tải toàn bộ block cần hơn 500.000 byte. Nhưng để chứng minh giao dịch D có trong block, ví chỉ cần ba hash trung gian (C, AB và EEEE) cùng block header — khoảng 140 byte. Bằng chứng là không cần tin tưởng node cung cấp dữ liệu, vì làm giả block header hoặc các hash trung gian là tốn kém hơn nhiều so với tự tính lại.
Các biến thể và nơi ứng dụng
Cây băm không bị giới hạn ở dạng nhị phân. Merkle-Patricia trie với số nhánh lớn hơn là cấu trúc Ethereum dùng để lưu trạng thái và chứng minh giao dịch. Git lưu lịch sử bằng đồ thị có hướng không chu trình, một biến thể của cây băm. IPFS định danh nội dung bằng CID tính từ Merkle DAG, nên cùng một tập dữ liệu luôn cho cùng một địa chỉ. ZFS dùng cây băm làm checksum để phát hiện và tự sửa lỗi dữ liệu hỏng trên ổ đĩa.
Lưu ý khi dùng cây băm
Cây băm chỉ bảo vệ tính toàn vẹn, không bảo vệ tính xác thực. Nếu kẻ tấn công kiểm soát được nguồn dữ liệu gốc, họ có thể tạo ra cây băm hoàn toàn hợp lệ cho dữ liệu giả mạo. Vì vậy trong Bitcoin, cây băm luôn đi kèm hằng số khó hơn nhiều: bằng chứng công việc của toàn khối. Ngoài ra, hàm băm phải là hàm mật mã chống va chạm như SHA-256; nếu chỉ cần phát hiện hỏng dữ liệu do vô tình, CRC đơn giản là đủ và nhanh hơn nhiều.
Tóm tắt
Cây băm Merkle biến bài toán xác thực dữ liệu lớn thành một phép so sánh hash. Nhờ cấu trúc nhị phân, số phép băm cần thiết chỉ tăng theo logarit thay vì tuyến tính. Trong Bitcoin, Merkle root gắn toàn bộ giao dịch vào block header, cho phép ví nhẹ xác thực thanh toán với vài trăm byte dữ liệu. Đây là ví dụ kinh điển cho sức mạnh của cấu trúc dữ liệu đơn giản trong thiết kế hệ thống phân tán quy mô lớn.
