Buku Putih NEAR
State Validity and Data Availability
State Validity and Data Availability
The core idea in sharded blockchains is that most participants operating or using the network cannot validate blocks in all the shards. As such, whenever any participant needs to interact with a particular shard they generally cannot download and validate the entire history of the shard. The partitioning aspect of sharding, however, raises a significant potential problem: without downloading and validating the entire history of a particular shard the participant cannot necessarily be certain that the state with which 5This section, except for subsection 2.5.3, was previously published at https://near.ai/ shard2. If you read it before, skip to the next section.
they interact is the result of some valid sequence of blocks and that such sequence of blocks is indeed the canonical chain in the shard. A problem that doesn’t exist in a non-sharded blockchain. We will first present a simple solution to this problem that has been proposed by many protocols and then analyze how this solution can break and what attempts have been made to address it. 2.1 Validators rotation The naive solution to state validity is shown on figure 5: let’s say we assume that the entire system has on the order of thousands validators, out of which no more than 20% are malicious or will otherwise fail (such as by failing to be online to produce a block). Then if we sample 200 validators, the probability of more than 1 3 failing for practical purposes can be assumed to be zero. Figure 5: Sampling validators 1 3 is an important threshold. There’s a family of consensus protocols, called BFT consensus protocols, that guarantees that for as long as fewer than 1 3 of participants fail, either by crashing or by acting in some way that violates the protocol, the consensus will be reached. With this assumption of honest validator percentage, if the current set of validators in a shard provides us with some block, the naive solution assumes that the block is valid and that it is built on what the validators believed to be the canonical chain for that shard when they started validating. The validators learned the canonical chain from the previous set of validators, who by the same assumption built on top of the block which was the head of the canonical chain before that. By induction the entire chain is valid, and since no set of validators at any point produced forks, the naive solution is also certain that the current chain is the only chain in the shard. See figure 6 for a visualization.
Figure 6: A blockchain with each block finalized via BFT consensus This simple solution doesn’t work if we assume that the validators can be corrupted adaptively, which is not an unreasonable assumption6. Adaptively corrupting a single shard in a system with 1000 shards is significantly cheaper than corrupting the entire system. Therefore, the security of the protocol decreases linearly with the number of shards. To have certainty in the validity of a block, we must know that at any point in history no shard in the system has a majority of validators colluding; with adaptive adversaries, we no longer have such certainty. As we discussed in section 1.5, colluding validators can exercise two basic malicious behaviors: create forks, and produce invalid blocks. Malicious forks can be addressed by blocks being cross-linked to the Beacon chain that is generally designed to have significantly higher security than the shard chains. Producing invalid blocks, however, is a significantly more challenging problem to tackle. 2.2 State Validity Consider figure 7 on which Shard #1 is corrupted and a malicious actor produces invalid block B. Suppose in this block B 1000 tokens were minted out of thin air on Alice’s account. The malicious actor then produces valid block C (in a sense that the transactions in C are applied correctly) on top of B, obfuscating the invalid block B, and initiates a cross-shard transaction to Shard #2 that transfers those 1000 tokens to Bob’s account. From this moment the improperly created tokens reside on an otherwise completely valid blockchain in Shard #2. Some simple approaches to tackle this problem are: 6Read this article for details on how adaptive corruption can be carried out: https://medium.com/nearprotocol/d859adb464c8. For more details on adaptive corruption, read https://github.com/ethereum/wiki/wiki/Sharding-FAQ# what-are-the-security-models-that-we-are-operating-under
Figure 7: A cross-shard transaction from a chain that has an invalid block 1. For validators of Shard #2 to validate the block from which the transaction is initiated. This won’t work even in the example above, since block C appears to be completely valid. 2. For validators in Shard #2 to validate some large number of blocks preceding the block from which the transaction is initiated. Naturally, for any number of blocks N validated by the receiving shard the malicious validators can create N+1 valid blocks on top of the invalid block they produced. A promising idea to resolve this issue would be to arrange shards into an undirected graph in which each shard is connected to several other shards, and only allow cross-shard transactions between neighboring shards (e.g. this is how Vlad Zamfir’s sharding essentially works7, and similar idea is used in Kadena’s Chainweb [1]). If a cross-shard transaction is needed between shards that are not neighbors, such transaction is routed through multiple shards. In this design a validator in each shard is expected to validate both all the blocks in their shard as well as all the blocks in all the neighboring shards. Consider a figure below with 10 shards, each having four neighbors, and no two shards requiring more than two hops for a cross-shard communication shown on figure 8. Shard #2 is not only validating its own blockchain, but also blockchains of all the neighbors, including Shard #1. So if a malicious actor on Shard #1 is attempting to create an invalid block B, then build block C on top of it and initiate a cross-shard transaction, such cross-shard transaction will not go through since Shard #2 will have validated the entire history of Shard #1 which will cause it to identify invalid block B. 7Read more about the design here: https://medium.com/nearprotocol/37e538177ed9
Figure 8: An invalid cross-shard transaction in chainweb-like system that will get detected While corrupting a single shard is no longer a viable attack, corrupting a few shards remains a problem. On figure 9 an adversary corrupting both Shard
1 and Shard #2 successfully executes a cross-shard transaction to Shard #3
with funds from an invalid block B: Figure 9: An invalid cross-shard transaction in chainweb-like system that will not get detected Shard #3 validates all the blocks in Shard #2, but not in Shard #1, and has no way to detect the malicious block. There are two major directions of properly solving state validity: fishermen
and cryptographic proofs of computation. 2.3 Fisherman The idea behind the first approach is the following: whenever a block header is communicated between chains for any purpose (such as cross-linking to the beacon chain, or a cross-shard transaction), there’s a period of time during which any honest validator can provide a proof that the block is invalid. There are various constructions that enable very succinct proofs that the blocks are invalid, so the communication overhead for the receiving nodes is way smaller than that of receiving a full block. With this approach for as long as there’s at least one honest validator in the shard, the system is secure. Figure 10: Fisherman This is the dominant approach (besides pretending the problem doesn’t exist) among the proposed protocols today. This approach, however, has two major disadvantages: 1. The challenge period needs to be sufficiently long for the honest validator to recognize a block was produced, download it, fully verify it, and prepare the challenge if the block is invalid. Introducing such a period would significantly slow down the cross-shard transactions. 2. The existence of the challenge protocol creates a new vector of attacks when malicious nodes spam with invalid challenges. An obvious solution to this problem is to make challengers deposit some amount of tokens that are returned if the challenge is valid. This is only a partial solution, as it might still be beneficial for the adversary to spam the system (and burn the deposits) with invalid challenges, for example to prevent the valid
challenge from a honest validator from going through. These attacks are called Grieving Attacks. See section 3.7.2 for a way to get around the latter point. 2.4 Succinct Non-interactive Arguments of Knowledge The second solution to multiple-shard corruption is to use some sort of cryptographic constructions that allow one to prove that a certain computation (such as computing a block from a set of transactions) was carried out correctly. Such constructions do exist, e.g. zk-SNARKs, zk-STARKs and a few others, and some are actively used in blockchain protocols today for private payments, most notably ZCash. The primary problem with such primitives is that they are notoriously slow to compute. E.g. Coda Protocol, that uses zk-SNARKs specifically to prove that all the blocks in the blockchain are valid, said in one of the interviews that it can take 30 seconds per transaction to create a proof (this number is probably smaller by now). Interestingly, a proof doesn’t need to be computed by a trusted party, since the proof not only attests to the validity of the computation it is built for, but to the validity of the proof itself. Thus, the computation of such proofs can be split among a set of participants with significantly less redundancy than would be necessary to perform some trustless computation. It also allows for participants who compute zk-SNARKs to run on special hardware without reducing the decentralization of the system. The challenges of zk-SNARKs, besides performance, are: 1. Dependency on less-researched and less-time-tested cryptographic primitives; 2. ”Toxic waste” — zk-SNARKs depend on a trusted setup in which a group of people performs some computation and then discards the intermediate values of that computation. If all the participants of the procedure collude and keep the intermediate values, fake proofs can be created; 3. Extra complexity introduced into the system design; 4. zk-SNARKs only work for a subset of possible computations, so a protocol with a Turing-complete smart contract language wouldn’t be able to use SNARKs to prove the validity of the chain. 2.5 Data Availability The second problem we will touch upon is data availability. Generally nodes operating a particular blockchain are separated into two groups: Full Nodes, those that download every full block and validate every transaction, and Light Nodes, those that only download block headers, and use Merkle proofs for parts of the state and transactions they are interested in, as shown on figure 11.
Figure 11: Merkle Tree Now if a majority of full nodes collude, they can produce a block, valid or invalid, and send its hash to the light nodes, but never disclose the full content of the block. There are various ways they can benefit from it. For example, consider figure 12: Figure 12: Data Availability problem There are three blocks: the previous, A, is produced by honest validators; the current, B, has validators colluding; and the next, C, will be also produced by honest validators (the blockchain is depicted in the bottom right corner). You are a merchant. The validators of the current block (B) received block A from the previous validators, computed a block in which you receive money,
and sent you a header of that block with a Merkle proof of the state in which you have money (or a Merkle proof of a valid transaction that sends the money to you). Confident the transaction is finalized, you provide the service. However, the validators never distribute the full content of the block B to anyone. As such, the honest validators of block C can’t retrieve the block, and are either forced to stall the system or to build on top of A, depriving you as a merchant of money. When we apply the same scenario to sharding, the definitions of full and light node generally apply per shard: validators in each shard download every block in that shard and validate every transaction in that shard, but other nodes in the system, including those that snapshot shard chains state into the beacon chain, only download the headers. Thus the validators in the shard are effectively full nodes for that shard, while other participants in the system, including the beacon chain, operate as light nodes. For the fisherman approach we discussed above to work, honest validators need to be able to download blocks that are cross-linked to the beacon chain. If malicious validators cross-linked a header of an invalid block (or used it to initiate a cross-shard transaction), but never distributed the block, the honest validators have no way to craft a challenge. We will cover three approaches to address this problem that complement each other. 2.5.1 Proofs of Custody The most immediate problem to be solved is whether a block is available once it is published. One proposed idea is to have so-called Notaries that rotate between shards more often than validators whose only job is to download a block and attest to the fact that they were able to download it. They can be rotated more frequently because they don’t need to download the entire state of the shard, unlike the validators who cannot be rotated frequently since they must download the state of the shard each time they rotate, as shown on figure 13. The problem with this naive approach is that it is impossible to prove later whether the Notary was or was not able to download the block, so a Notary can choose to always attest that they were able to download the block without even attempting to retrieve it. One solution to this is for Notaries to provide some evidence or to stake some amount of tokens attesting that the block was downloaded. One such solution is discussed here: https://ethresear.ch/t/ 1-bit-aggregation-friendly-custody-bonds/2236. 2.5.2 Erasure Codes When a particular light node receives a hash of a block, to increase the node’s confidence that the block is available it can attempt to download a few random pieces of the block. This is not a complete solution, since unless the light nodes collectively download the entire block the malicious block producers can choose
Figure 13: Validators need to download state and thus cannot be rotated frequently to withhold the parts of the block that were not downloaded by any light node, thus still making the block unavailable. One solution is to use a construction called Erasure Codes to make it possible to recover the full block even if only some part of the block is available, as shown on figure 14. Figure 14: Merkle tree built on top of erasure coded data Both Polkadot and Ethereum Serenity have designs around this idea that provide a way for light nodes to be reasonably confident the blocks are available. The Ethereum Serenity approach has a detailed description in [2].
2.5.3 Polkadot’s approach to data availability In Polkadot, like in most sharded solutions, each shard (called parachain) snapshots its blocks to the beacon chain (called relay chain). Say there are 2f + 1 validators on the relay chain. The block producers of the parachain blocks, called collators, once the parachain block is produced compute an erasure coded version of the block that consists of 2f +1 parts such that any f parts are sufficient to reconstruct the block. They then distribute one part to each validator on the relay chain. A particular relay chain validator would only sign on a relay chain block if they have their part for each parachain block that is snapshotted to such relay chain block. Thus, if a relay chain block has signatures from 2f + 1 validators, and for as long as no more than f of them violated the protocol, each parachain block can be reconstructed by fetching the parts from the validators that follow the protocol. See figure 15. Figure 15: Polkadot’s data availability 2.5.4 Long term data availability Note that all the approaches discussed above only attest to the fact that a block was published at all, and is available now. Blocks can later become unavailable for a variety of reasons: nodes going offline, nodes intentionally erasing historical data, and others. A whitepaper worth mentioning that addresses this issue is Polyshard [3], which uses erasure codes to make blocks available across shards even if several shards completely lose their data. Unfortunately their specific approach requires all the shards to download blocks from all other shards, which is prohibitively expensive. The long term availability is not as pressing of an issue: since no participant in the system is expected to be capable of validating all the chains in all the
shards, the security of the sharded protocol needs to be designed in such a way that the system is secure even if some old blocks in some shards become completely unavailable.
Validitas Negara dan Ketersediaan Data
Ide inti dalam blockchains yang dipecah adalah sebagian besar peserta mengoperasikan atau menggunakan jaringan tidak dapat memvalidasi blok di semua pecahan. Dengan demikian, kapan pun setiap peserta perlu berinteraksi dengan pecahan tertentu yang biasanya tidak bisa mereka lakukan unduh dan validasi seluruh riwayat beling. Namun, aspek partisi sharding memunculkan potensi yang signifikan masalah: tanpa mengunduh dan memvalidasi seluruh riwayat tertentu shard peserta belum tentu bisa memastikan negara bagian mana 5Bagian ini, kecuali subbagian 2.5.3, sebelumnya diterbitkan di https://near.ai/ pecahan2. Jika Anda membacanya sebelumnya, lewati ke bagian berikutnya.
mereka berinteraksi adalah hasil dari beberapa rangkaian blok yang valid dan rangkaian tersebut blok memang merupakan rantai kanonik dalam beling. Sebuah masalah yang tidak terjadi ada di blockchain yang tidak di-sharding. Pertama-tama kami akan menyajikan solusi sederhana untuk masalah yang telah diusulkan ini oleh banyak protokol dan kemudian menganalisis bagaimana solusi ini dapat rusak dan apa upaya telah dilakukan untuk mengatasinya. 2.1 Rotasi validator Solusi naif terhadap validitas negara ditunjukkan pada gambar 5: katakanlah kita berasumsi yang dimiliki seluruh sistem berjumlah ribuan validator, di antaranya tidak lebih dari 20% bersifat berbahaya atau akan gagal (misalnya gagal online untuk menghasilkan blok). Lalu jika kita mengambil sampel 200 validators, probabilitasnya lebih dari 1 3 kegagalan untuk tujuan praktis dapat diasumsikan nol. Gambar 5: Pengambilan sampel validatordtk 1 3 adalah ambang batas yang penting. Ada sekumpulan protokol konsensus, yang disebut BFT protokol konsensus, yang menjamin bahwa selama kurang dari 1 3 dari peserta gagal, baik karena menabrak atau bertindak dengan cara yang melanggar protokol, konsensus akan tercapai. Dengan asumsi persentase validator yang jujur, jika ditetapkan saat ini validators dalam pecahan memberi kita beberapa blok, asumsi solusi naif bahwa blok tersebut valid dan dibangun berdasarkan apa yang diyakini oleh validator rantai kanonik untuk pecahan tersebut ketika mereka mulai memvalidasi. validators mempelajari rantai kanonik dari kumpulan validator sebelumnya, yang juga melakukan hal yang sama asumsi yang dibangun di atas blok yang merupakan kepala rantai kanonik sebelum itu. Dengan induksi seluruh rantai valid, dan karena tidak ada himpunan validators pada titik mana pun dihasilkan garpu, solusi naifnya juga pasti arusnya rantai adalah satu-satunya rantai di pecahan. Lihat gambar 6 untuk visualisasinya.
Gambar 6: blockchain dengan setiap blok diselesaikan melalui konsensus BFT Solusi sederhana ini tidak akan berhasil jika kita berasumsi bahwa validator bisa berhasil dirusak secara adaptif, yang bukan merupakan asumsi yang tidak masuk akal6. Secara adaptif merusak satu pecahan dalam sistem dengan 1000 pecahan jauh lebih murah daripada merusak seluruh sistem. Oleh karena itu, keamanan protokol menurun secara linear seiring dengan jumlah shard. Untuk memperoleh kepastian keabsahan sebuah blok, kita harus tahu bahwa pada titik mana pun dalam sejarah tidak ada pecahan dalam sistem yang memilikinya mayoritas validator berkolusi; dengan musuh adaptif, kita tidak lagi memilikinya kepastian seperti itu. Seperti yang telah kita bahas di bagian 1.5, berkolusi validator dapat dilakukan dua perilaku dasar berbahaya: membuat fork, dan menghasilkan blok yang tidak valid. Garpu berbahaya dapat diatasi dengan menghubungkan blok ke rantai Beacon yang umumnya dirancang untuk memiliki keamanan yang jauh lebih tinggi daripada rantai pecahan. Namun, menghasilkan blok yang tidak valid adalah hal yang jauh lebih buruk masalah yang menantang untuk diatasi. 2.2 Validitas Negara Perhatikan gambar 7 di mana Shard #1 rusak dan dihasilkan oleh aktor jahat blok B tidak valid. Misalkan di blok ini 1000 token dicetak tipis mengudara di akun Alice. Aktor jahat kemudian menghasilkan blok C yang valid (dalam a merasakan bahwa transaksi di C diterapkan dengan benar) di atas B, membingungkan blok B yang tidak valid, dan memulai transaksi lintas pecahan ke Shard #2 itu mentransfer 1000 token itu ke rekening Bob. Mulai saat ini yang tidak semestinya token yang dibuat berada di blockchain yang sepenuhnya valid di Shard #2. Beberapa pendekatan sederhana untuk mengatasi masalah ini adalah: 6Baca ini artikel untuk detail pada bagaimana adaptif korupsi bisa menjadi dibawa keluar: https://medium.com/nearprotocol/d859adb464c8. Untuk lebih detail pada adaptif korupsi, membaca https://github.com/ethereum/wiki/wiki/Sharding-FAQ# model-keamanan-apa-yang-kami-operasikan-dibawahnyaGambar 7: Transaksi lintas pecahan dari rantai yang memiliki blok tidak valid 1. Untuk validators Shard #2 untuk memvalidasi blok tempat transaksi dimulai. Ini tidak akan berfungsi bahkan pada contoh di atas, karena blok C tampaknya sepenuhnya valid. 2. Untuk validators di Shard #2 untuk memvalidasi sejumlah besar blok sebelum blok tempat transaksi dimulai. Tentu saja untuk sejumlah blok N yang divalidasi oleh pecahan penerima yang berbahaya validators dapat membuat N+1 blok valid di atas blok tidak valid tersebut diproduksi. Ide yang menjanjikan untuk mengatasi masalah ini adalah dengan menyusun pecahan menjadi sebuah grafik tidak berarah di mana setiap pecahan terhubung ke beberapa pecahan lainnya, dan hanya mengizinkan transaksi lintas pecahan antar pecahan yang bertetangga (misalnya begini caranya Pecahan Vlad Zamfir pada dasarnya berhasil7, dan gagasan serupa digunakan dalam gagasan Kadena Jaringan rantai [1]). Jika diperlukan transaksi lintas shard antar shard yang ada bukan tetangga, transaksi tersebut disalurkan melalui banyak pecahan. Dalam desain ini a validator di setiap shard diharapkan memvalidasi semua blok di shardnya serta semua blok di semua pecahan di sekitarnya. Perhatikan gambar di bawah ini dengan 10 pecahan, masing-masing memiliki empat pecahan tetangga, dan tidak ada dua pecahan yang membutuhkan lebih banyak dari dua lompatan untuk komunikasi lintas pecahan yang ditunjukkan pada gambar 8. Pecahan #2 tidak hanya memvalidasi blockchain miliknya sendiri, tetapi juga blockchain dari semua tetangga, termasuk Shard #1. Jadi jika ada aktor jahat di Shard #1 sedang mencoba membuat blok B yang tidak valid, lalu membangun blok C di atasnya dan memulai transaksi lintas pecahan, transaksi lintas pecahan tersebut tidak akan berjalan melalui sejak Shard #2 akan memvalidasi seluruh sejarah Shard #1 yang mana akan menyebabkannya mengidentifikasi blok B yang tidak valid. 7Baca lebih lanjut tentang desain di sini: https://medium.com/nearprotocol/37e538177ed9
Gambar 8: Transaksi lintas pecahan yang tidak valid dalam sistem seperti chainweb yang akan melakukannya terdeteksi Meskipun merusak satu pecahan bukan lagi serangan yang layak, namun merusak a beberapa pecahan masih menjadi masalah. Pada gambar 9 musuh merusak kedua Shard
1 dan Shard #2 berhasil mengeksekusi transaksi lintas shard ke Shard #3
dengan dana dari blok B yang tidak valid: Gambar 9: Transaksi lintas pecahan yang tidak valid dalam sistem seperti chainweb yang akan melakukannya tidak terdeteksi Shard #3 memvalidasi semua blok di Shard #2, tetapi tidak di Shard #1, dan tidak memiliki cara untuk mendeteksi blok berbahaya. Ada dua arah utama dalam menyelesaikan validitas negara dengan tepat: nelayan
dan bukti komputasi kriptografi. 2.3 Nelayan Ide di balik pendekatan pertama adalah sebagai berikut: setiap kali ada header blok dikomunikasikan antar rantai untuk tujuan apa pun (seperti tautan silang ke rantai suar, atau transaksi lintas pecahan), ada periode waktu selama itu yang mana validator yang jujur dapat memberikan bukti bahwa blok tersebut tidak valid. Di sana Ada berbagai konstruksi yang memungkinkan bukti yang sangat ringkas bahwa balok-balok tersebut memang ada tidak valid, sehingga overhead komunikasi untuk node penerima jauh lebih kecil daripada menerima blok penuh. Dengan pendekatan ini selama setidaknya ada satu validator yang jujur di dalamnya pecahan, sistem aman. Gambar 10: Nelayan Ini adalah pendekatan yang dominan (selain berpura-pura bahwa masalahnya tidak ada) di antara protokol-protokol yang diusulkan saat ini. Namun pendekatan ini memiliki dua hal kelemahan utama: 1. Periode tantangan harus cukup lama untuk validator yang jujur untuk mengenali suatu blok telah diproduksi, mengunduhnya, memverifikasinya sepenuhnya, dan mempersiapkannya tantangan jika blok tidak valid. Memperkenalkan periode seperti itu akan membantu secara signifikan memperlambat transaksi lintas pecahan. 2. Adanya protokol tantangan menciptakan vektor serangan baru ketika node jahat melakukan spam dengan tantangan yang tidak valid. Solusi yang jelas untuk masalah ini adalah membuat penantang menyetor sejumlah tokens itu dikembalikan jika tantangannya valid. Ini hanyalah solusi parsial mungkin masih bermanfaat bagi musuh untuk mengirim spam ke sistem (dan membakar deposito) dengan tantangan yang tidak valid, misalnya untuk mencegah validtantangan dari validator yang jujur dari yang dilalui. Serangan-serangan ini adalah disebut Serangan Berduka. Lihat bagian 3.7.2 untuk mengetahui cara menyiasati poin terakhir. 2.4 Argumen Pengetahuan Non-interaktif Ringkas Solusi kedua terhadap korupsi multiple-shard adalah dengan menggunakan semacam konstruksi kriptografi yang memungkinkan seseorang membuktikan bahwa perhitungan tertentu (seperti sebagai komputasi satu blok dari serangkaian transaksi) dilakukan dengan benar. Konstruksi seperti itu memang ada, mis. zk-SNARKs, zk-STARKs dan beberapa lainnya, dan beberapa saat ini secara aktif digunakan dalam protokol blockchain untuk pembayaran pribadi, terutama ZCash. Masalah utama dengan kaum primitif seperti itu adalah mereka terkenal lambat untuk dihitung. Misalnya. Protokol Coda, yang menggunakan zk-SNARKs khusus untuk membuktikan bahwa semua blok di blockchain valid, dikatakan dalam satu dari wawancara bahwa diperlukan waktu 30 detik per transaksi untuk membuat bukti (jumlah ini mungkin lebih kecil saat ini). Menariknya, sebuah pembuktian tidak perlu dihitung oleh pihak yang terpercaya buktinya tidak hanya membuktikan keabsahan penghitungan yang dibuatnya, tetapi juga membuktikannya keabsahan pembuktian itu sendiri. Dengan demikian, perhitungan pembuktian tersebut dapat dibagi di antara sekelompok peserta dengan redundansi yang jauh lebih sedikit dibandingkan yang seharusnya diperlukan untuk melakukan beberapa perhitungan yang tidak dapat dipercaya. Hal ini juga memungkinkan untuk peserta yang menghitung zk-SNARK untuk dijalankan pada perangkat keras khusus tanpa mengurangi desentralisasi sistem. Tantangan zk-SNARKs, selain kinerja, adalah: 1. Ketergantungan pada kriptografi primitif yang kurang diteliti dan kurang teruji waktu; 2. "Limbah beracun" - zk-SNARK bergantung pada pengaturan tepercaya di mana suatu grup orang melakukan beberapa perhitungan dan kemudian membuang perantara nilai perhitungan itu. Jika semua peserta dalam prosedur berkolusi dan mempertahankan nilai tengahnya, bukti palsu dapat dibuat; 3. Kompleksitas ekstra dimasukkan ke dalam desain sistem; 4. zk-SNARKs hanya berfungsi untuk sebagian dari kemungkinan komputasi, jadi sebuah protokol dengan bahasa smart contract lengkap Turing tidak akan dapat digunakan SNARK untuk membuktikan validitas rantai. 2.5 Ketersediaan Data Masalah kedua yang akan kami bahas adalah ketersediaan data. Umumnya node mengoperasikan blockchain tertentu dipisahkan menjadi dua kelompok: Node Penuh, mereka yang mengunduh setiap blok penuh dan memvalidasi setiap transaksi, dan Ringan Node, yang hanya mengunduh header blok, dan menggunakan bukti Merkle untuk bagian-bagiannya negara dan transaksi yang mereka minati, seperti yang ditunjukkan pada gambar 11.
Gambar 11: Pohon Merkle Sekarang jika mayoritas node penuh berkolusi, mereka dapat menghasilkan blok, valid atau tidak valid, dan kirimkan hash-nya ke node lampu, tetapi jangan pernah mengungkapkan konten lengkapnya dari blok tersebut. Ada berbagai cara yang dapat mereka manfaatkan. Misalnya, perhatikan gambar 12: Gambar 12: Masalah Ketersediaan Data Ada tiga blok: blok sebelumnya, A, diproduksi oleh validators yang jujur; arus, B, berkolusi validator; dan berikutnya, C, juga akan diproduksi dengan jujur validators (blockchain digambarkan di pojok kanan bawah). Anda adalah seorang pedagang. validators dari blok saat ini (B) menerima blok A dari validators sebelumnya, menghitung blok tempat Anda menerima uang,dan mengirimi Anda tajuk blok itu dengan bukti Merkle tentang negara bagiannya Anda memiliki uang (atau bukti Merkle dari transaksi sah yang mengirimkan uang tersebut kepada Anda). Yakin transaksi telah selesai, Anda menyediakan layanan tersebut. Namun, validators tidak pernah mendistribusikan seluruh konten blok B ke dalamnya siapa pun. Dengan demikian, validator yang jujur dari blok C tidak dapat mengambil blok tersebut, dan terpaksa menghentikan sistem atau membangun di atas A, sehingga membuat Anda kehilangan a pedagang uang. Saat kami menerapkan skenario yang sama pada sharding, definisi penuh dan light node umumnya berlaku per shard: validators di setiap unduhan shard memblokir di pecahan itu dan memvalidasi setiap transaksi di pecahan itu, tetapi lainnya node dalam sistem, termasuk node yang mengambil status rantai pecahan ke dalam rantai suar, hanya unduh headernya. Jadi validator yang ada di pecahan adalah node penuh secara efektif untuk pecahan itu, sementara peserta lain dalam sistem, termasuk rantai suar, beroperasi sebagai titik cahaya. Agar pendekatan nelayan yang kita bahas di atas berhasil, jujurlah validators harus dapat mengunduh blok yang terhubung silang ke rantai suar. Jika validators jahat menghubungkan header dari blok yang tidak valid (atau menggunakannya untuk memulai transaksi lintas pecahan), tetapi tidak pernah mendistribusikan blok, jujur validators tidak punya cara untuk membuat tantangan. Kami akan membahas tiga pendekatan untuk mengatasi masalah ini yang saling melengkapi satu sama lain. 2.5.1 Bukti Penitipan Masalah paling mendesak yang harus dipecahkan adalah apakah suatu blok tersedia satu kali itu diterbitkan. Salah satu ide yang diusulkan adalah untuk memiliki apa yang disebut Notaris yang melakukan rotasi antar pecahan lebih sering daripada validator yang tugasnya hanya mengunduh a memblokir dan membuktikan fakta bahwa mereka dapat mengunduhnya. Bisa jadi diputar lebih sering karena tidak perlu mengunduh seluruh negara bagian pecahan, tidak seperti validator yang tidak dapat sering diputar sejak saat itu harus mengunduh status pecahan setiap kali beling diputar, seperti yang ditunjukkan pada gambar 13. Masalah dengan pendekatan naif ini adalah tidak mungkin dibuktikan di kemudian hari apakah Notaris itu mampu atau tidak untuk mengunduh blok tersebut, jadi Notaris dapat memilih untuk selalu membuktikan bahwa mereka dapat mengunduh blok tersebut tanpa bahkan mencoba mengambilnya. Salah satu solusinya adalah Notaris yang menyediakan beberapa bukti atau mempertaruhkan sejumlah token untuk membuktikan bahwa blok tersebut benar diunduh. Salah satu solusi tersebut dibahas di sini: https://ethresear.ch/t/ Obligasi-penahanan-ramah-agregasi-1-bit/2236. 2.5.2 Kode Penghapusan Ketika node cahaya tertentu menerima hash dari sebuah blok, untuk meningkatkan node tersebut yakin bahwa blok tersebut tersedia, ia dapat mencoba mengunduh beberapa secara acak potongan blok. Ini bukan solusi yang lengkap, karena kecuali titik cahaya secara kolektif mengunduh seluruh blok yang dapat dipilih oleh produsen blok jahat
Gambar 13: Validator perlu mengunduh status sehingga tidak dapat dirotasi sering untuk menahan bagian blok yang tidak diunduh oleh node lampu mana pun, sehingga masih membuat blok tidak tersedia. Salah satu solusinya adalah dengan menggunakan konstruksi yang disebut Erasure Codes untuk mewujudkannya untuk memulihkan blok penuh meskipun hanya sebagian dari blok yang tersedia, seperti yang ditunjukkan pada gambar 14. Gambar 14: Merkle tree dibangun di atas data berkode penghapusan Baik Polkadot dan Ethereum Serenity memiliki desain seputar gagasan ini yang menyediakan cara bagi node cahaya untuk cukup yakin bahwa blok tersebut tersedia. Pendekatan Ethereum Serenity memiliki penjelasan rinci di [2].2.5.3 Pendekatan Polkadot terhadap ketersediaan data Di Polkadot, seperti pada sebagian besar solusi shard, setiap shard (disebut parachain) mengambil snapshot bloknya ke rantai suar (disebut rantai relai). Katakanlah ada 2f + 1 validators pada rantai relai. Produsen blok dari blok parachain, disebut collators, setelah blok parachain diproduksi, hitung versi blok yang diberi kode penghapusan yang terdiri dari 2f +1 bagian sedemikian rupa sehingga f bagian mana pun mencukupi untuk merekonstruksi blok tersebut. Mereka kemudian mendistribusikan satu bagian ke setiap validator di rantai relai. Rantai relai tertentu validator hanya akan masuk pada rantai relai blok jika mereka memiliki bagiannya untuk setiap blok parachain yang di-snapshot blok rantai relai tersebut. Jadi, jika blok rantai relai memiliki tanda tangan dari 2f + 1 validators, dan selama tidak lebih dari f yang melanggar protokol, masing-masing blok parachain dapat direkonstruksi dengan mengambil bagian dari validators yang mengikuti protokol. Lihat gambar 15. Gambar 15: ketersediaan data Polkadot 2.5.4 Ketersediaan data jangka panjang Perhatikan bahwa semua pendekatan yang dibahas di atas hanya membuktikan fakta bahwa sebuah blok telah diterbitkan sama sekali, dan tersedia sekarang. Blok nantinya bisa menjadi tidak tersedia karena berbagai alasan: node mati, node sengaja menghapus riwayat data, dan lain-lain. Whitepaper yang layak disebutkan untuk mengatasi masalah ini adalah Polyshard [3], yang menggunakan kode penghapusan untuk membuat blok tersedia di seluruh pecahan meskipun beberapa pecahan benar-benar kehilangan datanya. Sayangnya pendekatan khusus mereka memerlukan hal ini semua pecahan untuk mengunduh blok dari semua pecahan lainnya, yang merupakan penghalang mahal. Ketersediaan jangka panjang bukanlah suatu masalah yang mendesak: karena tidak ada peserta dalam sistem diharapkan mampu memvalidasi semua rantai di semua
pecahan, keamanan protokol shard perlu dirancang sedemikian rupa cara agar sistem tetap aman meskipun beberapa blok lama di beberapa pecahan menjadi sama sekali tidak tersedia.
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 Dari rantai pecahan hingga pecahan pecahan Model sharding dengan rantai shard dan rantai suar sangat kuat namun mempunyai kompleksitas tertentu. Secara khusus, aturan pilihan garpu perlu dijalankan di setiap rantai secara terpisah, aturan pilihan garpu di rantai pecahan dan suar rantai harus dibuat secara berbeda dan diuji secara terpisah. Di Nightshade kami memodelkan sistem sebagai blockchain tunggal, yang masing-masingnya blok secara logis berisi semua transaksi untuk semua pecahan, dan mengubah seluruh keadaan dari semua pecahan. Namun secara fisik, tidak ada peserta yang mengunduhnya keadaan penuh atau blok logis penuh. Sebaliknya, masing-masing peserta jaringan saja mempertahankan status yang sesuai dengan pecahan yang transaksinya divalidasi, dan daftar semua transaksi di blok dibagi menjadi fisik potongan, satu potongan per pecahan. Dalam kondisi ideal, setiap blok berisi tepat satu bongkahan per pecahan per blok, yang kira-kira sesuai dengan model dengan rantai pecahan di mana rantai pecahan menghasilkan balok dengan kecepatan yang sama dengan rantai suar. Namun, karena penundaan jaringan, beberapa bagian mungkin hilang, jadi dalam praktiknya setiap blok berisi satu atau nol potongan per pecahan. Lihat bagian 3.3 untuk rincian tentang caranya blok diproduksi. Gambar 16: Model dengan rantai pecahan di sebelah kiri dan memiliki satu rantai blok terbelah menjadi beberapa bagian di sebelah kanan
3.2 Konsensus Dua pendekatan dominan terhadap konsensus di blockchains saat ini adalah rantai terpanjang (atau terberat), yaitu rantai yang mempunyai pekerjaan atau pasak paling banyak digunakan untuk membangunnya dianggap kanonik, dan BFT, di mana untuk setiap blok beberapa kumpulan validator mencapai konsensus BFT. Dalam protokol yang diusulkan baru-baru ini, pendekatan terakhir adalah pendekatan yang lebih dominan, karena hal ini memberikan penyelesaian langsung, sedangkan pada rantai terpanjang dibutuhkan lebih banyak blok untuk dibangun di atas blok untuk memastikan finalitas. Seringkali untuk sesuatu yang bermakna keamanan waktu yang dibutuhkan untuk membangun jumlah blok yang cukup urutan jam. Penggunaan konsensus BFT pada setiap blok juga memiliki kelemahan, seperti: 1. BFT konsensus melibatkan banyak komunikasi. Sementara kemajuan terkini memungkinkan konsensus dicapai dalam jumlah waktu yang linier peserta (lihat misalnya [4]), masih terlihat biaya overhead per blok; 2. Tidak mungkin semua peserta jaringan berpartisipasi dalam BFT konsensus per blok, sehingga biasanya hanya sebagian peserta yang diambil sampelnya secara acak yang mencapai konsensus. Himpunan sampel yang diambil secara acak, pada prinsipnya, dapat berupa dirusak secara adaptif, dan sebuah percabangan dalam teori dapat tercipta. Sistem keduanya perlu dicontohkan agar siap menghadapi peristiwa semacam itu, dan dengan demikian tetap saja memiliki aturan pilihan bercabang selain konsensus BFT, atau dirancang untuk ditutup turun dalam acara seperti itu. Perlu disebutkan bahwa beberapa desain, seperti Algorand [5], secara signifikan mengurangi kemungkinan korupsi adaptif. 3. Yang terpenting, sistem terhenti jika 1 3 atau lebih dari semua peserta adalah offline. Oleh karena itu, kesalahan jaringan sementara atau perpecahan jaringan dapat menghentikan sistem sepenuhnya. Idealnya sistem harus dapat terus berjalan beroperasi selama setidaknya setengah dari peserta sedang online (yang terberat protokol berbasis rantai terus beroperasi meskipun kurang dari separuh peserta sedang online, namun keinginan akan properti ini masih bisa diperdebatkan dalam komunitas). Model hibrida yang menggunakan konsensus adalah model yang paling berat rantai, tetapi beberapa blok diselesaikan secara berkala menggunakan gadget finalitas BFT mempertahankan keunggulan kedua model. Gadget finalitas BFT seperti itu Casper FFG [6] digunakan di Ethereum 2.0 8, Casper CBC (lihat https://vitalik. ca/general/2018/12/05/cbc_casper.html) dan GRANDPA (lihat https:// medium.com/polkadot-network/d08a24a021b5) digunakan di Polkadot. Nightshade menggunakan konsensus rantai terberat. Khususnya ketika sebuah blok produsen memproduksi sebuah blok (lihat bagian 3.3), mereka dapat mengumpulkan tanda tangan darinya produsen blok lain dan validators membuktikan blok sebelumnya. Lihat bagian 3.8 untuk rincian bagaimana sejumlah besar tanda tangan dikumpulkan. Beratnya 8Lihat juga sesi papan tulis bersama Justin Drake untuk gambaran mendalam tentang Casper FFG, dan bagaimana integrasinya dengan konsensus rantai terberat GHOST di sini: https://www. youtube.com/watch?v=S262StTwkmosuatu blok kemudian merupakan saham kumulatif dari semua penandatangan yang memiliki tanda tangan tersebut termasuk dalam blok tersebut. Berat suatu rantai adalah jumlah dari berat balok. Di atas konsensus rantai terberat, kami menggunakan gadget finalitas yang digunakan pengesahan untuk menyelesaikan blok. Untuk mengurangi kompleksitas sistem, kami menggunakan gadget finalitas yang tidak mempengaruhi aturan pilihan garpu dengan cara apa pun, dan sebagai gantinya hanya memperkenalkan kondisi pemotongan tambahan, sehingga satu blok menjadi satu diselesaikan oleh gadget finalitas, percabangan tidak mungkin dilakukan kecuali persentasenya sangat besar dari total taruhannya dipotong. Casper CBC adalah gadget finalitas, dan kami saat ini menjadi model dengan mempertimbangkan Casper CBC. Kami juga mengerjakan protokol BFT terpisah yang disebut TxFlow. Pada saat saat menulis dokumen ini, tidak jelas apakah TxFlow akan digunakan sebagai pengganti Casper KBK. Namun kami mencatat bahwa pilihan gadget finalitas sebagian besar ortogonal terhadap desain lainnya. 3.3 Blokir produksi Di Nightshade ada dua peran: produser blok dan validators. Kapan saja titik sistem berisi produsen blok w, w = 100 dalam model kita, dan wv validators, dalam model kami v = 100, wv = 10, 000. Sistemnya adalah Proof-of-Stake, artinya produsen blok dan validator memiliki sejumlah internal mata uang (disebut ”tokens”) dikunci untuk durasi waktu yang jauh melebihi waktu yang mereka habiskan untuk melaksanakan tugas mereka membangun dan memvalidasi rantai. Seperti semua sistem Proof of Stake, tidak semua produsen blok w dan tidak semua wv validator adalah entitas yang berbeda, karena hal tersebut tidak dapat diterapkan. Masing-masing dari produsen blok w dan wv validators, bagaimanapun, memiliki yang terpisah taruhan. Sistem berisi n pecahan, n = 1000 dalam model kami. Seperti disebutkan dalam bagian 3.1, di Nightshade tidak ada rantai pecahan, sebagai gantinya semua produsen blok dan validator sedang membangun satu blockchain, yang kami sebut sebagai rantai utama. Keadaan rantai utama dibagi menjadi n pecahan, dan setiap blok produser dan validator setiap saat hanya mengunduh sebagian dari secara lokal keadaan yang sesuai dengan beberapa subset pecahan, dan hanya memproses dan memvalidasi transaksi yang mempengaruhi bagian negara bagian tersebut. Untuk menjadi produsen blok, peserta jaringan mengunci beberapa blok besar jumlah tokens (satu taruhan). Pemeliharaan jaringan dilakukan dalam jangka waktu tertentu, di mana suatu zaman adalah periode waktu dalam urutan hari. Para peserta dengan taruhan terbesar pada awal periode tertentu adalah blok produsen untuk zaman itu. Setiap produser blok ditugaskan ke sw shards, (misalnya sw = 40, yang berarti sww/n = 4 produsen blok per pecahan). Blok produser mengunduh status shard yang ditugaskan kepada mereka sebelum epoch dimulai, dan sepanjang epoch mengumpulkan transaksi yang memengaruhi pecahan itu, dan menerapkannya pada negara. Untuk setiap blok b pada rantai utama, dan untuk setiap pecahan s, terdapat salah satu darinya menugaskan produser blok ke s yang bertanggung jawab memproduksi bagian b terkait ke pecahan. Bagian b yang berhubungan dengan shard s disebut chunk, dan berisi daftar transaksi pecahan yang akan dimasukkan ke dalam b, serta merkleakar dari keadaan yang dihasilkan. b pada akhirnya hanya akan berisi header yang sangat kecil chunk yaitu akar merkle dari semua transaksi yang diterapkan (lihat bagian 3.7.1 untuk rincian yang tepat), dan akar merkle dari keadaan akhir. Sepanjang sisa dokumen ini kita sering merujuk pada produsen blok yang bertanggung jawab untuk menghasilkan potongan pada waktu tertentu untuk pecahan tertentu sebagai produsen bongkahan. Produser bongkahan selalu menjadi salah satu produsen blok. Produsen blok dan produsen bongkahan merotasi setiap blok sesuai ke jadwal yang tetap. Produsen blok mendapat pesanan dan memproduksi berulang kali blok dalam urutan itu. Misalnya. jika ada 100 produsen blok, blok pertama produsen bertanggung jawab untuk memproduksi blok 1, 101, 201 dst, yang kedua adalah bertanggung jawab untuk memproduksi 2, 102, 202 dll). Karena produksi potongan, tidak seperti produksi blok, memerlukan pemeliharaan negara bagian, dan untuk setiap shard hanya produsen blok sww/n yang mempertahankan negara bagian tersebut per pecahan, hanya produsen blok sww/n yang dirotasi untuk membuat potongan. Misalnya. dengan konstanta di atas dengan empat produsen blok yang ditugaskan setiap pecahan, setiap produsen blok akan membuat potongan setiap empat blok. 3.4 Memastikan ketersediaan data Untuk memastikan ketersediaan data kami menggunakan pendekatan yang serupa dengan Polkadot dijelaskan di bagian 2.5.3. Setelah produsen blok memproduksi suatu bongkahan, mereka menciptakannya versi kode penghapusan dengan kode blok optimal (w, ⌊w/6 + 1⌋) dari potongan. Mereka kemudian mengirimkan satu bagian dari potongan kode penghapusan (kami menyebutnya potongan tersebut bagian potongan, atau hanya bagian) ke setiap produsen blok. Kami menghitung pohon merkle yang berisi semua bagian seperti daun, dan header setiap potongan berisi akar merkle dari pohon tersebut. Bagian-bagian tersebut dikirim ke validators melalui pesan satu bagian. Setiap pesan tersebut berisi header potongan, urutan bagian, dan isi bagian. Itu pesan juga berisi tanda tangan produser blok yang memproduksinya chunk dan jalur merkle untuk membuktikan bahwa bagian tersebut sesuai dengan header dan diproduksi oleh produsen blok yang tepat. Setelah produsen blok menerima blok rantai utama, pertama-tama mereka memeriksa apakah sudah diterima memiliki pesan satu bagian untuk setiap potongan yang disertakan dalam blok. Jika tidak, blokir tidak diproses sampai pesan satu bagian yang hilang diambil. Setelah semua pesan satu bagian diterima, produser blok mengambil pesan tersebut bagian yang tersisa dari rekan-rekannya dan merekonstruksi bagian-bagian yang mereka pegang negara bagian. Produsen blok tidak memproses blok rantai utama jika setidaknya untuk satu blok potongan yang termasuk dalam blok tersebut tidak memiliki pesan satu bagian yang sesuai, atau jika setidaknya untuk satu pecahan yang statusnya dipertahankan, mereka tidak dapat merekonstruksi seluruh potongan. Agar potongan tertentu tersedia, cukup ⌊w/6⌋+1 blok tersebut produsen memiliki bagiannya dan melayaninya. Jadi, selama jumlahnya aktor jahat tidak melebihi ⌊w/3⌋tidak ada rantai yang memiliki lebih dari setengah blok produsen yang membangunnya mungkin memiliki bagian yang tidak tersedia.Gambar 17: Setiap blok berisi satu atau nol bongkahan per pecahan, dan setiap bongkahan adalah kode penghapusan. Setiap bagian dari potongan kode penghapusan dikirim ke tempat yang ditunjuk blok produser melalui pesan satu bagian khusus 3.4.1 Berurusan dengan produsen blok yang malas Jika produsen blok mempunyai blok yang pesan satu bagiannya hilang, mereka mungkin memilih untuk tetap menandatanganinya, karena jika blok itu akhirnya dirantai akan memaksimalkan imbalan bagi produsen blok. Tidak ada risiko untuk pemblokiran tersebut produsen blok karena tidak mungkin untuk membuktikan kemudian bahwa produsen blok tidak memilikinya pesan satu bagian. Untuk mengatasinya kita membuat setiap potongan menjadi produser saat membuat potongan tersebut pilih warna (merah atau biru) untuk setiap bagian dari potongan yang dikodekan di masa depan, dan simpan bitmask warna yang ditetapkan dalam potongan sebelum dikodekan. Masing-masing bagian pesan kemudian berisi warna yang ditetapkan ke bagian tersebut, dan warna tersebut digunakan saat menghitung akar merkle dari bagian yang dikodekan. Jika produsen bongkahan menyimpang dari protokolnya bisa dibuktikan dengan mudah, karena root merkle juga tidak sesuai dengan pesan satu bagian, atau warna dalam pesan satu bagian itu sesuai dengan akar merkle tidak akan cocok dengan topeng di potongan. Ketika produsen blok menandatangani sebuah blok, mereka menyertakan bitmask dari semuanya bagian merah yang mereka terima untuk bongkahan yang termasuk dalam blok. Penerbitan sebuah bitmask yang salah adalah perilaku yang dapat disayat. Jika produsen blok belum menerima a pesan satu bagian, mereka tidak tahu warna pesannya, dan sehingga memiliki peluang 50% untuk ditebas jika mereka mencoba menandatangani secara membabi buta blok. 3.5 Aplikasi transisi negara Produsen bongkahan hanya memilih transaksi mana yang akan dimasukkan ke dalam bongkahan tersebut jangan menerapkan transisi keadaan ketika mereka menghasilkan potongan. Sejalan dengan itu,
header chunk berisi root merkle dari status merkel seperti sebelumnya transaksi dalam potongan diterapkan. Transaksi hanya diterapkan bila blok penuh yang mencakup potongan sedang diproses. Seorang peserta hanya memproses satu blok jika 1. Blok sebelumnya telah diterima dan diproses; 2. Untuk setiap bagian, peserta tidak mempertahankan status yang mereka miliki melihat pesan satu bagian; 3. Untuk setiap bagian, peserta mempertahankan status yang mereka miliki potongan penuh. Setelah blok diproses, untuk setiap pecahan yang menjadi peserta mempertahankan statusnya, mereka menerapkan transaksi dan menghitung status baru terhitung setelah transaksi diterapkan, setelah itu siap berproduksi potongan untuk blok berikutnya, jika ditugaskan ke pecahan apa pun, karena sudah ada akar merkle dari negara merkel baru. 3.6 Transaksi dan penerimaan lintas pecahan Jika suatu transaksi perlu memengaruhi lebih dari satu shard, transaksi tersebut harus dilakukan secara berurutan dieksekusi di setiap pecahan secara terpisah. Transaksi lengkap dikirim ke pecahan pertama terpengaruh, dan setelah transaksi dimasukkan dalam potongan untuk pecahan tersebut, dan diterapkan setelah potongan dimasukkan ke dalam blok, itu menghasilkan apa yang disebut tanda terima transaksi, yang dialihkan ke pecahan berikutnya yang memerlukan transaksi dieksekusi. Jika diperlukan lebih banyak langkah, eksekusi transaksi penerimaan menghasilkan transaksi penerimaan baru dan seterusnya. 3.6.1 Penerimaan transaksi seumur hidup Sebaiknya transaksi penerimaan diterapkan di blok yang segera mengikuti blok tempat transaksi tersebut dihasilkan. Transaksi resinya saja dihasilkan setelah blok sebelumnya diterima dan diterapkan oleh produsen blok yang mempertahankan pecahan asal, dan perlu diketahui pada saat itu potongan untuk blok berikutnya diproduksi oleh produsen blok tujuan pecahan. Oleh karena itu, tanda terima harus dikomunikasikan dari pecahan sumber ke pecahan tujuan dalam jangka waktu singkat antara kedua peristiwa tersebut. Misalkan A adalah blok terakhir yang diproduksi yang berisi transaksi t yang menghasilkan tanda terima r. Misalkan B adalah blok yang diproduksi berikutnya (yaitu blok yang mempunyai A sebagai blok sebelumnya) yang ingin kita tampung r. Misalkan t berada di pecahan a dan r dalam pecahan b. Masa berlaku kuitansi, juga digambarkan pada gambar 18, adalah sebagai berikut: Memproduksi dan menyimpan kuitansi. Cpa produsen bongkahan untuk shard a menerima blok A, menerapkan transaksi t dan menghasilkan tanda terima r. cpa kemudian menyimpan semua penerimaan yang dihasilkan dalam penyimpanan persisten internal yang diindeks dengan id pecahan sumber.Mendistribusikan kuitansi. Setelah cpa siap untuk menghasilkan potongannya shard a untuk blok B, mereka mengambil semua tanda terima yang dihasilkan dengan menerapkan transaksi dari blok A untuk shard a, dan memasukkannya ke dalam potongan untuk shrad a di blok B. Setelah potongan tersebut dibuat, cpa menghasilkan kode penghapusannya versi dan semua pesan satu bagian yang terkait. cpa mengetahui produsen blok mana yang mempertahankan status penuh untuk pecahan mana. Untuk produsen blok tertentu bp cpa mencakup penerimaan yang dihasilkan dari penerapan transaksi di blok A untuk shard a yang memiliki salah satu shard yang dipedulikan bp sebagai tujuannya dalam pesan satu bagian ketika mereka mendistribusikan potongan untuk pecahan a di blok B (lihat gambar 17, yang menunjukkan tanda terima yang disertakan dalam pesan satu bagian). Menerima kuitansi. Ingatlah bahwa peserta (produsen blok dan validators) tidak memproses blok sampai mereka memiliki pesan satu bagian untuk setiap potongan yang termasuk dalam blok. Jadi, pada saat peserta tertentu menerapkan blok B, mereka memiliki semua pesan satu bagian yang sesuai potongan di B, dan dengan demikian mereka memiliki semua tanda terima masuk yang memiliki pecahannya peserta mempertahankan negara bagian sebagai tujuannya. Saat menerapkan transisi status untuk pecahan tertentu, peserta menerapkan kedua tanda terima tersebut yang telah mereka kumpulkan untuk pecahan di pesan satu bagian, dan juga semuanya transaksi yang termasuk dalam potongan itu sendiri. Gambar 18: Seumur hidup transaksi penerimaan 3.6.2 Menangani terlalu banyak tanda terima Ada kemungkinan bahwa jumlah penerimaan yang menargetkan pecahan tertentu di a blok tertentu terlalu besar untuk diproses. Misalnya, perhatikan gambar 19, di yang mana setiap transaksi di setiap shard menghasilkan tanda terima yang menargetkan shard 1. Pada blok berikutnya, jumlah resi yang perlu diproses oleh shard 1 adalah sebanding dengan beban yang diproses gabungan semua pecahan saat ditangani blok sebelumnya.
Gambar 19: Jika semua tanda terima menargetkan shard yang sama, shard tersebut mungkin tidak memilikinya kemampuan untuk memprosesnya Untuk mengatasinya kami menggunakan teknik serupa dengan yang digunakan di QuarkChain 9. Khususnya, untuk setiap shard, blok B terakhir dan shard terakhir di dalamnya blok dari mana tanda terima diterapkan dicatat. Saat pecahan baru ada dibuat, tanda terima diterapkan secara berurutan terlebih dahulu dari sisa pecahan di B, dan kemudian di blok berikutnya B, sampai bongkahan baru penuh. Di bawah normal keadaan dengan beban seimbang maka umumnya akan menghasilkan semua penerimaan sedang diterapkan (dan dengan demikian pecahan terakhir dari blok terakhir akan dicatat setiap potongan), tetapi pada saat beban tidak seimbang, dan tertentu shard menerima banyak tanda terima yang tidak proporsional, teknik ini memungkinkannya diproses dengan tetap menghormati batasan jumlah transaksi yang disertakan. Perhatikan bahwa jika beban tidak seimbang tersebut bertahan dalam waktu yang lama, penundaan akan terjadi pembuatan tanda terima hingga aplikasi dapat terus berkembang tanpa batas. Satu cara untuk mengatasinya adalah dengan membatalkan transaksi apa pun yang menghasilkan tanda terima yang menargetkan a pecahan yang memiliki penundaan pemrosesan yang melebihi beberapa konstanta (misalnya satu zaman). Perhatikan gambar 20. Berdasarkan blok B pecahan 4 tidak dapat memproses semua kuitansi, jadi hanya memproses penerimaan asal hingga shard 3 di blok A, dan mencatatnya. Di blok C disertakan resi hingga pecahan 5 di blok B, dan kemudian di blok D pecahannya menyusul, memproses semua sisa kuitansi yang masuk blok B dan semua kuitansi dari blok C. 3.7 Validasi potongan Potongan yang dihasilkan untuk shard tertentu (atau blok shard yang diproduksi untuk rantai shard tertentu dalam model dengan rantai shard) hanya dapat divalidasi oleh 9Lihat episode papan tulis dengan QuarkChain di sini: https://www.youtube.com/watch? v=opEtG6NM4x4, yang didalamnya dibahas antara lain pendekatan transaksi cross-shard halGambar 20: Pemrosesan tanda terima tertunda peserta yang memelihara negara. Mereka dapat menjadi produsen blok, validators, atau hanya saksi eksternal yang mengunduh status dan memvalidasi pecahannya tempat mereka menyimpan aset. Dalam dokumen ini kami berasumsi bahwa mayoritas peserta tidak dapat menyimpan keadaan untuk sebagian besar pecahan. Namun perlu disebutkan, bahwa ada blockchain pecahan yang dirancang dengan asumsi bahwa sebagian besar peserta memiliki kapasitas untuk menyimpan status dan memvalidasi sebagian besarnya pecahannya, seperti QuarkChain. Karena hanya sebagian kecil peserta yang memiliki negara bagian untuk memvalidasi pecahan tersebut potongannya, dimungkinkan untuk adaptif korup hanya pada peserta yang memilikinya negara bagian, dan menerapkan transisi keadaan yang tidak valid. Beberapa desain sharding diusulkan dengan sampel validators setiap beberapa hari, dan dalam satu hari setiap blok dalam rantai pecahan yang memiliki lebih dari 2/3 tanda tangan validator yang ditugaskan pada pecahan tersebut segera dipertimbangkan terakhir. Dengan pendekatan seperti itu, musuh adaptif hanya perlu merusak 2n/3+1 dari validators dalam rantai pecahan untuk menerapkan transisi keadaan yang tidak valid, yang, Meskipun hal ini mungkin sulit dilakukan, namun tingkat keamanannya tidak memadai bagi masyarakat blockchain. Seperti yang dibahas di bagian 2.3, pendekatan umum adalah memberikan jangka waktu tertentu setelah blok dibuat untuk setiap peserta yang memiliki status (baik itu adalah produsen blok, validator, atau pengamat eksternal) yang menantang validitasnya. Peserta seperti ini disebut Nelayan. Agar seorang nelayan bisa menantang blok yang tidak valid, harus dipastikan bahwa blok tersebut tersedia mereka. Ketersediaan data di Nightshade dibahas di bagian 3.4. Di Nightshade, setelah blok diproduksi, potongan tersebut tidak divalidasi oleh siapa pun kecuali produser bongkahan sebenarnya. Khususnya, produsen blok itu menyarankan blok tersebut secara alami tidak memiliki status untuk sebagian besar pecahannya, dantidak dapat memvalidasi potongan tersebut. Ketika blok berikutnya diproduksi, blok tersebut berisi pengesahan (lihat bagian 3.2) dari beberapa produsen blok dan validators, tapi karena mayoritas produsen blok dan validator tidak mengelola negara untuk sebagian besar shard, sebuah blok yang hanya memiliki satu bongkahan yang tidak valid akan mengumpulkan lebih dari separuh pengesahan secara signifikan dan akan terus berada pada pengesahan terberat. rantai. Untuk mengatasi masalah ini, kami mengizinkan peserta mana pun yang mempertahankan status pecahan untuk mengirimkan tantangan secara on-chain untuk setiap potongan tidak valid yang dihasilkan di dalamnya pecahan. 3.7.1 Tantangan validitas negara Setelah peserta mendeteksi bahwa potongan tertentu tidak valid, mereka harus memberikan bukti bahwa potongan tersebut tidak valid. Karena sebagian besar peserta jaringan tidak mempertahankan status pecahan yang berisi potongan tidak valid dihasilkan, bukti tersebut perlu memiliki informasi yang cukup untuk memastikan blok tersebut tidak sah tanpa memiliki negara. Kami menetapkan batas Ls dari jumlah negara (dalam byte) yang satu transaksi dapat membaca atau menulis secara kumulatif. Setiap transaksi yang menyentuh lebih dari Ls negara dianggap tidak sah. Ingat dari bagian 3.5 bahwa potongan tersebut di blok B tertentu hanya berisi transaksi yang akan diterapkan, tapi tidak akar negara baru. Akar negara bagian yang termasuk dalam potongan di blok B adalah negara bagian root sebelum menerapkan transaksi tersebut, tetapi setelah menerapkan transaksi dari potongan terakhir di pecahan yang sama sebelum blok B. Aktor jahat itu ingin menerapkan transisi keadaan yang tidak valid akan mencakup akar keadaan yang salah di blok B yang tidak sesuai dengan state root yang dihasilkan dari penerapan transaksi pada potongan sebelumnya. Kami memperluas informasi yang disertakan oleh produsen bongkahan ke dalam bongkahan tersebut. Alih-alih hanya menyertakan negara setelah menerapkan semua transaksi, malahan menyertakan akar keadaan setelah menerapkan setiap rangkaian transaksi yang berdekatan itu secara kolektif membaca dan menulis Ls byte negara. Dengan informasi ini untuk nelayan untuk menciptakan tantangan bahwa transisi negara diterapkan secara tidak benar cukup untuk menemukan akar status pertama yang tidak valid, dan hanya menyertakan Ls byte keadaan yang dipengaruhi oleh transaksi antara akar keadaan terakhir (yang tadinya valid) dan akar status saat ini dengan bukti merkle. Lalu peserta mana saja dapat memvalidasi transaksi di segmen tersebut dan memastikan bahwa potongan tersebut benar tidak valid. Demikian pula, jika produsen potongan mencoba memasukkan transaksi yang terbaca dan menulis lebih dari Ls byte status, untuk tantangannya cukup dengan menyertakannya byte Ls pertama yang disentuhnya dengan bukti merkle, yang sudah cukup menerapkan transaksi dan memastikan bahwa ada saatnya upaya untuk melakukannya membaca atau menulis konten melebihi Ls byte dibuat.
3.7.2 Nelayan dan transaksi lintas pecahan yang cepat Seperti yang dibahas di bagian 2.3, setelah kita berasumsi bahwa potongan shard (atau shard blok dalam model dengan rantai pecahan) bisa jadi tidak valid dan menimbulkan tantangan periode, hal ini berdampak negatif pada finalitas, dan dengan demikian komunikasi lintas pecahan. Di khususnya, shard tujuan dari transaksi lintas shard tidak dapat dipastikan bongkahan atau blok pecahan asal bersifat final hingga periode tantangan selesai (lihat gambar 21). Gambar 21: Menunggu periode tantangan sebelum menerapkan tanda terima Cara mengatasinya dengan cara melakukan transaksi cross-shard instantenious adalah agar shard tujuan tidak menunggu periode tantangan setelah transaksi pecahan sumber dipublikasikan, dan terapkan transaksi tanda terima segera, tetapi kemudian kembalikan pecahan tujuan bersama dengan sumbernya shard jika kemudian potongan atau blok asal ditemukan tidak valid (lihat gambar 22). Ini berlaku secara alami pada desain Nightshade yang menggunakan beling rantai tidak independen, melainkan semua potongan pecahannya dipublikasikan bersama-sama dalam blok rantai utama yang sama. Jika ada potongan yang ditemukan tidak valid, maka seluruh blok dengan potongan itu dianggap tidak valid, dan semua blok dibangun di atasnya di atasnya. Lihat gambar 23. Kedua pendekatan di atas memberikan atomisitas dengan asumsi tantangan tersebut periodenya cukup lama. Kami menggunakan pendekatan terakhir karena menyediakan transaksi crossshard cepat dalam keadaan normal melebihi ketidaknyamanannya pecahan tujuan dibatalkan karena transisi status yang tidak valid di salah satu pecahan sumber, yang merupakan peristiwa yang sangat langka. 3.7.3 Menyembunyikan validators Adanya tantangan-tantangan tersebut sudah secara signifikan mengurangi kemungkinan terjadinya hal tersebut korupsi adaptif, karena menyelesaikan bagian dengan pos transisi keadaan yang tidak validGambar 22: Menerapkan tanda terima segera dan mengembalikan tujuan rantai jika rantai sumber memiliki blok yang tidak valid Gambar 23: Tantangan nelayan di Nightshade periode tantangan yang dibutuhkan musuh adaptif untuk merusak semua peserta yang mempertahankan status pecahan, termasuk semua validators. Memperkirakan kemungkinan kejadian seperti itu sangatlah rumit, karena tidak ada sharded blockchain telah berumur cukup lama untuk mencoba melakukan serangan seperti itu. Kami berpendapat bahwa kemungkinannya, walaupun sangat rendah, masih cukup besar besar untuk sistem yang diharapkan dapat mengeksekusi jutaan transaksi dan menjalankan operasi keuangan di seluruh dunia. Ada dua alasan utama keyakinan ini: 1. Sebagian besar validator rantai Proof-of-Stake dan penambang di
Rantai Proof-of-Work terutama diberi insentif oleh keuntungan finansial. Jika musuh yang adaptif menawarkan mereka lebih banyak uang daripada keuntungan yang diharapkan dari beroperasi dengan jujur, masuk akal untuk mengharapkan banyak validator akan menerima tawaran itu. 2. Banyak entitas melakukan validasi rantai Proof-of-Stake secara profesional, dan diperkirakan akan ada sebagian besar saham di rantai mana pun dari entitas tersebut. Jumlah entitas tersebut cukup kecil untuk sebuah musuh adaptif untuk mengenal sebagian besar dari mereka secara pribadi dan memiliki a pemahaman yang baik tentang kecenderungan mereka untuk dirusak. Kami mengambil satu langkah lebih jauh dalam mengurangi kemungkinan korupsi adaptif dengan menyembunyikan validator yang ditugaskan ke shard mana. Idenya adalah mirip dengan cara Algorand [5] menyembunyikan validators. Penting untuk dicatat bahwa meskipun validator disembunyikan, seperti pada Algorand atau seperti dijelaskan di bawah ini, korupsi adaptif secara teori masih mungkin terjadi. Sementara musuh adaptif tidak mengetahui peserta yang akan membuat atau memvalidasi satu blok atau satu bagian, para peserta sendiri mengetahui bahwa mereka akan tampil tugas seperti itu dan memiliki bukti kriptografiknya. Jadi, musuh bisa menyiarkan niatnya untuk melakukan korupsi, dan membayar kepada siapa saja peserta yang mau memberikan bukti kriptografi seperti itu. Namun kami mencatat, karena musuh tidak melakukannya mengetahui validator yang ditugaskan ke pecahan yang ingin mereka rusak, mereka tidak punya pilihan lain selain menyiarkan niat mereka untuk merusak pecahan tertentu seluruh komunitas. Pada titik ini, hal ini menguntungkan secara ekonomi bagi siapa pun yang jujur peserta untuk memutar node penuh yang memvalidasi pecahan tersebut, karena ada nilai high kemungkinan munculnya blok yang tidak valid di pecahan itu, yang merupakan peluang untuk itu buat tantangan dan kumpulkan hadiah terkait. Untuk tidak mengungkapkan validator yang ditetapkan ke pecahan tertentu, kami melakukannya berikut ini (lihat gambar 24): Menggunakan VRF untuk mendapatkan tugas. Di awal setiap zaman masing-masing validator menggunakan VRF untuk mendapatkan bitmask dari pecahan yang validator ditugaskan. Bitmask setiap validator akan memiliki bit Sw (lihat bagian 3.3 untuk definisinya dari Sw). validator kemudian mengambil status pecahan yang sesuai, dan selama masa untuk setiap blok yang diterima memvalidasi potongan yang sesuai ke pecahan tempat validator ditugaskan. Masuk dalam blok, bukan bongkahan. Karena penetapan pecahan disembunyikan, validator tidak dapat menandatangani pecahan. Sebaliknya, ia selalu memberi tanda secara keseluruhan blok, sehingga tidak mengungkapkan pecahan apa yang divalidasinya. Khususnya, ketika validator menerima sebuah blok dan memvalidasi semua potongan, ia akan membuat pesan yang membuktikan bahwa semua potongan di semua pecahan yang validator ditugaskan adalah valid (tanpa menunjukkan dengan cara apa pun pecahan itu), atau pesan itu berisi bukti transisi keadaan yang tidak valid jika ada bagian yang tidak valid. Lihat bagian 3.8 untuk rincian tentang bagaimana pesan-pesan tersebut dikumpulkan, bagian 3.7.4 untuk detail tentang cara mencegah validators membonceng pesan dari validator lainnya, dan bagian 3.7.5 untuk detail cara memberi penghargaan dan hukuman validators seandainya tantangan transisi keadaan tidak valid yang berhasil benar-benar terjadi.Gambar 24: Menyembunyikan validator di Nightshade 3.7.4 Pengungkapan Komitmen Salah satu masalah umum dengan validators adalah validator dapat melewatkan pengunduhan status dan benar-benar memvalidasi potongan dan blok, dan sebagai gantinya amati jaringannya, lihat apa yang dikirimkan validator lainnya dan ulangi pesan. validator yang mengikuti strategi seperti itu tidak memberikan tambahan apa pun keamanan untuk jaringan, tetapi mengumpulkan hadiah. Solusi umum untuk masalah ini adalah setiap validator memberikan bukti bahwa mereka benar-benar memvalidasi blok tersebut, misalnya dengan memberikan jejak unik penerapan transisi negara, namun bukti-bukti tersebut meningkatkan biaya secara signifikan validasi. Gambar 25: Pengungkapan komitmen
Sebaliknya kita membuat validator pertama yang berkomitmen pada hasil validasi (baik pesan yang membuktikan keabsahan potongan, atau bukti ketidakabsahan transisi keadaan), tunggu selama jangka waktu tertentu, baru kemudian tampilkan hasil validasi sebenarnya, seperti ditunjukkan pada gambar 25. Periode penerapan tidak bersinggungan dengan periode pengungkapan, dan dengan demikian validator yang malas tidak dapat meniru validator yang jujur. Terlebih lagi, jika validator yang tidak jujur berkomitmen pada pesan yang membuktikan hal tersebut validitas potongan yang ditetapkan, dan setidaknya satu potongan tidak valid, jika memang demikian ditunjukkan bahwa potongan tersebut tidak valid, validator tidak dapat menghindari pemotongan, karena, seperti yang kami tunjukkan di bagian 3.7.5, satu-satunya cara agar tidak terpotong dalam situasi seperti ini adalah menyajikan pesan yang berisi bukti transisi keadaan yang tidak valid itu cocok dengan komit. 3.7.5 Menangani tantangan Seperti dibahas di atas, setelah validator menerima blok dengan potongan yang tidak valid, mereka terlebih dahulu menyiapkan bukti transisi keadaan yang tidak sah (lihat bagian 3.7.1), kemudian berkomitmen pada bukti tersebut (lihat 3.7.4), dan setelah beberapa waktu ungkapkan tantangannya. Setelah tantangan yang terungkap dimasukkan ke dalam blok, hal berikut akan terjadi: 1. Semua transisi keadaan yang terjadi dari blok yang berisi potongan tidak valid sampai blok di mana tantangan yang terungkap disertakan, dapatkan dibatalkan. Keadaan sebelum blok yang mencakup tantangan yang terungkap dianggap sama dengan keadaan sebelum blok yang memuatnya potongan yang tidak valid. 2. Dalam jangka waktu tertentu setiap validator harus menampilkan bitmasknya pecahan yang mereka validasi. Karena bitmask dibuat melalui VRF, jika mereka ditugaskan ke pecahan yang memiliki transisi status tidak valid, mereka tidak bisa menghindari pengungkapannya. Setiap validator yang gagal menampilkan bitmask diasumsikan ditugaskan ke beling. 3. Setiap validator yang setelah periode tersebut ditemukan ditugaskan ke pecahan, yang melakukan komit pada beberapa hasil validasi untuk blok yang berisi potongan yang tidak valid dan itu tidak mengungkapkan bukti transisi keadaan yang tidak valid yang sesuai dengan komit mereka dipotong. 4. Setiap validator mendapat tugas pecahan baru, dan periode baru dijadwalkan untuk memulai setelah beberapa waktu yang cukup bagi semua validator untuk mengunduh keadaan, seperti yang ditunjukkan pada gambar 26. Perhatikan bahwa sejak validator mengungkapkan pecahan yang ditugaskan padanya hingga zaman baru dimulai, keamanan sistem berkurang sejak tugas pecahan terungkap. Para peserta jaringan perlu menjaganya diingat saat menggunakan jaringan selama periode tersebut. 3.8 Agregasi Tanda Tangan Agar sistem dengan ratusan pecahan dapat beroperasi dengan aman, kami ingin memilikinya pesanan 10.000 atau lebih validators. Seperti yang dibahas di bagian 3.7, kita menginginkan masing-masingGambar 26: Menangani tantangan validator untuk mempublikasikan rata-rata komit pada pesan dan tanda tangan tertentu sekali per blok. Meskipun pesan komitnya sama, menggabungkan a Menandatangani BLS dan memvalidasinya akan sangat mahal. Tapi tentu saja pesan komit dan pengungkapan tidak sama di validators, dan oleh karena itu kita memerlukan cara untuk menggabungkan pesan-pesan dan tanda tangan tersebut di a cara yang memungkinkan validasi cepat nanti. Pendekatan spesifik yang kami gunakan adalah sebagai berikut: Validator bergabung dengan produsen blok. Produsen blok sudah dikenal beberapa saat sebelum zaman dimulai, karena mereka memerlukan waktu untuk mengunduhnya menyatakan sebelum epoch dimulai, dan tidak seperti validators, produsen bloknya tidak disembunyikan. Setiap produser blok memiliki v validator slot. Validator mengirimkan proposal off-chain kepada produsen blok untuk dimasukkan sebagai salah satu dari v validatordtk. Jika produsen blok ingin memasukkan validator, mereka mengirimkan a transaksi yang berisi permintaan off-chain awal dari validator, dan tanda tangan produser blok yang membuat validator bergabung dengan produser blok. Perhatikan bahwa validator yang ditugaskan ke produsen blok belum tentu memvalidasi pecahan yang sama dengan yang dihasilkan oleh produsen blok. Jika sebuah validator diterapkan untuk bergabung dengan beberapa produsen blok, hanya transaksi dari produsen blok pertama akan berhasil. Produsen blok mengumpulkan komitmen. Produser blok terus-menerus mengumpulkan komit dan mengungkapkan pesan dari validators. Setelah sejumlah pesan tersebut terakumulasi, produsen blok menghitung merekle pohon pesan-pesan ini, dan mengirimkan ke setiap validator root merkle dan jalur merkle ke pesan mereka. validator memvalidasi jalur dan tanda masuk akar merkle. Produser blok kemudian mengumpulkan tanda tangan BLS di root merkle dari validators, dan hanya menerbitkan root merkle dan akumulasi tanda tangan. Produsen blok juga menandatangani keabsahan multisignature menggunakan tanda tangan ECDSA yang murah. Jika multisignature tidak cocok dengan root merkle yang dikirimkan atau bitmask dari validator yang berpartisipasi, ini merupakan perilaku yang dapat disayat. Saat menyinkronkan rantai, seorang peserta dapat memilih untuk memvalidasi semua tanda tangan BLS dari validator (yang sangat mahal karena melibatkan pengumpulan kunci publik validator), atau hanyatanda tangan ECDMA dari produsen blok dan mengandalkan fakta bahwa produsen blok tidak ditantang dan dipangkas. Menggunakan transaksi on-chain dan bukti merkle untuk tantangan. Itu dapat dicatat bahwa tidak ada gunanya mengungkapkan pesan dari validators jika tidak transisi keadaan yang tidak valid terdeteksi. Hanya pesan-pesan yang berisi hal yang sebenarnya bukti transisi negara yang tidak valid perlu diungkapkan, dan hanya untuk pesan-pesan seperti itu perlu ditunjukkan bahwa mereka cocok dengan komitmen sebelumnya. Pesannya perlu diungkapkan untuk dua tujuan: 1. Untuk benar-benar memulai rollback rantai ke momen sebelum transisi keadaan tidak valid (lihat bagian 3.7.5). 2. Untuk membuktikan bahwa validator tidak berusaha membuktikan keabsahan potongan tidak valid. Apa pun kasusnya, kita perlu mengatasi dua masalah: 1. Komit sebenarnya tidak disertakan pada rantai, hanya akar merkle saja komit dikumpulkan dengan pesan lain. validator perlu menggunakan jalur merkle yang disediakan oleh produsen blok dan komitmen awal mereka membuktikan bahwa mereka berkomitmen terhadap tantangan tersebut. 2. Ada kemungkinan bahwa semua validator yang ditugaskan ke beling dengan yang tidak valid transisi negara kebetulan ditugaskan ke produsen blok yang korup itu sedang menyensor mereka. Untuk menyiasatinya, kami mengizinkan mereka mengirimkan pengungkapannya sebagai transaksi reguler on-chain dan melewati agregasi. Yang terakhir ini hanya diperbolehkan untuk bukti transisi negara yang tidak sah, yaitu sangat jarang terjadi, sehingga tidak akan mengakibatkan pemblokiran spam. Masalah terakhir yang perlu diatasi adalah bahwa produsen blok dapat melakukan hal tersebut memilih untuk tidak berpartisipasi dalam pengumpulan pesan atau dengan sengaja menyensor validators tertentu. Kita buat yang tidak menguntungkan secara ekonomi, dengan membuat blok imbalan produser sebanding dengan jumlah validator yang ditugaskan kepada mereka. Kami juga mencatat bahwa karena produsen blok antar zaman sebagian besar berpotongan (sejak selalu menjadi peserta teratas dengan taruhan tertinggi), validator bisa sebagian besar tetap bekerja sama dengan produsen blok yang sama, dan dengan demikian mengurangi risiko ditugaskan ke produser blok yang pernah menyensornya di masa lalu. 3.9 Rantai Snapshot Karena blok pada rantai utama sangat sering diproduksi, pengunduhan sejarah lengkap mungkin menjadi mahal dengan sangat cepat. Apalagi sejak setiap blok berisi tanda tangan BLS dari sejumlah besar peserta, hanya agregasi kunci publik untuk memeriksa tanda tangan mungkin menjadi penghalang mahal juga. Terakhir, karena di masa mendatang Ethereum 1.0 kemungkinan besar akan tetap menjadi satu dari blockchain yang paling banyak digunakan, memiliki cara yang berarti untuk mentransfer aset
Mendekati Ethereum adalah persyaratan, dan hari ini memverifikasi tanda tangan BLS untuk memastikannya Validitas blok dekat pada sisi Ethereum tidak dimungkinkan. Setiap blok di rantai utama Nightshade secara opsional dapat berisi Schnorr multisignature pada header blok terakhir yang menyertakan Schnorr tersebut multitanda tangan. Kami menyebut blok tersebut sebagai blok snapshot. Blok pertama dari setiap zaman harus berupa blok snapshot. Saat mengerjakan multisignature seperti itu, produsen blok juga harus mengumpulkan tanda tangan BLS dari validators pada blok snapshot terakhir, dan menggabungkannya dengan cara yang sama seperti yang dijelaskan dalam bagian 3.8. Karena kumpulan produsen blok konstan sepanjang zaman, maka validasi hanya blok snapshot pertama di setiap epoch yang cukup dengan asumsi bahwa pada no menunjukkan sebagian besar produsen blok dan validator berkolusi dan berkreasi sebuah garpu. Blok pertama dari zaman tersebut harus berisi informasi yang cukup untuk dihitung produsen blok dan validators untuk zaman tersebut. Kami menyebut subrantai dari rantai utama yang hanya berisi snapshot memblokir rantai snapshot. Membuat multisignature Schnorr adalah proses interaktif, tapi sejak kami hanya perlu melakukannya secara jarang, proses apa pun, tidak peduli seberapa tidak efisiennya akan cukup. Multisignature Schnorr dapat dengan mudah divalidasi di Ethereum, sehingga memberikan primitif penting untuk cara yang aman dalam melakukan cross-blockchain komunikasi. Untuk menyinkronkan dengan rantai Dekat, seseorang hanya perlu mengunduh semua snapshot memblokir dan mengonfirmasi bahwa tanda tangan Schnorr sudah benar (opsional juga memverifikasi masing-masing tanda tangan BLS dari validators), dan kemudian hanya menyinkronkan blok rantai utama dari blok snapshot terakhir.
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.
Kesimpulan
Dalam dokumen ini kita membahas pendekatan untuk membangun blockchains dan mencakup dua tantangan besar dengan pendekatan yang ada, yaitu validitas negara dan ketersediaan data. Kami kemudian menghadirkan Nightshade, desain sharding itu kekuasaan NEAR Protokol. Desain sedang dalam proses, jika Anda memiliki komentar, pertanyaan, atau masukan pada dokumen ini, silakan buka https://near.chat.