El Libro Blanco de NEAR

Nightshade: Near Protocol Sharding Design

Por Alex Skidanov and Illia Polosukhin · 2019

🇺🇸 English (Original)

🇪🇸 Español (Traducción)

Sharding Basics

Let’s start with the simplest approach to sharding. In this approach instead of running one blockchain, we will run multiple, and call each such blockchain a “shard”. Each shard will have its own set of validators. Here and below we use a generic term “validator” to refer to participants that verify transactions and produce blocks, either by mining, such as in Proof of Work, or via a voting-based 1This section was previously published at https://near.ai/shard1. If you read it before, skip to the next section.

mechanism. For now let’s assume that the shards never communicate with each other. This design, though simple, is suﬃcient to outline some initial major challenges in sharding. 1.1 Validator partitioning and Beacon chains Say that the system comprises 10 shards. The ﬁrst challenge is that with each shard having its own validators, each shard is now 10 times less secure than the entire chain. So if a non-sharded chain with X validators decides to hard-fork into a sharded chain, and splits X validators across 10 shards, each shard now only has X/10 validators, and corrupting one shard only requires corrupting 5.1% (51% / 10) of the total number of validators (see ﬁgure 1), Figure 1: Splitting the validators across shards which brings us to the second point: who chooses validators for each shard? Controlling 5.1% of validators is only damaging if all those 5.1% of validators are in the same shard. If validators can’t choose which shard they get to validate in, a participant controlling 5.1% of the validators is highly unlikely to get all their validators in the same shard, heavily reducing their ability to compromise the system. Almost all sharding designs today rely on some source of randomness to assign validators to shards. Randomness on blockchain on itself is a very challenging topic and is out of scope for this document. For now let’s assume there’s some source of randomness we can use. We will cover validators assignment in more detail in section 2.1. Both randomness and validator assignment require computation that is not speciﬁc to any particular shard. For that computation, practically all existing designs have a separate blockchain that is tasked with performing operations necessary for the maintenance of the entire network. Besides generating random

numbers and assigning validators to the shards, these operations often also include receiving updates from shards and taking snapshots of them, processing stakes and slashing in Proof-of-Stake systems, and rebalancing shards when that feature is supported. Such chain is called a Beacon chain in Ethereum, a Relay chain in PolkaDot, and the Cosmos Hub in Cosmos. Throughout this document we will refer to such chain as a Beacon chain. The existence of the Beacon chain brings us to the next interesting topic, the quadratic sharding. 1.2 Quadratic sharding Sharding is often advertised as a solution that scales inﬁnitely with the number of nodes participating in the network operation. While it is in theory possible to design such a sharding solution, any solution that has the concept of a Beacon chain doesn’t have inﬁnite scalability. To understand why, note that the Beacon chain has to do some bookkeeping computation, such as assigning validators to shards, or snapshotting shard chain blocks, that is proportional to the number of shards in the system. Since the Beacon chain is itself a single blockchain, with computation bounded by the computational capabilities of nodes operating it, the number of shards is naturally limited. However, the structure of a sharded network does bestow a multiplicative eﬀect on any improvements to its nodes. Consider the case in which an arbitrary improvement is made to the eﬃciency of nodes in the network which will allow them faster transaction processing times. If the nodes operating the network, including the nodes in the Beacon chain, become four times faster, then each shard will be able to process four times more transactions, and the Beacon chain will be able to maintain 4 times more shards. The throughput across the system will increase by the factor of 4 × 4 = 16 — thus the name quadratic sharding. It is hard to provide an accurate measurement for how many shards are viable today, but it is unlikely that in any foreseeable future the throughput needs of blockchain users will outgrow the limitations of quadratic sharding. The sheer number of nodes necessary to operate such a volume of shards securely is likely orders of magnitude higher than the number of nodes operating all the blockchains combined today. 1.3 State sharding Up until now we haven’t deﬁned very well what exactly is and is not separated when a network is divided into shards. Speciﬁcally, nodes in the blockchain perform three important tasks: not only do they 1) process transactions, they also 2) relay validated transactions and completed blocks to other nodes and 3) store the state and the history of the entire network ledger. Each of these three tasks imposes a growing requirement on the nodes operating the network:

The necessity to process transactions requires more compute power with the increased number of transactions being processed;
The necessity to relay transactions and blocks requires more network bandwidth with the increased number of transactions being relayed;
The necessity to store data requires more storage as the state grows. Importantly, unlike the processing power and network, the storage requirement grows even if the transaction rate (number of transactions processed per second) remains constant. From the above list it might appear that the storage requirement would be the most pressing, since it is the only one that is being increased over time even if the number of transactions per second doesn’t change, but in practice the most pressing requirement today is the compute power. The entire state of Ethereum as of this writing is 100GB, easily manageable by most of the nodes. But the number of transactions Ethereum can process is around 20, orders of magnitude less than what is needed for many practical use cases. Zilliqa is the most well-known project that shards processing but not storage. Sharding of processing is an easier problem because each node has the entire state, meaning that contracts can freely invoke other contracts and read any data from the blockchain. Some careful engineering is needed to make sure updates from multiple shards updating the same parts of the state do not conﬂict. In those regards Zilliqa is taking a relatively simplistic approach2. While sharding of storage without sharding of processing was proposed, it is extremely uncommon. Thus in practice sharding of storage, or State Sharding, almost always implies sharding of processing and sharding of network. Practically, under State Sharding the nodes in each shard are building their own blockchain that contains transactions that aﬀect only the local part of the global state that is assigned to that shard. Therefore, the validators in the shard only need to store their local part of the global state and only execute, and as such only relay, transactions that aﬀect their part of the state. This partition linearly reduces the requirement on all compute power, storage, and network bandwidth, but introduces new problems, such as data availability and cross-shard transactions, both of which we will cover below. 1.4 Cross-shard transactions The sharding model we described so far is not a very useful, because if individual shards cannot communicate with each other, they are no better than multiple independent blockchains. Even today, when sharding is not available, there’s a huge demand for interoperability between various blockchains. Let’s for now only consider simple payment transactions, where each participant has account on exactly one shard. If one wishes to transfer money from 2Our analysis of their approach can be found here: https://medium.com/nearprotocol/ 8f9efae0ce3b

one account to another within the same shard, the transaction can be processed entirely by the validators in that shard. If, however, Alice that resides on shard

1 wants to send money to Bob who resides on shard #2, neither validators

on shard #1(they won’t be able to credit Bob’s account) nor the validators on shard #2 (they won’t be able to debit Alice’s account) can process the entire transaction. There are two families of approaches to cross-shard transactions: • Synchronous: whenever a cross-shard transaction needs to be executed, the blocks in multiple shards that contain state transition related to the transaction get all produced at the same time, and the validators of multiple shards collaborate on executing such transactions.3 • Asynchronous: a cross-shard transaction that aﬀects multiple shards is executed in those shards asynchronously, the “Credit” shard executing its half once it has suﬃcient evidence that the “Debit” shard has executed its portion. This approach tends to be more prevalent due to its simplicity and ease of coordination. This system is today proposed in Cosmos, Ethereum Serenity, Near, Kadena, and others. A problem with this approach lies in that if blocks are produced independently, there’s a nonzero chance that one of the multiple blocks will be orphaned, thus making the transaction only partially applied. Consider ﬁgure 2 that depicts two shards both of which encountered a fork, and a cross-shard transaction that was recorded in blocks A and X’ correspondingly. If the chains A-B and V’-X’-Y’-Z’ end up being canonical in the corresponding shards, the transaction is fully ﬁnalized. If A’-B’-C’-D’ and V-X become canonical, then the transaction is fully abandoned, which is acceptable. But if, for example, A-B and V-X become canonical, then one part of the transaction is ﬁnalized and one is abandoned, creating an atomicity failure. We will cover how this problem is addressed in proposed protocols in the second part, when covering changes to the fork-choice rules and consensus algorithms proposed for sharded protocols. Note that communication between chains is useful outside of sharded blockchains too. Interoperability between chains is a complex problem that many projects are trying to solve. In sharded blockchains the problem is somewhat easier since the block structure and consensus are the same across shards, and there’s a beacon chain that can be used for coordination. In a sharded blockchain, however, all the shard chains are the same, while in the global blockchains ecosystem there are lots of diﬀerent blockchains, with diﬀerent target use cases, decentralization and privacy guarantees. Building a system in which a set of chains have diﬀerent properties but use suﬃciently similar consensus and block structure and have a common beacon chain could enable an ecosystem of heterogeneous blockchains that have a 3The most detailed proposal known to the authors of this document is Merge Blocks, described here: https://ethresear.ch/t/ merge-blocks-and-synchronous-cross-shard-state-execution/1240

Figure 2: Asynchronous cross-shard transactions working interoperability subsystem. Such system is unlikely to feature validator rotation, so some extra measures need to be taken to ensure security. Both Cosmos and PolkaDot are eﬀectively such systems4 1.5 Malicious behavior In this section we will review what adversarial behavior can malicious validators exercise if they manage to corrupt a shard. We will review classic approaches to avoiding corrupting shards in section 2.1. 1.5.1 Malicious forks A set of malicious validators might attempt to create a fork. Note that it doesn’t matter if the underlying consensus is BFT or not, corrupting suﬃcient number of validators will always make it possible to create a fork. It is signiﬁcantly more likely for more that 50% of a single shard to be corrupted, than for more than 50% of the entire network to be corrupted (we will dive deeper into these probabilities in section 2.1). As discussed in section 1.4, cross-shard transactions involve certain state changes in multiple shards, and the corresponding blocks in such shards that apply such state changes must either be all ﬁnalized (i.e. appear in the selected chains on their corresponding shards), or all be orphaned (i.e. not appear in the selected chains on their corresponding shards). Since generally the probability of shards being corrupted 4Refer to this writeup by Zaki Manian from Cosmos: https://forum.cosmos.network/ t/polkadot-vs-cosmos/1397/2 and this tweet-storm by the ﬁrst author of this document: https://twitter.com/AlexSkidanov/status/1129511266660126720 for a detailed comparison of the two

is not negligible, we can’t assume that the forks won’t happen even if a byzantine consensus was reached among the shard validators, or many blocks were produced on top of the block with the state change. This problem has multiple solutions, the most common one being occasional cross-linking of the latest shard chain block to the beacon chain. The fork choice rule in the shard chains is then changed to always prefer the chain that is cross-linked, and only apply shard-speciﬁc fork-choice rule for blocks that were published since the last cross-link. 1.5.2 Approving invalid blocks A set of validators might attempt to create a block that applies the state transition function incorrectly. For example, starting with a state in which Alice has 10 tokens and Bob has 0 tokens, the block might contain a transaction that sends 10 tokens from Alice to Bob, but ends up with a state in which Alice has 0 tokens and Bob has 1000 tokens, as shown on ﬁgure 3. Figure 3: An example of an invalid block In a classic non-sharded blockchain such an attack is not possible, since all the participant in the network validate all the blocks, and the block with such an invalid state transition will be rejected by both other block producers, and the participants of the network that do not create blocks. Even if the malicious validators continue creating blocks on top of such an invalid block faster than honest validators build the correct chain, thus having the chain with the invalid block being longer, it doesn’t matter, since every participant that is using the blockchain for any purpose validates all the blocks, and discards all the blocks built on top of the invalid block. On the ﬁgure 4 there are ﬁve validators, three of whom are malicious. They created an invalid block A’, and then continued building new blocks on top of it. Two honest validators discarded A’ as invalid and were building on top

Figure 4: Attempt to create an invalid block in a non-sharded blockchain of the last valid block known to them, creating a fork. Since there are fewer validators in the honest fork, their chain is shorter. However, in classic nonsharded blockchain every participant that uses blockchain for any purpose is responsible for validating all the blocks they receive and recomputing the state. Thus any person who has any interest in the blockchain would observe that A’ is invalid, and thus also immediately discard B’, C’ and D’, as such taking the chain A-B as the current longest valid chain. In a sharded blockchain, however, no participant can validate all the transactions on all the shards, so they need to have some way to conﬁrm that at no point in history of any shard of the blockchain no invalid block was included. Note that unlike with forks, cross-linking to the Beacon chain is not a suﬃcient solution, since the Beacon chain doesn’t have the capacity to validate the blocks. It can only validate that a suﬃcient number of validators in that shard signed the block (and as such attested to its correctness). We will discuss solutions to this problem in section 2.2 below.

Conceptos básicos de fragmentación

Comencemos con el enfoque más simple para fragmentar. En este enfoque en lugar de Al ejecutar un blockchain, ejecutaremos varios y llamaremos a cada uno de ellos blockchain como “fragmento”. Cada fragmento tendrá su propio conjunto de validators. Aquí y abajo utilizamos un término genérico “validator” para referirse a los participantes que verifican transacciones y producir bloques, ya sea mediante minería, como en Prueba de trabajo, o mediante una votación 1Esta sección se publicó anteriormente en https://near.ai/shard1. Si la leyó antes, salte a la siguiente sección.

mecanismo. Por ahora supongamos que los fragmentos nunca se comunican entre sí. otro. Este diseño, aunque simple, es suficiente para esbozar algunos de los principales desafíos iniciales en la fragmentación. 1.1 Partición de validadores y cadenas de balizas Digamos que el sistema consta de 10 fragmentos. El primer desafío es que con cada fragmento que tiene sus propios validators, cada fragmento ahora es 10 veces menos seguro que el cadena entera. Entonces, si una cadena no fragmentada con X validators decide realizar un hard-fork en una cadena fragmentada y divide X validators en 10 fragmentos, cada fragmento ahora solo tiene X/10 validators, y corromper un fragmento solo requiere corromper 5,1% (51% / 10) del número total de validators (ver figura 1), Figura 1: Dividiendo los validators en fragmentos lo que nos lleva al segundo punto: ¿quién elige validators para cada fragmento? Controlar el 5,1% de validators solo es perjudicial si todos esos 5,1% de validators están en el mismo fragmento. Si validators no pueden elegir qué fragmento validar En, es muy poco probable que un participante que controle el 5,1% de los validator obtenga todos sus validators en el mismo fragmento, lo que reduce en gran medida su capacidad de comprometerse el sistema. Casi todos los diseños de fragmentación actuales dependen de alguna fuente de aleatoriedad para asigne validators a fragmentos. La aleatoriedad en blockchain en sí misma es un tema muy desafiante y está fuera del alcance de este documento. Por ahora supongamos que hay alguna fuente de aleatoriedad que podamos utilizar. Cubriremos la tarea de validator en más detalle en la sección 2.1. Tanto la aleatoriedad como la asignación validator requieren un cálculo que no es específico de cualquier fragmento en particular. Para ese cómputo, prácticamente todos los existentes Los diseños tienen un blockchain separado que se encarga de realizar las operaciones. necesarios para el mantenimiento de toda la red. Además de generar aleatorionúmeros y asignando validators a los fragmentos, estas operaciones a menudo también incluir recibir actualizaciones de fragmentos y tomar instantáneas de ellos, procesar apuestas y recortes en los sistemas de prueba de participación, y reequilibrio de fragmentos cuando eso La función es compatible. Dicha cadena se denomina cadena de baliza en Ethereum, retransmisión cadena en PolkaDot y el Cosmos Hub en Cosmos. A lo largo de este documento nos referiremos a dicha cadena como cadena Beacon. La existencia de la cadena Beacon nos lleva al siguiente tema interesante, el fragmentación cuadrática. 1.2 fragmentación cuadrática La fragmentación a menudo se anuncia como una solución que escala infinitamente con el número de nodos que participan en la operación de la red. Si bien en teoría es posible diseñar una solución de fragmentación de este tipo, cualquier solución que tenga el concepto de Beacon La cadena no tiene una escalabilidad infinita. Para entender por qué, tenga en cuenta que Beacon cadena tiene que hacer algunos cálculos contables, como asignar validators a fragmentos, o instantáneas de bloques de cadena de fragmentos, que es proporcional al número de fragmentos en el sistema. Dado que la cadena Beacon es en sí misma un único blockchain, con computación limitada por las capacidades computacionales de los nodos que la operan, la cantidad de fragmentos es naturalmente limitada. Sin embargo, la estructura de una red fragmentada otorga un efecto multiplicativo. efecto sobre cualquier mejora en sus nodos. Consideremos el caso en el que una decisión arbitraria Se realiza una mejora en la eficiencia de los nodos de la red que permitirá ellos tiempos de procesamiento de transacciones más rápidos. Si los nodos que operan la red, incluidos los nodos de la cadena Beacon, se vuelve cuatro veces más rápido, entonces cada fragmento podrá procesar cuatro veces más transacciones, y la cadena Beacon podrá mantener 4 veces más fragmentos. El rendimiento en todo el sistema aumentará en un factor de 4 × 4 = 16 - de ahí el nombre de fragmentación cuadrática. Es difícil proporcionar una medición precisa de cuántos fragmentos hay viable hoy, pero es poco probable que en un futuro previsible el rendimiento Las necesidades de los usuarios blockchain superarán las limitaciones de la fragmentación cuadrática. La gran cantidad de nodos necesarios para operar tal volumen de fragmentos de forma segura es probablemente órdenes de magnitud mayor que el número de nodos que operan todos los blockchains combinados hoy. 1.3 fragmentación de estado Hasta ahora no hemos definido muy bien qué es exactamente lo que está y qué no está separado cuando una red se divide en fragmentos. Específicamente, los nodos en el blockchain realizan tres tareas importantes: no sólo 1) procesan transacciones, también también 2) transmitir transacciones validadas y bloques completados a otros nodos y 3) almacenar el estado y el historial de todo el libro mayor de la red. Cada uno de estos tres tareas impone una exigencia creciente a los nodos que operan la red:1. La necesidad de procesar transacciones requiere más potencia informática con el mayor número de transacciones procesadas; 2. La necesidad de retransmitir transacciones y bloques requiere más ancho de banda de red debido al mayor número de transacciones que se retransmiten; 3. La necesidad de almacenar datos requiere más almacenamiento a medida que crece el estado. Es importante destacar que, a diferencia de la potencia de procesamiento y la red, el requisito de almacenamiento crece incluso si la tasa de transacción (número de transacciones procesadas por segundo) permanece constante. De la lista anterior podría parecer que el requisito de almacenamiento sería el más apremiante, ya que es el único que se va incrementando con el tiempo incluso si el número de transacciones por segundo no cambia, pero en la práctica El requisito más urgente hoy en día es la potencia informática. todo el estado de Ethereum al momento de escribir este artículo es de 100 GB, fácilmente manejable por la mayoría de los nodos. Pero el número de transacciones que Ethereum puede procesar es de alrededor de 20, órdenes de magnitud menor de lo que se necesita para muchos casos de uso práctico. Zilliqa es el proyecto más conocido que fragmenta el procesamiento pero no el almacenamiento. La fragmentación del procesamiento es un problema más fácil porque cada nodo tiene la totalidad estado, lo que significa que los contratos pueden invocar libremente otros contratos y leer cualquier dato del blockchain. Se necesita una ingeniería cuidadosa para garantizar las actualizaciones. de múltiples fragmentos que actualizan las mismas partes del estado no entran en conflicto. en En ese sentido, Zilliqa está adoptando un enfoque relativamente simplista2. Si bien se propuso fragmentar el almacenamiento sin fragmentar el procesamiento, es extremadamente poco común. Así, en la práctica, la fragmentación del almacenamiento, o fragmentación del estado, casi siempre implica fragmentación del procesamiento y fragmentación de la red. En la práctica, bajo State Sharding, los nodos de cada fragmento están construyendo su propio blockchain que contiene transacciones que afectan sólo la parte local del estado global que está asignado a ese fragmento. Por lo tanto, los validators en el El fragmento solo necesita almacenar su parte local del estado global y solo ejecutarse, y como tal sólo transmiten transacciones que afectan su parte del estado. esto La partición reduce linealmente los requisitos de toda la potencia informática, el almacenamiento y la ancho de banda de la red, pero introduce nuevos problemas, como la disponibilidad de datos y transacciones entre fragmentos, las cuales cubriremos a continuación. 1.4 Transacciones entre fragmentos El modelo de fragmentación que describimos hasta ahora no es muy útil, porque si los individuos Los fragmentos no pueden comunicarse entre sí, no son mejores que múltiples blockchains independientes. Incluso hoy en día, cuando la fragmentación no está disponible, existe una enorme demanda de interoperabilidad entre varios blockchains. Por ahora, consideremos solo transacciones de pago simples, donde cada participante tiene una cuenta en exactamente un fragmento. Si uno desea transferir dinero desde 2Nuestro análisis de su enfoque se puede encontrar aquí: https://medium.com/nearprotocol/ 8f9efae0ce3buna cuenta a otra dentro del mismo fragmento, la transacción se puede procesar enteramente por los validators en ese fragmento. Sin embargo, si Alice reside en el fragmento

1 quiere enviar dinero a Bob que reside en el fragmento #2, ni a validators

en el fragmento #1 (no podrán acreditar la cuenta de Bob) ni los validators en El fragmento #2 (no podrán debitar la cuenta de Alice) puede procesar todo el proceso. transacción. Hay dos familias de enfoques para las transacciones entre fragmentos: • Síncrono: siempre que sea necesario ejecutar una transacción entre fragmentos, los bloques en múltiples fragmentos que contienen transición de estado relacionada con el Todas las transacciones se producen al mismo tiempo, y los validators de múltiples fragmentos colaboran en la ejecución de dichas transacciones.3 • Asíncrono: una transacción entre fragmentos que afecta a varios fragmentos. se ejecuta en esos fragmentos de forma asincrónica, el fragmento "Crédito" que se ejecuta su mitad una vez que tenga evidencia suficiente de que el fragmento "Debito" ha ejecutado su parte. Este enfoque tiende a ser más frecuente debido a su Simplicidad y facilidad de coordinación. Este sistema se propone hoy en Cosmos, Ethereum Serenity, Near, Kadena y otros. Un problema con esto El enfoque radica en que si los bloques se producen de forma independiente, existe una probabilidad distinta de cero de que uno de los múltiples bloques quede huérfano, lo que hace que la transacción sólo se aplicó parcialmente. Considere la figura 2 que muestra dos fragmentos que encontraron una bifurcación y una transacción entre fragmentos que quedó registrado en los bloques A y X’ respectivamente. Si las cadenas A-B y V’-X’-Y’-Z’ terminan siendo canónicos en los fragmentos correspondientes, el la transacción está completamente finalizada. Si A'-B'-C'-D' y V-X se vuelven canónicos, entonces la transacción se abandona por completo, lo cual es aceptable. Pero si, por Por ejemplo, A-B y V-X se vuelven canónicos, luego una parte de la transacción finaliza y otra se abandona, creando una falla de atomicidad. nosotros Cubriremos cómo se aborda este problema en los protocolos propuestos en la segunda parte, al cubrir los cambios en las reglas de elección de la bifurcación y el consenso. algoritmos propuestos para protocolos fragmentados. Tenga en cuenta que la comunicación entre cadenas es útil fuera de los blockchains fragmentados. también. La interoperabilidad entre cadenas es un problema complejo que muchos proyectos están tratando de resolver. En blockchains fragmentados el problema es algo más fácil ya que la estructura de bloques y el consenso son los mismos en todos los fragmentos, y hay una cadena de balizas que se puede utilizar para la coordinación. Sin embargo, en un blockchain fragmentado, todas las cadenas de fragmentos son iguales, mientras que en el ecosistema global de blockchains hay Hay muchos blockchain diferentes, con diferentes casos de uso objetivo, descentralización y garantías de privacidad. Construir un sistema en el que un conjunto de cadenas tengan diferentes propiedades pero usar consenso y estructura de bloques suficientemente similares y tener una cadena de baliza común podría permitir un ecosistema de blockchains heterogéneos que tengan una 3El la mayoría detallado propuesta conocido a el autores de esto documento es fusionar bloques, descrito aquí: https://ethresear.ch/t/ fusionar-bloques-y-ejecución-sincrónica-de-estado-entre-fragmentos/1240Figura 2: Transacciones asincrónicas entre fragmentos subsistema de interoperabilidad en funcionamiento. Es poco probable que dicho sistema presente rotación validator, por lo que se deben tomar algunas medidas adicionales para garantizar la seguridad. ambos Cosmos y PolkaDot son efectivamente tales sistemas4 1.5 Comportamiento malicioso En esta sección revisaremos qué comportamiento adversario pueden tener los validators maliciosos. ejercicio si logran corromper un fragmento. Revisaremos los enfoques clásicos. para evitar la corrupción de fragmentos en la sección 2.1. 1.5.1 tenedores maliciosos Un conjunto de validators maliciosos podría intentar crear una bifurcación. Tenga en cuenta que no importa si el consenso subyacente es BFT o no, corrompiendo un número suficiente de validators siempre permitirá crear una bifurcación. Es significativamente más probable que se corrompa más del 50% de un único fragmento que que se corrompa más del 50% de toda la red (veremos). profundizaremos en estas probabilidades en la sección 2.1). Como se analiza en la sección 1.4, Las transacciones entre fragmentos implican ciertos cambios de estado en múltiples fragmentos, y los bloques correspondientes en dichos fragmentos que aplican dichos cambios de estado deben estar completamente finalizado (es decir, aparecer en las cadenas seleccionadas en sus correspondientes fragmentos), o todos quedarán huérfanos (es decir, no aparecerán en las cadenas seleccionadas en sus fragmentos correspondientes). Dado que generalmente la probabilidad de que los fragmentos se corrompan 4Consulte este artículo de Zaki Manian de Cosmos: https://forum.cosmos.network/ t/polkadot-vs-cosmos/1397/2 y esta tormenta de tweets del primer autor de este documento: https://twitter.com/AlexSkidanov/status/1129511266660126720 para una comparación detallada de los dos

no es despreciable, no podemos asumir que las bifurcaciones no ocurrirán incluso si se alcanzó un consenso bizantino entre los fragmentos validators, o si se crearon muchos bloques. producido en la parte superior del bloque con el cambio de estado. Este problema tiene múltiples soluciones, siendo la más común la ocasional. reticulación del último bloque de la cadena de fragmentos con la cadena de baliza. el tenedor La regla de elección en las cadenas de fragmentos se cambia para preferir siempre la cadena que es entrecruzado y solo aplica la regla de elección de bifurcación específica de fragmentos para bloques que fueron publicado desde el último enlace cruzado. 1.5.2 Aprobar bloques no válidos Un conjunto de validator podría intentar crear un bloque que aplique la función de transición de estado incorrectamente. Por ejemplo, comenzando con un estado en el que Alice tiene 10 tokens y Bob tiene 0 tokens, el bloque podría contener una transacción que envía 10 tokens de Alice a Bob, pero termina con un estado en el que Alice tiene 0 tokens y Bob tiene 1000 tokens, como se muestra en la figura 3. Figura 3: Un ejemplo de un bloque no válido En un blockchain clásico no fragmentado, tal ataque no es posible, ya que todos el participante en la red valida todos los bloques, y el bloque con tales una transición de estado no válida será rechazada por los otros dos productores de bloques, y los participantes de la red que no crean bloques. Incluso si los maliciosos validators continúan creando bloques encima de un bloque no válido más rápido que Los validators honestos construyen la cadena correcta, teniendo así la cadena con el valor no válido. Si el bloque es más largo, no importa, ya que cada participante que esté usando el blockchain para cualquier propósito valida todos los bloques y descarta todos los bloques construido sobre el bloque no válido. En la figura 4 hay cinco validator, tres de los cuales son maliciosos. ellos creó un bloque A' no válido y luego continuó construyendo nuevos bloques encima de ello. Dos validators honestos descartaron A’ como inválida y estaban construyendo desde arribaFigura 4: Intento de crear un bloque no válido en un blockchain no fragmentado del último bloque válido conocido por ellos, creando una bifurcación. ya que hay menos validators en el tenedor honesto, su cadena es más corta. Sin embargo, en el blockchain clásico no fragmentado, cada participante que usa blockchain para cualquier propósito es responsable de validar todos los bloques que reciben y recalcular el estado. Por lo tanto, cualquier persona que tenga algún interés en el blockchain observará que A’ es inválido, y por lo tanto también descartar inmediatamente B’, C’ y D’, como tales tomando cadena A-B como la cadena válida más larga actual. Sin embargo, en un blockchain fragmentado, ningún participante puede validar todas las transacciones en todos los fragmentos, por lo que necesitan tener alguna forma de conﬁrmar que en ningún caso. En cualquier momento del historial de cualquier fragmento de blockchain no se incluyó ningún bloque no válido. Tenga en cuenta que, a diferencia de las bifurcaciones, el enlace cruzado a la cadena Beacon no es una solución suficiente, ya que la cadena Beacon no tiene la capacidad de validar la cadena. bloques. Solo puede validar que haya una cantidad suficiente de validator en ese fragmento. firmó el bloque (y como tal dio fe de su exactitud). Discutiremos soluciones a este problema en la sección 2.2 a continuación.

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 signiﬁcant 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 ﬁrst 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 ﬁgure 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 ﬁgure 6 for a visualization.

Figure 6: A blockchain with each block ﬁnalized 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 signiﬁcantly 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 signiﬁcantly higher security than the shard chains. Producing invalid blocks, however, is a signiﬁcantly more challenging problem to tackle. 2.2 State Validity Consider ﬁgure 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 Zamﬁr’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 ﬁgure below with 10 shards, each having four neighbors, and no two shards requiring more than two hops for a cross-shard communication shown on ﬁgure 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 ﬁgure 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: ﬁshermen

and cryptographic proofs of computation. 2.3 Fisherman The idea behind the ﬁrst 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 suﬃciently 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 signiﬁcantly 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 beneﬁcial 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 speciﬁcally 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 signiﬁcantly 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 ﬁgure 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 beneﬁt from it. For example, consider ﬁgure 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). Conﬁdent the transaction is ﬁnalized, 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 deﬁnitions 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 eﬀectively full nodes for that shard, while other participants in the system, including the beacon chain, operate as light nodes. For the ﬁsherman 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 ﬁgure 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 conﬁdence 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 ﬁgure 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 conﬁdent 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 suﬃcient 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 ﬁgure 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 oﬄine, 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 speciﬁc 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.

Validez del estado y disponibilidad de datos

La idea central en blockchains fragmentados es que la mayoría de los participantes que operan o el uso de la red no puede validar bloques en todos los fragmentos. Como tal, siempre que cualquier participante necesita interactuar con un fragmento en particular que generalmente no puede descargue y valide el historial completo del fragmento. El aspecto de partición de la fragmentación, sin embargo, plantea un potencial significativo problema: sin descargar y validar el historial completo de un determinado fragmento, el participante no puede necesariamente estar seguro de que el estado con el que 5Esta sección, excepto la subsección 2.5.3, se publicó anteriormente en https://near.ai/ fragmento2. Si lo leíste antes, salta a la siguiente sección.

interactúan es el resultado de alguna secuencia válida de bloques y que dicha secuencia de bloques es de hecho la cadena canónica en el fragmento. Un problema que no existe en un blockchain no fragmentado. Primero presentaremos una solución simple a este problema que ha sido propuesta. por muchos protocolos y luego analizar cómo esta solución puede romperse y qué se han hecho intentos para abordarlo. 2.1 Rotación de validadores La solución ingenua a la validez del estado se muestra en la figura 5: digamos que asumimos que todo el sistema tiene del orden de miles de validators, de los cuales no más del 20% son maliciosos o fallarán de otra manera (por ejemplo, al no ser en línea para producir un bloque). Entonces, si tomamos una muestra de 200 validators, la probabilidad de más de 1 3 reprobados a efectos prácticos se puede suponer que es cero. Figura 5: Muestreo validators 1 3 es un umbral importante. Existe una familia de protocolos de consenso, llamados BFT protocolos de consenso, que garantizan que mientras menos de 1 3 de los participantes fallan, ya sea al estrellarse o al actuar de alguna manera que viole las protocolo, se alcanzará el consenso. Con esta suposición de porcentaje honesto validator, si el conjunto actual de validators en un fragmento nos proporciona algún bloque, la solución ingenua supone que el bloque es válido y que está construido sobre lo que los validators creían que era la cadena canónica para ese fragmento cuando comenzaron a validar. Los validators aprendió la cadena canónica del conjunto anterior de validators, quienes por el mismo suposición construida sobre el bloque que era la cabeza de la cadena canónica antes de eso. Por inducción toda la cadena es válida y dado que no hay un conjunto de validators en cualquier momento se producen bifurcaciones, la solución ingenua también es segura de que la corriente chain es la única cadena en el fragmento. Consulte la figura 6 para obtener una visualización.

Figura 6: Un blockchain con cada bloque finalizado mediante el consenso BFT Esta solución simple no funciona si asumimos que los validators pueden ser corrompidos adaptativamente, lo cual no es una suposición descabellada6. Adaptablemente corromper un solo fragmento en un sistema con 1000 fragmentos es significativamente más barato que corromper todo el sistema. Por tanto, la seguridad del protocolo disminuye linealmente con el número de fragmentos. Para tener certeza en la validez de un bloque, debemos saber que en cualquier momento de la historia ningún fragmento del sistema ha una mayoría de validators en connivencia; con adversarios adaptativos, ya no tenemos tal certeza. Como comentamos en la sección 1.5, los validator en colusión pueden ejercer dos comportamientos maliciosos básicos: crear bifurcaciones y producir bloques no válidos. Las bifurcaciones maliciosas pueden abordarse mediante bloques que se entrecruzan con la cadena Beacon, que generalmente está diseñada para tener una seguridad significativamente mayor que la cadena Beacon. las cadenas de fragmentos. Sin embargo, producir bloques no válidos es una tarea mucho más problema desafiante de abordar. 2.2 Validez del estado Considere la figura 7 en la que el fragmento #1 está dañado y un actor malicioso produce bloque B no válido. Supongamos que en este bloque B se acuñaron 1000 tokens de la nada aire en la cuenta de Alice. El actor malintencionado produce entonces un bloque C válido (en un sentido de que las transacciones en C se aplican correctamente) encima de B, ofuscando el bloque B no válido e inicia una transacción entre fragmentos al fragmento #2 que transfiere esos 1000 tokens a la cuenta de Bob. A partir de este momento el mal Los token creados residen en un blockchain completamente válido en el fragmento #2. Algunos enfoques simples para abordar este problema son: 6Leer esto artículo para detalles en como adaptativo corrupción puede ser llevado fuera: https://medium.com/nearprotocol/d859adb464c8. Para más detalles en adaptativo corrupción, leer https://github.com/ethereum/wiki/wiki/Sharding-FAQ# ¿Cuáles-son-los-modelos-de-seguridad-bajo-los-que-estamos-operando?Figura 7: Una transacción entre fragmentos de una cadena que tiene un bloque no válido 1. Para validators del fragmento #2 para validar el bloque desde el cual se realizó la transacción se inicia. Esto no funcionará ni siquiera en el ejemplo anterior, ya que el bloque C parece ser completamente válido. 2. Para validators en el fragmento #2 para validar una gran cantidad de bloques que preceden al bloque desde el cual se inicia la transacción. Naturalmente, para cualquier número de bloques N validados por el fragmento receptor el malicioso validators pueden crear N+1 bloques válidos además del bloque no válido que producido. Una idea prometedora para resolver este problema sería organizar los fragmentos en un gráfico no dirigido en el que cada fragmento está conectado a varios otros fragmentos, y solo permitir transacciones entre fragmentos entre fragmentos vecinos (por ejemplo, así es como La fragmentación de Vlad Zamfir esencialmente funciona7, y una idea similar se utiliza en la de Kadena. Chainweb [1]). Si se necesita una transacción entre fragmentos entre fragmentos que están no vecinos, dicha transacción se enruta a través de múltiples fragmentos. en este diseño Se espera que un validator en cada fragmento valide todos los bloques en su fragmento así como todos los bloques en todos los fragmentos vecinos. Considere una figura a continuación con 10 fragmentos, cada uno con cuatro vecinos y no hay dos fragmentos que requieran más de dos saltos para una comunicación entre fragmentos como se muestra en la figura 8. El fragmento #2 no solo valida su propio blockchain, sino también los blockchains de todos los vecinos, incluido el fragmento n.° 1. Entonces, si un actor malicioso en el fragmento #1 está intentando crear un bloque B no válido, luego construye el bloque C encima de él e inicia una transacción entre fragmentos, dicha transacción entre fragmentos no se realizará desde el Fragmento #2 habrá validado toda la historia del Fragmento #1 que hará que identifique el bloque B no válido. 7Lea más sobre el diseño aquí: https://medium.com/nearprotocol/37e538177ed9

Figura 8: Una transacción entre fragmentos no válida en un sistema tipo cadena web que ser detectado Si bien corromper un único fragmento ya no es un ataque viable, corromper un pocos fragmentos siguen siendo un problema. En la figura 9, un adversario corrompiendo ambos Shard

1 y el fragmento #2 ejecutan con éxito una transacción entre fragmentos al fragmento #3

con fondos de un bloque B no válido: Figura 9: Una transacción entre fragmentos no válida en un sistema tipo cadena web que no ser detectado El fragmento n.º 3 valida todos los bloques del fragmento n.º 2, pero no del fragmento n.º 1, y no tiene forma de detectar el bloque malicioso. Hay dos direcciones principales para resolver adecuadamente la validez estatal: los pescadores

y pruebas criptográficas de cómputo. 2.3 pescador La idea detrás del primer enfoque es la siguiente: siempre que un encabezado de bloque se comunica entre cadenas para cualquier propósito (como el enlace cruzado con el cadena de baliza, o una transacción entre fragmentos), hay un período de tiempo durante cual cualquier validator honesto puede proporcionar una prueba de que el bloqueo no es válido. allí Hay varias construcciones que permiten pruebas muy sucintas de que los bloques son no válido, por lo que la sobrecarga de comunicación para los nodos receptores es mucho menor que el de recibir un bloqueo completo. Con este enfoque, siempre que haya al menos un validator honesto en el fragmento, el sistema es seguro. Figura 10: pescador Este es el enfoque dominante (además de fingir que el problema no existe) entre los protocolos propuestos hoy. Este enfoque, sin embargo, tiene dos principales desventajas: 1. El período de desafío debe ser lo suficientemente largo para el validator honesto. para reconocer que se produjo un bloque, descargarlo, verificarlo completamente y preparar el desafío si el bloque no es válido. La introducción de ese período ralentizar significativamente las transacciones entre fragmentos. 2. La existencia del protocolo de desafío crea un nuevo vector de ataques cuando los nodos maliciosos envían spam con desafíos no válidos. Una solución obvia a este problema es hacer que los retadores depositen una cierta cantidad de tokens que se devuelven si el desafío es válido. Esta es sólo una solución parcial, ya que Todavía podría ser benéfico para el adversario enviar spam al sistema (y quemar los depósitos) con impugnaciones no válidas, por ejemplo para impedir la validezdesafío de un honesto validator de pasar. Estos ataques son llamados ataques de duelo. Consulte la sección 3.7.2 para conocer una forma de evitar este último punto. 2.4 Argumentos de conocimiento sucintos y no interactivos La segunda solución a la corrupción de múltiples fragmentos es utilizar algún tipo de construcción criptográfica que permita demostrar que un determinado cálculo (como como calcular un bloque a partir de un conjunto de transacciones) se realizó correctamente. Este tipo de construcciones existen, p. zk-SNARK, zk-STARK y algunos otros, y algunos se utilizan activamente en los protocolos blockchain actuales para pagos privados, más notablemente ZCash. El principal problema con tales primitivos es que son notoriamente lentos de calcular. P.ej. Protocolo Coda, que utiliza zk-SNARK específicamente para demostrar que todos los bloques en el blockchain son válidos, dijo en un de las entrevistas que puede tomar 30 segundos por transacción para crear una prueba (Este número probablemente sea menor ahora). Curiosamente, no es necesario que una parte de confianza calcule una prueba, ya que la prueba no sólo da fe de la validez del cálculo para el que está construida, sino también de la la validez de la prueba misma. Por tanto, el cálculo de tales pruebas se puede dividir entre un conjunto de participantes con significativamente menos redundancia de lo que sería necesario realizar algún cálculo sin confianza. También permite a los participantes que calculan zk-SNARK para ejecutarse en hardware especial sin reducir el descentralización del sistema. Los desafíos de los zk-SNARK, además del rendimiento, son: 1. Dependencia de primitivas criptográficas menos investigadas y menos probadas; 2. "Residuos tóxicos": los zk-SNARK dependen de una configuración confiable en la que un grupo de personas realiza algún cálculo y luego descarta el intermedio valores de ese cálculo. Si todos los participantes del procedimiento se confabulan y se mantienen los valores intermedios, se pueden crear pruebas falsas; 3. Se introduce complejidad adicional en el diseño del sistema; 4. Los zk-SNARK solo funcionan para un subconjunto de cálculos posibles, por lo que un protocolo con un lenguaje Turing completo smart contract no podría usar SNARK para demostrar la validez de la cadena. 2.5 Disponibilidad de datos El segundo problema que abordaremos es la disponibilidad de datos. Generalmente nodos que operan un blockchain particular se separan en dos grupos: nodos completos, aquellos que descargan cada bloque completo y validan cada transacción, y Light Nodos, aquellos que solo descargan encabezados de bloques y usan pruebas de Merkle para las partes del estado y las transacciones que les interesan, como se muestra en la figura 11.

Figura 11: árbol de merkle Ahora bien, si la mayoría de los nodos completos se confabulan, pueden producir un bloque, válido o no es válido y envía su hash a los nodos de luz, pero nunca revela el contenido completo del bloque. Hay varias maneras en que pueden beneﬁciarse de ello. Por ejemplo, considere la figura 12: Figura 12: Problema de disponibilidad de datos Hay tres bloques: el anterior, A, está producido por validators honestos; el actual, B, tiene validators en connivencia; y el siguiente, C, también se producirá por validators honestos (el blockchain se muestra en la esquina inferior derecha). Eres un comerciante. Los validators del bloque actual (B) recibieron el bloque A de los validators anteriores, calculó un bloque en el que recibe dinero,y le envié un encabezado de ese bloque con una prueba Merkle del estado en el que tiene dinero (o una prueba Merkle de una transacción válida que envía el dinero a ti). Con la seguridad de que la transacción está finalizada, usted brinda el servicio. Sin embargo, los validators nunca distribuyen el contenido completo del bloque B a cualquiera. Como tal, los validator__s honestos del bloque C no pueden recuperar el bloque y se ven obligados a detener el sistema o a construir sobre A, privándolo a usted como comerciante de dinero. Cuando aplicamos el mismo escenario a la fragmentación, las definiciones de completo y El nodo ligero generalmente se aplica por fragmento: validators en cada fragmento descarga cada bloquear en ese fragmento y validar cada transacción en ese fragmento, pero otros nodos del sistema, incluidos aquellos que capturan el estado de las cadenas de fragmentos en el cadena de balizas, descargue solo los encabezados. Por lo tanto, los validators en el fragmento son efectivamente nodos completos para ese fragmento, mientras que otros participantes en el sistema, incluida la cadena de balizas, funcionan como nodos luminosos. Para que funcione el enfoque del pescador que analizamos anteriormente, los validators honestos Debe poder descargar bloques que estén vinculados cruzadamente a la cadena de baliza. Si validators maliciosos vinculaban un encabezado de un bloque no válido (o lo usaban para iniciar una transacción entre fragmentos), pero nunca distribuyó el bloque, el honesto Los validators no tienen forma de crear un desafío. Cubriremos tres enfoques para abordar este problema que complementan unos a otros. 2.5.1 Pruebas de custodia El problema más inmediato a resolver es si un bloque está disponible una vez esta publicado. Una idea propuesta es tener los llamados Notarios que rotan entre fragmentos con más frecuencia que validators cuyo único trabajo es descargar un bloquear y dar fe de que pudieron descargarlo. pueden ser rotan con más frecuencia porque no necesitan descargar el estado completo del fragmento, a diferencia de los validators que no se pueden rotar con frecuencia ya que debe descargar el estado del fragmento cada vez que gira, como se muestra en la figura 13. El problema con este enfoque ingenuo es que es imposible demostrar más tarde si el Notario pudo o no descargar el bloque, por lo que un Notario pueden optar por dar fe siempre de que pudieron descargar el bloque sin incluso intentar recuperarlo. Una solución a esto es que los notarios proporcionen alguna evidencia o apostar alguna cantidad de tokens que acrediten que el bloque fue descargado. Una de esas soluciones se analiza aquí: https://ethresear.ch/t/ Bonos de custodia de 1 bit amigables con la agregación/2236. 2.5.2 Códigos de borrado Cuando un nodo de luz en particular recibe un hash de un bloque, para aumentar el valor del nodo Si está seguro de que el bloque está disponible, puede intentar descargar algunos archivos aleatorios. pedazos del bloque. Esta no es una solución completa, ya que a menos que los nodos de luz descargar colectivamente el bloque completo que los productores de bloques maliciosos pueden elegir

Figura 13: Los validadores necesitan descargar el estado y, por lo tanto, no se pueden rotar. frecuentemente retener las partes del bloque que no fueron descargadas por ningún nodo ligero, por lo que el bloque aún no está disponible. Una solución es utilizar una construcción llamada Códigos de borrado para que sea posible para recuperar el bloque completo incluso si solo una parte del bloque está disponible, como se muestra en la figura 14. Figura 14: Merkle tree construido sobre datos codificados de borrado Tanto Polkadot como Ethereum Serenity tienen diseños en torno a esta idea que Proporcionar una manera para que los nodos ligeros estén razonablemente seguros de que los bloques están disponibles. El enfoque Ethereum Serenity tiene una descripción detallada en [2].2.5.3 El enfoque de Polkadot respecto de la disponibilidad de datos En Polkadot, como en la mayoría de las soluciones fragmentadas, cada fragmento (llamado parachain) envía instantáneas de sus bloques a la cadena de baliza (llamada cadena de retransmisión). Digamos que hay 2f + 1 validators en la cadena de relés. Los productores de bloques de los bloques parachain, llamados Alzadores, una vez que se produce el bloque parachain, calcule una versión codificada de borrado del bloque que consta de 2f +1 partes, de modo que cualquier f partes sea suficiente. para reconstruir el bloque. Luego distribuyen una parte a cada validator en el cadena de relevo. Una cadena de retransmisión particular validator solo firmaría en una cadena de retransmisión bloque si tienen su parte para cada bloque de parachain que se captura en dicho bloque de cadena de relés. Por lo tanto, si un bloque de cadena de retransmisión tiene firmas de 2f + 1 validators, y mientras no más de f de ellos violen el protocolo, cada El bloque parachain se puede reconstruir obteniendo las piezas de validators. que siguen el protocolo. Ver figura 15. Figura 15: Disponibilidad de datos de Polkadot 2.5.4 Disponibilidad de datos a largo plazo Tenga en cuenta que todos los enfoques discutidos anteriormente solo dan fe del hecho de que un bloque se publicó y ya está disponible. Los bloques pueden dejar de estar disponibles más adelante por una variedad de razones: nodos que se desconectan, nodos que borran intencionalmente datos históricos datos, y otros. Un documento técnico que vale la pena mencionar y que aborda este problema es Polyshard [3], que utiliza códigos de borrado para hacer que los bloques estén disponibles en todos los fragmentos, incluso si hay varios Los fragmentos pierden completamente sus datos. Desafortunadamente, su enfoque específico requiere todos los fragmentos para descargar bloques de todos los demás fragmentos, lo cual es prohibitivamente caro. La disponibilidad a largo plazo no es un problema tan urgente: dado que ningún participante Se espera que el sistema sea capaz de validar todas las cadenas en todos los

fragmentos, la seguridad del protocolo fragmentado debe diseñarse de tal manera manera que el sistema sea seguro incluso si algunos bloques antiguos en algunos fragmentos se vuelven completamente no disponible.

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 diﬀerently 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 ﬁnality, while in the longest chain more blocks need to be built on top of the block to ensure the ﬁnality. Often for a meaningful security the time it takes for suﬃcient 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], signiﬁcantly reduce the probability of adaptive corruption. 3. Most importantly, the system stalls if 1 3 or more of all the participants are oﬄine. 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 ﬁnalized using a BFT ﬁnality gadget maintain the advantages of both models. Such BFT ﬁnality 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. Speciﬁcally 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 ﬁnality gadget that uses the attestations to ﬁnalize the blocks. To reduce the complexity of the system, we use a ﬁnality gadget that doesn’t inﬂuence the fork choice rule in any way, and instead only introduces extra slashing conditions, such that once a block is ﬁnalized by the ﬁnality gadget, a fork is impossible unless a very large percentage of the total stake is slashed. Casper CBC is such a ﬁnality 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 ﬁnality 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 diﬀerent 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 aﬀect 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 aﬀect 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 ﬁnal 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 ﬁxed schedule. The block producers have an order and repeatedly produce blocks in that order. E.g. if there are 100 block producers, the ﬁrst 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 ﬁrst 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 aﬀect more than one shard, it needs to be consecutively executed in each shard separately. The full transaction is sent to the ﬁrst shard aﬀected, 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 ﬁgure 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 ﬁgure 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 ﬁgure 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. Speciﬁcally, 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 ﬁrst 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 indeﬁnitely. 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 ﬁgure 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 ﬁnal. 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 oﬀ, is not a level of security suﬃcient 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 ﬁsherman 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 signiﬁcantly 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 suﬃcient information to conﬁrm 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 ﬁsherman to create a challenge that a state transition is applied incorrectly it is suﬃcient to ﬁnd the ﬁrst such invalid state root, and include just Ls bytes of state that are aﬀected 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 conﬁrm 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 ﬁrst Ls bytes it touches with the merkle proofs, which will be enough to apply the transactions and conﬁrm 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 aﬀects the ﬁnality, 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 ﬁnal until the challenge period is over (see ﬁgure 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 ﬁgure 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 ﬁgure 23. Both of the above approaches provide atomicity assuming that the challenge period is suﬃciently 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 signiﬁcantly reduces the probability of adaptive corruption, since to ﬁnalize 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 suﬃciently long for any such attack to be attempted. We argue that the probability, while extremely low, is still suﬃciently large for a system that is expected to execute multi-million transactions and run a world-wide ﬁnancial 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 ﬁnancial upside. If an adaptive adversary oﬀers them more money then the expected return from operating honestly, it is reasonable to expect that many validators will accept the oﬀer. 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 suﬃciently 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 beneﬁcial 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 ﬁgure 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 deﬁnition 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. Speciﬁcally, 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 signiﬁcantly increase the cost of validation. Figure 25: Commit-reveal

Instead we make the validators ﬁrst 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 ﬁgure 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 ﬁrst 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 nullyﬁed. 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 suﬃcient for all the validators to download the state, as shown on ﬁgure 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 speciﬁc 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 oﬀ-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 oﬀ-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 ﬁrst 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 ﬁnal 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 ﬁrst 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 ﬁrst snapshot blocks in each epoch is suﬃcient assuming that at no point a large percentage of block producers and validators colluded and created a fork. The ﬁrst block of the epoch must contain information suﬃcient 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 ineﬃcient, process will suﬃce. 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 conﬁrm 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 De cadenas de fragmentos a fragmentos de fragmentos El modelo de fragmentación con cadenas de fragmentos y una cadena de balizas es muy poderoso pero tiene ciertas complejidades. En particular, es necesario ejecutar la regla de elección de la bifurcación. en cada cadena por separado, la regla de elección de bifurcación en las cadenas de fragmentos y la baliza La cadena debe construirse de manera diferente y probarse por separado. En Nightshade modelamos el sistema como un único blockchain, en el que cada El bloque contiene lógicamente todas las transacciones para todos los fragmentos y cambia el Estado completo de todos los fragmentos. Físicamente, sin embargo, ningún participante descarga el estado completo o el bloque lógico completo. En cambio, cada participante de la red sólo mantiene el estado que corresponde a los fragmentos para los que validan las transacciones, y la lista de todas las transacciones en el bloque se divide en físicas trozos, un trozo por fragmento. En condiciones ideales, cada bloque contiene exactamente un fragmento por fragmento por bloque, que corresponde aproximadamente al modelo con cadenas de fragmentos en el que el Las cadenas de fragmentos producen bloques con la misma velocidad que la cadena de baliza. Sin embargo, Debido a retrasos en la red, es posible que falten algunos fragmentos, por lo que en la práctica cada bloque contiene uno o cero fragmentos por fragmento. Consulte la sección 3.3 para obtener detalles sobre cómo Se producen bloques. Figura 16: Un modelo con cadenas de fragmentos a la izquierda y con una cadena que tiene bloques divididos en trozos a la derecha

3.2 Consenso Los dos enfoques dominantes para el consenso en la década de blockchains hoy son el cadena más larga (o más pesada), en la que la cadena que tiene más trabajo o participación utilizado para construirlo se considera canónico, y BFT, en el que para cada bloque algunos un conjunto de validator alcanzan un consenso BFT. En los protocolos propuestos recientemente, este último es el enfoque más dominante, ya que proporciona una finalidad inmediata, mientras que en la cadena más larga se necesitan más bloques. que se construirá encima del bloque para asegurar la finalidad. A menudo para un significado seguridad: el tiempo que lleva construir un número suficiente de bloques supone el orden de horas. Usar el consenso BFT en cada bloque también tiene desventajas, tales como: 1. El consenso BFT implica una cantidad considerable de comunicación. mientras Los avances recientes permiten alcanzar el consenso en tiempo lineal en número. de los participantes (ver, por ejemplo, [4]), todavía se nota una sobrecarga por bloque; 2. Es inviable que todos los participantes de la red participen en el BFT consenso por bloque, por lo que normalmente sólo un subconjunto de participantes muestreados aleatoriamente alcanza el consenso. Un conjunto muestreado aleatoriamente puede ser, en principio, se corrompe adaptativamente y, en teoría, se puede crear una bifurcación. el sistema cualquiera de los dos necesita ser modelado para estar listo para tal evento y, por lo tanto, aún tener una regla de elección de bifurcación además del consenso BFT, o estar diseñado para cerrar abajo en tal evento. Cabe mencionar que algunos diseños, como Algorand [5], reducen significativamente la probabilidad de corrupción adaptativa. 3. Lo más importante es que el sistema se detiene si 1 3 o más de todos los participantes son fuera de línea. Por lo tanto, cualquier falla temporal de la red o una división de la red puede detener completamente el sistema. Idealmente, el sistema debe poder continuar operar mientras al menos la mitad de los participantes estén en línea (la mayoría Los protocolos basados en cadena continúan funcionando incluso si menos de la mitad de los participantes están en línea, pero la conveniencia de esta propiedad es más discutible. dentro de la comunidad). Un modelo híbrido en el que el consenso utilizado es el más pesado La cadena, pero algunos bloques se finalizan periódicamente utilizando un dispositivo de finalidad BFT mantienen las ventajas de ambos modelos. Estos dispositivos de finalidad BFT son Casper FFG [6] usado en Ethereum 2.0 8, Casper CBC (ver https://vitalik. ca/general/2018/12/05/cbc_casper.html) y ABUELO (ver https:// medium.com/polkadot-network/d08a24a021b5) utilizado en Polkadot. Nightshade utiliza el consenso de cadena más pesado. Específicamente cuando un bloque productor produce un bloque (ver sección 3.3), puede recolectar firmas de otros productores de bloques y validators que acrediten el bloque anterior. Ver sección 3.8 para obtener detalles sobre cómo se agrega una cantidad tan grande de firmas. el peso 8Vea también la sesión de pizarra con Justin Drake para obtener una descripción detallada de Casper. FFG y cómo se integra con el consenso de la cadena más pesada de GHOST aquí: https://www. youtube.com/watch?v=S262StTwkmode un bloque es entonces la participación acumulada de todos los firmantes cuyas firmas son incluido en el bloque. El peso de una cadena es la suma de los pesos de los bloques. Además del consenso de cadena más pesado, utilizamos un dispositivo de finalidad que utiliza las certificaciones para finalizar los bloques. Para reducir la complejidad del sistema, utilizamos un dispositivo de finalidad que no influye de ninguna manera en la regla de elección de la bifurcación, y en su lugar sólo introduce condiciones de corte adicionales, de modo que una vez que un bloque es finalizado por el dispositivo de finalidad, una bifurcación es imposible a menos que un porcentaje muy grande del total de la apuesta se reduce drásticamente. Casper CBC es un dispositivo de finalidad, y Actualmente modela con Casper CBC en mente. También trabajamos en un protocolo BFT separado llamado TxFlow. En el momento de Al escribir este documento no está claro si se utilizará TxFlow en lugar de Casper. CBC. Sin embargo, observamos que la elección del dispositivo final es en gran medida ortogonal al resto del diseño. 3.3 producción de bloques En Nightshade hay dos roles: productores de bloques y validators. en cualquier punto el sistema contiene w productores de bloques, w = 100 en nuestros modelos, y wv validators, en nuestro modelo v = 100, wv = 10, 000. El sistema es Prueba de participación, lo que significa que tanto los productores de bloques como los validators tienen algún número de moneda (denominada "tokens") bloqueada por un período de tiempo que excede con creces el tiempo que dedican a realizar sus tareas de construcción y validación de la cadena. Como ocurre con todos los sistemas de Prueba de participación, no todos los productores de bloques w y no todos los wv validators son entidades diferentes, ya que eso no se puede hacer cumplir. cada uno de los productores de bloques w y los wv validators, sin embargo, tienen una estaca. El sistema contiene n fragmentos, n = 1000 en nuestro modelo. Como se menciona en sección 3.1, en Nightshade no hay cadenas de fragmentos; en cambio, todos los productores de bloques y validator están construyendo un único blockchain, al que nos referimos como cadena principal. El estado de la cadena principal se divide en n fragmentos y cada bloque productor y validator en cualquier momento solo han descargado localmente un subconjunto de el estado que corresponde a algún subconjunto de los fragmentos, y solo el proceso y validar transacciones que afecten a esas partes del estado. Para convertirse en productor de bloques, un participante de la red bloquea algunos grandes cantidad de tokens (una participación). El mantenimiento de la red se realiza en épocas, donde una época es un período de tiempo del orden de días. Los participantes con lo que está en juego más al comienzo de una época particular es el bloque productores de esa época. Cada productor de bloques se asigna a fragmentos sw (digamos sw = 40, lo que haría sww/n = 4 productores de bloques por fragmento). el bloque El productor descarga el estado del fragmento al que están asignados antes de la época. comienza, y a lo largo de la época recopila transacciones que afectan ese fragmento, y los aplica al Estado. Para cada bloque b en la cadena principal, y para cada fragmento s, hay uno de los productores de bloques asignados a s, quien es responsable de producir la parte de b relacionada al fragmento. La parte de b relacionada con el fragmento s se llama fragmento y contiene el lista de las transacciones para que el fragmento se incluya en b, así como el merkleraíz del estado resultante. b en última instancia sólo contendrá un encabezado muy pequeño de el fragmento, es decir, la raíz merkle de todas las transacciones aplicadas (consulte la sección 3.7.1 para detalles exactos), y la raíz merkle del estado final. A lo largo del resto del documento, a menudo nos referimos al productor de bloques. que es responsable de producir un fragmento en un momento particular para un fragmento en particular como productor de trozos. El productor de fragmentos es siempre uno de los productores de bloques. Los productores de bloques y los productores de trozos rotan cada bloque según a un horario fijo. Los productores de bloques tienen un pedido y producen repetidamente. bloques en ese orden. P.ej. Si hay 100 productores de bloques, el primer bloque Los productores son responsables de producir los bloques 1, 101, 201, etc., el segundo es responsable de producir 2, 102, 202, etc.). Dado que la producción de trozos, a diferencia de la producción de bloques, requiere mantener el estado, y para cada fragmento solo los productores de bloques sww/n mantienen el estado por fragmento, en consecuencia, solo los productores de bloques sww/n rotan para crear trozos. P.ej. con las constantes anteriores con cuatro productores de bloques asignados a En cada fragmento, cada productor de bloques creará fragmentos una vez cada cuatro bloques. 3.4 Garantizar la disponibilidad de datos Para garantizar la disponibilidad de datos utilizamos un enfoque similar al de Polkadot descrito en la sección 2.5.3. Una vez que un productor de bloques produce un fragmento, crea una versión codificada de borrado con un código de bloque óptimo (w, ⌊w/6 + 1⌋) del trozo. Luego envían una parte del fragmento codificado de borrado (a esas partes las llamamos partes de fragmentos, o solo partes) a cada productor de bloques. Calculamos un árbol merkle que contiene todas las partes como las hojas, y el El encabezado de cada fragmento contiene la raíz merkle de dicho árbol. Las piezas se envían a los validators mediante mensajes onepart. Cada uno de esos mensajes contiene el encabezado del fragmento, el ordinal de la parte y el contenido de la parte. el El mensaje también contiene la firma del productor del bloque que produjo el chunk y la ruta merkle para demostrar que la parte corresponde al encabezado y es producido por el productor de bloques adecuado. Una vez que un productor de bloques recibe un bloque de la cadena principal, primero verifica si tenga mensajes de una parte para cada fragmento incluido en el bloque. Si no, el bloque no se procesa hasta que se recuperan los mensajes de una parte que faltan. Una vez que se reciben todos los mensajes de una parte, el productor del bloque recupera el partes restantes de los pares y reconstruye los fragmentos que mantienen el estado. El productor de bloques no procesa un bloque de la cadena principal si es por al menos un fragmento incluido en el bloque no tienen el mensaje de una parte correspondiente, o si al menos para un fragmento para el cual mantienen el estado no pueden reconstruir todo el trozo. Para que un fragmento en particular esté disponible es suficiente que ⌊w/6⌋+1 del bloque los productores tienen sus partes y les sirven. Así, mientras el número de Los actores maliciosos no superan ⌊w/3⌋ninguna cadena que tenga más de medio bloque. los productores que lo construyen pueden tener fragmentos no disponibles.Figura 17: Cada bloque contiene uno o cero fragmentos por fragmento, y cada fragmento tiene un código de borrado. Cada parte del fragmento codificado de borrado se envía a un lugar designado productor de bloques a través de un mensaje especial de una parte 3.4.1 Tratar con productores de bloques perezosos Si un productor de bloques tiene un bloque al que le falta un mensaje de una parte, podría optar por firmar aún así, porque si el bloque termina en la cadena, maximizará la recompensa para el productor del bloque. No hay riesgo para el bloque. productor ya que es imposible probar posteriormente que el productor del bloque no tenía el mensaje de una parte. Para solucionarlo, hacemos que cada fragmento sea productor al crear el fragmento para elija un color (rojo o azul) para cada parte del futuro fragmento codificado y guárdelo la máscara de bits del color asignado en el fragmento antes de codificarlo. cada una de las partes El mensaje contiene el color asignado a la pieza y el color se utiliza cuando calcular la raíz merkle de las partes codificadas. Si el productor del trozo se desvía del protocolo, se puede probar fácilmente, ya que la raíz de merkle no corresponden a mensajes de una parte, o los colores en los mensajes de una parte que corresponden a la raíz de merkle no coincidirán con la máscara en el fragmento. Cuando un productor de bloques firma en un bloque, incluye una máscara de bits de todos los piezas rojas que recibieron por los trozos incluidos en el bloque. Publicar un la máscara de bits incorrecta es un comportamiento que se puede recortar. Si un productor de bloques no ha recibido un mensaje de una parte, no tienen forma de saber el color del mensaje, y Por lo tanto, tienen un 50% de posibilidades de ser eliminados si intentan firmar a ciegas el bloque. 3.5 Solicitud de transición de estado Los productores de fragmentos sólo eligen qué transacciones incluir en el fragmento, pero no aplique la transición de estado cuando produzcan un fragmento. En consecuencia,

el encabezado del fragmento contiene la raíz merkle del estado merkelizado como antes se aplican las transacciones en el fragmento. Las transacciones solo se aplican cuando un bloque completo que incluye el fragmento se procesa. Un participante solo procesa un bloque si 1. El bloque anterior fue recibido y procesado; 2. Para cada fragmento, el participante no mantiene el estado que tiene. visto el mensaje de una parte; 3. Para cada fragmento, el participante mantiene el estado porque tiene el trozo completo. Una vez que se procesa el bloque, para cada fragmento para el cual el participante mantiene el estado, aplican las transacciones y calculan el nuevo estado a partir de que se aplican las transacciones, después de lo cual están listas para producir los fragmentos para el siguiente bloque, si están asignados a algún fragmento, ya que tienen la raíz merkle del nuevo estado merkelizado. 3.6 Transacciones y recibos entre fragmentos Si una transacción necesita afectar a más de un fragmento, debe realizarse consecutivamente. ejecutado en cada fragmento por separado. La transacción completa se envía al primer fragmento. afectado, y una vez que la transacción se incluye en el fragmento de dicho fragmento, y se aplica después de que el fragmento se incluye en un bloque, genera el llamado recibo transacción, que se enruta al siguiente fragmento en el que la transacción debe ser ejecutado. Si se requieren más pasos, la ejecución de la transacción de recibo genera una nueva transacción de recibo y así sucesivamente. 3.6.1 Duración de la transacción del recibo Es deseable que la transacción de recibo se aplique en el bloque que sigue inmediatamente al bloque en el que se generó. La transacción del recibo es sólo generado después de que el bloque anterior fue recibido y aplicado por los productores de bloques que mantienen el fragmento de origen, y debe ser conocido en el momento en que El fragmento para el siguiente bloque es producido por los productores de bloques del destino. fragmento. Por lo tanto, el recibo debe comunicarse desde el fragmento de origen al fragmento de destino en el corto período de tiempo entre esos dos eventos. Sea A el último bloque producido que contiene una transacción t que genera un recibo r. Sea B el siguiente bloque producido (es decir, un bloque que tiene A como su bloque anterior) que queremos contener r. Sea t estar en el fragmento a y r en el fragmento b. La vida útil del recibo, también representada en la figura 18, es la siguiente: Elaborar y almacenar los recibos. El cpa del productor de fragmentos para fragmentos a recibe el bloque A, aplica la transacción t y genera el recibo r. cpa luego almacena todos los recibos producidos en su almacenamiento interno persistente indexado por la identificación del fragmento de origen.Distribuyendo los recibos. Una vez que cpa esté listo para producir el fragmento para fragmento a para el bloque B, obtienen todos los recibos generados al aplicar las transacciones del bloque A para el fragmento a y los incluyen en el fragmento para shrad a en el bloque B. Una vez que se genera dicho fragmento, cpa produce su borrado codificado versión y todos los mensajes onepart correspondientes. cpa sabe qué productores de bloques mantienen el estado completo para qué fragmentos. Para un productor de bloques en particular pb cpa incluye los ingresos que resultaron de aplicar las transacciones del bloque A para el fragmento a que tiene como destino cualquiera de los fragmentos que le interesan a bp en el mensaje de una parte cuando distribuyeron el fragmento para el fragmento a en el bloque B (consulte la figura 17, que muestra los recibos incluidos en el mensaje de una parte). Recibir los recibos. Recuerde que los participantes (tanto productores de bloques como validators) no procesan bloques hasta que tengan mensajes de una parte. para cada fragmento incluido en el bloque. Por lo tanto, cuando un participante en particular aplica el bloque B, tiene todos los mensajes de una parte que corresponden a fragmentos en B, y por lo tanto tienen todos los recibos entrantes que tienen los fragmentos el participante mantiene el estado como destino. Al aplicar el transición de estado para un fragmento en particular, el participante aplica ambos recibos que han recopilado para el fragmento en los mensajes de una parte, así como todos las transacciones incluidas en el propio fragmento. Figura 18: La vida útil de una transacción de recibo 3.6.2 Manejar demasiados recibos Es posible que el número de recibos dirigidos a un fragmento concreto en un bloque en particular es demasiado grande para ser procesado. Por ejemplo, considere la figura 19, en en el que cada transacción en cada fragmento genera un recibo dirigido al fragmento 1. En el siguiente bloque, la cantidad de recibos que el fragmento 1 debe procesar es comparable a la carga que todos los fragmentos combinados procesaron mientras se manipulaban el bloque anterior.

Figura 19: Si todos los recibos apuntan al mismo fragmento, es posible que el fragmento no tenga la capacidad de procesarlos Para solucionarlo utilizamos una técnica similar a la utilizada en QuarkChain 9. Específicamente, para cada fragmento, el último bloque B y el último fragmento dentro de ese Se registra el bloque desde el cual se aplicaron los recibos. Cuando el nuevo fragmento esté creado, los recibos se aplican en orden primero a partir de los fragmentos restantes en B, y luego en bloques que siguen a B, hasta que el nuevo fragmento esté lleno. En condiciones normales circunstancias con una carga equilibrada, generalmente resultará en todos los recibos que se está aplicando (y por lo tanto, el último fragmento del último bloque se registrará para cada trozo), pero durante los momentos en que la carga no está equilibrada, y un particular Shard recibe una cantidad desproporcionada de recibos, esta técnica les permite procesarse respetando los límites en el número de transacciones incluidas. Tenga en cuenta que si dicha carga desequilibrada permanece durante mucho tiempo, el retraso desde la creación del recibo hasta que la aplicación pueda seguir creciendo indefinidamente. uno forma de abordarlo es descartar cualquier transacción que genere un recibo dirigido a un fragmento que tiene un retraso de procesamiento que excede alguna constante (por ejemplo, una época). Considere la figura 20. En el bloque B, el fragmento 4 no puede procesar todos los recibos, por lo que solo procesa el origen de los recibos desde hasta el fragmento 3 en el bloque A, y lo registra. En el bloque C se incluyen los recibos hasta el fragmento 5 del bloque B, y luego, en el bloque D, el fragmento se pone al día y procesa todos los recibos restantes en bloque B y todos los recibos del bloque C. 3.7 Validación de fragmentos Un fragmento producido para un fragmento en particular (o un bloque de fragmentos producido para una cadena de fragmentos particular en el modelo con cadenas de fragmentos) solo puede ser validado por el 9Vea el episodio de la pizarra con QuarkChain aquí: https://www.youtube.com/watch? v=opEtG6NM4x4, en el que se analiza el enfoque de las transacciones entre fragmentos, entre otros cosasFigura 20: Procesamiento de recibos retrasados participantes que mantienen el estado. Pueden ser productores de bloques, validators, o simplemente testigos externos que descargaron el estado y validaron el fragmento en donde almacenan activos. En este documento asumimos que la mayoría de los participantes no pueden almacenar al Estado una gran parte de los fragmentos. Vale la pena mencionar, sin embargo, que hay blockchains fragmentados que están diseñados con la suposición de que la mayoría de los participantes tienen capacidad para almacenar el estado y validar la mayoría de los fragmentos, como QuarkChain. Dado que solo una fracción de los participantes tiene el estado para validar el fragmento fragmentos, es posible corromper adaptativamente solo a los participantes que tienen la estado y aplicar una transición de estado no válida. Se propusieron múltiples diseños de fragmentación que muestrean validators cada pocos días, y dentro de un día cualquier bloque en la cadena de fragmentos que tenga más de 2/3 de firmas de los validator asignados a dicho fragmento se considera inmediatamente final. Con tal enfoque un adversario adaptativo sólo necesita corromper 2n/3+1 de los validators en una cadena de fragmentos para aplicar una transición de estado no válida, que, Aunque probablemente sea difícil de lograr, no es un nivel de seguridad suficiente para un público. blockchain. Como se analizó en la sección 2.3, el enfoque común es permitir una cierta ventana de tiempo después de que se crea un bloque para cualquier participante que tenga estado (ya sea es un productor de bloques, un validator o un observador externo) para cuestionar su validez. Estos participantes se llaman pescadores. Para que un pescador pueda impugnar un bloque no válido, se debe garantizar que dicho bloque esté disponible para ellos. La disponibilidad de datos en Nightshade se analiza en la sección 3.4. En Nightshade, una vez que se produce un bloque, los fragmentos no fueron validados por cualquiera excepto el productor de fragmentos real. En particular, el productor de bloques que sugirió que el bloque naturalmente no tenía el estado para la mayoría de los fragmentos, yno pudo validar los fragmentos. Cuando se produce el siguiente bloque, contiene certificaciones (consulte la sección 3.2) de múltiples productores de bloques y validators, pero dado que la mayoría de los productores de bloques y validators no mantienen el estado Además, para la mayoría de los fragmentos, un bloque con solo un fragmento no válido recopilará significativamente más de la mitad de las certificaciones y seguirá estando en la lista más pesada. cadena. Para abordar este problema, permitimos que cualquier participante que mantenga el estado de un fragmento para presentar un desafío en la cadena por cualquier fragmento no válido producido en ese fragmento. 3.7.1 Desafío de validez estatal Una vez que un participante detecta que un fragmento en particular no es válido, debe proporcionar una prueba de que el fragmento no es válido. Dado que la mayoría de los participantes de la red no mantienen el estado del fragmento en el que se encuentra el fragmento no válido producida, la prueba debe tener suficiente información para confirmar que el bloque es inválido sin tener el estado. Establecemos un límite Ls de la cantidad de estado (en bytes) que una sola transacción Puede leer o escribir de forma acumulativa. Cualquier transacción que toque más de Ls. El estado se considera inválido. Recuerde de la sección 3.5 que el trozo en un bloque particular B sólo contiene las transacciones a aplicar, pero no la nueva raíz estatal. La raíz del estado incluida en el fragmento del bloque B es el estado root antes de aplicar dichas transacciones, pero después de aplicar las transacciones de el último fragmento en el mismo fragmento antes del bloque B. Un actor malicioso que desea aplicar una transición de estado no válida incluiría una raíz de estado incorrecta en el bloque B que no corresponde al estado raíz que resulta de aplicar las transacciones en el fragmento anterior. Ampliamos la información que un productor de fragmentos incluye en el fragmento. En lugar de simplemente incluir el estado después de aplicar todas las transacciones, en su lugar incluye una raíz de estado después de aplicar cada conjunto contiguo de transacciones que leer y escribir colectivamente Ls bytes de estado. Con esta información para el pescador para crear un desafío que una transición de estado se aplica incorrectamente es suficiente encontrar la primera raíz de estado no válida e incluir solo Ls bytes de estado que se ven afectados por las transacciones entre la última raíz del estado (que fue válido) y la raíz del estado actual con las pruebas de merkle. Entonces cualquier participante puede validar las transacciones en el segmento y confirmar que el fragmento es inválido. De manera similar, si el productor del fragmento intentara incluir transacciones que leyeran y escribir más de Ls bytes de estado, para el desafío basta con incluir los primeros Ls bytes que toca con las pruebas merkle, que serán suficientes para aplicar las transacciones y confirmar que hay un momento en el que se intenta Se realiza lectura o escritura de contenido más allá de Ls bytes.

3.7.2 Pescadores y transacciones rápidas entre fragmentos. Como se analizó en la sección 2.3, una vez que asumimos que los fragmentos (o fragmentos) bloques en el modelo con cadenas de fragmentos) pueden no ser válidos e introducir un desafío período, afecta negativamente la finalidad y, por lo tanto, la comunicación entre fragmentos. en En particular, el fragmento de destino de cualquier transacción entre fragmentos no puede estar seguro el fragmento o bloque de origen es definitivo hasta que finaliza el período de desafío (ver figura 21). Figura 21: Esperar el período de impugnación antes de aplicar un recibo La forma de abordarlo de manera que se realicen transacciones entre fragmentos. instantáneo es que el fragmento de destino no espere el período de desafío después de que se publique la transacción del fragmento de origen y aplique la transacción del recibo inmediatamente, pero luego revertir el fragmento de destino junto con el origen fragmento si más tarde se descubre que el fragmento o bloque original no es válido (consulte la figura 22). Esto se aplica de forma muy natural al diseño Nightshade en el que el fragmento Las cadenas no son independientes, sino que todos los fragmentos se publican. juntos en el mismo bloque de cadena principal. Si se determina que algún fragmento no es válido, el todo el bloque con ese fragmento se considera inválido y todos los bloques construidos en él encima. Ver figura 23. Ambos enfoques anteriores proporcionan atomicidad suponiendo que el desafío el período es lo suficientemente largo. Usamos el último enfoque, ya que proporcionar transacciones rápidas entre fragmentos en circunstancias normales supera los inconvenientes de el fragmento de destino retrocede debido a una transición de estado no válida en uno de los fragmentos de origen, lo cual es un evento extremadamente raro. 3.7.3 Ocultar validators La existencia de los desafíos ya reduce significativamente la probabilidad de corrupción adaptativa, ya que para finalizar una parte con un estado de transición inválidoFigura 22: Aplicar recibos inmediatamente y revertir el destino cadena si la cadena fuente tenía un bloque no válido Figura 23: Desafío del pescador en Nightshade El período de desafío el adversario adaptativo necesita corromper a todos los participantes. que mantienen el estado del fragmento, incluidos todos los validator. Estimar la probabilidad de que ocurra tal evento es extremadamente complejo, ya que no sharded blockchain ha estado activo el tiempo suficiente para intentar cualquier ataque de este tipo. Sostenemos que la probabilidad, aunque extremadamente baja, sigue siendo suficientemente grande para un sistema que se espera que ejecute transacciones multimillonarias y ejecutar operaciones financieras a nivel mundial. Hay dos razones principales para esta creencia: 1. La mayoría de los validators de las cadenas de Prueba de Participación y mineros del

Las cadenas de prueba de trabajo están incentivadas principalmente por las ventajas financieras. si un adversario adaptativo les ofrece más dinero que el retorno esperado de operar honestamente, es razonable esperar que muchos validators aceptará la oferta. 2. Muchas entidades validan las cadenas de prueba de participación de manera profesional, y Se espera que un gran porcentaje de la participación en cualquier cadena sea de dichas entidades. El número de tales entidades es lo suficientemente pequeño para una adversario adaptativo para conocer a la mayoría de ellos personalmente y tener una buena comprensión de su inclinación a corromperse. Damos un paso más para reducir la probabilidad de corrupción adaptativa al ocultar qué validator están asignados a cada fragmento. La idea es remotamente similar a la forma en que Algorand [5] oculta validators. Es fundamental tener en cuenta que incluso si los validator están ocultos, como en Algorand o como se describe a continuación, la corrupción adaptativa todavía es posible en teoría. mientras El adversario adaptativo no conoce a los participantes que crearán o validarán. un bloque o un trozo, los propios participantes saben que realizarán tal tarea y tener una prueba criptográfica de ello. Así, el adversario puede difundir su intención de corromper y pagar a cualquier participante que proporcione tal prueba criptográfica. Sin embargo, observamos que dado que el adversario no conocen los validator que están asignados al fragmento que quieren corromper, no tienen otra opción que transmitir su intención de corromper un fragmento en particular a toda la comunidad. En ese punto es económicamente benéfico para cualquier persona honesta. participante para activar un nodo completo que valide ese fragmento, ya que hay un alto posibilidad de que aparezca un bloque no válido en ese fragmento, lo cual es una oportunidad para crea un desafío y recolecta la recompensa asociada. Para no revelar los validators que están asignados a un fragmento en particular, hacemos lo siguiente (ver figura 24): Usando VRF para obtener la tarea. Al comienzo de cada época cada validator usa un VRF para obtener una máscara de bits de los fragmentos a los que está asignado validator. La máscara de bits de cada validator tendrá bits Sw (consulte la sección 3.3 para conocer la definición de SW). Luego, el validator recupera el estado de los fragmentos correspondientes y durante la época para cada bloque recibido valida los fragmentos que corresponden a los fragmentos a los que está asignado el validator. Regístrate en bloques en lugar de trozos. Dado que la asignación de fragmentos está oculta, validator no puede firmar fragmentos. En cambio, siempre firma en todo el bloque, por lo que no revela qué fragmentos valida. Específicamente, cuando validator recibe un bloque y valida todos los fragmentos, crea un mensaje que atestigua que todos los fragmentos en todos los fragmentos a los que está asignado el validator son válido (sin indicar de ninguna manera cuáles son esos fragmentos), o un mensaje que contiene una prueba de una transición de estado no válida si algún fragmento no es válido. Ver el sección 3.8 para obtener detalles sobre cómo se agregan dichos mensajes, sección 3.7.4 para los detalles sobre cómo evitar que validators se aprovechen de los mensajes de otros validators, y la sección 3.7.5 para obtener detalles sobre cómo recompensar y castigar validators en caso de que realmente se produzca una impugnación exitosa de una transición de estado no válida.Figura 24: Ocultando los validators en Nightshade 3.7.4 Comprometerse-Revelar Uno de los problemas comunes con validators es que un validator puede omitir la descarga del estado y validar los fragmentos y bloques, y en su lugar observar la red, ver lo que envían los otros validators y repetir sus mensajes. Un validator que sigue dicha estrategia no proporciona ningún beneficio adicional. seguridad para la red, pero recoge recompensas. Una solución común para este problema es que cada validator proporcione una prueba que realmente validaron el bloque, por ejemplo proporcionando un seguimiento único de aplicar la transición estatal, pero tales pruebas aumentan significativamente el costo de validación. Figura 25: comprometerse-revelar

En su lugar, hacemos que los validators se comprometan por primera vez con el resultado de la validación (ya sea el mensaje que da fe de la validez de los fragmentos, o la prueba de una invalidez transición de estado), espere un cierto período y solo entonces revele el resultado de validación real, como se muestra en la figura 25. El período de confirmación no se cruza con el período de revelación y, por lo tanto, un validator perezoso no puede imitar a los validators honestos. Además, si un validator deshonesto se comprometió con un mensaje que da fe de la validez de los fragmentos asignados, y al menos un fragmento no era válido, una vez que se demostrado que el fragmento no es válido, validator no puede evitar la reducción, ya que, Como mostramos en la sección 3.7.5, la única manera de no ser cortado en tal situación es presentar un mensaje que contiene una prueba de la transición de estado no válida que coincide con el compromiso. 3.7.5 Manejando desafíos Como se analizó anteriormente, una vez que un validator recibe un bloque con un fragmento no válido, Primero preparan una prueba de la transición de estado no válida (ver sección 3.7.1), luego comprometerse con dicha prueba (ver 3.7.4) y después de un período revelar el desafío. Una vez incluido el desafío revelado en un bloque, sucede lo siguiente: 1. Todas las transiciones de estado que ocurrieron desde el bloque que contiene el fragmento no válido hasta que se obtenga el bloque en el que se incluye el desafío revelado. anulado. El estado ante el bloque que incluye el desafío revelado se considera el mismo que el estado anterior al bloque que contenía el trozo inválido. 2. Dentro de un cierto período de tiempo cada validator debe revelar su máscara de bits de los fragmentos que validan. Dado que la máscara de bits se crea a través de un VRF, si fueron asignados al fragmento que tenía la transición de estado no válida, No puedo evitar revelarlo. Cualquier validator que no revele la máscara de bits se supone que está asignado al fragmento. 3. Cada validator que después de dicho período se encuentre asignado al fragmento, que se comprometió con algún resultado de validación para el bloque que contiene el fragmento inválido y que no reveló la prueba de transición de estado inválido que corresponde a su compromiso se reduce. 4. Cada validator recibe una nueva asignación de fragmentos y se programa una nueva época. para comenzar después de un tiempo suficiente para que todos los validators descarguen el estado, como se muestra en la figura 26. Tenga en cuenta que desde el momento en que los validator revelan los fragmentos que se les asignan hasta que comienza la nueva época, la seguridad del sistema se reduce desde el Se revela la asignación de fragmentos. Los participantes de la red deben mantenerlo. en mente al utilizar la red durante dicho período. 3.8 Agregación de firmas Para que un sistema con cientos de fragmentos funcione de forma segura, queremos tener en el orden de 10, 000 o más validators. Como se discutió en la sección 3.7, queremos que cadaFigura 26: Manejando el desafío validator para publicar un compromiso con un determinado mensaje y una firma en promedio una vez por bloque. Incluso si los mensajes de confirmación fueran los mismos, agregar tal La firma BLS y su validación habrían sido prohibitivamente costosas. pero naturalmente, los mensajes de confirmación y revelación no son los mismos en validators, y por lo tanto necesitamos alguna forma de agregar dichos mensajes y las firmas en un forma que permita una validación rápida posterior. El enfoque específico que utilizamos es el siguiente: Validadores que se unen a productores de bloques. Los productores de bloques son conocidos. algún tiempo antes de que comience la época, ya que necesitan algo de tiempo para descargar el estado antes de que comience la época y, a diferencia de los validators, los productores de bloques son no oculto. Cada productor de bloques tiene v validator ranuras. Los validadores envían propuestas fuera de la cadena a los productores de bloques para ser incluidos como uno de sus v validators. Si un productor de bloques desea incluir un validator, envía un transacción que contiene la solicitud inicial fuera de la cadena del validator, y el firma del productor del bloque que hace que validator se una al productor del bloque. Tenga en cuenta que los validators asignados a los productores de bloques no necesariamente valide los mismos fragmentos para los que el productor de bloques produce fragmentos. si un validator se aplicó para unir múltiples productores de bloques, solo la transacción de el primer productor de bloques tendrá éxito. Los productores de bloques recopilan compromisos. El productor de bloques recopila constantemente los mensajes de confirmación y revelación de los validator. Una vez que se acumula una cierta cantidad de dichos mensajes, el productor del bloque calcula un merkle árbol de estos mensajes, y envía a cada validator la raíz de merkle y el camino merkle a su mensaje. El validator valida el camino y se registra la raíz de merkle. Luego, el productor del bloque acumula una firma BLS en el raíz de merkle de validators, y publica solo la raíz de merkle y el firma acumulada. El productor del bloque también firma sobre la validez del firma múltiple utilizando una firma ECDSA barata. Si la firma múltiple no coincide con la raíz de merkle enviada o la máscara de bits de los validators participantes, es un comportamiento que se puede recortar. Al sincronizar la cadena, un participante puede optar por validar todas las firmas BLS de validators (lo cual es extremadamente costoso ya que implica agregar las claves públicas de validators), o sololas firmas ECDMA de los productores de bloques y se basan en el hecho de que el El productor de bloques no fue cuestionado ni recortado. Uso de transacciones en cadena y pruebas merkle para desafíos. eso Se puede observar que no tiene ningún valor revelar mensajes de validators si no Se detectó una transición de estado no válida. Sólo los mensajes que contienen la información real Es necesario revelar pruebas de una transición de estado inválida, y sólo para tales mensajes. es necesario demostrar que coinciden con el compromiso anterior. El mensaje necesita ser revelado con dos propósitos: 1. Para iniciar realmente la reversión de la cadena al momento anterior al transición de estado no válida (ver sección 3.7.5). 2. Para demostrar que el validator no intentó dar fe de la validez del trozo no válido. En cualquier caso debemos abordar dos cuestiones: 1. El compromiso real no se incluyó en la cadena, solo la raíz merkle del confirmar agregado con otros mensajes. El validator necesita utilizar el ruta merkle proporcionada por el productor del bloque y su compromiso original con demostrar que se comprometieron con el desafío. 2. Es posible que todos los validator asignados al fragmento con el valor no válido La transición de estado se asigna a productores de bloques corruptos que los están censurando. Para evitarlo, les permitimos enviar sus revelaciones. como una transacción regular en cadena y evitar la agregación. Esto último sólo se permite para las pruebas de transición de estado inválida, que son extremadamente raro y, por lo tanto, no debería generar spam en los bloques. La última cuestión que debe abordarse es que los productores de bloques pueden optar por no participar en la agregación de mensajes o censurar intencionalmente validators concretos. Lo hacemos económicamente desventajoso al hacer que el bloque Recompensa al productor proporcional al número de validators que se les asignen. nosotros También tenga en cuenta que dado que los productores de bloques entre épocas se cruzan en gran medida (ya que siempre son los primeros w participantes con la apuesta más alta), los validators pueden atenerse en gran medida a trabajar con los mismos productores de bloques, y así reducir el riesgo de ser asignados a un productor de bloques que los censuró en el pasado. 3.9 Cadena de instantáneas Dado que los bloques de la cadena principal se producen con mucha frecuencia, descargar el historial completo podría resultar caro muy rápidamente. Es más, dado que cada El bloque contiene una firma BLS de una gran cantidad de participantes, solo la agregación de las claves públicas para verificar la firma podría resultar prohibitiva. caro también. Finalmente, dado que en un futuro previsible Ethereum 1.0 probablemente seguirá siendo uno de los blockchains más utilizados, que tiene una forma significativa de transferir activos desde

Cerca de Ethereum es un requisito y hoy se verifican las firmas BLS para garantizar La validez de bloques cercanos en el lado de Ethereum no es posible. Cada bloque de la cadena principal de Nightshade puede contener opcionalmente un Schnorr firma múltiple en el encabezado del último bloque que incluía dicho Schnorr multifirma. A estos bloques los llamamos bloques instantáneos. El primer bloque de cada época debe ser un bloque de instantáneas. Mientras trabajaba en una firma múltiple de este tipo, los productores de bloques también deben acumular las firmas BLS de los validators en el último bloque de instantáneas y agréguelas de la misma manera que se describe en sección 3.8. Dado que el conjunto de productores de bloques es constante a lo largo de la época, validar sólo los primeros bloques de instantáneas en cada época son suficientes suponiendo que en ningún momento punto, un gran porcentaje de productores de bloques y validators se confabularon y crearon un tenedor. El primer bloque de la época debe contener información suficiente para calcular los productores de bloques y validators para la época. Llamamos a la subcadena de la cadena principal que solo contiene la instantánea. bloquea una cadena de instantáneas. Crear una firma múltiple de Schnorr es un proceso interactivo, pero como Sólo es necesario realizarlo con poca frecuencia, cualquier proceso, por ineficiente que sea, será suficiente. Las firmas múltiples de Schnorr se pueden validar fácilmente en Ethereum, proporcionando así primitivas cruciales para una forma segura de realizar cross-blockchain comunicación. Para sincronizar con la cadena Near solo es necesario descargar toda la instantánea. bloquea y confirma que las firmas Schnorr son correctas (opcionalmente, también verifica las firmas BLS individuales de los validators), y luego solo sincroniza bloques de la cadena principal desde el último bloque de instantánea.

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.

Conclusión

En este documento analizamos enfoques para crear blockchains fragmentados y cubrió dos desafíos principales con los enfoques existentes, a saber, la validez del estado y disponibilidad de datos. Luego presentamos Nightshade, un diseño de fragmentación que poderes NEAR Protocolo. El diseño es un trabajo en progreso, si tiene comentarios, preguntas o comentarios en este documento, vaya a https://near.chat.