Walrus 백서

Walrus

원문

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

consistent blob’s slivers, along with a pointer to the on-chain evidence for the inconsistency. 4.5 Committee Reconfiguration W alrusis a decentralized protocol, hence it is natural that the set of storage nodes will fluctuate between epochs. When a new committee replaces the current committee between epochs, recon- figuration takes place. The goal of the reconfiguration protocol is to preserve the invariant that all blobs past PoA are available, no matter if the set of storage nodes changes. Subject of course to 2𝑓+ 1 nodes being honest in all epochs. Reconfiguration may take hours if a significant amount of data needs to be transferred between nodes. In that period, W alrusmust continue to perform reads and writes for blobs to ensure no downtime. Core Design. At a high-level the reconfiguration protocol of W al- rus is similar to the reconfiguration protocols of blockchain sys- tems, since W alrusalso operates in quorums of storage nodes. However, the reconfiguration of W alrushas its own challenges because the migration of state is orders of magnitude more expen- sive than classic blockchain systems. The main challenge is the race between writing blobs for epoch 𝑒 and transferring slivers from outgoing storage nodes to incoming storage nodes during the reconfiguration event between𝑒 and𝑒+ 1. More specifically, if the amount of data written in epoch𝑒 is greater than the ability of a storage node to transfer them over to the new storage node, then the epoch will never finish. This problem is exacerbated when some of the outgoing storage nodes of 𝑒 are unavailable, as this means that the incoming storage nodes need to recover the slivers from the committee of epoch𝑒. Fortunately, by using Red Stuff, the bandwidth cost of the faulty case is the same as that of the fault-free case. but it still requires more messages to be sent over the network and more computation to verify proofs and to decode symbols to slivers. To resolve this problem without shutting off the write path, we take a different approach by requiring writes to be directed to the committee of𝑒+ 1 the moment the reconfiguration starts, while still directing reads to the old committee, instead of having a single 7 The MystenLabs Team point at which both reads and writes are handed over to the new committee. This can unfortunately create challenges when it comes to reading these fresh blobs, as during the handover period it is unclear which nodes store the data. To resolve this, we include in the𝑚𝑒𝑡𝑎𝑑𝑎 of every𝑏𝑙𝑜𝑏 the epoch in which it was first written. If the epoch is𝑒+ 1 then the client is asked to direct reads to the new committee; otherwise, it can direct reads to the old committee. This happens only during handover period (when both committees need to be live and secure). Once a member of the new committee has bootstrapped their part of the state, i.e., they have gotten all slivers for their shard, they signal that they are ready to take over. When 2𝑓+ 1 members of the new committee have signaled this, the reconfiguration process finishes and all reads are redirected to the storage nodes of the new committee. Security arguments: In a nutshell, reconfiguration ensures all ACDS properties across epochs. The key invariant is: the reconfig- uration algorithm ensures that if a blob is to be available across epochs, in each epoch𝑓+ 1 correct storage nodes (potentially differ- ent ones) hold slivers. This is the purpose of the explicit signaling that unlocks the epoch change by 2𝑓+ 1 nodes. Therefore, even- tually all other honest storage nodes can recover their sliver pairs, and in all cases, 𝑓+ 1 honest nodes in the next epoch are able to recover correct sliver pairs as a condition to move epochs. 4.6 Storage Challenges W alrususes a challenge protocol to prevent cheating nodes that trivially never store or serve data from receiving rewards and to incentivize honest nodes. To the best of our knowledge, we present here the first storage proof protocol to make no assumptions about network synchrony. It leverages the completeness property of Red Stuff and the ability to reconstruct blobs with 2𝑓+ 1 threshold. In this section, we first present the simple protocol that is theoretically secure but costly. Then we discuss a relaxation that makes the se- curity probabilistic but reduces the cost of challenging significantly and can be tuned dynamically if reads start to fail. Fully Asynchronous Challenge Protocol. Close to the end of the epoch, the storage nodes witness a “challenge start” event on-chain, such as a specific block height. At that point, they stop serving read and recovery requests and broadcast an acknowledgment. When 2𝑓+1 honest nodes have entered the challenge phase, the challenges start. Every challenged node sends the common symbols per blob to each other along with a proof against the commitment of the writer of the blob. The receiving nodes check the symbols and send a confirmation signature. When the proving storage node collects 2𝑓+ 1 signatures, it forms a certificate, which it submits on-chain. When 2𝑓+ 1 certificates are valid, the challenge period ends, and the reads and recovery are re-enabled. During the challenge period, the nodes that witnessed the chal- lenge start message do not respond to read or recovery requests. Since the threshold for starting a challenge is 2𝑓+ 1, at least𝑓+ 1 honest will not reply after the challenged files are determined. As a result, even if the adversary has𝑓 slivers stored and has slowed down 𝑓 honest nodes to not see the challenge start message, it can only get 2𝑓 symbols from their secondary slivers and then 2𝑓 signatures on its certificate. These are not enough to recover the full secondary sliver and convince the rest of the honest nodes to sign the certificate, and as a result, it will fail the challenge. The proof can be seen in Section 5.4. Relaxations. Although this protocol is secure, it has the caveat that no reads are served during the challenge period and that a full- blown challenge requires bandwidth equal to the amount stored. To reduce its impact, we plan to trade-off security for allowing most blobs to be readable and not under a challenge. For the lighweight challenge protocol, we require the storage nodes to setup a random coin with a2𝑓+1 reconstruction threshold. This is possible using any kind of asynchronous DKG [13, 14, 20] or randomness generation protocol [17, 40]. The coin is used to seed a pseudo-random function (PRF) that defines which blobs need to be challenged per storage node. Any blob not in the set can be accessible directly again. The number of blobs challenged needs to be sufficiently large compared to the total number of blobs such that storage nodes have a negligible probability of holding all the challenged blobs unless they hold the overwhelming majority of blobs. For example, if a storage node holds 90% (99%) of the blobs, it has less than a 10−30 probability of success in a 640 (7000) file challenge. If we notice that reads fail although challenges pass, it means that we do not challenge enough files. In this case,W alruswill increase the challenges up to the point of reenabling the full challenge protocol. However, for this to happen, it means that the malicious storage nodes have minimal storage savings (less than a constant factor), which is unlikely to have a real impact on their resource cost. 5 Red Stuff and W alrusProofs This section completes Section 3 by showing that Red Stuff satis- fies all the properties of a ACDS. The casual reader can skip it. 5.1 Write Completeness We show that Red Stuff satisfies Write Completeness. Informally, if an honest writer writes a blob 𝐵 to the network, every honest storage node eventually holds a primary and secondary correctly encoded sliver of𝐵. For this part we assume the writer is honest and provides a correct vector commitment𝑀. Lemma 1 (Primary Sliver Reconstruction). If a party holds a set of(2𝑓+ 1) symbols{𝐸(𝑖,∗)} 2𝑓+1from a primary sliver 𝑆(𝑝,𝑖) , it can obtain the complete primary sliver 𝑆(𝑝,𝑖) . Proof. The proofs directly follows from the reconstruction property of erasure codes with reconstruction threshold (2𝑓 + 1). □ Lemma 2 (Secondary Sliver Reconstruction). If a party holds a set of(𝑓+ 1) symbols{𝐸(∗,𝑖)}𝑓+1 from a secondary sliver 𝑆(𝑠,𝑖) , it can obtain the complete secondary sliver 𝑆(𝑠,𝑖) . Proof. The proofs directly follows from the reconstruction property of erasure codes with reconstruction threshold(𝑓+1). □ Theorem 1. Red Stuff satisfies Write Completeness (Definition 1). 8 W alrus: An Efficient Decentralized Storage Network Proof. To write a blob 𝐵, an honest writer 𝑊 sends at least (2𝑓+ 1) correctly encoded slivers (parts) to different storage nodes, along with a binding vector commitment𝑀 over those slivers. For these nodes the property holds by definition. Now let’s assume a node 𝑗 that is not in the initial 2𝑓+ 1 recipients. The node will ask every node𝑖 for their shared symbols in its primary (i.e.,𝐸(𝑗,𝑖)) and secondary (i.e.,𝐸(𝑖,𝑗)) sliver. Given the binding vector commitment 𝑀 node𝑖 can either send the true symbols or not reply. Given that at least 2𝑓+ 1 nodes acknowledged𝑀 then 𝑗 will get𝑓+ 1 correct symbols for its primary sliver{𝐸(𝑗,∗)}𝑓+1 and𝑓+1 correct symbols for its secondary sliver{𝐸(∗,𝑗)}𝑓+1. From Lemma 2 this means that 𝑗 will reconstruct its full secondary sliver𝑆(𝑠,𝑗) . Since this reasoning applies to any generic node𝑖, it holds for all nodes. As a result, eventually all2𝑓+1 honest nodes will reconstruct their secondary slivers𝑆(𝑠,∗) . Every time a node reconstructs their secondary sliver, they also reply to node𝑗 with the shared symbol which is part of the primary sliver of 𝑗(i.e.,𝐸(𝑗,∗)) . As a result, eventually 𝑗 will go from{𝐸(𝑗,∗)}𝑓+1 to{𝐸(𝑗,∗)} 2𝑓+1 This allows node 𝑗 to apply Lemma 1 and reconstruct its primary sliver𝑆(𝑝,𝑗). Since this reasoning applies to any generic node𝑖, it holds for all nodes and concludes the proof that all honest nodes will eventually hold both their primary and secondary sliver. □ 5.2 Read Consistency We prove that Red Stuff satisfies Read Consistency. Informally, if two honest readers read a blob 𝐵 written to the network, they either both eventually obtain𝐵 or both eventually fail and obtain ⊥. Theorem 2. Red Stuff satisfies Read Consistency (Definition 1). Proof. Notice that the encoding scheme is deterministic and the last step of reading is to re-run the encoding and reconstruct 𝑀. As a result, a reader that accepts the read as correct needs to output𝐵. The challenge with Read Consistency is if the writer can convince different readers that collect different slivers to output 𝐵 and⊥. Let’s assume that two honest readers𝑅1 and𝑅2 read a blob𝐵 from the network and𝑅1 eventually obtains𝐵 while𝑅2 eventually fails and obtains⊥. There are two scenarios for𝑅2 to output⊥: (1) 𝑅2 gets 2𝑓 + 1 replies matching 𝑀 and tries to reconstruct. During reconstruction, the commitment does not much𝑀 (2) Some node failed to reconstruct their secondary sliver. By the algorithm this nodes will hold a proof of inconsistency, which it will send to𝑅2 In either scenario 𝑅1 during their reconstruction should have also detected the inconsistency and output⊥ otherwise the bind- ing property of the vector commitment does not hold. Hence a contradiction. □ 5.3 Validity We prove that Red Stuff satisfies Validity. Informally, if an honest writer writes a correctly encoded blob 𝐵 to the network, every honest reader eventually obtains𝐵. Theorem 3 (Validity). Red Stuff satisfies Validity (Definition 1). Proof. To write a blob𝐵, an honest writer𝑊 construct𝑛 correct encoded slivers (parts) along with a binding vector commitment𝑀 over those slivers. Since the writer is honest from Theorem 1 all (at least 2𝑓+ 1) honest storage nodes will hold their respective slivers. Let’s note by nodes the entire set of storage nodes. An honest reader queries each storage node 𝑛∈ nodes for their secondary sliver, verifies them against𝑀 and when it holds 2𝑓+ 1 uses them to reconstruct the𝐵. Since all honest storage nodes will eventually reply to the reader and𝑊 was honest, the reader will eventually obtain𝐵. □ 5.4 Asychronous Challenges We prove that no malicious storage node that does not hold all slivers of blobs will succeed in replying to a challenge. We note that storage nodes of the adversary can collude and hold a single version of their common symbols. However, they would still need to hold 2𝑓+ 1 symbols per sliver which is effectively the cost of a full sliver as far as storage is concerned. Theorem 4 (Secure Challenge Protocol). No malicious storage node running W alrusthat does not hold all slivers of blobs will succeed in replying to a challenge. Proof. We assume there exists a storage node that deletes a symbol it is supposed to hold and the respective symbol is held by an honest node. At challenge time it will need to send this symbol to the honest node to get a certificate. To do so, it will need to recover the sliver. For this it will get𝑓− 1 symbols from the other malicious storage nodes. It can also get𝑓 symbols from slow, honest nodes through the read path. However𝑓+𝑓− 1 = 2𝑓− 1. From lemma 1 the node need 2𝑓+ 1 to reconstruct the primary sliver and get this symbol. Hence it will fail to reply. If it fails to reply then it cannot get a certificate as only the 2𝑓−1 node mentioned above plus its self-signature will be collected, resulting in 2𝑓 < 2𝑓+ 1 signatures. □ 6 Economics and Incentives Beyond simple reads and writes, we design robust economic and incentive mechanisms for W alrusto ensure competitive pricing, efficient allocation of resources, and minimal adversarial behavior. Conceptually, W alrus’s economic challenges differ from those of a typical blockchain, since W alrusleverages a blockchain as a control plane, and hence inherits the security of the blockchain consensus. Instead, W alrusfaces challenges around enforcing long-term contracts. W alrusnodes and users strike agreements in advance to store data for some duration of time and provide access to that data in the future. But nodes may be tempted to default over time, e.g. resell committed storage at higher prices to other users or withhold later access unless ransoms are paid. Moreover, given that W alrusis decentralized nodes may simply churn from the system over time and leave it to future committees of nodes to fulfill their commitments without even fully internalizing future reputation costs when acting in their own interests, as the well- known “tragedy of the commons" problem. Unlike in traditional markets, where long-term contracts can be enforced through the 9 The MystenLabs Team legal system, W alrushas to rely on incentives and disincentives to mitigate this. The primary tool that ensures contracts are honored is staked capital – oriented around the new WAL token – which earns re- wards for good behavior and is slashed for bad behavior. This capital can come from the nodes directly, or it can come from users who delegate their capital to well-run nodes. In tandem, the economics behind W alruscontinues to assume that up to 𝑓 =⌊𝑛3⌋ nodes (or, more accurately, nodes controlling up to ⌊𝑛3⌋ of the shards) are Byzantine, building robustness for arbitrary failures including malicious actions. Finally, this principal tool is paired with other mechanisms to coordinate pricing, access, migrations, and integrity checks in the system. This section proceeds as follows. Section 6.1 describes the staking mechanism that underpins the security and efficiency of the entire system. Section 6.2 outlines the migration of shards, when new nodes join the system (or increase relative stake) or existing nodes exit the system (or decrease relative stake). Section 6.3 explains how nodes collectively set prices in competitive and fair ways. Finally, Section 6.4 briefly explains the token governance processes. 6.1 Staking Staking of WAL tokens, by or on behalf of storage nodes, underpins W alrus’s security. By earning rewards when storage nodes honor commitments and being slashed when nodes do not. Staking on W alrushas four core components: assignment of stakes and shards, the unstaking process, the accrual of rewards and penalties, and the adjustments needed for self-custodial objects. Stake and Shard Assignment. W alrusincludes an in-built layer of delegated staking, so that users can participate in the network’s security regardless of whether they operate storage services directly. Nodes compete with one another to attract stake from users, which in turn governs the assignment of shards to them. Users make this choice based on the storage node’s reputation, the node’s own staked capital, the commission rates set, and other factors. Once the epoch is set to change, i.e. point 𝑐 in Figure 5, the stake is considered locked in its assignment to storage nodes (and any unstaking requires the formal unstaking process described next). Shards are now assigned to nodes for the upcoming epoch in proportion to the nodes’ associated stakes. This is described in more detail in Section 6.2. W alrusdoes not impose requirements on storage nodes to pro- vide some minimal level of capital, allowing nodes to choose be- tween funding some, all, or none of its own capital. This is deliberate. Delegators will likely consider a nodes’ own capital when making delegation decisions, but W alrusneed not be prescriptive of the required level. W alrusdoes impose one safeguard on commission rates: they must be set by nodes afull epoch before the cutoff point. As such, if a node raises commission rates too far, its delegators have sufficient time to unstake before those new rates go into effect. Unstaking. The unstaking process is similar to the staking pro- cess, in that a wallet must register the request before the cutoff point in a given epoch (point𝑐 in Figure 5). Once the cutoff point is reached, the departing stake no longer counts towards the node’s aggregate stake for allocating shards. However, the departing stake is not released at that point. Instead, the departing stake is held by W alrusthrough the shard migration process described in Section 6.2, which takes place after the epoch ends; and its value can be slashed if the shard migration procedures involving its node fail. The departing stake is subsequently released. If the node is not in- volved in shard migration processes, the departing stake is released at the end of the epoch instead. W alrusagain imposes no further requirements on the process.8 Rewards and Penalties. At the end of each epoch, a node earns rewards or is punished based on its actions throughout the epoch. Nodes that have answered challenges (Section 4.6) correctly and thus have proven data storage, have facilitated writes to the system, or have participated in recovery of shards earn rewards. Nodes that have not answered challenges correctly are penalised. These reward and penalty rates are based on a combination of protocol revenue and parameters tuned by token governance, and they are discussed later. In addition, penalties on nodes around the recovery process for shards are levied earlier, at the end of the migration period. This allows capital that wishes to unstake from the system to be potentially slashed and complete the exit. Users share in rewards and penalties on a proportionate basis, for the full epochs that their stakes are active. Storage nodes themselves can bring their own capital to earn similar rewards and penalties; and storage nodes separately earn commissions from the rewards that they bring to their delegators. Initially W alruswill treat all stake equivalently, such that there are no junior or senior stake tranches, and all stakes earn rewards and penalties at the same rate. This can be changed in the protocol later, at the community’s discretion; or it can be built as custom functionality on top of W alrusby a given node. Self-Custody in Staking. Like Sui [7], W alruswill implement staking via self-cu
프로젝트로 돌아가기