Walrus 백서

Walrus

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 1쪽

W alrus: An Efficient Decentralized Storage Network The MystenLabs Team hello@mystenlabs.com v2.0 – April 11, 2025 Abstract Decentralized storage systems face a fundamental trade-off between replication overhead, recovery efficiency, and security guarantees. Current approaches either rely on full replication, incurring sub- stantial storage costs, or employ trivial erasure coding schemes that struggle with efficient recovery especially under high storage- node churn. We presentW alrus, a novel decentralized blob storage system that addresses these limitations through multiple technical innovations. At the core of W alrusis Red Stuff, a two-dimensional erasure coding protocol that achieves high security with only 4.5x repli- cation factor, while enabling self-healing recovery that requires bandwidth proportional to only the lost data (𝑂(|𝑏𝑙𝑜𝑏|/𝑛) versus 𝑂(|𝑏𝑙𝑜𝑏|) in traditional systems). Crucially, Red Stuff is the first protocol to support storage challenges in asynchronous networks, preventing adversaries from exploiting network delays to pass ver- ification without actually storing data. W alrusalso introduces a novel multi-stage epoch change proto- col that efficiently handles storage node churn while maintaining uninterrupted availability during committee transitions. Our sys- tem incorporates authenticated data structures to defend against malicious clients and ensures data consistency throughout stor- age and retrieval processes. Experimental evaluation demonstrates that W alrusachieves practical performance at scale, making it suitable for a wide range of decentralized applications requiring high-integrity, available blob storage with reasonable overhead. 1 Introduction Blockchains support decentralized computation through the State Machine Replication (SMR) paradigm [37]. However, they are prac- tically limited to distributed applications that require little data for operation. Since SMR requires all validators to replicate data fully, it results in a large replication factor ranging from 100 to 1000, depending on the number of validators in each blockchain. While full data replication is practically needed for comput- ing on state, it introduces substantial overhead when applications only need to store and retrieve binary large objects (blobs) not computed upon1. Dedicated decentralized storage [ 6] networks emerged to store blobs more efficiently. For example, early net- works like IPFS [30] offer robust resistance to censorship, enhanced reliability and availability during faults, via replication on only a small subset of nodes [47]. Decentralized blob storage is invaluable to modern decentralized applications. We highlight the following use-cases: • Digital assets, managed on a blockchain, such as non fungible tokens (NFTs) need high integrity and availability guarantees provided by decentralized blob stores. The current practice of storing data off-chain on traditional stores only secures metadata, 1A recent example includes ‘inscriptions’ on bitcoin and other chains, see https: //medium.com/@thevalleylif e/crypto- terms- explained- exploring- bitcoin- inscriptions-51699dc218d2. while the actual NFT data remains vulnerable to removal or misrepresentation depending on the browser2. • Digital provenance of data assets is also increasingly important in the age of AI: to ensure the authenticity of documentary mate- rial; to ensure training data sets are not manipulated or polluted; and to certify that certain models generated specific instances of data [45]. These applications benefit from authenticity, traceabil- ity, integrity and availability decentralized stores provide. • Decentralized apps, whether web-based or as binaries, need to be distributed from decentralized stores. Today, the major- ity of decentralized apps rely on traditional web hosting to serve their front ends and client-side code, which offers poor integrity and availability. Decentralized stores may be used to serve web and dapps content directly while ensuring its integrity and availability. Similarly, decentralized stores can ensure binary transparency for software and support the storage needs of full pipelines of reproducible builds to support the strongest forms of software auditing and chain of custody [22, 29]. • Decentralized storage plays a critical role in ensuring data avail- ability for roll-ups [1], the current scaling strategy of Ethereum. In this setting, storage nodes hold the data temporarily allowing blockchain validators to recover it for execution. As a result, the system imposes replication costs solely on the netted state of the roll-up, rather than the full sequence of updates (e.g. transac- tions). • Decentralized social network platforms [18] are trying to chal- lenge centralized incumbents. But the nature of social network- ing requires support for rich media user content, such as long texts, images or videos. Beyond social, collaborative platforms as well as civic participation platforms [4] need a way to store both public interest data and the application data itself in credibly neutral stores such as decentralized stores. • Finally, the integration of decentralized storage with encryp- tion techniques marks a significant paradigm shift [ 19]. This approach offers users comprehensive data management aligned with the Confidentiality, Integrity, and Availability (CIA) triad, eliminating the need to rely on cloud services as fiduciaries. This integration unlocks numerous promising applications, including sovereign data management, decentralized data marketplaces, and computational operations over encrypted datasets. Although this paper does not focus on these applications, our decentralized storage system, W alrus, can naturally function as the storage layer for encrypted blobs. This approach provides a structured, layered framework that allows encryption overlays to focus on creating a secure and efficient Key Management System (KMS) without worrying about data availability. In brief, secure decentralized blob stores are critical for all appli- cations where data is relied upon by multiple mutually distrustful parties, and needs to stored in a credibly neutral store that provides 2A recent proof of concept attack is described here: https://moxie.org/2022/01/07/web3- first-impressions.html 1 The MystenLabs Team high authenticity, integrity, auditability and availability – all this at a reasonable cost and low complexity. Approaches to Decentralized Storage Protocols for decentralized storage generally fall into two main categories. The first category includes systems with full replication, with Filecoin [30] and Arweave [46] serving as prominent examples. The main advantage of these systems is the complete availability of the blob on the storage nodes, which allows for easy access and seamless migration if a storage node goes offline. This setup enables a permissionless environment since storage nodes do not need to rely on each other for file recovery. However, the reliability of these systems hinges on the robustness of the selected storage nodes. For instance, assuming a classic 1/3 static adversary model and an infinite pool of candidate storage nodes, achieving “twelve nines” of security – meaning a probability of less than 10−12 of losing access to a file – requires storing more than 25 copies on the network 3. This results in a 25x storage overhead. A further challenge arises from Sybil attacks [16], where malicious actors can pretend to store multiple copies of a file, undermining the system’s integrity. The second category of decentralized storage services [23] uses Reed-Solomon (RS) encoding [32]. RS encoding reduces replication requirements significantly. For example, in a system similar to blockchain operations, with𝑛 nodes, of which1/3 may be malicious, and in an asynchronous network, RS encoding can achieve sufficient security with the equivalent of just 3x storage overhead. This is possible since RS encoding splits a file into smaller pieces, that we call slivers, each representing a fraction of the original file. Any set of slivers greater in total size to the original file can be decoded back into the original file. However, an issue with erasure coding arises when a storage node goes offline, and needs to be replaced by another. Unlike fully replicated systems, where data can simply be copied from one node to another, RS-encoded systems require that all existing storage nodes send their slivers to the substitute node. The substitute can then recover the lost sliver, but this process results in 𝑂(|blob|) data being transmitted across the network. Frequent recoveries can erode the storage savings achieved through reduced replication, which means that these systems need a low churn of storage nodes and hence be less permisionless. Regardless of the replication protocol, all existing decentral- ized storage systems face an additional challenges: the need for a continuous stream of challenges to ensure that storage nodes are incentivized to retain the data and do not discard it. This is crucial in an open, decentralized system that offers payments for storage and goes beyond the honest/malicious setting. Current solutions always assume that the network is synchronous such that the ad- versary cannot read any missing data from honest nodes and reply to challenges in time. Introducing W alrus We introduceW alrus, a new approach to decentralized blob storage. It follows the erasure codes type of architecture in order to scale to 100s of storage nodes providing high resilience at a low storage overhead. At the heart of W alrus, lies a new encoding protocol, 3The chance that all 25 storage nodes are adversarial and delete the file is 3−25 = 1.18× 10−12. called Red Stuff that uses a novel two-dimensional (2D) encoding algorithm that is self-healing. Specificaly, it enables the recovery of lost slivers using bandwidth proportional to the amount of lost data (𝑂(|blob|𝑛 ) in our case). Moreover, Red Stuff incorporates authenticated data structures to defend against malicious clients, ensuring that the data stored and retrieved remains consistent. One unique feature of Red Stuff is its ability to work in an asychronous network while supporting storage challenges, making it the first of its kind. This is only possible thanks to the two- dimensional encoding that allows for different encoding thresholds per dimension. The low-threshold dimension can be used from nodes that did not get the symbols during the write flow to recover what they missed, whereas the high-threshold dimension can be used for the read flow to prevent the adversary from slowing down honest nodes during challenge periods and collecting sufficient information to reply to challenges. One final challenge for W alrus, and in general, any encoding- based decentralized storage system is operating securely across epochs each managed by a different committee of storage nodes. This is challenging because we want to ensure uninterrupted avail- ability to both read and write blobs during the naturally occurring churn of a permissionless system, but if we keep writing data in the nodes about to depart, they keep needing to transfer them to the nodes that are replacing them. This creates a race for the resources of those nodes, which will either stop accepting writes or fail to ever transfer responsibility. W alrusdeals with this through its novel multi-stage epoch change protocol that naturally fits the principles of decentralized storage systems. In summary, we make the following contributions: • We define the problem of Asynchronous Complete Data-Sharing and propose Red Stuff, the first protocol to solve it efficiently even under Byzantine Faults (Section 3) • We present W alrus, the first permissionless decentralized stor- age protocol designed for low replication cost and the ability to efficiently recover lost data due to faults or participant churn (Section 4). • We show how W alrusleverages Red Stuff to implement the first asynchronous challenge protocol (Section 4.6) • We provide a production-ready implementation of W alrusand deploy a public testnet of W alrus. We then measure its perfor- mance and scalability in a real environment (Section 7). 2 Models and Definitions W alrusrelies on the following assumptions. Cryptographic assumptions. Throughout the paper, we useℎ𝑎𝑠ℎ() to denote a collision resistant hash function. We also assume the existence of secure digital signatures and binding commitments. Network and adversarial assumptions. W alrusruns in epochs, each with a static set of storage nodes. At the end of the epoch 𝑛 = 3𝑓+ 1 storage nodes are elected as part of the the storage committee of the epoch and each one controls a storage shard such that a malicious adversary can control up to𝑓 of them. The corrupted nodes can deviate arbitrarily from the protocol. The remaining nodes are honest and strictly adhere to the protocol. If a node controlled by the adversary at epoch𝑒 is not a part of the 2 W alrus: An Efficient Decentralized Storage Network Table 1: Comparing Replication Algorithms Replication for 10−12 Security Write/Read Cost Single Shard Recovery Cost Asychronous Challenges Replication 25x 𝑂(𝑛|𝑏𝑙𝑜𝑏|) 𝑂(|𝑏𝑙𝑜𝑏|) Unsupported Classic ECC 3x 𝑂(|𝑏𝑙𝑜𝑏|) 𝑂(|𝑏𝑙𝑜𝑏|) Unsupported RedStuff 4.5x 𝑂(|𝑏𝑙𝑜𝑏|) 𝑂(|𝑏𝑙𝑜𝑏|𝑛 ) Supported storage node set at epoch𝑒+ 1 then the adversary can adapt and compromise a different node at epoch𝑒+ 1 after the epoch change has completed. We assume every pair of honest nodes has access to a reliable and authenticated channel. The network is asynchronous, so the adversary can arbitrarily delay or reorder messages between honest nodes, but must eventually deliver every message unless the epoch ends first. If the epoch ends then the messages can be dropped. Our goal is not only to provide a secure decentralized system but to also detect and punish any storage node that does not hold the data that it is assigned. This is a standard additional assumption for dencentralized storage system to make sure that honest parties cannot be covertly compromised forever. Erasure codes. As part of W alrus, we propose Asynchronous Complete Data Storage (ACDS) that uses an erasure coding scheme. While not necessary for the core parts of the protocol, we also assume that the encoding scheme is systematic for some of our optimizations, meaning that the source symbols of the encoding scheme also appear as part of its output symbols. Let Encode(𝐵,𝑡,𝑛) be the encoding algorithm. Its output are𝑛 symbols such that any𝑡 can be used to reconstruct𝐵. This happens by first splitting𝐵 into𝑡 symbols of size𝑂(|𝐵|𝑡 ) which are called source symbols. These are then expanded by generating𝑛−𝑡 repair symbols for a total of 𝑛 output symbols. On the decoding side, anyone can callDecode(𝑇,𝑡,𝑛) where𝑇 is a set of at least𝑡 correctly encoded symbols, and it returns the blob𝐵. Blockchain substrate. W alrususes an external blockchain as a black box for all control operations that happen on W alrus. A blockchain protocol can be abstracted as a computational black box that accepts a concurrent set of transactions, each with an input message𝑇𝑥(𝑀) and outputs a total order of updates to be applied on the state 𝑅𝑒𝑠(𝑠𝑒𝑞,𝑈). We assume that the blockchain does not deviate from this abstract and does not censor 𝑇𝑥(𝑀) indefinitely. Any high-performance modern SMR protocol satisfies these requirements, in our implementation we use Sui [8] and have implemented critical W alruscoordination protocols in the Move smart contract language [7]. 3 Asynchronous Complete Data Storage (ACDS) We first define the problem of Complete Data Storage in a dis- tributed system, and describe our solution for an asynchronous network which we refer to as Asynchronous Complete Data Stor- age (ACDS). Secondly, we show its correctness and complexity. 3.1 Problem Statement In a nutshell a Complete Data Storage protocol allows a writer to write a blob to a network of storage nodes ( Write Completeness), and then ensures that any reader can read it despite some failures and byzantine behaviour amongst storage nodes ( Validity); and read it consistently, despite a potentially byzantine writer ( Read Consistency). More formally: Definition 1 (Complete Data Storage). Given a network of𝑛 = 3𝑓+1 nodes, where up to 𝑓 are byzantine, let 𝐵 be a blob that a writer 𝑊 wants to store within the network, and share it with a set of readers 𝑅. A protocol for Complete Data Storage guarantees three properties: • Write Completeness: If a writer𝑊 is honest, then every honest node holding a commitment to blob 𝐵 eventually holds a part 𝑝 (derived from𝐵), such that 𝐵 can be recovered fromO |𝐵| |𝑝|  parts. • Read Consistency: Two honest readers, 𝑅1 and𝑅2, reading a suc- cessfully written blob 𝐵 either both succeed and return 𝐵 or both return⊥. • Validity: If an honest writer𝑊 successfully writes𝐵, then an honest reader𝑅 holding a commitment to 𝐵 can successfully read 𝐵. We present the ACDS protocols in a context where the storage node set is fixed and static. And in subsequent sections describing its use within W alrus, we discuss how it is adapted to allow for churn into the committees of storage nodes. 3.2 Strawman Design In this section, we iterate first through two strawman designs and discuss their inefficiencies. Strawman I: Full Replication. The simplest protocol uses full replication in the spirit of Filecoin [ 30] and Arweave [ 46]. The writer𝑊 broadcasts its blob𝐵 along with a binding commitment to 𝐵 (e.g.,𝐻𝐵 =ℎ𝑎𝑠ℎ(𝐵)), to all storage nodes and then waits to receive 𝑓+ 1 receipt acknowledgments. These acknowledgments form an availability certificate which guarantees availability because at least one acknowledgement comes from an honest node. The writer𝑊 can publish this certificate on the blockchain, which ensures that it is visible to every other honest node, who can then request a Read(𝐵) successfully. This achieves Write Completeness since eventually all honest nodes will hold blob𝐵 locally. The rest of the properties also hold trivially. Notice that the reader never reads⊥. Although the Full Replication protocol is simple, it requires the writer to send anO(𝑛|𝐵|) amount of data on the network which is also the total cost of storage. Additionally, if the network is asyn- chronous, it can cost up to 𝑓+ 1 requests to guarantee a correct replica is contacted, which would lead toO(𝑛|𝐵|) cost per recov- ering storage node with a total cost ofO(𝑛2|𝐵|) over the network. Similarly, even a read can be very inefficient in asynchrony, as the reader might need to send𝑓+ 1 requests costingO(𝑛|𝐵|). Strawman II: Encode & Share. To reduce the upfront data dissem- ination cost, some distributed storage protocols such as Storj [39] 3 The MystenLabs Team S31 S11 S21 S41 Encode: from f+1 to nslivers Figure 1: Encoding a Blob in one dimension. First the blob is split into 𝑓+ 1 systematic slivers and then a further 2𝑓 repair slivers are encoded and Sia [43] use RS-coding [32]. The writer𝑊 divides its blob𝐵 into𝑓+ 1 slivers and encodes 2𝑓 extra repair slivers. Thanks to the encoding properties, any𝑓+ 1 slivers can be used to recover𝐵. Each sliver has a size ofO(|𝐵|𝑛 ). The writer𝑊 then commits to all the slivers using a binding commitment such as a Merkle tree [27] and sends each node a separate sliver together with a proof of inclusion4. The nodes receive their slivers and check against the commitment; if the sliver is correctly committed, they acknowledge reception by signing the commitment. The writer𝑊 can then generate an availability certificate from 2𝑓+ 1 signatures and post it on the blockchain. A reader continuously requests slivers from the nodes until it receives 𝑓+ 1 valid replies (i.e., replies that are verified against the commitment). The reader is guaranteed to receive them since at least 𝑓 + 1 honest nodes have stored their sliver. The reader then reconstructs blob𝐵 from the slivers and then additionally, re-
프로젝트로 돌아가기