Trie

Trie là gì?

Trie là cấu trúc dữ liệu dạng cây, dùng để lưu trữ và truy xuất dữ liệu khóa-giá trị bằng cách lần theo từng phần của khóa.

Trong crypto, trie quan trọng vì blockchain cần phương thức đáng tin cậy để tổ chức tài khoản, số dư, dữ liệu lưu trữ hợp đồng thông minh, giao dịch và bằng chứng.

Từ trie bắt nguồn từ retrieval và thường được phát âm như “try”.

Cơ sở dữ liệu thông thường có thể lưu trực tiếp một khóa và giá trị, nhưng trie chia khóa thành các phần nhỏ hơn và đặt các phần đó dọc theo một đường dẫn.

Mỗi bước trên đường dẫn thu hẹp phạm vi tìm kiếm cho đến khi hệ thống đến giá trị gắn với khóa đầy đủ.

Điều này khiến trie hữu ích với dữ liệu cần được tìm kiếm, cập nhật và xác minh nhiều lần.

Trong hệ thống blockchain, trie thường được kết hợp với hashing mật mã để tạo cấu trúc dữ liệu được xác thực.

Cấu trúc dữ liệu được xác thực cho phép người dùng kiểm chứng dữ liệu cụ thể thuộc một tập dữ liệu lớn hơn mà không cần tải xuống mọi phần của tập dữ liệu đó.

Đây là lý do trie quan trọng với node, ví, trình khám phá blockchain, light client, hợp đồng thông minh và nghiên cứu mở rộng blockchain.

Ví dụ crypto nổi tiếng nhất là modified Merkle Patricia trie của Ethereum, được dùng trên toàn execution layer để tổ chức dữ liệu khóa-giá trị theo cách xác định và có thể xác minh bằng mật mã.

Vì sao trie quan trọng trong crypto?

Trie quan trọng trong crypto vì blockchain phải cho phép nhiều máy tính độc lập đồng thuận về cùng một trạng thái.

Trạng thái là tình trạng hiện tại của blockchain, gồm số dư tài khoản, mã hợp đồng thông minh, giá trị lưu trữ và dữ liệu sổ cái khác.

Nếu hai node xử lý cùng một block, chúng phải kết thúc với cùng state root.

State root là bản tóm tắt mật mã nhỏ gọn của toàn bộ trạng thái.

Nếu chỉ một số dư tài khoản hoặc giá trị lưu trữ thay đổi không chính xác, root kết quả phải thay đổi.

Điều này cho phép node so sánh giá trị root nhỏ thay vì tự so sánh toàn bộ cơ sở dữ liệu.

Ethereum.org giải thích Merkle Patricia trie có tính xác định và có thể xác minh bằng mật mã; mọi nỗ lực sửa đổi trạng thái bằng giá trị khác sẽ tạo state root hash khác, theo tài liệu Merkle Patricia Trie.

Thuộc tính này thiết yếu cho cơ chế đồng thuận blockchain vì validator và node cần cách chung để biết block producer đã tính kết quả đúng hay chưa.

Nếu không có trie được xác thực hoặc cấu trúc tương tự, việc xác minh trạng thái blockchain lớn sẽ khó và kém hiệu quả hơn nhiều.

Trie cơ bản hoạt động như thế nào?

Trie cơ bản lưu dữ liệu bằng cách chia khóa thành các ký hiệu nhỏ hơn.

Ví dụ, trie dựa trên từ có thể lưu “cat”, “car” và “cap” bằng cách dùng chung hai chữ cái đầu “ca”, sau đó phân nhánh ở chữ cái cuối.

Cấu trúc tiền tố dùng chung này giảm lưu trữ lặp lại khi nhiều khóa bắt đầu giống nhau.

Trong hệ thống crypto, khóa thường không phải từ tiếng Anh đơn giản.

Chúng có thể là địa chỉ, storage slot đã hash, chỉ mục giao dịch hoặc giá trị đã mã hóa.

Trie lần theo từng phần của khóa cho đến khi đến giá trị.

Nếu khóa không tồn tại, đường dẫn sẽ thất bại trước khi đến giá trị hợp lệ.

Về lý thuyết, cấu trúc này có thể hỗ trợ tra cứu, chèn và xóa nhanh.

Tuy nhiên, trie thuần có thể kém hiệu quả nếu khóa dài và nhiều đường dẫn chỉ có một node con.

Đó là lý do hệ thống blockchain thường dùng các dạng trie tối ưu như Patricia trie và Merkle Patricia trie.

Trie và tree

Trie là một loại tree, nhưng được thiết kế xoay quanh khóa và tiền tố.

Tree thông thường có thể tổ chức giá trị theo phép so sánh, phân cấp hoặc quan hệ cha-con.

Trie tổ chức giá trị bằng cách đi qua các ký hiệu của khóa.

Điều này khiến trie đặc biệt hữu ích khi nhiều khóa cùng tiền tố.

Trong blockchain, khóa có thể là chuỗi byte dài, nên tree đơn giản không phải lúc nào cũng lý tưởng.

Trie có thể khiến đường dẫn đến một giá trị phụ thuộc trực tiếp vào chính khóa đó.

Điều này hữu ích khi node cần hành vi xác định.

Hành vi xác định nghĩa là mọi node trung thực đều đạt cùng kết quả với cùng dữ liệu đầu vào.

Trong crypto, cấu trúc dữ liệu xác định quan trọng vì mạng không thể phụ thuộc vào một máy chủ cơ sở dữ liệu trung tâm để quyết định kết quả.

Mọi full node đều phải có thể tính cùng root từ cùng dữ liệu.

Trie và Merkle tree

Trie tổ chức dữ liệu theo đường dẫn khóa, trong khi Merkle tree tổ chức dữ liệu bằng cách hash các leaf với nhau cho đến khi còn một root hash.

Merkle tree hữu ích vì tạo cam kết mật mã đối với một tập dữ liệu.

Merkle proof có thể chứng minh một dữ liệu thuộc tập đã cam kết mà không cần tiết lộ hoặc tải toàn bộ tập đó.

Trie hữu ích vì hỗ trợ tra cứu khóa-giá trị hiệu quả.

Merkle Patricia trie kết hợp các ý tưởng này.

Nó dùng đường dẫn khóa kiểu trie để tra cứu và hashing kiểu Merkle để xác minh.

Sự kết hợp này mạnh mẽ vì node blockchain cần cả truy cập cơ sở dữ liệu lẫn bằng chứng mật mã.

Trie thông thường có thể tìm giá trị, nhưng không tự động chứng minh các giá trị thuộc state root đáng tin cậy.

Merkle tree thông thường có thể chứng minh tính thành viên, nhưng không phải lúc nào cũng được thiết kế để cập nhật khóa-giá trị hiệu quả.

Merkle Patricia trie cung cấp cho hệ thống kiểu Ethereum cách quản lý trạng thái thay đổi trong khi vẫn duy trì cam kết root có thể xác minh.

Patricia trie là gì?

Patricia trie là trie tối ưu nén các đường dẫn khi có đoạn dài không phân nhánh.

PATRICIA là viết tắt của Practical Algorithm To Retrieve Information Coded in Alphanumeric.

Mục tiêu là tránh lãng phí không gian cho các node chỉ trỏ đến một node tiếp theo.

Trong trie thông thường, khóa dài có thể cần nhiều bước ngay cả khi không có nhánh có ý nghĩa trên đường đi.

Patricia trie có thể lưu một đoạn đường dẫn dùng chung gọn hơn.

Điều này hữu ích với khóa blockchain vì địa chỉ và hash có thể dài.

Ethereum.org giải thích cấu trúc dữ liệu của Ethereum mượn các đặc điểm từ PATRICIA vì được thiết kế để truy xuất hiệu quả các mục tạo nên trạng thái Ethereum, trong hướng dẫn Patricia Merkle trie.

Nén đường dẫn giúp giảm số node cần được duyệt, lưu trữ và chứng minh.

Điều đó quan trọng vì trạng thái blockchain có thể gồm hàng triệu tài khoản và nhiều mục lưu trữ hơn nữa.

Cấu trúc nhỏ hơn, hiệu quả hơn giúp node xử lý thay đổi trạng thái với chi phí hoạt động thấp hơn.

Merkle Patricia trie là gì?

Merkle Patricia trie là cấu trúc dữ liệu khóa-giá trị được xác thực, kết hợp Merkle hashing, tra cứu trie và nén đường dẫn Patricia.

Nó đôi khi được viết tắt là MPT.

Ethereum sử dụng modified Merkle Patricia trie cho dữ liệu quan trọng ở execution layer.

Tài liệu cấu trúc dữ liệu Ethereum chính thức cho biết Patricia Merkle tries mã hóa các cặp khóa-giá trị thành trie có tính xác định và được xác thực bằng mật mã.

Trong Ethereum, MPT cho phép mạng cam kết với cơ sở dữ liệu trạng thái lớn bằng một root hash duy nhất.

Root hash được lưu trong dữ liệu block và hoạt động như dấu vân tay của trạng thái sau khi giao dịch được thực thi.

Nếu node tính state root khác block proposer, node biết rằng có vấn đề.

Đây là một lý do MPT rất quan trọng với mô hình thực thi Ethereum.

Chúng giúp liên kết cập nhật cơ sở dữ liệu cục bộ với đồng thuận toàn cục.

Chúng cũng hỗ trợ Merkle proof để chứng minh dữ liệu tài khoản hoặc lưu trữ so với root đã biết.

Modified Merkle Patricia trie trong Ethereum

Phiên bản Ethereum thường được gọi là modified Merkle Patricia trie.

Ethereum Yellow Paper nêu rằng Ethereum duy trì ánh xạ world state trong modified Merkle Patricia tree và hash node root có thể đóng vai trò định danh an toàn cho toàn bộ trạng thái hệ thống, trong Ethereum Yellow Paper.

Điều này nghĩa root trie cam kết với toàn bộ tập trạng thái tài khoản.

Trạng thái tài khoản gồm dữ liệu như nonce, số dư, storage root và code hash.

Dữ liệu lưu trữ hợp đồng thông minh cũng được tổ chức qua các cấu trúc trie.

Khi giao dịch thay đổi số dư hoặc giá trị lưu trữ hợp đồng, đường dẫn trie liên quan thay đổi.

Thay đổi đó tác động đến các hash node cha cho đến tận root.

State root cuối cùng sau đó phản ánh trạng thái blockchain đã cập nhật.

Đây là cách một hash nhỏ có thể đại diện cho lượng lớn dữ liệu trạng thái thay đổi.

Modified MPT là một trong những lý do node Ethereum có thể độc lập xác minh việc thực thi block có đúng không.

Các node trong Merkle Patricia trie

Merkle Patricia trie sử dụng nhiều loại node.

Ethereum.org liệt kê null node, branch node, leaf node và extension node trong tài liệu MPT.

Null node đại diện cho giá trị trống.

Branch node có thể trỏ đến nhiều đường dẫn tiếp theo.

Leaf node lưu đường dẫn đã mã hóa cuối cùng và giá trị.

Extension node lưu đoạn đường dẫn dùng chung và trỏ tới node khác.

Các loại node này cho phép trie lưu dữ liệu khóa-giá trị thưa thớt hiệu quả.

Cấu trúc thưa thớt nghĩa là có nhiều khóa khả dĩ, nhưng chỉ một số khóa thực sự có giá trị.

Khóa Ethereum thường được biểu diễn bằng nibble, trong đó một nibble bằng nửa byte.

Việc dùng nibble cho trie tối đa 16 lựa chọn đường dẫn tại mỗi branch node.

Thiết kế này giúp trie điều hướng đường dẫn khóa thập lục phân theo cách dễ dự đoán.

State trie

State trie là trie cam kết với world state của Ethereum.

World state bao gồm mọi tài khoản và dữ liệu tài khoản tương ứng.

Mỗi tài khoản có thể là externally owned account được kiểm soát bằng khóa riêng tư hoặc contract account được kiểm soát bằng mã.

State trie ánh xạ địa chỉ tài khoản tới dữ liệu tài khoản đã mã hóa.

State root là root hash của trie này sau khi giao dịch trong block được xử lý.

Khi validator xác minh block, họ thực thi lại giao dịch và tính state root kết quả.

Trang lộ trình Verkle trees của Ethereum.org giải thích block đã xác minh là block có state root hash tính được khớp với root do block proposer cung cấp.

Điều này khiến state trie trở thành thành phần trung tâm của việc xác thực block.

Đây không chỉ là chi tiết lưu trữ ẩn trong phần mềm client.

Nó là một phần trong cách Ethereum chứng minh chuyển đổi trạng thái hợp lệ.

Storage trie

Storage trie lưu dữ liệu lưu trữ hợp đồng thông minh cho một tài khoản cụ thể.

Mỗi tài khoản hợp đồng thông minh có storage root trỏ đến storage trie riêng.

Storage trie này ánh xạ khóa lưu trữ đến giá trị lưu trữ.

Ví dụ, hợp đồng token có thể lưu số dư, allowances, dữ liệu nguồn cung và giá trị cấu hình trong storage.

Mỗi giá trị đó có thể được biểu diễn qua storage slot.

Khi người dùng chuyển token, storage hợp đồng có thể thay đổi do số dư được cập nhật.

Thay đổi storage đó cập nhật storage trie root của hợp đồng.

Dữ liệu tài khoản trong state trie sau đó thay đổi vì storage root của tài khoản đã đổi.

Điều này tạo chuỗi cam kết mật mã từ một storage slot đến state root tổng thể.

Chuỗi này giúp storage proof trở nên khả thi.

Transaction trie

Transaction trie cam kết với các giao dịch được đưa vào block.

Mỗi block có transaction root tóm tắt các giao dịch trong block đó.

Điều này cho phép node và client xác minh giao dịch được đưa vào block so với dữ liệu block.

Transaction trie khác state trie vì nó mô tả nội dung block thay vì trạng thái tài khoản hiện tại.

State trie thay đổi khi giao dịch cập nhật tài khoản và hợp đồng.

Transaction trie ghi nhận những giao dịch nào được đưa vào một block cụ thể.

Sự phân biệt này quan trọng vì việc giao dịch được đưa vào block và tác động trạng thái của nó có liên quan nhưng không giống nhau.

Một giao dịch có thể được đưa vào block nhưng vẫn thất bại khi thực thi.

Transaction trie có thể chứng minh tính bao gồm, trong khi receipt trie có thể cho biết chi tiết kết quả thực thi.

Người dùng kiểm tra giao dịch nên hiểu việc được đưa vào block chỉ là một phần của toàn bộ câu chuyện giao dịch.

Receipt trie

Receipt trie cam kết với biên nhận giao dịch của một block.

Biên nhận ghi lại kết quả thực thi giao dịch.

Nó có thể gồm trạng thái, gas đã dùng, logs và dữ liệu liên quan sự kiện tùy quy tắc chain và cách client hiển thị.

Biên nhận quan trọng với ví, trình khám phá, indexer và ứng dụng phi tập trung.

Ví dụ, sự kiện chuyển token thường được đọc từ transaction logs.

Receipt trie giúp cam kết các kết quả đó vào dữ liệu block.

Điều này cho phép client xác minh một biên nhận cụ thể thuộc block.

Đối với nhà phát triển, receipt proofs có thể quan trọng khi xây dựng nhắn tin cross-chain, bridge, công cụ phân tích hoặc ứng dụng dựa trên proof.

Với người dùng, receipt trie thường không hiển thị.

Tuy nhiên, nó hỗ trợ dữ liệu explorer mà người dùng dựa vào để kiểm tra giao dịch thành công hoặc thất bại.

Trie root

Trie root là hash cấp cao nhất, tóm tắt toàn bộ dữ liệu trong trie.

Nếu bất kỳ giá trị nào trong trie thay đổi, root phải thay đổi.

Điều này biến root thành cam kết nhỏ gọn với toàn bộ tập dữ liệu.

Trong Ethereum, block header bao gồm các root tóm tắt cấu trúc dữ liệu quan trọng.

State root tóm tắt trạng thái sau block.

Transaction root tóm tắt giao dịch trong block.

Receipt root tóm tắt biên nhận giao dịch của block.

Các root này giúp node độc lập đồng thuận về những gì đã xảy ra mà không tin cậy máy chủ trung tâm.

Root sai là dấu hiệu phép tính của node hoặc dữ liệu block proposer không khớp kết quả dự kiến.

Với crypto, đây là một cách thực tế hashing biến dữ liệu thô thành đồng thuận có thể xác minh.

Merkle proofs và trie

Merkle proof là tập dữ liệu chứng minh một giá trị được bao gồm trong cấu trúc dữ liệu lớn hơn đã cam kết.

Trong trie, proof thường bao gồm các node trên đường dẫn từ root đến giá trị cần chứng minh.

Người xác minh có thể hash dữ liệu proof từng bước và so sánh kết quả với root đã biết.

Nếu root tính được khớp root đáng tin cậy, proof hợp lệ theo các giả định hash.

Điều này cho phép light client hoặc hợp đồng thông minh xác minh giá trị cụ thể mà không cần lưu toàn bộ trạng thái.

Ví dụ, proof có thể cho thấy tài khoản nhất định có số dư nhất định tại state root đã biết.

Proof cũng có thể cho thấy storage slot hợp đồng thông minh có giá trị nhất định.

Storage proofs hữu ích cho bridge, ứng dụng cross-chain, rollup và xác minh trạng thái lịch sử.

Tuy nhiên, tạo và xác minh proof có thể phức tạp vì định dạng trie, mã hóa và root chính xác phải khớp quy tắc chain.

Proof chỉ có ý nghĩa nếu người xác minh tin cậy root mà họ kiểm tra.

Trie và light client

Light client là client blockchain không lưu trữ hoặc xử lý mọi thứ mà full node lưu trữ và xử lý.

Chúng dựa vào proof nhỏ gọn, header và cam kết mật mã đáng tin cậy.

Trie hỗ trợ light client vì root hash có thể cam kết với trạng thái lớn.

Light client có thể xác minh proof nhỏ so với root đã biết thay vì tải toàn bộ cơ sở dữ liệu.

Điều này quan trọng với ví di động, thiết bị nhúng, trình duyệt và ứng dụng không thể chạy full node.

Tuy nhiên, Merkle Patricia trie proofs hiện tại có thể lớn trong một số trường hợp sử dụng.

Ethereum.org giải thích các Merkle trie witness hiện tại quá lớn để hỗ trợ stateless client hiệu quả trong tài liệu Verkle trees.

Đây là lý do nhà nghiên cứu Ethereum nghiên cứu Verkle trees và cải tiến cam kết trạng thái khác.

Mục tiêu là giúp việc xác minh nhẹ hơn mà không làm suy yếu bảo mật.

Vì vậy, trie quan trọng không chỉ với node hiện nay mà còn với thiết kế mở rộng blockchain trong tương lai.

Trie và stateless client

Stateless client là client có thể xác minh block mà không lưu trữ đầy đủ trạng thái hiện tại tại chỗ.

Thay vì lưu toàn bộ cơ sở dữ liệu trạng thái, client nhận witness cùng block.

Witness chứa các mảnh trạng thái và dữ liệu proof cần thiết để xác minh chuyển đổi trạng thái của block.

Ethereum.org giải thích stateless client dùng witness cho dữ liệu trạng thái thay vì bản sao cục bộ của toàn bộ cơ sở dữ liệu trạng thái, qua lộ trình stateless client và Verkle tree.

Thách thức là witness dựa trên cấu trúc Merkle trie hiện tại có thể quá lớn.

Witness lớn là vấn đề vì chúng phải được chia sẻ nhanh trong mạng ngang hàng.

Nếu chỉ máy mạnh với băng thông lớn có thể theo kịp, mạng trở nên tập trung hơn.

Cấu trúc trie hoặc tree tốt hơn có thể giảm kích thước witness và giúp nhiều người dùng xác minh dễ hơn.

Đây là lý do thiết kế cấu trúc dữ liệu liên hệ trực tiếp với tính phi tập trung.

Một cấu trúc dữ liệu trông như chi tiết kỹ thuật cấp thấp có thể ảnh hưởng đến việc ai có thể chạy node.

Trie và Verkle trees

Verkle trees là hướng nâng cấp được đề xuất cho cấu trúc dữ liệu trạng thái Ethereum.

Verkle tree có mục đích tương tự Merkle tree, nhưng dùng vector commitments để hỗ trợ witness nhỏ hơn.

Ethereum.org giải thích Verkle trees có thể giúp node ngừng lưu lượng lớn dữ liệu trạng thái mà không mất khả năng xác thực block, qua lộ trình Verkle trees chính thức.

Điều này quan trọng vì state trie hiện tại của Ethereum lớn và khó xác thực theo cách nhẹ.

Verkle trees được thiết kế để witness nhỏ hơn và thực tế hơn cho stateless client.

Chúng không giống Merkle Patricia tries.

Chúng là một phần của nỗ lực hướng tới tương lai nhằm cải thiện truy cập và xác minh trạng thái.

Với người đọc thuật ngữ, điểm chính là trie không phải chủ đề đã được giải quyết cố định.

Cấu trúc dữ liệu blockchain tiếp tục phát triển vì mạng cần khả năng mở rộng tốt hơn, yêu cầu phần cứng thấp hơn và hiệu quả proof cao hơn.

Hiểu trie giúp dễ hiểu lý do Verkle trees đang được nghiên cứu.

Trie và chi phí gas

Thao tác trie có thể ảnh hưởng hiệu suất blockchain và chi phí giao dịch.

Khi giao dịch đọc hoặc ghi trạng thái, client có thể cần truy cập và cập nhật dữ liệu liên quan trie.

Ghi storage hợp đồng thông minh tốn phí một phần vì thay đổi trạng thái vĩnh viễn.

Thay đổi trạng thái vĩnh viễn tốn kém hơn tính toán tạm thời vì kết quả phải được mạng lưu trữ và xác minh.

Chuyển token có thể cập nhật số dư trong storage hợp đồng.

Giao dịch DeFi có thể cập nhật nhiều storage slot trên nhiều hợp đồng.

Mỗi lần cập nhật có thể góp phần làm tăng trạng thái và công việc bảo trì trie.

Đây là lý do nhà phát triển blockchain quan tâm đến tối ưu hóa storage.

Viết hợp đồng thông minh hiệu quả không chỉ giúp người dùng tiết kiệm phí.

Nó cũng giúp giảm áp lực trạng thái dài hạn lên mạng.

Trie và storage hợp đồng thông minh

Storage hợp đồng thông minh là một trong những nơi trie quan trọng nhất với nhà phát triển.

Khi hợp đồng lưu dữ liệu vĩnh viễn, dữ liệu đó trở thành một phần trạng thái blockchain.

Storage root của hợp đồng cam kết với storage trie của hợp đồng.

Mỗi biến storage cuối cùng đều được biểu diễn qua storage slots.

Các kiểu dữ liệu Solidity phức tạp như mappings và arrays được mã hóa thành storage slots theo quy tắc compiler.

Khi người dùng tương tác với hợp đồng, các slot đó có thể được đọc hoặc thay đổi.

Nhà phát triển nên hiểu storage không chỉ là tiện ích lập trình.

Nó là một phần của cơ sở dữ liệu toàn cục được cam kết bằng mật mã.

Thiết kế storage kém có thể tăng phí gas, làm proof lớn hơn và tạo rủi ro nâng cấp.

Thiết kế storage tốt có thể giúp hợp đồng rẻ hơn, rõ ràng hơn và dễ audit hơn.

Trie và trình khám phá blockchain

Trình khám phá blockchain dựa vào cấu trúc dữ liệu blockchain, lập chỉ mục và dữ liệu client để hiển thị thông tin dễ đọc cho người dùng.

Người dùng có thể tìm một địa chỉ và xem số dư, chuyển token, lệnh gọi hợp đồng và lịch sử giao dịch.

Phía sau giao diện, blockchain lưu trạng thái và dữ liệu block dưới các dạng kỹ thuật hơn.

Trie giúp cam kết với dữ liệu đó, còn explorer lập chỉ mục và hiển thị dữ liệu.

Người dùng nên hiểu explorer là công cụ đọc, không tự nó là nguồn chân thực.

Nguồn chân thực là dữ liệu blockchain được node xác minh và cam kết qua các root.

Nếu explorer bị chậm hoặc có lỗi lập chỉ mục, chain cơ bản vẫn có thể chính xác.

Đây là lý do nhà phát triển và người dùng nâng cao thường xác minh dữ liệu qua node, proof hoặc nhiều nguồn.

Trie roots tạo nền tảng mật mã để explorer có thể xây dựng phía trên.

Explorer giúp dữ liệu dễ đọc với con người, nhưng trie giúp dữ liệu có thể xác minh.

Trie và rollup

Rollup có thể dùng state trees hoặc tries riêng để theo dõi trạng thái off-chain hoặc Layer 2.

Rollup cần cách cam kết với trạng thái hiện tại và chứng minh chuyển đổi trạng thái hợp lệ.

Một số rollup sử dụng zero-knowledge proofs, fraud proofs, Merkle proofs hoặc cấu trúc cam kết khác.

Ngay cả khi cấu trúc dữ liệu chính xác không phải MPT của Ethereum, ý tưởng cơ bản tương tự vẫn thường xuất hiện.

Hệ thống cam kết với trạng thái lớn bằng root nhỏ gọn.

Người dùng hoặc hợp đồng có thể xác minh các tuyên bố so với root đó.

Đây là lý do học về trie giúp hiểu kiến trúc rollup.

Rollup không chỉ là giao dịch rẻ hơn.

Chúng còn liên quan đến cam kết trạng thái, tạo proof, khả dụng dữ liệu và xác minh.

Cấu trúc giống trie là một trong các nền tảng làm những hệ thống này khả thi.

Trie và bridge

Bridge đôi khi dùng proof để xác minh sự kiện, số dư, thông điệp hoặc giá trị storage từ chain khác.

Bridge có thể cần chứng minh giao dịch đã xảy ra hoặc giá trị storage đã thay đổi.

Trie proofs có thể giúp xác minh các tuyên bố đó khi chain đích hoặc verifier biết root đáng tin cậy của chain nguồn.

Tuy nhiên, bảo mật bridge phụ thuộc nhiều hơn chính trie proof.

Nó cũng có thể phụ thuộc vào tập validator, relayer, logic light client, giả định về tính hoàn tất, bảo mật hợp đồng thông minh và quyền kiểm soát nâng cấp.

Proof chính xác vẫn có thể không an toàn nếu root đáng tin cậy đến từ nguồn yếu hoặc bị xâm phạm.

Đây là lý do người dùng không nên cho rằng từ “proof” khiến bridge không có rủi ro.

Proof phải gắn với mô hình xác minh an toàn.

Trie cung cấp công cụ mạnh để chứng minh dữ liệu được bao gồm, nhưng thiết kế bridge phải xử lý nhiều rủi ro bổ sung.

Phân tích bridge tốt xem xét toàn bộ đường tin cậy từ trạng thái chain nguồn đến hành động trên chain đích.

Trie và bảo mật

Trie tăng cường bảo mật bằng cách giúp việc giả mạo dữ liệu dễ bị phát hiện hơn.

Nếu ai đó thay đổi giá trị được lưu, các hash dọc theo đường dẫn phải thay đổi.

Thay đổi đó phải dẫn đến root khác.

Node so sánh root tính được với root dự kiến có thể phát hiện sự không khớp.

Đây là phần quan trọng của tính toàn vẹn mật mã.

Tuy nhiên, trie tự nó không phải giải pháp bảo mật hoàn chỉnh.

Trie không thể ngăn người dùng ký giao dịch độc hại.

Trie không thể sửa lỗi hợp đồng thông minh.

Trie không thể làm giá oracle sai trở nên chính xác.

Trie không thể bảo vệ tiền nếu bridge tin nhầm root.

Trie giúp chứng minh tính toàn vẹn dữ liệu, nhưng bảo mật ứng dụng vẫn cần mã an toàn, quản lý khóa tốt, audit và thiết kế giao thức mạnh.

Lợi ích của trie trong hệ thống blockchain

Lợi ích đầu tiên của trie là lưu trữ khóa-giá trị có tổ chức.

Lợi ích thứ hai là tra cứu có tính xác định, giúp các node độc lập đạt cùng kết quả.

Lợi ích thứ ba là nén tiền tố dùng chung khi áp dụng tối ưu hóa kiểu Patricia.

Lợi ích thứ tư là xác minh mật mã khi trie được kết hợp với Merkle hashing.

Lợi ích thứ năm là hỗ trợ proof, cho phép người dùng xác minh dữ liệu cụ thể so với root.

Lợi ích thứ sáu là cam kết trạng thái, giúp blockchain tóm tắt cơ sở dữ liệu lớn bằng hash nhỏ.

Lợi ích thứ bảy là tương thích với nghiên cứu light client và stateless client.

Các lợi ích này giải thích vì sao trie xuất hiện trong thiết kế giao thức blockchain nghiêm túc.

Chúng không chỉ là khoa học máy tính trừu tượng.

Chúng giúp mạng thực lưu, xác minh và cập nhật dữ liệu tài chính.

Hạn chế của trie

Trie có thể phức tạp để triển khai chính xác.

Quy tắc mã hóa phải được tuân thủ tuyệt đối, nếu không các root sẽ không khớp.

Proof có thể trở nên lớn khi cần nhiều đường dẫn hoặc node đồng cấp.

Sự tăng trưởng trạng thái có thể khiến cơ sở dữ liệu nền trở nên nặng đối với node.

Cập nhật trạng thái có thể đòi hỏi nhiều lần đọc và ghi cơ sở dữ liệu.

Các implementation client khác nhau phải thống nhất về cùng quy tắc trie.

Trạng thái lịch sử có thể cần thêm dung lượng nếu node cần cung cấp proof cũ.

Merkle Patricia trie witnesses đủ lớn khiến Ethereum đang nghiên cứu Verkle trees như cấu trúc tương lai hiệu quả hơn.

Các hạn chế này không có nghĩa trie là xấu.

Chúng có nghĩa cấu trúc dữ liệu blockchain bao gồm đánh đổi giữa xác minh, lưu trữ, chi phí cập nhật, kích thước proof và tính phi tập trung.

Những hiểu lầm phổ biến về trie

Hiểu lầm đầu tiên là trie giống tree thông thường.

Trie là cấu trúc dữ liệu đường dẫn khóa, trong khi tree tổng quát có thể biểu diễn nhiều loại phân cấp.

Hiểu lầm thứ hai là trie tự động cung cấp bảo mật mật mã.

Trie cơ bản không cung cấp bảo mật proof nếu không kết hợp hashing hoặc phương thức cam kết khác.

Hiểu lầm thứ ba là state root trực tiếp lưu toàn bộ trạng thái.

State root chỉ là cam kết nhỏ gọn với trạng thái, không phải toàn bộ cơ sở dữ liệu.

Hiểu lầm thứ tư là Merkle proof chứng minh điều gì đó mãi mãi mà không cần bối cảnh.

Proof chỉ có ý nghĩa liên quan đến root đáng tin cậy cụ thể và quy tắc chain chính xác.

Hiểu lầm thứ năm là người dùng không bao giờ cần quan tâm đến trie.

Hầu hết người dùng không tương tác trực tiếp với trie, nhưng trie ảnh hưởng đến proof ví, xác thực block, bảo mật bridge và tính phi tập trung mạng.

Nhà phát triển nên nghĩ về trie như thế nào?

Nhà phát triển nên xem trie là một phần của hệ thống cam kết trạng thái blockchain.

Khi viết hợp đồng thông minh, họ tạo thay đổi trạng thái cuối cùng tác động đến trie roots.

Khi xây dựng ví hoặc indexer, họ có thể dựa vào dữ liệu đến từ trạng thái được hỗ trợ bởi trie.

Khi xây dựng bridge hoặc hệ thống proof, họ có thể cần xác minh trie proofs.

Khi tối ưu hóa hợp đồng, họ nên nhớ storage vĩnh viễn tạo chi phí trên toàn mạng.

Khi thiết kế giao thức, họ cần hiểu có cần membership proofs, non-membership proofs, historical proofs hoặc storage proofs hay không.

Nhu cầu proof này có thể ảnh hưởng lựa chọn cấu trúc dữ liệu.

Nhà phát triển không cần tự triển khai trie cho mọi dApp.

Tuy nhiên, hiểu trie giúp nhà phát triển tránh giả định sai về storage blockchain.

Nó cũng giúp họ hiểu vì sao quy tắc client cấp thấp quan trọng đến vậy.

Trader và người dùng nên nghĩ về trie như thế nào?

Trader và người dùng thông thường không cần tự tính trie roots.

Tuy nhiên, họ nên hiểu số dư blockchain và trạng thái hợp đồng không được lưu dưới dạng ảnh chụp đơn giản trong ví.

Chúng là một phần của trạng thái toàn cục có thể xác minh.

Khi giao dịch thay đổi số dư, thay đổi đó cập nhật các cam kết mật mã trong chain.

Đây là lý do hash giao dịch, số block và state root có thể được dùng để xác minh.

Với người dùng, bài học thực tế là tin vào xác minh on-chain hơn ảnh chụp màn hình hoặc tin nhắn.

Nếu khoản nạp bị thiếu, hash giao dịch và dữ liệu explorer rất quan trọng.

Nếu bridge tuyên bố xác minh chain khác, mô hình proof rất quan trọng.

Nếu ví hiển thị số dư, số dư cuối cùng phải có thể truy vết về trạng thái chain.

Trie giúp việc xác minh này diễn ra phía sau hệ thống.

FAQ

Trie trong crypto là gì?

Trie trong crypto là cấu trúc dữ liệu khóa-giá trị tổ chức dữ liệu theo đường dẫn khóa và thường kết hợp hashing mật mã để hỗ trợ xác minh.

Trie được phát âm như thế nào?

Trie thường được phát âm như “try”.

Vì sao Ethereum sử dụng trie?

Ethereum dùng modified Merkle Patricia tries để mã hóa và xác minh trạng thái, giao dịch, biên nhận và storage hợp đồng thông minh bằng root hashes mật mã.

Merkle Patricia trie là gì?

Merkle Patricia trie là cấu trúc dữ liệu kết hợp tra cứu trie, nén đường dẫn Patricia và Merkle hashing.

State trie là gì?

State trie là cấu trúc dữ liệu cam kết với trạng thái tài khoản và hợp đồng hiện tại của blockchain.

Storage trie là gì?

Storage trie là trie dành riêng cho hợp đồng, cam kết với các giá trị lưu trữ của một tài khoản hợp đồng thông minh.

Trie root là gì?

Trie root là hash cấp cao nhất tóm tắt toàn bộ dữ liệu lưu trong trie.

Điều gì xảy ra nếu một giá trị trong trie thay đổi?

Nếu một giá trị thay đổi, các hash trên đường dẫn của nó thay đổi và root cuối cùng cũng phải thay đổi.

Trie có giống Merkle tree không?

Không. Trie tổ chức dữ liệu theo đường dẫn khóa, còn Merkle tree tổ chức dữ liệu chủ yếu qua việc hash lặp lại các leaf.

Merkle proof là gì?

Merkle proof là tập dữ liệu chứng minh một giá trị thuộc cấu trúc dữ liệu lớn hơn đã được cam kết bằng root đã biết.

Vì sao trie quan trọng với light client?

Trie giúp light client xác minh dữ liệu cụ thể bằng proof thay vì tải xuống và lưu toàn bộ trạng thái blockchain.

Verkle trees là gì?

Verkle trees là nâng cấp cấu trúc dữ liệu trạng thái được đề xuất, có thể tạo witness nhỏ hơn các cấu trúc Merkle trie hiện tại.

Người dùng có tương tác trực tiếp với trie không?

Hầu hết người dùng không tương tác trực tiếp với trie, nhưng trie hỗ trợ cơ chế xác minh phía sau số dư, biên nhận, storage proofs và xác thực block.

Trie có không rủi ro không?

Không. Trie hỗ trợ tính toàn vẹn dữ liệu, nhưng không loại bỏ lỗi hợp đồng thông minh, sai sót ví, rủi ro bridge hoặc thiết kế ứng dụng kém.

Kết luận

Trie là cấu trúc dữ liệu đường dẫn khóa giúp hệ thống blockchain tổ chức và truy xuất dữ liệu khóa-giá trị.

Trong crypto, trie đặc biệt mạnh khi được kết hợp với hashing mật mã.

Sự kết hợp này tạo cấu trúc dữ liệu được xác thực, có thể cam kết với lượng dữ liệu blockchain rất lớn bằng root hashes nhỏ gọn.

Modified Merkle Patricia trie của Ethereum là ví dụ nổi tiếng nhất vì hỗ trợ state roots, storage roots, transaction roots, receipt roots và Merkle proofs.

Trie giúp các node độc lập xác minh chúng đã đạt cùng trạng thái sau khi xử lý block.

Chúng cũng giúp chứng minh dữ liệu tài khoản, giao dịch, biên nhận hoặc storage cụ thể thuộc root blockchain đã biết.

Tuy nhiên, trie cũng có các đánh đổi, gồm độ phức tạp triển khai, áp lực lưu trữ, chi phí cập nhật và witness lớn.

Các đánh đổi này là một lý do Ethereum đang nghiên cứu Verkle trees để có witness nhỏ hơn và hỗ trợ stateless client tốt hơn.

Với nhà phát triển, trie giải thích vì sao storage hợp đồng thông minh và thiết kế proof cần được cân nhắc kỹ.

Với người dùng, trie giải thích vì sao dữ liệu blockchain có thể được xác minh thay vì chỉ được tin tưởng.

Trong thuật ngữ crypto, Trie nên được hiểu là cấu trúc dữ liệu nền tảng đằng sau trạng thái blockchain, proof mật mã, xác minh node và tương lai của các mạng phi tập trung có khả năng mở rộng.