Cây Merkle và gốc Merkle

Cây Merkle là gì?

Khái niệm về cây Merkle được đặt ra vào đầu những năm 80 bởi Ralph Merkle – một nhà khoa học máy tính nổi tiếng với công trình nghiên cứu về công nghệ mật mã khóa công khai. Cây Merkle là một cấu trúc hiệu quả dùng để xác minh tính toàn vẹn của dữ liệu trong tập hợp. Cấu trúc này đặc biệt thú vị trong bối cảnh mạng lưới P2P, khi những người tham gia cần chia sẻ và xác thực thông tin một cách độc lập. Hàm băm là gốc của cấu trúc cây Merkle, vì vậy bạn nên xem bài Hashing (băm) là gì? trước khi tiếp tục.

Cách cây Merkle hoạt động

Giả sử bạn muốn tải về một tệp lớn. Khi dùng phần mềm mã nguồn mở, bạn thường muốn kiểm tra xem hàm băm của tệp đã tải về có khớp với mã mà nhà phát triển công khai hay không. Nếu đúng, bạn biết được rằng tệp trên máy tính của mình hoàn toàn giống với tệp của nhà phát triển.

Nếu các hàm băm không khớp tức là đã xảy ra vấn đề. Bạn đã tải về một tệp độc hại giả dạng phần mềm hoặc tải phần mềm không đúng cách nên phần mềm sẽ không thể hoạt động. Nếu trường hợp thứ hai xảy ra, thật chẳng vui chút nào khi bạn phải chờ một lúc để tệp tải về. Bây giờ, bạn cần thực hiện lại quá trình và hy vọng không xảy ra lỗi nữa. Bạn nghĩ rằng giá như có một cách dễ dàng hơn để thực hiện việc này. Thật may mắn, đây là lúc cần đến cây Merkle. Khi dùng một trong những cấu trúc cây này, bạn sẽ chia nhỏ tệp của mình thành nhiều phần. Nếu sử dụng với tệp 50GB, bạn có thể chia thành một trăm phần, sao cho mỗi phần có kích thước 0,5GB. Sau đó, hệ thống sẽ tải về từng phần một. Về cơ bản, đây quá trình thực hiện khi bạn chia nhỏ tệp của mình. Trong trường hợp này, nguồn của bạn sẽ cung cấp một hàm băm được gọi là gốc Merkle. Hàm băm đơn này là đại diện cho mọi phần dữ liệu tạo nên tệp của bạn. Nhưng nhờ gốc Merkle, việc xác minh dữ liệu dễ dàng hơn nhiều. Để bạn dễ hiểu hơn, chúng tôi sẽ lấy một ví dụ sử dụng tệp 8GB được chia thành tám phần. Đặt tên các mảnh này từ A đến H. Mỗi mảnh sau đó được chuyển qua một hàm băm và chúng tôi có tám hàm băm.

Chúng tôi chuyển mỗi mảnh trong số tám mảnh thông qua một hàm băm để lấy các hàm băm của chúng.

Chúng tôi chuyển mỗi mảnh trong số tám mảnh thông qua một hàm băm để lấy các hàm băm của chúng.

Tốt rồi, giờ đây những việc chúng tôi thực hiện sẽ dễ hiểu hơn một chút. Chúng tôi có hàm băm của tất cả các mảnh nên nếu một mảnh bị lỗi, chúng tôi sẽ phát hiện bằng cách so sánh mảnh đó với hàm băm của nguồn, phải không? Có thể, nhưng việc này cũng rất kém hiệu quả. Nếu tệp có hàng nghìn mảnh, liệu bạn có thực sự sẽ “băm” tất cả và so sánh tỉ mỉ kết quả không? Không. Thay vào đó, chúng tôi sẽ lấy từng cặp hàm băm, kết hợp lại, sau đó băm chúng với nhau. Vì thế chúng tôi băm hA + hBhC + hDhE + hF và  hG + hH. Chúng tôi kết thúc với bốn hàm băm. Sau đó, chúng tôi thực hiện một vòng băm khác với những hàm băm này và kết thúc khi còn lại hai hàm băm. Cuối cùng, chúng tôi băm hai hàm băm còn lại để thu được đến hàm băm chính của mình –  gốc Merkle (hoặc hàm băm gốc).

Cấu trúc này giống với một cái cây lộn ngược. Ở hàng dưới cùng, chúng tôi có lá, được kết hợp để tạo ra các node và cuối cùng là gốc.

Cấu trúc này giống với một cái cây lộn ngược. Ở hàng dưới cùng, chúng tôi có lá, được kết hợp để tạo ra các node và cuối cùng là gốc.

Bây giờ chúng tôi có gốc Merkle đại diện cho tệp mình đã tải về. Chúng tôi có thể so sánh hàm băm gốc này với hàm băm do nguồn cung cấp. Nếu hai hàm này khớp nhau thì tuyệt vời! Nhưng nếu các hàm băm khác nhau, thì chắc chắn rằng dữ liệu đã bị sửa đổi. Nói cách khác, một hoặc nhiều mảnh đã tạo ra hàm băm khác. Vì vậy, bất kỳ sửa đổi nhỏ nào trong dữ liệu cũng sẽ mang đến cho chúng tôi một gốc Merkle hoàn toàn khác. May mắn là có một cách thức hữu ích để chúng tôi kiểm tra được mảnh nào bị lỗi. Trong tình huống của này, giả sử mảnh hE bị lỗi. Bạn sẽ bắt đầu bằng cách hỏi một người dùng khác về hai hàm băm tạo nên gốc Merkle là (hABCD và hEFGH). Giá trị hABCD của bạn sẽ khớp với giá trị của nguồn vì sẽ không có sai sót trong nhánh cây đó. Nhưng hEFGH thì không khớp nên bạn biết mình cần kiểm tra hàm này. Sau đó, bạn yêu cầu kiểm tra hai hàm băm hEF và hGH, rồi so sánh chúng với các hàm băm của bạn. hGH sẽ ổn nên bạn biết rằng hEF là nguyên nhân gây ra lỗi. Cuối cùng, bạn so sánh các hàm băm của hE và hF. Bây giờ bạn đã biết rằng hE không chính xác nên bạn có thể tải lại mảnh này.

Tóm lại, một cây Merkle được tạo ra bằng cách chia dữ liệu thành nhiều phần, sau đó được băm nhiều lần để tạo thành gốc Merkle. Tiếp đó, bạn có thể xác minh một cách hiệu quả xem có vấn đề gì xảy ra với một phần dữ liệu hay không. Như chúng ta sẽ thấy trong phần tiếp theo, còn có cả những ứng dụng thú vị khác.

Tại sao dùng gốc Merkle trong Bitcoin?

Bạn có thể dùng cây Merkle trong nhiều trường hợp nhưng trong bài viết này, chúng tôi sẽ tập trung vào tầm quan trọng của cấu trúc này đối với các blockchain. Cây Merkle rất quan trọng đối với Bitcoin và nhiều loại tiền mã hóa khác. Cấu trúc này là một phần không thể thiếu của mọi block và mọi người có thể tìm thấy các cấu trúc cây này trong tiêu đề khối. Để lấy “lá” dữ liệu cho cây của mình, chúng tôi sử dụng hàm băm giao dịch (TXID) của mọi giao dịch có trong block. 

Gốc Merkle dùng để phục vụ cho một vài mục đích trong trường hợp này. Hãy xem xét các ứng dụng của chúng trong việc đào tiền mã hóa và xác minh giao dịch.

Đào tiền

Một block Bitcoin được cấu thành từ hai phần. Phần đầu tiên là tiêu đề khối, một phân đoạn có kích thước cố định chứa siêu dữ liệu cho block. Phần thứ hai là danh sách các giao dịch có nhiều kích thước nhưng thường lớn hơn nhiều so với tiêu đề. Thợ đào phải liên tục băm dữ liệu để tạo ra kết quả khớp với các điều kiện nhất định, từ đó đào ra block hợp lệ. Trước khi tìm ra một block, họ phải nỗ lực thử hàng nghìn tỷ lần. Với mỗi lần thử, họ thay đổi một số ngẫu nhiên trong tiêu đề khối (nonce) để tạo ra một kết quả khác. Tuy nhiên, vẫn giữ nguyên phần lớn của block. Có thể có hàng nghìn giao dịch và bạn vẫn cần băm chúng mỗi lần giao dịch.

Một gốc Merkle giúp đơn giản hóa quy trình đáng kể. Khi bắt đầu đào, bạn sẽ sắp xếp tất cả các giao dịch muốn thêm vào và xây dựng một cây Merkle. Bạn đặt hàm băm gốc kết quả (32 byte) vào tiêu đề khối. Sau đó, khi đang đào, bạn chỉ cần băm tiêu đề khối, thay vì toàn bộ block.

Phương pháp này thực sự hiệu quả vì có thể chống giả mạo. Bạn tóm tắt hiệu quả tất cả các giao dịch của block trong một định dạng nhỏ gọn. Bạn không thể tìm tiêu đề khối hợp lệ, rồi thay đổi danh sách giao dịch, vì điều đó sẽ làm thay đổi gốc Merkle. Khi block được gửi đến các node khác, chúng sẽ tính gốc từ danh sách giao dịch. Nếu block này không khớp với một trong những tiêu đề thì sẽ bị từ chối.

Xác minh

Gốc Merkle có một tính chất thú vị khác mà chúng ta có thể tận dụng. Điều này liên quan đến các light client (các node không chứa bản sao đầy đủ của blockchain). Nếu đang chạy một node trên thiết bị có tài nguyên hạn chế, bạn sẽ không muốn tải về và băm toàn bộ giao dịch của block. Thay vào đó, những gì bạn có thể làm chỉ là yêu cầu cung cấp bằng chứng Merkle – bằng chứng do node đầy đủ cung cấp để chứng minh rằng giao dịch của bạn nằm trong một block cụ thể. Quy trình này thường được gọi là Xác minh thanh toán đơn giản hóa hoặc SPV và được Satoshi Nakamoto trình bày chi tiết trong sách trắng về Bitcoin.

Để kiểm tra hD, chúng tôi chỉ cần các hàm băm có màu đỏ.

Để kiểm tra hD, chúng tôi chỉ cần các hàm băm có màu đỏ. Hãy xem xét tình huống mà chúng tôi muốn biết thông tin về giao dịch có TXID là hD. Nếu hC được cung cấp, chúng tôi có thể tính hCD. Khi đó, ta cần hAB để tính hABCD. Cuối cùng, với hEFGH, chúng tôi có thể kiểm tra xem gốc Merkle được tính ra có khớp với gốc từ tiêu đề khối hay không. Nếu khớp, đó chính là bằng chứng cho thấy giao dịch đã được thêm vào block – thật khó để tạo ra cùng một hàm băm với nhiều dữ liệu.

Trong ví dụ trên, chúng ta chỉ phải băm ba lần. Nếu không có bằng chứng Merkle, chúng ta sẽ cần thực hiện việc này bảy lần. Vì các block ngày nay chứa hàng nghìn giao dịch, việc sử dụng bằng chứng Merkle giúp chúng ta tiết kiệm rất nhiều thời gian và tài nguyên máy tính.

Tổng kết

Cây Merkle đã tự chứng minh tính hữu ích trong một loạt các ứng dụng khoa học máy tính – như đã thấy, chúng mang lại nhiều giá trị trong các blockchain. Trong các hệ thống phân tán, cây Merkle cho phép dễ dàng xác minh thông tin mà không làm ngập mạng lưới với dữ liệu không cần thiết. Nếu không có cây Merkle (và gốc Merkle), Bitcoin và các block của các loại tiền mã hóa khác khó mà nhỏ gọn như ngày nay. Đồng thời, khi các light client thiếu khía cạnh quyền riêng tư và bảo mật, bằng chứng Merkle sẽ cho phép người dùng kiểm tra xem các giao dịch của họ đã được đưa vào một block với chi phí tối thiểu hay chưa.

Bài viết mới
Tin nổi bật