bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 2쪽 중 1쪽
Avail: The Data Availability Blockchain
Avail
ABSTRACT
We study the scalability issue in present blockchain architecture
and propose a design which decouples the data hosting, execution
and verification. We discuss few suitable primitives for the con-
struction of a data hosting layer that guarantees data availability.
We sketch out the system goals, design, security and implementa-
tion details of Avail which is our availability focussed blockchain
solution.
1 PRESENT DAPP ARCHITECTURE
In present day Ethereum-like ecosystems, there are mainly three
types of peers - validator nodes, full nodes and light clients. A
block is appended to the blockchain by a validator node which col-
lects transactions from the mempool, executes them, generates the
block before propagating it across the network. The block contains
a small block header containing digest and metadata related to the
transactions included in the block. The full nodes across the net-
work receive this block and verify its correctness by re-executing
the transactions. The light clients only fetch the block header and
fetch transaction details from neighbouring full nodes on an as-
needed basis. The metadata inside the block header enables the
light client to verify the authenticity of the received transactional
details.
While this architecture is extremely secure and has been widely
adopted, it has some serious practical limitations [ 9]. Because ev-
ery transaction is executed by all the full nodes in the system, it
becomes a bottleneck resulting in limited throughput. With wide
adoption of such DApps, the number of transactions grow rapidly
resulting in increased cost of including a transaction into a block.
To counter these issues, layer 2 solutions have been proposed.
Layer 2 scaling solutions work by creating a chain anchored to
the main chain like Ethereum. In such an architecture, DApps re-
side on the L2 chain and only periodic checkpoints are recorded
on the main chain. The throughput in such a system depends on
the transaction processing rate of the L2 chain whereas any dis-
pute resolution can be performed on the main chain. The benefit
of such a decoupled execution and dispute resolution is that it gives
much higher throughput while retaining the security properties. In
practice, multiple such L2 chains may function in parallel resulting
in improved processing power of the system, while retaining the
security of the main chain.
2 PLASMA, OPTIMISTIC ROLLUP AND ZK
ROLLUP
A major part of a successful layer 2 solution is the execution and
verification framework. Plasma based sidechain approach can pro-
cess thousands of transactions and submit only a single hash as
checkpoint to the main chain. However, it faces an important is-
sue. In case of a dispute on the sidechain, Plasma lacks an effi-
cient mechanisms for users to exit the sidechain. Also, Plasma lacks
the ability to process arbitrary instructions although they are sup-
ported by a quasi Turing-complete main chain like Ethereum.
Optimistic Rollups like Arbitrum and Optimism use the opti-
mistic execution paradigm where a manager/operator executes the
sidechain transactions and submits an assertion on the main chain.
In case of dispute, other participants can challenge the assertion on
chain within a fixed timeout and then the main chain performs the
dispute resolution. While this scales up the transaction processing
rate, it has a few downsides like delayed finality for non-fungible
assets among others.
Zero-knowledge based rollups like Polygon zkEVM and Stark-
ware take the ZK based approach to off-chain execution. The oper-
ators execute the transactions and submit a ZK proof to the main
chain. The main chain can quickly verify the proof and on-chain
participants can be assured that only valid state transitions were
performed.
Another class of rollup is Validium which is a hybrid between
Plasma and ZK based rollups. They make use of Zero-knowledge
based proofs of execution and at the same time keep the transac-
tional data off-chain. Although this improves the throughput of the
system, they suffer similar problems to that of Plasma. User funds
can be frozen or seized and other crypto-economic attacks are also
possible on such a system. [5] provides a detailed discussion on the
approach and possible attacks.
While there is still debate inside the community about which
of these approaches is the best, we envision multiple such roll-ups
operating simultaneously together forming the execution layer of
our design.
3 THE DATA A V AILABILITY PROBLEM
While the off-chain execution based architecture improves through-
put, it is still limited by the amount of data that the main chain like
Ethereum can handle. This is because although the execution is
off-chain, the verification or dispute resolution is strictly on-chain.
The transactional data is submitted as calldata on Ethereum to en-
sure that the data is available for future reconstruction. This is ex-
tremely important. In case of optimistic rollups, the operator may
submit invalid transactions and then suppress parts of the block
to the world. This way, the other full nodes in the system will
not be able to verify whether the submitted assertion is correct.
Due to lack of data, they will not be able to produce any fraud
proof/challenge to show that the assertion is indeed invalid. In case
of Zero-knowledge based rollups, the ZKP soundness ensures that
accepted transactions are valid. However, even in the presence of
such guarantees, not revealing the data backing a transaction can
Avail
have serious side effects. It may lead to other validators not be-
ing able to calculate the current state of the system. [ 3] contains a
detailed discussion on the subject.
We recognize that to achieve higher throughput, we not only
need to put execution off-chain but also need to have a scalable
data hosting layer that guarantees data availability. In later sec-
tions we discuss a design of such a decentralized Data Availability
layer.
4 SYSTEM OVERVIEW
4.1 Decoupling the components
On a high level, a successful blockchain design needs to address
the following components:
• Data Hosting and Ordering: This component would re-
ceive transactional data and order it without any execution.
It would then store the data and ensure complete data avail-
ability in a decentralized manner. We call this component
the DA layer.
• Execution: The execution component should take ordered
transactions from the DA layer and execute them. It should
create a checkpoint/assertion/proof and submit it to theDR
layer. We call this the Exec layer.
• Verification/Dispute Resolution: This component rep-
resents the settlement layer to which the system is anchored.
The security of the design is dependent on the robustness
and security properties of this component along with the
DA layer. The checkpoint or assertion or proof submitted
by Exec layer is processed by this layer to guarantee that
only valid state transitions are accepted in the system (pro-
vided that the data is available). We refer to this component
as the DR layer.
In this work, we are proposing Avail, which acts as the DA layer.
We envision the multiple roll-up initiatives or legacy execution lay-
ers to form the Exec layer. The DR layer can be any secure settle-
ment layer which supports the execution verification.
4.2 Participants and System Goals
4.2.1 Types of Nodes. We consider the following types of nodes
for Avail:
• Full Nodes: The full nodes download the blocks and vali-
date their correctness but do not participate in consensus.
They store the blockchain but are not incentivized to par-
ticipate or remain honest.
• Validator Nodes: The validator nodes take part in block
generation and decide on transaction inclusion and order-
ing. These nodes are incentivized to participate in consen-
sus and host the blockchain. Essentially, they are also full
nodes with stake in the system.
• Light Clients: These are clients with resource constraints
who have access to only the block header and query trans-
actional data from other full nodes on an as-needed basis.
They want to have high confidence that the block is avail-
able, and when querying data they want a proof that the
data belongs to the block.
4.2.2 System Goals. Our design for Avail should provide the fol-
lowing guarantees:
(1) The decentralized data availability blockchain keeps pro-
ducing a canonical chain of blocks even in the presence of
an adversary that controls < 13 of the validator nodes in the
network.
(2) The honest participants of the system with access to the
canonical chain of block headers will not accept a block
whose underlying data is unavailable even if a very power-
ful adversary is controlling all the other nodes in the sys-
tem. Under the assumption that there are enough honest
participants, the data should remain available for a limited
amount of time.
We want to guarantee achieving both these system goals. We want
to emphasize that both the goals have different adversarial assump-
tions. Goal 1 ensures that the blockchain system continues to func-
tion in a decentralized manner as long as a super-majority of val-
idator nodes remain honest. Goal 2 ensures that an outside partici-
pant like an application running a light node, who has access to the
canonical chain of block headers, need not trust any full node to
have the guarantee that the underlying data for a particular block
is available. This is an extremely strong assumption which elim-
inates any trust assumption to detect data hiding attempt. In the
next sections we discuss our construction ideas and argue that they
achieve these goals.
5 DESIGNING THE DATA A V AILABILITY
LAYER
5.1 Primitives
5.1.1 Why is redundancy important in ensuring Data Availability?
Suppose we have a block 𝐵 divided into data chunks 𝐷1, . . . , 𝐷𝑛.
The block producer wants to suppress one chunk. Without loss of
generality, let us assume that the first chunk is hidden by the block
producer. Clients can query one chunk at random to get guarantees
that data is indeed available. It can repeat this process many times
so as to get sufficient confidence that the data is accessible. Hence,
for each query, the block producer needs to be lucky enough that
𝐷1 is not queried.
However, with redundancy included by schemes like erasure
coding, suppose the 𝑛 chunks are encoded into 2𝑛 chunks. Erasure
coding ensures that any 𝑛 out of the 2𝑛 chunks are sufficient to
recreate the data. This makes the hiding task harder for the block
producer. To hide one particular chunk, it needs to make at least
𝑛 + 1 chunks unavailable. As a client, querying constant number
of times gives a very high confidence that the data is indeed avail-
able. Hence, redundancy plays a vital role in the data availability.
An erasure coding based design along with the related tradeoffs
are discussed in [ 1].
5.1.2 FraudProofs. In the previous section although we discussed
the advantage of redundancy in data, we omitted the case when the
erasure coded chunks are misconstructed by the block producer.
In these cases, even though most chunks are indeed available, the
entire block data might not be accessible. Hence, fraud proofs are
constructed by other full nodes in the system and propagated to
Avail: The Data Availability Blockchain
the light nodes. The light nodes verify the fraud proof and get con-
vinced that the received block header is that of an erroneous block.
An interesting property of fraud proofs is that they function even
under a minority honest assumption. This is because having a sin-
gle honest full node as a neighbour is sufficient for an honest light
node to be guaranteed that it receives the fraud proof.
An important factor to consider during design of DA layer is the
size of fraud proofs. In simple erasure coded chunks, to proof that
the encoding is incorrect, the entire original data block needs to
be propagated to the light client. Hence, the fraud proof size is at
least linear to the size of the block. Although we do not discuss the
higher dimensional erasure coding based design here, we refer to
[1] for a detailed analysis of fraud proof sizes.
5.1.3 CommitmentSize. In a one dimensional erasure coding based
design, once a block producer selects data chunks 𝐷1, . . . , 𝐷𝑛, it en-
codes the chunks to generate 𝐷1, . . . , 𝐷2𝑛 (assuming coding rate to
be 0.5). It then constructs a Merkle tree over the chunks and keeps
the root of it in the block header which acts as the commitment.
A light client fetching 𝐷𝑖 gets a Merkle membership proof along
with the data chunk so that it can quickly verify that a legitimate
chunk has been supplied. The commitment (root of Merkle tree)
size is an important factor to consider in any design. With large
commitments, block headers become larger resulting in increased
network traffic. While higher dimensional erasure coding based
schemes achieve shorter fraud proof size, it comes at the cost of
larger commitments.
5.2 Coded Merkle Tree based Design
We briefly discuss the Coded Merkle Tree (CMT) based approach [10]
proposed by Yu et al. The novelty of this approach is that it gives
constant sized commitments with logarithmic sized fraud proofs.
The design uses systematic erasure codes at each layer of the
Merkle tree. In particular, at the base layer, it takes 𝑘 data chunks
and extends it to 𝑛 data chunks in such a manner that the first𝑘 out
of 𝑛 chunks are the original chunks and the rest are parity symbols.
Each chunk in the next layer of the tree is made from hashes of 𝑞
chunks of the previous layer. Similar systematic erasure code is ap-
plied on that layer as well and we keep building successive levels of
the tree until we have 𝑡 hashes which we keep as the commitment
inside the block header.
When a light node samples a base layer chunk, the chunk along
with a Merkle membership proof is given in such a manner that
not only availability of base layer is ensured but also the higher
layer availability is guaranteed. A light client sampling 𝑠 base layer
chunks the Merkle membership proof will automatically sample 𝑠
intermediate layer chunks with high probability.
For a full client, decoding the tree and generation of fraud proof
is also extremely efficient. With access to the root layer of the CMT
present in the header and some coded chunks of the previous layer,
the hash-aware peeling decoder decodes the previous layer getting
access to all the hashes of the preceding layer. The decoder con-
tinues until all the chunks in the base layer is decoded or it finds
evidence of an incorrect coding. In case of the former, the full node
gets access to the entire data and in case of the latter, it generates
the fraud proof and broadcasts it.
A detailed description of the construction along with perfor-
mance analysis is present in [ 10].
5.3 Kate Commitment based Design
In this section we first discuss polynomial commitments proposed
by Kate et al. [6]. Then we go on to discuss a DA layer design based
on Kate commitments as proposed in [ 4].
Given a polynomial 𝜙 (𝑥) ∈ Z𝑝 [𝑥] over a bilinear pairing group,
Kate et al. proposed a scheme to have a commitment to the polyno-
mial using a single group element. Moreover, the scheme supports
opening of a commitment at a point 𝑖 to get 𝜙 (𝑖) using constant
sized witness that allows a verifier to confirm that 𝜙 (𝑥) was in-
deed evaluated at 𝑖 to get 𝜙 (𝑖). The commitment scheme is both
computationally hiding and binding. The commitment scheme is
additively homomorphic and supports a single witness for a batch
of openings on multiple points of the same polynomial.
Given such a scheme, the block producer breaks the block data
into chunks such that each chunk is an element of the field. It ar-
ranges the chunks into n rows and m columns such that it forms an
𝑛 × 𝑚 matrix 𝐷. It uses the evaluation form to construct a polyno-
mial from each row to obtain 𝜙1 (𝑥), . . . , 𝜙𝑛 (𝑥). It then commits
each polynomial to get 𝐶1, . . . , 𝐶𝑛 respectively. For redundancy,
it extends 𝐶1, . . . , 𝐶𝑛 to 𝐶1, . . . , 𝐶2𝑛. It puts 𝐶1, . . . , 𝐶2𝑛 inside the
block header and broadcasts it. Figure 1 shows the data arrange-
ment and the corresponding commitments.
Figure 1: Data Arrangement in Kate Commitment based DA
layer
The light clients querying a data block will sample some chunk
𝐷 [𝑖] [𝑗]. Along with the data, the light client gets a witness𝑤 [𝑖] [𝑗]
and it can immediately verify the validity using the Kate Commit-
ment scheme discussed above. If it queries multiple chunks of the
same row, the batch commitment scheme helps have a single wit-
ness for all the sampled points. Hence the membership proofs are
extremely efficient.
For full nodes, the system can have two types of full nodes: 1.
classical full nodes having entire block, 2. Column full nodes which
Avail
keep only a single column of the data. For classical ones, it takes
the entire matrix 𝐷, extends each column to 2𝑛 points and getting
an extended matrix 𝐷′.
It then verifies for each row of 𝐷′ whether the commitment to
𝑖𝑡ℎ row is 𝐶𝑖 for 1 ≤ 𝑖 ≤ 2𝑛.
For the column full nodes, they can fetch and keep only a col-
umn of the matrix 𝐷. They would extend each column to check
whether they belong to the extended set of commitments. This is
possible because of the homomorphic nature of the commitments
and witnesses. In particular, having𝐷 [1] [𝑗], . . . , 𝐷[𝑛] [𝑗] and 𝑤 [1] [𝑗],
. . . , 𝑤[𝑛] [𝑗], the node can extend both to 2𝑛 points and immedi-
ately verify whether the extended openings are valid. If the num-
ber of such column full node is 𝑂 (𝑚), and each column full node
ensures at least one column is available, then collaboratively the
entire data is available within the column full nodes.
As the block size grows, so does the number of commitments
(keeping number of columns fixed, the number of rows grow). Hence
the commitment size grows linear to that of the block size. How-
ever, we do not need any fraud proofs in such a system. For each
light client, the communication and computational overhead is con-
stant. For each full node, the computational overhead is 𝑂 (𝑚 ∗
𝑛𝑙𝑜𝑔 (𝑛)) as it needs to perform 𝑂 (𝑚) FFTs, 𝑂 (1) for each column,
along with some pairing checks for verification. However, a col-
umn node has to only perform 𝑂 (𝑛𝑙𝑜𝑔 (𝑛)) work because it works
on a single column of data.
6 ANALYSIS
6.1 Attack Vectors
Any DA layer needs to counter the following attacks on data avail-
ability:
(1) A super-majority of the validators in the DA layer wants
to change the ordering of an already finalized block.
(2) A super-majority of the validators create a wrong block
header, i.e., the commitment of the data present in the header
is wrong.
(3) A super-majority of the validators want to hide at least one
chunk of the block. For a light node, this would mean not
being able to detect hiding of data with a non-negligible
probability. For a full node, this would mean not being able
to reconstruct the data.
We take the case of the super-majority of validators attacking
the DA layer because we want to minimize honesty assumption
required for our design.
Under the assumption that finality is reached, the reordering
attack (attack 1) is hard to mount. This is because, to successfully
mount this attack the attacker would need to break the non-equivocation
property of the underlying consensus. In particular, the finality
layer ensures that if equivocation occurs, the dishonest parties can
be identified and their stake slashed.
In the subsequent sections we show how Attack 2 and Attack
3 is countered in each of the two design choices - CMT and Kate
Commitments.
6.2 Coded Merkle Trees
In the CMT based approach, the block proposer(s) may attempt to
construct wrong header in two ways:
• The erasure coding in one or more layers is wrong.
• The Merkle tree construction is wrong.
In both cases, the fraud proof captures such an attack. A full
node, with access to the data, can build the incorrect-coding proof
and broadcast it for the light clients. [ 10] contains프로젝트로 돌아가기