Trie

什麼是 Trie？

Trie 是一種樹狀資料結構，透過逐步沿著金鑰的各個部分查找，用於儲存及擷取鍵值資料。

在加密貨幣領域中，Trie 相當重要，因為區塊鏈需要可靠的方法來組織帳戶、餘額、智能合約儲存空間、交易及證明。

Trie 一詞源自 retrieval，通常發音與英文「try」相同。

一般資料庫可能直接儲存金鑰與值，但 Trie 會將金鑰拆分成較小部分，並將這些部分放置於一條路徑上。

路徑中的每個步驟都會縮小搜尋範圍，直到系統找到與完整金鑰連結的值。

這使 Trie 適合用於必須多次搜尋、更新及驗證的資料。

在區塊鏈系統中，Trie 常與密碼學雜湊結合，形成經驗證的資料結構。

經驗證的資料結構可讓使用者驗證特定資料屬於較大的資料集，而無須下載該資料集中的每一筆資料。

這也是 Trie 對節點、錢包、區塊鏈瀏覽器、輕量客戶端、智能合約及區塊鏈擴容研究很重要的原因。

最著名的加密貨幣案例是 Ethereum 經修改的 Merkle Patricia trie，其用於執行層，以確定性且可透過密碼學驗證的方式組織鍵值資料。

Trie 為何在加密貨幣中重要

Trie 在加密貨幣中很重要，因為區塊鏈必須讓許多獨立電腦對相同狀態達成共識。

狀態是指區塊鏈目前的情況，包括帳戶餘額、智能合約程式碼、儲存值及其他帳本資料。

若兩個節點處理相同區塊，最終應得到相同的狀態根。

狀態根是完整狀態的精簡密碼學摘要。

即使只有一個帳戶餘額或儲存值遭到錯誤變更，產生的根也應改變。

這讓節點可比較一個小型根值，而非手動比較整個資料庫。

Ethereum.org 在其 Merkle Patricia Trie 文件中說明，Merkle Patricia trie 具確定性且可透過密碼學驗證；任何以不同值修改狀態的嘗試，都會產生不同的狀態根雜湊值。

此特性對區塊鏈共識至關重要，因為驗證者與節點需要共同的方法，以判斷區塊生產者是否計算出正確結果。

若沒有經驗證的 Trie 或類似結構，驗證龐大區塊鏈狀態將更加困難且效率較低。

基本 Trie 如何運作

基本 Trie 會透過將金鑰拆分為較小符號來儲存資料。

例如，以單字為基礎的 Trie 可儲存「cat」、「car」及「cap」，方式是共用前兩個字母「ca」，再於最後一個字母分叉。

當許多金鑰以相同內容開頭時，這種共用前綴結構可減少重複儲存。

在加密貨幣系統中，金鑰通常不是簡單的英文單字。

它們可能是地址、經雜湊處理的儲存槽、交易索引或編碼值。

Trie 會逐段追蹤金鑰，直到找到對應值。

若金鑰不存在，路徑會在到達有效值之前失敗。

理論上，此結構可支援快速查詢、插入及刪除。

不過，若金鑰很長且許多路徑僅包含一個子節點，普通 Trie 可能效率不佳。

因此，區塊鏈系統常使用 Patricia trie 與 Merkle Patricia trie 等最佳化 Trie 形式。

Trie 與 Tree 的差異

Trie 是 Tree 的一種，但其設計以金鑰與前綴為核心。

一般 Tree 可能依比較、階層或父子關係組織值。

Trie 則透過走訪金鑰的符號來組織值。

這使 Trie 特別適合許多金鑰共用前綴的情況。

在區塊鏈中，金鑰可能是很長的位元組字串，因此簡單 Tree 不一定理想。

Trie 可讓通往某個值的路徑直接取決於金鑰本身。

當節點需要確定性行為時，這相當有用。

確定性行為是指每個誠實節點在取得相同輸入時，都會得出相同結果。

在加密貨幣中，確定性資料結構相當重要，因為網路不能依賴中央資料庫伺服器決定答案。

每個全節點都應能從相同資料計算出相同根。

Trie 與 Merkle Tree 的差異

Trie 透過金鑰路徑組織資料，而 Merkle Tree 則透過對葉節點進行雜湊，直到只剩下一個根雜湊值來組織資料。

Merkle Tree 很有用，因為它可對一組資料建立密碼學承諾。

Merkle 證明可證明某筆資料屬於已承諾的資料集，無須揭露或下載整個資料集。

Trie 很有用，因為它支援有效率的鍵值查詢。

Merkle Patricia trie 結合了這些概念。

它使用類 Trie 的金鑰路徑進行查詢，並使用 Merkle 風格雜湊進行驗證。

這個組合非常強大，因為區塊鏈節點同時需要資料庫存取與密碼學證明。

一般 Trie 可以找到值，但不會自動證明這些值屬於可信狀態根。

一般 Merkle Tree 可以證明成員關係，但不一定是為高效率鍵值更新而設計。

Merkle Patricia trie 為 Ethereum 風格系統提供管理持續變動狀態的方式，同時保有可驗證的根承諾。

什麼是 Patricia Trie？

Patricia trie 是一種最佳化 Trie，在沒有分叉的長路徑區段中進行路徑壓縮。

PATRICIA 是 Practical Algorithm To Retrieve Information Coded in Alphanumeric 的縮寫。

其目標是避免將空間浪費在僅指向下一個節點的節點上。

在一般 Trie 中，即使沿途沒有有意義的分叉，長金鑰仍可能需要許多步驟。

Patricia trie 可更精簡地儲存共用途徑區段。

這對區塊鏈金鑰相當有用，因為地址與雜湊值可能很長。

Ethereum.org 在其 Patricia Merkle trie 指南中說明，Ethereum 的資料結構借用了 PATRICIA 的特性，因其旨在有效擷取構成 Ethereum 狀態的項目。

路徑壓縮有助於減少必須走訪、儲存及證明的節點數量。

這很重要，因為區塊鏈狀態可能包含數百萬個帳戶，以及更多儲存項目。

更小且更有效率的結構，有助於節點以較少負擔處理狀態變更。

什麼是 Merkle Patricia Trie？

Merkle Patricia trie 是一種經驗證的鍵值資料結構，結合 Merkle 雜湊、Trie 查詢及 Patricia 路徑壓縮。

它有時簡稱為 MPT。

Ethereum 對重要執行層資料採用經修改的 Merkle Patricia trie。

官方 Ethereum 資料結構文件指出，Patricia Merkle tries 可將鍵值對編碼為具確定性且經密碼學驗證的 Trie。

在 Ethereum 中，MPT 讓網路可透過單一根雜湊值對龐大的狀態資料庫做出承諾。

根雜湊值儲存在區塊資料中，猶如執行交易後狀態的指紋。

若節點計算出的狀態根與區塊提議者不同，節點便知道出現問題。

這是 MPT 對 Ethereum 執行模型至關重要的原因之一。

它們有助於連接本地資料庫更新與全域共識。

它們也支援 Merkle 證明，可針對已知根證明帳戶或儲存資料。

Ethereum 中的修改版 Merkle Patricia Trie

Ethereum 的版本常被稱為修改版 Merkle Patricia trie。

Ethereum Yellow Paper 在其 Ethereum Yellow Paper中指出，Ethereum 會在經修改的 Merkle Patricia tree 中維護世界狀態映射，而根節點雜湊值可作為整個系統狀態的安全識別碼。

這表示 Trie 根會對完整帳戶狀態集做出承諾。

帳戶狀態包括 nonce、餘額、儲存根及程式碼雜湊值等資料。

智能合約儲存空間也透過 Trie 結構組織。

當交易變更餘額或合約儲存值時，相關 Trie 路徑會改變。

此變更會一路影響父節點雜湊值直到根節點。

最終狀態根便反映更新後的區塊鏈狀態。

這正是小型雜湊值可代表大量持續變動狀態資料的方式。

修改版 MPT 是 Ethereum 節點能夠獨立驗證區塊執行是否正確的原因之一。

Merkle Patricia Trie 中的節點

Merkle Patricia trie 使用多種類型的節點。

Ethereum.org 在其 MPT 文件中列出空節點、分支節點、葉節點及擴充節點。

空節點代表空值。

分支節點可指向多個可能的後續路徑。

葉節點儲存最終編碼路徑與值。

擴充節點儲存共用途徑區段，並指向另一個節點。

這些節點類型讓 Trie 能有效率地儲存稀疏鍵值資料。

稀疏結構是指可能存在許多金鑰，但實際上只有部分金鑰具有值。

Ethereum 金鑰通常以半位元組（nibble）表示，每個 nibble 為半個位元組。

使用 nibble 讓 Trie 在每個分支節點最多有 16 種路徑選擇。

此設計讓 Trie 能以可預測的方式走訪十六進位金鑰路徑。

State Trie

State trie 是對 Ethereum 世界狀態做出承諾的 Trie。

世界狀態包含所有帳戶及其帳戶資料。

每個帳戶可以是由私鑰控制的外部帳戶，或由程式碼控制的合約帳戶。

State trie 將帳戶地址映射至編碼後的帳戶資料。

狀態根是在處理完一個區塊交易後，該 Trie 的根雜湊值。

驗證者驗證區塊時，會重新執行交易並計算產生的狀態根。

Ethereum.org 的 Verkle trees 路線圖頁面說明，經驗證的區塊是指其計算出的狀態根雜湊值與區塊提議者提供的根相符。

這使 State trie 成為區塊驗證的核心。

它不只是隱藏於客戶端軟體中的儲存細節。

它是 Ethereum 證明狀態轉換有效方式的一部分。

Storage Trie

Storage trie 用於儲存特定帳戶的智能合約儲存資料。

每個智能合約帳戶都有一個儲存根，指向其專屬的 Storage trie。

此 Storage trie 將儲存金鑰映射至儲存值。

例如，代幣合約可在儲存空間中保存餘額、授權額度、供應資料及設定值。

這些值各自都可透過儲存槽表示。

使用者轉移代幣時，合約儲存資料可能因餘額更新而變更。

該儲存變更會更新合約的 Storage trie 根。

State trie 中的帳戶資料接著也會變更，因為帳戶的儲存根已改變。

這會從單一儲存槽到整體狀態根，建立一連串密碼學承諾。

這條鏈使儲存證明成為可能。

Transaction Trie

Transaction trie 對納入區塊的交易做出承諾。

每個區塊都有交易根，用以摘要該區塊中的交易。

這讓節點與客戶端可根據區塊資料驗證交易是否被納入。

Transaction tries 與 State trie 不同，因為它們描述的是區塊內容，而非目前帳戶狀態。

State trie 會隨交易更新帳戶與合約而變化。

Transaction trie 則記錄哪些交易被納入特定區塊。

此區別很重要，因為交易是否被納入與其狀態影響雖有關聯，卻不完全相同。

交易可能被納入區塊，卻仍在執行時失敗。

Transaction trie 可證明納入情況，而 Receipt trie 可顯示執行結果細節。

查詢交易的使用者應了解，納入區塊只是完整交易過程的一部分。

Receipt Trie

Receipt trie 對區塊中的交易收據做出承諾。

收據會記錄交易執行結果。

依鏈規則及客戶端顯示方式而定，收據可能包含狀態、Gas 用量、日誌及事件相關資料。

收據對錢包、區塊鏈瀏覽器、索引器及去中心化應用程式相當重要。

例如，代幣轉帳事件通常會從交易日誌中讀取。

Receipt trie 有助於將這些結果納入區塊資料的承諾中。

這讓客戶端可驗證特定收據屬於某個區塊。

對開發者而言，在建置跨鏈訊息、跨鏈橋、分析工具或以證明為基礎的應用程式時，收據證明可能很重要。

對使用者而言，Receipt trie 通常不可見。

不過，它有助於支援使用者查詢交易成功或失敗時依賴的瀏覽器資料。

Trie Root

Trie root 是摘要 Trie 中所有資料的頂層雜湊值。

若 Trie 內任何值改變，根也應改變。

這使根成為對完整資料集的精簡承諾。

在 Ethereum 中，區塊標頭包含用於摘要重要資料結構的根。

狀態根摘要區塊後的狀態。

交易根摘要區塊中的交易。

收據根摘要區塊的交易收據。

這些根可協助獨立節點對發生的事件達成共識，而不必信任中央伺服器。

錯誤的根表示節點的計算或區塊提議者的資料，與預期結果不符。

在加密貨幣中，這是雜湊如何將原始資料轉化為可驗證共識的實際方式之一。

Merkle 證明與 Trie

Merkle 證明是一組資料，可證明某個值被包含於較大的已承諾資料結構中。

在 Trie 中，證明通常包含從根到被證明值之路徑上的節點。

驗證者可逐步雜湊證明資料，並將結果與已知根比較。

若計算出的根與可信根相符，則在雜湊假設下，該證明有效。

這讓輕量客戶端或智能合約無須儲存完整狀態，即可驗證特定值。

例如，證明可顯示某帳戶在已知狀態根下具有特定餘額。

證明也可顯示智能合約儲存槽具有特定值。

儲存證明對跨鏈橋、跨鏈應用程式、Rollup 及歷史狀態驗證很有用。

不過，證明生成與驗證可能相當複雜，因為精確的 Trie 格式、編碼及根必須符合鏈規則。

證明只有在驗證者信任其檢查對象根的情況下才有意義。

Trie 與輕量客戶端

輕量客戶端是指不會儲存或處理全節點所儲存與處理全部資料的區塊鏈客戶端。

它們依賴精簡證明、區塊標頭及可信的密碼學承諾。

Trie 有助於輕量客戶端，因為根雜湊值可對龐大狀態做出承諾。

輕量客戶端可根據已知根驗證小型證明，而無須下載整個資料庫。

這對無法運行全節點的行動錢包、嵌入式裝置、瀏覽器及應用程式相當重要。

不過，目前的 Merkle Patricia trie 證明在部分使用情境中可能很大。

Ethereum.org 在其 Verkle trees 文件中說明，目前的 Merkle trie witness 過大，無法有效支援無狀態客戶端。

這也是 Ethereum 研究人員研究 Verkle trees 與其他狀態承諾改善方案的原因。

目標是在不削弱安全性的前提下，讓驗證更加輕量。

因此，Trie 不僅對目前節點很重要，對未來區塊鏈擴容設計也同樣重要。

Trie 與無狀態客戶端

無狀態客戶端是可在不於本地儲存完整目前狀態的情況下驗證區塊的客戶端。

客戶端不保留完整狀態資料庫，而是隨區塊接收一個 witness。

witness 包含驗證區塊狀態轉換所需的狀態片段與證明資料。

Ethereum.org 在其 無狀態客戶端與 Verkle tree 路線圖中說明，無狀態客戶端使用狀態資料的 witness，而非持有整個狀態資料庫的本地副本。

挑戰在於，基於目前 Merkle trie 結構的 witness 可能過大。

大型 witness 是問題，因為它們必須快速在點對點網路中傳播。

若只有具備強大頻寬的高效能機器能夠跟上，網路就會更加中心化。

更好的 Trie 或 Tree 結構可減少 witness 大小，並讓更多使用者更容易進行驗證。

這也是資料結構設計與去中心化直接相關的原因。

看似底層技術細節的資料結構，可能影響哪些人能夠運行節點。

Trie 與 Verkle Trees

Verkle trees 是 Ethereum 狀態資料結構的擬議升級方向。

Verkle tree 的用途與 Merkle Tree 類似，但使用向量承諾以支援更小的 witness。

Ethereum.org 在官方 Verkle trees 路線圖中說明，Verkle trees 可協助節點停止儲存大量狀態資料，同時不失去驗證區塊的能力。

這很重要，因為 Ethereum 目前的 State trie 很大，且不利於輕量驗證。

Verkle trees 的設計目標是讓 witness 更小，並更適合無狀態客戶端。

它們與 Merkle Patricia tries 並不相同。

它們是著眼於未來、用以改善狀態存取與驗證的工作之一。

對詞彙讀者而言，重點在於 Trie 並非已完全解決且不再改變的議題。

區塊鏈資料結構持續演進，因為網路需要更好的可擴展性、更低的硬體需求及更高的證明效率。

了解 Trie 有助於理解為何 Verkle trees 正在被研究。

Trie 與 Gas 成本

Trie 操作可能影響區塊鏈效能與交易成本。

交易讀取或寫入狀態時，客戶端可能需要存取及更新與 Trie 相關的資料。

智能合約儲存寫入成本較高，部分原因是它們會變更持久狀態。

變更持久狀態比執行暫時運算成本更高，因為結果必須由網路儲存及驗證。

代幣轉帳可能更新合約儲存空間中的餘額。

DeFi 交易可能跨多個合約更新許多儲存槽。

每次更新都可能增加狀態成長及 Trie 維護工作。

這也是區塊鏈開發者重視儲存最佳化的原因之一。

撰寫高效率智能合約不只是為使用者節省手續費。

同時也是為了降低網路的長期狀態壓力。

Trie 與智能合約儲存空間

智能合約儲存空間是 Trie 對開發者最重要的應用之一。

當合約永久儲存資料時，該資料會成為區塊鏈狀態的一部分。

合約的儲存根會對合約的 Storage trie 做出承諾。

每個儲存變數最終都會透過儲存槽表示。

映射與陣列等複雜 Solidity 資料類型，會依編譯器規則編碼至儲存槽。

使用者與合約互動時，這些儲存槽可能被讀取或變更。

開發者應了解，儲存空間不只是程式設計上的便利功能。

它是經密碼學承諾的全域資料庫的一部分。

不佳的儲存設計可能提高 Gas 費、使證明更大，並形成升級風險。

良好的儲存設計可讓合約成本更低、更清晰且更容易稽核。

Trie 與區塊鏈瀏覽器

區塊鏈瀏覽器依賴區塊鏈資料結構、索引及客戶端資料，向使用者顯示易讀資訊。

使用者可搜尋地址並查看餘額、代幣轉帳、合約呼叫及交易歷史。

在介面背後，區塊鏈本身以更技術性的形式儲存狀態與區塊資料。

Trie 有助於對這些資料做出承諾，而瀏覽器則將資料建立索引並顯示。

使用者應了解，瀏覽器是讀取工具，本身不是唯一的真相來源。

真相來源是由節點驗證並透過根做出承諾的區塊鏈資料。

若瀏覽器延遲或發生索引錯誤，底層鏈可能仍是正確的。

這也是開發者與進階使用者常透過節點、證明或多個來源驗證資料的原因。

Trie 根為區塊鏈提供了瀏覽器可建立於其上的密碼學骨幹。

瀏覽器使資料可供人類閱讀，而 Trie 有助於使資料可驗證。

Trie 與 Rollups

Rollup 可能使用自己的狀態 Tree 或 Trie 來追蹤鏈下或 Layer 2 狀態。

Rollup 需要一種方式對目前狀態做出承諾，並證明狀態轉換有效。

部分 Rollup 使用零知識證明、詐欺證明、Merkle 證明或其他承諾結構。

即使精確資料結構不是 Ethereum 的 MPT，相同的基本概念通常仍會出現。

系統會使用精簡根，對龐大狀態做出承諾。

使用者或合約可針對該根驗證主張。

這也是學習 Trie 有助於理解 Rollup 架構的原因。

Rollup 不只是關於更便宜的交易。

它們也關於狀態承諾、證明生成、資料可用性及驗證。

類 Trie 結構是使這些系統得以實現的基礎之一。

Trie 與跨鏈橋

跨鏈橋有時使用證明驗證另一條鏈的事件、餘額、訊息或儲存值。

跨鏈橋可能需要證明交易已發生，或某個儲存值已變更。

當目標鏈或驗證者知道來源鏈的可信根時，Trie 證明可協助驗證此類主張。

不過，跨鏈橋安全性遠不只取決於 Trie 證明本身。

它還可能取決於驗證者集合、轉送者、輕量客戶端邏輯、最終性假設、智能合約安全性及升級控制。

即使證明正確，若可信根來自薄弱或已遭入侵的來源，仍可能不安全。

因此，使用者不應假設「證明」一詞會讓跨鏈橋沒有風險。

證明必須與安全的驗證模型連結。

Trie 為資料納入提供強大工具，但跨鏈橋設計仍必須處理許多額外風險。

良好的跨鏈橋分析會檢視從來源鏈狀態到目標鏈操作的完整信任路徑。

Trie 與安全性

Trie 透過讓資料竄改更容易被偵測來提升安全性。

若有人變更儲存值，路徑上的雜湊值應隨之改變。

該變更應導致不同的根。

比較計算根與預期根的節點可偵測不一致情況。

這是密碼學完整性的關鍵部分。

不過，Trie 本身並非完整安全解決方案。

Trie 無法阻止使用者簽署惡意交易。

Trie 無法修復智能合約漏洞。

Trie 無法讓錯誤的預言機價格變正確。

若跨鏈橋信任錯誤根，Trie 無法保護資金。

Trie 有助於證明資料完整性，但應用程式安全性仍需要安全程式碼、良好金鑰管理、稽核及穩健協議設計。

Trie 在區塊鏈系統中的優點

Trie 的第一項優點是有組織的鍵值儲存。

第二項優點是確定性查詢，有助於獨立節點得出相同結果。

第三項優點是採用 Patricia 風格最佳化時的共用前綴壓縮。

第四項優點是 Trie 與 Merkle 雜湊結合時提供的密碼學驗證。

第五項優點是證明支援，可讓使用者針對根驗證特定資料。

第六項優點是狀態承諾，有助於區塊鏈以小型雜湊值摘要龐大資料庫。

第七項優點是與輕量客戶端及無狀態客戶端研究的相容性。

這些優點說明了為何 Trie 會出現在嚴謹的區塊鏈協議設計中。

它們不只是抽象的電腦科學概念。

它們協助真實網路儲存、驗證及更新金融資料。

Trie 的限制

Trie 可能難以正確實作。

編碼規則必須完全遵守，否則根將不會相符。

當需要許多路徑或同層節點時，證明可能變得很大。

狀態成長可能讓節點的底層資料庫負擔沉重。

更新狀態可能需要大量資料庫讀取與寫入。

不同客戶端實作必須遵循相同 Trie 規則。

若節點需要提供舊證明，歷史狀態可能需要額外儲存空間。

Merkle Patricia trie witness 的大小，使 Ethereum 正在研究 Verkle trees 作為更有效率的未來結構。

這些限制並不代表 Trie 不好。

它們表示區塊鏈資料結構涉及驗證、儲存、更新成本、證明大小及去中心化之間的取捨。

關於 Trie 的常見誤解

第一項誤解是 Trie 與一般 Tree 相同。

Trie 是金鑰路徑資料結構，而一般 Tree 可以表示多種階層關係。

第二項誤解是 Trie 會自動提供密碼學安全性。

基本 Trie 除非結合雜湊或其他承諾方法，否則不會提供證明安全性。

第三項誤解是狀態根直接儲存完整狀態。

狀態根只是對狀態的精簡承諾，而非完整資料庫本身。

第四項誤解是 Merkle 證明在沒有背景下可永遠證明某事。

證明只有相對於特定可信根及正確鏈規則才有意義。

第五項誤解是使用者永遠不需要關心 Trie。

大多數使用者不會直接與 Trie 互動，但 Trie 會影響錢包證明、區塊驗證、跨鏈橋安全及網路去中心化。

開發者應如何看待 Trie

開發者應將 Trie 視為區塊鏈狀態承諾系統的一部分。

撰寫智能合約時，開發者會建立最終影響 Trie 根的狀態變更。

建置錢包或索引器時，開發者可能依賴來自 Trie 支援狀態的資料。

建置跨鏈橋或證明系統時，開發者可能需要驗證 Trie 證明。

最佳化合約時，開發者應記得持久儲存具有全網路成本。

設計協議時，開發者應了解是否需要成員證明、非成員證明、歷史證明或儲存證明。

這些證明需求可能影響資料結構的選擇。

開發者不需要為每個 dApp 手動實作 Trie。

不過，了解 Trie 有助於開發者避免對區塊鏈儲存產生錯誤假設。

這也有助於他們理解為何底層客戶端規則如此重要。

交易者與使用者應如何看待 Trie

交易者與一般使用者不需要手動計算 Trie 根。

不過，他們應了解，區塊鏈餘額與合約狀態並非像錢包中的簡單螢幕截圖一樣儲存。

它們是可驗證全域狀態的一部分。

交易改變餘額時，該變更會更新鏈內的密碼學承諾。

這也是交易雜湊值、區塊編號及狀態根可用於驗證的原因。

對使用者而言，實際的教訓是應更信任鏈上驗證，而非螢幕截圖或訊息。

若入金未顯示，交易雜湊值與瀏覽器資料很重要。

若跨鏈橋聲稱可驗證另一條鏈，證明模型就很重要。

若錢包聲稱有某個餘額，該餘額最終應可追溯至鏈上狀態。

Trie 在幕後協助實現這種驗證。

常見問題

加密貨幣中的 Trie 是什麼？

加密貨幣中的 Trie 是一種鍵值資料結構，透過金鑰路徑組織資料，並常與密碼學雜湊結合以支援驗證。

Trie 怎麼發音？

Trie 通常發音與英文「try」相同。

為何 Ethereum 使用 Trie？

Ethereum 使用修改版 Merkle Patricia tries，透過密碼學根雜湊值編碼及驗證狀態、交易、收據及智能合約儲存資料。

什麼是 Merkle Patricia trie？

Merkle Patricia trie 是一種結合 Trie 查詢、Patricia 路徑壓縮及 Merkle 雜湊的資料結構。

什麼是 State trie？

State trie 是對區塊鏈目前帳戶與合約狀態做出承諾的資料結構。

什麼是 Storage trie？

Storage trie 是針對特定合約的 Trie，會對智能合約帳戶的儲存值做出承諾。

什麼是 Trie root？

Trie root 是摘要 Trie 中所有資料的頂層雜湊值。

若 Trie 中的一個值改變，會發生什麼事？

若一個值改變，路徑上的雜湊值會改變，最終根也應改變。

Trie 與 Merkle Tree 相同嗎？

不同。Trie 透過金鑰路徑組織資料，而 Merkle Tree 主要透過重複雜湊葉節點來組織資料。

什麼是 Merkle 證明？

Merkle 證明是一組資料，可證明某個值屬於由已知根承諾的較大資料結構。

為何 Trie 對輕量客戶端很重要？

Trie 可讓輕量客戶端使用證明驗證特定資料，而不必下載及儲存完整區塊鏈狀態。

什麼是 Verkle trees？

Verkle trees 是一種擬議的狀態資料結構升級，可建立比目前 Merkle trie 結構更小的 witness。

使用者會直接與 Trie 互動嗎？

大多數使用者不會直接與 Trie 互動，但 Trie 支援餘額、收據、儲存證明及區塊驗證背後的驗證機制。

Trie 沒有風險嗎？

不是。Trie 有助於資料完整性，但不會消除智能合約漏洞、錢包錯誤、跨鏈橋風險或不佳應用程式設計。

結論

Trie 是一種金鑰路徑資料結構，可協助區塊鏈系統組織及擷取鍵值資料。

在加密貨幣中，Trie 與密碼學雜湊結合時尤其強大。

此組合會建立經驗證的資料結構，可利用精簡根雜湊值對大量區塊鏈資料做出承諾。

Ethereum 的修改版 Merkle Patricia trie 是最知名的例子，因其支援狀態根、儲存根、交易根、收據根及 Merkle 證明。

Trie 有助於獨立節點驗證其處理區塊後是否到達相同狀態。

它們也讓人們可證明特定帳戶、交易、收據或儲存資料屬於已知區塊鏈根。

不過，Trie 也存在取捨，包括實作複雜性、儲存壓力、更新成本及大型 witness。

這些取捨是 Ethereum 研究 Verkle trees 以建立更小 witness 並更好支援無狀態客戶端的原因之一。

對開發者而言，Trie 說明了為何智能合約儲存與證明設計需要審慎思考。

對使用者而言，Trie 說明了為何區塊鏈資料可以被驗證，而非僅能被信任。

在加密貨幣詞彙中，Trie 應理解為支撐區塊鏈狀態、密碼學證明、節點驗證及可擴展去中心化網路未來的基礎資料結構。