Kairos: Efficient Merkle Trie for ZK VMs | by Avi Dessauer | Casper Association R & D | Sep, 2024 | Medium

This blog post is a deep dive into kairos-trie, a Rust trie store specially conceived for ZK environments. Following an overview of the motivation for and usage of kairos-trie, we will touch on the implementation details. Merkle trees are a fundamental component in blockchains, enabling efficient verification of large datasets. The most common form of merkle tree used in both Casper and Ethereum is the merkle trie. A trie is a tree data structure where the path from root to each node is a prefix of the keys under that node. A trie provides ordering over keys, like a BTree, but unlike a BTree it has no balancing operation. To balance a trie the keys must be hashed, such that keys are uniformly distributed across the trie. Zero-knowledge layer 2 (ZK L2) solutions, like their L1 counterparts, require verifiable access to specific portions of the massive data structure representing the chain state. However, Zero-knowledge L2s operate in a fundamentally different environment. Instead of run

This blog post is a deep dive into kairos-trie, a Rust trie store specially conceived for ZK environments. Following an overview of the motivation for and usage of kairos-trie, we will touch on the implementation details. Merkle trees are a fundamental component in blockchains, enabling efficient verification of large datasets. The most common form of merkle tree used in both Casper and Ethereum is the merkle trie. A trie is a tree data structure where the path from root to each node is a prefix of the keys under that node. A trie provides ordering over keys, like a BTree, but unlike a BTree i