Tìm hiểu về cây Merkle (Merkle Tree)

Cây Merkle (Merkle Tree) là gì?

Cây Merkle, còn được gọi là cây băm nhị phân, là một cấu trúc dữ liệu quan trọng trong khoa học máy tính. Trong các loại tiền mã hóa như Bitcoin, cây Merkle được sử dụng để mã hóa dữ liệu blockchain một cách hiệu quả và bảo mật.

Phương thức hoạt động của cây Merkle (Merkle Tree)

Trong blockchain của bitcoin, một khối giao dịch được chạy qua thuật toán để tạo ra một hàm băm, đó là một chuỗi ký tự số và chữ cái được sử dụng để xác minh tính toàn vẹn của dữ liệu giao dịch. Thay vì chạy toàn bộ khối giao dịch thông qua chức năng băm cùng một lúc, phần mềm Bitcoin chạy từng giao dịch riêng lẻ và sau đó nối chúng lại và băm thành một khối hoàn chỉnh. Quá trình này được lặp lại cho đến khi tạo ra một hàm băm cho toàn bộ khối. Trong trường hợp có số lượng giao dịch lẻ, một giao dịch sẽ được nhân đôi và hàm băm của nó sẽ được nối với chính nó.

Hàm băm

Hãy tưởng tượng rằng cấu trúc này giống như một cây. Trong sơ đồ dưới đây, “T” đại diện cho một giao dịch, “H” đại diện cho một hàm băm. Hãy lưu ý rằng hình ảnh được đơn giản hóa để hiển thị; một khối trung bình chứa hơn 500 giao dịch, không chỉ 8.

Các giá trị băm ở hàng cuối cùng được gọi là “lá”, các giá trị băm trung gian là “nhánh”, và hàm băm ở trên cùng được gọi là “gốc”. Gốc 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 số 482819 là

e045b18e7a3d708d686717b4f44db2099aabcad9bebf968de5f7271b458f8.

Gốc này đượ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), sau đó chạy qua hàm băm để tạo ra một hàm băm duy nhất của khối:

000000000000000000bfc767ef8bf28c42cbd4bdbafd9aa1bbc.

Hàm băm này thực tế không được bao gồm trong khối liên quan, mà thay vào đó nó được sử dụng trong khối tiếp theo, và 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 (khoảng 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 TD được bao gồm trong khối trong sơ đồ trên. Nếu bạn có gốc hàm băm (HABCDEFGH), quá trình này tương tự như một trò chơi sudoku: bạn truy vấn mạng với HC, HAB và HEFGH, và mạng sẽ trả về cho bạn. Cây Merkle cho phép bạn xác minh rằng ba giá trị băm này – HAB, HC, HEFGH – cùng với gốc HABCDEFGH (hàm băm duy nhất bị thiếu) phải có trong dữ liệu để xác minh TD giao dịch.

Ethereum

Ethereum sử dụng ba root Merkle khác nhau trong mỗi khối:

– Root đầu tiên là root của các giao dịch trong khối.
– Root thứ hai đại diện cho nhà nước.
– Root thứ ba dành cho biên lai giao dịch.

Ethereum sử dụng một loại cây băm đặc biệt gọi là “Merkle Patricia Tree”.

Cây Merkle là một công cụ mạnh mẽ và không thể thiếu cho các thợ mỏ và người dùng trên blockchain. Chúng có sức mạnh phi thường và là trung tâm của một số mạng ngang hàng như BitTorrent, Git, Bitcoin và Ethereum.

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 đề “Digital Signatures Based on the Standardized Hash Function”. Merkle cũng là người phát minh ra hàm băm mật mã.