whitepaper.pdf
Onchain Social Graph Storage with Concurrent Merkle Trees: An Integrated Approach
Abstract
The Tapestry Protocol proposes a method to utilize advancements in storage efficiency to dramatically lower the storage costs associated with fully onchain digital identity and social graphs. The protocol aims to improve the current state of decentralized social graphs in which storing the graph onchain is cost-prohibitive, non-standardized, and difficult to scale in a decentralized manner. By applying Merkle tree technology—known for its role in optimizing storage through data verification and integrity checks—to the storage of social graphs, we can achieve near-zero marginal storage cost for each additional identity or connection added to the network while keeping the entire social graph onchain. The integration of Merkle tree technology and compressed NFT technology introduces a new primitive to the ecosystem: Non-Fungible Graphs, completing the abstraction of our analog world onchain (e.g., wallets, NFTs, social connections). This paper explores integrating Compressed NFT technology through Remote Procedure Calls (RPCs), which monitor blockchain activities and index blockchain data within Merkle Trees. This mechanism not only ensures the efficient and secure management of decentralized identities but also enables full composability within and across decentralized applications.
Introduction
The introduction of blockchain technology has significantly changed how digital assets are stored. Building on this transformation, new breakthroughs in the Solana ecosystem have enabled the storage of graph data on the blockchain at scale, prompting a reevaluation of how we store, manage, and leverage social connections. The role of a social graph—a graphical representation of interpersonal relationships—has significant implications for the way we understand and interact with blockchain entities, such as wallets and non-fungible tokens (NFTs). However, the contemporary state of crypto social graphs face two primary challenges: decentralization and scalability. Traditional methods of representing these graphs are either overly reliant on off-chain abstractions or are constrained by the limitations of onchain storage solutions. In response to these challenges, we propose the Tapestry Protocol, a blockchain-first approach to constructing a social graph that is inherently decentralized, scalable, and composable.
A Blockchain First Social Graph
A modern graph database consists of a set of nodes and edges, in which each node and edge possesses a map of properties. A vertex, representing something like a wallet address or token collection, is the basic object of a graph. For web3, a social graph can represent the relationships between wallets, NFTs, and other assets. However, not everyone will agree on how and even if nodes in a social graph are connected. Because of this, composability is paramount for the design of a crypto social graph.
Compressing a Social Graph
The goal of the decentralized social graph is for the ability of any party to rebuild a graph database from scratch. This also means anyone maintaining an index of a crypto graph database will have to continually listen to appends to the Merkle tree and ingest the changes.
| Seed | Type | Size(B) | Description |
|---|---|---|---|
| Label | String | 8 | Label of the node |
| Properties | String | 256 | Properties of node- key:value |
| Seed | Type | Size(B) | Description |
|---|---|---|---|
| Start ID | PublicKey | 32 | Address or Id of starting node |
| End ID | PublicKey | 32 | Address or Id of ending node |
| Properties | String | 256 | Properties of node- key:value |
Cost Comparisons
Not only does the Tapestry Protocol integrate well with existing Solana infrastructure and ideals, but it is also extremely cost-competitive.
| # of Nodes | # of Edges | Compressed Cost | Solana NFT Cost | ETH Cost |
|---|---|---|---|---|
| 10,000 | 250,000 | $887 | $727,864 | $1,300,000-13,000,000 |
| 100,000 | 2,500,000 | $894 | $7,278,648 | $13,000,000-130,000,000 |
| 1,000,000 | 25,000,000 | $1214 | $72,786,480 | $130,000,000-1,300,000,000 |
| 10,000,000 | 250,000,000 | $1267 | $727,864,800 | $1,300,000,000-13,000,000,000 |
| 250,000,000 | 750,000,000 | $1267 | $2,799,480,000 | $50,000,000,000-500,000,000,000 |
Integration with Existing Solana Infrastructure
It is one thing to have a theoretically perfect design for a social graph; it is another to have mass adoption of this protocol. When creating the Tapestry Protocol, a survey of the current Solana ecosystem was conducted. It was found that Metaplex already standardized how one would listen to the blockchain and index the data of the Merkle tree.
Concurrency
To achieve global scale, the underlying web3 social graph protocol needs to not only provide competitive data storage costs and fast reads - the protocol also needs to enable applications to write nodes and edges concurrently. These fast writes are enabled by Solana’s short block times and the ability to do concurrent updates on the Merkle tree. As of February 2024, Solana has an average block time of 400ms and an average block size of around 2MB.
Social Authority
The Tapestry Protocol will enable multiple key pairs to write and/or alter the social graph. When you create the Merkle tree onchain, the wallet or key pair that signed the transaction is the tree creator. If one wants to give another wallet the ability to write to the tree, one can delegate the authority to another wallet.
| Action | Tree Operation | Tree Authority |
|---|---|---|
| Create Node | Append | Social Authority or Delegate |
| Follow | Append | Social Authority or Delegate |
| Like | Append | Social Authority or Delegate |
| Collect | Append | Social Authority or Delegate |
| Delete | Replace Leaf | Social Authority |
Spam Protection
One of the biggest issues facing crypto adoption today is spam in wallets. The importance of the Tapestry Protocol is that the relationships represented in these Merkle trees will outlive the lifespan of any single company. The idea that there is a single point of failure is antithetical to the decentralized values in crypto.
Blockchain Agnostic
The Tapestry Protocol is flexible enough to store which blockchain an entity is on. Nothing is stopping a developer from writing a Solana wallet node and an Ethereum wallet node and connecting them with an edge.
Build Applications on Top of Non-Fungible Graphs
Non-Fungible Graphs present the opportunity to build social graphs that the public can verify. The Tapestry Protocol is meant to give developers the ability to build social applications faster than ever before.
Conclusion
Non-fungible graphs represent the relationships between wallets, NFTs, and other assets onchain, which is both novel and necessary. The Tapestry Protocol turns the vision of decentralized social networks into reality. It allows you to transfer your social connections across different applications and even other blockchains.