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.
Statusgültigkeit und Datenverfügbarkeit
Die Kernidee bei Sharded blockchains ist, dass die meisten Teilnehmer, die bzw Durch die Nutzung des Netzwerks können Blöcke in allen Shards nicht validiert werden. Also wann immer Jeder Teilnehmer muss mit einem bestimmten Shard interagieren, was ihm im Allgemeinen nicht möglich ist Laden Sie den gesamten Verlauf des Shards herunter und validieren Sie ihn. Der Partitionierungsaspekt des Shardings birgt jedoch ein erhebliches Potenzial Problem: ohne den gesamten Verlauf einer bestimmten Datei herunterzuladen und zu validieren Shard Der Teilnehmer kann nicht unbedingt sicher sein, dass der Staat mit dem 5Dieser Abschnitt, mit Ausnahme von Unterabschnitt 2.5.3, wurde zuvor unter https://near.ai/ veröffentlicht. shard2. Wenn Sie es schon einmal gelesen haben, fahren Sie mit dem nächsten Abschnitt fort.
Ihre Interaktion ist das Ergebnis einer gültigen Folge von Blöcken und dieser Folge der Blöcke ist tatsächlich die kanonische Kette im Shard. Ein Problem, das nicht der Fall ist existieren in einem nicht fragmentierten blockchain. Wir werden zunächst eine einfache Lösung für dieses vorgeschlagene Problem vorstellen durch viele Protokolle und analysieren Sie dann, wie diese Lösung kaputt gehen kann und was Es wurden Versuche unternommen, das Problem anzugehen. 2.1 Rotation der Validatoren Die naive Lösung zur Staatsgültigkeit ist in Abbildung 5 dargestellt: Nehmen wir an, wir nehmen an dass das gesamte System in der Größenordnung von Tausenden validators hat, davon nicht mehr als 20 % sind böswillig oder werden auf andere Weise scheitern (z. B. indem sie es nicht tun). online, um einen Block zu erstellen). Wenn wir dann 200 validators abtasten, ist die Wahrscheinlichkeit von mehr als 1 3 Aus praktischen Gründen kann davon ausgegangen werden, dass der Wert null ist. Abbildung 5: Probenahme validators 1 3 ist ein wichtiger Schwellenwert. Es gibt eine Familie von Konsensprotokollen, genannt BFT Konsensprotokolle, die dies für weniger als 1 garantieren 3 von Teilnehmer scheitern, entweder durch einen Absturz oder durch ein Verhalten, das gegen die Regeln verstößt Protokoll wird der Konsens erzielt. Mit dieser Annahme ehrlicher validator Prozent, wenn der aktuelle Satz von Die naive Lösung geht davon aus, dass validators in einem Shard uns einen Block geben dass der Block gültig ist und dass er auf dem aufbaut, was die validators glaubten die kanonische Kette für diesen Shard, als sie mit der Validierung begannen. Die validators lernte die kanonische Kette aus dem vorherigen Satz von validators, die von demselben Annahme, die auf dem Block aufgebaut ist, der der Kopf der kanonischen Kette war davor. Durch Induktion ist die gesamte Kette gültig, und da keine Menge von validators An jedem Punkt, an dem Gabeln hergestellt werden, ist die naive Lösung auch sicher, dass der Strom vorhanden ist Kette ist die einzige Kette im Shard. Eine Visualisierung finden Sie in Abbildung 6.
Abbildung 6: Ein blockchain, bei dem jeder Block über einen BFT-Konsens abgeschlossen wird Diese einfache Lösung funktioniert nicht, wenn wir davon ausgehen, dass die validators möglich sind adaptiv korrumpiert, was keine unvernünftige Annahme ist6. Adaptiv Die Beschädigung eines einzelnen Shards in einem System mit 1000 Shards ist deutlich günstiger als das gesamte System zu beschädigen. Daher nimmt die Sicherheit des Protokolls linear mit der Anzahl der Shards ab. Um Gewissheit über die Gültigkeit zu haben Um einen Block zu erstellen, müssen wir wissen, dass es zu keinem Zeitpunkt in der Geschichte einen Shard im System gibt eine Mehrheit der validators konspiriert; Mit adaptiven Gegnern haben wir das nicht mehr solche Gewissheit. Wie wir in Abschnitt 1.5 besprochen haben, können konspirative validators Ausübung ausüben zwei grundlegende böswillige Verhaltensweisen: Forks erstellen und ungültige Blöcke erzeugen. Schädliche Forks können dadurch bekämpft werden, dass Blöcke mit der Beacon-Kette vernetzt werden, die im Allgemeinen für eine deutlich höhere Sicherheit ausgelegt ist die Scherbenketten. Das Erzeugen ungültiger Blöcke ist jedoch ein wesentlich größerer Aufwand herausforderndes Problem, das es zu bewältigen gilt. 2.2 Staatliche Gültigkeit Betrachten Sie Abbildung 7, in der Shard Nr. 1 beschädigt ist und ein böswilliger Akteur produziert ungültiger Block B. Angenommen, in diesem Block B wurden 1000 tokens aus dem Nichts geprägt Luft auf Alices Konto. Der böswillige Akteur erstellt dann einen gültigen Block C (in a (das Gefühl, dass die Transaktionen in C korrekt angewendet werden) auf B, was verschleiert den ungültigen Block B und initiiert eine Shard-übergreifende Transaktion zu Shard Nr. 2 überweist diese 1000 tokens auf Bobs Konto. Von diesem Moment an ist das falsch Die erstellten tokens befinden sich auf einem ansonsten vollständig gültigen blockchain in Shard Nr. 2. Einige einfache Ansätze zur Lösung dieses Problems sind: 6Lesen dies Artikel für Details auf wie adaptiv Korruption kann sein getragen aus: https://medium.com/nearprotocol/d859adb464c8. Für mehr Details auf adaptiv Korruption, lesen https://github.com/ethereum/wiki/wiki/Sharding-FAQ# Was sind die Sicherheitsmodelle, nach denen wir arbeiten?Abbildung 7: Eine Shard-übergreifende Transaktion aus einer Kette, die einen ungültigen Block hat 1. Für validators von Shard Nr. 2, um den Block zu validieren, von dem aus die Transaktion erfolgt wird eingeleitet. Dies wird auch im obigen Beispiel nicht funktionieren, da Block C scheint völlig gültig zu sein. 2. Damit validators in Shard Nr. 2 eine große Anzahl von Blöcken vor dem Block validieren, von dem aus die Transaktion initiiert wird. Natürlich, z Eine beliebige Anzahl von Blöcken N wird vom empfangenden Shard des Böswilligen validiert validators können N+1 gültige Blöcke zusätzlich zu dem ungültigen Block erstellen, den sie verwenden produziert. Eine vielversprechende Idee zur Lösung dieses Problems wäre die Anordnung von Shards in einer ungerichteter Graph, in dem jeder Shard mit mehreren anderen Shards verbunden ist, und Lassen Sie nur Cross-Shard-Transaktionen zwischen benachbarten Shards zu (z. B. so geht's). Das Sharding von Vlad Zamfir funktioniert im Wesentlichen7, und eine ähnliche Idee wird bei Kadena verwendet Chainweb [1]). Wenn eine Shard-übergreifende Transaktion zwischen Shards erforderlich ist keine Nachbarn, eine solche Transaktion wird über mehrere Shards geleitet. In diesem Design Es wird erwartet, dass ein validator in jedem Shard alle Blöcke in seinem Shard validiert sowie alle Blöcke in allen benachbarten Shards. Betrachten Sie die folgende Abbildung mit 10 Shards, von denen jeder vier Nachbarn hat und keine zwei Shards, die mehr erfordern mehr als zwei Hops für eine Shard-übergreifende Kommunikation, wie in Abbildung 8 dargestellt. Shard Nr. 2 validiert nicht nur seine eigene blockchain, sondern auch blockchains von alle Nachbarn, einschließlich Shard #1. Wenn es sich also um einen böswilligen Akteur auf Shard Nr. 1 handelt versucht, einen ungültigen Block B zu erstellen und dann Block C darauf aufzubauen und eine Cross-Shard-Transaktion initiieren, eine solche Cross-Shard-Transaktion wird nicht durchgeführt durch, da Shard Nr. 2 die gesamte Geschichte von Shard Nr. 1 validiert hat führt dazu, dass der ungültige Block B identifiziert wird. 7Lesen Sie hier mehr über das Design: https://medium.com/nearprotocol/37e538177ed9
Abbildung 8: Eine ungültige Cross-Shard-Transaktion in einem Chainweb-ähnlichen System entdeckt werden Während das Korrumpieren eines einzelnen Shards kein brauchbarer Angriff mehr ist, ist das Korrumpieren eines Shards kein brauchbarer Angriff mehr Wenig Scherben bleiben ein Problem. In Abbildung 9 korrumpiert ein Gegner beide Shards
1 und Shard #2 führen erfolgreich eine Cross-Shard-Transaktion zu Shard #3 aus
mit Mitteln aus einem ungültigen Block B: Abbildung 9: Eine ungültige Cross-Shard-Transaktion in einem Chainweb-ähnlichen System nicht erkannt werden Shard Nr. 3 validiert alle Blöcke in Shard Nr. 2, jedoch nicht in Shard Nr. 1, und hat keine Möglichkeit, den bösartigen Block zu erkennen. Es gibt zwei Hauptrichtungen zur ordnungsgemäßen Lösung der Staatsvalidität: Fischer
und kryptografische Rechennachweise. 2.3 Fischer Die Idee hinter dem ersten Ansatz ist die folgende: Immer wenn ein Blockheader angezeigt wird wird zwischen Ketten zu irgendeinem Zweck kommuniziert (z. B. zur Vernetzung mit dem B. einer Beacon-Kette oder einer Cross-Shard-Transaktion), gibt es einen Zeitraum während womit jeder ehrliche validator einen Beweis dafür liefern kann, dass der Block ungültig ist. Da Es gibt verschiedene Konstruktionen, die sehr prägnante Beweise dafür ermöglichen, dass es sich um Blöcke handelt ungültig, sodass der Kommunikationsaufwand für die empfangenden Knoten viel geringer ist als das Erhalten eines vollständigen Blocks. Mit diesem Ansatz, solange es mindestens einen ehrlichen validator in der Shard, das System ist sicher. Abbildung 10: Fischer Dies ist der vorherrschende Ansatz (neben der Behauptung, dass das Problem nicht existiert) unter den heute vorgeschlagenen Protokollen. Dieser Ansatz hat jedoch zwei Hauptnachteile: 1. Der Herausforderungszeitraum muss für den ehrlichen validator ausreichend lang sein Um zu erkennen, dass ein Block erstellt wurde, laden Sie ihn herunter, überprüfen Sie ihn vollständig und bereiten Sie ihn vor die Challenge, wenn der Block ungültig ist. Die Einführung eines solchen Zeitraums würde verlangsamen die Cross-Shard-Transaktionen erheblich. 2. Die Existenz des Challenge-Protokolls schafft einen neuen Angriffsvektor wenn bösartige Knoten mit ungültigen Herausforderungen spammen. Eine naheliegende Lösung Dieses Problem besteht darin, die Herausforderer dazu zu bringen, einen bestimmten Betrag an tokens einzuzahlen werden zurückgegeben, wenn die Challenge gültig ist. Dies ist nur eine Teillösung, wie es heißt könnte für den Angreifer immer noch von Vorteil sein, das System zu spammen (und zu verbrennen). der Einlagen) mit ungültigen Anfechtungen, beispielsweise zur Verhinderung der gültigenHerausforderung von einem ehrlichen validator vom Durchgehen. Diese Angriffe sind sogenannte Trauerattacken. Eine Möglichkeit, den letztgenannten Punkt zu umgehen, finden Sie in Abschnitt 3.7.2. 2.4 Prägnante, nicht interaktive Wissensargumente Die zweite Lösung für die Beschädigung mehrerer Shards besteht darin, kryptografische Konstruktionen zu verwenden, mit denen man beweisen kann, dass eine bestimmte Berechnung (z. B (z. B. die Berechnung eines Blocks aus einer Reihe von Transaktionen) wurde korrekt durchgeführt. Es gibt solche Konstruktionen, z.B. zk-SNARKs, zk-STARKs und einige andere, und einige werden heute aktiv in blockchain-Protokollen für private Zahlungen verwendet, vor allem ZCash. Das Hauptproblem bei solchen Grundelementen besteht darin, dass sie sind notorisch langsam zu berechnen. Z.B. Coda-Protokoll, das zk-SNARKs verwendet Insbesondere um zu beweisen, dass alle Blöcke in blockchain gültig sind, in einem Aus den Interviews geht hervor, dass die Erstellung eines Beweises 30 Sekunden pro Transaktion dauern kann (Diese Zahl ist wahrscheinlich mittlerweile kleiner). Interessanterweise muss ein Beweis nicht von einer vertrauenswürdigen Partei berechnet werden Der Beweis bescheinigt nicht nur die Gültigkeit der Berechnung, für die er erstellt wurde, sondern auch die Gültigkeit des Beweises selbst. Daher kann die Berechnung solcher Beweise aufgeteilt werden unter einer Gruppe von Teilnehmern mit deutlich geringerer Redundanz, als es der Fall wäre notwendig, um eine vertrauenswürdige Berechnung durchzuführen. Es ermöglicht auch Teilnehmern die zk-SNARKs berechnen, um auf spezieller Hardware zu laufen, ohne die zu reduzieren Dezentralisierung des Systems. Die Herausforderungen von zk-SNARKs sind neben der Leistung: 1. Abhängigkeit von weniger erforschten und weniger bewährten kryptografischen Grundelementen; 2. „Giftiger Abfall“ – zk-SNARKs sind auf ein vertrauenswürdiges Setup angewiesen, in dem eine Gruppe vorhanden ist der Leute führt eine Berechnung durch und verwirft dann das Zwischenprodukt Werte dieser Berechnung. Wenn alle Verfahrensbeteiligten Absprachen treffen und die Zwischenwerte beibehalten, können gefälschte Beweise erstellt werden; 3. Zusätzliche Komplexität im Systemdesign; 4. zk-SNARKs funktionieren nur für eine Teilmenge möglicher Berechnungen, also ein Protokoll mit einer Turing-vollständigen smart contract-Sprache wäre dies nicht möglich SNARKs zum Beweis der Gültigkeit der Kette. 2.5 Datenverfügbarkeit Das zweite Problem, das wir ansprechen werden, ist die Datenverfügbarkeit. Im Allgemeinen Knoten Betrieb eines bestimmten blockchain sind in zwei Gruppen unterteilt: Vollständige Knoten, diejenigen, die jeden vollständigen Block herunterladen und jede Transaktion validieren, und Light Knoten, die nur Blockheader herunterladen und Merkle-Proofs für Teile verwenden des Zustands und der Transaktionen, an denen sie interessiert sind, wie in Abbildung 11 dargestellt.
Abbildung 11: Merkle-Baum Wenn nun die Mehrheit der vollständigen Knoten zusammenarbeitet, können sie einen Block erzeugen, gültig oder ungültig, und senden Sie seine hash an die Lichtknoten, geben Sie jedoch niemals den vollständigen Inhalt preis des Blocks. Es gibt verschiedene Möglichkeiten, wie sie davon profitieren können. Zum Beispiel, Betrachten Sie Abbildung 12: Abbildung 12: Problem mit der Datenverfügbarkeit Es gibt drei Blöcke: Der vorherige, A, wird von ehrlichen validators erzeugt; der Strom, B, hat validators, die konspirieren; und das nächste, C, wird ebenfalls produziert von ehrlichen validators (der blockchain ist in der unteren rechten Ecke abgebildet). Sie sind ein Händler. Die validators des aktuellen Blocks (B) empfangenen Blocks Ein aus den vorherigen validators berechneter Block, in dem Sie Geld erhalten,und habe Ihnen einen Header dieses Blocks mit einem Merkle-Beweis für den Zustand geschickt, in dem er sich befindet Sie haben Geld (oder einen Merkle-Nachweis einer gültigen Transaktion, die das Geld sendet). für dich). Im Vertrauen darauf, dass die Transaktion abgeschlossen ist, erbringen Sie den Service. Allerdings verteilen die validators niemals den gesamten Inhalt des Blocks B an irgendjemand. Daher können die ehrlichen validators von Block C den Block nicht abrufen, und sind entweder gezwungen, das System zum Stillstand zu bringen oder auf A aufzubauen, wodurch Sie als a benachteiligt werden Geldhändler. Wenn wir das gleiche Szenario auf Sharding anwenden, ergeben sich die Definitionen von vollständig und Light-Knoten gelten im Allgemeinen pro Shard: validators in jedem Shard-Download alle Blockieren Sie diesen Shard und validieren Sie jede Transaktion in diesem Shard, außer anderen Knoten im System, einschließlich derjenigen, die Snapshot-Shard-Ketten in den Status aufnehmen Beacon-Kette, laden Sie nur die Header herunter. So lauten die validators im Shard effektiv vollständige Knoten für diesen Shard, während andere Teilnehmer im System, einschließlich der Beacon-Kette, fungieren als Lichtknoten. Damit der oben besprochene Fisherman-Ansatz funktioniert, sind ehrliche validators erforderlich Sie müssen in der Lage sein, Blöcke herunterzuladen, die mit der Beacon-Kette vernetzt sind. Wenn böswillige validators einen Header eines ungültigen Blocks vernetzten (oder ihn dazu nutzten). eine Cross-Shard-Transaktion initiieren), aber niemals den Block verteilen, das ehrlich validators haben keine Möglichkeit, eine Herausforderung zu gestalten. Wir werden drei Ansätze zur Lösung dieses Problems behandeln, die sich ergänzen einander. 2.5.1 Sorgerechtsnachweise Das unmittelbarste zu lösende Problem ist, ob ein Block einmal verfügbar ist es wird veröffentlicht. Eine vorgeschlagene Idee besteht darin, so genannte Notare einzusetzen, die rotieren zwischen Shards häufiger als validators, deren einzige Aufgabe darin besteht, a herunterzuladen blockieren und bestätigen, dass sie es herunterladen konnten. Das können sie sein häufiger rotiert, da nicht der gesamte Bundesstaat heruntergeladen werden muss des Shards, im Gegensatz zu den validators, die seitdem nicht häufig rotiert werden können Sie müssen bei jeder Drehung den Status des Shards herunterladen, wie in der Abbildung dargestellt 13. Das Problem bei diesem naiven Ansatz ist, dass es unmöglich ist, ihn später zu beweisen ob der Notar den Block herunterladen konnte oder nicht, also ein Notar können sich dafür entscheiden, immer zu bestätigen, dass sie den Block auch ohne herunterladen konnten sogar versucht, es wiederzubekommen. Eine Lösung hierfür ist die Bereitstellung durch Notare einige Beweise oder eine gewisse Menge an tokens einzusetzen, die belegen, dass der Block vorhanden war heruntergeladen. Eine solche Lösung wird hier diskutiert: https://ethresear.ch/t/ 1-bit-aggregation-freundliche-custody-bonds/2236. 2.5.2 Löschcodes Wenn ein bestimmter Lichtknoten einen hash eines Blocks empfängt, um den Knoten zu erhöhen Wenn Sie sicher sind, dass der Block verfügbar ist, können Sie versuchen, einige zufällige herunterzuladen Stücke des Blocks. Dies ist keine vollständige Lösung, da es sich nicht um die Lichtknoten handelt Laden Sie gemeinsam den gesamten Block herunter, den die böswilligen Blockproduzenten auswählen können
Abbildung 13: Validatoren müssen den Status herunterladen und können daher nicht rotiert werden häufig um die Teile des Blocks zurückzuhalten, die von keinem Lichtknoten heruntergeladen wurden, Dadurch ist der Block immer noch nicht verfügbar. Eine Lösung besteht darin, eine Konstruktion namens Erasure Codes zu verwenden, um dies zu ermöglichen um den gesamten Block wiederherzustellen, auch wenn nur ein Teil des Blocks verfügbar ist, wie gezeigt auf Abbildung 14. Abbildung 14: Merkle tree basiert auf löschcodierten Daten Sowohl Polkadot als auch Ethereum Serenity haben Designs rund um diese Idee Bieten Sie Lichtknoten die Möglichkeit, einigermaßen sicher zu sein, dass die Blöcke verfügbar sind. Eine ausführliche Beschreibung des Ethereum Serenity-Ansatzes finden Sie in [2].2.5.3 Polkadots Ansatz zur Datenverfügbarkeit In Polkadot erstellt, wie in den meisten Shard-Lösungen, jeder Shard (Parachain genannt) einen Snapshot seiner Blöcke in der Beacon-Kette (Relay-Kette genannt). Angenommen, es gibt 2f + 1 validators in der Relaiskette. Die Blockproduzenten der Parachain-Blöcke, genannt Collatoren berechnen nach der Erstellung des Parachain-Blocks eine löschcodierte Version des Blocks, die aus 2f +1 Teilen besteht, sodass alle f-Teile ausreichen um den Block zu rekonstruieren. Anschließend verteilen sie einen Teil an jeden validator auf der Relaiskette. Eine bestimmte Relay-Kette validator würde sich nur an einer Relay-Kette anmelden Block, wenn sie ihren Teil für jeden Parachain-Block haben, auf den ein Snapshot erstellt wird ein solcher Relaiskettenblock. Wenn also ein Relay-Chain-Block Signaturen von 2f + 1 hat validators und solange jeweils nicht mehr als f von ihnen gegen das Protokoll verstoßen haben Der Parachain-Block kann durch Abrufen der Teile aus den validators rekonstruiert werden die dem Protokoll folgen. Siehe Abbildung 15. Abbildung 15: Datenverfügbarkeit von Polkadot 2.5.4 Langfristige Datenverfügbarkeit Beachten Sie, dass alle oben diskutierten Ansätze nur die Tatsache bestätigen, dass ein Block vorliegt wurde überhaupt veröffentlicht und ist jetzt verfügbar. Blöcke können später nicht mehr verfügbar sein Aus verschiedenen Gründen: Knoten gehen offline, Knoten löschen absichtlich historische Daten Daten und andere. Ein erwähnenswertes Whitepaper, das sich mit diesem Problem befasst, ist Polyshard [3], das Löschcodes verwendet, um Blöcke über Shards hinweg verfügbar zu machen, auch wenn es mehrere sind Shards verlieren ihre Daten vollständig. Leider erfordert ihr spezifischer Ansatz Alle Shards, um Blöcke von allen anderen Shards herunterzuladen, was unerschwinglich ist teuer. Die langfristige Verfügbarkeit ist kein so dringendes Problem: da kein Teilnehmer Es wird erwartet, dass das System in der Lage ist, alle Ketten in allen zu validieren
Shards, die Sicherheit des Shard-Protokolls muss so gestaltet sein So ist das System sicher, auch wenn einige alte Blöcke in einigen Shards beschädigt werden völlig nicht verfügbar.
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 Von Splitterketten bis hin zu Splitterbrocken Das Sharding-Modell mit Shard-Ketten und einer Beacon-Kette ist jedoch sehr leistungsfähig hat gewisse Komplexitäten. Insbesondere muss die Fork-Choice-Regel ausgeführt werden in jeder Kette separat, die Fork-Choice-Regel in den Shard-Ketten und das Beacon Die Kette muss unterschiedlich aufgebaut und separat getestet werden. In Nightshade modellieren wir das System als ein einzelnes blockchain, in dem jedes Der Block enthält logisch alle Transaktionen für alle Shards und ändert die Gesamtzustand aller Scherben. Physisch lädt jedoch kein Teilnehmer das herunter Vollständiger Zustand oder vollständiger logischer Block. Stattdessen nur jeder Teilnehmer des Netzwerks behält den Zustand bei, der den Shards entspricht, für die sie Transaktionen validieren, und die Liste aller Transaktionen im Block wird in physische Transaktionen aufgeteilt Chunks, ein Chunk pro Shard. Unter idealen Bedingungen enthält jeder Block genau einen Chunk pro Shard Block, der in etwa dem Modell mit Shard-Ketten entspricht, in dem die Shard-Ketten produzieren Blöcke mit der gleichen Geschwindigkeit wie die Beacon-Kette. Allerdings Aufgrund von Netzwerkverzögerungen könnten einige Chunks fehlen, also in der Praxis jeder Block enthält entweder einen oder keinen Chunk pro Shard. Einzelheiten dazu finden Sie in Abschnitt 3.3 Blöcke entstehen. Abbildung 16: Ein Modell mit Splitterketten auf der linken Seite und mit einer Kette auf der linken Seite Auf der rechten Seite sind die Blöcke in Stücke aufgeteilt
3.2 Konsens Die beiden vorherrschenden Konsensansätze in den blockchains sind heute die längste (oder schwerste) Kette, in der die Kette die meiste Arbeit oder den größten Anteil hat Es gilt als kanonisch, um es zu erstellen, und BFT, in dem für jeden Block einige Satz von validators erreichen einen BFT Konsens. In den kürzlich vorgeschlagenen Protokollen ist letzterer ein dominanterer Ansatz. da es sofortige Endgültigkeit bietet, während in der längsten Kette mehr Blöcke benötigt werden auf dem Block aufgebaut werden, um die Endgültigkeit zu gewährleisten. Oftmals für eine sinnvolle Sicherheit: Die Zeit, die benötigt wird, um eine ausreichende Anzahl von Blöcken zu erstellen, nimmt auf Reihenfolge der Stunden. Die Verwendung des BFT-Konsenses für jeden Block hat auch Nachteile, wie zum Beispiel: 1. BFT Konsens erfordert einen erheblichen Kommunikationsaufwand. Während Die jüngsten Fortschritte ermöglichen es, den Konsens in linearer Zeit in Zahlen zu erreichen der Teilnehmer (siehe z. B. [4]), ist der Overhead pro Block immer noch spürbar; 2. Es ist nicht möglich, dass alle Netzwerkteilnehmer am BFT teilnehmen. Konsens pro Block, daher erreicht normalerweise nur eine zufällig ausgewählte Teilmenge der Teilnehmer den Konsens. Eine zufällig ausgewählte Menge kann im Prinzip sein: adaptiv korrumpiert, und theoretisch kann eine Abzweigung erstellt werden. Das System Beides muss modelliert werden, um für ein solches Ereignis bereit zu sein, und somit still haben neben dem BFT-Konsens eine Fork-Choice-Regel oder sind so konzipiert, dass sie geschlossen werden in einem solchen Fall niedergeschlagen. Es ist erwähnenswert, dass einige Designs, wie z Algorand [5], reduzieren die Wahrscheinlichkeit einer adaptiven Korruption erheblich. 3. Am wichtigsten ist, dass das System blockiert, wenn 1 3 oder mehr aller Teilnehmer sind offline. Daher kann jeder vorübergehende Netzwerkfehler oder eine Netzwerkaufteilung das System vollständig zum Stillstand bringen. Im Idealfall muss das System weiterhin in der Lage sein funktionieren, solange mindestens die Hälfte der Teilnehmer online ist (am schwersten). Kettenbasierte Protokolle funktionieren auch dann weiter, wenn weniger als die Hälfte der Teilnehmer online ist, aber die Zweckmäßigkeit dieser Eigenschaft ist umstrittener innerhalb der Gemeinschaft). Ein Hybridmodell, bei dem der verwendete Konsens am stärksten ist Kette, aber einige Blöcke werden regelmäßig mit einem BFT Finalitäts-Gadget finalisiert, um die Vorteile beider Modelle beizubehalten. Solche BFT Endgültigkeits-Gadgets sind Casper FFG [6] verwendet in Ethereum 2.0 8, Casper CBC (siehe https://vitalik. ca/general/2018/12/05/cbc_casper.html) und GRANDPA (siehe https:// medium.com/polkadot-network/d08a24a021b5) verwendet in Polkadot. Nightshade verwendet den stärksten Kettenkonsens. Insbesondere wenn ein Block Der Produzent erzeugt einen Block (siehe Abschnitt 3.3), von dem er Signaturen sammeln kann andere Blockproduzenten und validators, die den vorherigen Block bestätigen. Siehe Abschnitt 3.8 für Einzelheiten, wie eine so große Anzahl von Signaturen aggregiert wird. Das Gewicht 8Sehen Sie sich auch die Whiteboard-Sitzung mit Justin Drake an, um einen detaillierten Überblick über Casper zu erhalten FFG und wie es in den GHOST-Konsens über die schwerste Kette integriert ist, finden Sie hier: https://www. youtube.com/watch?v=S262StTwkmoeines Blocks ist dann der kumulative Einsatz aller Unterzeichner, deren Unterschriften vorhanden sind im Block enthalten. Das Gewicht einer Kette ist die Summe der Blockgewichte. Zusätzlich zum schwersten Kettenkonsens verwenden wir ein Finalitäts-Gadget, das verwendet die Bescheinigungen zur Fertigstellung der Blöcke. Um die Komplexität des Systems zu reduzieren, Wir verwenden ein Finalitäts-Gadget, das die Fork-Choice-Regel in keiner Weise beeinflusst. und führt stattdessen nur zusätzliche Slashing-Bedingungen ein, so dass einmal ein Block vorhanden ist Durch das Finalitäts-Gadget finalisiert, ist eine Abzweigung unmöglich, es sei denn, es handelt sich um einen sehr großen Prozentsatz des Gesamteinsatzes wird gekürzt. Casper CBC ist so ein Endgültigkeits-Gadget, und wir derzeit Modell mit Blick auf Casper CBC. Wir arbeiten auch an einem separaten BFT-Protokoll namens TxFlow. Zur Zeit von Beim Schreiben dieses Dokuments ist unklar, ob TxFlow anstelle von Casper verwendet wird CBC. Wir stellen jedoch fest, dass die Wahl des Endgültigkeits-Gadgets weitgehend orthogonal zum Rest des Designs ist. 3.3 Blockproduktion In Nightshade gibt es zwei Rollen: Blockproduzenten und validators. Auf jeden Fall Punkt enthält das System w Blockproduzenten, w = 100 in unseren Modellen und wv validators, in unserem Modell v = 100, wv = 10.000. Das System ist Proof-of-Stake, Dies bedeutet, dass sowohl Blockproduzenten als auch validators über eine gewisse Anzahl interner verfügen Währung (bezeichnet als „tokens“) für einen Zeitraum gesperrt, der weit über den hinausgeht Zeit, die sie mit der Erfüllung ihrer Aufgaben zum Aufbau und zur Validierung der Kette verbringen. Wie bei allen Proof-of-Stake-Systemen sind nicht alle W-Blockproduzenten und nicht Alle wv validators sind unterschiedliche Entitäten, da dies nicht erzwungen werden kann. Jeder der w-Blockproduzenten und die wv validators haben jedoch eine separate Pfahl. Das System enthält n Shards, in unserem Modell ist n = 1000. Wie erwähnt in Abschnitt 3.1: In Nightshade gibt es keine Shard-Ketten, stattdessen erstellen alle Blockproduzenten und validators ein einziges blockchain, das wir als das bezeichnen Hauptkette. Der Zustand der Hauptkette ist in n Shards und jeden Block aufgeteilt Produzent und validator haben zu jedem Zeitpunkt nur eine Teilmenge von lokal heruntergeladen der Zustand, der einer Teilmenge der Shards entspricht, und nur verarbeiten und Validierung von Transaktionen, die diese Teile des Staates betreffen. Um ein Blockproduzent zu werden, sperrt ein Teilnehmer des Netzwerks einige große Blöcke Betrag von tokens (ein Einsatz). Die Wartung des Netzwerks erfolgt in Epochen, wobei eine Epoche ein Zeitraum in der Größenordnung von Tagen ist. Die Teilnehmer mit den w größten Einsätzen zu Beginn einer bestimmten Epoche sind der Block Produzenten für diese Epoche. Jedem Blockproduzenten sind SW-Shards zugewiesen (z. B sw = 40, was sww/n = 4 Blockproduzenten pro Shard ergeben würde. Der Block Der Produzent lädt den Status des Shards herunter, dem er vor der Epoche zugewiesen ist beginnt und sammelt im Laufe der Epoche Transaktionen, die sich auf diesen Shard auswirken. und wendet sie auf den Staat an. Für jeden Block b in der Hauptkette und für jeden Shard s gibt es einen davon s Blockproduzenten zugewiesen, die für die Produktion des Teils von b verantwortlich sind zur Scherbe. Der Teil von b, der sich auf Shard s bezieht, wird als Chunk bezeichnet und enthält die Liste der Transaktionen für den Shard, die in b aufgenommen werden sollen, sowie das MerkleWurzel des resultierenden Zustands. b wird letztendlich nur einen sehr kleinen Header von enthalten der Chunk, nämlich die Merkle-Wurzel aller angewendeten Transaktionen (siehe Abschnitt 3.7.1 für genaue Details) und die Merkle-Wurzel des Endzustands. Im weiteren Verlauf des Dokuments beziehen wir uns häufig auf den Blockproduzenten Das ist dafür verantwortlich, zu einem bestimmten Zeitpunkt einen Chunk für einen bestimmten Shard zu produzieren als Chunk-Produzent. Der Chunk-Produzent ist immer einer der Blockproduzenten. Die Blockproduzenten und die Chunk-Produzenten rotieren jeden Block entsprechend nach einem festen Zeitplan. Die Blockproduzenten haben einen Auftrag und produzieren wiederholt Blöcke in dieser Reihenfolge. Z.B. wenn es 100 Blockproduzenten gibt, der erste Block Der Hersteller ist für die Produktion der Blöcke 1, 101, 201 usw. verantwortlich, der zweite verantwortlich für die Produktion von 2, 102, 202 usw.). Da die Chunk-Produktion im Gegensatz zur Blockproduktion eine Wartung erfordert den Status, und für jeden Shard behalten nur sww/n-Blockproduzenten den Status bei Pro Shard rotieren dementsprechend nur die SWW/N-Blockproduzenten, um sie zu erstellen Brocken. Z.B. mit den oben genannten Konstanten mit vier zugewiesenen Blockproduzenten Jeder Shard und jeder Blockproduzent erstellt alle vier Blöcke einmal Chunks. 3.4 Sicherstellung der Datenverfügbarkeit Um die Datenverfügbarkeit sicherzustellen, verwenden wir einen ähnlichen Ansatz wie Polkadot beschrieben in Abschnitt 2.5.3. Sobald ein Blockproduzent einen Block produziert, erstellt er ihn eine löschcodierte Version davon mit einem optimalen (w, ⌊w/6 + 1⌋) Blockcode des Brocken. Anschließend senden sie einen Teil des löschcodierten Blocks (wir nennen solche Teile). Chunk-Teile oder nur Teile) an jeden Blockproduzenten. Wir berechnen einen Merkle-Baum, der alle Teile wie die Blätter und die enthält Der Header jedes Blocks enthält die Merkle-Wurzel dieses Baums. Die Teile werden über Onepart-Nachrichten an die validators gesendet. Jede solche Nachricht enthält den Chunk-Header, die Ordnungszahl des Teils und den Teilinhalt. Die Die Nachricht enthält auch die Signatur des Blockproduzenten, der sie erstellt hat Chunk und den Merkle-Pfad, um zu beweisen, dass der Teil dem Header entspricht und wird vom richtigen Blockproduzenten produziert. Sobald ein Blockproduzent einen Hauptkettenblock erhält, prüft er zunächst, ob dies der Fall ist Für jeden im Block enthaltenen Block gibt es einteilige Nachrichten. Wenn nicht, die Sperre wird erst verarbeitet, wenn die fehlenden Onepart-Nachrichten abgerufen wurden. Sobald alle einteiligen Nachrichten empfangen wurden, ruft der Blockproduzent die ab Die restlichen Teile werden von den Peers abgezogen und die Chunks rekonstruiert, die sie enthalten der Staat. Der Blockproduzent verarbeitet keinen Hauptkettenblock, wenn es sich um mindestens einen handelt Wenn ein im Block enthaltener Chunk nicht über die entsprechende Onepart-Nachricht verfügt, oder wenn für mindestens einen Shard, für den sie den Status aufrechterhalten, dies nicht der Fall ist den gesamten Block rekonstruieren. Damit ein bestimmter Block verfügbar ist, reicht es aus, dass ⌊w/6⌋+1 des Blocks Produzenten haben ihre Teile und bedienen sie. Also solange die Zahl der böswillige Akteure überschreiten nicht ⌊w/3⌋keine Kette, die mehr als einen halben Block hat Hersteller, die es bauen, können nicht verfügbare Teile haben.Abbildung 17: Jeder Block enthält einen oder keinen Chunk pro Shard und jeden Chunk ist löschcodiert. Jeder Teil des löschcodierten Blocks wird an eine bestimmte Adresse gesendet Blockproduzent über eine spezielle Onepart-Nachricht 3.4.1 Umgang mit faulen Blockproduzenten Wenn ein Blockproduzent einen Block hat, für den eine Onepart-Nachricht fehlt, wird er Vielleicht entscheiden Sie sich trotzdem dafür, ihn zu signieren, denn wenn der Block am Ende in der Kette landet, ist er es maximiert die Belohnung für den Blockproduzenten. Für den Block besteht kein Risiko Der Blockproduzent war nicht der einzige Blockproduzent, da es später unmöglich ist, zu beweisen, dass der Blockproduzent ihn nicht hatte die einteilige Nachricht. Um dies zu beheben, machen wir jeden Chunk zum Produzenten, wenn wir den Chunk erstellen Wählen Sie eine Farbe (Rot oder Blau) für jeden Teil des zukünftigen codierten Blocks und speichern Sie ihn die Bitmaske der zugewiesenen Farbe im Block, bevor er codiert wird. Jeweils ein Teil Die Nachricht enthält dann die dem Teil zugewiesene Farbe, und die Farbe wird verwendet, wenn Berechnen der Merkle-Wurzel der codierten Teile. Wenn der Chunk-Produzent abweicht Aus dem Protokoll lässt sich dies leicht beweisen, da dies bei der Merkle-Wurzel nicht der Fall ist entsprechen einteiligen Nachrichten oder den Farben in den einteiligen Nachrichten die der Merkle-Wurzel entsprechen, stimmt nicht mit der Maske im Block überein. Wenn ein Blockproduzent einen Block anmeldet, fügt er eine Bitmaske aller Blöcke hinzu rote Teile erhielten sie für die im Block enthaltenen Chunks. Veröffentlichung einer Eine falsche Bitmaske ist ein streichbares Verhalten. Wenn ein Blockproduzent keine erhalten hat Bei einer einzelnen Nachricht haben sie keine Möglichkeit, die Farbe der Nachricht zu kennen, und Daher besteht eine Wahrscheinlichkeit von 50 %, dass sie gekürzt werden, wenn sie versuchen, das Dokument blind zu unterschreiben blockieren. 3.5 Antrag auf Staatsübergang Die Chunk-Produzenten wählen lediglich aus, welche Transaktionen in den Chunk aufgenommen werden sollen Wenden Sie den Zustandsübergang nicht an, wenn sie einen Block erzeugen. Dementsprechend
Der Chunk-Header enthält die Merkle-Wurzel des merkelisierten Zustands wie zuvor Die Transaktionen im Block werden angewendet. Die Transaktionen werden nur angewendet, wenn ein vollständiger Block den Block enthält verarbeitet wird. Ein Teilnehmer bearbeitet einen Block nur, wenn 1. Der vorherige Block wurde empfangen und verarbeitet; 2. Für jeden Block behält der Teilnehmer nicht den Status bei, den er hat habe die einteilige Nachricht gesehen; 3. Für jeden Block behält der Teilnehmer den Status bei, den er hat volles Stück. Sobald der Block verarbeitet wird, für jeden Shard, für den der Teilnehmer zuständig ist behält den Zustand bei, wendet die Transaktionen an und berechnet den neuen Zustand ab dem Zeitpunkt, an dem die Transaktionen angewendet wurden, und sind danach zur Produktion bereit die Chunks für den nächsten Block, wenn sie einem Shard zugewiesen sind, da sie dies getan haben die Merkle-Wurzel des neuen merkelisierten Staates. 3.6 Shardübergreifende Transaktionen und Belege Wenn eine Transaktion mehr als einen Shard betreffen muss, muss sie nacheinander erfolgen wird in jedem Shard separat ausgeführt. Die vollständige Transaktion wird an den ersten Shard gesendet betroffen, und sobald die Transaktion im Chunk für diesen Shard enthalten ist, und Wird angewendet, nachdem der Block in einen Block eingefügt wurde, wird eine sogenannte Quittung generiert Transaktion, die an den nächsten Shard weitergeleitet wird, in dem die Transaktion ausgeführt werden muss ausgeführt werden. Wenn weitere Schritte erforderlich sind, erfolgt die Ausführung der Empfangstransaktion generiert eine neue Belegtransaktion und so weiter. 3.6.1 Lebensdauer der Quittungstransaktion Es ist wünschenswert, dass die Empfangstransaktion in dem Block angewendet wird, der unmittelbar auf den Block folgt, in dem sie generiert wurde. Die Quittungstransaktion ist nur generiert, nachdem der vorherige Block empfangen und von Blockproduzenten angewendet wurde die den ursprünglichen Shard verwalten und zum Zeitpunkt des bekannt sein müssen Der Block für den nächsten Block wird von den Blockproduzenten des Ziels erstellt Scherbe. Daher muss der Empfang vom Quell-Shard an den übermittelt werden Ziel-Shard in dem kurzen Zeitrahmen zwischen diesen beiden Ereignissen. Sei A der zuletzt produzierte Block, der eine Transaktion t enthält, die eine Quittung r generiert. Sei B der nächste produzierte Block (d. h. ein Block, der A als hat). sein vorheriger Block), den wir r enthalten wollen. Lass es in der Scherbe a und r sein in der Scherbe b. Die Lebensdauer des Belegs, ebenfalls in Abbildung 18 dargestellt, ist wie folgt: Erstellen und Aufbewahren der Belege. Der Chunk-Produzenten-CPA für Shard a empfängt den Block A, wendet die Transaktion t an und generiert die Quittung r. cpa Anschließend speichert es alle derart erstellten Belege in seinem indizierten internen persistenten Speicher nach der Quell-Shard-ID.Verteilen der Quittungen. Sobald CPA bereit ist, den Chunk zu produzieren Wenn Sie Shard a für Block B verwenden, rufen sie alle Belege ab, die durch die Anwendung der Transaktionen von Block A für Shard a generiert wurden, und fügen sie in den Block für Shrad ein a in Block B. Sobald ein solcher Block generiert ist, erzeugt cpa seinen Löschcode Version und alle zugehörigen Onepart-Nachrichten. cpa weiß, welche Blockproduzenten den vollständigen Status für welche Shards beibehalten. Für einen bestimmten Blockproduzenten bp cpa umfasst die Einnahmen, die aus der Anwendung von Transaktionen in Block A resultierten für Shard a, der einen der Shards hat, die bp als Ziel interessieren in der einteiligen Nachricht, als sie den Block für Shard a in Block B verteilten (siehe Abbildung 17, die die in der Onepart-Nachricht enthaltenen Quittungen zeigt). Erhalt der Quittungen. Denken Sie daran, dass die Teilnehmer (sowohl Blockproduzenten als auch validators) Blöcke erst verarbeiten, wenn sie einteilige Nachrichten haben für jeden im Block enthaltenen Block. Wenn also ein bestimmter Teilnehmer den Block B anwendet, verfügt er über alle entsprechenden Onepart-Nachrichten Chunks in B, und somit verfügen sie über alle eingehenden Belege, die die Shards enthalten Der Teilnehmer behält den Status als Ziel bei. Bei der Anwendung der Beim Zustandsübergang für einen bestimmten Shard wendet der Teilnehmer beide Quittungen an dass sie für den Shard in den Onepart-Nachrichten sowie allen gesammelt haben die im Chunk selbst enthaltenen Transaktionen. Abbildung 18: Die Lebensdauer einer Empfangstransaktion 3.6.2 Umgang mit zu vielen Belegen Es ist möglich, dass die Anzahl der Belege, die auf einen bestimmten Shard in einem abzielen Ein bestimmter Block ist zu groß, um verarbeitet zu werden. Betrachten Sie zum Beispiel Abbildung 19, in wobei jede Transaktion in jedem Shard eine Quittung generiert, die auf Shard 1 abzielt. Bis zum nächsten Block beträgt die Anzahl der Belege, die Shard 1 verarbeiten muss vergleichbar mit der Last, die alle Scherben zusammen während der Handhabung verarbeitet haben den vorherigen Block.
Abbildung 19: Wenn alle Belege auf denselben Shard abzielen, ist dies möglicherweise nicht der Fall die Fähigkeit, sie zu verarbeiten Um dieses Problem anzugehen, verwenden wir eine Technik, die der in QuarkChain 9 verwendeten ähnelt. Konkret gilt für jeden Shard der letzte Block B und der letzte Shard darin Es wird der Block erfasst, aus dem die Belege übernommen wurden. Wenn der neue Shard ist erstellt, die Quittung wird in der Reihenfolge zuerst aus den verbleibenden Shards in B angewendet, und dann in Blöcken, die auf B folgen, bis der neue Block voll ist. Unter normal Bei ausgeglichener Belastung kommt es in der Regel zu allen Einnahmen angewendet wird (und somit wird der letzte Shard des letzten Blocks aufgezeichnet jedes Stück), aber zu Zeiten, in denen die Last nicht ausgeglichen ist, und ein bestimmtes Da Shard überproportional viele Belege erhält, ist dies mit dieser Technik möglich unter Einhaltung der Beschränkungen für die Anzahl der enthaltenen Transaktionen verarbeitet werden. Beachten Sie, dass die Verzögerung abnimmt, wenn eine solche unausgeglichene Belastung über einen längeren Zeitraum anhält Die Belegerstellung bis zur Anwendung kann unbegrenzt weiter wachsen. Eins Eine Möglichkeit, das Problem zu lösen, besteht darin, jede Transaktion zu verwerfen, die eine Quittung für a erstellt Shard, dessen Verarbeitungsverzögerung eine bestimmte Konstante überschreitet (z. B. eine Epoche). Betrachten Sie Abbildung 20. Durch Block B kann der Shard 4 nicht alle Belege verarbeiten. es verarbeitet also nur Quittungsursprünge von bis zu Shard 3 in Block A und zeichnet es auf. In Block C sind die Belege bis Shard 5 in Block B enthalten, und Dann holt der Shard bei Block D auf und verarbeitet alle verbleibenden Belege Block B und alle Belege aus Block C. 3.7 Chunks-Validierung Ein für einen bestimmten Shard erstellter Chunk (oder ein für eine bestimmte Shard-Kette im Modell mit Shard-Ketten erstellter Shard-Block) kann nur von validiert werden 9Sehen Sie sich hier die Whiteboard-Folge mit QuarkChain an: https://www.youtube.com/watch? v=opEtG6NM4x4, in dem unter anderem der Ansatz für Cross-Shard-Transaktionen diskutiert wird DingeAbbildung 20: Verzögerte Belegverarbeitung Teilnehmer, die den Staat aufrechterhalten. Sie können Blockproduzenten sein, validators, oder nur externe Zeugen, die den Status heruntergeladen und den Shard darin validiert haben in dem sie Vermögenswerte speichern. In diesem Dokument gehen wir davon aus, dass die Mehrheit der Teilnehmer nicht speichern kann der Staat für einen großen Teil der Scherben. Es ist jedoch erwähnenswert, dass es Shard-blockchains gibt, die unter der Annahme entworfen wurden, dass Die meisten Teilnehmer verfügen über die Kapazität, den Zustand zu speichern und die meisten davon zu validieren die Shards, wie zum Beispiel QuarkChain. Da nur ein Bruchteil der Teilnehmer den Status hat, den Shard zu validieren Chunks ist es möglich, adaptiv nur die Teilnehmer zu korrumpieren, die das haben Zustand ändern und einen ungültigen Zustandsübergang anwenden. Es wurden mehrere Sharding-Designs vorgeschlagen, die alle paar validators abtasten Tage und innerhalb eines Tages jeder Block in der Shard-Kette, der mehr als 2/3 hat der diesem Shard zugewiesenen Signaturen der validators werden sofort berücksichtigt endgültig. Mit einem solchen Ansatz muss ein adaptiver Gegner nur 2n/3+1 korrumpieren der validators in einer Shard-Kette, um einen ungültigen Zustandsübergang anzuwenden, der, Auch wenn es wahrscheinlich schwer zu bewerkstelligen ist, ist das Sicherheitsniveau für die Öffentlichkeit nicht ausreichend blockchain. Wie in Abschnitt 2.3 besprochen, besteht der übliche Ansatz darin, nach der Erstellung eines Blocks für jeden Teilnehmer, der über den Status (ob) verfügt, ein bestimmtes Zeitfenster einzuräumen es ist ein Blockproduzent, ein validator oder ein externer Beobachter), um seine Gültigkeit in Frage zu stellen. Solche Teilnehmer werden Fischer genannt. Damit ein Fischer es kann Um einen ungültigen Block anzufechten, muss sichergestellt werden, dass ein solcher Block verfügbar ist sie. Die Datenverfügbarkeit in Nightshade wird in Abschnitt 3.4 erläutert. Sobald in Nightshade ein Block erstellt wurde, wurden die Chunks nicht validiert irgendjemand außer dem eigentlichen Chunk-Produzenten. Insbesondere der Blockproduzent schlug vor, dass der Block natürlich nicht den Status für die meisten Shards hatte, undkonnte die Chunks nicht validieren. Wenn der nächste Block produziert wird, enthält er Attestierungen (siehe Abschnitt 3.2) mehrerer Blockproduzenten und validators, aber da die Mehrheit der Blockproduzenten und validators den Status nicht aufrechterhalten Auch bei den meisten Shards sammelt ein Block mit nur einem ungültigen Chunk deutlich mehr als die Hälfte der Attestierungen und bleibt weiterhin am schwersten Kette. Um dieses Problem zu beheben, gestatten wir jedem Teilnehmer, den Status von beizubehalten Ein Shard, um in der Kette eine Herausforderung für jeden darin erzeugten ungültigen Chunk einzureichen Scherbe. 3.7.1 Staatliche Gültigkeitsherausforderung Sobald ein Teilnehmer feststellt, dass ein bestimmter Block ungültig ist, muss er einen Beweis dafür erbringen, dass der Block ungültig ist. Da die Mehrheit der Netzwerkteilnehmer den Zustand für den Shard, in dem sich der ungültige Chunk befindet, nicht aufrechterhalten Wenn der Beweis erstellt wird, muss er über ausreichende Informationen verfügen, um den Block zu bestätigen ungültig, ohne den Staat zu haben. Wir legen einen Grenzwert Ls für die Statusmenge (in Bytes) fest, die eine einzelne Transaktion umfasst kann kumulativ lesen oder schreiben. Jede Transaktion, die mehr als Ls berührt Zustand gilt als ungültig. Erinnern Sie sich aus Abschnitt 3.5 daran, dass der Chunk In einem bestimmten Block enthält B nur die anzuwendenden Transaktionen, jedoch nicht die neue Staatswurzel. Der im Block in Block B enthaltene Statusstamm ist der Status root, bevor Sie solche Transaktionen anwenden, aber nachdem Sie die Transaktionen angewendet haben der letzte Block im selben Shard vor dem Block B. Ein böswilliger Akteur Der Wunsch, einen ungültigen Zustandsübergang anzuwenden, würde einen falschen Zustandsstamm beinhalten in Block B entspricht das nicht der Zustandswurzel, die sich aus der Anwendung ergibt die Transaktionen im vorherigen Block. Wir erweitern die Informationen, die ein Chunk-Produzent in den Chunk einfügt. Anstatt nur den Status einzubeziehen, nachdem alle Transaktionen angewendet wurden, wird dieser stattdessen angezeigt Enthält eine Statuswurzel, nachdem jeder zusammenhängende Satz von Transaktionen angewendet wurde Lesen und schreiben Sie gemeinsam Ls Zustandsbytes. Mit diesen Informationen für die Fischer stellt eine Herausforderung dar, dass ein Zustandsübergang falsch angewendet wird reicht aus, um den ersten solchen ungültigen Zustandsstamm zu finden, und umfasst nur Ls Bytes davon Staaten, die von den Transaktionen zwischen dem letzten Stammstaat (der war) betroffen sind gültig) und die aktuelle Statuswurzel mit den Merkle-Beweisen. Dann jeder Teilnehmer kann die Transaktionen im Segment validieren und bestätigen, dass der Block vorhanden ist ungültig. Das Gleiche gilt, wenn der Blockproduzent versucht hat, lesende Transaktionen einzuschließen und mehr als Ls Statusbytes schreiben, für die Herausforderung reicht es aus, sie einzuschließen Die ersten Ls-Bytes berührt es mit den Merkle-Beweisen, was ausreichen wird Wenden Sie die Transaktionen an und bestätigen Sie, dass es einen Moment gibt, in dem ein Versuch dazu erfolgt Das Lesen oder Schreiben von Inhalten über Ls Bytes hinaus erfolgt.
3.7.2 Fischer und schnelle Cross-Shard-Transaktionen Wie in Abschnitt 2.3 besprochen, nehmen wir einmal an, dass die Shard-Chunks (oder Shard Blöcke im Modell mit Shard-Ketten) können ungültig sein und eine Herausforderung darstellen Dies wirkt sich negativ auf die Endgültigkeit und damit auf die Shard-übergreifende Kommunikation aus. In Insbesondere kann der Ziel-Shard einer Cross-Shard-Transaktion nicht sicher sein Der ursprüngliche Shard-Block oder -Block ist endgültig, bis der Herausforderungszeitraum abgelaufen ist (siehe Abbildung 21). Abbildung 21: Warten Sie den Herausforderungszeitraum ab, bevor Sie eine Quittung beantragen Die Art und Weise, es so anzugehen, dass die Cross-Shard-Transaktionen möglich sind Instantenious bedeutet, dass der Ziel-Shard nicht auf den Herausforderungszeitraum warten muss Nachdem die Quell-Shard-Transaktion veröffentlicht wurde, wenden Sie die Empfangstransaktion an sofort ausführen, aber dann den Ziel-Shard zusammen mit der Quelle zurücksetzen Shard, wenn sich später herausstellt, dass der ursprüngliche Chunk oder Block ungültig ist (siehe Abbildung). 22). Dies gilt ganz natürlich für das Nightshade-Design, in dem die Scherbe enthalten ist Ketten sind nicht unabhängig, stattdessen werden alle Shard-Blöcke veröffentlicht zusammen im selben Hauptkettenblock. Wenn sich herausstellt, dass ein Block ungültig ist, wird der Der gesamte Block mit diesem Block wird als ungültig betrachtet, ebenso alle darauf aufbauenden Blöcke oben drauf. Siehe Abbildung 23. Beide oben genannten Ansätze bieten Atomizität unter der Annahme, dass die Herausforderung besteht Der Zeitraum ist ausreichend lang. Wir verwenden den letzteren Ansatz, da die Bereitstellung schneller Cross-Shard-Transaktionen unter normalen Umständen die Unannehmlichkeiten überwiegt Der Ziel-Shard wird aufgrund eines ungültigen Zustandsübergangs in einem von ihnen zurückgesetzt die Quellsplitter, was ein äußerst seltenes Ereignis ist. 3.7.3 validators werden ausgeblendet Das Vorhandensein der Herausforderungen verringert bereits die Wahrscheinlichkeit erheblich Adaptive Korruption, da ein Block mit einem ungültigen Zustandsübergangsposten abgeschlossen werden mussAbbildung 22: Belege sofort anwenden und das Ziel zurücksetzen Kette, wenn die Quellkette einen ungültigen Block hatte Abbildung 23: Fischer-Herausforderung in Nightshade Der Herausforderungszeitraum, den der adaptive Gegner benötigt, um alle Teilnehmer zu korrumpieren die den Zustand des Shards beibehalten, einschließlich aller validators. Die Wahrscheinlichkeit eines solchen Ereignisses abzuschätzen ist äußerst komplex, da nein sharded blockchain ist schon so lange aktiv, dass ein solcher Angriff versucht werden kann. Wir argumentieren, dass die Wahrscheinlichkeit zwar äußerst gering, aber immer noch ausreichend ist groß für ein System, von dem erwartet wird, dass es mehrere Millionen Transaktionen ausführt Führen Sie ein weltweites Finanzgeschäft. Es gibt zwei Hauptgründe für diesen Glauben: 1. Die meisten validators der Proof-of-Stake-Ketten und Miner der
Der Anreiz für Proof-of-Work-Ketten besteht in erster Linie aus finanziellen Vorteilen. Wenn Ein adaptiver Gegner bietet ihnen mehr Geld als die erwartete Rendite Wenn man ehrlich vorgeht, kann man davon ausgehen, dass es viele validators gibt werde das Angebot annehmen. 2. Viele Unternehmen führen die Validierung von Proof-of-Stake-Ketten professionell durch Es wird erwartet, dass ein großer Prozentsatz der Anteile an jeder Kette liegen wird von solchen Einheiten. Die Anzahl solcher Entitäten ist für eine ausreichend klein adaptiver Gegner, um die meisten von ihnen persönlich kennenzulernen und zu haben gutes Verständnis für ihre Neigung, korrumpiert zu werden. Wir gehen einen Schritt weiter, um die Wahrscheinlichkeit der adaptiven Korruption zu verringern, indem wir verbergen, welche validators welchem Shard zugewiesen sind. Die Idee ist entfernt ähnlich der Art und Weise, wie Algorand [5] validators verbirgt. Es ist wichtig zu beachten, dass selbst wenn die validators verborgen sind, wie in Algorand oder wie unten beschrieben, ist die adaptive Korruption theoretisch immer noch möglich. Während Der adaptive Gegner kennt die Teilnehmer nicht, die erstellen oder validieren Ob ein Block oder ein Brocken, die Teilnehmer wissen selbst, dass sie etwas leisten werden eine solche Aufgabe erfüllen und einen kryptografischen Beweis dafür haben. So kann der Gegner Machen Sie ihre Korruptionsabsicht öffentlich und zahlen Sie an jeden Teilnehmer, der dies bereitstellt so ein kryptografischer Beweis. Wir stellen jedoch fest, dass der Gegner dies nicht tut Sie kennen die validators, die dem Shard zugewiesen sind, den sie beschädigen möchten haben keine andere Wahl, als ihre Absicht, einen bestimmten Shard zu beschädigen, zu verbreiten die gesamte Gemeinschaft. An diesem Punkt ist es für jeden Ehrlichen wirtschaftlich vorteilhaft Der Teilnehmer muss einen vollständigen Knoten hochfahren, der diesen Shard validiert, da ein Hoch vorliegt Wahrscheinlichkeit, dass ein ungültiger Block in diesem Shard erscheint, was eine Gelegenheit dazu darstellt Erstellen Sie eine Herausforderung und sammeln Sie die zugehörige Belohnung. Um die validators, die einem bestimmten Shard zugewiesen sind, nicht preiszugeben, tun wir dies Folgendes (siehe Abbildung 24): Verwenden Sie VRF, um die Zuweisung zu erhalten. Zu Beginn jeder Epoche validator verwendet eine VRF, um eine Bitmaske der Shards abzurufen, denen validator zugewiesen ist. Die Bitmaske jedes validator wird Sw-Bits haben (Definition siehe Abschnitt 3.3). von Sw). Der validator ruft dann den Status der entsprechenden Shards ab und Während der Epoche werden für jeden empfangenen Block die entsprechenden Blöcke validiert zu den Shards, denen validator zugewiesen ist. Melden Sie sich in Blöcken statt in Blöcken an. Da die Shard-Zuweisung verborgen ist, kann validator keine Chunks anmelden. Stattdessen wird immer das Ganze unterschrieben blockieren, sodass nicht verraten wird, welche Shards validiert werden. Insbesondere wenn validator einen Block empfängt und alle Blöcke validiert, erstellt er entweder eine Nachricht Dies bestätigt, dass alle Chunks in allen Shards, denen validator zugewiesen ist, vorhanden sind gültig (ohne in irgendeiner Weise anzugeben, um welche Shards es sich handelt) oder eine Nachricht darüber enthält einen Beweis für einen ungültigen Zustandsübergang, wenn ein Block ungültig ist. Siehe die Einzelheiten zur Aggregation solcher Nachrichten finden Sie in Abschnitt 3.8, in Abschnitt 3.7.4 die Details, wie verhindert werden kann, dass validators Nachrichten von huckepack nehmen andere validators und Abschnitt 3.7.5 für Einzelheiten zur Belohnung und Bestrafung validators, falls tatsächlich eine erfolgreiche ungültige Zustandsübergangsherausforderung stattfindet.Abbildung 24: Die validators in Nightshade verbergen 3.7.4 Commit-Reveal Eines der häufigsten Probleme mit validators besteht darin, dass ein validator das Herunterladen des Status und die tatsächliche Validierung der Chunks und Blöcke überspringen kann und stattdessen Beobachten Sie das Netzwerk, sehen Sie, was die anderen validators einreichen, und wiederholen Sie dies Nachrichten. Ein validator, der einer solchen Strategie folgt, bietet keinen Mehrwert Sicherheit für das Netzwerk, kassiert aber Belohnungen. Eine übliche Lösung für dieses Problem besteht darin, für jeden validator einen Beweis bereitzustellen dass sie den Block tatsächlich validiert haben, beispielsweise durch Bereitstellung einer eindeutigen Ablaufverfolgung Die Anwendung des Zustandsübergangs ist zwar nicht möglich, aber solche Nachweise erhöhen die Kosten erheblich der Validierung. Abbildung 25: Commit-Enthüllung
Stattdessen veranlassen wir, dass die validators zuerst auf das Validierungsergebnis übertragen werden (entweder die Nachricht, die die Gültigkeit der Chunks bestätigt, oder der Beweis einer Ungültigkeit Warten Sie einen bestimmten Zeitraum und zeigen Sie erst dann das tatsächliche Validierungsergebnis an, wie in Abbildung 25 dargestellt. Der Festschreibungszeitraum überschneidet sich nicht mit der Enthüllungszeitraum, und daher kann ein fauler validator keine ehrlichen validators kopieren. Darüber hinaus, wenn ein unehrlicher validator sich zu einer Nachricht verpflichtet hat, die dies bestätigt Gültigkeit der zugewiesenen Chunks, und mindestens ein Chunk war ungültig, sobald dies der Fall ist gezeigt, dass der Block ungültig ist, kann validator den Schrägstrich nicht vermeiden, da Wie wir in Abschnitt 3.7.5 zeigen, ist dies der einzige Weg, in einer solchen Situation nicht aufgeschlitzt zu werden besteht darin, eine Nachricht zu präsentieren, die einen Beweis für den ungültigen Zustandsübergang enthält entspricht dem Commit. 3.7.5 Umgang mit Herausforderungen Wie oben erläutert, sobald ein validator einen Block mit einem ungültigen Block empfängt, Sie bereiten zunächst einen Beweis für den ungültigen Zustandsübergang vor (siehe Abschnitt 3.7.1) und dann verpflichten Sie sich zu einem solchen Beweis (siehe 3.7.4) und offenbaren Sie nach einiger Zeit die Herausforderung. Sobald die aufgedeckte Herausforderung in einen Block aufgenommen wird, passiert Folgendes: 1. Alle Zustandsübergänge, die von dem Block aus stattgefunden haben, der die enthält ungültiger Block, bis der Block, in dem die aufgedeckte Herausforderung enthalten ist, abgerufen wird für nichtig erklärt. Der Zustand vor dem Block, der die offenbarte Herausforderung enthält gilt als derselbe wie der Zustand vor dem enthaltenen Block der ungültige Block. 2. Innerhalb einer bestimmten Zeitspanne muss jeder validator seine Bitmaske offenlegen der Shards, die sie validieren. Da die Bitmaske über ein VRF erstellt wird, wenn Sie wurden dem Shard zugewiesen, der den ungültigen Zustandsübergang „they“ hatte kann nicht umhin, es zu enthüllen. Alle validator, bei denen die Bitmaske nicht angezeigt wird Es wird davon ausgegangen, dass es dem Shard zugewiesen ist. 3. Jeder validator, der nach diesem Zeitraum dem Shard zugeordnet ist, das hat zu einem Validierungsergebnis für den Block geführt, der das enthält ungültiger Block und das ergab keinen Beweis für einen ungültigen Zustandsübergang das ihrem Commit entspricht, wird gestrichen. 4. Jeder validator erhält eine neue Shard-Zuweisung und eine neue Epoche wird geplant um nach einiger Zeit zu beginnen, die ausreicht, damit alle validators das herunterladen können Zustand, wie in Abbildung 26 dargestellt. Beachten Sie, dass die validators ab dem Moment die ihnen zugewiesenen Shards offenlegen Bis zum Beginn der neuen Epoche ist die Sicherheit des Systems verringert, da die Die Shard-Zuordnung wird enthüllt. Die Teilnehmer des Netzwerks müssen es behalten Beachten Sie dies bei der Nutzung des Netzwerks in diesem Zeitraum. 3.8 Signaturaggregation Damit ein System mit Hunderten von Shards sicher funktioniert, möchten wir Folgendes haben: Größenordnung von 10.000 oder mehr validators. Wie in Abschnitt 3.7 besprochen, wollen wir jedesAbbildung 26: Die Herausforderung meistern validator um im Durchschnitt ein Commit für eine bestimmte Nachricht und eine Signatur zu veröffentlichen einmal pro Block. Selbst wenn die Commit-Nachrichten gleich wären, wäre eine solche Aggregation möglich BLS-Signatur und deren Validierung wären unerschwinglich teuer gewesen. Aber Natürlich sind die Commit- und Reveal-Nachrichten bei allen validators nicht gleich. und daher brauchen wir eine Möglichkeit, solche Nachrichten und die Signaturen in einem zusammenzufassen Dies ermöglicht eine spätere schnelle Validierung. Der spezifische Ansatz, den wir verwenden, ist der folgende: Validatoren schließen sich Blockproduzenten an. Die Blockproduzenten sind bekannt einige Zeit vor Beginn der Epoche, da sie einige Zeit zum Herunterladen benötigen Zustand vor Beginn der Epoche, und im Gegensatz zu den validators sind es die Blockproduzenten nicht verborgen. Jeder Blockproduzent verfügt über v validator Slots. Validatoren reichen ein Off-Chain-Vorschläge an die Blockproduzenten, als einer ihrer v validators. Wenn ein Blockproduzent einen validator einschließen möchte, reicht er einen ein Transaktion, die die erste Off-Chain-Anfrage von validator enthält, und die Signatur des Blockproduzenten, die dafür sorgt, dass validator dem Blockproduzenten beitritt. Beachten Sie, dass die den Blockproduzenten zugewiesenen validators dies nicht unbedingt tun Validieren Sie dieselben Shards, für die der Blockproduzent Chunks produziert. Wenn ein validator wird angewendet, um mehrere Blockproduzenten zu verbinden, nur die Transaktion von Der erste Blockproduzent wird erfolgreich sein. Blockproduzenten sammeln Commits. Der Blockproduzent sammelt ständig die Commit- und Reveal-Nachrichten von den validators. Sobald eine bestimmte Anzahl solcher Nachrichten angesammelt ist, berechnet der Blockproduzent ein Merkle Baum dieser Nachrichten und sendet an jeden validator die Merkle-Wurzel und die Merkle Weg zu ihrer Botschaft. Der validator validiert den Pfad und meldet sich an die Merkle-Wurzel. Der Blockproduzent sammelt dann eine BLS-Signatur auf dem Merkle Root aus den validators und veröffentlicht nur die Merkle Root und die gesammelte Unterschrift. Der Blockproduzent unterzeichnet auch die Gültigkeit des Multisignatur mit einer günstigen ECDSA-Signatur. Wenn die Multisignatur dies nicht tut Wenn Sie mit dem übermittelten Merkle-Stamm oder der Bitmaske der teilnehmenden validators übereinstimmen, handelt es sich um ein streichbares Verhalten. Beim Synchronisieren der Kette ein Teilnehmer Sie können wählen, ob alle BLS-Signaturen der validators validiert werden sollen (was extrem teuer ist, da die öffentlichen Schlüssel der validators aggregiert werden müssen) oder nurdie ECDMA-Signaturen von den Blockproduzenten und verlassen sich darauf, dass die Der Blockproduzent wurde nicht angefochten und gekürzt. Verwendung von On-Chain-Transaktionen und Merkle-Beweisen für Herausforderungen. Es Es kann festgestellt werden, dass es keinen Wert hat, Nachrichten von validators preiszugeben, wenn nein Es wurde ein ungültiger Zustandsübergang erkannt. Nur die Nachrichten, die das tatsächliche enthalten Beweise für einen ungültigen Zustandsübergang müssen offengelegt werden, und zwar nur für solche Nachrichten Es muss gezeigt werden, dass sie mit dem vorherigen Commit übereinstimmen. Die Nachricht muss zu zwei Zwecken offengelegt werden: 1. Um den Rollback der Kette tatsächlich auf den Moment vor dem einzuleiten ungültiger Zustandsübergang (siehe Abschnitt 3.7.5). 2. Um zu beweisen, dass der validator nicht versucht hat, die Gültigkeit des zu bestätigen Ungültiger Block. In beiden Fällen müssen wir uns mit zwei Problemen befassen: 1. Der eigentliche Commit war nicht in der Kette enthalten, sondern nur die Merkle-Wurzel des Commit aggregiert mit anderen Nachrichten. Der validator muss das verwenden Merkle-Pfad, der vom Blockproduzenten bereitgestellt wird, und dessen ursprüngliches Commit beweisen, dass sie sich der Herausforderung gestellt haben. 2. Es ist möglich, dass alle dem Shard zugewiesenen validators ungültig sind Zustandsübergänge werden zufällig beschädigten Blockproduzenten zugewiesen zensieren sie. Um dies zu umgehen, erlauben wir ihnen, ihre Enthüllungen einzureichen als reguläre Transaktion in der Kette und umgeht die Aggregation. Letzteres ist nur für die Nachweise eines ungültigen Zustandsübergangs zulässig äußerst selten und sollte daher nicht zum Spam der Blöcke führen. Das letzte Problem, das angegangen werden muss, besteht darin, dass die Blockproduzenten dies können sich dafür entscheiden, nicht an der Nachrichtenaggregation teilzunehmen oder bestimmte validators absichtlich zu zensieren. Wir machen es wirtschaftlich unvorteilhaft, indem wir den Block herstellen Produzentenbelohnung proportional zur Anzahl der ihnen zugewiesenen validators. Wir Beachten Sie auch, dass sich die Blockproduzenten zwischen den Epochen weitgehend überschneiden (seit Es sind immer die Top-W-Teilnehmer mit dem höchsten Einsatz), die validators können Bleiben Sie weitgehend bei der Zusammenarbeit mit denselben Blockproduzenten und reduzieren Sie so das Risiko dass sie einem Blockproduzenten zugewiesen wurden, der sie in der Vergangenheit zensiert hat. 3.9 Snapshots-Kette Da die Blöcke in der Hauptkette sehr häufig produziert werden, ist das Herunterladen erforderlich Die vollständige Historie könnte sehr schnell teuer werden. Darüber hinaus seit jedem Block eine BLS-Signatur einer großen Anzahl von Teilnehmern enthält, allein die Aggregation der öffentlichen Schlüssel zur Überprüfung der Signatur könnte unerschwinglich werden auch teuer. Schließlich wird Ethereum 1.0 in absehbarer Zukunft wahrscheinlich einer bleiben einer der am häufigsten verwendeten blockchains und bietet eine sinnvolle Möglichkeit, Vermögenswerte von dort zu übertragen
In der Nähe von Ethereum ist eine Anforderung, und heute ist die Überprüfung von BLS-Signaturen erforderlich, um dies sicherzustellen Die Gültigkeit naher Blöcke auf der Seite von Ethereum ist nicht möglich. Jeder Block in der Nightshade-Hauptkette kann optional einen Schnorr enthalten Multisignatur im Header des letzten Blocks, der einen solchen Schnorr enthielt Multisignatur. Wir nennen solche Blöcke Snapshot-Blöcke. Der allererste Block von Jede Epoche muss ein Snapshot-Block sein. Während ich an einer solchen Multisignatur arbeitete, Die Blockproduzenten müssen auch die BLS-Signaturen der validators sammeln auf dem letzten Snapshot-Block und aggregieren Sie sie auf die gleiche Weise wie in beschrieben Abschnitt 3.8. Da die Menge der Blockproduzenten während der gesamten Epoche konstant ist, ist eine Validierung erforderlich Nur die ersten Snapshot-Blöcke in jeder Epoche sind ausreichend, vorausgesetzt, dass bei Nr weisen darauf hin, dass ein großer Prozentsatz der Blockproduzenten und validators zusammengearbeitet und erstellt haben eine Gabel. Der erste Block der Epoche muss für die Berechnung ausreichende Informationen enthalten die Blockproduzenten und validators für die Epoche. Wir nennen die Unterkette der Hauptkette, die nur den Snapshot enthält blockiert eine Snapshot-Kette. Das Erstellen einer Schnorr-Multisignatur ist ein interaktiver Prozess, aber da wir Es muss nur selten durchgeführt werden, egal wie ineffizient der Prozess ist wird genügen. Die Schnorr-Multisignaturen können einfach unter Ethereum validiert werden, Dadurch werden entscheidende Grundelemente für eine sichere Durchführung von Cross-blockchain bereitgestellt. Kommunikation. Für die Synchronisierung mit der Near-Kette muss lediglich der gesamte Snapshot heruntergeladen werden blockiert und bestätigt, dass die Schnorr-Signaturen korrekt sind (optional auch Überprüfung der einzelnen BLS-Signaturen der validators) und dann nur die Synchronisierung Hauptkettenblöcke vom letzten Snapshot-Block.
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.
Abschluss
In diesem Dokument haben wir Ansätze zum Erstellen von Shard-blockchains und besprochen deckte mit bestehenden Ansätzen zwei große Herausforderungen ab, nämlich die Zustandsvalidität und Datenverfügbarkeit. Anschließend präsentierten wir Nightshade, ein Sharding-Design Befugnisse NEAR Protokoll. Der Entwurf ist in Arbeit. Wenn Sie Kommentare, Fragen oder Feedback haben Zu diesem Dokument gehen Sie bitte zu https://near.chat.