Công cụ mật mã học 101 - Giải thích hàm băm và cây Merkle
Bài viết này nói về điều gì?
Blockchain cho phép con người đạt được sự đồng thuận mà không cần bên trung gian. Thay vì dựa vào niềm tin, blockchain dựa vào các bằng chứng mật mã. Các nguyên thủy mật mã được sử dụng để cung cấp những bằng chứng này. Nhưng chúng là gì?
Trong bài viết này, chúng ta sẽ tìm hiểu hai nguyên thủy mật mã thiết yếu đối với bằng chứng mật mã trên blockchain: hàm băm và cây Merkle. Chúng ta sẽ khám phá cơ chế cốt lõi của hàm băm, xem vai trò của chúng đối với blockchain và tìm hiểu về con trỏ băm. Sau đó, chúng ta sẽ xem xét cây Merkle truyền thống và cây Merkle đồng thời, đồng thời trình bày tầm quan trọng của chúng đối với Solana.
Nguyên thủy mật mã là gì?
Nguyên thủy mật mã là một phép toán hoặc thuật toán nền tảng để xây dựng các giao thức và hệ thống mật mã. Nguyên thủy mật mã đối với giao thức mật mã cũng giống như nguyên tử đối với phân tử — chúng là các khối xây dựng nên những giải pháp phức tạp hơn. Trình tạo số ngẫu nhiên, lược đồ cam kết và mật mã khóa công khai đều là những ví dụ về nguyên thủy mật mã.
Khi đứng riêng lẻ, các nguyên thủy mật mã khá hạn chế. Khi được kết hợp, chúng cung cấp các chức năng bảo mật cơ bản như xác thực, bảo mật và toàn vẹn. Kết hợp các nguyên thủy mật mã là một quy trình rất tinh tế, đòi hỏi việc lập kế hoạch cẩn thận và hiểu biết sâu sắc về cách từng nguyên thủy tương tác với nhau. Trong quy trình này, bạn phải cân nhắc các yếu tố bảo mật dựa trên mục tiêu bảo mật muốn đạt được. Các phương pháp kết hợp nguyên thủy mật mã có thể được phân loại khái quát như sau:
- Kết hợp tuần tự: Áp dụng lần lượt từng nguyên thủy (ví dụ: chuỗi băm)
- Kết hợp song song: Sử dụng các nguyên thủy đồng thời và độc lập (ví dụ: mã hóa và băm dữ liệu cùng lúc)
- Kết hợp phân cấp: Sử dụng một nguyên thủy mật mã bên trong một nguyên thủy khác (ví dụ: cây Merkle)
Hiểu nguyên thủy mật mã là gì, cách chúng hoạt động và những điểm tinh tế khi kết hợp chúng sẽ giúp bạn hiểu và thiết kế các hệ thống an toàn, hiệu quả. Một trong những nguyên thủy mật mã được sử dụng và kết hợp phổ biến nhất là hàm băm.
Hàm băm là gì?
Hàm băm là một hàm mật mã nhận dữ liệu có kích thước bất kỳ và trả về một giá trị có kích thước cố định. Giá trị mà hàm này trả về được gọi là bản tóm lược hoặc giá trị băm. Các thuật toán băm phổ biến gồm: SHA-1, SHA-2, SHA-3, MD5 và Argon2. Hàm băm được sử dụng ở khắp nơi trong blockchain, vì vậy việc hiểu chúng là gì và hoạt động như thế nào là rất quan trọng.
Một phép so sánh đơn giản
Hãy tưởng tượng bạn đang làm một chiếc bánh sô-cô-la cầu kỳ. Chiếc bánh có nhiều tầng, mỗi tầng được làm từ những nguyên liệu riêng. Trong lúc nướng bánh, một người bạn nhắn tin hỏi bạn đang làm gì. Việc giải thích chi tiết cách làm bánh và tất cả nguyên liệu đã sử dụng sẽ khá rườm rà. Thay vào đó, bạn quyết định gửi cho người bạn đó một bức ảnh chiếc bánh sô-cô-la.
Ở đây, bức ảnh chiếc bánh đóng vai trò như một giá trị băm — đó là cách biểu diễn đơn giản, cô đọng của một thứ phức tạp hơn nhiều. Người bạn sẽ không biết mọi nguyên liệu được dùng để làm bánh, nhưng sẽ hình dung rõ bạn vừa làm gì. Giả sử chiếc bánh sô-cô-la có quả mâm xôi bên trên. Nếu bạn bỏ chúng đi hoặc thay bằng dâu tây, hình ảnh chiếc bánh sẽ hoàn toàn khác với thành phẩm. Tương tự, bất kỳ thay đổi nào đối với dữ liệu được băm cũng sẽ tạo ra một giá trị băm mới.
Đặc tính của một hàm băm mật mã tốt
Phải thừa nhận rằng định nghĩa về hàm băm nêu trước đó có thể gây hiểu lầm. Một hàm băm có thể trả về giá trị băm có kích thước thay đổi. Nó cũng có thể trả về cùng một giá trị băm cho hai đầu vào khác nhau. Ngoài ra, ai đó có thể dễ dàng dịch ngược giá trị băm để tìm ra đầu vào ban đầu. Định nghĩa trước đó thực chất dành cho một hàm băm mật mã tốt. Nhưng điều gì khiến một hàm băm mật mã trở nên tốt?
Một hàm băm tốt có tính xác định — cùng một đầu vào sẽ luôn tạo ra cùng một đầu ra. Nếu tôi băm đầu vào “baseball”, thì bất kể hệ thống nào, hàm băm đó cũng sẽ luôn tạo ra cùng một giá trị băm. Điều này cũng phần nào có nghĩa là giá trị băm sẽ có cùng kích thước, bất kể kích thước đầu vào. Đây là yếu tố quan trọng đối với hiệu quả xử lý và lưu trữ dữ liệu. Việc một đầu vào duy nhất luôn tạo ra một đầu ra duy nhất và các đầu ra này luôn có kích thước cố định là dấu hiệu rõ ràng của một hàm băm mật mã tốt.
Một hàm băm tốt có khả năng kháng tiền ảnh. Điều này có nghĩa là không thể dịch ngược đầu vào từ giá trị băm của nó trong phạm vi tính toán khả thi. Vì vậy, nếu ai đó cung cấp cho bạn một giá trị băm, bạn không thể xác định dữ liệu nào đã tạo ra giá trị đó. Điều này cũng dẫn đến nguyên tắc rằng hai tập dữ liệu khác nhau không được tạo ra cùng một giá trị băm. Một hàm băm tốt được xem là có khả năng kháng va chạm khi hai đầu vào bất kỳ không bao giờ tạo ra cùng một giá trị băm.
Một hàm băm tốt tuân theo Hiệu ứng Tuyết lở — một thay đổi nhỏ trong đầu vào phải tạo ra giá trị băm khác biệt đáng kể. Ngay cả khi chỉ thay đổi một ký tự, kết quả cũng phải là một giá trị băm hoàn toàn khác. Do đó, đầu ra băm không được tiết lộ bất kỳ thông tin nào về đầu vào hoặc có bất kỳ mẫu hình dễ nhận biết nào. Hãy chú ý đến sự khác biệt giữa các giá trị băm trong hình trên. Cáo đỏ “chạy” tạo ra một giá trị băm hoàn toàn khác so với cáo đỏ “đi bộ”. Cũng không có dấu hiệu nào cho thấy hai giá trị băm này chứa thông tin gần như giống hệt nhau.
Một hàm băm tốt phải được tính toán nhanh. Hàm băm chậm không phù hợp với các tình huống cần tính toán theo thời gian thực hoặc gần thời gian thực, chẳng hạn như xác minh giao dịch. Một hàm băm chậm có thể trở thành nút thắt nghiêm trọng, hạn chế cả thông lượng lẫn hiệu suất mạng. Hàm băm nhanh là yếu tố cần thiết để blockchain vận hành hiệu quả và an toàn.
Tại sao điều này quan trọng đối với blockchain?
Blockchain là một sổ cái phi tập trung, phân tán, ghi lại các giao dịch trên toàn mạng. Những giao dịch này được nhóm thành các khối và liên kết an toàn với nhau bằng một hàm băm tốt. Mỗi khối chứa dữ liệu giao dịch, dấu thời gian và giá trị băm của khối trước đó. Vì giá trị băm của mỗi khối phụ thuộc vào giá trị băm của khối trước, mọi thay đổi đối với nội dung của một khối sẽ làm thay đổi giá trị băm của khối đó và vô hiệu hóa tất cả các khối tiếp theo. Quy trình sử dụng các giá trị băm trước đó để tạo ra một giá trị băm mới được gọi là chuỗi băm.
Việc thêm một khối mới vào blockchain được gọi là xác nhận. Một xác nhận sẽ xác minh và bảo vệ tất cả giao dịch trong khối mới cũng như mọi khối trước đó. Lý do là mỗi xác nhận mới sẽ khiến việc thay đổi các khối trước đó trở nên khó khăn hơn. Để thay đổi một khối trước đó, kẻ tấn công sẽ phải tính toán lại tất cả giá trị băm về sau. Vì vậy, chuỗi băm đảm bảo rằng việc thay đổi blockchain là bất khả thi trong thực tế sau khi một khối đã nhận được số lượng xác nhận đáng kể.
Nói đơn giản, blockchain là một chuỗi các khối được bảo vệ bằng hàm băm. Nhưng chính xác thì chúng ta trỏ từ khối này sang khối khác bằng cách nào? Đúng là hàm băm mật mã được dùng để liên kết các khối với nhau, nhưng làm sao chúng ta có thể xem dữ liệu từ các khối trước? Tôi tưởng một hàm băm mật mã tốt phải có khả năng kháng tiền ảnh.
Con trỏ băm là gì?
Con trỏ là một biến lưu giữ vị trí của dữ liệu cụ thể trong bộ nhớ. Có thể dễ dàng truy cập dữ liệu tại địa chỉ bộ nhớ này vì con trỏ “trỏ đến” vị trí của dữ liệu. Con trỏ băm là một cấu trúc dữ liệu tương tự con trỏ, nhưng cũng chứa giá trị băm mật mã của dữ liệu được tham chiếu. Vì vậy, con trỏ băm cho bạn biết nơi truy cập một phần dữ liệu cụ thể và cho phép kiểm tra tính toàn vẹn của dữ liệu được truy cập.
Cấu trúc của blockchain có thể được mô tả chính xác hơn là một danh sách liên kết sử dụng con trỏ băm. Giá trị băm của khối trước là một con trỏ băm trỏ đến một tập hợp giao dịch và giá trị băm của tất cả giao dịch đó. Con trỏ băm hỗ trợ liên kết các khối, bảo đảm tính toàn vẹn của từng khối và xác minh rằng các khối mới thêm vào nối tiếp chính xác các khối trước đó.
Con trỏ băm được dùng để liên kết các khối với nhau một cách hiệu quả. Nhưng còn các giao dịch trong khối thì sao? Nếu một khối chứa một nghìn giao dịch, chẳng phải việc xác minh từng giao dịch sẽ rất tốn kém sao?
Cây Merkle là gì?
Cây Merkle là một cấu trúc dữ liệu dùng để tổ chức và xác minh các tập dữ liệu lớn. Dữ liệu được sắp xếp theo cấu trúc dạng cây, trong đó mỗi lá hoặc nút được gắn nhãn bằng giá trị băm của một tập dữ liệu. Mỗi nút không phải nút lá là giá trị băm của các nút con. Cây Merkle được dùng để xác minh các giao dịch nằm trong những khối cụ thể được truyền lên blockchain. Vậy nó hoạt động như thế nào?
Các giao dịch được gom thành một danh sách để tạo nên một khối. Mỗi giao dịch trong danh sách được băm bằng một hàm băm tốt. Những giá trị băm này đóng vai trò là các nút lá. Các cặp nút lá được băm cùng nhau để tạo ra một lớp giá trị băm mới. Quy trình này tiếp tục lặp lại cho đến khi chỉ còn một giá trị băm duy nhất, được gọi là gốc Merkle. Gốc Merkle được lưu trong tiêu đề của khối và đóng vai trò là dấu vân tay số của tất cả giao dịch trong khối đó. Chúng ta cũng có thể gọi gốc Merkle là giá trị băm của khối. Vì vậy, khi nói một khối mới được liên kết với khối trước đó bằng blockhash của khối trước, tức là khối mới sử dụng gốc Merkle của khối trước làm một phần trong giá trị băm của mình.
Cây Merkle giúp việc xác minh từng giao dịch trong một khối trở nên hiệu quả. Theo cách truyền thống, để xác minh một giao dịch cụ thể, bạn phải xác minh từng giao dịch, một quy trình tốn kém và mất thời gian. Cây Merkle cung cấp một “lối tắt” mật mã hỗ trợ quy trình xác minh này, được gọi là bằng chứng Merkle. Bằng chứng Merkle là đường dẫn từ nút lá của giao dịch lên đến gốc Merkle. Dựa trên hình trên, hãy hình dung đó là đường dẫn từ Data A đến gốc Merkle. Đường dẫn này cũng bao gồm các nút anh em, tức các lá nằm cạnh mỗi nút trên đường dẫn nhưng không thuộc chính đường dẫn đó. Người xác minh có thể tính toán một giá trị băm bằng đường dẫn bằng chứng để kiểm tra xem giá trị băm tính được có khớp với gốc Merkle hay không. Nếu giá trị băm kết quả khớp, người xác minh có thể tin tưởng rằng giao dịch là hợp lệ và chưa bị chỉnh sửa.
Có thể thay đổi một lá bằng cách băm dữ liệu mới của lá đó và tính toán lại gốc Merkle. Gốc Merkle mới này được dùng để xác minh những thay đổi mới và làm mất hiệu lực bằng chứng trước đó. Trong một mạng có thông lượng cao như Solana, validator có thể nhận liên tiếp nhiều yêu cầu thay đổi đối với cây Merkle on-chain (ví dụ: trong cùng một slot). Mỗi thay đổi dữ liệu phải được tính toán lại tuần tự, nếu không mỗi yêu cầu thay đổi tiếp theo sẽ bị yêu cầu thay đổi trước đó trong cùng slot làm mất hiệu lực. Thay đổi dữ liệu lá và tính toán gốc Merkle mới là thao tác rất phổ biến trong blockchain. Vậy chúng ta xử lý các thay đổi nhanh chóng bằng cách nào?
Cây Merkle đồng thời là gì?
Cây Merkle đồng thời là một cây Merkle được tối ưu hóa cho các thao tác đọc và ghi đồng thời. Nó lưu trữ một nhật ký thay đổi an toàn gồm những thay đổi gần đây nhất, giá trị băm gốc của chúng và bằng chứng để suy ra giá trị đó. Nhật ký thay đổi này được lưu on-chain trong một account dành riêng cho cây, với số lượng thay đổi tối đa có thể xảy ra trong khi gốc Merkle vẫn còn hợp lệ. Số lượng thay đổi tối đa này được gọi là maxBufferSize. Vì vậy, khi validator nhận liên tiếp các yêu cầu thay đổi đối với cây Merkle on-chain, validator có thể sử dụng nhật ký này làm nguồn dữ liệu chuẩn, cho phép thực hiện tối đa maxBufferSize thay đổi đối với cây trong cùng một slot.
Cây Merkle đồng thời cải tiến cây Merkle truyền thống, giúp chúng phù hợp với các môi trường có thông lượng cao như Solana. Để tạo một cây Merkle đồng thời on-chain trên Solana, có ba thuộc tính ảnh hưởng đến kích thước cây, chi phí tạo cây và số lượng thay đổi đồng thời đối với cây:
- Độ sâu tối đa
- Kích thước bộ đệm tối đa
- Độ sâu canopy
Độ sâu tối đa là số bước nhảy lớn nhất cần thực hiện để đi từ một lá bất kỳ đến gốc Merkle. maxDepth được dùng để xác định số nút tối đa cần lưu trữ trong cây. Có thể tính giá trị này bằng công thức: numberOfNodes = 2 ^ maxDepth. Độ sâu của cây phải được đặt khi khởi tạo, vì vậy bạn cần sử dụng công thức này để xác định số lượng phần dữ liệu muốn lưu trong cây.
Như đã nêu, kích thước bộ đệm tối đa là số lượng thay đổi lớn nhất có thể thực hiện đối với một cây trong khi gốc Merkle của cây vẫn còn hợp lệ.
Độ sâu canopy chỉ một tập hợp con của cây Merkle được lưu on-chain. Các bằng chứng được lưu vào bộ nhớ đệm này dùng để đối chiếu một giá trị băm với gốc Merkle on-chain. Phải sử dụng toàn bộ đường dẫn bằng chứng để xác minh quyền sở hữu ban đầu của một lá khi thực hiện thao tác ghi lên lá đó. Ví dụ: bạn sẽ cần ghi vào cây nếu đang chuyển một NFT. Canopy cho phép giảm kích thước bằng chứng và tránh phải sử dụng kích thước bằng chứng là maxDepth để xác minh cây. Một cây có maxDepth bằng 20 sẽ yêu cầu kích thước bằng chứng là 20. Với canopy bằng 15, mỗi giao dịch ghi chỉ cần gửi bằng chứng có kích thước 5. Vì vậy, độ sâu canopy cao hơn đồng nghĩa với chi phí trả trước cao hơn để sau này có thể gửi các bằng chứng nhỏ hơn.
Độ sâu canopy là một trong những yếu tố chính quyết định chi phí tạo cây. Nguyên nhân là độ sâu canopy càng lớn thì account cần thiết càng lớn. Nhà phát triển có thể sử dụng gói @solana/spl-account-compression để tính dung lượng cần thiết cho một kích thước cây nhất định và chi phí phân bổ dung lượng cần thiết cho cây on-chain. Nhà phát triển có thể sử dụng hàm getConcurrentMerkleTreeAccountSize để tính dung lượng cần thiết cho một account dựa trên các tham số của account đó, rồi sử dụng getMinimumBalanceForRentExemption trên dung lượng cần thiết để nhận được chi phí cuối cùng tính bằng Lamport.
Solana sử dụng cây Merkle đồng thời để nén trạng thái. Nén trạng thái là phương pháp tạo giá trị băm từ dữ liệu off-chain và lưu giá trị đó on-chain để xác minh an toàn. Trường hợp sử dụng phổ biến nhất của nén trạng thái là NFT nén vì phương pháp này giảm đáng kể chi phí đúc. Ví dụ: đúc một tỷ NFT trên Solana sẽ tốn 507 $SOL, so với 12 000 000 $SOL khi dùng NFT “thông thường”. Giờ đây, khi đã hiểu rõ về hàm băm và cây Merkle, chúng ta sẽ đi sâu vào NFT nén trong một bài viết sắp tới!
Kết luận
Xin chúc mừng! Trong bài viết này, chúng ta đã phân tích hàm băm và cây Merkle, hai nguyên thủy mật mã đóng vai trò thiết yếu đối với blockchain. Hiểu blockchain không phải là việc đơn giản — đây là những hệ thống phân tán phức tạp, đòi hỏi kiến thức kỹ thuật rộng. Kiến thức này thường được mặc định là điều mà một nhà phát triển, người dùng hoặc nhà đầu tư bình thường đã biết. Bài viết này không yêu cầu bất kỳ kiến thức nào trước đó về nguyên thủy mật mã. Thay vào đó, chúng ta bắt đầu từ những kiến thức cơ bản trước khi chuyển sang thảo luận các chủ đề phức tạp hơn về cây Merkle truyền thống và cây Merkle đồng thời. Nắm vững nền tảng này là điều rất quan trọng khi chúng ta chuẩn bị tìm hiểu những chủ đề phức tạp hơn như NFT nén. Với kiến thức mới này, bạn sẽ có sự chuẩn bị tốt hơn để tìm hiểu các cơ sở mã hoặc tham gia thảo luận về nguyên thủy mật mã và những giải pháp mật mã phức tạp hơn.
Nếu bạn đã đọc đến đây, anon, xin cảm ơn!
Tài nguyên bổ sung / Đọc thêm
Bài viết liên quan
Đăng ký nhận tin từ Helius
Luôn cập nhật những thông tin mới nhất về phát triển Solana và nhận thông báo khi chúng tôi đăng bài