Avail 백서

Avail

원문

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]
프로젝트로 돌아가기