Những điểm chính cần ghi nhớ
Cây Merkle là một cấu trúc dữ liệu mật mã tổ chức dữ liệu thành các cặp hàm băm, kết hợp chúng từ dưới lên cho đến khi một hàm băm duy nhất, được gọi là gốc Merkle, đại diện cho toàn bộ tập dữ liệu.
Các gốc Merkle cho phép các mạng blockchain xác minh xem một giao dịch có được bao gồm trong một khối hay không mà không cần tải xuống toàn bộ khối, bằng cách sử dụng bằng chứng Merkle nhỏ gọn có khả năng mở rộng theo hàm logarit với số lượng giao dịch.
Bitcoin nhúng mã gốc Merkle vào mỗi tiêu đề khối, cho phép các ứng dụng khách nhẹ xác minh giao dịch chỉ bằng cách sử dụng tiêu đề khối thay vì toàn bộ chuỗi khối.
Ethereum sử dụng cấu trúc dữ liệu Merkle Patricia Trie phức tạp hơn để lưu trữ số dư tài khoản và trạng thái hợp đồng thông minh, giúp chứng minh trạng thái cho các client nhẹ và các thao tác tổng hợp lớp 2.
Giới thiệu
Cây Merkle là một trong những ý tưởng nền tảng giúp hệ thống blockchain hoạt động hiệu quả và có thể kiểm chứng được ở quy mô lớn. Chúng cho phép các mạng lưới tóm tắt toàn bộ tập dữ liệu trong một dấu vân tay mật mã duy nhất, đồng thời vẫn đảm bảo tính xác thực của một giao dịch hoặc thông tin cụ thể. Để hiểu tại sao cây Merkle lại quan trọng trong thiết kế blockchain, chúng ta hãy xem xét cách chúng hoạt động, cách các mạng lưới khác nhau sử dụng chúng và cách các cấu trúc mới hơn như cây Merkle có thể cải tiến chúng trong tương lai.
Cách thức hoạt động của cây Merkle
Cây Merkle, được đặt theo tên của nhà khoa học máy tính Ralph Merkle, người đã cấp bằng sáng chế cho khái niệm này vào năm 1979, là một cấu trúc dữ liệu được sử dụng để tóm tắt và xác minh tính toàn vẹn của các tập dữ liệu lớn một cách hiệu quả. Trong chuỗi khối (blockchain), cây Merkle nén hàng nghìn giao dịch thành một giá trị nhỏ gọn duy nhất được lưu trữ trong tiêu đề khối.
Cây được xây dựng từ dưới lên bằng cách sử dụng các hàm băm mật mã. Mỗi nút lá chứa giá trị băm của một mẩu dữ liệu duy nhất, chẳng hạn như một giao dịch. Sau đó, các giá trị băm của các nút lá này được ghép thành từng cặp: giá trị băm của mỗi cặp được tính bằng cách nối hai giá trị băm của các nút con lại với nhau và băm kết quả. Quá trình này lặp lại theo chiều lên, từng lớp một, cho đến khi chỉ còn lại một giá trị băm duy nhất ở trên cùng, đó chính là gốc Merkle.
Vì mỗi nút cha phụ thuộc vào cả hai nút con của nó, bất kỳ thay đổi nào đối với một nút lá duy nhất sẽ lan truyền lên trên và tạo ra một gốc Merkle hoàn toàn khác. Thuộc tính này làm cho cây Merkle trở thành một công cụ hiệu quả để phát hiện sự giả mạo: nếu hai bản sao của một tập dữ liệu tạo ra cùng một gốc Merkle, thì các tập dữ liệu đó giống hệt nhau với xác suất cực kỳ cao.
Rễ cây Merkle
Merkle root là một mã băm có kích thước cố định, thường là 32 byte (256 bit) trong các ứng dụng blockchain, hoạt động như một dấu vân tay kỹ thuật số cho toàn bộ tập dữ liệu. Phần tiêu đề khối trong hầu hết các mạng blockchain bao gồm Merkle root cùng với các siêu dữ liệu khác như dấu thời gian và mã băm của khối trước đó, giúp giữ cho tiêu đề nhỏ gọn trong khi vẫn đảm bảo tính bảo mật về mặt mật mã đối với toàn bộ các giao dịch trong khối.
Để minh họa một cách đơn giản, hãy xem xét một tập tin 8GB được chia thành tám phần. Gọi các phần khác nhau là A đến H. Mỗi phần sau đó được đưa qua một hàm băm, cho ta tám giá trị băm khác nhau.
Với mã băm của tất cả các đoạn dữ liệu, nếu có đoạn nào bị lỗi, bạn sẽ biết bằng cách so sánh nó với mã băm của nguồn, đúng không? Có thể, nhưng cách này cũng cực kỳ kém hiệu quả. Nếu tệp của bạn có hàng nghìn đoạn dữ liệu, bạn có nên băm tất cả chúng và so sánh kết quả một cách tỉ mỉ không?
Thuật toán Merkle cung cấp một giải pháp thanh lịch hơn. Lấy từng cặp mã băm, kết hợp chúng lại, sau đó băm chúng cùng nhau. Bạn sẽ nhận được mã băm hA + hB, hC + hD, hE + hF và hG + hH, và cuối cùng là bốn mã băm.
Sau đó, thực hiện thêm một vòng băm nữa và bạn sẽ nhận được hai giá trị: hABCD và hEFGH. Cuối cùng, băm hai giá trị còn lại để có được giá trị băm chính, và bạn sẽ có được Merkle gốc (hoặc giá trị băm gốc): hABCDEFGH.
Chứng minh và xác minh Merkle
Một trong những tính năng thực tiễn nhất của cây Merkle là khả năng chứng minh rằng một phần dữ liệu cụ thể thuộc về tập dữ liệu mà không cần tiết lộ toàn bộ tập dữ liệu. Điều này được gọi là bằng chứng Merkle. Để xác minh rằng một giao dịch được bao gồm trong một khối, một máy khách nhẹ chỉ cần chính giao dịch đó, một tập hợp nhỏ các hàm băm anh em dọc theo đường dẫn đến gốc và gốc Merkle từ tiêu đề khối. Trình xác minh sẽ tính toán lại các hàm băm dọc theo đường dẫn và kiểm tra xem kết quả có khớp với gốc đã biết hay không. Nếu khớp, giao dịch được chứng minh về mặt toán học là một phần của khối.
Hãy xem xét một kịch bản mà bạn muốn xác minh một giao dịch có TXID là hD. Nếu hC được cung cấp, bạn có thể tính toán hCD. Sau đó, sử dụng hAB để tính toán hABCD. Cuối cùng, với hEFGH, hãy kiểm tra xem Merkle gốc thu được có khớp với Merkle gốc trong tiêu đề khối hay không. Nếu khớp, đó là bằng chứng cho thấy giao dịch đã được bao gồm trong khối. Việc tạo ra cùng một hàm băm với dữ liệu khác nhau gần như là không thể.
Trong ví dụ trên, bạn chỉ cần băm ba lần. Nếu không có bằng chứng Merkle, bạn sẽ phải thực hiện bảy lần. Vì các khối hiện nay chứa hàng nghìn giao dịch, việc sử dụng bằng chứng Merkle giúp tiết kiệm rất nhiều thời gian và tài nguyên tính toán.
Kích thước bằng chứng tăng theo hàm logarit với số lượng lá: đối với một triệu giao dịch (một cây nhị phân có độ sâu 20), chỉ cần khoảng 20 hàm băm, tương đương khoảng 640 byte. Đây là điều cho phép các nút nhẹ, đôi khi được gọi là máy khách Xác minh Thanh toán Đơn giản (SPV), xác minh giao dịch mà không cần tải xuống toàn bộ chuỗi khối, một quy trình mà nếu không sẽ yêu cầu hàng trăm gigabyte dữ liệu.
Cây Merkle trong mạng lưới Blockchain
Bitcoin và xác minh giao dịch
Trong Bitcoin, mỗi tiêu đề khối chứa một gốc Merkle 32 byte cam kết tất cả các giao dịch trong khối đó. Các thợ đào Bitcoin xây dựng một cây Merkle từ các giao dịch mà họ đưa vào, và gốc kết quả được nhúng vào tiêu đề khối cùng với giải pháp Bằng chứng Công việc (Proof of Work). Thiết kế này có nghĩa là tiêu đề khối, thường khoảng 80 byte, đủ để xác minh rằng bất kỳ giao dịch cụ thể nào đã được bao gồm trong khối, mà không cần đến các giao dịch khác.
Bitcoin cũng sử dụng cây Merkle trong đề xuất MAST (Merkelized Abstract Syntax Trees), cho phép biểu diễn các điều kiện chi tiêu phức tạp trong các kịch bản Bitcoin dưới dạng cây Merkle. Chỉ cần tiết lộ nhánh được thực thi của kịch bản, giữ cho các điều kiện không được sử dụng ở chế độ riêng tư và giảm kích thước giao dịch.
Ethereum và bằng chứng trạng thái
Ethereum sử dụng một biến thể phức tạp hơn gọi là cây Merkle Patricia Trie, một cấu trúc cây lục phân (16 nhánh) lưu trữ số dư tài khoản, mã hợp đồng và dữ liệu lưu trữ. Không giống như cây Merkle nhị phân đơn giản được sử dụng cho các giao dịch Bitcoin, cây Merkle Patricia Trie được thiết kế để hỗ trợ cập nhật trạng thái thường xuyên: khi số dư tài khoản thay đổi, chỉ cần tính toán lại đường dẫn từ lá đó đến gốc, thay vì phải xây dựng lại toàn bộ cây.
Các bằng chứng trạng thái được tạo ra từ cây trie Merkle Patricia cho phép các máy khách nhẹ của Ethereum và các ứng dụng tổng hợp lớp 2 xác minh số dư tài khoản và lưu trữ hợp đồng mà không cần chạy một node đầy đủ. Những bằng chứng này cũng rất cần thiết cho các cầu nối xuyên chuỗi cần xác minh các sự kiện trên một chuỗi từ chuỗi khác.
Những hạn chế và hướng phát triển trong tương lai
Mặc dù cây Merkle cung cấp khả năng xác minh hiệu quả, kích thước bằng chứng vẫn tăng theo cấp số nhân với tập dữ liệu. Đối với Ethereum, khi trạng thái tăng lên, các chứng thực khối, tức là các bằng chứng cần thiết để xác thực một khối, có thể đạt đến vài megabyte. Điều này đặt ra thách thức về khả năng mở rộng đối với các máy khách không trạng thái, vì chúng sẽ cần nhận và xác minh các bằng chứng này cho mỗi khối.
Cây Verkle, sử dụng cam kết vectơ dựa trên cam kết đa thức (Kate-Zaverucha-Goldberg, hay KZG) thay vì hàm băm truyền thống, cung cấp một giải pháp tiềm năng. Bằng cách nhóm nhiều nút con dưới mỗi nút (hệ số phân nhánh là 256), cây Verkle tạo ra các bằng chứng có kích thước gần như không đổi, khoảng 170 byte, bất kể tập dữ liệu lớn đến mức nào. Ethereum đang tích cực phát triển việc tích hợp cây Verkle, dự kiến sẽ được triển khai trong bản nâng cấp tương lai. Quá trình chuyển đổi này sẽ giảm đáng kể tải dữ liệu trên các máy khách nhẹ và cải thiện khả năng mở rộng của toàn mạng.
Câu hỏi thường gặp
Nói một cách đơn giản, cây Merkle là gì?
Cây Merkle là một cách để tổ chức dữ liệu sao cho một mẩu thông tin nhỏ duy nhất, được gọi là gốc Merkle, có thể đại diện cho một tập dữ liệu lớn. Nó hoạt động bằng cách liên tục băm các cặp dữ liệu với nhau cho đến khi chỉ còn lại một mã băm duy nhất, giúp xác minh xem một mục cụ thể có thuộc tập hợp đó hay không mà không cần kiểm tra từng mục riêng lẻ.
Rễ Merkle là gì?
Gốc Merkle là mã băm duy nhất ở đỉnh của cây Merkle. Nó hoạt động như một dấu vân tay kỹ thuật số nhỏ gọn cho tất cả dữ liệu bên dưới nó. Trong mạng blockchain, gốc Merkle được lưu trữ trong tiêu đề khối và được ghi nhận vào mọi giao dịch trong khối đó, cho phép xác minh hiệu quả rằng một giao dịch là một phần của khối.
Phương pháp chứng minh Merkle hoạt động như thế nào?
Bằng chứng Merkle cung cấp một giao dịch cùng với tập hợp tối thiểu các hàm băm anh em cần thiết để tính toán lại đường dẫn từ giao dịch đó lên đến gốc Merkle. Trình xác minh sẽ băm giao dịch, kết hợp nó với các hàm băm anh em được cung cấp theo đúng thứ tự và kiểm tra xem kết quả cuối cùng có khớp với gốc Merkle đã biết trong tiêu đề khối hay không. Nếu khớp, giao dịch được chứng minh là đã được bao gồm.
Tại sao cây Merkle lại quan trọng đối với công nghệ blockchain?
Cây Merkle cho phép các mạng blockchain tách biệt tiêu đề khối khỏi dữ liệu giao dịch đầy đủ. Một máy khách nhẹ có thể chỉ tải xuống tiêu đề khối, khoảng 80 byte mỗi khối, và vẫn xác minh được giao dịch đó bằng cách sử dụng bằng chứng Merkle nhỏ gọn. Nếu không có cây Merkle, việc xác minh giao dịch sẽ yêu cầu tải xuống toàn bộ khối hoặc toàn bộ chuỗi.
Sự khác biệt giữa cây Merkle và cây Verkle là gì?
Cả hai đều là các bộ tích lũy mật mã được sử dụng để chứng minh tính thuộc về dữ liệu, nhưng chúng sử dụng các phương pháp toán học khác nhau. Cây Merkle sử dụng hàm băm và tạo ra các bằng chứng có kích thước tăng theo hàm logarit với tập dữ liệu (O(log n)). Cây Verkle sử dụng cam kết đa thức (KZG) và tạo ra các bằng chứng có kích thước gần như không đổi, chỉ vài trăm byte bất kể kích thước tập dữ liệu, khiến chúng phù hợp hơn cho các bằng chứng trạng thái chuỗi khối quy mô lớn.
Lời kết
Cây Merkle là nền tảng của kiến trúc blockchain, cho phép xác minh phi tập trung trên quy mô lớn. Bằng cách nén toàn bộ một khối giao dịch thành một mã băm 32 byte duy nhất, chúng cho phép người tham gia xác minh dữ liệu mà không cần tải xuống mọi thứ, một nguyên tắc làm nền tảng cho mọi thứ từ ví Bitcoin SPV đến bằng chứng trạng thái Ethereum và cầu nối chuỗi chéo. Khi mạng blockchain tiếp tục phát triển, các cấu trúc mật mã mới hơn như cây Merkle cuối cùng có thể bổ sung hoặc thay thế cây Merkle, nhưng khái niệm cơ bản, tính toàn vẹn dữ liệu dựa trên mã băm hiệu quả, có khả năng sẽ vẫn là một khối xây dựng cơ bản của các hệ thống phân tán trong nhiều năm tới.
Đọc thêm
Thuật toán đồng thuận Blockchain là gì?
Lịch sử mật mã học
Giải pháp mở rộng quy mô Blockchain Lớp 1 so với Lớp 2
Phân mảnh dữ liệu (Sharding) là gì và nó hoạt động như thế nào?
Tuyên bố miễn trừ trách nhiệm: Nội dung này được cung cấp cho bạn trên cơ sở "nguyên trạng" chỉ nhằm mục đích thông tin chung và giáo dục, không kèm theo bất kỳ sự đảm bảo hoặc cam kết nào. Nội dung này không nên được hiểu là lời khuyên về tài chính, pháp lý hoặc chuyên môn khác, cũng như không nhằm mục đích khuyến nghị mua bất kỳ sản phẩm hoặc dịch vụ cụ thể nào. Bạn nên tìm kiếm lời khuyên từ các cố vấn chuyên nghiệp phù hợp. Trường hợp nội dung được đóng góp bởi bên thứ ba, vui lòng lưu ý rằng những quan điểm được thể hiện thuộc về bên thứ ba đó và không nhất thiết phản ánh quan điểm của Binance Academy. Giá tài sản kỹ thuật số có thể biến động. Giá trị khoản đầu tư của bạn có thể giảm hoặc tăng và bạn có thể không thu hồi được số tiền đã đầu tư. Bạn hoàn toàn chịu trách nhiệm về các quyết định đầu tư của mình và Binance Academy không chịu trách nhiệm cho bất kỳ tổn thất nào bạn có thể phải chịu. Để biết thêm thông tin, vui lòng xem Điều khoản sử dụng, Cảnh báo rủi ro và Điều khoản của Binance Academy.