Cardano Foundation CTO Matthias Benkort, @KtorZ, encapsulated the entire Bitcoin blockchain within a single block on the Cardano blockchain.
This announcement, made via X, has generated a lot of buzz in the blockchain community. It highlights the potential for advanced data management and interoperability between different blockchains.
Contents
A Step Forward for Cardano
Benkort’s revelation goes along with releasing a new open-source library on GitHub titled “Merkle Patricia Forestry.” This library introduces on-chain and off-chain tools designed to work with Merkle Patricia Tries in Cardano. According to documentation, a Merkle Patricia Trie is a “persistent, authenticated data structure for mapping between arbitrary keys and values.” It essentially functions as a highly efficient and secure hashmap.
The structure of this library is detailed in the documentation. “The elements are represented in a space-optimized trie (also known as a prefix tree) of radix 16. The hash of the keys provides the path to the values in the tries“. This approach offers numerous use cases, such as maintaining large on-chain records (e.g., domains). It may also provide vast oracle datasets of intrinsic data (e.g., a delegator/delegate map) or extrinsic data (e.g., GitHub data related to a project ecosystem). It is particularly suited for long-running datasets that grow slowly, such as a Proof-of-Work (PoW) blockchain.
Key Features of the Merkle Patricia Forestry Library
Key features of the library include fast membership, insertion, and deletion of any key/value element in a large store facilitated by a root hash (32 bytes) and succinct proof (<1KB). The library incorporates several optimizations inspired by the Ethereum Modified Merkle Patricia Trie (MPT) but introduces a novel approach to organize nodes as small Dispersed Merkle Trees. This innovation results in much smaller tests and is the basis for the library name: Merkle Patricia Forestry.
Benkort explained the performance tradeoffs, noting that the optimization sacrifices some memory and CPU execution units to achieve smaller test sizes. Despite this, the library finds 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 test size, memory units, and CPU units required, highlighting the efficiency of the library in different scenarios.
Information and Implementation
In a series of detailed posts on X, Benkort provided more information on the implementation and capabilities of the library. He explained that the library consists of two parts: one implemented in Aiken for utilities specific 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.”
I've put the entire Bitcoin chain on Cardano and added a block to it!
— KtorZ (@_KtorZ_) June 3, 2024
… sort of.
Let's rewind a bit.
This has already somewhat leaked, but I've been working on a (top-secret) open source library which I am happy to "officially" release. Enters:https://t.co/THOrvKk6rA
“Fundamentally, this is an authenticated data structure for mapping arbitrary keys to arbitrary values. However, it’s done in such a way that it’s possible to perform some operations from just a small hash and a succinct proof without the need to carry the entire data structure.”
Matthias Benkort
Merkle Trees
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 (MPTs) extend this functionality, allowing membership verification and the insertion and deletion of key/value pairs. Ethereum employs MPTs for its blockchain state and transaction storage. Their use allows thin clients to query balances without storing the entire blockchain.
A significant problem with traditional MPTs is the large size of the tests. The size can span several kilobytes for large data stores. The size is not as problematic for off-chain operations, but on-chain, every byte is valuable. Benkort’s implementation addresses this by using small 16-element Dispersed Merkle Trees at each level, effectively creating trees within tries. This structure drastically reduces the size of the tries, trading off some computational steps for efficiency gains in Cardano.
Benkort demonstrated this capability through a recent transaction that spent a UTxO containing the root hash of a Merkle Patricia Forestry. This MPF represents the header hashes of the entire Bitcoin block, 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.
Future Applications and Use Cases
Benkort highlighted the potential applications of this technology, ranging from trustless bridges to arbitrarily large key/value stores managed on-chain. “Imagine the realm of possibilities with such large data sets,” he suggested. “A domain registry? A financial market data feed? GitHub statistics? I see a world where institutions or committees publish large data sets in the form of a simple on-chain root hash, effectively serving as oracles for a variety of smart contracts in the future.” Benkort concluded by reflecting on the journey of this project, which began as a side project late last year. “It feels good to finally release this,” he said. “It was originally something I started late last year, a bit of a side project. Given the many conversations about it lately, I thought I’d resurrect and properly package that code. Open source to win.”
This innovative integration of technologies highlights not only the technical capability of the Cardano Foundation but also the vast potential of blockchain technology to evolve and adapt to new demands and use cases. This breakthrough pushes the frontier of what is possible in the realm of cryptocurrencies and decentralized technology.