The Technical Director at the Cardano Foundation, Matthias Benkort (also known as @KtorZ), has successfully encapsulated the entire Bitcoin blockchain within a single block on the Cardano blockchain. This announcement, made via X (formerly Twitter), has sent ripples through the blockchain community, highlighting the potential for advanced data management and interoperability between blockchains.
A Breakthrough For Cardano And Blockchain Technology
Benkort’s revelation came with the release of a new open-source library on GitHub, titled “Merkle Patricia Forestry.” The library introduces a set of both on-chain and off-chain tools designed to work with Merkle Patricia Tries on Cardano. As described in the release documentation, a Merkle Patricia Trie is “a persistent & authenticated data structure to map between arbitrary keys and values.” Essentially, it functions as a highly efficient and secure hashmap.
The documentation elaborates on the structure, stating, “Items are represented in a space-optimized trie (a.k.a prefix tree) of radix 16. The hash digest of their keys provides the path to values in the trie.” This approach offers numerous use cases, such as maintaining large on-chain registries (e.g., domains), or providing vast oracled datasets of intrinsic data (e.g., a map of delegators/delegatees) or extrinsic data (e.g., GitHub data related to an ecosystem of projects). It is particularly well-suited for long-running datasets that grow at a slow rate, such as a Proof-of-Work (PoW) blockchain.
Key features of the Merkle Patricia Forestry library include rapid membership, insertion, and deletion of any key/value item in a large store, facilitated by a root hash digest (32 bytes) and a succinct proof (<1KB). The library incorporates several optimizations inspired by Ethereum’s Modified Merkle Patricia Trie (MPT), but introduces a novel approach for organizing nodes as tiny Sparse Merkle Trees. This innovation results in much smaller proof sizes and is the basis for the library’s name: Merkle Patricia Forestry.
Benkort explained the performance trade-offs, noting that the optimization sacrifices some memory and CPU execution units to achieve smaller proof sizes. Despite this, the library strikes a good balance between proof size, memory usage, and CPU efficiency, as detailed in the performance tables included in the documentation. These tables summarize the proof size, memory units, and CPU units required for various trie sizes, highlighting the efficiency of the library in different scenarios.
Detailed Explanation And Demonstration
In a series of detailed posts on X, Cardano Foundation’s Benkort provided further insights into the implementation and capabilities of the library. He explained that the library consists of two parts: one implemented in Aiken for specific utilities to smart contracts, and another in Node.js for off-chain operations. This comprehensive implementation of modified Merkle Patricia Tries, with a unique twist, is what Benkort calls ‘Merkle Patricia Forestry.’
“Fundamentally, this is an authenticated data structure for mapping arbitrary keys to arbitrary values,” Benkort stated. “Yet, it is done in such a way that it is possible to perform some operations from only a small hash and a succinct proof, without the need to carry the entire data structure.”
For those familiar with blockchain technology, Merkle Trees are a similar, albeit simpler structure, primarily used for representing lists of items and verifying their membership using a root hash. However, Merkle Patricia Tries (MPTs) extend this functionality, allowing not only membership verification but also the insertion and deletion of key/value pairs. Ethereum employs MPTs for its blockchain state and transaction storage, enabling light clients to query balances without storing the entire blockchain.
One significant issue with traditional MPTs is the large size of proofs, which can span multiple kilobytes for extensive data stores. This isn’t as problematic for off-chain operations, but on-chain, every byte is precious. Benkort’s implementation addresses this by using tiny Sparse Merkle Trees of 16 items at each level, effectively creating trees within tries. This structure drastically reduces the size of proofs, trading off some computational steps for Cardano’s efficiency gains.
Benkort demonstrated this capability through a recent transaction that spent a UTxO containing the root hash of a Merkle Patricia Forestry representing the entire Bitcoin block header hashes, compressed into just 32 bytes. The transaction proved the ability to continue the chain by inserting a new block into the trie, maintaining an authenticated chain of over 850,000 blocks with minimal data overhead.
“The transaction I just linked is doing something quite unexpected,” Benkort explained. “It spends a UTxO that contains the root hash of a Merkle Patricia Forestry representing the entire Bitcoin block header hashes, mapped to their transactions. That’s about 850,000 blocks, compressed in 32 bytes.”
To spend this UTxO, a proof must be provided on-chain to show the continuation of the chain by inserting a new block in the trie. The updated root hash stored on-chain must represent the previous chain plus one block. The entire validator for this operation fits into just 26 lines of Cardano’s Aiken.
Future Implications And Use Cases
Benkort highlighted the potential applications of this technology, ranging from trustless bridges to arbitrarily large key/value stores managed fully on-chain. “Imagine the realm of possibilities with such large datasets,” he suggested. “A domains registry? A feed of financial market data? GitHub stats? I do see a world where institutions or committees publish large datasets in the form of a simple root hash on-chain, effectively serving as oracles for a variety of smart contracts down the line.”
Benkort concluded by reflecting on the journey of this project, which began as a side project at the end of last year. “It feels good to finally release this,” he said. “It was originally something I started at the end of last year, a bit as a side project. Given the many conversations about this lately, I thought I’d resurrect and properly package that code. Open sourcing for the win.”
At press time, Cardano (ADA) traded at $0.455.
Featured image created with DALL·E, chart from TradingView.com
