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