KHÁM PHÁ / THUẬT NGỮ · Blockchain cơ bản

Cây Merkle

Merkle tree

Cấu trúc dữ liệu gộp nhiều mã băm thành một mã gốc duy nhất bằng cách ghép và băm từng cặp, lặp lại tới khi chỉ còn một mã. Đổi bất kỳ dữ liệu nào, mã gốc cũng đổi.

Theo NIST, cây Merkle là cấu trúc dữ liệu trong đó dữ liệu được băm và ghép lại cho tới khi chỉ còn một mã băm gốc (root).

Cách hình dung: giống một giải đấu loại trực tiếp. Vòng đầu là mã băm của từng tài liệu hoặc giao dịch; mỗi vòng, hai mã băm được ghép và băm thành một nên số lượng giảm một nửa; cuối cùng còn một mã gốc.

Hai tính chất quan trọng. Một: đổi dù một ký tự ở bất kỳ dữ liệu nào, mã gốc cũng thay đổi. Hai: muốn chứng minh một dữ liệu nằm trong cây, chỉ cần các mã băm trên đường từ dữ liệu đó lên gốc (nhánh Merkle): với một triệu dữ liệu là khoảng 20 mã băm, không phải một triệu.

Bitcoin dùng cây Merkle để gộp các giao dịch trong mỗi khối: chỉ mã gốc nằm trong tiêu đề khối, nhờ đó ví nhẹ kiểm tra được một giao dịch bằng nhánh Merkle mà không tải toàn bộ khối. Dịch vụ dấu thời gian OpenTimestamps cũng dùng cây Merkle để neo rất nhiều tài liệu vào một giao dịch Bitcoin.

Nguồn tham khảo

Xuất hiện trong bài

Thuật ngữ liên quan

Định nghĩa do AI biên soạn từ các nguồn trên, tác giả duyệt. Đây là thông tin tham khảo, không phải tư vấn pháp lý hay đầu tư. Thấy chỗ chưa đúng? Hãy góp ý để tác giả sửa.