bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 2쪽
alidators
continue creating blocks on top of the invalid block faster than honest validators
build the correct chain (thus making the chain with the invalid block longer than
9
the chain without it), every participant using the blockchain for any purpose
validates all the blocks, and will discard all blocks built on top of the invalid
block.
Figure 4: Attempt to create an invalid block in a non-sharded blockchain
In figure 4 there are five validators, three of whom are malicious. They
created an invalid block A’, and then continued building new blocks on top
of it. Two honest validators have discarded A’ as invalid and built on top
of the last valid block known to them, creating a fork. Since there are fewer
validators in the honest fork, their chain is shorter. However, in a classic non-
sharded blockchain, every participant using the blockchain for any purpose is
responsible for validating all the blocks they receive and recomputing the state.
Thus any person with any interest in the blockchain would observe that A’ is
invalid, and thus also immediately discard B’, C’ and D’, taking the chain A-B
as the current longest valid chain.
In a sharded blockchain, however, no participant can validate all the trans-
actions on all the shards, so they need to have some way to confirm that at no
point in the history of any shard of the blockchain was an invalid block included.
Note that unlike with forks, cross-linking to the beacon chain is not a suf-
ficient solution for proving that the blockchain’s history contains no invalid
blocks, since the beacon chain doesn’t have the capacity to validate the blocks.
It can only validate that a sufficient number of validators in that shard signed
the block (and as such have attested to its correctness).
We will discuss solutions to this problem in section 2.2 below.
2 State Validity and Data Availability
The core idea in sharded blockchains is that most participants operating or
using the network cannot validate all blocks in all shards. As such, whenever
10
any participant needs to interact with a particular shard, they generally cannot
download and validate the entire history of the shard.
The partitioning aspect of sharding, however, raises a significant potential
problem: without downloading and validating the entire history of a particular
shard, a participant cannot be certain that the state they interact with is the
result of some valid sequence of blocks and that this sequence of blocks is indeed
the canonical chain in the shard. This is a problem that doesn’t exist in non-
sharded blockchains.
We will first present a simple solution to this problem that has been previ-
ously proposed by many protocols, and then analyze the way this solution can
break and the attempts that have been made to address it.
2.1 Validators rotation
The naive solution to state validity is shown on figure 5: let’s say we assume
that the entire system has on the order of thousands of validators, out of which
no more than 20% are malicious or will otherwise fail (such as by failing to be
online to produce a block). Then if we sample 200 validators, the probability
of more than 1 /3 failing can (for practical purposes) be assumed to be zero.
Figure 5: Sampling validators
1/3 is an important threshold. There’s a family of consensus protocols,
called byzantine fault tolerant (BFT) consensus protocols, that guarantees that
as long as fewer than 1 /3 of participants fail, either by crashing or by acting in
some way that violates the protocol, consensus will be reached.
With this assumed honest validator percentage, if the current set of valida-
tors in a shard provides us with some block, the naive solution assumes that
the block is valid and that it is built on what the validators believed to be
the canonical chain for that shard when they started validating. The validators
learned the canonical chain from the previous set of validators, who by the same
11
assumption built on top of the block which was the head of the canonical chain
before that. By induction the entire chain is valid, and since no set of validators
at any point produced forks, the naive assumption is also that the current chain
is the only chain in the shard. See figure 6 for a visualization.
Figure 6: A blockchain with each block finalized via BFT consensus
This simple solution doesn’t work if we assume that validators can be cor-
rupted adaptively, which is not an unreasonable assumption. 5 Adaptively cor-
rupting a single shard in a system with 1000 shards is significantly cheaper than
corrupting the entire system. Therefore, the security of the protocol decreases
linearly with the number of shards. To be certain about the validity of a block,
we must know that at any point in history no shard in the system has had a
colluding validator majority; taking into consideration adaptive adversaries, we
no longer have such certainty. As we discussed in section 1.5, colluding valida-
tors can produce two basic malicious behaviors: creating forks, and producing
invalid blocks.
Malicious forks can be addressed by blocks being cross-linked to the beacon
chain, which is generally designed to have significantly higher security than
the shard chains. Producing invalid blocks, however, is a significantly more
challenging problem to tackle.
2.2 State validity
Consider figure 7, in which Shard #1 is corrupted and a malicious actor produces
invalid block B. Suppose that in this block B 1000 tokens were minted out of thin
air and deposited in Alice’s account. The malicious actor then produces valid
5Read this article for details on how adaptive corruption can be carried
out: https://medium.com/nearprotocol/d859adb464c8. For more details on adap-
tive corruption, read https://github.com/ethereum/wiki/wiki/Sharding-FAQ#
what-are-the-security-models-that-we-are-operating-under .
12
block C (in a sense that the transactions in C are applied correctly) on top of B,
obfuscating the invalid block B, and initiates a cross-shard transaction to Shard
#2 that transfers those 1000 tokens to Bob’s account. From this moment, the
improperly created tokens reside on an otherwise completely valid blockchain in
Shard #2.
Figure 7: A cross-shard transaction from a chain that has an invalid block
Some simple approaches to tackling this problem are:
1. For validators of Shard #2 to validate the block from which the transaction
is initiated. This won’t work even in the example above, since block C
appears to be completely valid.
2. For validators in Shard #2 to validate some large number of blocks pre-
ceding the block from which the transaction is initiated. Naturally, for
any number of blocks N validated by the receiving shard, the malicious
validators can create N+1 valid blocks on top of the invalid block they
produced.
A promising idea to resolve this issue would be to arrange shards into an
un-directed graph in which each shard is connected to several other shards, and
only allow cross-shard transactions between neighboring shards (for example,
this is how Vlad Zamfir’s sharding essentially works 6, and a similar idea is used
in Kadena’s Chainweb [1]). If a cross-shard transaction is needed between shards
that are not neighbors, such a transaction is routed through multiple shards.
In this design, a validator in each shard is expected to validate all the blocks
in their shard as well as all the blocks in all the neighboring shards. Consider
the figure below with 10 shards, each with four neighbors, where no two shards
require more than two hops for a cross-shard communication — shown on figure
8.
6Read more about the design here: https://medium.com/nearprotocol/37e538177ed9.
13
Figure 8: An invalid cross-shard transaction in a Chainweb-like system that
will get detected
Shard #2 is not only validating its own blockchain, but also the blockchains
of all the neighbors, including Shard #1. So if a malicious actor on Shard #1
attempts to create an invalid block B, then build block C on top of it and initiate
a cross-shard transaction, such a cross-shard transaction will not go through
since Shard #2 will have validated the entire history of Shard #1 which will
have caused it to identify invalid block B.
While corrupting a single shard is no longer a viable attack, corrupting a
few shards remains a potential problem. On figure 9 an adversary corrupting
both Shard #1 and Shard #2 successfully executes a cross-shard transaction to
Shard #3 with funds from an invalid block B by corrupting both shard #1 and
shard #2.
Shard #3 validates all the blocks in Shard #2, but not in Shard #1, and
has no way to detect the malicious block.
There are a few directions towards properly solving state validity: fraud
proofs, stateless validation, and cryptographic computation proofs.
2.3 Fishermen
The idea behind the first approach is the following: whenever a block header
is communicated between chains for any purpose (such as cross-linking to the
beacon chain, or a cross-shard transaction), there is a period of time during
which any honest validator can provide a proof that the block is invalid. There
are various constructions that enable very succinct proofs that the blocks are
invalid, so the communication overhead for the receiving nodes is much smaller
than that of receiving a full block.
With this approach, as long as there is at least one honest validator in the
shard, the system is secure.
14
Figure 9: An invalid cross-shard transaction in a Chainweb-like system that
will not get detected
Figure 10: Fisherman
This is a well-known approach to the state validity problem. This approach,
however, has a few major disadvantages:
1. The challenge period needs to be sufficiently long for the honest validator
to recognize a block was produced, download it, fully verify it, and prepare
the challenge (if the block is in fact invalid). Introducing such a period
would significantly slow down cross-shard transactions.
2. The existence of the challenge protocol creates a new vector of attack as
malicious nodes could spam the network with invalid challenges. An obvi-
15
ous solution to this problem is to make challengers deposit some amount
of tokens that are returned if the challenge is valid. This is only a par-
tial solution, as it might still be beneficial for the adversary to spam the
system with invalid challenges (and burn their deposits) — for example,
to prevent a valid challenge from an honest validator from going through.
These attacks are called Grieving Attacks.
3. The implementation is quite complex and difficult to test. The complexity
comes from two aspects: 1) making sure that a challenge can be properly
processed by validators who do not have the state of the shard and 2)
rolling back the state of the blockchain after a challenge is successfully
processed and slashing the offending validator. The first one is not easy,
as it involves building a lot of the machinery described in section 2.4. The
second one is even more difficult, especially in a sharded blockchain. When
an invalid state transition is found, we cannot just roll back the state of the
affected shard because it is possible for an invalid state transition to mint,
say, 1 billion native or fungible tokens, and send them to other shards.
As a result, the state of all shards needs to be rolled back simultaneously,
which leads to a multitude of problems, especially in regards to consensus
and validator assignment.
Testing challenges is even more daunting. This is a mechanism that is
never expected to trigger in practice yet is crucial to the design – if some-
one finds a vulnerability in the implementation, it is very likely that the
exploit could cause someone to lose money. This is likely the reason why
after quite a few years of the idea being proposed, there is still no full (i.e.,
permissionless) implementation of challenges in any blockchain at the time
of writing.7
2.4 Stateless Validation
One of the core issues mentioned in section 2.1 is the adaptive corruption of
validators in a single shard. This is why the simple solution proposed above
does not work. One possible way to address the issue is to rotate validators very
frequently, e.g. every block. Since we assume that each validator assignment
is the result of a shuffling based on the on-chain randomness beacon, adaptive
corruption won’t work in this case.
However, a core challenge of rotating validators with each block is determin-
ing how validators will retrieve the state to verify the validity of shard blocks,
since they may be assigned to a different shard at every single block. Assuming
fast blocks (˜1s) and a reasonable state size (>10GB), it is not feasible to expect
that a node could download the state of a new shard and validate the new block
within a few seconds.
Stateless validation provides an elegant solution. Instead of maintaining the
full state to execute transactions and validate blocks, a validator is provided a
7Arbitrum implemented fraud proofs but as of this writing, only whitelisted entities can
submit them.
16
state witness to validate a block. State Witness refers to the state touched
during the execution of a chunk alonside with proof that they belong to the
state as of before the chunk. More specifically, assuming that a validator needs
to validate block h and it knows the prev state root sprev, i.e, state root as of
before block h, then a state witness is the state touched during the execution of
h and the proof that they indeed belong to the state specified by sprev. Using
the state witness, a validator can execute and verify blocks without maintaining
the state of that shard locally.
In order for stateless validation to work, some entity needs to be able to
provide state witness. Usually they are part of the overall validator set so that
they have an incentive to maintain the full state. It is worth noting that the state
witness provider, while necessary for the network to function, could not single-
handedly corrupt the network. This is because the state witness is validated
against the state root and even though a single node may be responsible for
producing the state witness, it has no way to produce an invalid state witness
without getting caught.
This property enables a design where most validators are lightweight and
only a few validators need to operate more expensive hardware. This is beneficial
for the decentralization of a blockchain network as it lowers the barrier to entry
to become a validator.
2.5 Succinct Non-interactive Arguments of Knowledge
Another solution to the multiple-shard corruption problem is to use a crypto-
graphic construction that allow participants to prove that a certain computation
(such as computing a block from a set of transactions) was carried out correctly.
Such constructions do exist, e.g. zkSNARKs, zkSTARKs, and a few others, and
some are actively used in blockchain protocols today for private payments —
most notably ZCash. The primary problem with such primitives is that they are
notoriously slow to compute. Despite significant progress made in this area in
the past few years with the emergence of new proving systems and engineering
optimizations, the state-of-the-art zero-knowledge (ZK) proving systems today
such as Polygon Hermez and Risc Zero are about 10,000 times slower than native
execution.
Interestingly, a proof doesn’t need to be computed by a trusted party, since
the proof not only attests to the validity of the computation it is validating, but
also to the validity of the proof itself. Thus, the computation of such proofs
can be split among a set of participants with significantly less redundancy than
would be necessary to perform some trustless computation. It also allows for
participants computing zk-SNARKs to run their processes on special hardware
without reducing the decentralization of the system.
The challenges of zk-SNARKs, besides performance, are:
1. Dependence on less researched and less time-tested cryptographic primi-
tives;
17
2. “Toxic waste” — zkSNARKs depend on a trusted setup in which a group
of people performs some computation and then discards the intermediate
values of that computation. If all the participants of the procedure collude
and keep the intermediate values, fake proofs can be created. zkSTARKs,
however, do not rely on the same underlying cryptographic primitives such
as KZG commitments and therefore do not suffer from the same problem;
3. Extra complexity introduced into the system design. While there are a
few zkEVM rollups in production today, they rely on a single sequencer
and a single prover, which greatly simplifies the design. How exactly ZK
proofs should be integrated into the design of a scalable blockchain is still
mostly a research topic at this point;
4. Generating zk-SNARK proofs can be computationally intensive, especially
for complex computation such as hashing. The computational resources
required for zk proofs inevitably lead to high cost of proof generation,
which poses a barrier for wide adoption.
Despite these challenges, the field of zero-knowledge research is progressing
very rapidly. When this paper was first written in 2019, few people believed
that a production-grade zkEVM would be possible in the next five years. Today,
however, there are multiple zkEVMs (Polygon, Scroll, zkSync, Linea, etc.) live
on Ethereum mainnet. It is not unreasonable to expect that in the next one or
two years, the overhead of zero-knowledge proofs would go down by one or two
orders of magnitude, which would greatly improve their usability in different
applications, including protocol design.
2.6 Data Availability
The second problem we will touch upon is data availability. Generally nodes
operating a particular blockchain are separated into two groups: Full Nodes,
those that download every full block and validate every transaction, and Light
Nodes, those that only download block headers, and use Merkle proofs for the
parts of state and transactions they are interested in, as shown in figure 11.
Now, if a majority of full nodes collude, they can produce a block (valid
or invalid) and send its hash to the light nodes, while never disclosing the full
contents of the block. There are various ways they can benefit from this. For
example, consider figure 12.
There are three blocks: the previous, A, is produced by honest validators;
the current, B, is produced by colluding validators; and the next, C, also will
be produced by honest validators (the blockchain is depicted in the lower right
corner).
Say you are a merchant. The validators of the current block (B) received
block A from the previous validators, computed a block in which you receive
money, and sent you a header of that block with a Merkle proof of the state
in which you have money (or a Merkle proof of a valid transaction that sends
18
Figure 11: Merkle Tree
Figure 12: Data Availability problem
the money to you). Confident that the transaction is finalized, you provide the
service.
However, the validators never distributed the full content of block B to
anyone. As such, the honest validators of block C can’t retrieve the block, and
are either forced to stall the system or to build on top of A — and depriving
you, as a merchant, of money.
When we apply the same scenario to sharding, the definitions of full and
light node generally apply per shard: validators in each shard download every
block in that shard and validate every transaction in that shard, but other
nodes in the system, including those that snapshot shard chains’ state into the
19
beacon chain, only download the headers. Thus the validators in the shard are
effectively full nodes for that shard, while other participants in the system,
including the beacon chain, operate as light nodes.
For the fisherman approach we discussed above to work, honest validators
need to be able to download blocks that are cross-linked to the beacon chain.
If malicious validators cross-linked the header of an invalid block (or used it
to initiate a cross-sha프로젝트로 돌아가기