Avail 백서

Avail

원문

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