Patricia Tries (Practical Algorithm to Retrieve Information Coded in Alphanumeric) are radix trees optimized for blockchain state storage, serving as the fundamental data structure in Substrate's state management system [114]. These compressed trie structures store key-value pairs efficiently, with path compression reducing storage overhead while maintaining fast lookup times of O(k) where k is the key length. Patricia Tries enable efficient state queries and provide cryptographic commitments to the entire state through their root hash. Within the [[ZKP/Introduction/ZKP Ecosystem/Architecture|ZKP ecosystem,]] Patricia Tries are utilized in Substrate's runtime to manage the blockchain's dynamic state, including [[ZKP/ZKP Base Layer/ZKP Blockchain/Technical Build Consensus Layer/Synchronization of PoI and PoSp in Consensus Rounds/PoI Scoring|PoI scores]], [[ZKP/ZKP Base Layer/ZKP Blockchain/Technical Build Consensus Layer/Synchronization of PoI and PoSp in Consensus Rounds/Staking Power|staking power]], and [[ZKP/ZKP Base Layer/ZKP Blockchain/Technical Build Consensus Layer/Synchronization of PoI and PoSp in Consensus Rounds/PoSp Scoring|PoSp commitments]] [107, 108]. For example, when a node submits an AI task result for PoI, the state update is recorded in the Patricia Trie, and a [[ZKP/ZKP Base Layer/Core Concepts/Merkle Trees|Merkle proof]] can validate this contribution across the network. This ensures transparency and auditability, reinforcing the reliability of the hybrid consensus model in supporting decentralized AI compute. The trie's structure enables efficient state queries and historical state access, crucial for ZKP verification and data marketplace operations. ![[Diagram6 1.png]] See also: [[Substrate]]