bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 3쪽
rd transaction), but never distributed the block, honest
validators have no way to craft a challenge.
We will cover three complementary approaches to address this problem.
2.6.1 Proofs of Custody
The most immediate problem to be solved is whether a block is available once
it is published. One proposed idea is to have so-called Notaries that rotate
between shards more often than validators whose only job is to download a
block and attest to the fact that they were able to download it. They can be
rotated more frequently because they don’t need to download the entire state of
the shard — unlike validators, who cannot be rotated as frequently, since they
must download the entire state of the shard each time they rotate (as shown in
figure 13).8
Figure 13: Validators need to download state and thus cannot be rotated
frequently
The problem with this naive approach is that it is impossible to prove later
whether the Notary was or was not able to download the block, so a Notary
can choose to always attest that they were able to download the block without
even attempting to retrieve it. One solution to this is for Notaries to provide
8Here we assume stateless validation is not used, so validators all have to download the
state of a shard.
20
some evidence or to stake some amount of tokens attesting that the block was
downloaded. One such solution is discussed here: https://ethresear.ch/t/
1-bit-aggregation-friendly-custody-bonds/2236 .
2.6.2 Erasure Codes
When a particular light node receives a hash of a block, in order to increase the
node’s confidence that the block is available, it can attempt to download a few
random pieces of the block. This is not a complete solution, because unless the
light nodes collectively download the entire block, the malicious block producers
can choose to withhold the parts of the block that were not downloaded by any
light node, thus still making the block unavailable.
One solution is to use a construction called Erasure Codes to make it possible
to recover the full block even if only some part of the block is available, as shown
in figure 14.
Figure 14: Merkle tree built on top of erasure coded data
Both Polkadot and Ethereum Serenity have designs around this idea that
provide a way for light nodes to be reasonably confident that blocks are available.
The Ethereum Serenity approach has a detailed description in [2].
2.6.3 Polkadot’s approach to data availability
In Polkadot, like in most sharded solutions, each shard (called a parachain) sends
snapshots of its blocks to the beacon chain (called a relay chain). Say there are
2f + 1 validators on the relay chain. The block producers of the parachain
blocks (called collators) compute an erasure coded version of the block that
consists of 2 f + 1 parts, once the parachain block is produced, such that any f
parts are sufficient to reconstruct the block. They then distribute one part to
each validator on the relay chain. A particular relay chain validator would only
21
sign a relay chain block if they have their part of each parachain block that is
snapshotted to the relay chain block. Thus, if a relay chain block has signatures
from 2 f + 1 validators, and as long as no more than f of them have violated
the protocol, each parachain block can be reconstructed by fetching the relevant
parts from the validators that followed the protocol. See figure 15.
Figure 15: Polkadot’s data availability
2.6.4 Long term data availability
Note that all the approaches discussed above only attest to the fact that a block
was published at all, and is available now. Blocks can become unavailable later
for a variety of reasons: nodes going offline, nodes intentionally erasing historical
data, etc.
A whitepaper worth mentioning that addresses this issue is Polyshard’s [3],
which uses erasure codes to make blocks available across shards even if several
shards completely lose their data. Unfortunately their specific approach requires
that all the shards download blocks from all other shards, which is prohibitively
expensive.
Long-term availability is not as pressing an issue; since no participant in the
system is expected to be capable of validating all the chains in all the shards,
the security of a sharded protocol needs to be designed in such a way that the
system is secure even if some of the old blocks in some shards become completely
unavailable.
22
3 Nightshade
3.1 From shard chains to shard chunks
The sharding model with shard chains and a beacon chain is very powerful but
comes with certain complexities. In particular, the fork choice rule needs to be
executed separately in each chain, so therefore the fork choice rule in the shard
chains and the beacon chain must be built differently and tested separately.
In Nightshade we model the system as a single blockchain, in which each
block logically contains all the transactions for all the shards, and changes the
whole state of all the shards. Physically, however, no participant downloads the
full state or the full logical block. Instead, each participant of the network either
maintains the state that corresponds to the shards that they validate transac-
tions for, or relies on others to provide them with state to validate transactions.
The list of all the transactions in the block is split into physical chunks (one
chunk per shard).
Under ideal conditions each block contains exactly one chunk per shard per
block, which roughly corresponds to the model with shard chains in which the
shard chains produce blocks with the same speed as the beacon chain. However,
some chunks might be missing due to network delays, so in practice each block
contains either one or zero chunks per shard. See section 3.3 for details on how
blocks are produced.
Figure 16: A model with shard chains on the left and with one chain with
blocks split into chunks on the right
3.2 Consensus
The two dominant approaches to consensus in blockchains today are longest (or
heaviest) chain, in which the chain that has the most work or stake used to
23
build it is considered canonical, and BFT, in which some set of validators reach
BFT consensus for each block.
In the recently proposed protocols, the latter is the dominant approach, since
it provides immediate finality. In the longest chain approach, more blocks need
to be built on top of a given block to ensure finality. For meaningful security,
the time it takes for a sufficient number of blocks to be built is often on the
order of hours.
Using BFT consensus on each block also has disadvantages, such as:
1. BFT consensus involves a considerable amount of communication. While
recent advances allow consensus to be reached in an interval of time that
is linear to number of participants (see e.g. [4]), it still adds noticeable
overhead per block;
2. It is not feasible for all network participants to participate in BFT con-
sensus for each block; thus, usually only a randomly sampled subset of
participants reaches consensus. A randomly sampled set can, in princi-
ple, be adaptively corrupted, and in theory a fork can be created. The
system either needs to be modelled to be ready for such an event, and
thus still have a fork-choice rule in addition to BFT consensus, or should
be designed to shut down in such an event. It is worth mentioning that
some designs, such as Algorand [5], significantly reduce the probability of
adaptive corruption.
3. Most importantly, the system stalls if 13 or more of all the participants
are offline. Thus, a temporary network glitch or a network split can com-
pletely stall the system. The system ideally should be able to continue
to operate, as long as at least half of the participants are online (heaviest
chain-based protocols continue operating even if fewer than half of the
participants are online, but the desirability of this property is debated
within the blockchain community).
A hybrid model, in which the consensus used is some sort of heaviest chain
approach, but some blocks are periodically finalized using a BFT finality gadget,
maintains the advantages of both models. Such BFT finality gadgets are Casper
FFG [6], used in Ethereum 2.09, Casper CBC, and GRANDPA used in Polkadot.
Nightshade uses heaviest-chain consensus. Specifically, when a block pro-
ducer produces a block (see section 3.3), they can collect signatures from other
block producers and validators, attesting to the previous block. The weight
of a block is then the cumulative stake of all the signers whose signatures are
included in the block. The weight of a chain is the sum of the block weights.
On top of heaviest-chain consensus, Nightshade uses a finality gadget that
uses attestations to finalize the blocks. To reduce the complexity of the system,
we use a finality gadget that doesn’t influence the fork-choice rule in any way.
Instead the gadget only introduces extra slashing conditions such that once a
9Also see the whiteboard session with Justin Drake for an in-depth overview of Casper
FFG, and how it is integrated with GHOST heaviest-chain consensus.
24
block is finalized by the finality gadget, a fork is impossible, unless a very large
percentage of the total stake is slashed. The full details of NEAR’s consensus
algorithm can be found in the Doomslug paper.
3.3 Block production
In Nightshade there are two roles: block producers and validators. At any
point the system contains w block producers, w = 100 in our models, and wv
validators, in our model v = 100, wv = 10, 000. The system is Proof-of-Stake,
meaning that both block producers and validators have some number of internal
currency (referred to as ”tokens”) locked for a duration of time far exceeding the
time they spend performing their duties of building and validating the chain.
As with all the Proof-of-Stake systems, not all the w block producers and
not all the wv validators are different entities, since that cannot be enforced.
Each of the w block producers and the wv validators, however, does have a
separate stake.
The system contains n shards, where n = 100 in our model. As mentioned
in section 3.1, in Nightshade there are no shard chains; instead all the block
producers and validators are building a single blockchain, which we refer to as
the main chain. The state of the main chain is split into n shards, and each
block producer has at any moment only downloaded locally a subset of the state
that corresponds to some subset of the shards, and only processes and validates
transactions that affect those parts of the state. Validators do not maintain
the state of any shard locally, but they do download and verify all the block
headers. They validate chunks using state witness created by chunk producers.
The details of this mechanism will be discussed in section 3.5.
To become a block producer, a participant of the network locks some large
amount of tokens (a stake). The maintenance of the network is done in epochs,
where an epoch is roughly 16 hours. The participants with the w largest stakes
at the beginning of a particular epoch are the block producers for that epoch.
Each block producer is assigned to sw shards, (say sw = 4, which would make
sww/n = 4 block producers per shard). The block producer downloads the
state of the shard they are assigned to before the epoch starts, and throughout
the epoch collects transactions that affect that shard, and applies them to the
state.
For each block b on the main chain, and for every shards, one of the assigned
block producers to s is responsible to produce the part of b related to the shard.
The part of b related to shard s is called a chunk, and contains the list of the
transactions for the shard to be included in b, as well as the Merkle root of the
resulting state. b will ultimately only contain a very small header of the chunk,
namely the Merkle root of all the applied transactions, and the Merkle root of
the final state. When a block producer produces a chunk, they also produce an
associated state witness required to execute the chunk.
Throughout the rest of this document we refer to the block producer that is
responsible for producing a chunk at a particular time for a particular shard as
a chunk producer. A chunk producer is always a block producer and vice versa,
25
this distinction is made to help provide more accurate context when we discuss
block production or chunk production.
Within an epoch, the block and chunk production schedule is determined by
a randomness seed generated at the beginning of the epoch and for each block
height, there is an assigned block producer. Similarly, for each height, there is
an assigned chunk producer for each shard.
Since chunk production, unlike block production, requires maintaining the
state, and for each shard only sww/n block producers maintain the state per
shard, correspondingly only those sww/n block producers are responsible for
producing chunks and associated state witnesses.
3.4 Ensuring data availability
To ensure data availability, Nightshade uses an approach similar to that of
Polkadot described in section 2.6.3. Once a block producer produces a chunk,
they create an erasure coded version of it with an optimal ( w, ⌊w/6 + 1⌋) block
code of the chunk. They then send one piece of the erasure coded chunk (we
call such pieces chunk parts, or just parts) to each block producer.
We compute a Merkle tree that contains all the parts as the leaves, and the
header of each chunk contains the Merkle root of such tree.
The parts are sent to the validators viaonepart messages. Each such message
contains the chunk header, the ordinal of the part, and the part contents. The
message also contains the signature of the block producer who produced the
chunk and the Merkle path to prove that the part corresponds to the header
and is produced by the proper block producer.
Once a block producer receives a main chain block, they first check if they
have onepart messages for each chunk included in the block. If not, the block
is not processed until the missing onepart messages are retrieved.
Once all the onepart messages are received, the block producer fetches the
remaining parts from the peers and reconstructs the chunks for which they hold
the state.
The block producer doesn’t process a main chain block if, for at least one
chunk included in the block, they don’t have the corresponding onepart mes-
sage, or if for at least one shard for which they maintain the state they cannot
reconstruct the entire chunk.
For a particular chunk to be available, it is enough that⌊w/6⌋+1 of the block
producers have their parts and serve them. Thus, for as long as the number of
malicious actors doesn’t exceed ⌊w/3⌋ no chain that has more than half of the
block producers building it can have unavailable chunks.
3.4.1 Dealing with lazy block producers
If a block producer has a block for which a onepart message is missing, they
might choose to still sign on it, because if the block ends up being on-chain, it
will maximize the reward for the block producer. There’s no risk for the block
26
Figure 17: Each block contains one or zero chunks per shard, and each chunk
is erasure coded. Each part of the erasure coded chunk is sent to a designated
block producer via a special onepart message
producer since it is impossible to prove later that the block producer didn’t have
the onepart message.
To address the lazy block producer problem, each chunk producer when
creating a chunk must choose a color (red or blue) for each part of the future
encoded chunk, as well as store the bitmask of assigned color in the chunk
before it is encoded. Each onepart message then contains the color assigned to
the part, and the color is used when computing the Merkle root of the encoded
parts. If the chunk producer deviates from the protocol, it can be easily, since
either the Merkle root will not correspond to onepart messages, or the colors
in the onepart messages that correspond to the Merkle root will not match the
mask in the chunk.
When a block producer signs on a block, they include a bitmask of all the
red parts they received for the chunks included in the block. Publishing an
incorrect bitmask is a slashable behavior. If a block producer hasn’t received a
onepart message, they have no way of knowing the color of the message, and
thus have a 50% chance of being slashed if they attempt to blindly sign the
block.
3.5 State transition application
A chunk producer chooses transactions to include in a chunk, applies the state
transition, and generates state witness along the way when they produce a
chunk. More specifically, when a chunk producer applies a chunk they produces,
they record all the trie nodes visited during the execution. This set of trie nodes
is the state witness for this chunk. The chunk header contains a Merkle root
27
of the Merkleized state after the chunk is applied. 10 The state witness is then
shared with validators assigned to this shard for the next block so that they
could validate the chunk.
A validator only processes a block if:
1. The previous block was received and processed;
2. For each chunk, it receives the onepart message if it is not assigned to the
corresponding shard.
3. For each chunk, it receives the full chunk if it is assigned to the corre-
sponding shard
Once the block is being processed, a validator applies the state transition
of the shard they are assigned to and checks whether the resulting state root
matches what is posted in the chunk header. If they match, the validator sends
an chunk endorsement to the next block producer. Block producers would
only include a chunk in a block if they have more than 2/3 endorsements from
validators assigned to the corresponding shard.
3.5.1 State Representation
In section 2.4, we define state witness as the state touched during the execution
of a chunk, along with a proof that the recorded state pieces indeed belong to
the state as specified by a state root. An important question left unanswered
is how the state is represented. In blockchains where state proofs are required,
their state is usually represented as a Merkle Patricia Trie (MPT). However,
even for MPTs, the branching factor matters for the size of state witness — a
critical component of the stateless validation design. A branching factor of 16 11
means that when the state is full, each branch node will have an overhead of 15
hashes, which is 480 bytes. In comparison, a branching factor of 2, or binary
Merkle trees, only have an overhead of 1 hash, which is 32 bytes, at each branch
node. An analysis shows that based on Ethereum data, the state witness size
can be reduced 40% by switching the state representation to a binary MPT.
Recent research on Verkle Trees shows even more promising results. Verkle
trees only require one 48-byte KZG commitment [7] per level. Therefore Verkle
trees can have a large branching factor (256 - 1024), which results in much
shallower trees and smaller witness sizes. Verkle tree is currently considered to
be the best state representation for stateless validation.
10This is not exactly what is implemented. To allow for an easier upgrade from the pre-
vious version where the previous state root instead of the post state root is stored in the
chunk headers, the implementation is changed to accommodate that. We describe the design
conceptually here to make it easier for readers to understand.
11This is what Ethereum and many other blockchains use as of this writing.
28
3.6 Cross-shard transactions and receipts
If a transaction needs to affect more than one shard, it needs to be consecutively
executed in each shard separately. The full transaction is sent to the first shard
affected, and once the transaction is included in the chunk for such shard and
is applied after the chunk is included in a block, it generates a so-called receipt
transaction, which is routed to the next shard in which the transaction need to
be executed. If more steps are required, the execution of the receipt transaction
generates a new receipt transaction, and so on.
3프로젝트로 돌아가기