O Livro Branco do NEAR

Nightshade: Near Protocol Sharding Design

Von Alex Skidanov and Illia Polosukhin · 2019

🇺🇸 English (Original)

🇧🇷 Português (Übersetzung)

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.

Noções básicas de fragmentação

Vamos começar com a abordagem mais simples de fragmentação. Nesta abordagem, em vez de executando um blockchain, executaremos vários e chamaremos cada um desses blockchain de “fragmento”. Cada fragmento terá seu próprio conjunto de validators. Aqui e abaixo usamos um termo genérico “validator” para se referir aos participantes que verificam transações e produzir blocos, seja por mineração, como em Prova de Trabalho, ou por meio de votação 1Esta seção foi publicada anteriormente em https://near.ai/shard1. Se você leu antes, pule para a próxima seção.

mecanismo. Por enquanto, vamos supor que os fragmentos nunca se comuniquem entre si outro. Este design, embora simples, é suficiente para delinear alguns grandes desafios iniciais na fragmentação. 1.1 Particionamento de validador e cadeias de beacon Digamos que o sistema compreenda 10 fragmentos. O primeiro desafio é que com cada shard tendo seus próprios validators, cada shard agora é 10 vezes menos seguro que o cadeia inteira. Portanto, se uma cadeia não fragmentada com X validators decidir fazer um hard fork em uma cadeia de fragmentos e divide X validators em 10 fragmentos, cada fragmento agora tem apenas X/10 validators, e corromper um fragmento requer apenas corromper 5,1% (51%/10) do número total de validators (ver figura 1), Figura 1: Dividindo os validators entre fragmentos o que nos leva ao segundo ponto: quem escolhe validators para cada fragmento? Controlar 5,1% de validators só será prejudicial se todos esses 5,1% de validators estão no mesmo fragmento. Se validators não puderem escolher qual fragmento eles validarão em, é altamente improvável que um participante que controle 5,1% dos validators obtenha todos seus validators no mesmo fragmento, reduzindo fortemente sua capacidade de comprometer o sistema. Quase todos os designs de sharding hoje dependem de alguma fonte de aleatoriedade para atribua validators aos fragmentos. A aleatoriedade em blockchain por si só é um tópico muito desafiador e está fora do escopo deste documento. Por enquanto vamos supor que haja alguma fonte de aleatoriedade que possamos usar. Abordaremos a tarefa de validator em mais detalhes na seção 2.1. Tanto a aleatoriedade quanto a atribuição validator requerem computação que não é específico para qualquer fragmento em particular. Para esse cálculo, praticamente todos os existentes projetos têm um blockchain separado encarregado de executar operações necessário para a manutenção de toda a rede. Além de gerar aleatoriamentenúmeros e atribuindo validators aos fragmentos, essas operações geralmente também incluem receber atualizações de fragmentos e tirar instantâneos deles, processar apostas e cortes em sistemas de prova de aposta e rebalanceamento de fragmentos quando isso recurso é suportado. Essa cadeia é chamada de cadeia Beacon em Ethereum, uma cadeia de relé cadeia em PolkaDot e o Hub Cosmos em Cosmos. Ao longo deste documento nos referiremos a essa cadeia como cadeia Beacon. A existência da cadeia Beacon nos leva ao próximo tópico interessante, o fragmentação quadrática. 1.2 Fragmentação quadrática A fragmentação é frequentemente anunciada como uma solução que se adapta infinitamente ao número de nós participantes da operação da rede. Embora seja em teoria possível projetar tal solução de sharding, qualquer solução que tenha o conceito de Beacon cadeia não tem escalabilidade infinita. Para entender o porquê, observe que o Beacon chain precisa fazer alguns cálculos contábeis, como atribuir validators a fragmentos, ou instantâneos de blocos de cadeia de fragmentos, que são proporcionais ao número de fragmentos no sistema. Como a própria cadeia Beacon é um único blockchain, com computação limitada pelas capacidades computacionais dos nós que a operam, o número de fragmentos é naturalmente limitado. No entanto, a estrutura de uma rede fragmentada confere um efeito multiplicativo afetará quaisquer melhorias em seus nós. Considere o caso em que um arbitrário melhoria é feita na eficiência dos nós da rede, o que permitirá proporcionando tempos de processamento de transações mais rápidos. Se os nós que operam a rede, incluindo os nós da cadeia Beacon, se tornar quatro vezes mais rápido, então cada fragmento será capaz de processar quatro vezes mais transações, e a cadeia Beacon será capaz de manter 4 vezes mais fragmentos. A taxa de transferência em todo o sistema aumentará pelo fator de 4 × 4 = 16 — daí o nome fragmentação quadrática. É difícil fornecer uma medida precisa de quantos fragmentos estão viável hoje, mas é improvável que num futuro próximo o rendimento as necessidades dos usuários blockchain superarão as limitações da fragmentação quadrática. O grande número de nós necessários para operar tal volume de fragmentos com segurança é provavelmente ordens de magnitude maior do que o número de nós operando em todos os blockchains combinados hoje. 1.3 Fragmentação de estado Até agora não definimos muito bem o que exatamente é e o que não é separado quando uma rede é dividida em fragmentos. Especificamente, nós no blockchain realizam três tarefas importantes: eles não apenas 1) processam transações, eles também 2) retransmitir transações validadas e blocos concluídos para outros nós e 3) armazenar o estado e o histórico de todo o livro-razão da rede. Cada um desses três tarefas impõe uma exigência crescente aos nós que operam a rede:1. A necessidade de processar transações requer mais poder computacional com o aumento do número de transações processadas; 2. A necessidade de retransmitir transações e blocos requer mais largura de banda de rede com o aumento do número de transações retransmitidas; 3. A necessidade de armazenar dados exige mais armazenamento à medida que o estado cresce. É importante ressaltar que, diferentemente do poder de processamento e da rede, a necessidade de armazenamento aumenta mesmo que a taxa de transação (número de transações processadas por segundo) permanece constante. Da lista acima pode parecer que o requisito de armazenamento seria o mais urgente, pois é o único que vem aumentando ao longo do tempo mesmo que o número de transações por segundo não mude, mas na prática o requisito mais urgente hoje é o poder de computação. Todo o estado de Ethereum no momento em que este livro foi escrito tinha 100 GB, facilmente gerenciável pela maioria dos nós. Mas o número de transações que Ethereum pode processar é cerca de 20, ordens de magnitude menor do que o necessário para muitos casos de uso prático. Zilliqa é o projeto mais conhecido que fragmenta o processamento, mas não o armazenamento. A fragmentação do processamento é um problema mais fácil porque cada nó possui todo o estado, o que significa que os contratos podem invocar livremente outros contratos e ler quaisquer dados do blockchain. É necessária alguma engenharia cuidadosa para garantir atualizações de vários fragmentos atualizando as mesmas partes do estado não entram em conflito. Em nestes aspectos, Zilliqa está a adoptar uma abordagem relativamente simplista2. Embora tenha sido proposta a fragmentação do armazenamento sem a fragmentação do processamento, é extremamente incomum. Assim, na prática, a fragmentação de armazenamento, ou fragmentação de estado, quase sempre implica fragmentação de processamento e fragmentação de rede. Praticamente, no State Sharding, os nós em cada shard estão construindo seus próprio blockchain que contém transações que afetam apenas a parte local do estado global atribuído a esse fragmento. Portanto, os validators no o fragmento só precisa armazenar sua parte local do estado global e apenas executar, e, como tal, apenas retransmitem transações que afetam a sua parte do Estado. Isto partição reduz linearmente o requisito de todo o poder de computação, armazenamento e largura de banda da rede, mas introduz novos problemas, como disponibilidade de dados e transações entre fragmentos, ambas abordadas abaixo. 1.4 Transações entre fragmentos O modelo de fragmentação que descrevemos até agora não é muito útil, porque se fragmentos não podem se comunicar entre si, eles não são melhores do que vários blockchains independentes. Ainda hoje, quando a fragmentação não está disponível, há uma enorme demanda por interoperabilidade entre vários blockchains. Por enquanto, vamos considerar apenas transações de pagamento simples, onde cada participante possui conta em exatamente um fragmento. Se alguém deseja transferir dinheiro de 2Nossa análise de sua abordagem pode ser encontrada aqui: https://medium.com/nearprotocol/ 8f9efa0ce3buma conta para outra dentro do mesmo fragmento, a transação pode ser processada inteiramente pelos validators naquele fragmento. Se, no entanto, Alice que reside no fragmento

1 deseja enviar dinheiro para Bob, que reside no fragmento #2, nem validators

no fragmento nº 1 (eles não poderão creditar a conta de Bob) nem os validators em o fragmento nº 2 (eles não poderão debitar a conta de Alice) pode processar todo o transação. Existem duas famílias de abordagens para transações entre fragmentos: • Síncrono: sempre que uma transação entre fragmentos precisa ser executada, os blocos em vários fragmentos que contêm transição de estado relacionada ao a transação é produzida ao mesmo tempo, e os validators de vários fragmentos colaboram na execução de tais transações.3 • Assíncrona: uma transação entre fragmentos que afeta vários fragmentos é executado nesses fragmentos de forma assíncrona, o fragmento “Crédito” em execução sua metade assim que tiver evidências suficientes de que o fragmento “Débito” executou sua parte. Esta abordagem tende a ser mais prevalente devido à sua simplicidade e facilidade de coordenação. Este sistema é hoje proposto em Cosmos, Ethereum Serenity, Near, Kadena e outros. Um problema com isso abordagem reside no fato de que, se os blocos forem produzidos independentemente, há uma chance diferente de zero de que um dos vários blocos fique órfão, tornando assim a transação foi aplicada apenas parcialmente. Considere a figura 2 que representa dois fragmentos que encontraram uma bifurcação e uma transação entre fragmentos que foi registrado nos blocos A e X’ correspondentemente. Se as cadeias A-B e V'-X'-Y'-Z' acabam sendo canônicos nos fragmentos correspondentes, o a transação está totalmente finalizada. Se A'-B'-C'-D' e V-X se tornarem canônicos, então a transação é totalmente abandonada, o que é aceitável. Mas se, por Por exemplo, A-B e V-X tornam-se canônicos, então uma parte da transação é finalizada e a outra é abandonada, criando uma falha de atomicidade. Nós abordará como esse problema é abordado nos protocolos propostos na segunda parte, ao cobrir mudanças nas regras de escolha bifurcada e no consenso algoritmos propostos para protocolos fragmentados. Observe que a comunicação entre cadeias é útil fora de blockchains fragmentados também. A interoperabilidade entre cadeias é um problema complexo que muitos projetos estão tentando resolver. Em blockchains fragmentados, o problema é um pouco mais fácil, pois a estrutura do bloco e o consenso são os mesmos entre os fragmentos e há uma cadeia de beacons que pode ser usada para coordenação. Em um blockchain fragmentado, no entanto, todas as cadeias de fragmentos são iguais, enquanto no ecossistema global blockchains existe existem muitos blockchains diferentes, com diferentes casos de uso alvo, descentralização e garantias de privacidade. Construir um sistema no qual um conjunto de cadeias tem propriedades diferentes, mas usar consenso e estrutura de bloco suficientemente semelhantes e ter uma cadeia de beacon comum poderia permitir um ecossistema de blockchains heterogêneos que têm um 3O mais detalhado proposta conhecido para o autores de isso documento é Mesclar Blocos, descrito aqui: https://ethresear.ch/t/ merge-blocks-and-synchronous-cross-shard-state-execution/1240Figura 2: Transações assíncronas entre fragmentos subsistema de interoperabilidade funcional. É improvável que tal sistema apresente rotação validator, portanto, algumas medidas extras precisam ser tomadas para garantir a segurança. Ambos Cosmos e PolkaDot são efetivamente esses sistemas4 1,5 Comportamento malicioso Nesta seção, revisaremos qual comportamento adversário pode validators maliciosos exercício se conseguirem corromper um fragmento. Revisaremos abordagens clássicas para evitar a corrupção de fragmentos na seção 2.1. 1.5.1 Garfos maliciosos Um conjunto de validators maliciosos pode tentar criar uma bifurcação. Observe que isso não importa se o consenso subjacente é BFT ou não, corrompendo um número suficiente de validators sempre possibilitará a criação de um fork. É significativamente mais provável que mais de 50% de um único fragmento seja corrompido do que mais de 50% de toda a rede seja corrompida (vamos aprofunde-se nessas probabilidades na seção 2.1). Conforme discutido na seção 1.4, transações entre fragmentos envolvem certas mudanças de estado em vários fragmentos e os blocos correspondentes em tais fragmentos que aplicam tais mudanças de estado devem ser todos finalizados (ou seja, aparecer nas cadeias selecionadas em seus correspondentes fragmentos), ou todos serão órfãos (ou seja, não aparecerão nas cadeias selecionadas em seus fragmentos correspondentes). Como geralmente a probabilidade de os fragmentos serem corrompidos 4Consulte este artigo de Zaki Manian de Cosmos: https://forum.cosmos.network/ t/polkadot-vs-cosmos/1397/2 e esta tempestade de tweets do primeiro autor deste documento: https://twitter.com/AlexSkidanov/status/1129511266660126720 para uma comparação detalhada dos dois

não é insignificante, não podemos presumir que as bifurcações não acontecerão mesmo se um consenso bizantino for alcançado entre os fragmentos validators, ou se muitos blocos forem produzido no topo do bloco com a mudança de estado. Este problema tem múltiplas soluções, sendo a mais comum a ocasional ligação cruzada do bloco de cadeia de shard mais recente à cadeia de beacon. O garfo a regra de escolha nas cadeias de fragmentos é então alterada para sempre preferir a cadeia que é reticulado e aplica apenas a regra de escolha de bifurcação específica do shard para blocos que foram publicados desde a última ligação cruzada. 1.5.2 Aprovando blocos inválidos Um conjunto de validators pode tentar criar um bloco que aplique a função de transição de estado incorretamente. Por exemplo, começando com um estado em que Alice tem 10 tokens e Bob tem 0 tokens, o bloco pode conter uma transação que envia 10 tokens de Alice para Bob, mas termina com um estado em que Alice tem 0 tokens e Bob tem 1000 tokens, conforme mostrado na figura 3. Figura 3: Um exemplo de bloco inválido Em um blockchain clássico não fragmentado, tal ataque não é possível, uma vez que todos o participante da rede valida todos os blocos, e o bloco com tal uma transição de estado inválida será rejeitada por ambos os outros produtores de blocos, e os participantes da rede que não criam blocos. Mesmo que o malicioso validators continuam criando blocos em cima de um bloco inválido mais rápido do que validators honestos constroem a cadeia correta, tendo assim a cadeia com o inválido bloco sendo mais longo, não importa, pois cada participante que estiver usando o blockchain para qualquer finalidade valida todos os blocos e descarta todos os blocos construído em cima do bloco inválido. Na figura 4 existem cinco validators, três dos quais são maliciosos. Eles criou um bloco A’ inválido e continuou construindo novos blocos no topo disso. Dois validators honestos descartaram A’ como inválido e estavam construindo em cimaFigura 4: Tentativa de criar um bloco inválido em um blockchain não fragmentado do último bloco válido conhecido por eles, criando uma bifurcação. Como há menos validators na bifurcação honesta, sua cadeia é mais curta. No entanto, no blockchain clássico não fragmentado, todo participante que usa blockchain para qualquer finalidade é responsável por validar todos os blocos que recebe e recalcular o estado. Assim, qualquer pessoa que tenha algum interesse no blockchain observaria que A’ é inválido e, portanto, também descarta imediatamente B', C' e D', como tal, tomando o cadeia AB como a cadeia válida mais longa atual. Em um blockchain fragmentado, entretanto, nenhum participante pode validar todas as transações em todos os fragmentos, então eles precisam ter alguma forma de confirmar que em nenhum ponto na história de qualquer fragmento de blockchain nenhum bloco inválido foi incluído. Observe que, diferentemente dos forks, a ligação cruzada com a cadeia Beacon não é uma solução suficiente, uma vez que a cadeia Beacon não tem a capacidade de validar a cadeia Beacon. blocos. Ele só pode validar que há um número suficiente de validators naquele fragmento assinou o bloco (e como tal atestou a sua veracidade). Discutiremos soluções para este problema na seção 2.2 abaixo.

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.

Validade estadual e disponibilidade de dados

A ideia central em blockchains fragmentados é que a maioria dos participantes operando ou usar a rede não pode validar blocos em todos os shards. Como tal, sempre que qualquer participante precisa interagir com um fragmento específico, eles geralmente não podem baixe e valide todo o histórico do shard. O aspecto de particionamento do sharding, no entanto, levanta um potencial significativo problema: sem baixar e validar todo o histórico de um determinado fragmento, o participante não pode necessariamente ter certeza de que o estado com o qual 5Esta seção, exceto a subseção 2.5.3, foi publicada anteriormente em https://near.ai/ fragmento2. Se você leu antes, pule para a próxima seção.

eles interagem é o resultado de alguma sequência válida de blocos e que tal sequência de blocos é de fato a cadeia canônica no fragmento. Um problema que não existe em um blockchain não fragmentado. Apresentaremos primeiro uma solução simples para este problema que foi proposta por muitos protocolos e depois analisar como essa solução pode falhar e o que foram feitas tentativas para resolvê-lo. 2.1 Rotação de validadores A solução ingênua para a validade do estado é mostrada na figura 5: digamos que assumimos que todo o sistema possui da ordem de milhares de validators, dos quais não mais do que 20% são maliciosos ou irão falhar de outra forma (como por não serem online para produzir um bloco). Então, se amostrarmos 200 validators, a probabilidade de mais de 1 3 a falha para fins práticos pode ser assumida como zero. Figura 5: Amostragem de validators 1 3 é um limite importante. Existe uma família de protocolos de consenso, chamada BFT protocolos de consenso, que garantem que por menos de 1 3 de participantes falham, seja por bater ou por agir de alguma forma que viole o protocolo, o consenso será alcançado. Com esta suposição de porcentagem honesta de validator, se o conjunto atual de validators em um fragmento nos fornece algum bloqueio, a solução ingênua assume que o bloco é válido e que é construído sobre o que os validators acreditam ser a cadeia canônica desse fragmento quando eles começaram a validar. Os validators aprendeu a cadeia canônica do conjunto anterior de validators, que pelo mesmo suposição construída no topo do bloco que era o topo da cadeia canônica antes disso. Por indução, toda a cadeia é válida e, como nenhum conjunto de validators em qualquer ponto produziu garfos, a solução ingênua também é certa de que o atual chain é a única cadeia no fragmento. Veja a figura 6 para uma visualização.

Figura 6: Um blockchain com cada bloco finalizado via consenso BFT Esta solução simples não funciona se assumirmos que os validators podem ser corrompido adaptativamente, o que não é uma suposição irracional6. Adaptativamente corromper um único fragmento em um sistema com 1.000 fragmentos é significativamente mais barato do que corromper todo o sistema. Portanto, a segurança do protocolo diminui linearmente com o número de shards. Para ter certeza da validade um bloco, devemos saber que em qualquer momento da história nenhum fragmento do sistema foi a maioria dos validators conspirando; com adversários adaptativos, não temos mais tanta certeza. Como discutimos na seção 1.5, validators coniventes podem exercer dois comportamentos maliciosos básicos: criar bifurcações e produzir blocos inválidos. Forks maliciosos podem ser resolvidos por blocos interligados à cadeia Beacon, que geralmente é projetada para ter segurança significativamente maior do que as cadeias de fragmentos. Produzir blocos inválidos, no entanto, é uma tarefa significativamente mais problema desafiador para resolver. 2.2 Validade do Estado Considere a figura 7 na qual o fragmento nº 1 está corrompido e um agente malicioso produz bloco inválido B. Suponha que neste bloco B 1000 tokens foram cunhados ir ao ar por conta de Alice. O ator malicioso então produz o bloco C válido (em um sentido de que as transações em C são aplicadas corretamente) em cima de B, ofuscando o bloco inválido B e inicia uma transação entre fragmentos para o fragmento #2 que transfere esses 1.000 tokens para a conta de Bob. A partir deste momento o indevidamente tokens criados residem em um blockchain completamente válido no fragmento #2. Algumas abordagens simples para resolver esse problema são: 6Leia isso artigo para detalhes ligado como adaptativo corrupção pode ser carregado fora: https://medium.com/nearprotocol/d859adb464c8. Para mais detalhes ligado adaptativo corrupção, leia https://github.com/ethereum/wiki/wiki/Sharding-FAQ# quais são os modelos de segurança sob os quais estamos operandoFigura 7: Uma transação entre fragmentos de uma cadeia que possui um bloco inválido 1. Para validators do Shard #2 para validar o bloco do qual a transação é iniciado. Isso não funcionará nem no exemplo acima, pois o bloco C parece ser completamente válido. 2. Para validators no Shard #2 para validar um grande número de blocos anteriores ao bloco a partir do qual a transação é iniciada. Naturalmente, por qualquer número de blocos N validados pelo fragmento receptor do malicioso validators podem criar N+1 blocos válidos em cima do bloco inválido que eles produzido. Uma ideia promissora para resolver esse problema seria organizar os fragmentos em um gráfico não direcionado em que cada fragmento está conectado a vários outros fragmentos, e permitir apenas transações entre fragmentos vizinhos (por exemplo, é assim que A fragmentação de Vlad Zamﬁr funciona essencialmente7, e uma ideia semelhante é usada na fragmentação de Kadena. Chainweb [1]). Se uma transação entre fragmentos for necessária entre fragmentos que são não vizinhos, tal transação é roteada através de vários fragmentos. Neste projeto espera-se que um validator em cada fragmento valide todos os blocos em seu fragmento bem como todos os blocos em todos os fragmentos vizinhos. Considere uma figura abaixo com 10 fragmentos, cada um com quatro vizinhos, e não há dois fragmentos que exijam mais mais de dois saltos para uma comunicação entre fragmentos mostrada na figura 8. O fragmento nº 2 não está apenas validando seu próprio blockchain, mas também blockchains de todos os vizinhos, incluindo o Shard #1. Então, se um ator malicioso no Shard #1 está tentando criar um bloco B inválido e, em seguida, construir o bloco C sobre ele e iniciar uma transação entre fragmentos, tal transação entre fragmentos não ocorrerá desde o Shard #2 terá validado toda a história do Shard #1 que fará com que ele identifique o bloco B inválido. 7Leia mais sobre o design aqui: https://medium.com/nearprotocol/37e538177ed9

Figura 8: Uma transação cruzada inválida em um sistema tipo chainweb que irá ser detectado Embora corromper um único fragmento não seja mais um ataque viável, corromper um poucos fragmentos continuam sendo um problema. Na figura 9, um adversário corrompendo ambos os Shard

1 e Shard #2 executam com sucesso uma transação entre fragmentos para o Shard #3

com fundos de um bloco B inválido: Figura 9: Uma transação cruzada inválida em um sistema tipo chainweb que irá não ser detectado O Shard #3 valida todos os blocos no Shard #2, mas não no Shard #1, e não tem como detectar o bloco malicioso. Existem duas direções principais para resolver adequadamente a validade do estado: os pescadores

e provas criptográficas de computação. 2.3 Pescador A ideia por trás da primeira abordagem é a seguinte: sempre que um cabeçalho de bloco é comunicado entre cadeias para qualquer finalidade (como ligação cruzada com o cadeia de beacon ou uma transação entre fragmentos), há um período de tempo durante qual qualquer validator honesto pode fornecer uma prova de que o bloqueio é inválido. Lá são diversas construções que permitem provas muito sucintas de que os blocos são inválido, então a sobrecarga de comunicação para os nós receptores é bem menor do que receber um bloco completo. Com esta abordagem, enquanto houver pelo menos um validator honesto no fragmento, o sistema é seguro. Figura 10: Pescador Esta é a abordagem dominante (além de fingir que o problema não existe) entre os protocolos propostos hoje. Esta abordagem, no entanto, tem duas principais desvantagens: 1. O período de desafio precisa ser suficientemente longo para o honesto validator reconhecer que um bloco foi produzido, baixá-lo, verificá-lo completamente e preparar o desafio se o bloco for inválido. A introdução de tal período seria retardar significativamente as transações entre fragmentos. 2. A existência do protocolo de desafio cria um novo vetor de ataques quando nós maliciosos enviam spam com desafios inválidos. Uma solução óbvia para este problema é fazer com que os desafiantes depositem alguma quantia de tokens que são retornados se o desafio for válido. Esta é apenas uma solução parcial, pois ainda pode ser benéfico para o adversário enviar spam ao sistema (e queimar os depósitos) com desafios inválidos, por exemplo, para evitar o válidodesafio de um validator honesto de passar. Esses ataques são chamados ataques de luto. Consulte a seção 3.7.2 para saber como contornar o último ponto. 2.4 Argumentos de conhecimento sucintos e não interativos A segunda solução para a corrupção de múltiplos fragmentos é usar algum tipo de construção criptográfica que permita provar que um determinado cálculo (como como calcular um bloco de um conjunto de transações) foi realizado corretamente. Tais construções existem, por ex. zk-SNARKs, zk-STARKs e alguns outros, e alguns são usados ativamente em protocolos blockchain hoje para pagamentos privados, mais notavelmente ZCash. O principal problema com tais primitivas é que elas são notoriamente lentos para calcular. Por exemplo Protocolo Coda, que usa zk-SNARKs especificamente para provar que todos os blocos em blockchain são válidos, dito em um das entrevistas que pode levar 30 segundos por transação para criar uma prova (este número provavelmente é menor agora). Curiosamente, uma prova não precisa ser computada por uma parte confiável, uma vez que a prova não apenas atesta a validade do cálculo para o qual foi construída, mas também a validade da própria prova. Assim, o cálculo de tais provas pode ser dividido entre um conjunto de participantes com significativamente menos redundância do que seria necessário para realizar alguma computação sem confiança. Também permite aos participantes que computam zk-SNARKs para rodar em hardware especial sem reduzir o descentralização do sistema. Os desafios dos zk-SNARKs, além do desempenho, são: 1. Dependência de primitivas criptográficas menos pesquisadas e testadas ao longo do tempo; 2. “Resíduos tóxicos” – zk-SNARKs dependem de uma configuração confiável na qual um grupo de pessoas realiza alguns cálculos e depois descarta o intermediário valores desse cálculo. Se todos os participantes do procedimento conspirarem e manter os valores intermediários, podem ser criadas provas falsas; 3. Complexidade extra introduzida no design do sistema; 4. zk-SNARKs funcionam apenas para um subconjunto de cálculos possíveis, portanto, um protocolo com uma linguagem Turing-completa smart contract não seria capaz de usar SNARKs para provar a validade da cadeia. 2,5 Disponibilidade de dados O segundo problema que abordaremos é a disponibilidade de dados. Geralmente nós operando um determinado blockchain são separados em dois grupos: Full Nodes, aqueles que baixam cada bloco completo e validam cada transação, e Light Nós, aqueles que baixam apenas cabeçalhos de bloco e usam provas Merkle para peças do estado e das transações nas quais estão interessados, conforme mostrado na figura 11.

Figura 11: Árvore Merkel Agora, se a maioria dos nós completos conspirar, eles podem produzir um bloco, válido ou inválido e envia seu hash para os nós leves, mas nunca divulga o conteúdo completo do bloco. Existem várias maneiras pelas quais eles podem se beneficiar disso. Por exemplo, considere a figura 12: Figura 12: Problema de disponibilidade de dados Existem três blocos: o anterior, A, é produzido por validators honestos; o atual, B, tem validators conspirando; e o próximo, C, também será produzido por validators honestos (o blockchain está representado no canto inferior direito). Você é um comerciante. Os validators do bloco atual (B) receberam o bloco A dos validators anteriores, calculou um bloco no qual você recebe dinheiro,e enviei a você um cabeçalho desse bloco com uma prova Merkle do estado em que você tem dinheiro (ou uma prova Merkle de uma transação válida que envia o dinheiro para você). Confiante de que a transação foi finalizada, você fornece o serviço. Porém, os validators nunca distribuem o conteúdo completo do bloco B para qualquer um. Como tal, os validators honestos do bloco C não podem recuperar o bloco e são forçados a paralisar o sistema ou a construir em cima de A, privando você como comerciante de dinheiro. Quando aplicamos o mesmo cenário à fragmentação, as definições de completo e nó leve geralmente se aplica por fragmento: validators em cada download de fragmento a cada bloquear nesse fragmento e validar todas as transações nesse fragmento, mas outros nós no sistema, incluindo aqueles que capturam o estado das cadeias de fragmentos no cadeia de beacon, baixe apenas os cabeçalhos. Assim, os validators no fragmento são nós efetivamente completos para esse fragmento, enquanto outros participantes do sistema, incluindo a cadeia de beacon, operam como nós leves. Para que a abordagem do pescador que discutimos acima funcione, validators honestos precisa ser capaz de baixar blocos que estão interligados à cadeia de beacon. Se validators maliciosos vinculassem um cabeçalho de um bloco inválido (ou o usassem para iniciar uma transação entre fragmentos), mas nunca distribuiu o bloco, o honesto validators não têm como criar um desafio. Abordaremos três abordagens para resolver este problema que complementam um ao outro. 2.5.1 Provas de Custódia O problema mais imediato a ser resolvido é se um bloco estará disponível uma vez está publicado. Uma ideia proposta é ter os chamados Notários que façam rodízio entre fragmentos com mais frequência do que validators cuja única tarefa é baixar um bloquear e atestar que eles conseguiram baixá-lo. Eles podem ser girados com mais frequência porque não precisam baixar o estado inteiro do fragmento, ao contrário dos validators que não podem ser girados com frequência, pois devem baixar o estado do shard cada vez que eles giram, conforme mostrado na figura 13. O problema com esta abordagem ingénua é que é impossível provar mais tarde se o Tabelião conseguiu ou não fazer o download do bloco, então um Tabelião podem optar por sempre atestar que conseguiram baixar o bloco sem mesmo tentando recuperá-lo. Uma solução para isto é os Notários fornecerem alguma evidência ou apostar alguma quantidade de tokens atestando que o bloco foi baixado. Uma dessas soluções é discutida aqui: https://ethresear.ch/t/ Títulos de custódia compatíveis com agregação de 1 bit/2236. 2.5.2 Códigos de apagamento Quando um determinado nó light recebe um hash de um bloco, para aumentar a capacidade do nó confiança de que o bloco está disponível, ele pode tentar baixar alguns blocos aleatórios. pedaços do bloco. Esta não é uma solução completa, pois a menos que os nós de luz baixar coletivamente o bloco inteiro que os produtores de blocos maliciosos podem escolher

Figura 13: Os validadores precisam baixar o estado e, portanto, não podem ser girados frequentemente reter as partes do bloco que não foram baixadas por nenhum light node, assim ainda tornando o bloco indisponível. Uma solução é usar uma construção chamada Erasure Codes para tornar possível para recuperar o bloco completo mesmo que apenas uma parte do bloco esteja disponível, conforme mostrado na figura 14. Figura 14: Merkle tree criado com base em dados codificados para eliminação Tanto Polkadot quanto Ethereum Serenity têm designs em torno dessa ideia de que fornecer uma maneira para que os nós leves tenham confiança razoável de que os blocos estão disponíveis. A abordagem Ethereum Serenity tem uma descrição detalhada em [2].2.5.3 Abordagem de Polkadot para disponibilidade de dados Em Polkadot, como na maioria das soluções fragmentadas, cada fragmento (chamado parachain) captura seus blocos na cadeia de beacon (chamada cadeia de retransmissão). Digamos que existem 2f + 1 validators na cadeia de retransmissão. Os produtores de blocos de parachain, chamados agrupadores, uma vez que o bloco parachain é produzido, calcule uma versão codificada para apagamento do bloco que consiste em 2f +1 partes, de modo que quaisquer f partes sejam suficientes para reconstruir o bloco. Eles então distribuem uma parte para cada validator no cadeia de relé. Uma cadeia de retransmissão específica validator só assinaria em uma cadeia de retransmissão bloco se eles tiverem sua parte para cada bloco parachain que é capturado para tal bloco de cadeia de relé. Assim, se um bloco de cadeia de relés tiver assinaturas de 2f + 1 validators, e enquanto não mais do que f deles violarem o protocolo, cada o bloco parachain pode ser reconstruído buscando as partes dos validators que seguem o protocolo. Veja a figura 15. Figura 15: Disponibilidade de dados de Polkadot 2.5.4 Disponibilidade de dados a longo prazo Observe que todas as abordagens discutidas acima apenas atestam o fato de que um bloco foi publicado e está disponível agora. Os blocos podem ficar indisponíveis posteriormente por vários motivos: nós ficando off-line, nós apagando intencionalmente o histórico dados e outros. Um whitepaper que vale a pena mencionar que aborda esse problema é o Polyshard [3], que usa códigos de apagamento para disponibilizar blocos em fragmentos, mesmo que vários os fragmentos perdem completamente seus dados. Infelizmente, a sua abordagem específica exige todos os shards para baixar blocos de todos os outros shards, o que é proibitivamente caro. A disponibilidade a longo prazo não é uma questão tão premente: uma vez que nenhum participante espera-se que o sistema seja capaz de validar todas as cadeias em todos os

fragmentos, a segurança do protocolo fragmentado precisa ser projetada de tal forma maneira que o sistema é seguro, mesmo que alguns blocos antigos em alguns fragmentos se tornem completamente indisponível.

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 cadeias de fragmentos a pedaços de fragmentos O modelo de sharding com shard chains e beacon chain é muito poderoso, mas tem certas complexidades. Em particular, a regra de escolha do fork precisa ser executada em cada cadeia separadamente, a regra de escolha do fork nas cadeias de fragmentos e no beacon a corrente deve ser construída de forma diferente e testada separadamente. No Nightshade modelamos o sistema como um único blockchain, no qual cada bloco contém logicamente todas as transações para todos os fragmentos e altera o estado completo de todos os fragmentos. Fisicamente, no entanto, nenhum participante baixa o estado completo ou o bloco lógico completo. Em vez disso, cada participante da rede apenas mantém o estado que corresponde aos fragmentos para os quais eles validam as transações, e a lista de todas as transações no bloco é dividida em físicas pedaços, um pedaço por fragmento. Sob condições ideais, cada bloco contém exatamente um pedaço por fragmento por bloco, que corresponde aproximadamente ao modelo com cadeias de fragmentos em que o shard chains produzem blocos com a mesma velocidade que a beacon chain. No entanto, devido a atrasos na rede, alguns pedaços podem estar faltando, então, na prática, cada bloco contém um ou zero pedaços por fragmento. Consulte a seção 3.3 para obter detalhes sobre como blocos são produzidos. Figura 16: Um modelo com cadeias de fragmentos à esquerda e com uma cadeia tendo blocos divididos em pedaços à direita

3.2 Consenso As duas abordagens dominantes para o consenso nos blockchains hoje são as cadeia mais longa (ou mais pesada), na qual a cadeia que tem mais trabalho ou participação usado para construí-lo é considerado canônico, e BFT, em que para cada bloco alguns conjunto de validators alcança um consenso BFT. Nos protocolos propostos recentemente, esta última é uma abordagem mais dominante, uma vez que fornece finalidade imediata, enquanto na cadeia mais longa mais blocos precisam a ser construído no topo do bloco para garantir a finalidade. Muitas vezes por um significado segurança o tempo que leva para que um número suficiente de blocos seja construído leva em conta ordem de horas. Usar o consenso BFT em cada bloco também tem desvantagens, como: 1. O consenso BFT envolve uma quantidade considerável de comunicação. Enquanto avanços recentes permitem que o consenso seja alcançado em tempo linear em número de participantes (ver, por exemplo, [4]), ainda é perceptível uma sobrecarga por bloco; 2. É inviável que todos os participantes da rede participem do BFT consenso por bloco, portanto, geralmente apenas um subconjunto de participantes amostrados aleatoriamente chega ao consenso. Um conjunto amostrado aleatoriamente pode ser, em princípio, corrompido adaptativamente e, em teoria, uma bifurcação pode ser criada. O sistema ou precisa ser modelado para estar pronto para tal evento e, portanto, ainda ter uma regra de escolha de bifurcação além do consenso BFT ou ser projetado para fechar cair em tal evento. Vale ressaltar que alguns projetos, como Algorand [5], reduzem significativamente a probabilidade de corrupção adaptativa. 3. Mais importante ainda, o sistema para se 1 3 ou mais de todos os participantes são off-line. Assim, qualquer falha temporária na rede ou divisão da rede pode paralisar completamente o sistema. Idealmente, o sistema deve ser capaz de continuar a operar enquanto pelo menos metade dos participantes estiver online (mais pesado protocolos baseados em cadeia continuam operando mesmo que menos da metade dos participantes estejam online, mas a conveniência desta propriedade é mais discutível dentro da comunidade). Um modelo híbrido em que o consenso utilizado é algum tipo de consenso mais pesado cadeia, mas alguns blocos são finalizados periodicamente usando um gadget de finalização BFT mantendo as vantagens de ambos os modelos. Esses BFT gadgets de finalidade são Casper FFG [6] usado em Ethereum 2.0 8, Casper CBC (ver https://vitalik. ca/general/2018/12/05/cbc_casper.html) e GRANDPA (consulte https:// Medium.com/polkadot-network/d08a24a021b5) usado em Polkadot. Nightshade usa o consenso da cadeia mais pesada. Especificamente quando um bloco produtor produz um bloco (ver seção 3.3), ele pode coletar assinaturas de outros produtores de bloco e validators atestando o bloco anterior. Veja a seção 3.8 para obter detalhes sobre como um número tão grande de assinaturas é agregado. O peso 8 Veja também a sessão do quadro branco com Justin Drake para uma visão geral detalhada de Casper FFG e como ele está integrado ao consenso da cadeia mais pesada do GHOST aqui: https://www. youtube.com/watch?v=S262StTwkmode um bloco é então a aposta cumulativa de todos os signatários cujas assinaturas são incluído no bloco. O peso de uma corrente é a soma dos pesos dos blocos. No topo do consenso da cadeia mais pesada, usamos um gadget de finalidade que usa os atestados para finalizar os blocos. Para reduzir a complexidade do sistema, usamos um gadget de finalidade que não influencia de forma alguma a regra de escolha do fork, e, em vez disso, apenas introduz condições de corte extras, de modo que, uma vez que um bloco seja finalizado pelo gadget de finalidade, um fork é impossível, a menos que uma porcentagem muito grande da aposta total é reduzida. Casper CBC é um gadget de finalidade, e nós atualmente modelo com Casper CBC em mente. Também trabalhamos em um protocolo BFT separado chamado TxFlow. Na hora de ao escrever este documento, não está claro se o TxFlow será usado em vez do Casper CBC. Notamos, no entanto, que a escolha do dispositivo final é em grande parte ortogonal ao resto do design. 3.3 Produção de blocos No Nightshade existem duas funções: produtores de blocos e validators. Em qualquer ponto em que o sistema contém w produtores de blocos, w = 100 em nossos modelos e wv validators, em nosso modelo v = 100, wv = 10.000. O sistema é Prova de Participação, o que significa que tanto os produtores de blocos quanto os validators têm algum número de recursos internos moeda (referida como ”tokens”) bloqueada por um período de tempo muito superior ao tempo que gastam no desempenho de suas funções de construção e validação da cadeia. Tal como acontece com todos os sistemas de Prova de Participação, nem todos os produtores de blocos w e nem todos os wv validators são entidades diferentes, uma vez que isso não pode ser aplicado. Cada dos produtores de bloco w e dos wv validators, no entanto, têm um separado aposta. O sistema contém n fragmentos, n = 1000 em nosso modelo. Como mencionado em seção 3.1, no Nightshade não há shard chains, em vez disso, todos os produtores de blocos e validators estão construindo um único blockchain, que chamamos de cadeia principal. O estado da cadeia principal é dividido em n fragmentos, e cada bloco produtor e validator a qualquer momento apenas baixaram localmente um subconjunto de o estado que corresponde a algum subconjunto dos fragmentos, e apenas processar e validar transações que afetam essas partes do estado. Para se tornar um produtor de blocos, um participante da rede bloqueia alguns grandes quantidade de tokens (uma aposta). A manutenção da rede é feita em épocas, onde uma época é um período de tempo da ordem de dias. Os participantes com as maiores apostas no início de uma época específica são o bloco produtores daquela época. Cada produtor de bloco é atribuído a fragmentos sw (digamos sw = 40, o que tornaria sww/n = 4 produtores de blocos por fragmento). O bloco o produtor baixa o estado do fragmento ao qual foi atribuído antes da época começa e, ao longo da época, coleta transações que afetam esse fragmento, e os aplica ao estado. Para cada bloco b na cadeia principal, e para cada fragmento s, há um dos atribuiu produtores de blocos a s, que é responsável por produzir a parte de b relacionada para o fragmento. A parte de b relacionada ao shard s é chamada de chunk e contém o lista das transações do shard a serem incluídas em b, bem como o merkleraiz do estado resultante. b acabará por conter apenas um cabeçalho muito pequeno de o pedaço, ou seja, a raiz merkle de todas as transações aplicadas (veja a seção 3.7.1 para detalhes exatos) e a raiz Merkle do estado final. Ao longo do restante do documento, frequentemente nos referimos ao produtor do bloco que é responsável por produzir um pedaço em um determinado momento para um determinado fragmento como produtor de pedaços. O produtor de pedaços é sempre um dos produtores de blocos. Os produtores de blocos e os produtores de pedaços giram cada bloco de acordo a um horário fixo. Os produtores de blocos têm um pedido e produzem repetidamente blocos nessa ordem. Por exemplo se houver 100 produtores de blocos, o primeiro bloco produtores é responsável pela produção dos blocos 1, 101, 201 etc, o segundo é responsável pela produção de 2, 102, 202 etc). Como a produção de pedaços, ao contrário da produção de blocos, exige a manutenção o estado, e para cada fragmento apenas os produtores de blocos sww/n mantêm o estado por fragmento, correspondentemente apenas os produtores de blocos sww/n giram para criar pedaços. Por exemplo com as constantes acima com quatro produtores de blocos atribuídos a cada fragmento, cada produtor de bloco criará pedaços uma vez a cada quatro blocos. 3.4 Garantindo a disponibilidade dos dados Para garantir a disponibilidade dos dados, usamos uma abordagem semelhante à de Polkadot descrito na seção 2.5.3. Depois que um produtor de bloco produz um pedaço, ele cria uma versão codificada para eliminação com um código de bloco ideal (w, ⌊w/6 + 1⌋) do pedaço. Eles então enviam um pedaço do pedaço codificado para eliminação (chamamos esses pedaços partes de pedaços, ou apenas partes) para cada produtor de bloco. Calculamos uma árvore Merkle que contém todas as partes como as folhas e as o cabeçalho de cada pedaço contém a raiz merkle dessa árvore. As peças são enviadas para validators por meio de mensagens onepart. Cada uma dessas mensagens contém o cabeçalho do bloco, o ordinal da parte e o conteúdo da parte. O mensagem também contém a assinatura do produtor do bloco que produziu o chunk e o caminho merkle para provar que a parte corresponde ao cabeçalho e é produzido pelo produtor de bloco adequado. Uma vez que um produtor de bloco recebe um bloco da cadeia principal, ele primeiro verifica se ele tenha mensagens únicas para cada pedaço incluído no bloco. Caso contrário, o bloco não é processado até que as mensagens onepart ausentes sejam recuperadas. Uma vez recebidas todas as mensagens onepart, o produtor do bloco busca o partes restantes dos pares e reconstrói os pedaços para os quais eles mantêm o estado. O produtor do bloco não processa um bloco da cadeia principal se por pelo menos um pedaço incluído no bloco eles não têm a mensagem onepart correspondente, ou se pelo menos um shard para o qual eles mantêm o estado eles não podem reconstruir todo o pedaço. Para que um determinado pedaço esteja disponível basta que ⌊w/6⌋+1 do bloco os produtores têm suas partes e as servem. Assim, enquanto o número de atores maliciosos não excedem ⌊w/3⌋nenhuma cadeia que tenha mais da metade do bloco os produtores que o constroem podem ter pedaços indisponíveis.Figura 17: Cada bloco contém um ou zero pedaços por fragmento, e cada pedaço é codificado para eliminação. Cada parte do pedaço codificado para eliminação é enviada para um determinado produtor de bloco através de uma mensagem especial onepart 3.4.1 Lidando com produtores de blocos preguiçosos Se um produtor de bloco tiver um bloco para o qual falta uma mensagem onepart, ele pode optar por ainda assiná-lo, porque se o bloco acabar sendo encadeado, maximizará a recompensa para o produtor do bloco. Não há risco para o bloqueio produtor, uma vez que é impossível provar posteriormente que o produtor do bloco não tinha a mensagem de uma parte. Para resolver isso, tornamos cada pedaço produtor ao criar o pedaço para escolha uma cor (vermelho ou azul) para cada parte do futuro bloco codificado e armazene a máscara de bits da cor atribuída no pedaço antes de ser codificada. Cada parte mensagem então contém a cor atribuída à peça, e a cor é usada quando calcular a raiz merkle das partes codificadas. Se o produtor do pedaço se desviar do protocolo, isso pode ser facilmente comprovado, já que a raiz merkle não correspondem a mensagens de uma parte ou às cores nas mensagens de uma parte que corresponder à raiz merkle não corresponderá à máscara no pedaço. Quando um produtor de bloco assina um bloco, ele inclui uma máscara de bits de todos os peças vermelhas que receberam pelos pedaços incluídos no bloco. Publicando um máscara de bits incorreta é um comportamento que pode ser cortado. Se um produtor de bloco não tiver recebido um mensagem única, eles não têm como saber a cor da mensagem e portanto, têm 50% de chance de serem cortados se tentarem assinar cegamente o bloco. 3.5 Pedido de transição de estado Os produtores de pedaços escolhem apenas quais transações incluir no pedaço, mas não aplique a transição de estado quando produzirem um pedaço. Correspondentemente,

o cabeçalho do bloco contém a raiz merkle do estado merkelizado de antes as transações no bloco são aplicadas. As transações só são aplicadas quando um bloco completo que inclui o pedaço é processado. Um participante só processa um bloco se 1. O bloco anterior foi recebido e processado; 2. Para cada pedaço, o participante não mantém o estado, pois possui vi a mensagem única; 3. Para cada pedaço, o participante mantém o estado, pois tem o pedaço inteiro. Depois que o bloco estiver sendo processado, para cada fragmento para o qual o participante mantém o estado, eles aplicam as transações e calculam o novo estado a partir da aplicação das transações, após o que elas estarão prontas para produzir os pedaços para o próximo bloco, se eles forem atribuídos a qualquer shard, uma vez que eles têm a raiz merkle do novo estado merkelizado. 3.6 Transações e recebimentos entre fragmentos Se uma transação precisar afetar mais de um fragmento, ela precisará ser consecutivamente executado em cada fragmento separadamente. A transação completa é enviada para o primeiro fragmento afetado, e uma vez que a transação é incluída no pedaço para tal fragmento, e é aplicado depois que o pedaço é incluído em um bloco, ele gera um chamado recibo transação, que é roteada para o próximo shard no qual a transação precisa ser executado. Se forem necessárias mais etapas, a execução da transação de recebimento gera uma nova transação de recebimento e assim por diante. 3.6.1 Vida útil da transação de recebimento É desejável que a transação de recebimento seja aplicada no bloco imediatamente seguinte ao bloco em que foi gerada. A transação de recebimento é apenas gerado após o bloco anterior ter sido recebido e aplicado pelos produtores do bloco que mantêm o fragmento de origem e precisa ser conhecido no momento em que o pedaço para o próximo bloco é produzido pelos produtores de bloco do destino fragmento. Assim, o recebimento deve ser comunicado do fragmento de origem ao fragmento de destino no curto período entre esses dois eventos. Seja A o último bloco produzido que contém uma transação t que gera um recibo r. Seja B o próximo bloco produzido (ou seja, um bloco que tem A como seu bloco anterior) que queremos conter r. Seja t no fragmento a e r no fragmento b. O tempo de vida do recibo, também representado na figura 18, é o seguinte: Produzir e armazenar os recibos. O CPA do produtor de pedaços para shard a recebe o bloco A, aplica a transação t e gera o recibo r. cpa em seguida, armazena todos esses recibos produzidos em seu armazenamento interno persistente indexado pelo ID do fragmento de origem.Distribuindo as receitas. Quando o cpa estiver pronto para produzir o pedaço para fragmento a para o bloco B, eles buscam todos os recibos gerados pela aplicação das transações do bloco A para o fragmento a e os incluem no bloco do fragmento a no bloco B. Uma vez gerado esse pedaço, cpa produz seu apagamento codificado versão e todas as mensagens onepart correspondentes. cpa sabe quais produtores de blocos mantêm o estado completo para quais fragmentos. Para um determinado produtor de blocos bp cpa inclui os recebimentos resultantes da aplicação de transações do bloco A para o fragmento a que possui qualquer um dos fragmentos com os quais bp se preocupa como destino na mensagem onepart quando eles distribuíram o pedaço para o fragmento A no bloco B (veja a figura 17, que mostra os recibos incluídos na mensagem onepart). Recebendo os recibos. Lembre-se de que os participantes (produtores de bloco e validators) não processam blocos até que tenham mensagens de uma parte para cada pedaço incluído no bloco. Assim, no momento em que qualquer participante em particular aplica o bloco B, ele possui todas as mensagens de uma parte que correspondem a pedaços em B e, portanto, eles têm todas as receitas recebidas que possuem os fragmentos o participante mantém o estado como destino. Ao aplicar o transição de estado para um fragmento específico, o participante aplica ambos os recibos que eles coletaram para o fragmento nas mensagens únicas, bem como todos as transações incluídas no próprio pedaço. Figura 18: A vida útil de uma transação de recebimento 3.6.2 Lidando com muitos recibos É possível que o número de recibos direcionados a um fragmento específico em um determinado bloco é muito grande para ser processado. Por exemplo, considere a figura 19, em em que cada transação em cada fragmento gera um recibo direcionado ao fragmento 1. No próximo bloco, o número de recibos que o fragmento 1 precisa processar é comparável à carga que todos os fragmentos combinados processaram durante o manuseio o bloco anterior.

Figura 19: Se todos os recibos forem direcionados ao mesmo fragmento, o fragmento poderá não ter a capacidade de processá-los Para resolver isso usamos uma técnica semelhante à usada no QuarkChain 9. Especificamente, para cada fragmento, o último bloco B e o último fragmento s dentro desse é registrado o bloco a partir do qual os recebimentos foram aplicados. Quando o novo fragmento for criado, os recibos são aplicados em ordem primeiro a partir dos fragmentos restantes em B, e depois nos blocos que seguem B, até que o novo pedaço esteja cheio. Sob normal circunstâncias com uma carga equilibrada, geralmente resultará em todos os recebimentos sendo aplicado (e assim o último fragmento do último bloco será gravado para cada pedaço), mas durante momentos em que a carga não está equilibrada e um determinado shard recebe muitas receitas desproporcionalmente, esta técnica permite que eles ser processado respeitando os limites do número de transações incluídas. Observe que se tal carga desequilibrada permanecer por muito tempo, o atraso de a criação de recibos até que a aplicação possa continuar crescendo indefinidamente. Um maneira de resolver isso é descartar qualquer transação que crie um recibo direcionado a um fragmento que possui um atraso de processamento que excede alguma constante (por exemplo, uma época). Considere a figura 20. No bloco B, o fragmento 4 não pode processar todos os recibos, portanto, ele processa apenas a origem de recibos de até o fragmento 3 no bloco A, e registra isso. No bloco C estão incluídos os recibos até o fragmento 5 do bloco B, e então, no bloco D, o fragmento alcança, processando todos os recibos restantes em bloco B e todas as receitas do bloco C. 3.7 Validação de pedaços Um pedaço produzido para um shard específico (ou um bloco de shard produzido para uma cadeia de shard específica no modelo com cadeias de shard) só pode ser validado pelo 9Veja o episódio do quadro branco com QuarkChain aqui: https://www.youtube.com/watch? v=opEtG6NM4x4, em que a abordagem para transações entre fragmentos é discutida, entre outros coisasFigura 20: Processamento de recibos atrasado participantes que mantêm o estado. Eles podem ser produtores de blocos, validators, ou apenas testemunhas externas que baixaram o estado e validaram o fragmento em quais eles armazenam ativos. Neste documento assumimos que a maioria dos participantes não consegue armazenar o estado para uma grande fração dos fragmentos. Vale ressaltar, porém, que existem blockchains fragmentados que são projetados com a suposição de que a maioria dos participantes tem capacidade de armazenar o estado e validar a maioria dos os fragmentos, como QuarkChain. Como apenas uma fração dos participantes tem estado para validar o fragmento pedaços, é possível corromper adaptativamente apenas os participantes que têm o estado e aplicar uma transição de estado inválida. Vários designs de fragmentação foram propostos para amostrar validators a cada poucos dias e dentro de um dia qualquer bloco na cadeia de fragmentos que tenha mais de 2/3 de assinaturas dos validators atribuídos a tal fragmento é imediatamente considerada final. Com tal abordagem, um adversário adaptativo só precisa corromper 2n/3+1 dos validators em uma cadeia de fragmentos para aplicar uma transição de estado inválida, que, embora seja provavelmente difícil de conseguir, não é um nível de segurança suficiente para um público blockchain. Conforme discutido na seção 2.3, a abordagem comum é permitir uma certa janela de tempo após a criação de um bloco para qualquer participante que tenha estado (seja é um produtor de bloco, um validator ou um observador externo) para desafiar sua validade. Esses participantes são chamados de Pescadores. Para que um pescador possa desafiar um bloco inválido, deve-se garantir que tal bloco esteja disponível para eles. A disponibilidade de dados no Nightshade é discutida na seção 3.4. No Nightshade, uma vez produzido um bloco, os pedaços não foram validados pelo qualquer um, exceto o próprio produtor do pedaço. Em particular, o produtor de blocos que sugeriu que o bloco naturalmente não tinha o estado para a maioria dos fragmentos, enão foi capaz de validar os pedaços. Quando o próximo bloco é produzido, ele contém atestados (ver seção 3.2) de múltiplos produtores de blocos e validators, mas como a maioria dos produtores de blocos e validators não mantêm o estado também para a maioria dos shards, um bloco com apenas um pedaço inválido coletará significativamente mais da metade dos atestados e continuará sendo o bloco mais pesado. cadeia. Para resolver esse problema, permitimos que qualquer participante que mantenha o estado de um fragmento para enviar um desafio na cadeia para qualquer pedaço inválido produzido naquele fragmento. 3.7.1 Desafio de validade do estado Depois que um participante detecta que um determinado pedaço é inválido, ele precisa fornecer uma prova de que o pedaço é inválido. Como a maioria dos participantes da rede não mantém o estado do fragmento no qual o pedaço inválido está produzido, a prova precisa ter informações suficientes para confirmar que o bloco é inválido sem ter o estado. Definimos um limite Ls da quantidade de estado (em bytes) que uma única transação pode ler ou escrever cumulativamente. Qualquer transação que toque mais de Ls estado é considerado inválido. Lembre-se da seção 3.5 que o pedaço em um determinado bloco B contém apenas as transações a serem aplicadas, mas não a nova raiz do estado. A raiz de estado incluída no pedaço do bloco B é o estado root antes de aplicar tais transações, mas depois de aplicar as transações de o último pedaço no mesmo fragmento antes do bloco B. Um ator malicioso que deseja aplicar uma transição de estado inválida incluiria uma raiz de estado incorreta no bloco B que não corresponde à raiz de estado resultante da aplicação as transações no bloco anterior. Estendemos as informações que um produtor de pedaços inclui no pedaço. Em vez de incluir apenas o estado depois de aplicar todas as transações, inclui uma raiz de estado após aplicar cada conjunto contíguo de transações que ler e escrever coletivamente Ls bytes de estado. Com essas informações para pescador criar o desafio de que uma transição de estado seja aplicada incorretamente, é suficiente para encontrar a primeira raiz de estado inválida e incluir apenas Ls bytes de estado que são afetados pelas transações entre a última raiz de estado (que foi válido) e a raiz do estado atual com as provas Merkle. Então qualquer participante pode validar as transações no segmento e confirmar que o pedaço está inválido. Da mesma forma, se o produtor do bloco tentasse incluir transações que leem e escrever mais de Ls bytes de estado, para o desafio basta incluir os primeiros Ls bytes que ele toca com as provas merkle, o que será suficiente para aplicar as transações e confirmar que há um momento em que uma tentativa de é feita a leitura ou gravação de conteúdo além de Ls bytes.

3.7.2 Pescadores e transações rápidas entre fragmentos Conforme discutido na seção 2.3, uma vez que assumimos que os pedaços de fragmento (ou fragmentos blocos no modelo com cadeias de fragmentos) podem ser inválidos e apresentar um desafio período, isso afeta negativamente a finalidade e, portanto, a comunicação entre fragmentos. Em em particular, o fragmento de destino de qualquer transação entre fragmentos não pode ser certo o fragmento ou bloco de origem é final até que o período de desafio termine (ver figura 21). Figura 21: Aguardando o período de desafio antes de aplicar um recibo A maneira de lidar com isso de uma forma que torne as transações entre fragmentos Instantâneo é para o fragmento de destino não esperar pelo período do desafio após a transação do fragmento de origem ser publicada e aplicar a transação de recebimento imediatamente, mas depois reverta o fragmento de destino junto com o fragmento de origem fragmento se posteriormente o pedaço ou bloco de origem for considerado inválido (veja a figura 22). Isso se aplica muito naturalmente ao design do Nightshade, no qual o fragmento as cadeias não são independentes, mas em vez disso, os fragmentos são todos publicados juntos no mesmo bloco da cadeia principal. Se algum pedaço for considerado inválido, o bloco inteiro com esse pedaço é considerado inválido e todos os blocos construídos nele topo disso. Veja a figura 23. Ambas as abordagens acima fornecem atomicidade, assumindo que o desafio período é suficientemente longo. Usamos a última abordagem, uma vez que fornecer transações cruzadas rápidas em circunstâncias normais supera a inconveniência de o fragmento de destino sendo revertido devido a uma transição de estado inválida em um dos os fragmentos de origem, o que é um evento extremamente raro. 3.7.3 Escondendo validators A existência dos desafios já reduz significativamente a probabilidade de corrupção adaptativa, já que para finalizar um pedaço com uma transição de estado inválida posteFigura 22: Aplicando recibos imediatamente e revertendo o destino cadeia se a cadeia de origem tiver um bloco inválido Figura 23: Desafio do pescador em Nightshade o período de desafio que o adversário adaptativo precisa para corromper todos os participantes que mantêm o estado do fragmento, incluindo todos os validators. Estimar a probabilidade de tal evento é extremamente complexo, uma vez que não sharded blockchain está ativo há tempo suficiente para que qualquer ataque desse tipo seja tentado. Argumentamos que a probabilidade, embora extremamente baixa, ainda é suficientemente grande para um sistema que deverá executar milhões de transações e executar operações financeiras em todo o mundo. Existem duas razões principais para esta crença: 1. A maioria dos validators das redes de Prova de Participação e mineradores do

As cadeias de prova de trabalho são incentivadas principalmente pela vantagem financeira. Se um adversário adaptativo oferece-lhes mais dinheiro do que o retorno esperado de operar honestamente, é razoável esperar que muitos validators aceitará a oferta. 2. Muitas entidades validam cadeias de Prova de Participação profissionalmente e espera-se que uma grande percentagem da participação em qualquer cadeia seja de tais entidades. O número de tais entidades é suficientemente pequeno para uma adversário adaptativo para conhecer a maioria deles pessoalmente e ter uma boa compreensão de sua inclinação para serem corrompidos. Damos um passo adiante na redução da probabilidade de corrupção adaptativa, ocultando quais validators estão atribuídos a qual fragmento. A ideia é remotamente semelhante à maneira como Algorand [5] esconde validators. É fundamental observar que mesmo que os validators estejam ocultos, como em Algorand ou conforme descrito abaixo, a corrupção adaptativa ainda é, em teoria, possível. Enquanto o adversário adaptativo não conhece os participantes que irão criar ou validar um bloco ou pedaço, os próprios participantes sabem que irão realizar tal tarefa e ter uma prova criptográfica disso. Assim, o adversário pode transmitir sua intenção de corromper e pagar a qualquer participante que forneça tal prova criptográfica. Notamos, no entanto, que como o adversário não conhecem os validators atribuídos ao fragmento que desejam corromper, eles não têm outra escolha a não ser transmitir sua intenção de corromper um fragmento específico para toda a comunidade. Nesse ponto, é economicamente benéfico para qualquer pessoa honesta. participante para criar um nó completo que valide esse fragmento, já que há um alto chance de um bloco inválido aparecer naquele fragmento, o que é uma oportunidade para crie um desafio e receba a recompensa associada. Para não revelar os validators atribuídos a um fragmento específico, fazemos o seguinte (ver figura 24): Usando VRF para obter a tarefa. No início de cada época cada validator usa um VRF para obter uma máscara de bits dos fragmentos aos quais validator está atribuído. A máscara de bits de cada validator terá bits Sw (veja seção 3.3 para a definição de Sw). O validator então busca o estado dos fragmentos correspondentes e durante a época para cada bloco recebido valida os pedaços que correspondem aos fragmentos aos quais validator está atribuído. Assine em blocos em vez de pedaços. Como a atribuição de fragmentos está oculta, validator não pode assinar fragmentos. Em vez disso, ele sempre assina por completo bloco, não revelando assim quais fragmentos ele valida. Especificamente, quando validator recebe um bloco e valida todos os pedaços, ele cria uma mensagem que atesta que todos os pedaços em todos os fragmentos aos quais validator está atribuído são válido (sem indicar de forma alguma quais são esses fragmentos) ou uma mensagem que contém uma prova de uma transição de estado inválida se algum pedaço for inválido. Veja o seção 3.8 para detalhes sobre como essas mensagens são agregadas, seção 3.7.4 para os detalhes sobre como evitar que validators pegue carona em mensagens de outros validators e seção 3.7.5 para detalhes sobre como recompensar e punir validators caso um desafio de transição de estado inválido bem-sucedido realmente aconteça.Figura 24: Escondendo os validators no Nightshade 3.7.4 Comprometer-Revelar Um dos problemas comuns com validators é que um validator pode pular o download do estado e realmente validar os pedaços e blocos e, em vez disso, observe a rede, veja o que os outros validators enviam e repita seus mensagens. Um validator que segue tal estratégia não fornece nenhum extra segurança para a rede, mas coleta recompensas. Uma solução comum para este problema é cada validator fornecer uma prova que eles realmente validaram o bloco, por exemplo, fornecendo um rastreamento exclusivo de aplicar a transição de estado, mas tais provas aumentam significativamente o custo de validação. Figura 25: Confirmar-revelar

Em vez disso, fazemos com que os validators primeiro se comprometam com o resultado da validação (seja a mensagem que atesta a validade dos pedaços, ou a prova de um inválido transição de estado), aguarde um determinado período, e só então revele o resultado real da validação, conforme mostrado na figura 25. O período de commit não se cruza com o período de revelação e, portanto, um validator preguiçoso não pode copiar validators honestos. Além disso, se um validator desonesto se comprometeu com uma mensagem que atesta a validade dos pedaços atribuídos, e pelo menos um pedaço era inválido, uma vez que é mostrado que o pedaço é inválido, o validator não pode evitar a redução, pois, como mostramos na seção 3.7.5, a única maneira de não ser cortado em tal situação é apresentar uma mensagem que contenha uma prova da transição de estado inválida que corresponde ao commit. 3.7.5 Lidando com desafios Conforme discutido acima, uma vez que um validator recebe um bloco com um pedaço inválido, eles primeiro preparam uma prova da transição de estado inválida (ver seção 3.7.1), depois comprometa-se com tal prova (ver 3.7.4) e, após algum período, revele o desafio. Uma vez que o desafio revelado é incluído em um bloco, acontece o seguinte: 1. Todas as transições de estado que aconteceram no bloco que contém o pedaço inválido até que o bloco no qual o desafio revelado está incluído seja obtido anulado. O estado antes do bloco que inclui o desafio revelado é considerado o mesmo que o estado antes do bloco que continha o pedaço inválido. 2. Dentro de um determinado período de tempo cada validator deve revelar sua bitmask dos fragmentos que eles validam. Como a máscara de bits é criada através de um VRF, se eles foram atribuídos ao fragmento que tinha a transição de estado inválida, eles não pode evitar revelá-lo. Qualquer validator que não revele a máscara de bits é considerado atribuído ao fragmento. 3. Cada validator que após esse período for atribuído ao shard, que se comprometeu com algum resultado de validação para o bloco que contém o pedaço inválido e que não revelou a prova de transição de estado inválida que corresponde ao seu commit é cortado. 4. Cada validator recebe uma nova atribuição de fragmentos e uma nova época é agendada para começar depois de algum tempo suficiente para que todos os validators baixem o estado, conforme mostrado na figura 26. Observe que a partir do momento em que os validators revelam os fragmentos aos quais são atribuídos até que a nova época comece, a segurança do sistema é reduzida, uma vez que o a atribuição de fragmentos é revelada. Os participantes da rede precisam mantê-la em mente ao usar a rede durante esse período. 3.8 Agregação de Assinatura Para que um sistema com centenas de fragmentos opere com segurança, queremos ter no ordem de 10.000 ou mais validators. Conforme discutido na seção 3.7, queremos que cadaFigura 26: Lidando com o desafio validator para publicar um commit para uma determinada mensagem e uma assinatura em média uma vez por bloco. Mesmo que as mensagens de commit fossem as mesmas, agregar tal A assinatura BLS e sua validação teriam sido proibitivamente caras. Mas naturalmente, as mensagens de confirmação e revelação não são as mesmas em validators, e, portanto, precisamos de alguma forma de agregar essas mensagens e as assinaturas em um maneira que permite uma validação rápida posteriormente. A abordagem específica que usamos é a seguinte: Validadores juntando-se aos produtores de blocos. Os produtores de blocos são conhecidos algum tempo antes do início da época, pois eles precisam de algum tempo para baixar o estado antes do início da época e, ao contrário dos validators, os produtores de blocos são não escondido. Cada produtor de bloco possui v validator slots. Validadores enviam propostas fora da cadeia aos produtores de blocos para serem incluídos como um de seus v validators. Se um produtor de bloco desejar incluir um validator, ele enviará um transação que contém a solicitação inicial fora da cadeia do validator e o assinatura do produtor do bloco que faz com que validator se junte ao produtor do bloco. Observe que os validators atribuídos aos produtores de blocos não necessariamente valide os mesmos fragmentos para os quais o produtor do bloco produz pedaços. Se um validator aplicado para ingressar em vários produtores de blocos, apenas a transação de o primeiro produtor de bloco terá sucesso. Os produtores de blocos coletam commits. O produtor do bloco coleta constantemente as mensagens de commit e revelação dos validators. Uma vez que um certo número dessas mensagens é acumulado, o produtor do bloco calcula um Merkle árvore dessas mensagens e envia para cada validator a raiz merkle e o merkle caminho para sua mensagem. O validator valida o caminho e faz login a raiz de merkle. O produtor do bloco então acumula uma assinatura BLS no raiz merkle de validators e publica apenas a raiz merkle e o assinatura acumulada. O produtor do bloco também assina a validade do multiassinatura usando uma assinatura ECDSA barata. Se a assinatura múltipla não corresponder à raiz merkle enviada ou à máscara de bits dos validators participantes, é um comportamento que pode ser cortado. Ao sincronizar a cadeia, um participante pode optar por validar todas as assinaturas BLS dos validators (o que é extremamente caro, pois envolve a agregação de chaves públicas de validators), ou apenasas assinaturas ECDMA dos produtores de blocos e contam com o fato de que o o produtor do bloco não foi desafiado e cortado. Usando transações on-chain e provas Merkle para desafios. Isso pode-se notar que não há valor em revelar mensagens de validators se não transição de estado inválida foi detectada. Somente as mensagens que contêm o real provas de transição de estado inválida precisam ser reveladas, e apenas para tais mensagens é preciso mostrar que eles correspondem ao commit anterior. A mensagem precisa ser revelado para dois propósitos: 1. Para realmente iniciar a reversão da cadeia para o momento anterior ao transição de estado inválida (ver seção 3.7.5). 2. Para provar que o validator não tentou atestar a validade do pedaço inválido. Em ambos os casos, precisamos abordar duas questões: 1. O commit real não foi incluído na cadeia, apenas a raiz merkle do commit agregado com outras mensagens. O validator precisa usar o caminho merkle fornecido pelo produtor do bloco e seu compromisso original com provar que eles se comprometeram com o desafio. 2. É possível que todos os validators atribuídos ao fragmento com o inválido transição de estado foi atribuída a produtores de blocos corrompidos que estão censurando-os. Para contornar isso, permitimos que eles enviem suas revelações como uma transação regular on-chain e ignorar a agregação. Este último só é permitido para as provas de transição de estado inválida, que são extremamente raro e, portanto, não deve resultar em spam nos blocos. A questão final que precisa ser abordada é que os produtores de blocos podem optar por não participar da agregação de mensagens ou censurar intencionalmente determinados validators. Tornamo-lo economicamente desvantajoso, ao tornar o bloco recompensa do produtor proporcional ao número de validators atribuídos a eles. Nós observe também que, uma vez que os produtores de blocos entre épocas se cruzam amplamente (já que são sempre os principais participantes com a aposta mais alta), os validators podem em grande parte, limitar-se a trabalhar com os mesmos produtores de blocos e, assim, reduzir o risco de serem atribuídos a um produtor de blocos que os censurou no passado. 3.9 Cadeia de instantâneos Como os blocos da cadeia principal são produzidos com muita frequência, o download o histórico completo pode ficar caro muito rapidamente. Além disso, uma vez que cada bloco contém uma assinatura BLS de um grande número de participantes, apenas a agregação das chaves públicas para verificar a assinatura pode se tornar proibitiva caro também. Finalmente, uma vez que em qualquer futuro previsível Ethereum 1.0 provavelmente permanecerá um dos blockchains mais usados, tendo uma maneira significativa de transferir ativos de

Perto de Ethereum é um requisito, e hoje verificar assinaturas BLS para garantir A validade de quase blocos no lado de Ethereum não é possível. Cada bloco na cadeia principal do Nightshade pode conter opcionalmente um Schnorr multiassinatura no cabeçalho do último bloco que incluía tal Schnorr multiassinatura. Chamamos esses blocos de blocos instantâneos. O primeiro bloco de cada época deve ser um bloco de instantâneo. Enquanto trabalhava em tal assinatura múltipla, os produtores de blocos também devem acumular as assinaturas BLS dos validators no último bloco de instantâneo e agregue-os da mesma maneira descrita em seção 3.8. Como o conjunto de produtores de blocos é constante ao longo da época, validando apenas os primeiros blocos de instantâneos em cada época são suficientes, assumindo que em nenhum momento apontam que uma grande porcentagem de produtores de blocos e validators conspiraram e criaram um garfo. O primeiro bloco da época deve conter informações suficientes para calcular os produtores de blocos e validators para a época. Chamamos a subcadeia da cadeia principal que contém apenas o instantâneo bloqueia uma cadeia de instantâneos. Criar uma multiassinatura Schnorr é um processo interativo, mas como só precisa executá-lo com pouca frequência, qualquer processo, não importa quão ineficiente, será suficiente. As multiassinaturas Schnorr podem ser facilmente validadas em Ethereum, fornecendo assim primitivas cruciais para uma maneira segura de realizar cross-blockchain comunicação. Para sincronizar com a cadeia Near, basta baixar todos os instantâneos blocos e confirme se as assinaturas Schnorr estão corretas (opcionalmente também verificando as assinaturas BLS individuais dos validators) e, em seguida, apenas sincronizando blocos da cadeia principal do último bloco de snapshot.

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.

Conclusão

Neste documento discutimos abordagens para construir blockchains fragmentados e cobriu dois grandes desafios com as abordagens existentes, nomeadamente a validade do estado e disponibilidade de dados. Em seguida, apresentamos o Nightshade, um design de fragmentação que poderes NEAR Protocolo. O design está em andamento, se você tiver comentários, perguntas ou feedback neste documento, vá para https://near.chat.