bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 1쪽
Nightshade: Near Protocol Sharding Design 2.0
Alex Skidanov
/♀r/AlexSkidanov
alex@near.org
Illia Polosukhin
/♀r/ilblackdragon
illia@near.org
Bowen Wang
/♀r/BowenWang18
bowen@near.org
July 2019
Updated February 2024
Contents
1 Sharding Basics 4
1.1 Validator partitioning and beacon chains . . . . . . . . . . . . . . 4
1.2 Quadratic sharding . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3 State sharding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Cross-shard transactions . . . . . . . . . . . . . . . . . . . . . . . 7
1.5 Malicious behavior . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Malicious forks . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.2 Approving invalid blocks . . . . . . . . . . . . . . . . . . . 9
2 State V alidity and Data Availability 10
2.1 Validators rotation . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2 State validity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.3 Fishermen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4 Stateless Validation . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.5 Succinct Non-interactive Arguments of Knowledge . . . . . . . . 17
2.6 Data Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.6.1 Proofs of Custody . . . . . . . . . . . . . . . . . . . . . . 20
2.6.2 Erasure Codes . . . . . . . . . . . . . . . . . . . . . . . . 21
2.6.3 Polkadot’s approach to data availability . . . . . . . . . . 21
2.6.4 Long term data availability . . . . . . . . . . . . . . . . . 22
3 Nightshade 23
3.1 From shard chains to shard chunks . . . . . . . . . . . . . . . . . 23
3.2 Consensus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.3 Block production . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.4 Ensuring data availability . . . . . . . . . . . . . . . . . . . . . . 26
3.4.1 Dealing with lazy block producers . . . . . . . . . . . . . 26
3.5 State transition application . . . . . . . . . . . . . . . . . . . . . 27
3.5.1 State Representation . . . . . . . . . . . . . . . . . . . . . 28
1
3.6 Cross-shard transactions and receipts . . . . . . . . . . . . . . . . 29
3.6.1 Receipt transaction lifetime . . . . . . . . . . . . . . . . . 29
3.6.2 Handling too many receipts . . . . . . . . . . . . . . . . . 30
3.7 Chunks validation . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.7.1 Zero-knowledge proofs . . . . . . . . . . . . . . . . . . . . 33
3.8 State Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.9 Snapshots Chain . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4 Conclusion 34
2
Introduction
The past several years have seen significant progress in scaling blockchains. Back
in 2018, when the early team first started to build NEAR Protocol, Ethereum
was one of the only smart contract platforms available to builders and it suffered
from high transaction costs and low throughput. Today, Ethereum is scaling
through rollups (a.k.a. L2s 1). Quite a few other layer 1 blockchains such as
Polkadot, Solana, Sui, and Aptos that promise different kinds of scaling have
launched in the past few years.
In general, most layer-one blockchains use one of two scaling approaches:
vertical scaling and horizontal scaling. For vertical scaling, a few approaches
are explored, including each validator operating more expensive hardware, par-
allelizing transaction execution, separating consensus from execution, etc. Hor-
izontal scaling has two categories: heterogeneous and homogeneous. In the
heterogeneous approach, there are different chains or execution environments
that operate independently and there is usually a main chain that orchestrates
everything and provides security guarantees. In the homogeneous approach, a
blockchain is divided into multiple parallel shards that have the same execution
environment and the protocol dictates how different shards communicate with
each other. Each shard maintains its own state, which allows the blockchain to
scale linearly by adding more shards.
NEAR Protocol chooses a homogeneous sharding approach to build a highly
scalable blockchain. This document outlines the general approach to blockchain
sharding as it exists today, the major problems that need to be overcome (in-
cluding state validity and data availability problems), and presents Nightshade,
the solution NEAR Protocol is built upon that addresses those issues. As of
this writing of the revised version in February 2024, NEAR has been live for
three and half years. There have been a total of 750M transactions and 57M
accounts on chain since the mainnet launch in October 2020.
Since the original publication of the Nightshade whitepaper in July 2019,
there have been a lot of new developments in blockchain protocol research, most
notably zero-knowledge proofs. In the case of NEAR, during the implementation
of Nightshade across different phases over three-plus years, we gained a better
understanding of blockchain scalability and also came to realize some limitations
of the original design. In short, we underestimated the engineering complexity
of fraud proofs in a sharded blockchain and started to question whether that
was still the most promising direction for the protocol. Recent advancements in
stateless validation research provided an alternative path, which not only elim-
inates the critical dependency on fraud proofs, but also significantly increases
per-shard throughput by enabling nodes to hold state in memory. As a result,
we decided to update the Nightshade design to incorporate stateless validation.
This is a revised edition of the Nightshade paper, version 2.0, reflecting this
change in the Nightshade roadmap. We will also elaborate on the power of zero-
knowledge proofs, and how they may be combined with stateless validation to
1Technically a rollup is a type of L2, but the success of rollups has made the two terms
almost synonymous today.
3
produce a future-proof sharding design that is both highly scalable and highly
decentralized. New or heavily modified text is included in section 2.4, section
2.5, section 3.5, section 3.7, and section 3.8.
1 Sharding Basics
Let’s start with the simplest approach to sharding. In this approach, instead
of running one blockchain we will run multiple, and call each such blockchain a
“shard.” Each shard will have its own set of validators. Here, and below, we use
a generic term “validator” to refer to participants that verify transactions and
produce blocks — either by mining, such as in Proof of Work, or via a voting-
based mechanism. For now, let’s assume that the shards never communicate
with each other.
This design, though simple, is sufficient to outline some of the initial major
challenges in sharding.
1.1 Validator partitioning and beacon chains
Say that the system comprises 10 shards. The first challenge is that with each
shard having its own validators, each shard is now 10 times less secure than the
entire chain. So if a non-sharded chain with X validators decides to hard-fork
into a sharded chain, and splits X validators across 10 shards, each shard now
only has X/10 validators, and corrupting one shard only requires corrupting
5.1% (51% / 10) of the total number of validators (see figure 1),
Figure 1: Splitting the validators across shards
which brings us to the second point: who chooses the validators for each shard?
Controlling 5.1% of validators is only damaging if all those 5.1% of validators
are in the same shard. If validators can’t choose which shard they get to validate
4
in, a participant controlling 5.1% of the validators is highly unlikely to get all
their validators in the same shard, heavily reducing their ability to compromise
the system.
Almost all sharding designs today rely on some source of randomness to
assign validators to shards. Randomness on a blockchain is in itself a very chal-
lenging topic and is out of scope for this document. For now let’s assume there’s
some source of randomness we can use. We will cover validator assignment in
more detail in section 2.1.
Both randomness and validator assignment require computation that is not
specific to any particular shard. For that computation, practically all existing
designs have a separate blockchain that is tasked with performing operations
necessary for the maintenance of the entire network. Besides generating random
numbers and assigning validators to the shards, these operations often also
include receiving updates from shards and taking snapshots of them, processing
stakes and slashing in Proof-of-Stake systems, and rebalancing shards (when
that feature is supported). Such chain is called a Beacon chain in Ethereum, a
Relay chain in Polkadot, and the Cosmos Hub in Cosmos.
Throughout this document we will refer to such a chain as a Beacon chain.
The existence of the Beacon chain brings us to the next interesting topic:
quadratic sharding.
1.2 Quadratic sharding
Sharding is often advertised as a solution that scales infinitely with the number
of nodes participating in the network operation. While it is possible in theory
to design such a sharding solution, any solution that includes the concept of
a beacon chain doesn’t have infinite scalability. To understand why, note that
the beacon chain has to do some bookkeeping computation, such as assigning
validators to shards, or snapshotting shard chain blocks, that is proportional to
the number of shards in the system. Since the beacon chain is itself a single
blockchain, with computation bounded by the computational capabilities of its
operating nodes, the number of shards is naturally limited.
However, the structure of a sharded network does bestow a multiplicative
effect on any improvements to its nodes. Consider the case in which an arbitrary
improvement is made to the efficiency of nodes in the network, which will allow
them to process transactions faster.
If the nodes operating the network, including the nodes in the beacon chain,
become four times faster, then each shard will be able to process four times more
transactions, and the beacon chain will be able to maintain 4 times more shards.
The throughput across the system will increase by the factor of 4 × 4 = 16 —
thus the name quadratic sharding.
It is hard to provide an accurate measurement for how many shards are
viable today, but it is unlikely that in any foreseeable future the throughput
needs of blockchain users will outgrow the limitations of quadratic sharding.
5
1.3 State sharding
Until now, we haven’t defined clearly what exactly is and is not separated when
a network is divided into shards. Specifically, nodes in a blockchain perform
three important tasks: not only do they 1) process transactions, they also 2)
relay validated transactions and completed blocks to other nodes and 3) store
the state and the history of the entire network ledger. Each of these three tasks
imposes a growing requirement on the nodes operating the network:
1. The task of processing transactions requires more compute power with the
increasing number of transactions being processed;
2. The task of relaying transactions and blocks requires more network band-
width with the increasing number of transactions being relayed;
3. The task of storing data requires more storage as the state grows. Im-
portantly, unlike the needs for processing power and network bandwidth,
the storage requirement grows even if the transaction rate (number of
transactions processed per second) remains constant.
From the above list it might appear that the storage requirement would be
the most pressing, since it is the only one that is being increased over time
even if the number of transactions per second doesn’t change, but in practice
the most pressing requirement today is the compute power. The entire state
of Ethereum as of this writing is 300GB — easily manageable by most of the
nodes. But the number of transactions Ethereum can process per second is
around 20 - orders of magnitude less than what is needed for many practical
use cases.
Zilliqa is the most well-known project that shards processing but not storage.
Sharding of processing is an easier problem because each node keeps the entire
state, meaning that contracts can freely invoke other contracts and read any data
from the blockchain. Some careful engineering is needed to make sure updates
from multiple shards updating the same parts of the state do not conflict. In
those regards Zilliqa takes a relatively simplistic approach 2.
While sharding of storage without sharding of processing was proposed, it is
extremely uncommon. Thus in practice sharding of storage, or State Sharding,
almost always implies sharding of processing and sharding of network band-
width.
Practically, under State Sharding, the nodes in each shard are building their
own blockchain that contains transactions affecting only the local part of the
global state that is assigned to that shard. Therefore, the validators in each
shard only need to store their local part of the global state and only execute
(and as such only relay) transactions that affect their part of the state. This
partition linearly reduces the requirement on all compute power, storage, and
network bandwidth, but introduces new problems, such as data availability and
cross-shard transactions, both of which we will cover below.
2Our analysis of their approach can be found here: https://medium.com/nearprotocol/
8f9efae0ce3b
6
1.4 Cross-shard transactions
The sharding model we have described so far is not very useful, because if in-
dividual shards cannot communicate with each other, they are no better than
multiple independent blockchains that can’t efficiently communicate. The pro-
liferation of bridges in today’s multichain ecosystem is a clear signal that cross-
chain (or cross-shard) communication is crucial.
For now let’s only consider simple payment transactions, where each partici-
pant has an account on exactly one shard. If someone wishes to transfer money
from one account to another within the same shard, the transaction can be
processed entirely by the validators in that shard. If, however, Alice resides on
shard #1, and wants to send money to Bob who resides on shard #2, neither the
validators on shard #1 (who can’t credit Bob’s account) nor the validators on
shard #2 (who can’t debit Alice’s account) can process the entire transaction.
There are two families of approaches to cross-shard transactions:
• Synchronous: whenever a cross-shard transaction needs to be executed,
all blocks in the relevant shards that contain state transitions related to
the transaction get produced at the same time, and the validators of the
relevant shards collaborate to execute such transactions. 3
• Asynchronous: a cross-shard transaction that affects multiple shards is
executed in those shards asynchronously, the “Credit” shard executing its
half once it has sufficient evidence that the “Debit” shard has executed its
portion. This approach tends to be more prevalent due to its simplicity
and ease of coordination. This system has been proposed today in Cosmos,
Ethereum Serenity, NEAR, Kadena, and others. A problem with this
approach is that if blocks are produced independently, there’s a non-zero
chance that one of the multiple blocks will be orphaned, thus making the
transaction only partially applied. Consider figure 2 depicting two shards,
both of which encounter a fork, and a cross-shard transaction that was
recorded in blocks A and X’ correspondingly. If the chains A-B and V’-X’-
Y’-Z’ end up being canonical in the corresponding shards, the transaction
is fully finalized. If A’-B’-C’-D’ and V-X become canonical, then the
transaction is fully abandoned, which is acceptable. But if, for example, A-
B and V-X become canonical, then one part of the transaction is finalized
and one is abandoned, creating an atomicity failure. We will cover how
this problem is addressed in the proposed protocols in the second part,
when covering changes to the fork-choice rules and consensus algorithms
proposed for sharded protocols.
Note that communication between chains is useful outside of sharded blockchains
too. Interoperability between chains is a complex problem that many projects
are trying to solve. In sharded blockchains the problem is somewhat more
3The most detailed proposal known to the authors of this doc-
ument is Merge Blocks, described here: https://ethresear.ch/t/
merge-blocks-and-synchronous-cross-shard-state-execution/1240
7
Figure 2: Asynchronous cross-shard transactions
straightforward since the block structure and consensus are the same across
shards, and there’s a beacon chain that can be used for coordination. However,
in a sharded blockchain, all the shard chains are the same, while in the global
blockchain ecosystem there are lots of different blockchains, with different target
use cases, levels of decentralization, and privacy guarantees.
Building a system in which a set of chains have different properties but use
sufficiently similar consensus and block structure and have a common beacon
chain could enable an ecosystem of heterogeneous blockchains with a working
interoperability subsystem. Such a system is unlikely to feature validator rota-
tion, so some extra measures need to be taken to ensure security. Both Cosmos
and Polkadot are effectively these types of systems. 4
1.5 Malicious behavior
In this section we will review the adversarial behaviors malicious validators can
exercise if they manage to corrupt a shard. We will review classic approaches
to avoiding corrupting shards in section 2.1.
1.5.1 Malicious forks
A set of malicious validators might attempt to create a fork. Note that it
doesn’t matter if the underlying consensus is byzantine fault tolerant (BFT) or
not; corrupting a sufficient number of validators will always make it possible to
create a fork.
It is significantly more likely that more that 50% of a single shard will be
corrupted, than that more than 50% of the entire network will be corrupted (we
4Refer to this writeup by Zaki Manian from Cosmos: and this Tweet-storm by the first
author of this document: for a detailed comparison of the two.
8
will dive deeper into these probabilities in section 2.1). As discussed in section
1.4, cross-shard transactions involve certain state changes in multiple shards,
and the corresponding blocks in such shards that apply such state changes must
either all be finalized (i.e. appear in the selected chains on their corresponding
shards), or all be orphaned (i.e. not appear in the selected chains on their cor-
responding shards). Since in general the probability of shards being corrupted
is non-negligible, we can’t assume that forks won’t happen, even if byzantine
consensus had been reached among the shard validators, or if many blocks were
produced on top of the block with the state change.
This problem has multiple potential solutions, the most common being oc-
casional cross-linking of the latest shard chain block to the beacon chain. The
fork choice rule in the shard chains is then changed to always prefer the chain
that is cross-linked, and only apply the shard-specific fork-choice rule for blocks
published since the last cross-link.
1.5.2 Approving invalid blocks
A set of validators might attempt to create a block that applies the state tran-
sition function incorrectly. For example, starting with a state in which Alice
has 10 tokens and Bob has 0 tokens, the block might contain a transaction that
sends 10 tokens from Alice to Bob, but ends up with a state in which Alice has
0 tokens and Bob has 1000 tokens, as shown in figure 3.
Figure 3: An example of an invalid block
In a classic non-sharded blockchain, such an attack is not possible, since all
the participants in the network validate all the blocks. A block with such an
invalid state transition will be rejected both by other block producers and non-
block-producing participants in the network. Even if the malicious v프로젝트로 돌아가기