Walrus 백서

Walrus

원문

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

encodes the recovered value and recomputes the commitment [10, 27]. If writer 𝑊 was honest, the recomputed commitment will match the commitment from the availability certificate and the reader outputs𝐵. Otherwise, writer𝑊 may not have committed to a valid encoding, in which case the commitments do not match and the reader outputs⊥. As before, the nodes that did not get slivers during the sharing phase can recover them by reading 𝐵. If the output of the read operation is⊥, the node returns⊥ on all future reads. Otherwise, the node stores their encoded sliver and discards the rest of𝐵. Note this recovery process is expensive: recovery costsO(|𝐵|) even if the storage cost afterwards isO(|𝐵|𝑛). This second protocol reduces the dissemination costs signifi- cantly at the expense of extra computation (encoding/decoding and committing to slivers from𝐵). Disseminating blob𝐵 only costs O(|𝐵|)5, which is the same cost as reading it. However, complete dispersal still costsO(𝑛|𝐵|), because as we saw the process of re- covering missing slivers requires downloading the entire blob 𝐵. Given that there can be up to 𝑓 storage nodes that did not manage to get their sliver from writer 𝑊 and need to invoke the recov- ery protocol, the protocol hasO(𝑛|𝐵|) total cost. This is not only important during the initial dispersal, but also in cases where the storage node set changes (at epoch boundaries) as the new set of storage nodes need to read their slivers by recovering them from the previous set of storage nodes. 4Writer𝑊 could prove consistency among all slivers, but this is overkill for ACDS. 5There may be an extraO( log𝑛) cost depending on the commitment scheme. 3.3 Final design: Red Stuff The encoding protocol above achieves the objective of a low over- head factor with very high assurance, but is still not suitable for a long-lasting deployment. The main challenge is that in a long- running large-scale system, storage nodes routinely experience faults, lose their slivers, and have to be replaced. Additionally, in a permissionless system, there is some natural churn of storage nodes even when they are well incentivized to participate. Both of these cases would result in enormous amounts of data being transferred over the network, equal to the total size of data being stored in order to recover the slivers for new storage nodes. This is prohibitively expensive. We would instead want the system to be self-healing such that the cost of recovery under churn is proportional only to the data that needs to be recovered, and scale inversely with𝑛. To achieve this,Red Stuff encodes blobs in two dimensions (2D- encoding). The primary dimension is equivalent to the RS-encoding used in prior systems. However, in order to allow efficient recovery of slivers of𝐵 we also encode on a secondary dimension.Red Stuff is based on linear erasure coding (see section 2) and the Twin-code framework [31], which provides erasure coded storage with efficient recovery in a crash-tolerant setting with trusted writers. We adapt this framework to make it suitable in the byzantine fault tolerant setting with a single set of storage nodes, and we add additional optimizations that we describe further below. Encoding. Our starting point is the second strawman design that splits the blobs into𝑓+ 1 slivers. Instead of simply encoding repair slivers, we first add one more dimension to the splitting process: the original blob is split into 𝑓 + 1 primary slivers (vertical in the figure) into 2𝑓+ 1 secondary slivers (horizontal in the figure). Figure 2 illustrates this process. As a result, the file is now split into (𝑓+ 1)( 2𝑓+ 1) symbols that can be visualized in an[𝑓+ 1, 2𝑓+ 1] matrix. Given this matrix we then generate repair symbols in both di- mensions. We take each of the 2𝑓+ 1 columns (of size𝑓+ 1) and extend them to𝑛 symbols such that there are𝑛 rows. We assign each of the rows as the primary sliver of a node (Figure 2a). This almost triples the total amount of data we need to send and is very close to what 1D encoding did in the protocol in Section 3.2. In order to provide efficient recovery for each sliver, we also take the initial[𝑓+ 1, 2𝑓+ 1] matrix and extend with repair symbols each of the 𝑓+ 1 rows (of size 2𝑓+ 1) and extend them to 𝑛 symbols (Figure 2b) using our encoding scheme. This creates 𝑛 columns, which we assign as the secondary sliver of each node, respectively. Handling Metadata. For each sliver (primary and secondary), 𝑊 also computes vector commitments over its symbols. For each primary sliver, the commitment commits to all symbols in the expanded row, and for each secondary sliver, it commits to all symbols in the expanded column. As a last step, the client creates a commitment over the list of these sliver commitments, which serves as a blob commitment. These vector commitments for each sliver form the blob meta- data. Using these, nodes can later, when queried for a single symbol, prove that the symbol they return is the symbol originally written. However, these proofs require the opening of the commitments for 4 W alrus: An Efficient Decentralized Storage Network S31 S11 S21 S41 S32 S12 S22 S42 S33 S13 S23 S43 Encode columns: from f+1 to n primary slivers (a) Primary Encoding in two dimensions. The file is split into 2𝑓+ 1 columns and 𝑓 + 1 rows. Each column is encoded as a separate blob with 2𝑓 repair symbols. Then each extended row is the primary sliver of the respective node. S14 S24 S11 S21 S12 S22 S13 S23 Encode rows: from 2f+1 to n secondary slivers (b) Secondary Encoding in two dimensions. The file is split into 2𝑓+ 1 columns and𝑓+ 1 rows. Each row is encoded as a separate blob with 𝑓 repair symbols. Then each extended columns is the secondary sliver of the respective node. Figure 2: 2D Encoding / Red Stuff the respective sliver as well as of the blob commitment w.r.t. the respective sliver commitment. A node that holds all of their slivers can easily recompute the sliver commitment and its openings, but to open the blob commit- ment, all sliver commitments from all nodes are required. If we naively replicate this metadata to every single storage node to enable secure self-healing, we create a large overhead that is quadratic in the number of nodes, since each node needs to store the sliver commitments of all nodes. Especially for small blobs, this can make a large difference in the relative overhead. For example, using 32B hashes in a system of 1000 nodes would require storing an additional 64kB on each node, or 64MB in total. To reduce the overhead, storage nodes maintain an encoded version of the metadata. Since all storage nodes need to get the metadata in full when they invoke a write or recovery process, there is no need for the client to perform the encoding or to do a 2D encoding. Instead, storage nodes can simply locally encode the metadata with an 1D (f+1)-out-of-n encoding and keep the shard assigned to them 6. This reduces the overhead to a constant per node, i.e., from quadratic to linear system-wide overhead. Write protocol. The Write protocol of Red Stuff uses the same pattern as the RS-code protocol. The writer 𝑊 first encodes the blobs and creates a sliver pair for each node. A sliver pair𝑖 is the pair of𝑖th primary and secondary slivers. There are𝑛 = 3𝑓+ 1 sliver pairs, as many as nodes. Then,𝑊 sends all of sliver commitments to every node, along with their respective sliver pair. The nodes check their own sliver in the pair against the commitments, recompute the blob commitment, and reply with a signed acknowledgment. When 2𝑓+ 1 signatures are collected,𝑊 generates a certificate and posts it on-chain to certify the blob will be available. 6They should also compute a commitment and an opening proof of their sliver. In theoretical asynchronous network models with reliable deliv- ery the above would result in all correct nodes eventually receiving a sliver pair from an honest writer. However, in practical protocols the writer may need to stop re-transmitting. It is safe to stop the re-transmission after 2𝑓+ 1 signatures are collected, leading to at least𝑓+ 1 correct nodes (out of the 2𝑓+ 1 that responded) holding a sliver pair for the blob. Read Protocol. The Read protocol is the same as for RS-codes. In order to allow for asychronous challenge nodes only use their secondary sliver. If this is not necessary, we can use the primary sliver and have a faster reconstruction threshold of𝑓+ 1. 𝑅 first collects the metadata, i.e., the list of sliver commitments for the blob commitment. To do so, 𝑅 requests the 1D encoded metadata parts from its peers along with the opening proofs. After the metadata is decoded, 𝑅 checks that the returned set corresponds to the blob commitment. Then𝑅 requests a read for the blob commitment from all nodes and they respond with the secondary sliver they hold (this may happen gradually to save bandwidth). Each response is checked against the corresponding commitments in the commitment set for the blob. When 2𝑓+ 1 correct secondary slivers are collected 𝑅 decodes𝐵 and then re- encodes it to recompute the blob commitment and check that it matches the blob commitment. If it is the same with the one 𝑊 posted on chain then𝑅 outputs𝐵, otherwise it outputs⊥. Sliver recovery. The big advantage of Red Stuff compared to the RS-code protocol is its self-healing property. This comes into play when nodes that did not receive their slivers directly from𝑊 try to recover their sliver. Any storage node can recover their secondary sliver by asking𝑓+ 1 storage nodes for the symbols that exist in their row, which should also exist in the (expanded) column of the requesting node (fig. 3b and fig. 3c). This means that eventually all 2𝑓+ 1 honest nodes will have secondary slivers. At that point, any node can also recover their primary sliver by asking the2𝑓+1 honest nodes for the symbols in their column (Figure 3d) that should also exist in the (expanded) row of the requesting storage node. In each case, the responding node also sends the opening for the requested symbol of the commitment of the source sliver. This allows the receiving node to verify that it received the symbol intended by the writer𝑊 , which ensures correct decoding if𝑊 was honest. Since the size of a symbol isO(|𝐵|𝑛2) each, and each storage node will downloadO(𝑛) total symbols, the cost per node remains at O(|𝐵|𝑛) and the total cost to recover the file is O(|𝐵|) which is equivalent to the cost of a Read and of a Write. As a result by using Red Stuff, the communication complexity of the protocol is (almost7) independent of𝑛 making the protocol scalable. Red Stuff is an ACDS. Section 5 provides proofs that Red Stuff satisfies all properties of a ACDS. Informally, Write Completeness is ensured by the fact that a correct writer will confirm that at least𝑓+ 1 correct nodes received sliver pairs before stopping re- transmissions. And the sliver recovery algorithm can ensure that the remaining honest nodes can efficiently recover their slivers from these, until all honest nodes eventually hold their respective sliver, or can prove that the encoding was incorrect. Validity holds 7Depends on the commitment scheme used. 5 The MystenLabs Team S14 S31 S11 S21 S41 S32 S12 S33 S13 S23 S43 (a) Nodes 1 and 3 collectively hold two rows and two columns S14 S31 S11 S21 S41 S32 S12 S33 S13 S23 S23 S34 (b) Each node sends the intersection of their row/column with the column/row of Node 4 to Node 4 (Red). Node 3 needs to encode the row for this. S14 S24 S31 S11 S23 S41 S32 S12 S22 S42 S33 S13 S23 S43 S34 S44 Recover from f+1 (c) Node 4 uses the𝑓+ 1 symbols on its column to recover the full secondary sliver (Green). It will then send any other recovering node the recovered inter- sections of its column to their row. S14 S24 S31 S11 S23 S41 S32 S12 S22 S42 S33 S13 S23 S43 S34 S44 Recover from 2f+1 (d) Node 4 uses the𝑓+1 symbols on its row as well as all the recovered secondary symbols send by other honest recovering nodes (Green) (which should be at least 2𝑓 plus the 1 recovered in the previous step) to recover its primary sliver (Dark Blue) Figure 3: Nodes 1 and 3 helping Node 4 recover its sliver pair due to the fact that 2𝑓+ 1 correct nodes wil eventually hold correct sliver pairs, and therefore a reader that contacts all nodes will eventually get enough slivers to recover the blob. Read Consistency holds since two correct readers that decode a blob from potentially different sets of slivers, re-encode it and check the correctness of the encoding. Either both output the same blob if it was correctly encoded or both output⊥ if it was incorrectly encoded. 4 The W alrusDecentralized Secure Blob Store W alrusis the integration of a blockchain as a control plane for meta-data and governance, with an encoding and decoding algo- rithm run by a separate committee of storage nodes handling blob data contents. This architecture uses the Red Stuff encoding/de- coding algorithm described in section 3.3, Merkle trees [27] as set commitments, and the Sui blockchain [8] . W alruscan, however, be generalized to any blockchains and encoding/decoding algorithm that satisfies the minimal requirements described in Section 2. We first describe W alrusflows in a single epoch and then we discuss how we allow for storage node dynamic availability through reconfiguration. Finally, we look into going beyond honest-malicius and providing storage challenges. During an epoch, the interactions of W alruswith the clients is through (a) writing a blob and (b) reading a blob. 4.1 Writing a Blob The process of writing a blob inW alruscan be seen in Algorithm 3 and Figure 4. The process begins with the writer (➊) encoding a blob usingRed Stuff as seen in Figure 2. This process yields sliver pairs, a list of commitments to slivers, and a blob commitment. The writer derives a blob id𝑖𝑑𝐵 by hashing the blob commitment with meta-data such as the length of the file, and the type of the encoding. Then, the writer ( ➋) submits a transaction on the blockchain to acquire sufficient space for the blob to be stored during a se- quence of epochs, and to register the blob. The size of the blob and Blockchain N1 N2 N4 N3 User 4 5 3 1 2 build blob id buy space collect acks publish PoA build PoA Figure 4: W alruswrite flow. The user generates the blob id of the file they wish to store; acquire storage space through the blockchain; submit the encoded file to W alrus; collect 2𝑓+ 1 acknowledgements; and submit them as proof of availability to the blockchain. blob commitment are sent, which can be used to rederive𝑖𝑑𝐵. The blockchain smart contract needs to secure sufficient space to store both the encoded slivers on each node, as well as store all metadata associated with the commitments for the blob. Some payment may be sent along with the transaction to secure empty space, or empty space over epochs can be a resource that is attached to this request to be used. Our implementation allows for both options. Once the register transaction commits (➌), the writer informs the storage nodes of their obligation to store the slivers of the blob identified by𝑖𝑑𝐵, sending them the transaction together with the commitments and the primary and secondary slivers assigned to the respective storage nodes along with proofs that the slivers are consistent with the published 𝑖𝑑𝐵. The storage node verifies the commitments and responds with a signed acknowledgment over 𝑖𝑑𝐵 once the commitments and the sliver pairs are stored. 6 W alrus: An Efficient Decentralized Storage Network Finally, the writer waits to collect 2𝑓+ 1 signed acknowledg- ments (➍), which constitute a write certificate. This certificate is then published on-chain (➎) which denotes the Point of A vailability (PoA) for the blob in W alrus. The PoA signals the obligation for the storage nodes to maintain the slivers available for reads for the specified epochs. At this point, the writer can delete the𝑏𝑙𝑜𝑏 from local storage, and go offline. Additionally, this PoA can be used as proof of availability of the𝑏𝑙𝑜𝑏 by the writer to third-party users and smart-contracts. Nodes listen to the blockchain for events indicating that a blob reached its PoA. If they do not hold sliver pairs for this blobs they execute the recovery process to get commitments and sliver pairs for all blobs past their PoA. This ensures that eventually all correct nodes will hold sliver pairs for all blobs. 4.2 Reading a Blob In the read path, a reader may ask any of the storage nodes for the commitments and secondary sliver (1) for a blob by𝑖𝑑𝐵. Once they collect 2𝑓+ 1 replies with valid proofs against 𝑖𝑑𝐵 (2) they reconstruct the blob. Then (3) the reader re-encodes the blob and re-computes a blob id𝑖𝑑′𝐵. If𝑖𝑑𝐵 =𝑖𝑑′𝐵 it outputs the blob, otherwise the blob is inconsistent and the reader outputs⊥. Reads happen consistently across all readers thanks to the prop- erties of Red Stuff. When no failures occur, reads only require downloading sliver data slightly larger than the byte length of the original blob in total. 4.3 Recovery of Slivers One issue with writing blobs in asynchronous networks or when nodes can crash-recover is that not every node can get their sliver during the Write. This is not a problem as these protocols can func- tion without completeness. Nevertheless, in W alruswe opted to use a two-dimensional encoding scheme because it allows for com- pleteness, i.e., the ability for every honest storage node to recover and eventually hold a sliver for every blob past PoA. This allows (1) better load balancing of read requests all nodes can reply to readers, (2) dynamic availability of storage nodes, which enables reconfigu- ration without needing to reconstruct and rewrite every blob, and (3) the first fully asynchronous protocol for proving storage of parts (described in Section 4.6). All these benefits rely on the ability for storage nodes to recover their slivers efficiently. The protocol closely follows the Red Stuff recovery protocols illustrated in Figure 3. When a storage node sees a certificate of a blob for which they did not receive slivers, it tries to recover its sliver pair from the rest of the storage nodes. For this, it requests from all storage nodes the symbols corresponding to the intersection of the recovering node’s primary/secondary sliver with the signatory nodes’ secondary/primary slivers. Given that 2𝑓+ 1 nodes signed the certificate, at least𝑓+ 1 will be honest and reply. This is sufficient for all 2𝑓+ 1 honest nodes to eventually hold their secondary slivers. As a result, when all honest nodes hold their secondary slivers, they can share those symbols corresponding to the recovering nodes’ primary slivers, who will then get to the 2𝑓+ 1 threshold and also recover their primary sliver. 4.4 Handling Inconsistent Encoding from Malicious Writers One last case we need to discuss is when the client is malicious and uploads slivers that do not correspond to the correct encoding of a blob. In that case, a node may not be able to recover a sliver that is consistent with the commitment from the symbols that it received. However, in this case it is guaranteed to generate a third party verifiable proof of inconsistency, associated with𝑖𝑑𝐵. The read process executed by a correct reader rejects any incon- sistently encoded blob by default, and as a result sharing this proof is not a necessity to ensure consistent reads. However agreeing on the inconsistency allows nodes to delete this blobs’ data and excluding it from the challenge protocol (section 4.6). To prove inconsistency, the storage node shares the inconsistency proof— consisting of the symbols that it received for recovery and their inclusion proofs—with the other nodes who can verify it by per- forming a trial recovery themselves. After verifying this fraud proof, the node attests on-chain that𝑖𝑑𝐵 is invalid. After observing a quo- rum of 𝑓+ 1 such attestations, all nodes will subsequently reply with⊥ to any request for the in
프로젝트로 돌아가기