NEAR Protocol 백서

NEAR Protocol

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 4쪽 중 4쪽

.6.1 Receipt transaction lifetime It is desirable that the receipt transaction should be applied in the block that immediately follows the block in which it was generated. The receipt transaction is only generated after the previous block was received and applied by block producers that maintain the originating shard, and needs to be known by the time the chunk for the next block is produced by the block producers of the destination shard. Thus, the receipt must be communicated from the source shard to the destination shard in the short time frame between those two events. Let A be the last produced block which contains a transaction t that gener- ates a receipt r. Let B be the next produced block (i.e. a block that has A as its previous block) that we want to contain r. Let t be in the shard a and r be in the shard b. The lifetime of the receipt, also depicted on figure 18, is the following: Producing and storing the receipts. The chunk producer cpa for shard a receives the block A, applies the transaction t, and generates the receipt r. cpa then stores all such produced receipts in its internal persistent storage indexed by the source shard ID. Distributing the receipts. Once cpa is ready to produce the chunk for shard a within block B, they fetch all the receipts generated by applying the transactions from block A for shard a, and include them in the chunk for shard a in block B. Once such a chunk is generated, cpa produces its erasure coded version and all the corresponding onepart messages. cpa knows which block producers maintain the full state for which shards. For a particular block pro- ducer, bp, let Sbp denote the set of shards that bp maintains full state for. Let R denote the receipts that are results of applying transactions in block A for shard a that have any shard in Sbp as the destination shard. Then cpa would include R in the onepart message when they distribute the chunk for shard in block B to bp. Receiving the receipts. Remember that the participants (both block pro- ducers and validators) do not process blocks until they have onepart messages for each chunk included in the block. Thus, by the time any particular partici- pant applies the block B, they have all the onepart messages that correspond to chunks in B, and thus they have all the incoming receipts that have the shards for which the participant maintains state as their destination. When applying the state transition for a particular shard, the participant applies both the re- 29 ceipts that they have collected for the shard in the onepart messages, as well as all the transactions included in the chunk itself. Figure 18: The lifetime of a receipt transaction 3.6.2 Handling too many receipts It is possible that the number of receipts that target a particular shard in a particular block is too large to be processed. For example, consider figure 19, in which each transaction in each shard generates a receipt that targets shard 1. By the next block, the number of receipts that shard 1 needs to process is comparable to the load that all the shards combined processed while handling the previous block. To address it we use a technique similar to that used in QuarkChain 12. Specifically, for each shard the last block B and the last shard s within that block from which the receipts were applied is recorded. When the new shard is created, the receipt are applied in order first from the remaining shards in B, and then in blocks that follow B, until the new chunk is full. Under normal circumstances with a balanced load it will generally result in all the receipts being applied (and thus the last shard of the last block will be recorded for each chunk), but during times when the load is not balanced, and a particular shard receives disproportionately many receipts, this technique allows them to be processed while respecting the limits on the number of transactions included. Note that if such an imbalanced load remains for a long time, the delay from the receipt creation until the application can continue growing indefinitely. One way to address this is to drop any transaction that creates a receipt targeting a shard that has a processing delay exceeding some constant (e.g. one epoch). 12See the whiteboard episode with QuarkChain here: https://www.youtube.com/watch?v= opEtG6NM4x4, in which the approach to cross-shard transactions is discussed. 30 Figure 19: If all the receipts target the same shard, the shard may not have the capacity to process them Consider figure 20. By block B the shard 4 cannot process all the receipts, so it only processes receipts originating from up to shard 3 in block A, and records this. In block C the receipts up to shard 5 in block B are included, and then by block D, the shard catches up, processing all the remaining receipts in block B and all the receipts from block C. Figure 20: Delayed receipts processing 31 3.7 Chunks validation As mentioned in section 3.5, a chunk is validated by a set of stateless validators assigned to the shard. In this section, we provide a more detailed analysis of the security of the design. Again, we assume the existence of a on-chain randomness beacon that can be used to generate random seeds with each block, which then can be used to shuffle validators. The core problem here can be formulated as follows: let’s assume a total of n validators (with equal stake) where at most 1/3 of them are malicious. There are s shards and k validators are assigned to each shard at every block, so n = sk. What is the probability of a random assignment of validators to a shard that results in a shard getting corrupted? First, it is worth noting that a shard being corrupted means that more than 2/3 of validators assigned to that specific shard are malicious and can perform an invalid state transition. If less than 2/3 of validators are malicious, it is still possible for the chunk to be skipped due to insufficient endorsement, but no invalid state transition is possible. In addition, since validators rotate every single block, it is not possible for a shard to get indefinitely stalled due to a bad assignment. Now let’s consider the probability of a single shard getting corrupted. Let p denote the probability of a randomly chosen validator being malicious (so p ≤ 1/3). For a single shard to have l malicious validators, the probability is hypergeometric distribution: P (X = l) = k l n−k k−l  n k  Therefore, the probability of having more than 2/3 malicious validators for a single shard is P (X ≥ 2k/3) ≤ e−D(p+1/3||p)k = e− k3 by Chernoff bound. For s shards, the probability that at least one shard is corrupted is Pbad ≤ sX i=1 P (one shard is corrupted) ≤ se− n3s When n and k are large, i.e, there are many validators assigned to the same shard, the last term se− n3s can be made negligbly small. Our numeric calculation based on multivariate hypergeometric distribution shows that with 800 validators and 4 shards, the probability of the networking getting corrupted is roughtly 10 −29, which means that in expectation it takes 10 29 blocks for the system to fail. Assuming one block per second, that translates to 3 × 1021 years. Therefore, while the security of the system is probabilistic, it is safe enough in practice. 32 3.7.1 Zero-knowledge proofs One problem that is often ignored in blockchain design is what happens when the BFT assumption is violated, i.e, if there are more than 1/3 malicious validators in a blockchain. Obviously the consensus could be broken and the network may fail to produce blocks. More importantly, the malicious validators could poten- tially attempt to create an invalid state transition. In a non-sharded blockchain, doing this would not only require a higher total stake (2/3 of validators being malicious), but also it is also very likely to be immediately noticed and a social consensus may ensue to resolve the attack. This is because the likelihood of every single validator being corrupted in a non-sharded blockchain is extremely low; there may also be others running RPC nodes who would notice the invalid state transition, as well. In a sharded blockchain, however, things are a bit different. It is more likely that the validators assigned to a shard could all be malicious and it is less likely that many people would run nodes that track every shard. This gives rise to the theoretical possibility of an invalid state transition attack occurring with few or any participants noticing. The result would be disastrous: a billion tokens could be minted out of thin air and moved to other shards and potentially even be bridged to other blockchains. This is where zero-knowledge proofs (ZKPs) can come in. Since ZKPs are very cheap to verify, if there is a proof generated for the state transition of each shard, then a very large number of people can independently verify the state transition without having to rely on the signatures of validators to trust the validity of a state transition. More specifically, every wallet could run a ZK full client that verifies the state transition of the entire blockchain and be assured that no invalid state transition has happened in the history of the blockchain. ZKPs also enable a stateless validation design that is simpler and more powerful than the one described in section 3.7. Instead of validators executing the chunk using state witness and verifying the state transition, they could verify one ZKP instead – which is much cheaper. The problem, however, is that generating a ZKP takes a long time. So if we naively swap out state witness with a ZKP, it won’t work due to the proof generation latency. Recent advancements in separating consensus and execution [8] provide a possible solution: blocks and chunks can be produced and optimistically ex- ecuted while ZK proofs are being generated. Once a ZKP is generated, it is submitted into a block for all validators to verify. Because ZKPs can be small in size and quite cheap to verify 13, they can be included in the blocks directly and all validators can validate the state transition of all shards14. In this design, the validators would be much more lightweight, given that they only need to verify some ZKP. This means that the cost of operating a validator is going to be much cheaper and that the validator set could be much larger, which further improves the decentralization of the design. 13While STARK proofs can be relatively large (a few hundred kilobytes), they can be compressed again using a SNARK which would result in a proof of a few hundred bytes. 14Alternatively, proofs from different shards can be aggregated into one ZKP for a block. 33 3.8 State Size Sharding allows us to divide the state of the entire blockchain into those of individual shards, which provides a solution to the state growth problem that is becoming more and more imminent today. The stateless validation approach makes the blockchain even more performant: there are relatively few chunk producers and they can afford to operate more expensive hardware, which means that for each individual shard, the state of the shard can be held in memory when chunk producers produce and process chunks. Validators, on the other hand, receive state witness, which is small in size, when they need to apply a chunk and can also have the required state in memory. As a result, the state reads and writes are very fast. The cost of operating a chunk producer is not going to be exorbitantly high either. If we limit the size of each shard to 50GB, then a chunk producer could be operated with a 64GB RAM machine, which is fairly commonplace today. This asymmetry between chunk producer and validator also works well when state witness is replaced by ZKPs. Chunk producer could also operate a prover, which requires more hardware resources and the validators can run on even cheaper hardware due to the low cost of verifying ZKPs. 3.9 Snapshots Chain Since the blocks on the main chain are produced very frequently, downloading the full history might become expensive very quickly. Since the block producers set is constant throughout the epoch, validating only the first snapshot blocks in each epoch is sufficient assuming that at no point a large percentage of block producers and validators colluded and created a fork. The first block of the epoch must contain information sufficient to compute the block producers and validators for the epoch. We call the subchain of the main chain that only contains thesnapshot blocks a snapshot chain. Such a chain can also be built and validated on Ethereum inside a smart contract can provides a secure method of cross-chain communi- cation. To sync with the NEAR chain, one only needs to download all the snapshot blocks and confirm that the signatures are correct, and then only have to sync the main chain blocks from the last snapshot block. 4 Conclusion In this document, we discussed approaches to building sharded blockchains and covered two major challenges that come with existing approaches, namely state validity and data availability. We then presented Nightshade, a sharding design that powers NEAR Protocol. The design is a work in progress. If you have comments, questions, or feedback on this document, please go to https://github.com/near/neps. 34 References [1] Monica Quaintance Will Martino and Stuart Popejoy. Chainweb: A proof- of-work parallel-chain architecture for massive throughput. 2018. [2] Mustafa Al-Bassam, Alberto Sonnino, and Vitalik Buterin. Fraud proofs: Maximising light client security and scaling blockchains with dishonest ma- jorities. CoRR, abs/1809.09044, 2018. [3] Songze Li, Mingchao Yu, Salman Avestimehr, Sreeram Kannan, and Pramod Viswanath. Polyshard: Coded sharding achieves linearly scaling efficiency and security simultaneously. CoRR, abs/1809.10361, 2018. [4] Ittai Abraham, Guy Gueta, and Dahlia Malkhi. Hot-stuff the linear, optimal- resilience, one-message BFT devil. CoRR, abs/1803.05069, 2018. [5] Yossi Gilad, Rotem Hemo, Silvio Micali, Georgios Vlachos, and Nickolai Zeldovich. Algorand: Scaling byzantine agreements for cryptocurrencies. In Proceedings of the 26th Symposium on Operating Systems Principles, SOSP ’17, pages 51–68, New York, NY, USA, 2017. ACM. [6] Vitalik Buterin and Virgil Griffith. Casper the friendly finality gadget. CoRR, abs/1710.09437, 2017. [7] Aniket Kate, Gregory Zaverucha, and Ian Goldberg. Constant-size commit- ments to polynomials and their applications. pages 177–194, 12 2010. [8] George Danezis, Eleftherios Kokoris-Kogias, Alberto Sonnino, and Alexan- der Spiegelman. Narwhal and tusk: A dag-based mempool and efficient BFT consensus. CoRR, abs/2105.11827, 2021. 35
프로젝트로 돌아가기