Sách trắng NEAR
State Validity and Data Availability
State Validity and Data Availability
The core idea in sharded blockchains is that most participants operating or using the network cannot validate blocks in all the shards. As such, whenever any participant needs to interact with a particular shard they generally cannot download and validate the entire history of the shard. The partitioning aspect of sharding, however, raises a significant potential problem: without downloading and validating the entire history of a particular shard the participant cannot necessarily be certain that the state with which 5This section, except for subsection 2.5.3, was previously published at https://near.ai/ shard2. If you read it before, skip to the next section.
they interact is the result of some valid sequence of blocks and that such sequence of blocks is indeed the canonical chain in the shard. A problem that doesn’t exist in a non-sharded blockchain. We will first present a simple solution to this problem that has been proposed by many protocols and then analyze how this solution can break and what attempts have been made to address it. 2.1 Validators rotation The naive solution to state validity is shown on figure 5: let’s say we assume that the entire system has on the order of thousands validators, out of which no more than 20% are malicious or will otherwise fail (such as by failing to be online to produce a block). Then if we sample 200 validators, the probability of more than 1 3 failing for practical purposes can be assumed to be zero. Figure 5: Sampling validators 1 3 is an important threshold. There’s a family of consensus protocols, called BFT consensus protocols, that guarantees that for as long as fewer than 1 3 of participants fail, either by crashing or by acting in some way that violates the protocol, the consensus will be reached. With this assumption of honest validator percentage, if the current set of validators in a shard provides us with some block, the naive solution assumes that the block is valid and that it is built on what the validators believed to be the canonical chain for that shard when they started validating. The validators learned the canonical chain from the previous set of validators, who by the same assumption built on top of the block which was the head of the canonical chain before that. By induction the entire chain is valid, and since no set of validators at any point produced forks, the naive solution is also certain that the current chain is the only chain in the shard. See figure 6 for a visualization.
Figure 6: A blockchain with each block finalized via BFT consensus This simple solution doesn’t work if we assume that the validators can be corrupted adaptively, which is not an unreasonable assumption6. Adaptively corrupting a single shard in a system with 1000 shards is significantly cheaper than corrupting the entire system. Therefore, the security of the protocol decreases linearly with the number of shards. To have certainty in the validity of a block, we must know that at any point in history no shard in the system has a majority of validators colluding; with adaptive adversaries, we no longer have such certainty. As we discussed in section 1.5, colluding validators can exercise two basic malicious behaviors: create forks, and produce invalid blocks. Malicious forks can be addressed by blocks being cross-linked to the Beacon chain that is generally designed to have significantly higher security than the shard chains. Producing invalid blocks, however, is a significantly more challenging problem to tackle. 2.2 State Validity Consider figure 7 on which Shard #1 is corrupted and a malicious actor produces invalid block B. Suppose in this block B 1000 tokens were minted out of thin air on Alice’s account. The malicious actor then produces valid block C (in a sense that the transactions in C are applied correctly) on top of B, obfuscating the invalid block B, and initiates a cross-shard transaction to Shard #2 that transfers those 1000 tokens to Bob’s account. From this moment the improperly created tokens reside on an otherwise completely valid blockchain in Shard #2. Some simple approaches to tackle this problem are: 6Read this article for details on how adaptive corruption can be carried out: https://medium.com/nearprotocol/d859adb464c8. For more details on adaptive corruption, read https://github.com/ethereum/wiki/wiki/Sharding-FAQ# what-are-the-security-models-that-we-are-operating-under
Figure 7: A cross-shard transaction from a chain that has an invalid block 1. For validators of Shard #2 to validate the block from which the transaction is initiated. This won’t work even in the example above, since block C appears to be completely valid. 2. For validators in Shard #2 to validate some large number of blocks preceding the block from which the transaction is initiated. Naturally, for any number of blocks N validated by the receiving shard the malicious validators can create N+1 valid blocks on top of the invalid block they produced. A promising idea to resolve this issue would be to arrange shards into an undirected graph in which each shard is connected to several other shards, and only allow cross-shard transactions between neighboring shards (e.g. this is how Vlad Zamfir’s sharding essentially works7, and similar idea is used in Kadena’s Chainweb [1]). If a cross-shard transaction is needed between shards that are not neighbors, such transaction is routed through multiple shards. In this design a validator in each shard is expected to validate both all the blocks in their shard as well as all the blocks in all the neighboring shards. Consider a figure below with 10 shards, each having four neighbors, and no two shards requiring more than two hops for a cross-shard communication shown on figure 8. Shard #2 is not only validating its own blockchain, but also blockchains of all the neighbors, including Shard #1. So if a malicious actor on Shard #1 is attempting to create an invalid block B, then build block C on top of it and initiate a cross-shard transaction, such cross-shard transaction will not go through since Shard #2 will have validated the entire history of Shard #1 which will cause it to identify invalid block B. 7Read more about the design here: https://medium.com/nearprotocol/37e538177ed9
Figure 8: An invalid cross-shard transaction in chainweb-like system that will get detected While corrupting a single shard is no longer a viable attack, corrupting a few shards remains a problem. On figure 9 an adversary corrupting both Shard
1 and Shard #2 successfully executes a cross-shard transaction to Shard #3
with funds from an invalid block B: Figure 9: An invalid cross-shard transaction in chainweb-like system that will not get detected Shard #3 validates all the blocks in Shard #2, but not in Shard #1, and has no way to detect the malicious block. There are two major directions of properly solving state validity: fishermen
and cryptographic proofs of computation. 2.3 Fisherman The idea behind the first approach is the following: whenever a block header is communicated between chains for any purpose (such as cross-linking to the beacon chain, or a cross-shard transaction), there’s a period of time during which any honest validator can provide a proof that the block is invalid. There are various constructions that enable very succinct proofs that the blocks are invalid, so the communication overhead for the receiving nodes is way smaller than that of receiving a full block. With this approach for as long as there’s at least one honest validator in the shard, the system is secure. Figure 10: Fisherman This is the dominant approach (besides pretending the problem doesn’t exist) among the proposed protocols today. This approach, however, has two major disadvantages: 1. The challenge period needs to be sufficiently long for the honest validator to recognize a block was produced, download it, fully verify it, and prepare the challenge if the block is invalid. Introducing such a period would significantly slow down the cross-shard transactions. 2. The existence of the challenge protocol creates a new vector of attacks when malicious nodes spam with invalid challenges. An obvious solution to this problem is to make challengers deposit some amount of tokens that are returned if the challenge is valid. This is only a partial solution, as it might still be beneficial for the adversary to spam the system (and burn the deposits) with invalid challenges, for example to prevent the valid
challenge from a honest validator from going through. These attacks are called Grieving Attacks. See section 3.7.2 for a way to get around the latter point. 2.4 Succinct Non-interactive Arguments of Knowledge The second solution to multiple-shard corruption is to use some sort of cryptographic constructions that allow one to prove that a certain computation (such as computing a block from a set of transactions) was carried out correctly. Such constructions do exist, e.g. zk-SNARKs, zk-STARKs and a few others, and some are actively used in blockchain protocols today for private payments, most notably ZCash. The primary problem with such primitives is that they are notoriously slow to compute. E.g. Coda Protocol, that uses zk-SNARKs specifically to prove that all the blocks in the blockchain are valid, said in one of the interviews that it can take 30 seconds per transaction to create a proof (this number is probably smaller by now). Interestingly, a proof doesn’t need to be computed by a trusted party, since the proof not only attests to the validity of the computation it is built for, but to the validity of the proof itself. Thus, the computation of such proofs can be split among a set of participants with significantly less redundancy than would be necessary to perform some trustless computation. It also allows for participants who compute zk-SNARKs to run on special hardware without reducing the decentralization of the system. The challenges of zk-SNARKs, besides performance, are: 1. Dependency on less-researched and less-time-tested cryptographic primitives; 2. ”Toxic waste” — zk-SNARKs depend on a trusted setup in which a group of people performs some computation and then discards the intermediate values of that computation. If all the participants of the procedure collude and keep the intermediate values, fake proofs can be created; 3. Extra complexity introduced into the system design; 4. zk-SNARKs only work for a subset of possible computations, so a protocol with a Turing-complete smart contract language wouldn’t be able to use SNARKs to prove the validity of the chain. 2.5 Data Availability The second problem we will touch upon is data availability. Generally nodes operating a particular blockchain are separated into two groups: Full Nodes, those that download every full block and validate every transaction, and Light Nodes, those that only download block headers, and use Merkle proofs for parts of the state and transactions they are interested in, as shown on figure 11.
Figure 11: Merkle Tree Now if a majority of full nodes collude, they can produce a block, valid or invalid, and send its hash to the light nodes, but never disclose the full content of the block. There are various ways they can benefit from it. For example, consider figure 12: Figure 12: Data Availability problem There are three blocks: the previous, A, is produced by honest validators; the current, B, has validators colluding; and the next, C, will be also produced by honest validators (the blockchain is depicted in the bottom right corner). You are a merchant. The validators of the current block (B) received block A from the previous validators, computed a block in which you receive money,
and sent you a header of that block with a Merkle proof of the state in which you have money (or a Merkle proof of a valid transaction that sends the money to you). Confident the transaction is finalized, you provide the service. However, the validators never distribute the full content of the block B to anyone. As such, the honest validators of block C can’t retrieve the block, and are either forced to stall the system or to build on top of A, depriving you as a merchant of money. When we apply the same scenario to sharding, the definitions of full and light node generally apply per shard: validators in each shard download every block in that shard and validate every transaction in that shard, but other nodes in the system, including those that snapshot shard chains state into the beacon chain, only download the headers. Thus the validators in the shard are effectively full nodes for that shard, while other participants in the system, including the beacon chain, operate as light nodes. For the fisherman approach we discussed above to work, honest validators need to be able to download blocks that are cross-linked to the beacon chain. If malicious validators cross-linked a header of an invalid block (or used it to initiate a cross-shard transaction), but never distributed the block, the honest validators have no way to craft a challenge. We will cover three approaches to address this problem that complement each other. 2.5.1 Proofs of Custody The most immediate problem to be solved is whether a block is available once it is published. One proposed idea is to have so-called Notaries that rotate between shards more often than validators whose only job is to download a block and attest to the fact that they were able to download it. They can be rotated more frequently because they don’t need to download the entire state of the shard, unlike the validators who cannot be rotated frequently since they must download the state of the shard each time they rotate, as shown on figure 13. The problem with this naive approach is that it is impossible to prove later whether the Notary was or was not able to download the block, so a Notary can choose to always attest that they were able to download the block without even attempting to retrieve it. One solution to this is for Notaries to provide some evidence or to stake some amount of tokens attesting that the block was downloaded. One such solution is discussed here: https://ethresear.ch/t/ 1-bit-aggregation-friendly-custody-bonds/2236. 2.5.2 Erasure Codes When a particular light node receives a hash of a block, to increase the node’s confidence that the block is available it can attempt to download a few random pieces of the block. This is not a complete solution, since unless the light nodes collectively download the entire block the malicious block producers can choose
Figure 13: Validators need to download state and thus cannot be rotated frequently to withhold the parts of the block that were not downloaded by any light node, thus still making the block unavailable. One solution is to use a construction called Erasure Codes to make it possible to recover the full block even if only some part of the block is available, as shown on figure 14. Figure 14: Merkle tree built on top of erasure coded data Both Polkadot and Ethereum Serenity have designs around this idea that provide a way for light nodes to be reasonably confident the blocks are available. The Ethereum Serenity approach has a detailed description in [2].
2.5.3 Polkadot’s approach to data availability In Polkadot, like in most sharded solutions, each shard (called parachain) snapshots its blocks to the beacon chain (called relay chain). Say there are 2f + 1 validators on the relay chain. The block producers of the parachain blocks, called collators, once the parachain block is produced compute an erasure coded version of the block that consists of 2f +1 parts such that any f parts are sufficient to reconstruct the block. They then distribute one part to each validator on the relay chain. A particular relay chain validator would only sign on a relay chain block if they have their part for each parachain block that is snapshotted to such relay chain block. Thus, if a relay chain block has signatures from 2f + 1 validators, and for as long as no more than f of them violated the protocol, each parachain block can be reconstructed by fetching the parts from the validators that follow the protocol. See figure 15. Figure 15: Polkadot’s data availability 2.5.4 Long term data availability Note that all the approaches discussed above only attest to the fact that a block was published at all, and is available now. Blocks can later become unavailable for a variety of reasons: nodes going offline, nodes intentionally erasing historical data, and others. A whitepaper worth mentioning that addresses this issue is Polyshard [3], which uses erasure codes to make blocks available across shards even if several shards completely lose their data. Unfortunately their specific approach requires all the shards to download blocks from all other shards, which is prohibitively expensive. The long term availability is not as pressing of an issue: since no participant in the system is expected to be capable of validating all the chains in all the
shards, the security of the sharded protocol needs to be designed in such a way that the system is secure even if some old blocks in some shards become completely unavailable.
Hiệu lực của trạng thái và tính sẵn có của dữ liệu
Ý tưởng cốt lõi trong sharded blockchains là hầu hết người tham gia đều vận hành hoặc việc sử dụng mạng không thể xác thực các khối trong tất cả các phân đoạn. Như vậy, bất cứ khi nào bất kỳ người tham gia nào cũng cần tương tác với một phân đoạn cụ thể mà họ thường không thể tải xuống và xác thực toàn bộ lịch sử của phân đoạn. Tuy nhiên, khía cạnh phân vùng của sharding làm tăng tiềm năng đáng kể vấn đề: không tải xuống và xác thực toàn bộ lịch sử của một ứng dụng cụ thể phân đoạn, người tham gia không nhất thiết phải chắc chắn rằng trạng thái của nó 5Phần này, ngoại trừ tiểu mục 2.5.3, đã được xuất bản trước đây tại https://near.ai/ mảnh vỡ2. Nếu bạn đã đọc nó trước đó, hãy chuyển sang phần tiếp theo.
chúng tương tác với nhau là kết quả của một chuỗi khối hợp lệ nào đó và chuỗi đó của các khối thực sự là chuỗi chuẩn trong phân đoạn. Một vấn đề không tồn tại trong blockchain không được phân chia. Đầu tiên chúng tôi sẽ trình bày một giải pháp đơn giản cho vấn đề này đã được đề xuất bằng nhiều giao thức và sau đó phân tích xem giải pháp này có thể bị hỏng như thế nào và điều gì đã có những nỗ lực để giải quyết nó. 2.1 Xoay vòng xác thực Giải pháp đơn giản cho tính hợp lệ của trạng thái được thể hiện trên hình 5: giả sử chúng ta giả sử mà toàn bộ hệ thống có khoảng hàng nghìn validator, trong đó không quá 20% là độc hại hoặc sẽ thất bại (chẳng hạn như không thể trực tuyến để tạo ra một khối). Sau đó, nếu chúng ta lấy mẫu 200 validators thì xác suất nhiều hơn 1 3 không đạt trong mục đích thực tế có thể được coi là bằng không. Hình 5: Đang lấy mẫu validators 1 3 là một ngưỡng quan trọng. Có một nhóm các giao thức đồng thuận, được gọi là BFT giao thức đồng thuận, đảm bảo rằng chỉ cần ít hơn 1 3 trong số người tham gia thất bại, do vi phạm hoặc do hành động theo cách nào đó vi phạm giao thức thì sẽ đạt được sự đồng thuận. Với giả định về tỷ lệ phần trăm validator trung thực này, nếu tập hợp hiện tại validator trong một phân đoạn cung cấp cho chúng ta một số khối, giải pháp ngây thơ giả định rằng khối đó hợp lệ và nó được xây dựng dựa trên những gì validator được cho là chuỗi chuẩn cho phân đoạn đó khi họ bắt đầu xác thực. validators đã học chuỗi chuẩn từ tập hợp validator trước đó, cũng bằng cách đó giả định được xây dựng trên khối đứng đầu chuỗi kinh điển trước đó. Bằng quy nạp, toàn bộ chuỗi là hợp lệ và vì không có tập hợp validator nào tại bất kỳ thời điểm nào sản xuất nĩa, giải pháp ngây thơ cũng chắc chắn rằng hiện tại chuỗi là chuỗi duy nhất trong phân đoạn. Xem hình 6 để hình dung.
Hình 6: blockchain với mỗi khối được hoàn tất thông qua sự đồng thuận BFT Giải pháp đơn giản này sẽ không hiệu quả nếu chúng ta giả sử rằng validator có thể bị hỏng một cách thích ứng, đây không phải là một giả định vô lý6. Thích ứng làm hỏng một phân đoạn trong hệ thống có 1000 phân đoạn sẽ rẻ hơn đáng kể hơn là làm hỏng toàn bộ hệ thống. Do đó, tính bảo mật của giao thức giảm tuyến tính theo số lượng phân đoạn. Để có sự chắc chắn về tính hợp lệ của một khối, chúng ta phải biết rằng tại bất kỳ thời điểm nào trong lịch sử không có phân đoạn nào trong hệ thống có phần lớn validator thông đồng; với những đối thủ có khả năng thích ứng, chúng ta không còn có sự chắc chắn như vậy. Như chúng ta đã thảo luận trong phần 1.5, việc thông đồng với validator có thể gây ảnh hưởng hai hành vi độc hại cơ bản: tạo nhánh và tạo các khối không hợp lệ. Các nhánh độc hại có thể được xử lý bằng các khối được liên kết chéo với chuỗi Beacon thường được thiết kế để có độ bảo mật cao hơn đáng kể so với các chuỗi khác. những chuỗi mảnh vỡ. Tuy nhiên, việc tạo ra các khối không hợp lệ là một vấn đề đáng kể hơn. vấn đề đầy thách thức cần giải quyết. 2.2 Hiệu lực của tiểu bang Hãy xem hình 7 trong đó Shard #1 bị hỏng và một tác nhân độc hại tạo ra khối B không hợp lệ. Giả sử trong khối B này 1000 token được đúc từ mỏng phát sóng trên tài khoản của Alice. Sau đó, tác nhân độc hại tạo ra khối C hợp lệ (trong một cảm thấy rằng các giao dịch trong C được áp dụng chính xác) trên B, làm xáo trộn khối B không hợp lệ và bắt đầu giao dịch chéo tới Phân đoạn số 2 chuyển 1000 tokens đó vào tài khoản của Bob. Từ lúc này trở đi không đúng cách đã tạo token nằm trên blockchain hoàn toàn hợp lệ trong Phân đoạn #2. Một số cách tiếp cận đơn giản để giải quyết vấn đề này là: 6Đọc cái này bài viết cho chi tiết trên làm thế nào thích nghi tham nhũng có thể được mang theo ra: https://medium.com/nearprotocol/d859adb464c8. cho hơn thế nữa chi tiết trên thích nghi tham nhũng, đọc https://github.com/ethereum/wiki/wiki/Sharding-FAQ# mô hình bảo mật mà chúng tôi đang vận hành là gìHình 7: Giao dịch chéo từ chuỗi có khối không hợp lệ 1. Dành cho validator của Phân đoạn số 2 để xác thực khối nơi giao dịch được thực hiện được khởi xướng. Điều này sẽ không hoạt động ngay cả trong ví dụ trên, vì khối C dường như hoàn toàn hợp lệ. 2. Dành cho validator trong Phân đoạn số 2 để xác thực một số lượng lớn khối trước khối mà giao dịch được bắt đầu. Đương nhiên, đối với bất kỳ số lượng khối N nào được xác nhận bởi phân đoạn nhận độc hại validators có thể tạo N+1 khối hợp lệ lên trên khối không hợp lệ mà họ được sản xuất. Một ý tưởng đầy hứa hẹn để giải quyết vấn đề này là sắp xếp các mảnh thành một đồ thị vô hướng trong đó mỗi phân đoạn được kết nối với một số phân đoạn khác và chỉ cho phép giao dịch chéo giữa các phân đoạn lân cận (ví dụ: đây là cách Về cơ bản, sharding của Vlad Zamfir hoạt động7 và ý tưởng tương tự được sử dụng trong Kadena Chuỗi mạng [1]). Nếu cần một giao dịch chéo giữa các phân đoạn không phải hàng xóm, giao dịch đó được định tuyến qua nhiều phân đoạn. Trong thiết kế này validator trong mỗi phân đoạn phải xác thực cả hai khối trong phân đoạn của chúng cũng như tất cả các khối trong tất cả các mảnh lân cận. Hãy xem xét một hình dưới đây với 10 phân đoạn, mỗi phân đoạn có bốn phân đoạn lân cận và không có phân đoạn nào yêu cầu nhiều hơn hơn hai bước nhảy cho giao tiếp chéo được hiển thị trên hình 8. Phân đoạn số 2 không chỉ xác thực blockchain của chính nó mà còn blockchain của tất cả những người hàng xóm, bao gồm cả Shard #1. Vì vậy, nếu một tác nhân độc hại trên Shard #1 đang cố gắng tạo khối B không hợp lệ, sau đó xây dựng khối C lên trên khối đó và bắt đầu một giao dịch chéo, giao dịch chéo đó sẽ không diễn ra kể từ khi Phân đoạn số 2 sẽ xác thực toàn bộ lịch sử của Phân đoạn số 1 sẽ khiến nó xác định khối B không hợp lệ. 7Đọc thêm về thiết kế tại đây: https://medium.com/nearprotocol/37e538177ed9
Hình 8: Một giao dịch chéo không hợp lệ trong hệ thống giống như chainweb sẽ bị phát hiện Mặc dù việc làm hỏng một phân đoạn không còn là một cuộc tấn công khả thi nữa, việc làm hỏng một vài mảnh vẫn còn là một vấn đề. Trên hình 9, một đối thủ đang làm hỏng cả Shard
1 và Shard #2 thực hiện thành công giao dịch chéo tới Shard #3
với số tiền từ khối B không hợp lệ: Hình 9: Một giao dịch chéo không hợp lệ trong hệ thống giống như chainweb sẽ không bị phát hiện Phân đoạn số 3 xác thực tất cả các khối trong Phân đoạn số 2, nhưng không có trong Phân đoạn số 1 và không có cách nào để phát hiện khối độc hại. Có hai hướng chính để giải quyết đúng đắn tính hợp lệ của trạng thái:
và bằng chứng mật mã của tính toán. 2.3 ngư dân Ý tưởng đằng sau cách tiếp cận đầu tiên là như sau: bất cứ khi nào một tiêu đề khối được truyền đạt giữa các chuỗi vì bất kỳ mục đích nào (chẳng hạn như liên kết chéo với chuỗi đèn hiệu hoặc giao dịch chéo), có một khoảng thời gian trong mà bất kỳ validator trung thực nào cũng có thể cung cấp bằng chứng cho thấy khối không hợp lệ. Ở đó là những công trình khác nhau cho phép chứng minh rất ngắn gọn rằng các khối không hợp lệ, do đó chi phí liên lạc cho các nút nhận sẽ nhỏ hơn nhiều hơn là nhận được một khối đầy đủ. Với cách tiếp cận này miễn là có ít nhất một validator trung thực trong mảnh vỡ, hệ thống được an toàn. Hình 10: ngư dân Đây là cách tiếp cận chủ đạo (ngoài việc giả vờ như vấn đề không tồn tại) trong số các giao thức được đề xuất hiện nay. Tuy nhiên, cách tiếp cận này có hai nhược điểm lớn: 1. Thời gian thử thách cần phải đủ dài đối với người trung thực validator để nhận biết một khối đã được tạo, tải xuống, xác minh đầy đủ và chuẩn bị thử thách nếu khối không hợp lệ. Giới thiệu một thời kỳ như vậy sẽ làm chậm đáng kể các giao dịch chéo. 2. Sự tồn tại của giao thức thử thách tạo ra một hướng tấn công mới khi các nút độc hại spam với các thách thức không hợp lệ. Một giải pháp rõ ràng của vấn đề này là bắt những người thách đấu gửi một số tiền tokens được trả lại nếu thử thách hợp lệ. Đây chỉ là giải pháp một phần vì nó vẫn có thể có lợi cho kẻ thù gửi thư rác vào hệ thống (và đốt cháy tiền gửi) với những thách thức không hợp lệ, ví dụ để ngăn chặn hợp lệthách thức từ validator trung thực khi vượt qua. Những cuộc tấn công này là được gọi là Cuộc tấn công đau buồn. Xem phần 3.7.2 để biết cách giải quyết điểm sau. 2.4 Lập luận ngắn gọn về kiến thức không tương tác Giải pháp thứ hai cho vấn đề hỏng nhiều phân đoạn là sử dụng một số loại cấu trúc mật mã cho phép người ta chứng minh rằng một tính toán nhất định (chẳng hạn như như việc tính toán một khối từ một tập hợp các giao dịch) đã được thực hiện chính xác. Những công trình như vậy tồn tại, ví dụ: zk-SNARK, zk-STARK và một số loại khác, và một số được sử dụng tích cực trong các giao thức blockchain ngày nay để thanh toán riêng tư, đáng chú ý nhất là ZCash. Vấn đề chính với những thứ nguyên thủy như vậy là chúng nổi tiếng là tính toán chậm. Ví dụ. Giao thức Coda, sử dụng zk-SNARK cụ thể là để chứng minh rằng tất cả các khối trong blockchain đều hợp lệ, được nói trong một trong số các cuộc phỏng vấn rằng có thể mất 30 giây cho mỗi giao dịch để tạo bằng chứng (con số này có lẽ bây giờ đã nhỏ hơn). Điều thú vị là, bằng chứng không cần phải được tính toán bởi một bên đáng tin cậy, vì bằng chứng không chỉ chứng thực tính hợp lệ của tính toán mà nó được xây dựng mà còn giá trị pháp lý của chính bằng chứng. Vì vậy, việc tính toán các chứng minh đó có thể được chia giữa một nhóm người tham gia với mức độ dư thừa ít hơn đáng kể so với cần thiết để thực hiện một số tính toán không tin cậy. Nó cũng cho phép người tham gia những người tính toán zk-SNARK để chạy trên phần cứng đặc biệt mà không làm giảm phi tập trung hóa hệ thống. Những thách thức của zk-SNARK, ngoài hiệu suất, là: 1. Sự phụ thuộc vào các mật mã nguyên thủy ít được nghiên cứu và thử nghiệm ít thời gian hơn; 2. ”Chất thải độc hại” — zk-SNARK phụ thuộc vào thiết lập đáng tin cậy trong đó một nhóm mọi người thực hiện một số tính toán và sau đó loại bỏ kết quả trung gian các giá trị của phép tính đó. Nếu tất cả những người tham gia thủ tục thông đồng và giữ nguyên các giá trị trung gian, có thể tạo ra bằng chứng giả; 3. Độ phức tạp cao hơn được đưa vào thiết kế hệ thống; 4. zk-SNARK chỉ hoạt động đối với một tập hợp con các phép tính có thể, do đó, một giao thức với ngôn ngữ Turing-complete smart contract sẽ không thể sử dụng SNARK để chứng minh tính hợp lệ của chuỗi. 2,5 Tính sẵn có của dữ liệu Vấn đề thứ hai chúng ta sẽ đề cập đến là tính sẵn có của dữ liệu. Nói chung các nút việc vận hành một blockchain cụ thể được tách thành hai nhóm: Nút đầy đủ, những thứ tải xuống mọi khối đầy đủ và xác thực mọi giao dịch và Light Các nút chỉ tải xuống tiêu đề khối và sử dụng bằng chứng Merkle cho các bộ phận của nhà nước và các giao dịch mà họ quan tâm, như thể hiện trên hình 11.
Hình 11: Cây Merkle Bây giờ nếu phần lớn các nút đầy đủ thông đồng với nhau, chúng có thể tạo ra một khối, hợp lệ hoặc không hợp lệ và gửi hash của nó tới các nút ánh sáng nhưng không bao giờ tiết lộ toàn bộ nội dung của khối. Có nhiều cách khác nhau để họ có thể hưởng lợi từ nó. Ví dụ, xét hình 12: Hình 12: Vấn đề về tính sẵn có của dữ liệu Có ba khối: khối trước, A, được tạo bởi validators trung thực; hiện tại, B, có validator thông đồng; và loại tiếp theo, C, cũng sẽ được sản xuất bởi validators trung thực (blockchain được mô tả ở góc dưới cùng bên phải). Bạn là một thương gia. validators của khối hiện tại (B) đã nhận được khối A từ validator trước đó, đã tính toán một khối trong đó bạn nhận được tiền,và gửi cho bạn tiêu đề của khối đó cùng với bằng chứng Merkle về trạng thái bạn có tiền (hoặc bằng chứng Merkle về giao dịch hợp lệ gửi tiền cho bạn). Tin chắc rằng giao dịch đã hoàn tất, bạn cung cấp dịch vụ. Tuy nhiên, validator không bao giờ phân phối toàn bộ nội dung của khối B cho bất cứ ai. Do đó, validator trung thực của khối C không thể truy xuất khối và hoặc bị buộc phải đình trệ hệ thống hoặc xây dựng trên đỉnh A, tước bỏ tư cách của bạn người buôn tiền. Khi chúng tôi áp dụng kịch bản tương tự cho sharding, các định nghĩa về đầy đủ và nút nhẹ thường áp dụng cho mỗi phân đoạn: validators trong mỗi lần tải xuống phân đoạn chặn trong phân đoạn đó và xác thực mọi giao dịch trong phân đoạn đó, nhưng các giao dịch khác các nút trong hệ thống, bao gồm cả các nút có trạng thái chuỗi phân đoạn nhanh vào chuỗi đèn hiệu, chỉ tải xuống các tiêu đề. Do đó, validator trong phân đoạn là các nút đầy đủ hiệu quả cho phân đoạn đó, trong khi những người tham gia khác trong hệ thống, bao gồm chuỗi đèn hiệu, hoạt động như các nút ánh sáng. Để cách tiếp cận của ngư dân mà chúng ta đã thảo luận ở trên có hiệu quả, validators trung thực cần có khả năng tải xuống các khối được liên kết chéo với chuỗi đèn hiệu. Nếu validator độc hại liên kết chéo tiêu đề của một khối không hợp lệ (hoặc sử dụng nó để bắt đầu một giao dịch chéo), nhưng không bao giờ phân phối khối, thì giao dịch trung thực validator không có cách nào để tạo ra thử thách. Chúng tôi sẽ đề cập đến ba cách tiếp cận để giải quyết vấn đề này, bổ sung cho lẫn nhau. 2.5.1 Bằng chứng về quyền nuôi con Vấn đề trước mắt nhất cần giải quyết là liệu một khối có sẵn một lần hay không nó được xuất bản. Một ý tưởng được đề xuất là có cái gọi là Công chứng viên luân phiên giữa các phân đoạn thường xuyên hơn validator có công việc duy nhất là tải xuống chặn và chứng thực rằng họ có thể tải xuống nó. Họ có thể được luân chuyển thường xuyên hơn vì họ không cần tải xuống toàn bộ trạng thái của phân đoạn, không giống như validator không thể xoay thường xuyên vì chúng phải tải xuống trạng thái của phân đoạn mỗi lần chúng xoay, như thể hiện trên hình 13. Vấn đề với cách tiếp cận ngây thơ này là không thể chứng minh sau này cho dù Công chứng viên có thể tải xuống khối hay không, vì vậy Công chứng viên có thể chọn luôn chứng thực rằng họ có thể tải xuống khối mà không cần thậm chí còn cố gắng lấy lại nó. Một giải pháp cho vấn đề này là Công chứng viên cung cấp một số bằng chứng hoặc đặt cược số lượng token chứng thực rằng khối đã được đã tải xuống. Một giải pháp như vậy được thảo luận ở đây: https://ethresear.ch/t/ Trái phiếu lưu ký thân thiện với tập hợp 1 bit/2236. 2.5.2 Mã xóa Khi một nút nhẹ cụ thể nhận được hash của một khối, để tăng sức mạnh của nút đó tin rằng khối đó có sẵn, nó có thể thử tải xuống một vài thông tin ngẫu nhiên các mảnh của khối. Đây không phải là một giải pháp hoàn chỉnh, vì trừ khi các nút ánh sáng tải xuống chung toàn bộ khối mà nhà sản xuất khối độc hại có thể chọn
Hình 13: Trình xác thực cần phải tải xuống trạng thái và do đó không thể xoay được thường xuyên để giữ lại các phần của khối không được tải xuống bởi bất kỳ nút ánh sáng nào, do đó vẫn làm cho khối không có sẵn. Một giải pháp là sử dụng một cấu trúc có tên là Erasure Codes để thực hiện điều đó. để khôi phục toàn bộ khối ngay cả khi chỉ có một phần của khối, như được hiển thị trên hình 14. Hình 14: Merkle tree được xây dựng dựa trên dữ liệu đã mã hóa bị xóa Cả Polkadot và Ethereum Serenity đều có thiết kế xoay quanh ý tưởng này cung cấp một cách để các nút nhẹ có thể tin cậy một cách hợp lý rằng các khối có sẵn. Phương pháp Ethereum Serenity có mô tả chi tiết trong [2].2.5.3 Cách tiếp cận của Polkadot đối với tính khả dụng của dữ liệu Trong Polkadot, giống như trong hầu hết các giải pháp phân đoạn, mỗi phân đoạn (được gọi là parachain) chụp nhanh các khối của nó vào chuỗi báo hiệu (được gọi là chuỗi chuyển tiếp). Giả sử có 2f + 1 validator trên chuỗi chuyển tiếp. Các nhà sản xuất khối của khối parachain, được gọi là đối chiếu, sau khi khối parachain được tạo ra, hãy tính toán một phiên bản mã hóa xóa của khối bao gồm 2f +1 phần sao cho bất kỳ phần f nào cũng đủ để xây dựng lại khối. Sau đó, họ phân phối một phần cho mỗi validator trên chuỗi rơle. Chuỗi chuyển tiếp cụ thể validator sẽ chỉ đăng nhập vào chuỗi chuyển tiếp khối nếu họ có phần của mình cho mỗi khối parachain được chụp nhanh vào khối chuỗi chuyển tiếp như vậy. Do đó, nếu khối chuỗi chuyển tiếp có chữ ký từ 2f + 1 validators và miễn là không quá f trong số chúng vi phạm giao thức, mỗi khối parachain có thể được xây dựng lại bằng cách tìm nạp các phần từ validators tuân theo giao thức. Xem hình 15. Hình 15: Tính khả dụng của dữ liệu Polkadot 2.5.4 Tính sẵn có của dữ liệu dài hạn Lưu ý rằng tất cả các phương pháp được thảo luận ở trên chỉ chứng thực thực tế là một khối đã được xuất bản và hiện có sẵn. Các khối sau này có thể không còn khả dụng vì nhiều lý do: các nút ngoại tuyến, các nút cố tình xóa lịch sử dữ liệu và những thứ khác. Sách trắng đáng được đề cập giải quyết vấn đề này là Polyshard [3], sử dụng mã xóa để cung cấp các khối trên các phân đoạn ngay cả khi một số mảnh vỡ hoàn toàn mất dữ liệu của họ. Thật không may, cách tiếp cận cụ thể của họ đòi hỏi tất cả các phân đoạn để tải xuống các khối từ tất cả các phân đoạn khác, điều này bị cấm đắt tiền. Tính khả dụng lâu dài không phải là vấn đề cấp bách: vì không có người tham gia trong hệ thống dự kiến sẽ có khả năng xác nhận tất cả các chuỗi trong tất cả
phân đoạn, tính bảo mật của giao thức phân đoạn cần phải được thiết kế theo cách cách mà hệ thống được an toàn ngay cả khi một số khối cũ trong một số phân đoạn trở thành hoàn toàn không có sẵn.
Nightshade
Nightshade
3.1 From shard chains to shard chunks The sharding model with shard chains and a beacon chain is very powerful but has certain complexities. In particular, the fork choice rule needs to be executed in each chain separately, the fork choice rule in the shard chains and the beacon chain must be built differently and tested separately. In Nightshade we model the system as a single blockchain, in which each block logically contains all the transactions for all the shards, and changes the whole state of all the shards. Physically, however, no participant downloads the full state or the full logical block. Instead, each participant of the network only maintains the state that corresponds to the shards that they validate transactions for, and the list of all the transactions in the block is split into physical chunks, one chunks per shard. Under ideal conditions each block contains exactly one chunk per shard per block, which roughly corresponds to the model with shard chains in which the shard chains produce blocks with the same speed as the beacon chain. However, due to network delays some chunks might be missing, so in practice each block contains either one or zero chunks per shard. See section 3.3 for details on how blocks are produced. Figure 16: A model with shard chains on the left and with one chain having blocks split into chunks on the right
3.2 Consensus The two dominant approaches to the consensus in the blockchains today are the longest (or heaviest) chain, in which the chain that has the most work or stake used to build it is considered canonical, and BFT, in which for each block some set of validators reach a BFT consensus. In the protocols proposed recently the latter is a more dominant approach, since it provides immediate finality, while in the longest chain more blocks need to be built on top of the block to ensure the finality. Often for a meaningful security the time it takes for sufficient number of blocks to be built takes on the order of hours. Using BFT consensus on each block also has disadvantages, such as: 1. BFT consensus involves considerable amount of communication. While recent advances allow the consensus to be reached in linear time in number of participants (see e.g. [4]), it is still noticeable overhead per block; 2. It is unfeasible for all the network participants to participate in the BFT consensus per block, thus usually only a randomly sampled subset of participants reach the consensus. A randomly sampled set can be, in principle, adaptively corrupted, and a fork in theory can be created. The system either needs to be modelled to be ready for such an event, and thus still have a fork-choice rule besides the BFT consensus, or be designed to shut down in such an event. It is worth mentioning that some designs, such as Algorand [5], significantly reduce the probability of adaptive corruption. 3. Most importantly, the system stalls if 1 3 or more of all the participants are offline. Thus, any temporary network glitch or a network split can completely stall the system. Ideally the system must be able to continue to operate for as long as at least half of the participants are online (heaviest chain-based protocols continue operating even if less than half of the participants are online, but the desirability of this property is more debatable within the community). A hybrid model in which the consensus used is some sort of the heaviest chain, but some blocks are periodically finalized using a BFT finality gadget maintain the advantages of both models. Such BFT finality gadgets are Casper FFG [6] used in Ethereum 2.0 8, Casper CBC (see https://vitalik. ca/general/2018/12/05/cbc_casper.html) and GRANDPA (see https:// medium.com/polkadot-network/d08a24a021b5) used in Polkadot. Nightshade uses the heaviest chain consensus. Specifically when a block producer produces a block (see section 3.3), they can collect signatures from other block producers and validators attesting to the previous block. See section 3.8 for details how such large number of signatures is aggregated. The weight 8Also see the whiteboard session with Justin Drake for an indepth overview of Casper FFG, and how it is integrated with the GHOST heaviest chain consensus here: https://www. youtube.com/watch?v=S262StTwkmo
of a block is then the cumulative stake of all the signers whose signatures are included in the block. The weight of a chain is the sum of the block weights. On top of the heaviest chain consensus we use a finality gadget that uses the attestations to finalize the blocks. To reduce the complexity of the system, we use a finality gadget that doesn’t influence the fork choice rule in any way, and instead only introduces extra slashing conditions, such that once a block is finalized by the finality gadget, a fork is impossible unless a very large percentage of the total stake is slashed. Casper CBC is such a finality gadget, and we presently model with Casper CBC in mind. We also work on a separate BFT protocol called TxFlow. At the time of writing this document it is unclear if TxFlow will be used instead of Casper CBC. We note, however, that the choice of the finality gadget is largely orthogonal to the rest of the design. 3.3 Block production In Nightshade there are two roles: block producers and validators. At any point the system contains w block producers, w = 100 in our models, and wv validators, in our model v = 100, wv = 10, 000. The system is Proof-of-Stake, meaning that both block producers and validators have some number of internal currency (referred to as ”tokens”) locked for a duration of time far exceeding the time they spend performing their duties of building and validating the chain. As with all the Proof of Stake systems, not all the w block producers and not all the wv validators are different entities, since that cannot be enforced. Each of the w block producers and the wv validators, however, do have a separate stake. The system contains n shards, n = 1000 in our model. As mentioned in section 3.1, in Nightshade there are no shard chains, instead all the block producers and validators are building a single blockchain, that we refer to as the main chain. The state of the main chain is split into n shards, and each block producer and validator at any moment only have downloaded locally a subset of the state that corresponds to some subset of the shards, and only process and validate transactions that affect those parts of the state. To become a block producer, a participant of the network locks some large amount of tokens (a stake). The maintenance of the network is done in epochs, where an epoch is a period of time on the order of days. The participants with the w largest stakes at the beginning of a particular epoch are the block producers for that epoch. Each block producer is assigned to sw shards, (say sw = 40, which would make sww/n = 4 block producers per shard). The block producer downloads the state of the shard they are assigned to before the epoch starts, and throughout the epoch collects transactions that affect that shard, and applies them to the state. For each block b on the main chain, and for every shards s, there’s one of the assigned block producers to s who is responsible to produce the part of b related to the shard. The part of b related to shard s is called a chunk, and contains the list of the transactions for the shard to be included in b, as well as the merkle
root of the resulting state. b will ultimately only contain a very small header of the chunk, namely the merkle root of all the applied transactions (see section 3.7.1 for exact details), and the merkle root of the final state. Throughout the rest of the document we often refer to the block producer that is responsible to produce a chunk at a particular time for a particular shard as a chunk producer. Chunk producer is always one of the block producers. The block producers and the chunk producers rotate each block according to a fixed schedule. The block producers have an order and repeatedly produce blocks in that order. E.g. if there are 100 block producers, the first block producers is responsible for producing blocks 1, 101, 201 etc, the second is responsible for producing 2, 102, 202 etc). Since chunk production, unlike the block production, requires maintaining the state, and for each shard only sww/n block producers maintain the state per shard, correspondingly only those sww/n block producers rotate to create chunks. E.g. with the constants above with four block producers assigned to each shard, each block producer will be creating chunks once every four blocks. 3.4 Ensuring data availability To ensure the data availability we use an approach similar to that of Polkadot described in section 2.5.3. Once a block producer produces a chunk, they create an erasure coded version of it with an optimal (w, ⌊w/6 + 1⌋) block code of the chunk. They then send one piece of the erasure coded chunk (we call such pieces chunk parts, or just parts) to each block producer. We compute a merkle tree that contains all the parts as the leaves, and the header of each chunk contains the merkle root of such tree. The parts are sent to the validators via onepart messages. Each such message contains the chunk header, the ordinal of the part and the part contents. The message also contains the signature of the block producer who produced the chunk and the merkle path to prove that the part corresponds to the header and is produced by the proper block producer. Once a block producer receives a main chain block, they first check if they have onepart messages for each chunk included in the block. If not, the block is not processed until the missing onepart messages are retrieved. Once all the onepart messages are received, the block producer fetches the remaining parts from the peers and reconstructs the chunks for which they hold the state. The block producer doesn’t process a main chain block if for at least one chunk included in the block they don’t have the corresponding onepart message, or if for at least one shard for which they maintain the state they cannot reconstruct the entire chunk. For a particular chunk to be available it is enough that ⌊w/6⌋+1 of the block producers have their parts and serve them. Thus, for as long as the number of malicious actors doesn’t exceed ⌊w/3⌋no chain that has more than half block producers building it can have unavailable chunks.
Figure 17: Each block contains one or zero chunks per shard, and each chunk is erasure coded. Each part of the erasure coded chunk is sent to a designated block producer via a special onepart message 3.4.1 Dealing with lazy block producers If a block producer has a block for which a onepart message is missing, they might choose to still sign on it, because if the block ends up being on chain it will maximize the reward for the block producer. There’s no risk for the block producer since it is impossible to prove later that the block producer didn’t have the onepart message. To address it we make each chunk producer when creating the chunk to choose a color (red or blue) for each part of the future encoded chunk, and store the bitmask of assigned color in the chunk before it is encoded. Each onepart message then contains the color assigned to the part, and the color is used when computing the merkle root of the encoded parts. If the chunk producer deviates from the protocol, it can be easily proven, since either the merkle root will not correspond to onepart messages, or the colors in the onepart messages that correspond to the merkle root will not match the mask in the chunk. When a block producer signs on a block, they include a bitmask of all the red parts they received for the chunks included in the block. Publishing an incorrect bitmask is a slashable behavior. If a block producer hasn’t received a onepart message, they have no way of knowing the color of the message, and thus have a 50% chance of being slashed if they attempt to blidnly sign the block. 3.5 State transition application The chunk producers only choose which transactions to include in the chunk but do not apply the state transition when they produce a chunk. Correspondingly,
the chunk header contains the merkle root of the merkelized state as of before the transactions in the chunk are applied. The transactions are only applied when a full block that includes the chunk is processed. A participant only processes a block if 1. The previous block was received and processed; 2. For each chunk the participant doesn’t maintain the state for they have seen the onepart message; 3. For each chunk the participant does maintain the state for they have the full chunk. Once the block is being processed, for each shard for which the participant maintains the state for, they apply the transactions and compute the new state as of after the transactions are applied, after which they are ready to produce the chunks for the next block, if they are assigned to any shard, since they have the merkle root of the new merkelized state. 3.6 Cross-shard transactions and receipts If a transaction needs to affect more than one shard, it needs to be consecutively executed in each shard separately. The full transaction is sent to the first shard affected, and once the transaction is included in the chunk for such shard, and is applied after the chunk is included in a block, it generates a so called receipt transaction, that is routed to the next shard in which the transaction need to be executed. If more steps are required, the execution of the receipt transaction generates a new receipt transaction and so on. 3.6.1 Receipt transaction lifetime It is desirable that the receipt transaction is 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 generates 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 for block B, they fetch all the receipts generated by applying the transactions from block A for shard a, and included them into the chunk for shrad a in block B. Once such chunk is generated, cpa produces its erasure coded version and all the corresponding onepart messages. cpa knows what block producers maintain the full state for which shards. For a particular block producer bp cpa includes the receipts that resulted from applying transactions in block A for shard a that have any of the shards that bp cares about as their destination in the onepart message when they distributed the chunk for shard a in block B (see figure 17, that shows receipts included in the onepart message). Receiving the receipts. Remember that the participants (both block producers and validators) do not process blocks until they have onepart messages for each chunk included in the block. Thus, by the time any particular particpiant 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 the participant maintains state for as their destination. When applying the state transition for a particular shard, the participant apply both the receipts 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.
Figure 19: If all the receipts target the same shard, the shard might not have the capacity to process them To address it we use a technique similar to that used in QuarkChain 9. 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 unbalanced load remains for a long time, the delay from the receipt creation until application can continue growing indefinitely. One way to address it is to drop any transaction that creates a receipt targeting a shard that has a processing delay that exceeds some constant (e.g. one epoch). Consider figure 20. By block B the shard 4 cannot process all the receipts, so it only processes receipts origination from up to shard 3 in block A, and records it. 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. 3.7 Chunks validation A chunk produced for a particular shard (or a shard block produced for a particular shard chain in the model with shard chains) can only be validated by the 9See the whiteboard episode with QuarkChain here: https://www.youtube.com/watch? v=opEtG6NM4x4, in which the approach to cross-shard transactions is discussed, among other things
Figure 20: Delayed receipts processing participants that maintain the state. They can be block producers, validators, or just external witnesses that downloaded the state and validate the shard in which they store assets. In this document we assume that majority of the participants cannot store the state for a large fraction of the shards. It is worth mentioning, however, that there are sharded blockchains that are designed with the assumption that most participants do have capacity to store the state for and validate most of the shards, such as QuarkChain. Since only a fraction of the participants have the state to validate the shard chunks, it is possible to adaptive corrupt just the participants that have the state, and apply an invalid state transition. Multiple sharding designs were proposed that sample validators every few days, and within a day any block in the shard chain that has more than 2/3 of signatures of the validators assigned to such shard is immediately considered final. With such approach an adaptive adversary only needs to corrupt 2n/3+1 of the validators in a shard chain to apply an invalid state transition, which, while is likely hard to pull off, is not a level of security sufficient for a public blockchain. As discussed in section 2.3, the common approach is to allow a certain window of time after a block is created for any participant that has state (whether it’s a block producer, a validator, or an external observer) to challenge its validity. Such participants are called Fishermen. For a fisherman to be able to challenge an invalid block, it must be ensured that such a block is available to them. The data availability in Nightshade is discussed in section 3.4. In Nightshade once a block is produced, the chunks were not validated by anyone but the actual chunk producer. In particular, the block producer that suggested the block naturally didn’t have the state for most of the shards, and
was not able to validate the chunks. When the next block is produced, it contains attestations (see section 3.2) of multiple block producers and validators, but since the majority of block producers and validators do not maintain state for most shards as well, a block with just one invalid chunk will collect significantly more than half of the attestations and will continue being on the heaviest chain. To address this issue, we allow any participant that maintains the state of a shard to submit a challenge on-chain for any invalid chunk produced in that shard. 3.7.1 State validity challenge Once a participant detects that a particular chunk is invalid, they need to provide a proof that the chunk is invalid. Since the majority of the network participants do not maintain the state for the shard in which the invalid chunk is produced, the proof needs to have sufficient information to confirm the block is invalid without having the state. We set a limit Ls of the amount of state (in bytes) that a single transaction can cumulatively read or write. Any transaction that touches more than Ls state is considered to be invalid. Remember from the section 3.5 that the chunk in a particular block B only contains the transactions to be applied, but not the new state root. The state root included in the chunk in block B is the state root before applying such transactions, but after applying the transactions from the last chunk in the same shard before the block B. A malicious actor that wishes to apply an invalid state transition would include an incorrect state root in block B that doesn’t correspond to the state root that results from applying the transactions in the preceding chunk. We extend the information that a chunk producer includes in the chunk. Instead of just including the state after applying all the transactions, it instead includes a state root after applying each contiguous set of transactions that collectively read and write Ls bytes of state. With this information for the fisherman to create a challenge that a state transition is applied incorrectly it is sufficient to find the first such invalid state root, and include just Ls bytes of state that are affected by the transactions between the last state root (which was valid) and the current state root with the merkle proofs. Then any participant can validate the transactions in the segment and confirm that the chunk is invalid. Similarly, if the chunk producer attempted to include transactions that read and write more than Ls bytes of state, for the challenge it is enough to include the first Ls bytes it touches with the merkle proofs, which will be enough to apply the transactions and confirm that there’s a moment when an attempt to read or write content beyond Ls bytes is made.
3.7.2 Fishermen and fast cross-shard transactions As discussed in section 2.3, once we assume that the shard chunks (or shard blocks in the model with shard chains) can be invalid and introduce a challenge period, it negatively affects the finality, and thus cross-shard communication. In particular, the destination shard of any cross-shard transction cannot be certain the originating shard chunk or block is final until the challenge period is over (see figure 21). Figure 21: Waiting for the challenge period before applying a receipt The way to address it in a way that makes the cross-shard transactions instantenious is for the destination shard to not wait for the challenge period after the source shard transaction is published, and apply the receipt transaction immediately, but then roll back the destination shard together with the source shard if later the originating chunk or block was found to be invalid (see figure 22). This applies very naturally to the Nightshade design in which the shard chains are not independent, but instead the shard chunks are all published together in the same main chain block. If any chunk is found to be invalid, the entire block with that chunk is considered invalid, and all the blocks built on top of it. See figure 23. Both of the above approaches provide atomicity assuming that the challenge period is sufficiently long. We use the latter approach since providing fast crossshard transactions under normal circumstances outweights the inconvenience of the destination shard rolling back due to an invalid state transition in one of the source shards, which is an extremely rare event. 3.7.3 Hiding validators The existence of the challenges already significantly reduces the probability of adaptive corruption, since to finalize a chunk with an invalid state transition post
Figure 22: Applying receipts immediately and rolling back the destination chain if the source chain had an invalid block Figure 23: Fisherman challenge in Nightshade the challenge period the adaptive adversary needs to corrupt all the participants that maintain the state of the shard, including all the validators. Estimating the likelihood of such an event is extremely complex, since no sharded blockchain has been live sufficiently long for any such attack to be attempted. We argue that the probability, while extremely low, is still sufficiently large for a system that is expected to execute multi-million transactions and run a world-wide financial operations. There are two main reasons for this belief: 1. Most of the validators of the Proof-of-Stake chains and miners of the
Proof-of-Work chains are primarily incentivized by the financial upside. If an adaptive adversary offers them more money then the expected return from operating honestly, it is reasonable to expect that many validators will accept the offer. 2. Many entities do validation of Proof-of-Stake chains professionally, and it is expected that a large percentage of the stake in any chain will be from such entities. The number of such entities is sufficiently small for an adaptive adversary to get to know most of them personally and have a good understanding of their inclanation to be corrupted. We take one step further in reducing the probability of the adaptive corruption by hiding which validators are assigned to which shard. The idea is remotely similar to the way Algorand [5] conceals validators. It is critical to note that even if the validators are concealed, as in Algorand or as described below, the adaptive corruption is still in theory possible. While the adaptive adversary doesn’t know the participants that will create or validate a block or a chunk, the participants themselves do know that they will perform such a task and have a cryptographic proof of it. Thus, the adversary can broadcast their intent to corrupt, and pay to any participant that will provide such a cryptographic proof. We note however, that since the adversary doesn’t know the validators that are assigned to the shard they want to corrupt, they have no other choice but to broadcast their intent to corrupt a particular shard to the entire community. At that point it is economically beneficial for any honest participant to spin up a full node that validates that shard, since there’s a high chance of an invalid block appearing in that shard, which is an opportunity to create a challenge and collect associated reward. To not reveal the validators that are assigned to a particular shard, we do the following (see figure 24): Using VRF to get the assignment. At the beginning of each epoch each validator uses a VRF to get a bitmask of the shards the validator is assigned to. The bitmask of each validator will have Sw bits (see section 3.3 for the definition of Sw). The validator then fetches the state of the corresponding shards, and during the epoch for each block received validates the chunks that correspond to the shards that the validator is assigned to. Sign on blocks instead of chunks. Since the shards assignment is concealed, the validator cannot sign on chunks. Instead it always signs on the entire block, thus not revealing what shards it validates. Specifically, when the validator receives a block and validates all the chunks, it either creates a message that attests that all the chunks in all the shards the validator is assigned to are valid (without indicating in any way what those shards are), or a message that contains a proof of an invalid state transition if any chunk is invalid. See the section 3.8 for the details on how such messages are aggregated, section 3.7.4 for the details on how to prevent validators from piggy-backing on messages from other validators, and section 3.7.5 for the details how to reward and punish validators should a successful invalid state transition challenge actually happen.
Figure 24: Concealing the validators in Nightshade 3.7.4 Commit-Reveal One of the common problems with validators is that a validator can skip downloading the state and actually validating the chunks and blocks, and instead observe the network, see what the other validators submit and repeat their messages. A validator that follows such a strategy doesn’t provide any extra security for the network, but collects rewards. A common solution for this problem is for each validator to provide a proof that they actually validated the block, for example by providing a unique trace of applying the state transition, but such proofs significantly increase the cost of validation. Figure 25: Commit-reveal
Instead we make the validators first commit to the validation result (either the message that attests to the validity of the chunks, or the proof of an invalid state transition), wait for a certain period, and only then reveal the actual validation result, as shown on figure 25. The commit period doesn’t intersect with the reveal period, and thus a lazy validator cannot copycat honest validators. Moreover, if a dishonest validator committed to a message that attests to the validity of the assigned chunks, and at least one chunk was invalid, once it is shown that the chunk is invalid the validator cannot avoid the slashing, since, as we show in section 3.7.5, the only way to not get slashed in such a situation is to present a message that contains a proof of the invalid state transition that matches the commit. 3.7.5 Handling challenges As discussed above, once a validator receives a block with an invalid chunk, they first prepare a proof of the invalid state transition (see section 3.7.1), then commit to such a proof (see 3.7.4), and after some period reveal the challenge. Once the revealed challenge is included in a block, the following happens: 1. All the state transitions that happened from the block containing the invalid chunk until the block in which the revealed challenge is included get nullyfied. The state before the block that includes the revealed challenge is considered to be the same as the state before the block that contained the invalid chunk. 2. Within a certain period of time each validator must reveal their bitmask of the shards they validate. Since the bitmask is created via a VRF, if they were assigned to the shard that had the invalid state transition, they cannot avoid revealing it. Any validator that fails to reveal the bitmask is assumed to be assigned to the shard. 3. Each validator that after such period is found to be assigned to the shard, that did commit to some validation result for the block containing the invalid chunk and that didn’t reveal the proof of invalid state transition that corresponds to their commit is slashed. 4. Each validator gets a new shards assignment, and a new epoch is scheduled to start after some time sufficient for all the validators to download the state, as shown on figure 26. Note that from the moment the validators reveal the shards they are assigned to until the new epoch starts the security of the system is reduced since the shards assignment is revealed. The participants of the network need to keep it in mind while using the network during such period. 3.8 Signature Aggregation For a system with hudreds of shards to operate securely, we want to have on the order of 10, 000 or more validators. As discussed in section 3.7, we want each
Figure 26: Handling the challenge validator to publish a commit to a certain message and a signature on average once per block. Even if the commit messages were the same, aggregating such a BLS-signature and validating it would have been prohibitively expensive. But naturally the commit and reveal messages are not the same across validators, and thus we need some way to aggregate such messages and the signatures in a way that allows for fast validation later. The specific approach we use is the following: Validators joining block producers. The block producers are known some time before the epoch starts, since they need some time to download the state before the epoch starts, and unlike the validators the block producers are not concealed. Each block producer has v validator slots. Validators submit off-chain proposals to the block producers to get included as one of their v validators. If a block producer wishes to include a validator, they submit a transaction that contains the initial off-chainrequest from the validator, and the block producer’s signature that makes the validator join the block producer. Note that the validators assigned to the block producers do not necessarily validate the same shards that the block producer produces chunks for. If a validator applied to join multiple block producers, only the transaction from the first block producer will succeed. Block producers collect commits. The block producer constantly collects the commit and reveal messages from the validators. Once a certain number of such messages are accumulated, the block producer computes a merkle tree of these messages, and sends to each validator the merkle root and the merkle path to their message. The validator validates the path and signs on the merkle root. The block producer then accumulates a BLS signature on the merkle root from the validators, and publishes only the merkle root and the accumulated signature. The block producer also signs on the validity of the multisignature using a cheap ECDSA signature. If the multisignature doesn’t match the merkle root submitted or the bitmask of the validators participating, it is a slashable behavior. When synchronizing the chain, a participant can choose to validate all the BLS signatures from the validators (which is extremely expensive since it involves aggregating validators public keys), or only
the ECDMA signatures from the block producers and rely on the fact that the block producer was not challenged and slashed. Using on-chain transactions and merkle proofs for challenges. It can be noted that there’s no value in revealing messages from validators if no invalid state transition was detected. Only the messages that contain the actual proofs of invalid state transition need to be revealed, and only for such messages it needs to be shown that they match the prior commit. The message needs to be revealed for two purposes: 1. To actually initiate the rollback of the chain to the moment before the invalid state transition (see section 3.7.5). 2. To prove that the validator didn’t attempt to attest to the validity of the invalid chunk. In either case we need to address two issues: 1. The actual commit was not included on chain, only the merkle root of the commit aggregated with other messages. The validator needs to use the merkle path provided by the block producer and their original commit to prove that they committed to the challenge. 2. It is possible that all the validators assigned to the shard with the invalid state transition happen to be assigned to corrupted block producers that are censoring them. To get around it we allow them to submit their reveals as a regular transaction on-chain and bypass the aggregation. The latter is only allowed for the proofs of invalid state transition, which are extremely rare, and thus should not result in spamming the blocks. The final issue that needs to be addressed is that the block producers can choose not to participate in messages aggregation or intentionally censor particular validators. We make it economically disadvantageous, by making the block producer reward proportional to the number of validators assigned to them. We also note that since the block producers between epochs largely intersect (since it’s always the top w participants with the highest stake), the validators can largely stick to working with the same block producers, and thus reduce the risk of getting assigned to a block producer that censored them in the past. 3.9 Snapshots Chain Since the blocks on the main chain are produced very frequently, downloading the full history might become expensive very quickly. Moreover, since every block contains a BLS signature of a large number of participants, just the aggregation of the public keys to check the signature might become prohibitively expensive as well. Finally, since in any foreseeable future Ethereum 1.0 will likely remain one of the most used blockchains, having a meaningful way to transfer assets from
Near to Ethereum is a requirement, and today verifying BLS signatures to ensure Near blocks validity on Ethereum’s side is not possible. Each block in the Nightshade main chain can optionally contain a Schnorr multisignature on the header of the last block that included such a Schnorr multisignature. We call such blocks snapshot blocks. The very first block of every epoch must be a snapshot block. While working on such a multisignature, the block producers must also accumulate the BLS signatures of the validators on the last snapshot block, and aggregate them the same way as described in section 3.8. 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 the snapshot blocks a snapshot chain. Creating a Schnorr multisignature is an interactive process, but since we only need to perform it infrequently, any, no matter how inefficient, process will suffice. The Schnorr multisignatures can be easily validated on Ethereum, thus providing crucial primitives for a secure way of performing cross-blockchain communication. To sync with the Near chain one only needs to download all the snapshot blocks and confirm that the Schnorr signatures are correct (optionally also verifying the individual BLS signatures of the validators), and then only syncing main chain blocks from the last snapshot block.
Nightshade
3.1 Từ chuỗi mảnh đến mảnh vỡ Mô hình sharding với chuỗi phân đoạn và chuỗi đèn hiệu rất mạnh mẽ nhưng có những phức tạp nhất định. Đặc biệt, quy tắc lựa chọn ngã ba cần được thực thi trong mỗi chuỗi riêng biệt, quy tắc lựa chọn ngã ba trong chuỗi phân đoạn và đèn hiệu chuỗi phải được xây dựng khác nhau và được thử nghiệm riêng biệt. Trong Nightshade, chúng tôi lập mô hình hệ thống dưới dạng một blockchain duy nhất, trong đó mỗi khối chứa tất cả các giao dịch cho tất cả các phân đoạn một cách hợp lý và thay đổi toàn bộ trạng thái của tất cả các mảnh vỡ. Tuy nhiên, về mặt vật lý, không có người tham gia nào tải xuống trạng thái đầy đủ hoặc khối logic đầy đủ. Thay vào đó, mỗi người tham gia mạng chỉ duy trì trạng thái tương ứng với các phân đoạn mà họ xác thực giao dịch và danh sách tất cả các giao dịch trong khối được chia thành các phần vật lý khối, một khối cho mỗi mảnh. Trong điều kiện lý tưởng, mỗi khối chứa chính xác một đoạn trên mỗi phân đoạn. khối, gần tương ứng với mô hình với các chuỗi phân đoạn trong đó chuỗi phân đoạn tạo ra các khối có cùng tốc độ với chuỗi đèn hiệu. Tuy nhiên, do sự chậm trễ của mạng, một số khối có thể bị thiếu, vì vậy trong thực tế mỗi khối chứa một hoặc không khối trên mỗi phân đoạn. Xem phần 3.3 để biết chi tiết về cách khối được sản xuất. Hình 16: Một mô hình có các chuỗi mảnh ở bên trái và có một chuỗi có các khối được chia thành các khối bên phải
3.2 Sự đồng thuận Hai cách tiếp cận chủ yếu để đạt được sự đồng thuận trong blockchain ngày nay là chuỗi dài nhất (hoặc nặng nhất), trong đó chuỗi có nhiều công việc hoặc cổ phần nhất được sử dụng để xây dựng nó được coi là chuẩn và BFT, trong đó đối với mỗi khối một số tập hợp validator đạt được sự đồng thuận BFT. Trong các giao thức được đề xuất gần đây thì cách thứ hai là cách tiếp cận ưu việt hơn, vì nó cung cấp tính hữu hạn ngay lập tức, trong khi ở chuỗi dài nhất cần nhiều khối hơn được xây dựng trên đỉnh của khối để đảm bảo tính cuối cùng. Thường vì một ý nghĩa bảo mật mất thời gian để xây dựng đủ số khối thứ tự giờ. Việc sử dụng sự đồng thuận BFT trên mỗi khối cũng có những nhược điểm, chẳng hạn như: 1. BFT sự đồng thuận đòi hỏi lượng trao đổi đáng kể. Trong khi những tiến bộ gần đây cho phép đạt được sự đồng thuận trong thời gian tuyến tính về số lượng của người tham gia (xem ví dụ: [4]), chi phí này vẫn đáng chú ý trên mỗi khối; 2. Tất cả những người tham gia mạng lưới đều không thể tham gia BFT sự đồng thuận trên mỗi khối, do đó thường chỉ có một tập hợp con người tham gia được lấy mẫu ngẫu nhiên đạt được sự đồng thuận. Về nguyên tắc, một tập hợp được lấy mẫu ngẫu nhiên có thể là về mặt lý thuyết có thể bị hỏng một cách thích ứng và một nhánh phân nhánh có thể được tạo ra. hệ thống hoặc cần phải được lập mô hình để sẵn sàng cho một sự kiện như vậy, và do đó vẫn có quy tắc lựa chọn nhánh bên cạnh sự đồng thuận BFT hoặc được thiết kế để đóng xuống trong một sự kiện như vậy. Điều đáng nói là một số thiết kế như Algorand [5], giảm đáng kể khả năng tham nhũng thích ứng. 3. Quan trọng nhất là hệ thống sẽ ngừng hoạt động nếu 1 3 hoặc nhiều hơn trong số tất cả những người tham gia là ngoại tuyến. Do đó, bất kỳ trục trặc mạng tạm thời hoặc sự chia tách mạng nào cũng có thể khiến hệ thống bị đình trệ hoàn toàn. Lý tưởng nhất là hệ thống phải có khả năng tiếp tục hoạt động miễn là có ít nhất một nửa số người tham gia trực tuyến (nặng nhất các giao thức dựa trên chuỗi tiếp tục hoạt động ngay cả khi có ít hơn một nửa số người tham gia trực tuyến, nhưng mức độ mong muốn của đặc tính này còn gây tranh cãi hơn trong cộng đồng). Một mô hình kết hợp trong đó sự đồng thuận được sử dụng là một trong những mô hình nặng nề nhất chuỗi, nhưng một số khối được hoàn thiện định kỳ bằng cách sử dụng tiện ích cuối cùng BFT duy trì những ưu điểm của cả hai mô hình. BFT tiện ích cuối cùng như vậy là Casper FFG [6] được sử dụng trong Ethereum 2.0 8, Casper CBC (xem https://vitalik. ca/general/2018/12/05/cbc_casper.html) và GRANDPA (xem https:// Medium.com/polkadot-network/d08a24a021b5) được sử dụng trong Polkadot. Nightshade sử dụng sự đồng thuận chuỗi cao nhất. Cụ thể khi một khối nhà sản xuất tạo ra một khối (xem phần 3.3), họ có thể thu thập chữ ký từ các nhà sản xuất khối khác và validator chứng thực khối trước đó. Xem phần 3.8 để biết chi tiết về cách tổng hợp số lượng chữ ký lớn như vậy. trọng lượng 8Ngoài ra, hãy xem phiên bảng trắng với Justin Drake để có cái nhìn tổng quan sâu sắc hơn về Casper FFG và cách nó được tích hợp với sự đồng thuận chuỗi nặng nhất GHOST tại đây: https://www. youtube.com/watch?v=S262StTwkmocủa một khối khi đó là cổ phần tích lũy của tất cả những người ký có chữ ký được đưa vào khối. Trọng lượng của chuỗi là tổng trọng lượng của khối. Để đạt được sự đồng thuận cao nhất trong chuỗi, chúng tôi sử dụng tiện ích cuối cùng sử dụng các chứng thực để hoàn thiện các khối. Để giảm độ phức tạp của hệ thống, chúng tôi sử dụng một tiện ích cuối cùng không ảnh hưởng đến quy tắc lựa chọn ngã ba dưới bất kỳ hình thức nào, và thay vào đó chỉ đưa ra các điều kiện cắt bổ sung, sao cho khi một khối được được hoàn thiện bởi tiện ích cuối cùng, việc phân nhánh là không thể trừ khi có một tỷ lệ phần trăm rất lớn tổng số cổ phần bị cắt giảm. Casper CBC là một tiện ích cuối cùng và chúng tôi hiện đang lưu ý đến mô hình Casper CBC. Chúng tôi cũng làm việc trên một giao thức BFT riêng biệt có tên là TxFlow. Vào thời điểm viết tài liệu này, không rõ liệu TxFlow có được sử dụng thay vì Casper hay không CBC. Tuy nhiên, chúng tôi lưu ý rằng việc lựa chọn tiện ích cuối cùng phần lớn là trực giao với phần còn lại của thiết kế. 3.3 Sản xuất khối Trong Nightshade có hai vai trò: nhà sản xuất khối và validators. Tại bất kỳ điểm hệ thống chứa w nhà sản xuất khối, w = 100 trong mô hình của chúng tôi và wv validators, trong mô hình của chúng tôi v = 100, wv = 10.000. Hệ thống là Bằng chứng cổ phần, có nghĩa là cả nhà sản xuất khối và validator đều có một số quyền nội bộ loại tiền tệ (được gọi là ”tokens”) bị khóa trong một khoảng thời gian vượt xa thời gian họ dành để thực hiện nhiệm vụ xây dựng và xác nhận chuỗi. Giống như tất cả các hệ thống Proof of Stake, không phải tất cả các nhà sản xuất khối w và không tất cả wv validator đều là các thực thể khác nhau vì điều đó không thể thực thi được. Mỗi Tuy nhiên, trong số các nhà sản xuất khối w và wv validators có một sự tách biệt cổ phần. Hệ thống chứa n phân đoạn, n = 1000 trong mô hình của chúng tôi. Như đã đề cập ở phần 3.1, trong Nightshade không có chuỗi phân đoạn, thay vào đó tất cả các nhà sản xuất khối và validator đang xây dựng một blockchain duy nhất mà chúng tôi gọi là chuỗi chính. Trạng thái của chuỗi chính được chia thành n phân đoạn và mỗi khối nhà sản xuất và validator bất kỳ lúc nào cũng chỉ tải xuống cục bộ một tập hợp con của trạng thái tương ứng với một số tập hợp con của phân đoạn và chỉ xử lý và xác thực các giao dịch ảnh hưởng đến các phần đó của trạng thái. Để trở thành nhà sản xuất khối, một người tham gia mạng sẽ khóa một số lượng lớn số lượng tokens (tiền đặt cọc). Việc bảo trì mạng được thực hiện theo thời gian, trong đó một kỷ nguyên là một khoảng thời gian theo thứ tự ngày. Những người tham gia với w cổ phần lớn nhất vào đầu một kỷ nguyên cụ thể là khối nhà sản xuất của thời đại đó. Mỗi nhà sản xuất khối được gán cho các phân đoạn sw, (giả sử sw = 40, điều này sẽ tạo ra sww/n = 4 nhà sản xuất khối trên mỗi phân đoạn). khối nhà sản xuất tải xuống trạng thái của phân đoạn mà họ được chỉ định trước kỷ nguyên bắt đầu và trong suốt thời kỳ đó sẽ thu thập các giao dịch ảnh hưởng đến phân đoạn đó, và áp dụng chúng cho nhà nước. Đối với mỗi khối b trên chuỗi chính và với mỗi phân đoạn, có một trong giao các nhà sản xuất khối cho s, người chịu trách nhiệm sản xuất phần liên quan của b đến mảnh vỡ. Phần của b liên quan đến phân đoạn s được gọi là đoạn và chứa danh sách các giao dịch cho phân đoạn được bao gồm trong b, cũng như merklegốc của trạng thái kết quả. b cuối cùng sẽ chỉ chứa một tiêu đề rất nhỏ của đoạn, cụ thể là gốc merkle của tất cả các giao dịch được áp dụng (xem phần 3.7.1 để biết chi tiết chính xác) và nghiệm merkle của trạng thái cuối cùng. Trong suốt phần còn lại của tài liệu, chúng tôi thường đề cập đến nhà sản xuất khối có trách nhiệm tạo ra một đoạn tại một thời điểm cụ thể cho một phân đoạn cụ thể với tư cách là một nhà sản xuất chunk. Nhà sản xuất chunk luôn là một trong những nhà sản xuất khối. Các nhà sản xuất khối và các nhà sản xuất khối xoay vòng từng khối theo theo một lịch trình cố định. Các nhà sản xuất khối có đơn đặt hàng và liên tục sản xuất khối theo thứ tự đó. Ví dụ. nếu có 100 nhà sản xuất khối thì khối đầu tiên nhà sản xuất chịu trách nhiệm sản xuất khối 1, 101, 201, v.v., khối thứ hai là chịu trách nhiệm sản xuất 2, 102, 202, v.v.). Vì sản xuất theo khối, không giống như sản xuất theo khối, đòi hỏi phải duy trì trạng thái và đối với mỗi phân đoạn, chỉ có nhà sản xuất khối sww/n mới duy trì trạng thái trên mỗi phân đoạn, tương ứng chỉ những nhà sản xuất khối sww/n mới xoay vòng để tạo khối. Ví dụ. với các hằng số ở trên với bốn nhà sản xuất khối được gán cho mỗi phân đoạn, mỗi nhà sản xuất khối sẽ tạo ra các khối cứ bốn khối một lần. 3,4 Đảm bảo tính sẵn có của dữ liệu Để đảm bảo tính khả dụng của dữ liệu, chúng tôi sử dụng phương pháp tương tự như phương pháp của Polkadot được mô tả ở phần 2.5.3. Khi nhà sản xuất khối tạo ra một đoạn, họ sẽ tạo một phiên bản được mã hóa xóa của nó với mã khối tối ưu (w, ⌊w/6 + 1⌋) của khúc. Sau đó, họ gửi một phần của đoạn mã bị xóa (chúng tôi gọi những phần đó là từng phần hoặc chỉ các phần) cho mỗi nhà sản xuất khối. Chúng tôi tính toán một cây merkle chứa tất cả các phần là lá và tiêu đề của mỗi đoạn chứa gốc merkle của cây đó. Các bộ phận được gửi tới validator thông qua tin nhắn một phần. Mỗi tin nhắn như vậy chứa tiêu đề chunk, thứ tự của phần và nội dung phần. các tin nhắn cũng chứa chữ ký của nhà sản xuất khối đã tạo ra chunk và đường dẫn merkle để chứng minh rằng phần đó tương ứng với tiêu đề và được sản xuất bởi nhà sản xuất khối thích hợp. Khi nhà sản xuất khối nhận được khối chuỗi chính, trước tiên họ sẽ kiểm tra xem chúng có có các thông điệp một phần cho mỗi đoạn được bao gồm trong khối. Nếu không, khối không được xử lý cho đến khi các tin nhắn onepart bị thiếu được lấy ra. Sau khi nhận được tất cả các tin nhắn một phần, nhà sản xuất khối sẽ tìm nạp các phần còn lại từ các đồng nghiệp và xây dựng lại các khối mà chúng nắm giữ nhà nước. Nhà sản xuất khối không xử lý khối chuỗi chính nếu có ít nhất một khối đoạn được bao gồm trong khối thì chúng không có thông báo một phần tương ứng hoặc nếu đối với ít nhất một phân đoạn mà chúng duy trì trạng thái thì chúng không thể xây dựng lại toàn bộ đoạn. Để có sẵn một đoạn cụ thể, chỉ cần ⌊w/6⌋+1 của khối là đủ nhà sản xuất có bộ phận của họ và phục vụ họ. Vì vậy, miễn là số lượng tác nhân độc hại không vượt quá ⌊w/3⌋không có chuỗi nào có hơn nửa khối các nhà sản xuất xây dựng nó có thể có những phần không có sẵn.Hình 17: Mỗi khối chứa một hoặc không có khối trên mỗi phân đoạn và mỗi khối được mã hóa xóa. Mỗi phần của đoạn mã xóa được gửi đến một địa chỉ được chỉ định nhà sản xuất khối thông qua tin nhắn onepart đặc biệt 3.4.1 Đối phó với các nhà sản xuất khối lười biếng Nếu nhà sản xuất khối có một khối bị thiếu thông báo một phần, họ sẽ có thể chọn vẫn đăng nhập vào nó, bởi vì nếu khối đó cuối cùng vẫn nằm trong chuỗi sẽ tối đa hóa phần thưởng cho nhà sản xuất khối. Không có rủi ro cho việc chặn nhà sản xuất vì sau này không thể chứng minh rằng nhà sản xuất khối không có tin nhắn một phần. Để giải quyết vấn đề này, chúng tôi tạo ra mỗi nhà sản xuất đoạn khi tạo đoạn để chọn một màu (đỏ hoặc xanh) cho từng phần của đoạn được mã hóa trong tương lai và lưu trữ bitmask của màu được gán trong đoạn trước khi nó được mã hóa. Mỗi phần một sau đó thông báo chứa màu được gán cho phần đó và màu này được sử dụng khi tính toán gốc merkle của các phần được mã hóa. Nếu nhà sản xuất chunk đi chệch hướng từ giao thức, điều đó có thể được chứng minh dễ dàng vì gốc merkle sẽ không tương ứng với tin nhắn một phần hoặc màu sắc trong tin nhắn một phần tương ứng với gốc merkle sẽ không khớp với mặt nạ trong đoạn. Khi nhà sản xuất khối ký vào một khối, họ sẽ bao gồm một bitmask của tất cả phần màu đỏ mà họ nhận được cho các khối có trong khối. Xuất bản một bitmask không chính xác là một hành vi có thể gạch chéo. Nếu nhà sản xuất khối chưa nhận được một tin nhắn, họ không có cách nào biết được màu sắc của tin nhắn, và do đó có 50% khả năng bị chém nếu họ cố gắng mù quáng ký vào bản hợp đồng. khối. 3,5 Ứng dụng chuyển trạng thái Nhà sản xuất khối chỉ chọn những giao dịch nào sẽ được đưa vào khối nhưng không áp dụng chuyển đổi trạng thái khi chúng tạo ra một đoạn. Tương ứng,
tiêu đề chunk chứa gốc merkle của trạng thái merkelized như trước các giao dịch trong chunk được áp dụng. Các giao dịch chỉ được áp dụng khi một khối đầy đủ bao gồm đoạn được xử lý. Một người tham gia chỉ xử lý một khối nếu 1. Khối trước đó đã được nhận và xử lý; 2. Đối với mỗi đoạn, người tham gia không duy trì trạng thái vì họ có đã xem tin nhắn onepart; 3. Đối với mỗi đoạn, người tham gia duy trì trạng thái vì họ có đoạn đầy đủ. Sau khi khối được xử lý, đối với mỗi phân đoạn mà người tham gia duy trì trạng thái, áp dụng các giao dịch và tính toán trạng thái mới kể từ sau khi các giao dịch được áp dụng, sau đó họ đã sẵn sàng sản xuất các khối cho khối tiếp theo, nếu chúng được gán cho bất kỳ phân đoạn nào, vì chúng có gốc merkle của trạng thái merkelized mới. 3.6 Giao dịch và biên lai chéo Nếu một giao dịch cần ảnh hưởng đến nhiều phân đoạn, thì nó cần phải được thực hiện liên tục được thực hiện trong từng phân đoạn riêng biệt. Giao dịch đầy đủ được gửi đến phân đoạn đầu tiên bị ảnh hưởng và khi giao dịch được bao gồm trong khối cho phân đoạn đó và được áp dụng sau khi đoạn được đưa vào một khối, nó tạo ra cái gọi là biên nhận giao dịch, được chuyển đến phân đoạn tiếp theo mà giao dịch cần thực hiện được thực thi. Nếu cần nhiều bước hơn, việc thực hiện giao dịch nhận tạo ra một giao dịch biên nhận mới, v.v. 3.6.1 Thời gian nhận giao dịch Điều mong muốn là giao dịch nhận được áp dụng trong khối ngay sau khối mà nó được tạo. Giao dịch nhận tiền chỉ được tạo sau khi khối trước đó được các nhà sản xuất khối nhận và áp dụng duy trì phân đoạn ban đầu và cần được biết vào thời điểm chunk cho khối tiếp theo được tạo ra bởi nhà sản xuất khối của đích mảnh vỡ. Do đó, biên nhận phải được truyền từ phân đoạn nguồn đến phân đoạn đích trong khung thời gian ngắn giữa hai sự kiện đó. Đặt A là khối được tạo cuối cùng chứa giao dịch t tạo ra biên nhận r. Đặt B là khối được tạo tiếp theo (tức là khối có A là khối trước đó của nó) mà chúng ta muốn chứa r. Đặt t ở trong mảnh a và r là trong mảnh vỡ b. Thời hạn sử dụng của biên nhận, cũng được mô tả trên hình 18, như sau: Lập và lưu trữ hóa đơn. Cpa của nhà sản xuất chunk cho phân đoạn a nhận khối A, áp dụng giao dịch t và tạo biên nhận r. cpa sau đó lưu trữ tất cả các biên lai được tạo ra như vậy trong bộ lưu trữ liên tục nội bộ được lập chỉ mục theo id phân đoạn nguồn.Phân phối các khoản thu. Khi cpa đã sẵn sàng để tạo đoạn cho phân đoạn a cho khối B, họ tìm nạp tất cả các biên lai được tạo bằng cách áp dụng các giao dịch từ khối A cho phân đoạn a và đưa chúng vào đoạn cho phân đoạn a trong khối B. Một khi đoạn như vậy được tạo ra, cpa sẽ tạo ra mã xóa của nó phiên bản và tất cả các thông báo onepart tương ứng. cpa biết nhà sản xuất khối nào duy trì trạng thái đầy đủ cho phân đoạn nào. Đối với một nhà sản xuất khối cụ thể bp cpa bao gồm các khoản thu được từ việc áp dụng các giao dịch trong khối A đối với phân đoạn a có bất kỳ phân đoạn nào mà bp quan tâm làm đích đến của họ trong tin nhắn onepart khi họ phân phối đoạn cho phân đoạn a trong khối B (xem hình 17, hiển thị các biên nhận có trong thông báo một phần). Nhận biên lai. Hãy nhớ rằng những người tham gia (cả nhà sản xuất khối và validator) không xử lý các khối cho đến khi họ có thông báo một phần cho mỗi đoạn có trong khối. Do đó, vào thời điểm bất kỳ người tham gia cụ thể nào áp dụng khối B, họ có tất cả các thông báo một phần tương ứng với các khối trong B và do đó họ có tất cả các biên nhận đến có các phân đoạn người tham gia duy trì trạng thái làm điểm đến của họ. Khi áp dụng các chuyển trạng thái cho một phân đoạn cụ thể, người tham gia sẽ áp dụng cả biên lai mà họ đã thu thập cho phân đoạn trong tin nhắn một phần, cũng như tất cả các giao dịch được bao gồm trong chính đoạn đó. Hình 18: Thời gian tồn tại của một giao dịch biên nhận 3.6.2 Xử lý quá nhiều biên lai Có thể số lượng biên lai nhắm mục tiêu vào một phân đoạn cụ thể trong một khối cụ thể quá lớn để được xử lý. Ví dụ, hãy xem xét hình 19, trong mỗi giao dịch trong mỗi phân đoạn sẽ tạo ra một biên nhận nhắm mục tiêu phân đoạn 1. Ở khối tiếp theo, số biên nhận mà phân đoạn 1 cần xử lý là có thể so sánh với tải mà tất cả các phân đoạn kết hợp được xử lý trong khi xử lý khối trước đó.
Hình 19: Nếu tất cả các khoản thu đều nhắm mục tiêu vào cùng một phân đoạn thì phân đoạn đó có thể không có khả năng xử lý chúng Để giải quyết vấn đề này, chúng tôi sử dụng một kỹ thuật tương tự như kỹ thuật được sử dụng trong QuarkChain 9. Cụ thể, đối với mỗi phân đoạn, khối B cuối cùng và phân đoạn cuối cùng trong đó khối mà biên lai được áp dụng được ghi lại. Khi có phân đoạn mới được tạo, biên nhận được áp dụng theo thứ tự đầu tiên từ các phân đoạn còn lại trong B, và sau đó theo các khối theo B, cho đến khi khối mới đầy. Dưới mức bình thường trường hợp có tải trọng cân bằng nhìn chung sẽ dẫn đến tất cả các khoản thu đang được áp dụng (và do đó phân đoạn cuối cùng của khối cuối cùng sẽ được ghi lại cho từng đoạn), nhưng trong những thời điểm tải không cân bằng và một phần cụ thể phân đoạn nhận được nhiều biên lai không tương xứng, kỹ thuật này cho phép họ được xử lý đồng thời tôn trọng các giới hạn về số lượng giao dịch được đưa vào. Lưu ý rằng nếu tải không cân bằng như vậy tồn tại trong một thời gian dài thì độ trễ từ việc tạo biên lai cho đến khi ứng dụng có thể tiếp tục phát triển vô thời hạn. một cách để giải quyết vấn đề này là loại bỏ bất kỳ giao dịch nào tạo ra biên nhận nhắm mục tiêu phân đoạn có độ trễ xử lý vượt quá một số hằng số (ví dụ: một kỷ nguyên). Hãy xem xét hình 20. Theo khối B, phân đoạn 4 không thể xử lý tất cả các biên nhận, vì vậy nó chỉ xử lý nguồn gốc biên lai từ tối đa phân đoạn 3 trong khối A và ghi lại nó. Trong khối C, bao gồm các khoản thu lên tới phân đoạn 5 trong khối B và sau đó đến khối D, phân đoạn sẽ bắt kịp, xử lý tất cả các khoản thu còn lại trong khối B và tất cả các khoản thu từ khối C. 3,7 Xác thực khối Một đoạn được tạo cho một phân đoạn cụ thể (hoặc một khối phân đoạn được tạo cho một chuỗi phân đoạn cụ thể trong mô hình có chuỗi phân đoạn) chỉ có thể được xác thực bởi 9Xem tập bảng trắng với QuarkChain tại đây: https://www.youtube.com/watch? v=opEtG6NM4x4, trong đó cách tiếp cận các giao dịch chéo được thảo luận, cùng với các vấn đề khác nhiều thứHình 20: Xử lý biên lai bị trì hoãn những người tham gia duy trì trạng thái. Họ có thể là nhà sản xuất khối, validators, hoặc chỉ những nhân chứng bên ngoài đã tải xuống trạng thái và xác thực phân đoạn trong mà họ lưu trữ tài sản. Trong tài liệu này chúng tôi giả định rằng phần lớn những người tham gia không thể lưu trữ trạng thái cho một phần lớn các phân đoạn. Tuy nhiên, điều đáng nói là rằng có blockchain được phân chia được thiết kế với giả định rằng hầu hết người tham gia đều có khả năng lưu trữ trạng thái và xác thực hầu hết các phân đoạn, chẳng hạn như QuarkChain. Vì chỉ một phần nhỏ người tham gia có trạng thái xác thực phân đoạn các khối, có thể thích ứng với tham nhũng chỉ những người tham gia có trạng thái và áp dụng chuyển đổi trạng thái không hợp lệ. Nhiều thiết kế phân đoạn đã được đề xuất lấy mẫu validator cứ sau vài lần ngày và trong vòng một ngày, bất kỳ khối nào trong chuỗi phân đoạn có hơn 2/3 chữ ký của validator được gán cho phân đoạn đó sẽ được xem xét ngay lập tức cuối cùng. Với cách tiếp cận như vậy, đối thủ thích ứng chỉ cần làm hỏng 2n/3+1 của validator trong chuỗi phân đoạn để áp dụng chuyển đổi trạng thái không hợp lệ, trong đó, mặc dù có thể khó thực hiện nhưng mức độ bảo mật không đủ cho công chúng blockchain. Như đã thảo luận trong phần 2.3, cách tiếp cận phổ biến là cho phép một khoảng thời gian nhất định sau khi khối được tạo cho bất kỳ người tham gia nào có trạng thái (cho dù đó là nhà sản xuất khối, validator hoặc người quan sát bên ngoài) để thách thức tính hợp lệ của nó. Những người tham gia như vậy được gọi là Ngư dân. Để một ngư dân có thể thách thức một khối không hợp lệ, phải đảm bảo rằng khối đó có sẵn để họ. Tính khả dụng của dữ liệu trong Nightshade được thảo luận trong phần 3.4. Trong Nightshade khi một khối được tạo ra, các khối không được xác thực bởi bất cứ ai ngoại trừ nhà sản xuất chunk thực sự. Đặc biệt, nhà sản xuất khối đó đề xuất khối tự nhiên không có trạng thái cho hầu hết các phân đoạn vàđã không thể xác nhận các khối. Khi khối tiếp theo được tạo ra, nó chứa các chứng thực (xem phần 3.2) của nhiều nhà sản xuất khối và validators, nhưng vì phần lớn các nhà sản xuất khối và validator không duy trì trạng thái đối với hầu hết các phân đoạn, một khối chỉ có một đoạn không hợp lệ sẽ thu thập được hơn một nửa số chứng thực và sẽ tiếp tục ở trạng thái nặng nhất. chuỗi. Để giải quyết vấn đề này, chúng tôi cho phép bất kỳ người tham gia nào duy trì trạng thái một phân đoạn để gửi thử thách trên chuỗi cho bất kỳ đoạn không hợp lệ nào được tạo ra trong đó mảnh vỡ. 3.7.1 Thử thách tính hợp lệ của trạng thái Khi người tham gia phát hiện thấy một đoạn cụ thể không hợp lệ, họ cần cung cấp bằng chứng cho thấy đoạn đó không hợp lệ. Vì phần lớn những người tham gia mạng không duy trì trạng thái cho phân đoạn có đoạn không hợp lệ được tạo ra, bằng chứng cần phải có đủ thông tin để xác nhận khối đó là không hợp lệ nếu không có trạng thái. Chúng tôi đặt giới hạn Ls về số lượng trạng thái (tính bằng byte) mà một giao dịch đơn lẻ có thể đọc hoặc viết tích lũy. Bất kỳ giao dịch nào chạm nhiều hơn Ls trạng thái được coi là không hợp lệ. Hãy nhớ từ phần 3.5 rằng đoạn trong khối B cụ thể chỉ chứa các giao dịch được áp dụng chứ không chứa gốc trạng thái mới. Gốc trạng thái có trong đoạn trong khối B là trạng thái root trước khi áp dụng các giao dịch đó, nhưng sau khi áp dụng các giao dịch từ đoạn cuối cùng trong cùng phân đoạn trước khối B. Một tác nhân độc hại mong muốn áp dụng chuyển đổi trạng thái không hợp lệ sẽ bao gồm gốc trạng thái không chính xác trong khối B không tương ứng với gốc trạng thái do áp dụng các giao dịch ở đoạn trước. Chúng tôi mở rộng thông tin mà nhà sản xuất chunk đưa vào chunk. Thay vì chỉ thêm trạng thái sau khi áp dụng tất cả các giao dịch, nó thay vào đó bao gồm một gốc trạng thái sau khi áp dụng từng bộ giao dịch liền kề đọc và ghi chung Ls byte trạng thái. Với thông tin này cho Fisherman tạo ra một thách thức rằng việc chuyển đổi trạng thái được áp dụng không chính xác là đủ để tìm ra gốc trạng thái không hợp lệ đầu tiên và chỉ bao gồm Ls byte của trạng thái bị ảnh hưởng bởi các giao dịch giữa trạng thái gốc cuối cùng (được hợp lệ) và trạng thái gốc hiện tại với bằng chứng merkle. Sau đó bất kỳ người tham gia nào có thể xác thực các giao dịch trong phân đoạn và xác nhận rằng đoạn đó là không hợp lệ. Tương tự, nếu nhà sản xuất chunk cố gắng đưa vào các giao dịch đọc và ghi nhiều hơn L byte trạng thái, đối với thử thách này, chỉ cần bao gồm Ls byte đầu tiên mà nó chạm tới với bằng chứng merkle, điều này sẽ đủ để áp dụng các giao dịch và xác nhận rằng sẽ có lúc cố gắng thực hiện đọc hoặc ghi nội dung vượt quá Ls byte được thực hiện.
3.7.2 Ngư dân và giao dịch xuyên mảnh nhanh chóng Như đã thảo luận trong phần 2.3, khi chúng ta giả định rằng các đoạn phân đoạn (hoặc phân đoạn các khối trong mô hình có chuỗi phân đoạn) có thể không hợp lệ và gây ra thách thức theo thời gian, nó ảnh hưởng tiêu cực đến tính cuối cùng và do đó giao tiếp giữa các phân đoạn. trong cụ thể, phân đoạn đích của bất kỳ chuyển đổi chéo nào đều không thể chắc chắn đoạn hoặc khối phân đoạn ban đầu là cuối cùng cho đến khi giai đoạn thử thách kết thúc (xem hình 21). Hình 21: Chờ đợi thời gian thử thách trước khi áp dụng biên nhận Cách giải quyết vấn đề theo cách thực hiện các giao dịch chéo tức thời là để mảnh đích không phải đợi đến giai đoạn thử thách sau khi giao dịch phân đoạn nguồn được xuất bản và áp dụng giao dịch biên nhận ngay lập tức, nhưng sau đó khôi phục phân đoạn đích cùng với phân đoạn nguồn phân đoạn nếu sau đó đoạn hoặc khối ban đầu được phát hiện là không hợp lệ (xem hình 22). Điều này áp dụng rất tự nhiên cho thiết kế Nightshade trong đó mảnh vỡ các chuỗi không độc lập mà thay vào đó, các đoạn phân đoạn đều được xuất bản cùng nhau trong cùng một khối chuỗi chính. Nếu bất kỳ đoạn nào được phát hiện là không hợp lệ, toàn bộ khối có đoạn đó được coi là không hợp lệ và tất cả các khối được xây dựng trên trên hết. Xem hình 23. Cả hai cách tiếp cận trên đều cung cấp tính nguyên tử giả định rằng thách thức thời gian đủ dài. Chúng tôi sử dụng phương pháp thứ hai vì việc cung cấp các giao dịch chéo nhanh trong các trường hợp thông thường sẽ vượt qua sự bất tiện của phân đoạn đích quay trở lại do chuyển đổi trạng thái không hợp lệ ở một trong các các mảnh nguồn, đây là một sự kiện cực kỳ hiếm. 3.7.3 Đang ẩn validators Sự tồn tại của những thách thức đã làm giảm đáng kể khả năng xảy ra tham nhũng thích ứng, vì để hoàn thiện một đoạn có bài chuyển đổi trạng thái không hợp lệHình 22: Áp dụng biên lai ngay lập tức và quay trở lại điểm đến chuỗi nếu chuỗi nguồn có khối không hợp lệ Hình 23: Thử thách làm ngư dân trong Nightshade giai đoạn thử thách mà đối thủ thích ứng cần để làm hỏng tất cả những người tham gia duy trì trạng thái của phân đoạn, bao gồm tất cả validator. Việc ước tính khả năng xảy ra một sự kiện như vậy là vô cùng phức tạp, vì không có sharded blockchain đã tồn tại đủ lâu để thực hiện bất kỳ cuộc tấn công nào như vậy. Chúng tôi lập luận rằng xác suất, mặc dù cực kỳ thấp, nhưng vẫn đủ lớn đối với một hệ thống dự kiến sẽ thực hiện hàng triệu giao dịch và điều hành các hoạt động tài chính trên toàn thế giới. Có hai lý do chính cho niềm tin này: 1. Hầu hết validator của chuỗi Bằng chứng cổ phần và công cụ khai thác của
Chuỗi Proof-of-Work chủ yếu được khuyến khích bởi lợi ích tài chính. Nếu một đối thủ có khả năng thích ứng mang lại cho họ nhiều tiền hơn lợi nhuận kỳ vọng từ việc vận hành một cách trung thực, thật hợp lý khi mong đợi rằng nhiều validators sẽ chấp nhận lời đề nghị. 2. Nhiều tổ chức thực hiện xác thực chuỗi Proof-of-Stake một cách chuyên nghiệp và người ta dự kiến rằng một tỷ lệ lớn cổ phần trong bất kỳ chuỗi nào sẽ được từ các thực thể đó. Số lượng các thực thể như vậy đủ nhỏ để đối thủ thích nghi để tìm hiểu cá nhân hầu hết họ và có một hiểu rõ khuynh hướng của họ là bị tha hóa. Chúng tôi tiến thêm một bước nữa trong việc giảm khả năng xảy ra lỗi thích ứng bằng cách ẩn validator được gán cho phân đoạn nào. Ý tưởng là tương tự như cách Algorand [5] che giấu validators. Điều quan trọng cần lưu ý là ngay cả khi validator bị ẩn, như trong Algorand hoặc như được mô tả dưới đây, về mặt lý thuyết, tham nhũng thích ứng vẫn có thể xảy ra. Trong khi đối thủ thích ứng không biết những người tham gia sẽ tạo hoặc xác thực một khối hay một đoạn, bản thân những người tham gia đều biết rằng họ sẽ thực hiện một nhiệm vụ như vậy và có bằng chứng mật mã về nó. Vì vậy, đối thủ có thể truyền bá ý định tham nhũng của họ và trả tiền cho bất kỳ người tham gia nào sẽ cung cấp một bằng chứng mật mã như vậy. Tuy nhiên, chúng tôi lưu ý rằng vì đối thủ không biết validator được gán cho phân đoạn mà chúng muốn làm hỏng, chúng không có lựa chọn nào khác ngoài việc truyền bá ý định làm hỏng một phân đoạn cụ thể tới toàn bộ cộng đồng. Vào thời điểm đó, nó mang lại lợi ích kinh tế cho bất kỳ người trung thực nào. người tham gia tạo ra một nút đầy đủ để xác thực phân đoạn đó vì có mức cao khả năng một khối không hợp lệ xuất hiện trong phân đoạn đó, đây là cơ hội để tạo ra một thử thách và thu thập phần thưởng liên quan. Để không tiết lộ validator được gán cho một phân đoạn cụ thể, chúng tôi thực hiện sau đây (xem hình 24): Sử dụng VRF để nhận nhiệm vụ. Vào đầu mỗi thời đại, mỗi validator sử dụng VRF để lấy mặt nạ bit của các phân đoạn mà validator được gán cho. Mặt nạ bit của mỗi validator sẽ có các bit Sw (xem phần 3.3 để biết định nghĩa của Sw). validator sau đó tìm nạp trạng thái của các phân đoạn tương ứng và trong kỷ nguyên cho mỗi khối nhận được sẽ xác thực các khối tương ứng vào các phân đoạn mà validator được gán cho. Đăng nhập vào khối thay vì khối. Vì việc gán phân đoạn bị ẩn nên validator không thể đăng nhập vào các phân đoạn. Thay vào đó nó luôn ký trên toàn bộ chặn, do đó không tiết lộ những phân đoạn mà nó xác nhận. Cụ thể, khi validator nhận được một khối và xác thực tất cả các khối, nó sẽ tạo ra một thông báo chứng thực rằng tất cả các đoạn trong tất cả các phân đoạn mà validator được chỉ định là hợp lệ (không cho biết những phân đoạn đó là gì) hoặc một thông báo rằng chứa bằng chứng về việc chuyển đổi trạng thái không hợp lệ nếu bất kỳ đoạn nào không hợp lệ. Xem phần 3.8 để biết chi tiết về cách tổng hợp các thông báo đó, phần 3.7.4 để biết chi tiết về cách ngăn chặn validator lợi dụng tin nhắn từ validators khác và phần 3.7.5 để biết chi tiết về cách khen thưởng và trừng phạt validators nếu thử thách chuyển đổi trạng thái không hợp lệ thành công thực sự xảy ra.Hình 24: Che giấu validator trong Nightshade 3.7.4 Cam kết-Tiết lộ Một trong những vấn đề phổ biến với validator là validator có thể bỏ qua việc tải xuống trạng thái và thực sự xác thực các khối và khối, thay vào đó quan sát mạng, xem những gì validator khác gửi và lặp lại tin nhắn. validator tuân theo chiến lược như vậy sẽ không cung cấp thêm bất kỳ bảo mật cho mạng nhưng thu thập phần thưởng. Một giải pháp phổ biến cho vấn đề này là mỗi validator cung cấp bằng chứng rằng họ thực sự đã xác thực khối đó, chẳng hạn như bằng cách cung cấp dấu vết duy nhất áp dụng chuyển đổi trạng thái, nhưng những bằng chứng như vậy làm tăng đáng kể chi phí xác nhận. Hình 25: Cam kết tiết lộ
Thay vào đó, chúng tôi thực hiện cam kết đầu tiên của validator với kết quả xác thực (hoặc thông báo chứng thực tính hợp lệ của các khối hoặc bằng chứng về tính hợp lệ của chuyển trạng thái), đợi một khoảng thời gian nhất định và chỉ sau đó mới tiết lộ kết quả xác thực thực tế, như được hiển thị trên hình 25. Khoảng thời gian cam kết không giao nhau với khoảng thời gian tiết lộ và do đó một validator lười biếng không thể bắt chước những validator trung thực. Hơn nữa, nếu một validator không trung thực cam kết thực hiện một thông báo chứng thực tính hợp lệ của các đoạn được gán và ít nhất một đoạn không hợp lệ một khi nó được đã chỉ ra rằng đoạn đó không hợp lệ nên validator không thể tránh được việc gạch chéo, vì, như chúng tôi trình bày trong phần 3.7.5, cách duy nhất để không bị chém trong tình huống như vậy là đưa ra một thông báo chứa bằng chứng về việc chuyển đổi trạng thái không hợp lệ phù hợp với cam kết. 3.7.5 Xử lý thử thách Như đã thảo luận ở trên, khi validator nhận được một khối có đoạn không hợp lệ, đầu tiên họ chuẩn bị bằng chứng về sự chuyển đổi trạng thái không hợp lệ (xem phần 3.7.1), sau đó cam kết với một bằng chứng như vậy (xem 3.7.4), và sau một thời gian hãy tiết lộ thách thức. Khi thử thách được tiết lộ được đưa vào một khối, điều sau đây sẽ xảy ra: 1. Tất cả các chuyển đổi trạng thái xảy ra từ khối chứa đoạn không hợp lệ cho đến khi khối chứa thử thách được tiết lộ bị vô hiệu hóa. Trạng thái trước khối bao gồm thử thách được tiết lộ được coi là giống với trạng thái trước khối chứa đoạn không hợp lệ. 2. Trong một khoảng thời gian nhất định, mỗi validator phải tiết lộ mặt nạ bit của mình của các phân đoạn mà họ xác nhận. Vì mặt nạ bit được tạo thông qua VRF, nếu họ được gán cho phân đoạn có quá trình chuyển đổi trạng thái không hợp lệ, họ không thể tránh khỏi việc tiết lộ nó. Bất kỳ validator nào không tiết lộ được mặt nạ bit được cho là được gán cho phân đoạn. 3. Mỗi validator sau khoảng thời gian đó được phát hiện sẽ được gán cho phân đoạn, đã cam kết với một số kết quả xác thực cho khối chứa đoạn không hợp lệ và điều đó không tiết lộ bằng chứng về việc chuyển đổi trạng thái không hợp lệ tương ứng với cam kết của họ bị cắt giảm. 4. Mỗi validator nhận được một phân đoạn mới và một kỷ nguyên mới được lên lịch bắt đầu sau một khoảng thời gian đủ để tất cả validator tải xuống trạng thái, như thể hiện trên hình 26. Lưu ý rằng kể từ thời điểm validator tiết lộ các phân đoạn mà chúng được chỉ định cho đến khi kỷ nguyên mới bắt đầu, tính bảo mật của hệ thống sẽ bị giảm do phân công mảnh vỡ được tiết lộ. Những người tham gia mạng cần phải giữ nó lưu ý khi sử dụng mạng trong thời gian đó. 3,8 Tổng hợp chữ ký Để một hệ thống có hàng trăm phân đoạn hoạt động an toàn, chúng tôi muốn có trên đơn hàng từ 10.000 trở lên validators. Như đã thảo luận trong phần 3.7, chúng tôi muốn mỗiHình 26: Xử lý thử thách validator để xuất bản một cam kết cho một tin nhắn nhất định và một chữ ký ở mức trung bình một lần cho mỗi khối. Ngay cả khi các thông điệp cam kết giống nhau, việc tổng hợp như vậy Chữ ký BLS và việc xác nhận nó sẽ rất tốn kém. Nhưng đương nhiên các thông báo cam kết và tiết lộ không giống nhau trên validators, và do đó chúng ta cần một số cách để tổng hợp các thông điệp và chữ ký đó trong một cách cho phép xác nhận nhanh chóng sau này. Cách tiếp cận cụ thể mà chúng tôi sử dụng như sau: Người xác nhận tham gia các nhà sản xuất khối. Các nhà sản xuất khối được biết đến một thời gian trước khi kỷ nguyên bắt đầu, vì họ cần một chút thời gian để tải xuống trạng thái trước khi kỷ nguyên bắt đầu và không giống như validator, các nhà sản xuất khối không che giấu. Mỗi nhà sản xuất khối có v validator vị trí. Trình xác nhận gửi đề xuất ngoài chuỗi cho các nhà sản xuất khối để được đưa vào như một trong những v validators. Nếu nhà sản xuất khối muốn bao gồm validator, họ sẽ gửi giao dịch chứa yêu cầu ngoài chuỗi ban đầu từ validator và chữ ký của nhà sản xuất khối khiến validator tham gia nhà sản xuất khối. Lưu ý rằng validator được gán cho nhà sản xuất khối không nhất thiết xác thực các phân đoạn tương tự mà nhà sản xuất khối tạo ra các khối. Nếu một validator áp dụng để tham gia nhiều nhà sản xuất khối, chỉ giao dịch từ nhà sản xuất khối đầu tiên sẽ thành công. Các nhà sản xuất khối thu thập các cam kết. Nhà sản xuất khối liên tục thu thập các thông báo cam kết và tiết lộ từ validator. Khi một số lượng tin nhắn như vậy nhất định được tích lũy, nhà sản xuất khối sẽ tính toán một merkle cây của những tin nhắn này và gửi tới mỗi validator gốc merkle và đường dẫn merkle đến tin nhắn của họ. validator xác thực đường dẫn và đăng nhập rễ merkle. Sau đó, nhà sản xuất khối sẽ tích lũy chữ ký BLS trên gốc merkle từ validators và chỉ xuất bản gốc merkle và chữ ký tích lũy Nhà sản xuất khối cũng ký vào tính hợp lệ của đa chữ ký bằng cách sử dụng chữ ký ECDSA giá rẻ. Nếu đa chữ ký không khớp với gốc merkle được gửi hoặc bitmask của validator tham gia, đó là hành vi có thể cắt được. Khi đồng bộ hóa chuỗi, người tham gia có thể chọn xác thực tất cả chữ ký BLS từ các validator (việc này cực kỳ tốn kém vì nó liên quan đến việc tổng hợp các khóa công khai của validator) hoặc chỉchữ ký ECDMA từ các nhà sản xuất khối và dựa vào thực tế là nhà sản xuất khối không bị thách thức và bị chém. Sử dụng các giao dịch trên chuỗi và bằng chứng merkle để giải quyết các thách thức. Nó có thể lưu ý rằng việc tiết lộ tin nhắn từ validator sẽ không có giá trị gì nếu không chuyển đổi trạng thái không hợp lệ đã được phát hiện. Chỉ những tin nhắn có chứa thông tin thực tế bằng chứng về việc chuyển đổi trạng thái không hợp lệ cần phải được tiết lộ và chỉ dành cho những tin nhắn như vậy nó cần phải được chứng minh rằng chúng phù hợp với cam kết trước đó. Thông điệp cần phải được tiết lộ nhằm hai mục đích: 1. Để thực sự bắt đầu quá trình khôi phục chuỗi về thời điểm trước khi thực hiện chuyển trạng thái không hợp lệ (xem phần 3.7.5). 2. Để chứng minh rằng validator không cố gắng chứng thực tính hợp lệ của đoạn không hợp lệ. Trong cả hai trường hợp, chúng ta cần giải quyết hai vấn đề: 1. Cam kết thực tế không được đưa vào chuỗi, chỉ có gốc merkle của cam kết tổng hợp với các tin nhắn khác. validator cần sử dụng đường dẫn merkle do nhà sản xuất khối cung cấp và cam kết ban đầu của họ đối với chứng minh rằng họ đã cam kết với thử thách. 2. Có thể tất cả validator được gán cho phân đoạn có giá trị không hợp lệ quá trình chuyển đổi trạng thái xảy ra được gán cho các nhà sản xuất khối bị hỏng đang kiểm duyệt chúng. Để giải quyết vấn đề này, chúng tôi cho phép họ gửi tiết lộ của mình như một giao dịch thông thường trên chuỗi và bỏ qua việc tổng hợp. Cái sau chỉ được phép đối với các bằng chứng về sự chuyển đổi trạng thái không hợp lệ, đó là cực kỳ hiếm và do đó sẽ không dẫn đến việc gửi thư rác vào các khối. Vấn đề cuối cùng cần được giải quyết là các nhà sản xuất khối có thể chọn không tham gia vào việc tổng hợp tin nhắn hoặc cố tình kiểm duyệt validators cụ thể. Chúng tôi làm cho nó trở nên bất lợi về mặt kinh tế bằng cách tạo ra khối phần thưởng của nhà sản xuất tỷ lệ thuận với số validator được chỉ định cho họ. Chúng tôi cũng lưu ý rằng vì các nhà sản xuất khối giữa các kỷ nguyên phần lớn giao nhau (vì luôn là những người tham gia có số tiền đặt cược cao nhất), validator có thể phần lớn tập trung vào làm việc với cùng một nhà sản xuất khối và do đó giảm thiểu rủi ro về việc được giao cho một nhà sản xuất khối đã kiểm duyệt chúng trong quá khứ. 3,9 Chuỗi ảnh chụp nhanh Vì các khối trên chuỗi chính được sản xuất rất thường xuyên nên việc tải xuống toàn bộ lịch sử có thể trở nên đắt đỏ rất nhanh. Hơn nữa, vì mỗi khối chứa chữ ký BLS của một số lượng lớn người tham gia, chỉ cần tổng hợp các khóa công khai để kiểm tra chữ ký có thể trở nên quá khó khăn. đắt tiền là tốt. Cuối cùng, vì trong bất kỳ tương lai gần nào Ethereum 1.0 có thể sẽ vẫn là một trong số blockchain được sử dụng nhiều nhất, có một cách hiệu quả để chuyển nội dung từ
Gần Ethereum là một yêu cầu và hôm nay việc xác minh chữ ký BLS để đảm bảo Không thể có hiệu lực ở các khối gần về phía Ethereum. Mỗi khối trong chuỗi chính Nightshade có thể tùy ý chứa Schnorr đa chữ ký trên tiêu đề của khối cuối cùng bao gồm Schnorr đa chữ ký. Chúng tôi gọi những khối như vậy là khối chụp nhanh. Khối đầu tiên của mỗi kỷ nguyên phải là một khối ảnh chụp nhanh. Trong khi làm việc trên một hệ thống đa chữ ký như vậy, nhà sản xuất khối cũng phải tích lũy chữ ký BLS của validators trên khối ảnh chụp nhanh cuối cùng và tổng hợp chúng theo cách tương tự như được mô tả trong phần 3.8. Vì bộ sản xuất khối không đổi trong suốt kỷ nguyên, nên việc xác thực chỉ các khối ảnh chụp nhanh đầu tiên trong mỗi kỷ nguyên là đủ với giả định rằng không có chỉ ra một tỷ lệ lớn các nhà sản xuất khối và validator đã thông đồng và tạo ra một cái nĩa. Khối đầu tiên của kỷ nguyên phải chứa thông tin đủ để tính toán nhà sản xuất khối và validator cho kỷ nguyên. Chúng tôi gọi chuỗi con của chuỗi chính chỉ chứa ảnh chụp nhanh chặn một chuỗi ảnh chụp nhanh. Tạo đa chữ ký Schnorr là một quá trình tương tác, nhưng vì chúng ta chỉ cần thực hiện nó không thường xuyên, bất kỳ quy trình nào, dù kém hiệu quả đến đâu sẽ đủ. Có thể dễ dàng xác thực đa chữ ký Schnorr trên Ethereum, do đó cung cấp các nguyên hàm quan trọng để thực hiện một cách an toàn chéo-blockchain giao tiếp. Để đồng bộ với chuỗi Gần, người ta chỉ cần tải xuống tất cả ảnh chụp nhanh chặn và xác nhận rằng chữ ký Schnorr là chính xác (tùy chọn cũng xác minh chữ ký BLS riêng lẻ của validators), sau đó chỉ đồng bộ hóa khối chuỗi chính từ khối ảnh chụp nhanh cuối cùng.
Conclusion
Conclusion
In this document we discussed approaches to building sharded blockchains and covered two major challenges with existing approaches, namely state validity and data availability. We then presented Nightshade, a sharding design that powers NEAR Protocol. The design is work in progress, if you have comments, questions or feedback on this document, please go to https://near.chat.
Phần kết luận
Trong tài liệu này, chúng tôi đã thảo luận các phương pháp tiếp cận để xây dựng blockchain phân đoạn và đã giải quyết được hai thách thức lớn với các phương pháp tiếp cận hiện có, đó là tính hợp lệ của trạng thái và tính sẵn có của dữ liệu. Sau đó chúng tôi đã giới thiệu Nightshade, một thiết kế sharding quyền hạn NEAR Giao thức. Thiết kế đang được tiến hành, nếu bạn có ý kiến, câu hỏi hoặc phản hồi trên tài liệu này, vui lòng truy cập https://near.chat.