Merkle Tree là gì?

April 21, 2019

Merkle Tree (Cây Merkle) là một thành phần cơ bản và là nền tảng cho chức năng của [blockchain] (https://skywirex.com/blockchain-la-gi/). Nó cho phép xác minh hiệu quả và an toàn các cấu trúc dữ liệu lớn trong trường hợp blockchain và các tập dữ liệu có khả năng lớn dần không giới hạn.

Việc triển khai Merkle Tree trong blockchain có nhiều hiệu ứng. Nó cho phép blockchain mở rộng quy mô đồng thời cung cấp kiến trúc dựa trên hàm băm để duy trì tính toàn vẹn dữ liệu và một cách thông thường để xác minh tính toàn vẹn của dữ liệu. Hàm băm mã hóa là công nghệ cơ bản cho phép Merkle Tree hoạt động, vì vậy trước tiên, điều quan trọng là phải hiểu hàm băm mã hóa là gì.

Hàm băm mã hóa

Hàm băm (hash) là bất kỳ hàm nào được sử dụng để ánh xạ dữ liệu có kích thước tùy ý (đầu vào) thành đầu ra có kích thước cố định. Một thuật toán băm được áp dụng cho đầu vào dữ liệu và kết quả đầu ra có độ dài cố định được gọi là hàm băm. Nhiều thuật toán băm được công khai rộng rãi và có thể được lựa chọn dựa trên nhu cầu của bạn.

Kết quả băm từ đầu vào tùy ý không chỉ cố định về chiều dài, nó cũng hoàn toàn duy nhất. Nghĩa là, cho dù bạn có chạy hàm trên cùng một đầu vào bao nhiêu lần thì đầu ra sẽ luôn giống nhau. Ví dụ, nếu bạn có các bộ dữ liệu sau đây làm đầu vào, thì kết quả đầu ra là duy nhất cho mỗi đầu vào. Lưu ý trong các ví dụ thứ hai và thứ ba, mặc dù sự khác biệt của các đầu vào chỉ là một từ, các kết quả đầu ra hoàn toàn khác nhau. Điều này rất quan trọng vì nó cho phép “lưu dấu vân tay” (“fingerprinting”) của dữ liệu.

Merkle Tree & Merkle Root

Câu chuyện về Merkle Tree bắt đầu từ năm 1979 với một thanh niên tên Ralph Merkle. Khi còn học tại trường đại học Stanford, Merkle đã viết một bài báo học thuật có tên là “Chữ ký số được chứng nhận” “A Certified Digital Signature”. Nói cách khác, anh ta đã thiết kế một quy trình xác minh dữ liệu cho phép máy tính thực hiện công việc của mình nhanh hơn nhiều so với trước đây.

Ý tưởng của Merkle, hiện được biết đến với tên Merkle Tree, đã cách mạng hóa thế giới mã hóa bằng cách mở rộng cách thức mà giao thức máy tính mã hóa hoạt động. Trên thực tế, Merkle Tree được nhắc đến nhiều lần trong bài luận năm 2008 của Satoshi Nakamoto để giới thiệu Bitcoin với thế giới. Chúng cũng được sử dụng rộng rãi trong mã Bitcoin.

Vậy, Merkle Tree là gì? Hiểu một cách đơn giản, Merkle Tree là một phương pháp cấu trúc dữ liệu cho phép một khối lượng lớn thông tin được xác minh tính chính xác cực kỳ nhanh chóng và hiệu quả.

Bây giờ ta xem xét nó trên blockchain. Đầu tiên, điều quan trọng cần lưu ý là mỗi giao dịch trên một blockchain có ID giao dịch là duy nhất. Với hầu hết các blockchain, mỗi ID giao dịch là một mã 64 ký tự chiếm 256 bit (32 byte) bộ nhớ.

Các blockchain thường được tạo thành từ hàng trăm nghìn khối, mỗi khối chứa tới vài nghìn giao dịch, bạn có thể tưởng tượng không gian bộ nhớ trở thành vấn đề như thế nào. Do đó, nó tối ưu hóa để sử dụng càng ít dữ liệu càng tốt khi xử lý và xác minh giao dịch. Điều này giảm thiểu thời gian xử lý CPU đồng thời đảm bảo mức độ bảo mật cao nhất.

Đó chính xác là những gì Merkle Tree làm. Một cách đơn giản, Merkle Tree lấy một số lượng lớn ID giao dịch và đưa chúng qua một quy trình toán học dẫn đến một mã 64 ký tự.

Mã này cực kỳ quan trọng vì nó cho phép bất kỳ máy tính nào nhanh chóng xác minh rằng một giao dịch xác định đã diễn ra trên một khối cụ thể một cách hiệu quả nhất có thể. Mã này được gọi là Merkle Root (Rễ Merkle).

Mã duy nhất mà Merkle Tree tạo ra được gọi là Merkle Root. Mỗi khối trong một blockchain có duy nhất chỉ một Merkle Root. Merkle Root là một phần dữ liệu quan trọng vì nó cho phép các máy tính xác minh thông tin với tốc độ và hiệu quả đáng kinh ngạc.

Tìm hiểu sâu hơn một chút để hiểu Merkle Root được tạo ra như thế nào? Bước đầu tiên là tổ chức tất cả các dữ liệu đầu vào.

Merkle Tree, theo thiết kế, luôn nhóm tất cả các đầu vào thành cặp. Nếu có một số lượng đầu vào lẻ, đầu vào cuối cùng được sao chép và sau đó được ghép nối với chính nó. Điều này đúng với tất cả các ID giao dịch được viết trên một khối của blockchain.

Chẳng hạn, giả sử rằng một khối duy nhất chứa tổng số 512 giao dịch. Merkle Tree sẽ bắt đầu bằng cách nhóm 512 ID giao dịch đó thành 256 cặp. Sau đó, 256 cặp ID giao dịch đó sẽ trải qua một quá trình toán học, được gọi là băm hoặc thuật toán băm, sẽ tạo ra 256 mã chữ và số 64 ký tự mới.

Quá trình chính xác tương tự sẽ xảy ra một lần nữa. 256 mã mới đó sẽ được ghép nối và biến thành 128 mã. Quá trình sẽ được lặp lại, cắt giảm một nửa số mã mỗi lần, cho đến khi chỉ còn lại một mã. Mã duy nhất đó là Merkle Root (Merkle Root).

Một ví dụ về Merkle Tree

Để hình dung khái niệm này rõ ràng, chúng ta hãy nhìn vào một ví dụ rất đơn giản về Merkle Tree. Hãy tưởng tượng rằng có 8 giao dịch được thực hiện trên một khối cụ thể với 8 ID khác nhau. Trên thực tế, ID giao dịch dài 64 ký tự (bao gồm số và chữ), nhưng để đơn giản, hãy cho rằng chúng chỉ dài 8 ký tự. Để việc giải thích trở nên đơn giản hơn, ta chỉ sử dụng các số (và bỏ qua các chữ cái).

Vì vậy, trong ví dụ này, tám ID giao dịch của chúng ta sẽ là:

11111111
22222222
33333333
44444444
55555555
66666666
77777777
88888888

Merkle Tree của chúng ta sẽ trông giống như sau:

Bây giờ, giả sử phương pháp để băm ID giao dịch là lấy các chữ số đầu tiên, thứ ba, thứ năm và thứ bảy từ mỗi hai ID được kết hợp, sau đó chỉ cần ghép các số đó lại với nhau để tạo thành một mã mới 8 chữ số.

Tất nhiên, trong thực tế, toán học đằng sau các thuật toán băm phức tạp hơn nhiều so với điều này. Nhưng đối với giải thích đơn giản này, hệ thống cơ bản này là đủ.

Hiệu quả và tốc độ: những lợi ích của Merkle Tree

Giả sử rằng chúng ta muốn xác thực ID giao dịch trong ví dụ hiện tại. Bob nói rằng anh ta đã trả cho Alice một khoản Bitcoin nhất định và nói với chúng ta rằng ID giao dịch là 88888888. Anh ta cũng gửi cho chúng ta 3 băm: 77777777, 55556666 và 11223344. Đó là tất cả thông tin cần được gửi hoặc nhận để xác minh thanh toán của Bob đến Alice.

Ba giá trị băm này, cùng với ID giao dịch được đề cập (Merkle Root của khối cụ thể này) chính là dữ liệu chỉ cần để xác minh thanh toán Bob cho Alice. Đây là dữ liệu ít hơn nhiều so với những gì sẽ được yêu cầu để xác minh toàn bộ Merkle Tree. Do đó, quá trình xác minh nhanh hơn và hiệu quả hơn nhiều đối với mọi người.

Xem xét cách thức hoạt động của nó. Chúng ta đã có khối Merkle Root, vì vậy Bob không cần phải gửi cho chúng ta thông tin đó. Anh ấy gửi cho chúng ta ID giao dịch của anh ấy và 3 băm bổ sung mà chúng ta đã liệt kê ở trên. Anh ta cũng gửi một chút thông tin về thứ tự và vị trí để sử dụng băm. Bây giờ, tất cả những gì chúng ta phải làm là chạy thuật toán băm trên tập dữ liệu mà Bob cung cấp.

Chúng ta bắt đầu bằng cách băm mã đầu tiên 77777777 với ID giao dịch 88888888, cho chúng ta kết quả 77778888. Bob đã không gửi cho chúng ta mã này (77778888) nhưng không cần thiết bởi vì chúng ta sử dụng thuật toán băm giống như anh ấy. Do đó, chúng ta nhận được kết quả chính xác như nhau.

Sau đó, chúng ta lấy mã thứ hai mà Bob đã gửi cho chúng ta, 55556666 và băm nó với mã mới 77778888 mà chúng ta vừa nhận được. Điều này, tất nhiên, tạo ra số 55667788.

Cuối cùng, chúng ta băm mã thứ ba mà Bob đã cung cấp cho chúng ta, 11223344, với mã mới khác mà chúng ta đã nhận được, 55667788, và chúng ta kết thúc với Merkle Root chính xác: 12345678.

Lưu ý rằng chúng ta chỉ cần 3 mã từ Bob và chỉ phải chạy thuật toán băm ba lần để thấy rằng giao dịch Bob là hợp lệ. Điều đó có nghĩa là máy tính của chúng ta đã thực hiện chưa đến một nửa công việc được yêu cầu để xác minh toàn bộ Merkle Tree. Sơ đồ Merkle Tree ban đầu có 15 số và thuật toán băm cần được chạy 7 lần. Nhưng hơn một nửa số cây đó không cần thiết để xác minh giao dịch của Bob!

Quy trình này đủ để xác minh rằng trên thực tế, Bob đã trả cho Alice số tiền Bitcoin nhất định vì chúng ta đã lấy được các số mà khi được băm cùng với các mã khác Bob đã gửi cho chúng ta, đã tạo ra cùng một Merkle Root mà chúng ta đã biết là đúng khối đặc biệt này.

Bob có thể giả mạo một giao dịch vì điều đó sẽ yêu cầu tìm ID giao dịch giả và một bộ mã giả bổ sung, khi được đưa vào chức năng băm, sẽ tạo ra Merkle Root thực sự. Cơ hội của việc này xảy ra rất nhỏ đến mức chúng ta có thể tự tin nói rằng điều đó là không thể.

Trong ví dụ đơn giản này, sự tiết kiệm sức mạnh tính toán có vẻ không đáng kể. Tuy nhiên, khi bạn xem xét các khối trong một blockchain có thể chứa vài nghìn giao dịch, thật dễ dàng để thấy Merkle Tree tăng hiệu quả đáng kể như thế nào.

Nói tóm lại, đó là lợi ích chính của Merkle Tree. Nó cho phép các máy tính xác minh thông tin cực kỳ hiệu quả với dữ liệu ít hơn nhiều so với những gì được yêu cầu nếu không có Merkle Tree.

Theo:

[komodoplatform.com] (https://komodoplatform.com/whats-merkle-tree/) | backup
[blockonomi.com] (https://blockonomi.com/merkle-tree/) | backup