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.
Durum Geçerliliği ve Veri Kullanılabilirliği
Parçalanmış blockchain'lerdeki temel fikir, çoğu katılımcının işletim veya ağı kullanmak tüm parçalardaki blokları doğrulayamaz. Bu nedenle, ne zaman olursa olsun herhangi bir katılımcının genellikle yapamadığı belirli bir parçayla etkileşime girmesi gerekir Parçanın tüm geçmişini indirin ve doğrulayın. Bununla birlikte, parçalamanın bölümleme yönü önemli bir potansiyel ortaya çıkarmaktadır. sorun: belirli bir uygulamanın tüm geçmişini indirmeden ve doğrulamadan katılımcının parçanın bulunduğu durumdan mutlaka emin olması mümkün değildir. 5Bu bölüm, alt bölüm 2.5.3 hariç, daha önce https://near.ai/ adresinde yayınlanmıştır. parça2. Daha önce okuduysanız bir sonraki bölüme geçin.
etkileşime girmeleri bazı geçerli blok dizilerinin sonucudur ve bu dizi Blok sayısı gerçekten de parçadaki kanonik zincirdir. Çözülmeyen bir sorun parçalanmamış bir blockchain içinde mevcut. Öncelikle bu soruna önerilen basit bir çözüm sunacağız. birçok protokole göre analiz edin ve ardından bu çözümün nasıl bozulabileceğini ve ne olacağını analiz edin. giderilmesine yönelik girişimlerde bulunuldu. 2.1 Doğrulayıcıların rotasyonu Durum geçerliliğine yönelik saf çözüm şekil 5'te gösterilmektedir: diyelim ki tüm sistemde binlerce validators var, bunlardan %20'den fazlası kötü niyetli değildir veya başka şekilde başarısız olacaktır (örneğin, Bir blok oluşturmak için çevrimiçi). O zaman 200 validators örnek alırsak olasılık 1'den fazla 3 pratik amaçlar açısından başarısızlığın sıfır olduğu varsayılabilir. Şekil 5: Örnekleme validators 1 3 önemli bir eşik. Bir mutabakat protokolü ailesi var. BFT fikir birliği protokolleri; bu, 1'den az olduğu sürece bunu garanti eder 3'ü Katılımcılar ya kaza yaparak ya da kuralları ihlal eden bir şekilde hareket ederek başarısız olurlar. Protokolde fikir birliğine varılacak. Bu dürüst validator yüzdelik varsayımla, eğer mevcut Saf çözüm, bir parçadaki validators'nin bize bir miktar blok sağladığını varsayar bloğun geçerli olduğunu ve validators olduğuna inanılanlar üzerine inşa edildiğini doğrulamaya başladıklarında söz konusu parçanın standart zinciri. validator'lar kanonik zinciri önceki validators kümesinden öğrendi; Kanonik zincirin başı olan bloğun üzerine inşa edilen varsayım ondan önce. Tümevarımla zincirin tamamı geçerlidir ve validators kümesi olmadığından Çatal üretilen herhangi bir noktada, naif çözüm aynı zamanda mevcut olanın da kesin olduğudur. zincir, parçadaki tek zincirdir. Görselleştirme için şekil 6'ya bakın.
Şekil 6: Her bloğun BFT fikir birliğiyle sonlandırıldığı bir blockchain validators'nin olabileceğini varsayarsak bu basit çözüm işe yaramaz. uyumsal olarak bozulmuştur ki bu mantıksız bir varsayım değildir6. Uyarlanabilir 1000 parçadan oluşan bir sistemde tek bir parçayı bozmak çok daha ucuzdur tüm sistemi bozmak yerine. Bu nedenle protokolün güvenliği, parça sayısı arttıkça doğrusal olarak azalır. Geçerliliğinden emin olmak için bir blok, tarihin herhangi bir noktasında sistemdeki hiçbir parçanın olmadığını bilmeliyiz. validator'ların çoğunluğu gizli anlaşma yapıyor; uyarlanabilir düşmanlarla artık elimizde değil öyle bir kesinlik ki. Bölüm 1.5'te tartıştığımız gibi, validators ile gizli anlaşma yapmak işe yarayabilir iki temel kötü niyetli davranış: çatallar oluşturmak ve geçersiz bloklar üretmek. Kötü niyetli çatallanmalar, blokların genel olarak diğerlerine göre önemli ölçüde daha yüksek güvenliğe sahip olacak şekilde tasarlanan Beacon zincirine çapraz bağlanmasıyla ele alınabilir. kırık zincirler. Geçersiz bloklar üretmek ise önemli ölçüde daha fazla bir sorundur. üstesinden gelinmesi zor bir sorun. 2.2 Durum Geçerliliği 1. Parçanın bozulduğu ve kötü niyetli bir aktörün ürettiği Şekil 7'yi düşünün. geçersiz blok B. Diyelim ki bu B bloğunda 1000 tokens yoktan basıldı Alice'in hesabında yayın. Kötü niyetli aktör daha sonra geçerli C bloğunu üretir (bir C'deki işlemlerin doğru bir şekilde uygulandığını hissetmek) B'nin yanı sıra kafa karıştırıcı geçersiz B bloğunu kullanır ve Parça #2'ye bir çapraz parça işlemi başlatır. bu 1000 tokens'yi Bob'un hesabına aktarır. Bu andan itibaren uygunsuz bir şekilde oluşturulan token'ler, Parça #2'deki tamamen geçerli bir blockchain üzerinde bulunuyor. Bu sorunu çözmeye yönelik bazı basit yaklaşımlar şunlardır: 6Oku bu makale için ayrıntılar üzerinde nasıl uyarlanabilir yolsuzluk yapabilir olmak taşınan dışarı: https://medium.com/nearprotocol/d859adb464c8. için daha fazla ayrıntılar üzerinde uyarlanabilir yolsuzluk, okumak https://github.com/ethereum/wiki/wiki/Sharding-FAQ# altında-çalıştığımız-güvenlik modelleri nelerdirŞekil 7: Geçersiz bloğu olan bir zincirden gelen parçalar arası işlem 1. İşlemin yapıldığı bloğu doğrulamak amacıyla validators Parça #2 için başlatılır. Bu yukarıdaki örnekte bile işe yaramayacaktır çünkü C bloğu tamamen geçerli olduğu görülmektedir. 2. İşlemin başlatıldığı bloktan önceki çok sayıda bloğu doğrulamak için Parça #2'deki validators için. Doğal olarak, kötü niyetli alıcı parça tarafından doğrulanan herhangi bir sayıda blok N validators, geçersiz bloğun üstünde N+1 geçerli blok oluşturabilir üretildi. Bu sorunu çözmek için umut verici bir fikir, parçaları bir düzende düzenlemek olacaktır. her bir parçanın diğer birkaç parçaya bağlandığı yönlendirilmemiş grafik ve yalnızca komşu parçalar arasında çapraz parça işlemlerine izin ver (ör. Vlad Zamfir'in parçalaması esasen işe yarıyor7 ve benzer fikir Kadena'nınkinde de kullanılıyor Chainweb [1]). Parçalar arasında parçalar arası bir işlem gerekiyorsa komşular değil, bu tür işlemler birden fazla parça aracılığıyla yönlendirilir. Bu tasarımda Her bir parçadaki bir validator'nin, kendi parçalarındaki tüm blokları doğrulaması bekleniyor ve ayrıca tüm komşu parçalardaki tüm bloklar. Aşağıdaki şekli düşünün 10 parçadan oluşan, her birinin dört komşusu olan ve daha fazlasını gerektiren iki parçanın olmadığı Şekil 8'de gösterilen çapraz parça iletişimi için ikiden fazla atlama. Parça #2 yalnızca kendi blockchain parçasını değil aynı zamanda blockchain parçasını da doğruluyor 1 numaralı Parça dahil tüm komşular. Yani Parça #1'de kötü niyetli bir aktör varsa geçersiz bir B bloğu oluşturmaya çalışıyor, ardından bunun üzerine C bloğunu inşa ediyor ve parçalar arası bir işlem başlatın, bu tür parçalar arası işlem gerçekleşmeyecek Parça #2'den beri Parça #1'in tüm geçmişi doğrulanmış olacak. geçersiz B bloğunu tanımlamasına neden olacaktır. 7Tasarım hakkında daha fazla bilgiyi burada bulabilirsiniz: https://medium.com/nearprotocol/37e538177ed9
Şekil 8: Chainweb benzeri sistemde geçersiz bir çapraz parça işlemi tespit edilmek Tek bir parçayı bozmak artık geçerli bir saldırı olmasa da, bir parçayı bozmak artık geçerli bir saldırı değildir. birkaç parça sorun olmaya devam ediyor. Şekil 9'da bir düşman her iki Shard'ı da bozuyor
1 ve Parça #2, Parça #3'e yönelik bir çapraz parça işlemini başarıyla yürütür
geçersiz bir B bloğundan gelen fonlarla: Şekil 9: Chainweb benzeri sistemde geçersiz bir çapraz parça işlemi tespit edilmemek Parça #3, Parça #2'deki tüm blokları doğrular ancak Parça #1'deki tüm blokları doğrular ve kötü amaçlı bloğu tespit etmenin bir yolu yoktur. Durum geçerliliğini doğru şekilde çözmenin iki ana yönü vardır: balıkçılar
ve hesaplamanın kriptografik kanıtları. 2.3 Balıkçı İlk yaklaşımın arkasındaki fikir şudur: ne zaman bir blok başlığı Herhangi bir amaç için zincirler arasında iletilir (örneğin çapraz bağlanma gibi). işaret zinciri veya parçalar arası bir işlem), bu sırada belirli bir süre vardır dürüst herhangi bir validator bloğun geçersiz olduğuna dair kanıt sağlayabilir. Orada blokların çok kısa ve öz kanıtlarını sağlayan çeşitli yapılardır. geçersiz olduğundan alıcı düğümlerin iletişim yükü çok daha küçüktür tam bir blok almaktan daha fazla. En az bir dürüst validator olduğu sürece bu yaklaşımla Shard, sistem güvenlidir. Şekil 10: Balıkçı Bu, bugün önerilen protokoller arasında (sorun yokmuş gibi davranmanın yanı sıra) baskın yaklaşımdır. Ancak bu yaklaşımın iki önemli dezavantajlar: 1. Dürüst validator için meydan okuma süresinin yeterince uzun olması gerekir Bir bloğun üretildiğini tanımak, onu indirmek, tamamen doğrulamak ve hazırlamak blok geçersizse meydan okuma. Böyle bir dönemin getirilmesi Parçalar arası işlemleri önemli ölçüde yavaşlatır. 2. Challenge protokolünün varlığı yeni bir saldırı vektörü yaratıyor Kötü niyetli düğümler geçersiz sorgulamalarla spam yaptığında. Açık bir çözüm Bu sorunun çözümü, meydan okuyanların bir miktar tokens yatırmasını sağlamaktır. meydan okuma geçerliyse iade edilir. Bu yalnızca kısmi bir çözümdür, çünkü saldırganın sisteme spam göndermesi (ve yakması) yine de faydalı olabilir. örneğin geçerli işlemleri engellemek için geçersiz sorgulamalarla yapılan para yatırma işlemleri)dürüst bir validator'dan gelen meydan okuma. Bu saldırılar Kederli Saldırılar denir. İkinci noktayı aşmanın bir yolu için bölüm 3.7.2'ye bakın. 2.4 Kısa ve Etkileşimli Olmayan Bilgi Argümanları Çoklu parça bozulmasına karşı ikinci çözüm, belirli bir hesaplamanın (örneğin, bir dizi işlemden bir bloğun hesaplanması gibi) doğru bir şekilde gerçekleştirildi. Bu tür yapılar mevcuttur; zk-SNARK'lar, zk-STARK'lar ve birkaç kişi daha, ve bazıları bugün blockchain protokollerinde özel ödemeler için aktif olarak kullanılıyor, en önemlisi ZCash. Bu tür ilkellerle ilgili temel sorun, onların hesaplamanın oldukça yavaş olduğu biliniyor. Örn. zk-SNARK'ları kullanan Coda Protokolü özellikle blockchain içindeki tüm blokların geçerli olduğunu kanıtlamak için, birinde söylendi Kanıt oluşturmanın işlem başına 30 saniye sürebileceği görüşmelerden (bu sayı muhtemelen şimdiye kadar daha küçüktür). İlginç bir şekilde, bir kanıtın güvenilir bir tarafça hesaplanmasına gerek yoktur, çünkü Kanıt yalnızca oluşturulduğu hesaplamanın geçerliliğini kanıtlamakla kalmaz, aynı zamanda kanıtın kendisinin geçerliliği. Dolayısıyla bu tür kanıtların hesaplanması bölünebilir önemli ölçüde daha az yedekliliğe sahip bir grup katılımcı arasında bazı güvenilir hesaplamalar yapmak için gereklidir. Aynı zamanda katılımcıların zk-SNARK'ları özel donanım üzerinde çalışacak şekilde hesaplayanlar sistemin ademi merkeziyetçiliği. zk-SNARK'ların performansın yanı sıra karşılaştığı zorluklar şunlardır: 1. Daha az araştırılmış ve daha az zaman içinde test edilmiş kriptografik temellere bağımlılık; 2. “Zehirli atık” — zk-SNARK'lar, bir grubun içinde bulunduğu güvenilir bir kuruluma bağlıdır İnsanların oranı bir miktar hesaplama yapıyor ve ardından ara hesaplamayı atıyor bu hesaplamanın değerleri. Prosedürün tüm katılımcıları gizli anlaşma yaparsa ve ara değerleri koruyarak sahte deliller oluşturulabilir; 3. Sistem tasarımına eklenen ekstra karmaşıklık; 4. zk-SNARK'lar yalnızca olası hesaplamaların bir alt kümesi için çalışır, dolayısıyla bir protokol Turing-complete smart contract dilini kullanamazsınız Zincirin geçerliliğini kanıtlamak için SNARK'lar. 2.5 Veri Kullanılabilirliği Değineceğimiz ikinci sorun veri kullanılabilirliğidir. Genellikle düğümler belirli bir blockchain çalıştıran iki gruba ayrılır: Tam Düğümler, her tam bloğu indiren ve her işlemi doğrulayanlar ve Light Yalnızca blok başlıklarını indiren ve parçalar için Merkle kanıtlarını kullanan düğümler Şekil 11'de gösterildiği gibi ilgilendikleri durum ve işlemler.
Şekil 11: Merkle Ağacı Artık tam düğümlerin çoğunluğu gizli anlaşma yaparsa geçerli veya geçerli bir blok üretebilirler. geçersizdir ve hash dosyasını hafif düğümlere gönderin, ancak içeriğin tamamını hiçbir zaman açıklamayın bloğun. Bundan faydalanabilecekleri çeşitli yollar vardır. Örneğin, Şekil 12'yi düşünün: Şekil 12: Veri Kullanılabilirliği sorunu Üç blok vardır: önceki A, dürüst validators tarafından üretilmiştir; mevcut B'nin validators gizli anlaşması var; ve bir sonraki C de üretilecek dürüst validators tarafından (blockchain sağ alt köşede gösterilmektedir). Sen bir tüccarsın. Geçerli bloğun (B) validator'leri alınan blok Önceki validator'lerden A, içinde para aldığınız bir blok hesapladı,ve size o bloğun başlığını, içinde bulunulan durumun Merkle kanıtıyla birlikte gönderdim. paranız var (veya parayı gönderen geçerli bir işlemin Merkle kanıtı) sana). İşlemin tamamlandığından emin olduğunuzda hizmeti sağlarsınız. Ancak validator'ler hiçbir zaman B bloğunun tam içeriğini dağıtmaz. herhangi biri. Bu nedenle, C bloğunun dürüst validator'leri bloğu geri alamaz ve ya sistemi durdurmaya zorlanırlar ya da A'nın üzerine inşa ederek sizi bir sistem olarak mahrum bırakırlar. para tüccarı. Aynı senaryoyu parçalamaya uyguladığımızda tam ve hafif düğüm genellikle parça başına uygulanır: her parça indirmesinde validators o parçada bloke edin ve o parçadaki her işlemi doğrulayın, ancak diğer parça zincirlerinin anlık görüntüsünü alan düğümler de dahil olmak üzere sistemdeki düğümler işaret zinciri, yalnızca başlıkları indirin. Böylece parçadaki validator'ler sistemdeki diğer katılımcılar bu parça için etkili bir şekilde tam düğümler oluştururken, işaret zinciri de dahil olmak üzere ışık düğümleri olarak çalışır. Yukarıda tartıştığımız balıkçı yaklaşımının işe yaraması için dürüst validators işaret zincirine çapraz bağlı blokları indirebilmeniz gerekir. Kötü niyetli validator'ler geçersiz bir bloğun başlığını çapraz bağladıysa (veya bunu kullandıysa) parçalar arası bir işlem başlatır), ancak bloğu asla dağıtmaz, dürüst validator'lerin bir meydan okuma oluşturmanın hiçbir yolu yok. Bu sorunu çözmek için birbirini tamamlayan üç yaklaşımı ele alacağız. Birbirimiz. 2.5.1 Velayet Kanıtları Çözülmesi gereken en acil sorun, bir bloğun bir kez kullanılabilir olup olmadığıdır. yayınlandı. Önerilen fikirlerden biri dönüşümlü Noterlere sahip olmaktır. tek işi bir dosya indirmek olan validator'lerden daha sık parçalar arasında engelleyin ve indirebildiklerini doğrulayın. Onlar olabilir tüm durumu indirmeleri gerekmediği için daha sık dönüşümlü olarak kullanılıyor parçanın aksine, sık sık döndürülemeyen validator'lerin aksine şekilde gösterildiği gibi her döndüklerinde parçanın durumunu indirmeleri gerekir 13. Bu naif yaklaşımın sorunu daha sonra kanıtlamanın imkansız olmasıdır. Noterin bloğu indirip indiremediğine bağlı olarak Noter bloğu indirebildiklerini her zaman onaylamayı seçebilirler. hatta onu geri almaya çalışıyorum. Bunun bir çözümü Noterlerin sağlamasıdır. bloğun olduğunu kanıtlayan bazı kanıtlar veya bir miktar tokens stake etmek indirildi. Böyle bir çözüm burada tartışılmaktadır: https://ethresear.ch/t/ 1 bitlik toplama dostu saklama tahvilleri/2236. 2.5.2 Silme Kodları Belirli bir ışık düğümü bir bloğun hash değerini aldığında, düğümün Bloğun mevcut olduğundan emin olmak için rastgele birkaç tane indirmeyi deneyebilir bloğun parçaları. Bu tam bir çözüm değil çünkü ışık düğümleri Kötü niyetli blok üreticilerinin seçebileceği bloğun tamamını toplu olarak indirin
Şekil 13: Doğrulayıcıların durumu indirmesi gerekir ve bu nedenle döndürülemez sık sık bloğun herhangi bir ışık düğümü tarafından indirilmeyen kısımlarını alıkoymak, böylece bloğu hala kullanılamaz hale getiriyoruz. Çözümlerden biri, bunu mümkün kılmak için Silme Kodları adı verilen bir yapıyı kullanmaktır. gösterildiği gibi bloğun yalnızca bir kısmı mevcut olsa bile tüm bloğu kurtarmak için Şekil 14'te. Şekil 14: Merkle tree silme kodlu veriler üzerine inşa edilmiştir Hem Polkadot hem de Ethereum Serenity'nin tasarımları bu fikir etrafında şekilleniyor: Hafif düğümlerin blokların mevcut olduğundan makul ölçüde emin olmaları için bir yol sağlar. Ethereum Serenity yaklaşımının ayrıntılı açıklaması [2]'da bulunmaktadır.2.5.3 Polkadot'nin veri kullanılabilirliğine yaklaşımı Polkadot'de, çoğu parçalı çözümde olduğu gibi, her parça (parachain olarak adlandırılır) bloklarının anlık görüntüsünü işaret zincirine (aktarma zinciri olarak adlandırılır) alır. Diyelim ki 2f + 1 var Aktarma zincirinde validators. Parachain bloklarının blok üreticileri, harmanlayıcılar, parachain bloğu üretildiğinde, herhangi bir f parçası yeterli olacak şekilde 2f +1 parçadan oluşan bloğun silme kodlu versiyonunu hesaplarlar. bloğu yeniden inşa etmek için. Daha sonra her validator'e bir parça dağıtırlar. röle zinciri. Belirli bir geçiş zinciri validator yalnızca bir geçiş zincirinde imza atar anlık görüntüsü alınan her parachain bloğu için kendi paylarına sahiplerse bloklayın böyle bir röle zinciri bloğu. Dolayısıyla, eğer bir aktarma zinciri bloğu 2f + 1'den imzalara sahipse validators ve bunlardan en fazla f tanesi protokolü ihlal etmediği sürece, her biri parachain bloğu validators'den parçalar alınarak yeniden oluşturulabilir protokolü takip edenler. Bkz. şekil 15. Şekil 15: Polkadot'nin veri kullanılabilirliği 2.5.4 Uzun vadeli veri kullanılabilirliği Yukarıda tartışılan tüm yaklaşımların yalnızca bir bloğun olduğu gerçeğini doğruladığını unutmayın. yayınlandı ve şu anda mevcut. Bloklar daha sonra kullanılamayabilir çeşitli nedenlerden dolayı: düğümlerin devre dışı kalması, düğümlerin kasıtlı olarak geçmişi silmesi veriler ve diğerleri. Bu sorunu ele alan bahsetmeye değer bir teknik inceleme Polyshard [3]'dir, birden fazla parça olsa bile blokların parçalar arasında kullanılabilir olmasını sağlamak için silme kodlarını kullanan Parçalar verilerini tamamen kaybeder. Ne yazık ki onların özel yaklaşımı şunu gerektirir: diğer tüm parçalardan blok indirmek için tüm parçalar, bu da yasaklayıcı bir şekilde pahalı. Uzun vadeli kullanılabilirlik o kadar acil bir sorun değil: hiçbir katılımcı olmadığı için Sistemin tüm zincirlerdeki tüm zincirleri doğrulayabilmesi bekleniyor.
Parçalanmış protokollerin güvenliğinin böyle bir şekilde tasarlanması gerekir. bazı parçalardaki bazı eski bloklar bozulsa bile sistemin güvenli kalmasının bir yolu tamamen kullanılamaz.
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 Parça zincirlerinden parça parçalara Parça zincirleri ve işaret zinciri içeren parçalama modeli çok güçlüdür ancak belirli karmaşıklıklara sahiptir. Özellikle çatal seçim kuralının uygulanması gerekiyor her zincirde ayrı ayrı, parça zincirlerinde ve işaretçide çatal seçim kuralı Zincir farklı şekilde oluşturulmalı ve ayrı olarak test edilmelidir. Nightshade'de sistemi tek bir blockchain olarak modelliyoruz; her biri blok mantıksal olarak tüm parçalar için tüm işlemleri içerir ve tüm parçaların tüm durumu. Ancak fiziksel olarak hiçbir katılımcı dosyayı indirmez. tam durum veya tam mantıksal blok. Bunun yerine, ağın her katılımcısı yalnızca İşlemleri doğruladıkları parçalara karşılık gelen durumu korur ve bloktaki tüm işlemlerin listesi fiziksel olarak bölünmüştür parçalar, parça başına bir parça. İdeal koşullar altında her blok, parça başına tam olarak bir parça içerir. kabaca parça zincirli modele karşılık gelen blok parça zincirleri işaret zinciriyle aynı hızda bloklar üretir. Ancak, ağ gecikmeleri nedeniyle bazı parçalar eksik olabilir; bu nedenle pratikte her blok parça başına bir veya sıfır parça içerir. Nasıl yapılacağına ilişkin ayrıntılar için bölüm 3.3'e bakın. bloklar üretilir. Şekil 16: Solda parça zincirleri ve tek zinciri olan bir model bloklar sağ tarafta parçalara bölünmüş
3.2 Konsensüs Bugün blockchain'lerde fikir birliğine yönelik iki baskın yaklaşım şunlardır: En fazla işe veya hisseye sahip olan zincirin en uzun (veya en ağır) zincir oluşturmak için kullanılan kurallı kabul edilir ve BFT, burada her blok için bazı validator kümesi BFT fikir birliğine ulaştı. Son zamanlarda önerilen protokollerde ikincisi daha baskın bir yaklaşımdır, anında kesinlik sağladığından, en uzun zincirde daha fazla bloğa ihtiyaç duyulurken Kesinliği sağlamak için bloğun üzerine inşa edilecek. Çoğu zaman anlamlı Yeterli sayıda bloğun inşa edilmesi için gereken süre güvenlik gerektirir. saat sırası. Her blokta BFT fikir birliğini kullanmanın aşağıdaki gibi dezavantajları da vardır: 1. BFT fikir birliği önemli miktarda iletişim gerektirir. iken Son gelişmeler sayıca doğrusal zamanda fikir birliğine varılmasına olanak tanıyor katılımcıların sayısı (bkz. örneğin [4]), blok başına hala fark edilebilir bir yüktür; 2. Tüm ağ katılımcılarının BFT'ya katılması mümkün değildir. Blok başına fikir birliğine varılır, dolayısıyla genellikle yalnızca rastgele örneklenmiş bir katılımcı alt kümesi fikir birliğine varır. Rastgele örneklenmiş bir küme prensip olarak şu şekilde olabilir: uyarlanabilir bir şekilde bozulur ve teoride bir çatal oluşturulabilir. sistem her ikisinin de böyle bir olaya hazır olmak için modellenmesi gerekiyor ve bu nedenle hala BFT fikir birliğinin yanı sıra bir çatal seçeneği kuralına sahip olmak veya kapanacak şekilde tasarlanmış olmak böyle bir olayda aşağı. Bazı tasarımların olduğunu belirtmekte fayda var. Algorand [5], uyarlamalı yolsuzluk olasılığını önemli ölçüde azaltır. 3. En önemlisi şu durumlarda sistem durur: Tüm katılımcıların 3 veya daha fazlası çevrimdışı. Bu nedenle, herhangi bir geçici ağ arızası veya ağ bölünmesi, sistemi tamamen durdurabilir. İdeal olarak sistem devam edebilmelidir katılımcıların en az yarısı çevrimiçi olduğu sürece faaliyet göstermektedir (en yoğun Zincir tabanlı protokoller, katılımcıların yarısından azı çevrimiçi olsa bile çalışmaya devam eder, ancak bu özelliğin arzu edilirliği daha tartışmalıdır topluluk içinde). Kullanılan fikir birliğinin bir tür en ağır olduğu hibrit bir model zincir, ancak bazı bloklar BFT sonlandırma aracı kullanılarak periyodik olarak sonlandırılır ve her iki modelin de avantajları korunur. Bu tür BFT nihai gadget'lar Ethereum 2.0 8'de kullanılan Casper FFG [6], Casper CBC (bkz. https://vitalik.) ca/general/2018/12/05/cbc_casper.html) ve GRANDPA (bkz. https:// Medium.com/polkadot-network/d08a24a021b5) Polkadot'de kullanıldı. Nightshade en ağır zincir konsensüsünü kullanır. Özellikle bir blok Üretici bir blok ürettiğinde (bkz. Bölüm 3.3), imza toplayabilirler. diğer blok üreticileri ve önceki bloğu doğrulayan validator'lar. Bölüme bakın Bu kadar çok sayıda imzanın nasıl toplandığıyla ilgili ayrıntılar için 3.8'e bakınız. Ağırlık 8Ayrıca Casper'a derinlemesine bir genel bakış için Justin Drake ile yapılan beyaz tahta oturumuna bakın FFG ve GHOST en ağır zincir konsensüsüne nasıl entegre edildiği burada: https://www. youtube.com/watch?v=S262StTwkmobir bloğun payı, imzaları imzalanan tüm imzalayanların kümülatif hissesidir. bloğa dahil edilmiştir. Bir zincirin ağırlığı blok ağırlıklarının toplamıdır. En ağır zincir mutabakatının yanı sıra, aşağıdakileri kullanan bir nihai gadget kullanıyoruz: blokları sonlandırmak için onaylar. Sistemin karmaşıklığını azaltmak için, Çatal seçim kuralını hiçbir şekilde etkilemeyen bir sonlandırma aracı kullanıyoruz, ve bunun yerine yalnızca ekstra eğik çizgi koşulları getirir, öyle ki bir blok bir kez Nihai gadget tarafından sonlandırıldığında, çok büyük bir yüzde olmadıkça çatallanma imkansızdır. toplam bahis miktarı kesildi. Casper CBC son derece kaliteli bir cihazdır ve biz şu anda Casper CBC'yi göz önünde bulundurarak model oluşturuyorum. Ayrıca TxFlow adı verilen ayrı bir BFT protokolü üzerinde de çalışıyoruz. O sırada Bu belgeyi yazarken Casper yerine TxFlow'un kullanılıp kullanılmayacağı belli değil CBC. Ancak son cihaz seçiminin büyük ölçüde tasarımın geri kalanına dik olduğunu belirtmeliyiz. 3.3 Blok üretimi Nightshade'de iki rol vardır: blok yapımcıları ve validator'ler. herhangi bir zamanda sistemin w blok üreticilerini içerdiği nokta, modellerimizde w = 100 ve wv validators, modelimizde v = 100, wv = 10, 000. Sistem Proof-of-Stake'tir, bu, hem blok üreticilerinin hem de validator'lerin bir takım dahili bağlantılara sahip olduğu anlamına gelir para birimi ("tokens" olarak anılır) belirtilen süreyi aşan bir süre boyunca kilitlendi zinciri oluşturma ve doğrulama görevlerini yerine getirmek için harcadıkları zaman. Tüm Proof of Stake sistemlerinde olduğu gibi, tüm w blok üreticileri ve tüm wv validator'ler farklı varlıklardır, çünkü bu uygulanamaz. Her biri Bununla birlikte, w blok üreticilerinin ve wv validator'lerin ayrı bir hisse. Sistem n parça içeriyor, modelimizde n = 1000. Bahsedildiği gibi bölüm 3.1, Nightshade'de hiçbir parça zinciri yoktur, bunun yerine tüm blok üreticileri ve validator'ler tek bir blockchain inşa ediyor, biz bunu ana zincir. Ana zincirin durumu n parçaya bölünmüştür ve her blok yapımcı ve validator her an yerel olarak yalnızca bir alt kümesini indirdi bazı parçaların alt kümesine karşılık gelen ve yalnızca işlem ve Eyaletin bu kısımlarını etkileyen işlemleri doğrulamak. Bir blok üreticisi olmak için ağın bir katılımcısı bazı büyükleri kilitler tokens miktarı (bir hisse). Ağın bakımı dönemler halinde yapılır, burada bir dönem gün sırasına göre bir zaman dilimidir. Katılımcılar Belirli bir çağın başında en büyük riske sahip olan bloklar O dönemin yapımcıları. Her blok üreticisi yazılım parçalarına atanır (örneğin sw = 40, bu da sww/n = parça başına 4 blok üreticisi anlamına gelir). Blok yapımcı, atandığı parçanın çağdan önceki durumunu indirir başlar ve dönem boyunca söz konusu parçayı etkileyen işlemleri toplar, ve bunları devlete uygular. Ana zincirdeki her b bloğu ve her parça s için aşağıdakilerden biri vardır: blok üreticilerini b ile ilgili kısmı üretmekten sorumlu olanlara atadık parçaya. b'nin parçayla ilgili kısmına yığın denir ve şunları içerir: merkle'nin yanı sıra b'ye dahil edilecek parçaya ilişkin işlemlerin listesiortaya çıkan durumun kökü. b sonuçta yalnızca çok küçük bir başlık içerecektir parça, yani uygulanan tüm işlemlerin merkle kökü (bkz. bölüm Kesin ayrıntılar için 3.7.1) ve son durumun merkle kökü. Belgenin geri kalanında sıklıkla blok üreticisinden bahsediyoruz belirli bir parça için belirli bir zamanda bir parça üretmekten sorumlu olan bir parça üreticisi olarak. Parça üreticisi her zaman blok üreticilerinden biridir. Blok üreticileri ve parça üreticileri her bloğu ona göre döndürür. sabit bir programa göre. Blok üreticilerinin siparişi var ve tekrar tekrar üretim yapıyorlar. bu sırayla bloklar. Örn. 100 blok üreticisi varsa ilk blok üreticiler 1, 101, 201 vb. blokların üretiminden sorumludur, ikincisi ise 2, 102, 202 vb. üretmekten sorumludur. Parça üretimi, blok üretiminden farklı olarak bakım gerektirdiğinden durum ve her parça için yalnızca sww/n blok üreticileri durumu korur parça başına, buna uygun olarak yalnızca sww/n blok üreticileri, oluşturmak için dönüşümlü olarak çalışır. parçalar. Örn. dört blok üreticisinin atandığı yukarıdaki sabitlerle Her parça, her blok üreticisi her dört blokta bir parça oluşturacak. 3.4 Veri kullanılabilirliğinin sağlanması Veri kullanılabilirliğini sağlamak için Polkadot yaklaşımına benzer bir yaklaşım kullanıyoruz bölüm 2.5.3'te açıklanmıştır. Bir blok üreticisi bir parça ürettiğinde, optimal (w, ⌊w/6 + 1⌋) blok koduna sahip silme kodlu versiyonu yığın. Daha sonra silme kodlu parçanın bir parçasını gönderirler (bu tür parçalar diyoruz) her blok üreticisine parça parçaları veya sadece parçalar). Yapraklar gibi tüm parçaları içeren bir merkle ağacı hesaplıyoruz ve Her parçanın başlığı bu ağacın merkle kökünü içerir. Parçalar tek parça mesajları aracılığıyla validators'ye gönderilir. Bu tür mesajların her biri öbek başlığını, parçanın sırasını ve parça içeriğini içerir. mesaj aynı zamanda blok üreticisinin imzasını da içermektedir. parçanın başlığa karşılık geldiğini kanıtlamak için parça ve merkle yolu ve uygun blok üreticisi tarafından üretilmektedir. Bir blok üreticisi bir ana zincir bloğunu aldığında ilk olarak bu bloğun olup olmadığını kontrol eder. blokta yer alan her parça için tek parçalı mesajlar bulunur. Aksi takdirde blok eksik tek parçalı mesajlar alınana kadar işlenmez. Tüm tek parçalı mesajlar alındıktan sonra blok üreticisi, akranlarından kalan parçaları alır ve tuttukları parçaları yeniden yapılandırır devlet. Blok üreticisi en az bir ana zincir bloğunu işlemez. bloğa dahil edilen parçalarda karşılık gelen tek parçalı mesaj yoktur veya durumu korudukları en az bir parça için bunu yapamazlar tüm parçayı yeniden yapılandırın. Belirli bir parçanın mevcut olması için bloğun ⌊w/6⌋+1 olması yeterlidir Üreticiler kendi paylarına sahipler ve onlara hizmet ediyorlar. Böylece sayı kadar Kötü niyetli aktörler, yarım bloktan fazla bloğu olan hiçbir zincirin ⌊w/3⌋ değerini aşmaz bunu inşa eden üreticiler kullanılamayan parçalara sahip olabilir.Şekil 17: Her blok, parça başına bir veya sıfır parça içerir ve her parça silme kodludur. Silme kodlu yığının her bir parçası belirlenmiş bir yere gönderilir. özel bir tek bölümlü mesaj aracılığıyla yapımcıyı bloke etme 3.4.1 Tembel blok üreticileriyle uğraşmak Bir blok üreticisinin tek parçalı mesajın eksik olduğu bir bloğu varsa, yine de imzalamayı seçebilir, çünkü eğer blok zincire bağlanırsa blok üreticisinin ödülünü maksimuma çıkaracak. Blok için risk yok Daha sonra blok üreticisinin sahip olmadığını kanıtlamak imkansız olduğundan üretici tek parça mesajı. Bunu ele almak için, her bir parça üreticisini, parçayı oluştururken yapıyoruz. gelecekteki kodlanmış parçanın her bir parçası için bir renk (kırmızı veya mavi) seçin ve saklayın kodlanmadan önce yığındaki atanan rengin bit maskesi. Her bir parça mesaj parçaya atanan rengi içerir ve renk şu durumlarda kullanılır: kodlanmış parçaların merkle kökünün hesaplanması. Parça üreticisi saparsa protokole göre kolayca kanıtlanabilir, çünkü merkle kökü tek parça mesajlarına veya tek parça mesajlarındaki renklere karşılık gelir merkle köküne karşılık gelen, yığındaki maskeyle eşleşmeyecektir. Bir blok üreticisi bir bloğa imza attığında, tüm blokların bit maskesini ekler. bloğa dahil edilen parçalar için aldıkları kırmızı parçalar. Bir yayınlama yanlış bit maskesi kesilebilir bir davranıştır. Bir blok üreticisi bir sertifika almamışsa tek parçalı mesaj, mesajın rengini bilmelerinin hiçbir yolu yoktur ve dolayısıyla körü körüne imza atmaya kalkışmaları halinde %50 oranında kesintiye uğrama şansları vardır. Blok. 3.5 Durum geçiş başvurusu Parça üreticileri yalnızca parçaya hangi işlemlerin dahil edileceğini seçerler ancak bir yığın ürettiklerinde durum geçişini uygulamayın. Buna bağlı olarak,
yığın başlığı, daha önce olduğu gibi merkelize durumun merkle kökünü içerir yığındaki işlemler uygulanır. İşlemler yalnızca parçayı içeren tam bir blok olduğunda uygulanır işlenir. Bir katılımcı yalnızca şu durumlarda bir bloğu işler: 1. Önceki blok alındı ve işlendi; 2. Her parça için katılımcı sahip olduğu durumu korumaz tek parça mesajını gördüm; 3. Her parça için katılımcı, sahip oldukları durumu korur. tam yığın. Blok işlendikten sonra, katılımcının her bir parça için durumu korur, işlemleri uygular ve yeni durumu hesaplarlar işlemler uygulandıktan sonra üretime hazır hale gelirler herhangi bir parçaya atanmışlarsa bir sonraki bloğun parçaları yeni merkelleşmiş durumun merkle kökü. 3.6 Parçalar arası işlemler ve makbuzlar Bir işlemin birden fazla parçayı etkilemesi gerekiyorsa bunun ardışık olarak yapılması gerekir her parçada ayrı ayrı yürütülür. İşlemin tamamı ilk parçaya gönderilir etkilendiğinde ve işlem söz konusu parçanın öbeğine dahil edildiğinde ve öbek bir bloğa dahil edildikten sonra uygulanır, sözde bir makbuz üretir işlemin yapılması gereken bir sonraki parçaya yönlendirilen işlem idam edilecek. Daha fazla adımın gerekli olması halinde, alındı işleminin yürütülmesi yeni bir giriş hareketi oluşturur ve bu şekilde devam eder. 3.6.1 Makbuz işleminin ömrü Alış işleminin oluşturulduğu bloğun hemen ardından gelen blokta uygulanması arzu edilir. Makbuz işlemi yalnızca Önceki bloğun blok üreticileri tarafından alınıp uygulanmasından sonra oluşturulan kaynak parçayı koruyan ve o zamana kadar bilinmesi gereken Bir sonraki blok için parça, hedefin blok üreticileri tarafından üretilir kırık. Bu nedenle, makbuzun kaynak parçadan alıcıya iletilmesi gerekir. Bu iki olay arasındaki kısa zaman dilimindeki hedef parça. A, r girişini üreten bir t işlemini içeren son üretilen blok olsun. B bir sonraki üretilen blok olsun (yani A'yı içeren bir blok) r'yi içermek istediğimiz önceki bloğu). a ve r parçasında olsun kırıkta b. Şekil 18'de de gösterilen faturanın kullanım ömrü aşağıdaki gibidir: Makbuzların üretilmesi ve saklanması. Parça için parça üreticisi EBM'si a, A bloğunu alır, t işlemini uygular ve r makbuzunu oluşturur. EBM daha sonra üretilen tüm makbuzları dahili kalıcı depolama biriminde indekslenmiş olarak saklar kaynak parça kimliğine göre.Makbuzların dağıtılması. EBM, parçayı üretmeye hazır olduğunda B bloğu için a parçasını, a bloğu için A bloğundaki işlemlerin uygulanmasıyla oluşturulan tüm makbuzları getirir ve bunları parça için parçaya dahil ederler. B bloğunda a. Böyle bir yığın oluşturulduktan sonra, cpa onun silme kodunu üretir sürümü ve karşılık gelen tüm onepart mesajları. EBM, hangi blok üreticilerinin hangi parçalar için tam durumu koruduğunu bilir. Belirli bir blok üreticisi için bp cpa, A bloğundaki işlemlerin uygulanmasından kaynaklanan makbuzları içerir bp'nin hedef olarak önemsediği parçalardan herhangi birine sahip olan parça a için B bloğundaki a parçası için yığını dağıttıklarında tek parçalı mesajda (tek parçalı mesaja dahil edilen makbuzları gösteren şekil 17'ye bakın). Makbuzların alınması. Katılımcıların (hem blok üreticileri hem de validator'ler) tek parçalı mesajları alana kadar blokları işlemediklerini unutmayın. blokta yer alan her parça için. Böylece, herhangi bir katılımcı B bloğunu uyguladığında, B bloğuna karşılık gelen tüm tek parçalı mesajlara sahip olur. B'deki parçalar ve dolayısıyla parçaların bulunduğu tüm gelen makbuzlara sahipler katılımcı, varış yeri olarak durumunu korur. Uygularken belirli bir parça için durum geçişi, katılımcı hem makbuzları uygular tek parçalı mesajlarda parça için topladıklarının yanı sıra tüm yığının kendisinde yer alan işlemler. Şekil 18: Bir makbuz işleminin ömrü 3.6.2 Çok fazla makbuz işlemek Belirli bir parçayı hedefleyen faturaların sayısının belirli blok işlenemeyecek kadar büyük. Örneğin, şekil 19'u düşünün, her bir parçadaki her işlem, parça 1'i hedefleyen bir makbuz oluşturur. Bir sonraki blokta, parça 1'in işlemesi gereken faturaların sayısı şu şekilde olur: taşıma sırasında tüm parçaların bir araya getirdiği yükle karşılaştırılabilir önceki blok.
Şekil 19: Tüm faturalar aynı parçayı hedefliyorsa parçanın bunları işleme kapasitesi Bu sorunu çözmek için QuarkChain 9'da kullanılana benzer bir teknik kullanıyoruz. Spesifik olarak, her bir parça için son B bloğu ve onun içindeki son parça Fişlerin uygulandığı blok kaydedilir. Yeni parça ne zaman Oluşturulduğunda, fiş ilk önce B'de kalan parçalardan başlayarak uygulanır, ve sonra yeni yığın dolana kadar B'yi takip eden bloklar halinde. Normalin altında Dengeli bir yüke sahip koşullar altında, genellikle tüm tahsilatlar sonuçlanacaktır. uygulanıyor (ve böylece son bloğun son parçası kaydedilecek) her parça), ancak yükün dengeli olmadığı zamanlarda ve belirli bir Shard orantısız bir şekilde çok sayıda makbuz alıyor, bu teknik onların dahil edilen işlem sayısındaki sınırlara uyularak işlenecektir. Böyle dengesiz bir yükün uzun süre kalması durumunda gecikmenin Başvuruya kadar fiş oluşturma süresiz olarak büyümeye devam edebilir. Bir Bunu çözmenin yolu, bir hedefi hedefleyen bir makbuz oluşturan herhangi bir işlemi iptal etmektir. Belirli bir sabiti (ör. bir dönem) aşan bir işlem gecikmesine sahip olan parça. Şekil 20'yi düşünün. B bloğuna göre 4 numaralı parça tüm girişleri işleyemez, bu nedenle yalnızca A bloğundaki 3. parçaya kadar olan makbuzları işler ve onu kaydeder. C bloğunda B bloğundaki 5. parçaya kadar olan makbuzlar dahil edilir ve daha sonra D blokta parça yakalanır ve kalan tüm faturalar işlenir. B bloğu ve C bloğundaki tüm faturalar. 3.7 Parça doğrulama Belirli bir parça için üretilen bir parça (veya parça zincirli modelde belirli bir parça zinciri için üretilen bir parça bloğu) yalnızca şu şekilde doğrulanabilir: 9QuarkChain ile beyaz tahta bölümünü buradan izleyin: https://www.youtube.com/watch? v=opEtG6NM4x4, diğerlerinin yanı sıra parçalar arası işlemlere yaklaşımın tartışıldığı şeylerŞekil 20: Gecikmeli makbuz işleme Devleti koruyan katılımcılar. Blok üreticileri olabilirler, validators, veya yalnızca durumu indiren ve parçayı doğrulayan harici tanıklar varlıkları depoluyorlar. Bu belgede katılımcıların çoğunluğunun depolama yapamadığını varsayıyoruz. parçaların büyük bir kısmı için devlet. Ancak şunu belirtmekte yarar var varsayımıyla tasarlanmış parçalanmış blockchain'lerin bulunduğunu çoğu katılımcının durumunu saklama ve çoğu şeyi doğrulama kapasitesi vardır. QuarkChain gibi parçalar. Katılımcıların yalnızca bir kısmı parçayı doğrulama durumuna sahip olduğundan Parçalar halinde, yalnızca aşağıdaki özelliklere sahip olan katılımcıları uyarlanabilir şekilde yozlaştırmak mümkündür. durumu seçin ve geçersiz bir durum geçişi uygulayın. Her birkaç örnekte validators içeren birden fazla parçalama tasarımı önerildi gün ve bir gün içinde parça zincirinde 2/3'ten fazla olan herhangi bir blok söz konusu parçaya atanan validator'lerin imzalarının sayısı hemen dikkate alınır son. Böyle bir yaklaşımla, uyum sağlayabilen bir düşmanın yalnızca 2n/3+1'i yozlaştırması yeterlidir Geçersiz bir durum geçişi uygulamak için bir parça zincirindeki validator'lerin sayısı; Bunu başarmak muhtemelen zor olsa da, kamuya açık bir güvenlik düzeyi yeterli değil blockchain. Bölüm 2.3'te tartışıldığı gibi, ortak yaklaşım, durumu olan herhangi bir katılımcı için bir blok oluşturulduktan sonra belirli bir zaman aralığına izin vermektir (ister geçerliliğine meydan okuyan bir blok üreticisi, bir validator veya harici bir gözlemci). Bu tür katılımcılara Balıkçı denir. Bir balıkçının bunu yapabilmesi için Geçersiz bir bloğa itiraz edilmesi durumunda, böyle bir bloğun erişime açık olduğundan emin olunmalıdır. onlar. Nightshade'deki veri kullanılabilirliği bölüm 3.4'te tartışılmaktadır. Nightshade'de bir blok üretildiğinde parçalar gerçek parça üreticisi dışında herkes. Özellikle blok üreticisi bloğun doğal olarak çoğu parça için duruma sahip olmadığını öne sürdü veparçaları doğrulayamadı. Bir sonraki blok üretildiğinde, birden fazla blok üreticisinin ve validator'lerin onaylarını (bkz. bölüm 3.2) içerir, ancak blok üreticilerinin ve validator'lerin çoğunluğu durumu korumadığından çoğu kırık için de yalnızca bir geçersiz parçaya sahip bir blok, doğrulamaların yarısından önemli ölçüde fazlasını toplayacak ve en ağır blokta yer almaya devam edecek zincir. Bu sorunu çözmek için, durumunu koruyan herhangi bir katılımcıya izin veriyoruz. bu şekilde üretilen herhangi bir geçersiz parça için zincir üzerinde bir meydan okuma gönderecek bir parça kırık. 3.7.1 Devlet geçerliliği sorunu Bir katılımcı belirli bir parçanın geçersiz olduğunu tespit ettiğinde parçanın geçersiz olduğuna dair bir kanıt sunması gerekir. Ağ katılımcılarının çoğunluğu geçersiz parçanın bulunduğu parçanın durumunu korumadığından üretildiğinde, kanıtın bloğun doğrulandığını doğrulamak için yeterli bilgiye sahip olması gerekir. devlet olmadan geçersiz. Tek bir işlemin gerçekleştirebileceği durum miktarının (bayt cinsinden) Ls sınırını belirliyoruz. toplu olarak okuyabilir veya yazabilir. L'den daha fazlasına dokunan herhangi bir işlem durum geçersiz kabul edilir. Bölüm 3.5'ten hatırlayın ki yığın belirli bir B bloğunda yalnızca uygulanacak işlemleri içerir, ancak yeni durum kökü. B bloğundaki yığının içerdiği durum kökü durumdur root, bu tür işlemleri uygulamadan önce, ancak işlemleri uyguladıktan sonra B bloğundan önceki aynı parçadaki son parça. Kötü niyetli bir aktör geçersiz bir durum geçişi uygulamak istemeniz, yanlış bir durum kökü içerecektir uygulamadan kaynaklanan durum köküne karşılık gelmeyen B bloğunda önceki parçadaki işlemler. Bir parça üreticisinin parçaya dahil ettiği bilgiyi genişletiyoruz. Tüm işlemleri uyguladıktan sonra sadece durumu dahil etmek yerine, her bir bitişik işlem kümesi uygulandıktan sonra bir durum kökü içerir. toplu olarak Ls durum baytını okur ve yazar. Bu bilgilerle birlikte balıkçının devlet geçişinin yanlış uygulandığına dair bir zorluk yaratması Bu türden ilk geçersiz durum kökünü bulmak yeterlidir ve yalnızca Ls baytını içerir. son durum kökü arasındaki işlemlerden etkilenen durum (ki bu geçerli) ve merkle kanıtlarıyla birlikte mevcut durum kökü. Daha sonra herhangi bir katılımcı segmentteki işlemleri doğrulayabilir ve parçanın olduğunu doğrulayabilir geçersiz. Benzer şekilde, yığın üreticisi şunu okuyan işlemleri dahil etmeye çalışırsa: ve Ls bayttan daha fazla durum yazın, zorluk için dahil etmek yeterlidir Merkle kanıtlarıyla dokunduğu ilk Ls baytı, bu da yeterli olacaktır. işlemleri uygulayın ve bir girişimde bulunulacağı bir anın olduğunu onaylayın Ls bayt ötesinde içerik okuma veya yazma işlemi yapılır.
3.7.2 Balıkçılar ve hızlı çapraz parça işlemleri Bölüm 2.3'te tartışıldığı gibi, parça parçalarının (veya parçanın) modeldeki parça zincirli bloklar) geçersiz olabilir ve zorluk yaratabilir Bu durum nihailiği ve dolayısıyla parçalar arası iletişimi olumsuz etkiler. içinde özellikle herhangi bir çapraz parça işleminin hedef parçası kesin olamaz kaynak parça parçası veya blok, meydan okuma süresi bitene kadar nihaidir (bkz. şekil 21). Şekil 21: Makbuz uygulamadan önce sorgulama süresinin beklenmesi Bunu, parçalar arası işlemleri gerçekleştirecek şekilde ele almanın yolu hedef parçanın meydan okuma süresini beklememesi anlıktır kaynak parça işlemi yayınlandıktan sonra ve alındı işlemini uygulayın hemen, ancak daha sonra hedef parçayı kaynakla birlikte geri alın daha sonra kaynak parçanın veya bloğun geçersiz olduğu tespit edilirse parça (bkz. şekil 22). Bu, parçanın bulunduğu Nightshade tasarımı için çok doğal olarak geçerlidir. zincirler bağımsız değildir ancak bunun yerine parça parçalarının tümü yayınlanır birlikte aynı ana zincir bloğunda. Herhangi bir parçanın geçersiz olduğu tespit edilirse, bu parçaya sahip bloğun tamamı geçersiz kabul edilir ve üzerine inşa edilen tüm bloklar üstüne. Bkz. şekil 23. Yukarıdaki yaklaşımların her ikisi de, sorunun şu şekilde olduğu varsayılarak atomiklik sağlar: süre yeterince uzundur. Normal koşullar altında hızlı çapraz parça işlemlerinin sağlanması, hedef parça, aşağıdakilerden birinde geçersiz bir durum geçişi nedeniyle geri alınıyor son derece nadir bir olay olan kaynak parçaları. 3.7.3 validators gizleniyor Zorlukların varlığı, halihazırda bu olasılığı önemli ölçüde azaltıyor. uyarlanabilir yolsuzluk, çünkü bir yığını geçersiz bir durum geçiş gönderisiyle sonuçlandırmak içinŞekil 22: Makbuzların anında uygulanması ve varış noktasına geri alınması kaynak zincirinde geçersiz bir blok varsa zincir Şekil 23: Nightshade'de balıkçı mücadelesi Adaptif düşmanın tüm katılımcıları yozlaştırması gereken meydan okuma dönemi tüm validator'ler dahil olmak üzere parçanın durumunu koruyan. Böyle bir olayın olasılığını tahmin etmek son derece karmaşıktır, çünkü hiçbir Sharded blockchain bu tür bir saldırının denenmesine yetecek kadar uzun süredir yayında. Olasılığın son derece düşük olmasına rağmen hala yeterince yüksek olduğunu savunuyoruz. Milyonlarca işlemi yürütmesi beklenen bir sistem için büyük ve dünya çapında finansal operasyonlar yürütmek. Bu inancın iki temel nedeni vardır: 1. Proof-of-Stake zincirlerinin ve madencilerin validator'lerinin çoğu
İş Kanıtı zincirleri öncelikle finansal yükselişle teşvik ediliyor. Eğer Adaptif bir düşman onlara beklenen getiriden daha fazla para teklif eder dürüst bir şekilde faaliyet göstermekten dolayı, birçok validators'nin olmasını beklemek makul olacaktır. teklifi kabul edecek. 2. Birçok kuruluş Proof-of-Stake zincirlerinin doğrulamasını profesyonelce yapar ve Herhangi bir zincirdeki hisselerin büyük bir yüzdesinin bu tür kuruluşlardan. Bu tür varlıkların sayısı bir dönem için yeterince azdır. çoğunu kişisel olarak tanımak ve bozulmaya olan eğilimlerini iyi anlıyorlar. Hangi validator'lerin hangi parçaya atandığını gizleyerek uyarlamalı bozulma olasılığını azaltma konusunda bir adım daha ileri gidiyoruz. Fikir şu Algorand [5]'nin validators'yi gizlemesine uzaktan benzer. validator'ler, Algorand'da olduğu gibi gizlenmiş olsa bile, şunu unutmamak önemlidir: veya aşağıda açıklandığı gibi, uyarlanabilir bozulma teoride hala mümkündür. iken uyarlanabilir rakip, oluşturacak veya doğrulayacak katılımcıları tanımıyor Bir blok ya da yığın halinde, katılımcılar performans sergileyeceklerini kendileri biliyorlar. böyle bir görev ve bunun kriptografik bir kanıtı var. Böylece düşman yolsuzluk yapma niyetlerini yayınlayacak ve bunu sağlayacak herhangi bir katılımcıya ödeme yapacaktır. böyle bir kriptografik kanıt. Ancak şunu da belirtmeliyiz ki, rakip bunu yapmadığından bozmak istedikleri parçaya atanan validator'leri biliyorlarsa, belirli bir parçayı bozma niyetlerini yayınlamaktan başka seçeneği yok tüm topluluk. Bu noktada herhangi bir dürüst için ekonomik olarak faydalıdır. katılımcının bu parçayı doğrulayan tam bir düğümü döndürmesi için yüksek bir söz konusu parçada geçersiz bir bloğun görünme olasılığı; bir meydan okuma yaratın ve ilgili ödülü toplayın. Belirli bir parçaya atanan validator'leri açığa çıkarmamak için şunu yaparız: aşağıdakiler (bkz. şekil 24): Ödevi almak için VRF'yi kullanma. Her çağın başında her validator, validator'nin atandığı parçaların bit maskesini almak için bir VRF kullanır. Her validator'nin bit maskesi Sw bitlerine sahip olacaktır (tanım için bölüm 3.3'e bakın) Sw). validator daha sonra karşılık gelen parçaların durumunu getirir ve Alınan her blok için dönem boyunca karşılık gelen parçaları doğrular validator öğesinin atandığı parçalara. Parçalar yerine bloklar üzerinde oturum açın. Parça ataması gizlendiğinden validator parçalar üzerinde oturum açamaz. Bunun yerine her zaman bütünü imzalar böylece hangi parçaları doğruladığını açığa çıkarmıyor. Özellikle, validator bir blok alıp tüm parçaları doğruladığında ya bir mesaj oluşturur bu, validator öğesinin atandığı tüm parçalardaki tüm parçaların geçerli (bu parçaların ne olduğunu hiçbir şekilde belirtmeden) veya herhangi bir parçanın geçersiz olması durumunda geçersiz durum geçişinin kanıtını içerir. Bkz. Bu tür mesajların nasıl bir araya getirildiğine ilişkin ayrıntılar için bölüm 3.8, aşağıdakiler için bölüm 3.7.4: validators adlı kişinin gelen iletileri arka arkaya almasının nasıl önleneceğine ilişkin ayrıntılar nasıl ödüllendirileceği ve cezalandırılacağıyla ilgili ayrıntılar için diğer validators ve bölüm 3.7.5'e bakın validators başarılı bir geçersiz durum geçiş sorunu gerçekten meydana gelirse.Şekil 24: Nightshade'de validator'leri gizlemek 3.7.4 Taahhüt-Açıklama validators ile ilgili yaygın sorunlardan biri, validator'nin durumu indirmeyi ve aslında parçaları ve blokları doğrulamayı atlayabilmesi ve bunun yerine Ağı gözlemleyin, diğer validator'ların neler gönderdiğini görün ve yaptıklarını tekrarlayın. mesajlar. Böyle bir stratejiyi izleyen bir validator fazladan bir şey sağlamaz ağ için güvenlik sağlar, ancak ödüller toplar. Bu soruna yönelik yaygın bir çözüm, her validator için bir kanıt sağlamaktır örneğin benzersiz bir izleme sağlayarak bloğu gerçekten doğruladıklarını devlet geçişini uygulamak, ancak bu tür kanıtlar maliyeti önemli ölçüde artırıyor doğrulama. Şekil 25: Taahhüt-açıklama
Bunun yerine validators'nin doğrulama sonucuna ilişkin ilk taahhüdünü yaparız (veya parçaların geçerliliğini doğrulayan mesaj veya geçersiz olduğunun kanıtı durum geçişi), belirli bir süre bekleyin ve ancak bundan sonra şekil 25'te gösterildiği gibi gerçek doğrulama sonucunu ortaya çıkarın. ortaya çıkma dönemidir ve bu nedenle tembel bir validator dürüst validator'leri taklit edemez. Ayrıca, dürüst olmayan bir validator şunu doğrulayan bir mesaj gönderirse: atanan parçaların geçerliliği ve en az bir parçanın geçersiz olması durumunda öbeğin geçersiz olduğu gösterildiğinde validator eğik çizgiden kaçınamaz, çünkü, Bölüm 3.7.5'te gösterdiğimiz gibi böyle bir durumda kesilmemenin tek yolu geçersiz durum geçişinin kanıtını içeren bir mesaj sunmaktır. taahhütle eşleşir. 3.7.5 Zorluklarla baş etme Yukarıda tartışıldığı gibi, validator geçersiz parçaya sahip bir blok aldığında, önce geçersiz durum geçişinin kanıtını hazırlarlar (bkz. bölüm 3.7.1), ardından böyle bir kanıtı taahhüt edin (bkz. 3.7.4) ve bir süre sonra zorluğu ortaya çıkarın. Ortaya çıkan zorluk bir bloğa dahil edildiğinde aşağıdakiler gerçekleşir: 1. Bloktan gerçekleşen tüm durum geçişleri Ortaya çıkan zorluğun dahil edildiği bloğa kadar geçersiz parça hükümsüz kılındı. Ortaya çıkan mücadeleyi içeren bloktan önceki durum içeren bloktan önceki durumla aynı olduğu kabul edilir geçersiz yığın. 2. Belirli bir süre içinde her validator kendi bit maskesini göstermelidir doğruladıkları parçalar. Bit maskesi bir VRF aracılığıyla oluşturulduğundan, geçersiz durum geçişine sahip olan parçaya atandılar, ifşa etmekten kaçınamaz. Bit maskesini ortaya çıkaramayan herhangi bir validator parçaya atandığı varsayılmaktadır. 3. Bu süre sonunda parçaya atandığı tespit edilen her validator, içeren blok için bazı doğrulama sonuçları taahhüt etti geçersiz yığın ve bu geçersiz durum geçişinin kanıtını ortaya çıkarmadı bu onların taahhütlerine karşılık gelir. 4. Her validator yeni bir parça ataması alır ve yeni bir dönem planlanır tüm validator'ların indirmesi için yeterli bir süre sonra başlamak üzere Şekil 26'da gösterildiği gibi. validator'lerin kendilerine atanan parçaları ortaya çıkardığı andan itibaren unutmayın yeni dönem başlayana kadar sistemin güvenliği azaltılmıştır. Shard'ın ataması ortaya çıktı. Ağın katılımcılarının bunu saklaması gerekir Bu dönemde ağı kullanırken aklınızda bulundurun. 3.8 İmza Toplama Yüzlerce parçaya sahip bir sistemin güvenli bir şekilde çalışabilmesi için, 10.000 veya daha fazla validators sırası. Bölüm 3.7'de tartışıldığı gibi, her birini istiyoruz.Şekil 26: Mücadeleyi ele almak validator ortalama olarak belirli bir mesaja ve imzaya yönelik bir taahhüt yayınlamak için blok başına bir kez. Taahhüt mesajları aynı olsa bile, böyle bir şeyin toplanması BLS imzası ve bunun doğrulanması son derece pahalı olurdu. Ama doğal olarak taahhüt ve açıklama mesajları validators genelinde aynı değildir, dolayısıyla bu tür mesajları ve imzaları bir araya getirmenin bir yoluna ihtiyacımız var. Daha sonra hızlı doğrulamaya izin veren bir yol. Kullandığımız özel yaklaşım şudur: Doğrulayıcılar blok üreticilerine katılıyor. Blok üreticileri biliniyor çağın başlamasından bir süre önce, çünkü indirmeleri için biraz zamana ihtiyaçları var. çağ başlamadan önceki durum ve validator'lerden farklı olarak blok üreticileri gizlenmedi. Her blok üreticisinin v validator yuvası vardır. Doğrulayıcılar gönderir Blok üreticilerine v'lerinden biri olarak dahil edilmeleri için zincir dışı teklifler validators. Bir blok üreticisi validator eklemek isterse, validator'den gelen ilk zincir dışı talebi içeren işlem ve validator öğesinin blok üreticisine katılmasını sağlayan blok üreticisinin imzası. Blok üreticilerine atanan validator'lerin zorunlu olarak atanmadığını unutmayın. Blok üreticisinin parçalar ürettiği aynı parçaları doğrulayın. eğer bir Birden fazla blok üreticisini birleştirmek için validator uygulandı, yalnızca işlem ilk blok üreticisi başarılı olacaktır. Blok üreticileri taahhütleri toplar. Blok üreticisi sürekli olarak validators'den taahhüt ve açıklama mesajlarını toplar. Bu tür mesajların belirli bir sayısı toplandığında, blok üreticisi bir merkle hesaplar. bu mesajların ağacını oluşturur ve her validator'e merkle kökünü ve mesajlarına giden merkle yolu. validator yolu doğrular ve imzalar merkle kökü. Blok üreticisi daha sonra blok üzerinde bir BLS imzası biriktirir. validators'den merkle kökü ve yalnızca merkle kökü ve birikmiş imza Blok üreticisi aynı zamanda sözleşmenin geçerliliğini de imzalar. Ucuz bir ECDSA imzası kullanarak çoklu imza. Çoklu imza çalışmıyorsa gönderilen merkle köküyle veya katılan validator'ların bit maskesiyle eşleşirse, bu eğik çizgi çizilebilir bir davranıştır. Zinciri senkronize ederken bir katılımcı validator'lerden gelen tüm BLS imzalarını doğrulamayı seçebilir (bu, validator'nin ortak anahtarlarının toplanmasını gerektirdiğinden son derece pahalıdır) veya yalnızcaBlok üreticilerinin ECDMA imzalarına güveniyoruz ve blok üreticisine meydan okunmadı ve kesildi. Zorluklar için zincir içi işlemleri ve merkle kanıtlarını kullanma. o eğer hayırsa validators'den gelen mesajları açığa çıkarmanın hiçbir değeri olmadığı belirtilebilir. geçersiz durum geçişi algılandı. Yalnızca gerçek bilgiyi içeren mesajlar Geçersiz durum geçişinin kanıtlarının açıklanması gerekir ve yalnızca bu tür mesajlar için önceki taahhütle eşleştiklerinin gösterilmesi gerekir. Mesajın ihtiyacı var iki amaçla ortaya çıkar: 1. Zincirin geri dönüşünü fiilen başlatmak için geçersiz durum geçişi (bkz. bölüm 3.7.5). 2. validator belgesinin geçerliliğini kanıtlamaya çalışmadığını kanıtlamak için geçersiz yığın. Her iki durumda da iki konuyu ele almamız gerekiyor: 1. Gerçek taahhüt zincire dahil edilmedi, yalnızca merkle kökü diğer mesajlarla birleştirilmiş taahhüt. validator öğesinin şunu kullanması gerekiyor: Blok üreticisi tarafından sağlanan merkle yolu ve orijinal taahhütleri bu mücadeleye kararlı olduklarını kanıtla. 2. Tüm validator'lerin geçersiz parçaya atanması mümkündür. durum geçişi bozuk blok üreticilerine atanacak bunları sansürlüyorlar. Bunu aşmak için onların açıklamalarını göndermelerine izin veriyoruz Zincir üzerinde düzenli bir işlem olarak ve toplamayı atlayarak. İkincisine yalnızca geçersiz durum geçişinin kanıtları için izin verilir; son derece nadirdir ve bu nedenle blokların spam gönderilmesiyle sonuçlanmamalıdır. Ele alınması gereken son konu, blok üreticilerinin iletilerin toplanmasına katılmamayı veya belirli validators'leri kasıtlı olarak sansürlememeyi tercih edin. Blok haline getirerek ekonomik açıdan dezavantajlı hale getiriyoruz üretici ödülü, kendilerine atanan validators sayısıyla orantılıdır. Biz ayrıca dönemler arasındaki blok üreticilerinin büyük ölçüde kesiştiğinden (çünkü her zaman en yüksek hisseye sahip olan en üstteki katılımcılardır), validator'ler yapabilir Büyük ölçüde aynı blok üreticileriyle çalışmaya devam edin ve böylece riski azaltın Geçmişte onları sansürleyen bir blok üreticisine atanmak. 3.9 Anlık Görüntü Zinciri Ana zincirdeki bloklar çok sık üretildiğinden indirme tarihin tamamı çok hızlı bir şekilde pahalı hale gelebilir. Üstelik her zamandan beri blok çok sayıda katılımcının BLS imzasını içeriyorsa, yalnızca imzayı kontrol etmek için ortak anahtarların toplanması engelleyici hale gelebilir aynı zamanda pahalı. Son olarak, öngörülebilir bir gelecekte Ethereum 1.0 muhtemelen bir tane olarak kalacak en çok kullanılan blockchain'lerden biridir ve varlıkları aktarmanın anlamlı bir yolunu sunar
Ethereum'ye yakın olması bir gerekliliktir ve bugün BLS imzalarının doğrulanması Ethereum tarafında yakın blokların geçerliliği mümkün değildir. Nightshade ana zincirindeki her blok isteğe bağlı olarak bir Schnorr içerebilir böyle bir Schnorr içeren son bloğun başlığındaki çoklu imza çoklu imza. Bu tür bloklara anlık görüntü blokları diyoruz. İlk blok her çağ bir anlık görüntü bloğu olmalıdır. Böyle bir çoklu imza üzerinde çalışırken, blok üreticileri ayrıca validators'nin BLS imzalarını da biriktirmelidir son anlık görüntü bloğuna yerleştirin ve bunları bölümünde açıklandığı şekilde toplayın. bölüm 3.8. Blok üreticilerinin belirlediği dönem boyunca sabit olduğundan doğrulama hiçbir çağda yalnızca ilk anlık görüntü blokları yeterlidir. blok üreticilerinin ve validator'lerin büyük bir yüzdesinin gizli anlaşma yapıp yarattığını gösteriyor bir çatal. Çağın ilk bloğu hesaplamaya yetecek bilgiyi içermelidir dönemin blok üreticileri ve validator'ler. Ana zincirin yalnızca anlık görüntüsünü içeren alt zincirine diyoruz. anlık görüntü zincirini engeller. Schnorr çoklu imzası oluşturmak etkileşimli bir süreçtir, ancak ne kadar verimsiz olursa olsun bunu nadiren gerçekleştirmeniz gerekir; yeterli olacaktır. Schnorr çoklu imzaları Ethereum üzerinde kolayca doğrulanabilir, böylece çapraz-blockchain gerçekleştirmenin güvenli bir yolu için önemli temel öğeler sağlanır iletişim. Yakın zincirle senkronizasyon için yalnızca tüm anlık görüntülerin indirilmesi gerekir bloklar ve Schnorr imzalarının doğru olduğunu onaylar (isteğe bağlı olarak validators'nin bireysel BLS imzalarını da doğrular) ve ardından yalnızca senkronizasyon son anlık görüntü bloğundan ana zincir blokları.
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.
Çözüm
Bu belgede parçalı blockchains oluşturmaya yönelik yaklaşımları tartıştık ve mevcut yaklaşımlarla iki büyük zorluğu, yani durum geçerliliğini ele aldı ve veri kullanılabilirliği. Daha sonra bir parçalama tasarımı olan Nightshade'i sunduk. NEAR Protokolüne güç verir. Yorumlarınız, sorularınız veya geri bildirimleriniz varsa tasarım üzerinde çalışma devam etmektedir bu belgede lütfen https://near.chat. adresine gidin