bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 2쪽 중 2쪽
a detailed de-
scription of such a fraud proof.
The random sampling from base layer by a light client also sam-
ples higher layers. As each layer is erasure coded, hence, proba-
bility of hiding any chunk from any of the layers of the Merkle
tree is extremely low for sufficiently many samplings. A full client
who wants to reconstruct the Merkle tree needs access to the block
header which contains the root hashes. Along with that, it needs
(1−𝛼)𝑛 samples of the each layer, where𝑛 is the total chunks in the
layer and 𝛼 is the minimum fraction of coded symbols a malicious
block producer needs to make unavailable to prevent full decod-
ing. With these information it can decode the entire tree. The en-
tire decoding strategy along with the hash-aware peeling decoder
construction is given in [ 10].
Hence, the CMT approach can mitigate both attack 2 and 3. We
however note that the mitigation assumes a single honest full node,
which is not as strong as Goal 2 defined in Section 4.2.2.
6.3 Kate Commitments
In the Kate commitment based approach, attack 2 amounts to a
wrong commitment by the block producer. Without loss of gen-
erality, suppose 𝐶1 is wrong. This would mean that at least one
out of 𝐷 [1] [1] to 𝐷 [1] [𝑛] does not belong to 𝐶1. Again, let us
assume 𝐷 [1] [1] ∉ 𝐶1. This would mean that at least one of this
is true: 𝐷 [𝑛 + 1] [1] ∉ 𝐶𝑛+1, . . . , 𝐷[2𝑛] [1] ∉ 𝐶2𝑛. This is because
𝐶𝑛+1, . . . , 𝐶2𝑛 are extended from𝐶1, . . . , 𝐶𝑛 and 𝐷 [𝑛+1] [1], . . . , 𝐷[2𝑛] [1]
are extended from 𝐷 [1] [1], . . . , 𝐷[𝑛] [1]. Hence, such an attack is
caught by a light client with overwhelming probability.
In case of attack 3, a light client querying constant samples can
achieve arbitrarily high confidence that the data is indeed available.
This is due to the redundancy in the data as discussed previously.
For a full node, it needs to download the at least 𝑛 chunks from
each column so that it can reconstruct the entire extended data. It
checks the commitments to know whether the downloaded data
is correct. A column full node needs to perform similar operations
but only for one column of data. Even if the supermajority wants
to suppress data after some time, the light client P2P layer contains
the data with redundancy. This enables new clients to recover block
data without reliance on the full nodes or validators.
Hence, this approach mitigates all discussed attacks and achieves
the goals set in Section 4.2.2.
7 IMPLEMENTATION
In this section, we discuss the implementation details of Avail. Among
the two techniques discussed above, we use the Kate commitment
based approach in order to avoid fraud proofs and provide strong
data availability guarantees even in presence of powerful adver-
saries.
Avail: The Data Availability Blockchain
7.1 Consensus
We need our validators to reach consensus on the next block which
contains the ordered set of transactions along with redundant era-
sure coded data. Although there exists many possible blockchain
consensus protocols, we opted for the Proof-of-Stake (PoS) family
of consensus algorithms. We wanted a PoS consensus that supports
high number of validators, provable finality and a robust security
framework. In particular, we chose the BABE/GRANDPA hybrid
consensus used by Polkadot [ 7]. It uses two separate protocols for
block production and finality.
The block production is done using Blind Assignment for Blockchain
Extension protocol (BABE) [2]. The block producers produce blocks
based on a Verifiable Random Function (VRF). The protocol does
not assume access to a central clock. In case no validator is chosen
as the block producer for a particular slot, or if the chosen pro-
ducer(s) go down, there is a secondary block producer who can
step in. BABE ensures liveness which guarantees that transactions
submitted to honest players will eventually be inserted into the
chain.
GRANDPA (GHOST-based Recursive ANcestor Deriving Prefix
Agreement) [8] is a finality gadget ensuring provable finality. With-
out the finality gadget, the users can only have probabilistic fi-
nality, like in classical blockchain systems. GRANDPA guarantees
that blocks reach quicker finality and a finalized block can never
be reverted.
7.2 Full Nodes
To implement our design in a standalone blockchain, we use the
Substrate framework 1. Substrate provides great flexibility to im-
plement custom runtime logic with inherent BABE/GRANDPA con-
sensus support. Our design needed major changes in the Substrate
codebase and hence we worked on a separate codebase 2. The ma-
jor changes that we made are:
• The contents of the block are arranged into the data ma-
trix, extended and polynomial commitment generation is
performed during the block building process.
• The header structure is changed to contain the commit-
ments as part of the header.
• Block sizes are made dynamic, according to the number
of transactions on the mempool. However, the maximum
block size allowed is 4 MB, including the data redundancy.
• Additional RPC methods to support data availability queries
are introduced. These can be used by light clients to gain
confidence about availability and inclusion.
We have modified the Polkadot Apps3 to build our block explorer 4
for our test network.
7.3 Light Client
In our present design, light clients are nodes that participate in the
system without investing resources to host a full node. We want
our light clients to have very high data availability guarantees
1https://github.com/paritytech/substrate
2https://github.com/availproject/avail
3https://github.com/availproject/avail-apps
4https://testnet.avail.tools/
without hosting a full node or trusting on any other peer. Keep-
ing this in mind, we have developed a light client 5 which keeps
track of the chain header and performs availability queries to gain
confidence on the availability of interested blocks. They also help
contribute to data availability by hosting sampled data for other
light clients within the P2P network. The client can gain as high
confidence as deemed suitable for the specific application. We en-
visage the applications using our chain to host a light client.
7.4 Ethereum Data Availability Guarantees
A DR layer layer like Ethereum, when validating proofs or resolv-
ing dispute, need assurance that the underlying data is indeed avail-
able (as discussed in Sec 2). To enable this in an organic manner, we
want to guarantee data availability to a smart contract on Ethereum
(or any settlement layer which supports this logic). This allows the
checkpoint/assertion/proof accepting smart contract to communi-
cate with this light client contract and directly get DA assurance.
We discuss three main approaches on how to provide the on-
chain DA guarantee. We also briefly mention their advantages and
limitations.
7.4.1 DataAvailabilityOracle. A widely accepted approach for off-
loading expensive tasks from smart contracts is the oracle based
approach. When on-chain DA guarantee for a particular block is
needed, multiple oracle nodes can be incentivized to submit their
respective confidence factors. The on-chain contract can aggregate
the metrics to decide whether it has sufficient guarantee that the
data is available. Although well-accepted within the community,
this approach has to trust the oracle nodes resulting in reduced
security guarantees. The amount of trust can be limited by proper
incentivization and decentralization.
Proof of Concept Implementation : To emphasize the viabil-
ity of the protocol, we have implemented an on-chain light client
using Chainlink Oracle Network, based on the second design dis-
cussed above. Whenever the on-chain contract needs availability
guarantee for a particular block, it requests the on-chain Chainlink
Oracle which uses events to communicate with multiple off-chain
oracle nodes. These off-chain nodes use their own light clients or
hosted instances to gain confidence and communicate the same
back to the original contract through the Chainlink Oracle. The
incentivization is handled using the LINK token.
7.4.2 Bridges. A well-known approach for cross-chain message
passing is using bridges. Using a bridge from Avail to DR layer, the
validators of Avail can attest to the fact that a particular piece of
data is available. The downside of such approach is that it relies
on the supermajority of the Avail validator set to be honest and
to keep the data available. For most applications, this is a good
enough assumption.
Under this model, the rollup operator submits the data on Avail
and gets back a finalized block post transaction inclusion. It com-
putes a proof of transaction inclusion within that block and posts it,
along with proof of transactional validity, to the settlement rollup
contract. The bridge operator(s), on the other hand, post finalized
block metadata on the settlement layer. The rollup contract, upon
receiving the proofs, checks the correctness of proofs against the
5https://github.com/availproject/avail-light
Avail
bridge contract. The rollup transaction is accepted iff the proofs
are verified to be correct.
8 ADDITIONAL MODULES
8.1 Application Specific Data Retrieval
We would want our construction to allow applications to download
data which is only relevant to them. To enable this, we want the
full nodes to prove to an application client that the complete set of
data relevant to the application has been communicated.
To enable Application Specific Data Retrieval (ASDR), we have
introduced two main fields:
• AppID: Every transaction has been associated with an ap-
plication identifier (appID). We envision rollup or applica-
tion specific chains to register as applications if they want
to download parts of block with only relevant application
data. Any user is free to use the default appID ‘0’ which
is used for all types of transaction, including Avail system
transactions. Any transaction with nonzero appID has to
be of type application data submission only.
• appDataLookup: Every block header contains an index
field, containing the starting cell indices of application cells
inside the block. This is created by the block producer when
creating the block by grouping the data matrix by appID
and then flattening it to infer the starting position of each
group.
The changes above together ensure that an application client
can download only app-specific cells without downloading other
application data.
However, it is worth noting that there is no reliance on the block
producer to create the index or group the data correctly. This is
because, we create a deterministic algorithm that all honest appli-
cation clients follow. Hence, all honest clients would retrieve the
same app data for a particular appID. It can happen that clients
get partial data, i.e., there exists data within the block associated
with an appID which was not downloaded following the algorithm.
However, the aim is to have the same view of their app to all hon-
est app clients by providing them with same data. The polynomial
commitments inside header assure that two clients with access to
the same header cannot receive different sets of data.
REFERENCES
[1] Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin. 2019. Fraud and Data
Availability Proofs: Maximising Light Client Security and Scaling Blockchains
with Dishonest Majorities. arXiv: 1809.09044 [cs.CR]
[2] Handan Kilinc Alper. 2020 (accessed December 18, 2020). BABE. https:
//research.web3.foundation/en/latest/polkadot/block-production/Babe.html
[3] Vitalik Buterin. 2018 (accessed November 24, 2020). A note on data availabil-
ity and erasure coding. https://github.com/ethereum/research/wiki/A-note-on-
data-availability-and-erasure-coding
[4] Vitalik Buterin. 2020 (accessed November 24, 2020). 2D data availability
with Kate commitments . https://ethresear.ch/t/2d-data-availability-with-kate-
commitments/8081
[5] Alex Gluchowski. 2020 (accessed November 24, 2020). zkRollup vs. Validium .
https://medium.com/matter-labs/zkrollup-vs-validium-starkex-5614e38bc263
[6] Aniket Kate, Gregory M. Zaverucha, and Ian Goldberg. 2010. Constant-Size
Commitments to Polynomials and Their Applications. In Advances in Cryptol-
ogy - ASIACRYPT 2010 , Masayuki Abe (Ed.). Springer Berlin Heidelberg, Berlin,
Heidelberg, 177–194.
[7] Polkadot. 2020 (accessed December 18, 2020). Polkadot Consensus. https://wiki.
polkadot.network/docs/en/learn-consensus
[8] Alistair Stewart and Eleftherios Kokoris-Kogia. 2020. GRANDPA: a Byzantine
Finality Gadget. arXiv: 2007.01560 [cs.DC]
[9] David Tse. 2020 (accessed November 24, 2020). Stanford Engineering - EE374:
Scaling Blockchains . https://web.stanford.edu/class/archive/ee/ee374/ee374.
1206/
[10] Mingchao Yu, Saeid Sahraei, Songze Li, Salman Avestimehr, Sreeram Kannan,
and Pramod Viswanath. 2019. Coded Merkle Tree: Solving Data Availability
Attacks in Blockchains. arXiv: 1910.01247 [cs.CR]프로젝트로 돌아가기