Cây Merkle là gì?
Khái niệm cây Merkle được đề xuất 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ề mật mã khóa công khai.
Cây Merkle là cấu trúc được sử dụng để xác minh hiệu quả tính toàn vẹn của dữ liệu trong một tập hợp. Chúng đặc biệt thú vị trong bối cảnh mạng ngang hàng, nơi 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à cốt lõi của cấu trúc cây Merkle, vì vậy chúng tôi khuyên bạn nên xem Hashing là gì? trước khi tiếp tục.
Cây Merkle hoạt động như thế nào?
Giả sử bạn muốn tải xuống một tệp lớn. Với phần mềm nguồn mở, bạn thường muốn kiểm tra xem hàm băm của tệp bạn đã tải xuống có khớp với mã được nhà phát triển công khai hay không. Nếu đúng như vậy, bạn biết rằng tệp bạn có trên máy tính của bạn giống hệt với tệp của họ.
Nếu giá trị băm không khớp thì bạn có vấn đề. Bạn đã tải xuống một tệp độc hại giả mạo phần mềm hoặc tệp đó không được tải xuống đúng cách và do đó sẽ không hoạt động. Nếu trường hợp sau xảy ra, bạn có thể sẽ không vui nếu phải đợi một thời gian để tải xuống tệp. Bây giờ, bạn cần khởi động lại quá trình và hy vọng rằng nó không bị hỏng nữa.
Bạn nghĩ giá như có một cách dễ dàng hơn để giải quyết vấn đề này. May mắn thay, đó là lúc cây Merkle phát huy tác dụng. Với một trong những cây này, bạn sẽ chia tệp của mình thành nhiều phần. Nếu đó là tệp 50 GB, bạn có thể chia nó thành một trăm phần, sao cho mỗi phần có kích thước 0,5 GB. Sau đó, nó sẽ được tải xuống từng phần một. Đây thực chất là những gì bạn làm khi tải torrent.
Trong trường hợp này, nguồn của bạn sẽ cung cấp cho bạn hàm băm được gọi là gốc Merkle. Hàm băm đơn này đại diện cho mọi đoạn dữ liệu tạo nên tệp của bạn. Nhưng root Merkle giúp việc xác minh dữ liệu dễ dàng hơn nhiều.
Để đơn giản, hãy lấy một ví dụ trong đó chúng tôi sử dụng tệp 8GB được chia thành tám phần. Gọi các đoạn khác nhau là A đến H. Sau đó, mỗi đoạn được chuyển qua một hàm băm, cho chúng ta tám hàm băm khác nhau.
Chúng tôi chuyển từng đoạn trong số tám đoạn của mình thông qua hàm băm để lấy giá trị băm của chúng.
Được rồi, vậy là chúng ta đã có thứ gì đó có ý nghĩa hơn một chút. Chúng tôi có hàm băm của tất cả các mảnh, vì vậy nếu một mảnh bị lỗi, chúng tôi sẽ biết bằng cách so sánh nó với mảnh của nguồn, phải không? Có thể, nhưng điều đó cũng cực kỳ kém hiệu quả. Nếu tệp của bạn có hàng nghìn mảnh, bạn có thực sự định băm tất cả chúng và so sánh kết quả một cách tỉ mỉ không?
Không. Thay vào đó, chúng ta sẽ lấy từng cặp giá trị băm, kết hợp chúng rồi băm chúng lại với nhau. Vì vậy, chúng tôi băm ha + hB, hC + hD, hE + hF và hG + hH. Chúng tôi kết thúc với bốn giá trị băm. Sau đó, chúng tôi thực hiện một vòng băm khác với những thứ này để có được hai. Cuối cùng, chúng tôi băm hai phần còn lại để có được hàm băm chính – gốc Merkle (hoặc hàm băm gốc).
Cấu trúc trông giống như một cái cây lộn ngược. Ở hàng dưới cùng, chúng ta có các lá, được kết hợp để tạo ra các nút và cuối cùng là gốc.
Bây giờ chúng ta có root Merkle đại diện cho tệp chúng ta đã tải xuống. Chúng ta có thể so sánh hàm băm gốc này với hàm băm được cung cấp bởi nguồn. Nếu nó phù hợp, hoàn hảo! Nhưng nếu các giá trị băm khác nhau, chúng ta có thể chắc chắn rằng dữ liệu đã được sửa đổi. Nói cách khác, một hoặc nhiều đoạn đã tạo ra một hàm băm khác. Vì vậy, bất kỳ sửa đổi nhỏ nào về dữ liệu sẽ mang lại cho chúng ta một gốc Merkle hoàn toàn khác.
May mắn thay, có một cách hữu ích để chúng ta kiểm tra xem đoạn nào bị lỗi. Trong trường hợp của chúng tôi, giả sử đó là hE. Bạn sẽ bắt đầu bằng cách hỏi một người ngang hàng về hai hàm băm tạo ra gốc Merkle (hABCD và hEFGH). Giá trị hABCD của bạn phải khớp với giá trị của chúng vì không có lỗi nào trong cây con đó. Nhưng hEFGH thì không, vì vậy bạn nên đăng ký ở đó. Sau đó, bạn yêu cầu hEF và hGH và so sánh chúng với của bạn. hGH trông sẽ ổn thôi, vì vậy bạn biết rằng hEF là thủ phạm của chúng ta. Cuối cùng, bạn so sánh giá trị 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 đoạn đó.
Tóm lại, cây Merkle được tạo 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. Sau đó, 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ó những ứng dụng thú vị khác.
Bạn đang muốn bắt đầu với tiền điện tử? Mua Bitcoin trên Binance!
Tại sao rễ Merkle được sử dụng trong Bitcoin?
Có một số trường hợp sử dụng cây Merkle, nhưng ở đây chúng ta sẽ tập trung vào tầm quan trọng của chúng trong chuỗi khối. Cây Merkle rất cần thiết trong Bitcoin và nhiều loại tiền điện tử khác. Chúng là thành phần không thể thiếu của mọi khối, nơi chúng có thể được tìm thấy trong tiêu đề khối. Để lấy các lá cho cây, chúng tôi sử dụng hàm băm giao dịch (TXID) của mọi giao dịch có trong khối.
Root Merkle phục vụ một số mục đích trong trường hợp này. Chúng ta hãy xem các ứng dụng của họ trong việc khai thác tiền điện tử và xác minh giao dịch.
Khai thác mỏ
Một khối Bitcoin được tạo thành từ hai phần. Phần đầu tiên là tiêu đề khối, một đoạn có kích thước cố định chứa siêu dữ liệu cho khối. Phần thứ hai là danh sách các giao dịch có kích thước thay đổi nhưng có xu hướng lớn hơn nhiều so với tiêu đề.
Người khai thác cần băm dữ liệu nhiều lần để tạo ra đầu ra phù hợp với các điều kiện nhất định nhằm khai thác một khối hợp lệ. Họ có thể thực hiện hàng nghìn tỷ lần thử trước khi tìm được. Với mỗi lần thử, chúng thay đổi một số ngẫu nhiên trong tiêu đề khối (số nonce) để tạo ra một đầu ra khác. Nhưng phần lớn khối vẫn giữ nguyên. Có thể có hàng nghìn giao dịch và bạn vẫn cần phải băm chúng mỗi lần.
Root Merkle hợp lý hóa quy trình một cách đáng kể. Khi bắt đầu khai thác, bạn sắp xếp tất cả các giao dịch bạn muốn đưa vào và xây dựng 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 khai thác, bạn chỉ cần băm tiêu đề khối thay vì toàn bộ khối.
Điều này hoạt động vì nó chống giả mạo. Bạn tóm tắt một cách hiệu quả tất cả các giao dịch của khối ở định dạng nhỏ gọn. Bạn không thể tìm thấy tiêu đề khối hợp lệ và sau đó thay đổi danh sách giao dịch vì điều đó sẽ thay đổi gốc Merkle. Khi khối được gửi đến các nút khác, họ sẽ tính toán gốc từ danh sách giao dịch. Nếu nó không khớp với cái trong tiêu đề, họ sẽ từ chối khối.
xác minh
Có một đặc tính thú vị khác của rễ Merkle mà chúng ta có thể tận dụng. Điều này liên quan đến các máy khách nhẹ (các nút không chứa bản sao đầy đủ của chuỗi khối). Nếu bạn đang chạy một nút trên một thiết bị có tài nguyên hạn chế, bạn sẽ không muốn tải xuống và băm tất cả các giao dịch của khối. Thay vào đó, những gì bạn có thể làm chỉ đơn giản là yêu cầu bằng chứng Merkle – bằng chứng được cung cấp bởi nút đầy đủ để chứng minh rằng giao dịch của bạn nằm trong một khối cụ thể. Điều này thường được gọi là Xác minh thanh toán đơn giản hoặc SPV và được Satoshi Nakamoto trình bày chi tiết trong sách trắng Bitcoin.
Để kiểm tra hD, chúng ta chỉ cần các giá trị băm hiển thị màu đỏ.
Hãy xem xét tình huống mà chúng ta muốn biết thông tin về giao dịch có TXID là hD. Nếu hC được cung cấp cho chúng tôi, chúng tôi có thể tìm ra hCD. Sau đó, chúng ta cần hAB để tính hABCD. Cuối cùng, với hEFGH, chúng ta có thể kiểm tra xem gốc Merkle thu được có khớp với gốc từ tiêu đề khối hay không. Nếu đúng như vậy, đó là bằng chứng cho thấy giao dịch đã được đưa vào khối – gần như không thể tạo cùng một hàm băm với các dữ liệu khác nhau.
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 tôi sẽ phải làm điều đó bảy lần. Vì các khối ngày nay chứa hàng nghìn giao dịch nên 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.
Bớt tư tưởng
Cây Merkle đã chứng tỏ chúng rất hữu ích trong nhiều ứng dụng khoa học máy tính – như chúng ta đã thấy, chúng cực kỳ có giá trị trong chuỗi khối. Trong các hệ thống phân tán, cây Merkle cho phép xác minh thông tin dễ dàng mà không làm tràn ngập mạng với dữ liệu không cần thiết.
Nếu không có cây Merkle (và rễ Merkle), các khối Bitcoin và các loại tiền điện tử khác sẽ không thể nhỏ gọn như ngày nay. Và mặc dù các ứng dụng khách hạng nhẹ còn thiếu các vấn đề về quyền riêng tư và bảo mật, nhưng bằng chứng Merkle cho phép người dùng kiểm tra xem các giao dịch của họ có được đưa vào một khối với chi phí tối thiểu hay không.
