News
Cardano Tech Lead encloses the Bitcoin chain in a single block
The Technical Director of the Cardano Foundation, Matthias Benkort (also known as @KtorZ), has successfully encapsulated the entire Bitcoin blockchain into a single block on the Cardano blockchain. This announcementmade via X (formerly Twitter), has caused a stir in the blockchain community, highlighting the potential for advanced data management and interoperability between blockchains.
A turning point 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 for mapping arbitrary keys and values.” Essentially, it works as a highly efficient and secure hashmap.
The documentation elaborates on the structure, stating: “The elements are represented in a space-optimized trie (also known as a prefix tree) of root 16. The hash digest of their keys provides the path to the values in the trie.” This approach offers numerous use cases, such as maintaining large on-chain ledgers (e.g., domains), or providing large oracle datasets of intrinsic data (e.g., a delegating/delegating map) or data extrinsic (for example, GitHub data about an ecosystem of projects). It is best suited for long-lived datasets that grow at a slow rate, such as a Blockchain Proof of Work (PoW)..
Key features of the Merkle Patricia Forestry library include rapid enrollment, insertion, and deletion of any key/value element in a large store, facilitated by a root hash digest (32 bytes) and a concise proof ( <1KB). The library incorporates several optimizations inspired by Ethereum's Modified Merkle Patricia Trie (MPT), but introduces a new approach to organizing nodes as small Sparse Merkle Trees. This innovation results in much smaller proof sizes and forms the basis for the library's name: Merkle Patricia Forestry.
Benkort explained the performance tradeoffs, pointing out that the optimization sacrifices some memory and CPU execution units to achieve smaller test sizes. Despite this, the library strikes a good balance between test size, memory usage, and CPU efficiency, as detailed in the performance tables included in the documentation. These tables summarize the trial sizes, memory units, and CPU units required for various trial 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 library’s implementation and capabilities. He explained that the library consists of two parts: one implemented in Aiken for smart contract-specific utilities and another in Node.js for off-chain operations. This complete implementation of the modified Merkle Patricia Tries, with a unique twist, is what Benkort calls “Merkle Patricia Forestry”.
“Basically, this is an authenticated data structure for mapping arbitrary keys to arbitrary values,” Benkort said. “However, it is made in such a way that it is possible to perform some operations just from a small hash and a concise proof, without the need to transport the entire data structure.”
For those familiar with blockchain technology, Merkle Trees are a similar, albeit simpler, structure used primarily to represent lists of items and verify their membership using a root hash. However, Merkle Patricia Tries (MPT) extend this functionality, allowing not only membership verification but also insertion and deletion of key/value pairs. Ethereum uses MPT for blockchain state and transaction storage, allowing light clients to query balances without storing the entire blockchain.
A significant problem with traditional MPTs is the large size of the evidence, which can span multiple kilobytes for large data stores. This isn’t as problematic for off-chain operations, but on-chain every byte is precious. Benkort’s implementation solves this problem by using tiny, sparse Merkle trees of 16 elements at each level, effectively creating trees within trials. This framework drastically reduces the size of proofs, trading some computational steps for Cardano’s efficiency gains.
Benkort demonstrated this ability through a recent transaction he spent on UTxO containing the root hash of a Merkle Patricia Forestry representing the entire Bitcoin block header hash, compressed into just 32 bytes. The transaction demonstrated 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 passes a UTxO that contains the root hash of a Merkle Patricia Forestry that represents the entire Bitcoin block header hash, mapped to their transactions. That’s approximately 850,000 blocks, compressed into 32 bytes.”
To spend this UTxO you need to provide on-chain proof to show the continuation of the chain by inserting a new block into the trie. The updated root hash stored on the chain must represent the previous chain plus one block. The entire validator for this operation fits into just 26 lines of Cardano 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 completely on-chain. “Imagine the realm of possibilities with such large data sets,” she suggested. “A domain registry? A data feed on financial markets? GitHub Stats? I see a world where institutions or committees publish large data sets in the form of a simple on-chain root hash, effectively acting as oracles for a variety of smart contracts along the line.”
Benkort concluded by reflecting on the journey of this project, which began as a parallel project at the end of last year. “It feels good to finally release it,” he said. “It was originally something I started at the end of last year, kind of as a side project. Given the many conversations about it lately, I thought I’d resurrect and package that code properly. Open source for the win.”
At the time of writing, Cardano (ADA) was trading at $0.455.
Featured image created with DALL·E, chart from TradingView.com