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프로젝트로 돌아가기