Cây Merkle là một cấu trúc dữ liệu được sử dụng trong các ứng dụng khoa học máy tính. Trong bitcoin và các loại tiền điện tử khác, cây Merkle phục vụ để mã hóa dữ liệu blockchain hiệu quả và an toàn hơn.
Chúng cũng được gọi là "cây băm nhị phân."
Phá vỡ cây Merkle
Trong blockchain của bitcoin, một khối giao dịch được chạy thông qua thuật toán để tạo ra hàm băm, đó là một chuỗi các số và chữ cái có thể được sử dụng để xác minh rằng một bộ dữ liệu nhất định giống với bộ giao dịch ban đầu, nhưng không để có được bộ giao dịch ban đầu. Phần mềm của Bitcoin không chạy toàn bộ khối dữ liệu giao dịch - trung bình tương đương với 10 phút giao dịch - thông qua chức năng băm. Thay vào đó, mỗi giao dịch được băm, sau đó mỗi cặp giao dịch được nối và băm với nhau, và cứ như vậy cho đến khi có một hàm băm cho toàn bộ khối. (Nếu có số lượng giao dịch lẻ, một giao dịch được nhân đôi và hàm băm của nó được nối với chính nó.)
Hình dung, cấu trúc này giống như một cái cây. Trong sơ đồ bên dưới, "T" chỉ định một giao dịch, "H" một hàm băm. Lưu ý rằng hình ảnh được đơn giản hóa cao; một khối trung bình chứa hơn 500 giao dịch, không phải tám.
Các giá trị băm ở hàng dưới cùng được gọi là "lá", các giá trị băm trung gian là "các nhánh" và hàm băm ở trên cùng là "gốc". Rễ Merkle của một khối nhất định được lưu trữ trong tiêu đề: ví dụ: gốc Merkle của khối # 482819 là e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f8. Root được kết hợp với các thông tin khác (phiên bản phần mềm, hàm băm của khối trước, dấu thời gian, mục tiêu độ khó và nonce) và sau đó chạy qua hàm băm để tạo ra hàm băm duy nhất của khối: 000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1bbc. Hàm băm này không thực sự được bao gồm trong khối có liên quan, nhưng là khối tiếp theo; nó khác với gốc Merkle.
Cây Merkle rất hữu ích vì nó cho phép người dùng xác minh một giao dịch cụ thể mà không cần tải xuống toàn bộ blockchain (hơn 130 gigabyte vào cuối tháng 8 năm 2017). Ví dụ: giả sử bạn muốn xác minh rằng giao dịch T D được bao gồm trong khối trong sơ đồ trên. Nếu bạn có hàm băm gốc (H ABCDEFGH), quá trình này giống như một trò chơi của sudoku: bạn truy vấn mạng về H D và nó trả về H C, H AB và H EFGH. Cây Merkle cho phép bạn xác minh rằng mọi thứ được tính bằng ba giá trị băm: đã cho H AB, H C, H EFGH và gốc H ABCDEFGH, H D (hàm băm duy nhất bị thiếu) phải có trong dữ liệu.
Cây Merkle được đặt theo tên của Ralph Merkle, người đã đề xuất chúng trong một bài báo năm 1987 có tiêu đề "Chữ ký số dựa trên chức năng mã hóa thông thường". Merkle cũng phát minh ra băm mật mã.
