bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 4쪽
.6.1 Receipt transaction lifetime
It is desirable that the receipt transaction should be applied in the block that
immediately follows the block in which it was generated. The receipt transaction
is only generated after the previous block was received and applied by block
producers that maintain the originating shard, and needs to be known by the
time the chunk for the next block is produced by the block producers of the
destination shard. Thus, the receipt must be communicated from the source
shard to the destination shard in the short time frame between those two events.
Let A be the last produced block which contains a transaction t that gener-
ates a receipt r. Let B be the next produced block (i.e. a block that has A as
its previous block) that we want to contain r. Let t be in the shard a and r be
in the shard b.
The lifetime of the receipt, also depicted on figure 18, is the following:
Producing and storing the receipts. The chunk producer cpa for shard
a receives the block A, applies the transaction t, and generates the receipt r. cpa
then stores all such produced receipts in its internal persistent storage indexed
by the source shard ID.
Distributing the receipts. Once cpa is ready to produce the chunk for
shard a within block B, they fetch all the receipts generated by applying the
transactions from block A for shard a, and include them in the chunk for shard
a in block B. Once such a chunk is generated, cpa produces its erasure coded
version and all the corresponding onepart messages. cpa knows which block
producers maintain the full state for which shards. For a particular block pro-
ducer, bp, let Sbp denote the set of shards that bp maintains full state for. Let
R denote the receipts that are results of applying transactions in block A for
shard a that have any shard in Sbp as the destination shard. Then cpa would
include R in the onepart message when they distribute the chunk for shard in
block B to bp.
Receiving the receipts. Remember that the participants (both block pro-
ducers and validators) do not process blocks until they have onepart messages
for each chunk included in the block. Thus, by the time any particular partici-
pant applies the block B, they have all the onepart messages that correspond to
chunks in B, and thus they have all the incoming receipts that have the shards
for which the participant maintains state as their destination. When applying
the state transition for a particular shard, the participant applies both the re-
29
ceipts that they have collected for the shard in the onepart messages, as well as
all the transactions included in the chunk itself.
Figure 18: The lifetime of a receipt transaction
3.6.2 Handling too many receipts
It is possible that the number of receipts that target a particular shard in a
particular block is too large to be processed. For example, consider figure 19, in
which each transaction in each shard generates a receipt that targets shard 1.
By the next block, the number of receipts that shard 1 needs to process is
comparable to the load that all the shards combined processed while handling
the previous block.
To address it we use a technique similar to that used in QuarkChain 12.
Specifically, for each shard the last block B and the last shard s within that
block from which the receipts were applied is recorded. When the new shard is
created, the receipt are applied in order first from the remaining shards in B,
and then in blocks that follow B, until the new chunk is full. Under normal
circumstances with a balanced load it will generally result in all the receipts
being applied (and thus the last shard of the last block will be recorded for
each chunk), but during times when the load is not balanced, and a particular
shard receives disproportionately many receipts, this technique allows them to
be processed while respecting the limits on the number of transactions included.
Note that if such an imbalanced load remains for a long time, the delay from
the receipt creation until the application can continue growing indefinitely. One
way to address this is to drop any transaction that creates a receipt targeting a
shard that has a processing delay exceeding some constant (e.g. one epoch).
12See the whiteboard episode with QuarkChain here: https://www.youtube.com/watch?v=
opEtG6NM4x4, in which the approach to cross-shard transactions is discussed.
30
Figure 19: If all the receipts target the same shard, the shard may not have
the capacity to process them
Consider figure 20. By block B the shard 4 cannot process all the receipts,
so it only processes receipts originating from up to shard 3 in block A, and
records this. In block C the receipts up to shard 5 in block B are included, and
then by block D, the shard catches up, processing all the remaining receipts in
block B and all the receipts from block C.
Figure 20: Delayed receipts processing
31
3.7 Chunks validation
As mentioned in section 3.5, a chunk is validated by a set of stateless validators
assigned to the shard. In this section, we provide a more detailed analysis of the
security of the design. Again, we assume the existence of a on-chain randomness
beacon that can be used to generate random seeds with each block, which then
can be used to shuffle validators.
The core problem here can be formulated as follows: let’s assume a total
of n validators (with equal stake) where at most 1/3 of them are malicious.
There are s shards and k validators are assigned to each shard at every block,
so n = sk. What is the probability of a random assignment of validators to a
shard that results in a shard getting corrupted?
First, it is worth noting that a shard being corrupted means that more than
2/3 of validators assigned to that specific shard are malicious and can perform
an invalid state transition. If less than 2/3 of validators are malicious, it is
still possible for the chunk to be skipped due to insufficient endorsement, but
no invalid state transition is possible. In addition, since validators rotate every
single block, it is not possible for a shard to get indefinitely stalled due to a bad
assignment.
Now let’s consider the probability of a single shard getting corrupted. Let
p denote the probability of a randomly chosen validator being malicious (so
p ≤ 1/3). For a single shard to have l malicious validators, the probability is
hypergeometric distribution:
P (X = l) =
k
l
n−k
k−l
n
k
Therefore, the probability of having more than 2/3 malicious validators for a
single shard is
P (X ≥ 2k/3) ≤ e−D(p+1/3||p)k = e− k3
by Chernoff bound.
For s shards, the probability that at least one shard is corrupted is
Pbad ≤
sX
i=1
P (one shard is corrupted) ≤ se− n3s
When n and k are large, i.e, there are many validators assigned to the
same shard, the last term se− n3s can be made negligbly small. Our numeric
calculation based on multivariate hypergeometric distribution shows that with
800 validators and 4 shards, the probability of the networking getting corrupted
is roughtly 10 −29, which means that in expectation it takes 10 29 blocks for the
system to fail. Assuming one block per second, that translates to 3 × 1021 years.
Therefore, while the security of the system is probabilistic, it is safe enough in
practice.
32
3.7.1 Zero-knowledge proofs
One problem that is often ignored in blockchain design is what happens when the
BFT assumption is violated, i.e, if there are more than 1/3 malicious validators
in a blockchain. Obviously the consensus could be broken and the network may
fail to produce blocks. More importantly, the malicious validators could poten-
tially attempt to create an invalid state transition. In a non-sharded blockchain,
doing this would not only require a higher total stake (2/3 of validators being
malicious), but also it is also very likely to be immediately noticed and a social
consensus may ensue to resolve the attack. This is because the likelihood of
every single validator being corrupted in a non-sharded blockchain is extremely
low; there may also be others running RPC nodes who would notice the invalid
state transition, as well.
In a sharded blockchain, however, things are a bit different. It is more likely
that the validators assigned to a shard could all be malicious and it is less likely
that many people would run nodes that track every shard. This gives rise to the
theoretical possibility of an invalid state transition attack occurring with few
or any participants noticing. The result would be disastrous: a billion tokens
could be minted out of thin air and moved to other shards and potentially even
be bridged to other blockchains.
This is where zero-knowledge proofs (ZKPs) can come in. Since ZKPs are
very cheap to verify, if there is a proof generated for the state transition of each
shard, then a very large number of people can independently verify the state
transition without having to rely on the signatures of validators to trust the
validity of a state transition. More specifically, every wallet could run a ZK full
client that verifies the state transition of the entire blockchain and be assured
that no invalid state transition has happened in the history of the blockchain.
ZKPs also enable a stateless validation design that is simpler and more
powerful than the one described in section 3.7. Instead of validators executing
the chunk using state witness and verifying the state transition, they could
verify one ZKP instead – which is much cheaper. The problem, however, is that
generating a ZKP takes a long time. So if we naively swap out state witness
with a ZKP, it won’t work due to the proof generation latency.
Recent advancements in separating consensus and execution [8] provide a
possible solution: blocks and chunks can be produced and optimistically ex-
ecuted while ZK proofs are being generated. Once a ZKP is generated, it is
submitted into a block for all validators to verify. Because ZKPs can be small
in size and quite cheap to verify 13, they can be included in the blocks directly
and all validators can validate the state transition of all shards14. In this design,
the validators would be much more lightweight, given that they only need to
verify some ZKP. This means that the cost of operating a validator is going to
be much cheaper and that the validator set could be much larger, which further
improves the decentralization of the design.
13While STARK proofs can be relatively large (a few hundred kilobytes), they can be
compressed again using a SNARK which would result in a proof of a few hundred bytes.
14Alternatively, proofs from different shards can be aggregated into one ZKP for a block.
33
3.8 State Size
Sharding allows us to divide the state of the entire blockchain into those of
individual shards, which provides a solution to the state growth problem that
is becoming more and more imminent today. The stateless validation approach
makes the blockchain even more performant: there are relatively few chunk
producers and they can afford to operate more expensive hardware, which means
that for each individual shard, the state of the shard can be held in memory
when chunk producers produce and process chunks. Validators, on the other
hand, receive state witness, which is small in size, when they need to apply a
chunk and can also have the required state in memory. As a result, the state
reads and writes are very fast.
The cost of operating a chunk producer is not going to be exorbitantly high
either. If we limit the size of each shard to 50GB, then a chunk producer could
be operated with a 64GB RAM machine, which is fairly commonplace today.
This asymmetry between chunk producer and validator also works well when
state witness is replaced by ZKPs. Chunk producer could also operate a prover,
which requires more hardware resources and the validators can run on even
cheaper hardware due to the low cost of verifying ZKPs.
3.9 Snapshots Chain
Since the blocks on the main chain are produced very frequently, downloading
the full history might become expensive very quickly. Since the block producers
set is constant throughout the epoch, validating only the first snapshot blocks
in each epoch is sufficient assuming that at no point a large percentage of block
producers and validators colluded and created a fork.
The first block of the epoch must contain information sufficient to compute
the block producers and validators for the epoch.
We call the subchain of the main chain that only contains thesnapshot blocks
a snapshot chain. Such a chain can also be built and validated on Ethereum
inside a smart contract can provides a secure method of cross-chain communi-
cation.
To sync with the NEAR chain, one only needs to download all the snapshot
blocks and confirm that the signatures are correct, and then only have to sync
the main chain blocks from the last snapshot block.
4 Conclusion
In this document, we discussed approaches to building sharded blockchains and
covered two major challenges that come with existing approaches, namely state
validity and data availability. We then presented Nightshade, a sharding design
that powers NEAR Protocol.
The design is a work in progress. If you have comments, questions, or
feedback on this document, please go to https://github.com/near/neps.
34
References
[1] Monica Quaintance Will Martino and Stuart Popejoy. Chainweb: A proof-
of-work parallel-chain architecture for massive throughput. 2018.
[2] Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin. Fraud proofs:
Maximising light client security and scaling blockchains with dishonest ma-
jorities. CoRR, abs/1809.09044, 2018.
[3] Songze Li, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, and Pramod
Viswanath. Polyshard: Coded sharding achieves linearly scaling efficiency
and security simultaneously. CoRR, abs/1809.10361, 2018.
[4] Ittai Abraham, Guy Gueta, and Dahlia Malkhi. Hot-stuff the linear, optimal-
resilience, one-message BFT devil. CoRR, abs/1803.05069, 2018.
[5] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai
Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In
Proceedings of the 26th Symposium on Operating Systems Principles, SOSP
’17, pages 51–68, New York, NY, USA, 2017. ACM.
[6] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget.
CoRR, abs/1710.09437, 2017.
[7] Aniket Kate, Gregory Zaverucha, and Ian Goldberg. Constant-size commit-
ments to polynomials and their applications. pages 177–194, 12 2010.
[8] George Danezis, Eleftherios Kokoris-Kogias, Alberto Sonnino, and Alexan-
der Spiegelman. Narwhal and tusk: A dag-based mempool and efficient BFT
consensus. CoRR, abs/2105.11827, 2021.
35프로젝트로 돌아가기