Olá, sou um dos desenvolvedores do Near Protocol de sharded blockchain e, neste artigo, quero falar sobre o que é sharding de blockchain, como ele é implementado e quais problemas existem nos projetos de sharding de blockchain.
É sabido que o Ethereum, o blockchain de uso geral mais usado no momento da redação deste documento, pode processar apenas menos de 20 transações por segundo na cadeia principal. Essa limitação, juntamente com a popularidade da rede, leva a altos preços do gás (o custo da execução de uma transação na rede) e longos tempos de confirmação; apesar do fato de que, no momento da redação deste documento, um novo bloco é produzido aproximadamente a cada 10 a 20 segundos, o tempo médio necessário para que uma transação seja adicionada ao blockchain é de 1,2 minutos, de acordo com o ETH Gas Station . Baixo rendimento, altos preços e alta latência tornam o Ethereum inadequado para executar serviços que precisam ser dimensionados com a adoção.
Qual é o principal motivo do baixo rendimento da Ethereum? O motivo é que todos os nós da rede precisam processar todas as transações. Os desenvolvedores propuseram muitas soluções para abordar a questão da taxa de transferência no nível do protocolo. Essas soluções podem ser separadas principalmente pelas que delegam toda a computação em um pequeno conjunto de nós poderosos, e as que possuem cada nó na rede fazem apenas um subconjunto da quantidade total de trabalho. Um caso extremo da abordagem anterior é o Thunder, que possui um único nó processando todas as transações e reivindicações para atingir 1200 tx / s, uma melhoria de 100x em relação ao Ethereum (no entanto, não endosso o Thunder nem atesto a validade de suas reivindicações ) Algorand , SpaceMesh , Solana se encaixam na categoria anterior, construindo várias melhorias no consenso e na estrutura da própria blockchain para executar significativamente mais transações, mas ainda limitadas pelo que uma única máquina (embora muito poderosa) possa processar.
A última abordagem, na qual o trabalho é dividido entre todos os nós participantes, é chamada sharding. É assim que a Ethereum Foundation atualmente planeja escalar o Ethereum. No momento da redação deste artigo, a especificação completa ainda não foi publicada. Aqui estão os links para uma visão geral detalhada das cadeias de fragmentos Ethereum e da cadeia Beacon .
Neste post, sumario as idéias principais do sharding de blockchain, nas quais o Near e a maioria dos outros protocolos sharded são baseados. A postagem subsequente descreverá tópicos mais avançados em sharding.
O sharding mais simples, também conhecido como beanstalk
Vamos começar com a abordagem mais simples ao sharding, que, ao longo deste artigo, chamaremos de Beanstalk. Isso é também o que Vitalik chama de "escalonamento de mil altcoins" nesta apresentação.
Nesta abordagem, em vez de executar uma blockchain, executaremos várias e chamaremos cada uma dessas blockchain de "fragmento". Cada shard terá seu próprio conjunto de validadores. Aqui e abaixo, usamos um termo genérico “validador” para se referir aos participantes que verificam transações e produzem blocos, por mineração, como na Prova de Trabalho, ou por meio de um mecanismo baseado em votação. Por enquanto, vamos supor que os fragmentos nunca se comuniquem.
O design do Beanstalk, embora simples, é suficiente para descrever alguns dos principais desafios do sharding.
Particionamento do validador e cadeias de beacon
O primeiro desafio é que, com cada fragmento tendo seus próprios validadores, cada fragmento agora é 10 vezes menos seguro que toda a cadeia. Portanto, se uma cadeia não fragmentada com validadores X decide se dividir com força em uma cadeia fragmentada e divide X validadores em 10 fragmentos, agora cada fragmento possui apenas validadores X / 10, e corromper um fragmento exige apenas 5,1% de corrupção (51% / 10) do número total de validadores.
O que nos leva ao segundo ponto: quem escolhe validadores para cada fragmento? Controlar 5,1% dos validadores é prejudicial apenas se todos os 5,1% dos validadores estiverem no mesmo fragmento. Se os validadores não puderem escolher em qual shard validar, é altamente improvável que um participante que controle 5,1% dos validadores obtenha todos os validadores no mesmo shard, reduzindo bastante sua capacidade de comprometer o sistema.
Atualmente, quase todos os projetos de sharding contam com alguma fonte de aleatoriedade para atribuir validadores a shards. A aleatoriedade no blockchain por si só é um tópico muito desafiador e merece uma postagem de blog separada em algum momento posterior, mas, por enquanto, vamos assumir que há alguma fonte de aleatoriedade que podemos usar.
Tanto a aleatoriedade quanto a atribuição dos validadores requerem computação que não é específica para nenhum fragmento específico. Para esse cálculo, praticamente todos os projetos existentes têm um blockchain separado, encarregado de executar as operações necessárias para a manutenção de toda a rede. Além de gerar números aleatórios e atribuir validadores aos shards, essas operações também incluem o recebimento de atualizações dos shards e a captura de instantâneos deles, o processamento de apostas e a barra nos sistemas de Prova de Participação e o reequilíbrio de shards quando esse recurso é suportado. Essa cadeia é chamada de cadeia Beacon no Ethereum e Near, uma cadeia de relés na PolkaDot e o Hub Cosmos no Cosmos.
Ao longo deste post, nos referiremos a essa cadeia como uma cadeia Beacon . A existência da cadeia Beacon nos leva ao próximo tópico interessante, o fragmento quadrático.
Fragmentação quadrática
O sharding é frequentemente anunciado como uma solução escalável infinitamente com o número de nós participantes da operação de rede. Embora seja teoricamente possível projetar uma solução de sharding, qualquer solução que tenha o conceito de uma cadeia Beacon não tem escalabilidade infinita. Para entender o porquê, observe que a cadeia Beacon precisa fazer algum cálculo contábil, como atribuir validadores a shards ou capturar instantâneos de blocos de cadeia de shard, proporcional ao número de shards no sistema. Como a cadeia Beacon é ela própria uma única blockchain, com a computação limitada pelas capacidades computacionais dos nós que a operam, o número de shards é naturalmente limitado.
No entanto, a estrutura de uma rede fragmentada concede um efeito multiplicativo a quaisquer melhorias em seus nós. Considere o caso em que uma melhoria arbitrária é feita na eficiência dos nós na rede, o que permitirá tempos de processamento de transação mais rápidos.
Se os nós que operam na rede, incluindo os nós da cadeia Beacon, se tornarem quatro vezes mais rápidos, cada fragmento poderá processar quatro vezes mais transações, e a cadeia Beacon poderá manter 4 vezes mais fragmentos. A taxa de transferência no sistema aumentará pelo fator de 4 x 4 = 16 - portanto, o nome sharding quadrático .
É difícil fornecer uma medida precisa de quantos fragmentos são viáveis atualmente, mas é improvável que, em um futuro previsível, as necessidades de taxa de transferência dos usuários de blockchain superem as limitações do sharding quadrático. O grande número de nós necessários para operar com segurança esse volume de fragmentos é uma ordem de magnitude superior ao número de nós que operam todas as cadeias de blocos combinadas hoje.
No entanto, se quisermos construir protocolos à prova do futuro, talvez valha a pena começar a pesquisar soluções para esse problema hoje. A proposta mais desenvolvida a partir de agora é o fragmento exponencial, no qual os próprios fragmentos estão formando uma árvore, e cada fragmento pai está orquestrando uma série de fragmentos filhos, enquanto ele próprio pode ser filho de outro fragmento.
Sabe-se que Vlad Zamfir, da Ethereum Foundation, está trabalhando em um projeto de sharding que não envolve uma corrente de farol; Eu trabalhei com ele em um dos protótipos, cuja visão detalhada está aqui .
Estilhaçamento de estado
Até agora, não definimos muito bem o que exatamente é e não é separado quando uma rede é dividida em shards. Especificamente, os nós no blockchain executam três tarefas importantes: não apenas 1) processam transações, mas também 2) retransmitem transações validadas e bloqueiam blocos para outros nós e 3) armazenam o estado e o histórico de todo o razão da rede. Cada uma dessas três tarefas impõe um requisito crescente aos nós que operam na rede:
- A necessidade de processar transações requer mais poder computacional com o aumento do número de transações sendo processadas;
- A necessidade de retransmitir transações e blocos requer mais largura de banda da rede, com o aumento do número de transações retransmitidas;
- A necessidade de armazenar dados requer mais armazenamento à medida que o estado cresce. É importante ressaltar que, diferentemente da capacidade de processamento e da rede, o requisito de armazenamento aumenta mesmo que a taxa de transação (número de transações processadas por segundo) permaneça constante.
Na lista acima, pode parecer que o requisito de armazenamento seria o mais urgente, pois é o único que está sendo aumentado 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 da computação. Todo o estado do Ethereum até o momento da redação deste documento é de 100 GB, facilmente gerenciável pela maioria dos nós. Mas o número de transações que o Ethereum pode processar é de cerca de 20, ordens de magnitude inferiores ao necessário para muitos casos de uso prático.
O 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ó tem 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 que as atualizações de vários shards atualizando as mesmas partes do estado não entrem em conflito. A esse respeito, Zilliqa está adotando uma abordagem muito simplista, cuja crítica pode ser encontrada neste post .
Embora tenha sido proposto sharding de armazenamento sem sharding de processamento, não conheço nenhum projeto trabalhando nele. Assim, na prática, sharding de armazenamento, ou State Sharding, quase sempre implica sharding de processamento e sharding de rede.
Praticamente, em State Sharding, os nós em cada shard estão construindo seu próprio blockchain que contém transações que afetam apenas a parte local do estado global atribuída a esse shard. Portanto, os validadores no shard precisam apenas armazenar sua parte local do estado global e executar e, como tal, apenas retransmitir transações que afetam sua parte do estado. Essa partição reduz linearmente o requisito de toda a energia de computação, armazenamento e largura de banda da rede, mas apresenta novos problemas, como disponibilidade de dados e transações entre shard, abordaremos a seguir.
Transações entre fragmentos
Beanstalk como modelo não é uma abordagem muito útil para sharding, porque se os shards individuais não podem se comunicar entre si, eles não são melhores do que várias cadeias de blocos independentes. Ainda hoje, quando o sharding não está disponível, há uma enorme demanda por interoperabilidade entre várias blockchains.
Por enquanto, consideremos apenas transações de pagamento simples, nas quais cada participante tem conta em exatamente um fragmento. Se alguém deseja transferir dinheiro de uma conta para outra no mesmo fragmento, a transação pode ser processada inteiramente pelos validadores desse fragmento. Se, no entanto, Alice que reside no fragmento 1 quiser enviar dinheiro para Bob, que reside no fragmento 2, nem os validadores no fragmento 1 (eles não poderão creditar a conta de Bob) nem os validadores no fragmento 2 ( eles não poderão debitar na conta de Alice) podem processar toda a transação.
Existem duas famílias de abordagens para transações entre fragmentos:
- Síncrono : sempre que uma transação entre shard precisa ser executada, os blocos em vários shards que contêm transição de estado relacionada à transação são produzidos ao mesmo tempo, e os validadores de vários shards colaboram na execução dessas transações. A proposta mais detalhada conhecida por mim é Merge Blocks, descrita aqui .
- Assíncrona : uma transação de fragmento cruzado que afeta vários fragmentos é executada nesses fragmentos de forma assíncrona, o fragmento de "Crédito" executa sua metade uma vez que possui evidências suficientes de que o fragmento de "Débito" executou sua parte. Essa abordagem tende a ser mais prevalente devido à sua simplicidade e facilidade de coordenação. Hoje, esse sistema é proposto no Cosmos, Ethereum Serenity, Near, Kadena e outros. Um problema com essa 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 a transação apenas parcialmente aplicada. Considere a figura abaixo que mostra dois shards que encontraram um fork e uma transação cross-shard que foi registrada nos blocos A e X 'correspondentemente. Se as cadeias AB e V'-X'-Y'-Z 'acabarem sendo canônicas nos fragmentos correspondentes, a transação será totalmente finalizada. Se A'-B'-C'-D 'e VX se tornarem canônicos, a transação será totalmente abandonada, o que é aceitável. Mas se, por exemplo, AB e VX se tornarem canônicos, uma parte da transação será finalizada e outra abandonada, criando uma falha de atomicidade. Abordaremos como esse problema é tratado nos protocolos propostos na segunda parte, ao abordar alterações nas regras de escolha de bifurcações e algoritmos de consenso propostos para protocolos sharded.
Observe que a comunicação entre cadeias também é útil fora de cadeias de blocos fragmentadas. A interoperabilidade entre cadeias é um problema complexo que muitos projetos estão tentando resolver. Nas cadeias de blocos fragmentadas, o problema é um pouco mais fácil, pois a estrutura e o consenso dos blocos são os mesmos entre os fragmentos, e há uma cadeia de beacon que pode ser usada para coordenação. Em uma blockchain fragmentada, no entanto, todas as cadeias de shard são iguais, enquanto no ecossistema global de blockchains existem muitas blockchains diferentes, com diferentes casos de uso de destino, descentralização e garantias de privacidade.
Construir um sistema no qual um conjunto de cadeias tenha propriedades diferentes, mas use consenso e estrutura de blocos suficientemente semelhantes e possua uma cadeia de beacon comum, poderá permitir um ecossistema de cadeias de blocos heterogêneas que possuam um subsistema de interoperabilidade em funcionamento. É improvável que esse sistema apresente rotação do validador, portanto, algumas medidas extras precisam ser tomadas para garantir a segurança. O Cosmos e o PolkaDot são efetivamente esses sistemas. Este artigo de Zaki Manian da Cosmos fornece uma visão geral detalhada e a comparação dos principais aspectos dos dois projetos.
Comportamento malicioso
Agora você tem um bom entendimento de como o sharding é implementado, incluindo os conceitos da cadeia de beacon, rotações do validador e transações entre shard.
Com todas essas informações, há uma última coisa importante a considerar. Especificamente, qual comportamento adversário os validadores maliciosos podem exercer.
Garfos maliciosos
Um conjunto de validadores maliciosos pode tentar criar uma bifurcação. Observe que não importa se o consenso subjacente é BFT ou não, um número suficiente de validadores corrompidos sempre possibilitará a criação de um fork.
É significativamente mais provável que mais de 50% de um único shard seja corrompido, do que mais de 50% de toda a rede seja corrompida (aprofundaremos essas probabilidades na segunda parte). Como discutido acima, as transações entre shards envolvem certas mudanças de estado em vários shards, e os blocos correspondentes nesses shards que aplicam essas mudanças de estado devem ser todos finalizados (ou seja, aparecer nas cadeias selecionadas em seus shards correspondentes) ou ficar órfãos (ou seja, não aparece nas cadeias selecionadas nos seus fragmentos correspondentes). Como geralmente a probabilidade de fragmentos serem corrompidos não é desprezível, não podemos presumir que os garfos não ocorram, mesmo que um consenso bizantino tenha sido alcançado entre os validadores de fragmentos ou muitos blocos tenham sido produzidos no topo do bloco com a mudança de estado .
Esse problema possui várias soluções, sendo a mais comum a reticulação ocasional do último bloco de cadeia de fragmentos com a cadeia de beacon. A regra de escolha de bifurcação nas cadeias de fragmentos é então alterada para sempre preferir a cadeia com reticulação e aplicar apenas a regra de escolha de forquilha específica de fragmento para blocos que foram publicados desde o último link cruzado.
Aprovando blocos inválidos
Um conjunto de validadores 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 possui 10 tokens e Bob possui 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 possui 0 tokens e Bob possui 1000 fichas.
Em um blockchain clássico não fragmentado, esse ataque não é possível, pois todos os participantes da rede validam todos os blocos e o bloco com uma transição de estado inválida será rejeitado pelos outros produtores de bloco e pelos participantes da rede. que não criam blocos. Mesmo que os validadores maliciosos continuem criando blocos em cima de um bloco inválido mais rapidamente do que os validadores honestos constroem a cadeia correta, mantendo a cadeia com o bloco inválido mais longo, não importa, pois todos os participantes que usam o blockchain para qualquer finalidade valida todos os blocos e descarta todos os blocos criados em cima do bloco inválido.
Na figura acima, existem cinco validadores, três dos quais são maliciosos. Eles criaram um bloco inválido A 'e continuaram construindo novos blocos sobre ele. Dois validadores honestos descartaram A 'como inválido e estavam construindo sobre o último bloco válido conhecido por eles, criando um fork. Como há menos validadores no garfo honesto, 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 descartaria imediatamente B', C 'e D', dessa forma tomando a cadeia AB como a corrente válida mais longa atual.
Em uma blockchain fragmentada, no entanto, nenhum participante pode validar todas as transações em todos os shards, portanto, eles precisam ter alguma maneira de confirmar que, em nenhum momento do histórico de qualquer shard da blockchain, nenhum bloco inválido foi incluído.
Observe que, diferentemente dos garfos, a reticulação com a cadeia Beacon não é uma solução suficiente, pois a cadeia Beacon não tem capacidade para validar os blocos. Só é possível validar que um número suficiente de validadores nesse fragmento assinou o bloco (e, como tal, atestou sua correção).
Estou ciente de apenas duas soluções para esse problema, nenhuma das quais é realmente satisfatória hoje:
- Tenha algum mecanismo razoável que alertará o sistema se for feita uma tentativa de aplicar a transição de estado incorretamente. Supondo que cada shard esteja executando algum tipo de consenso de BFT, enquanto o número de validadores maliciosos em um shard em particular for menor que less, pelo menos um validador honesto precisaria atestar um bloco e verificar se a função de transição de estado está aplicado corretamente. Se mais de ⅔ dos nós forem maliciosos, eles poderão finalizar um bloco sem a participação de um único nó honesto. Supondo que pelo menos um nó no shard não seja malicioso, é necessário algum mecanismo que permita que esses nós monitorem quais blocos estão sendo produzidos e tenham tempo suficiente para desafiar os nós com transição de estado inválida.
- Tenha algumas informações nos blocos suficientes para provar que a transição de estado foi aplicada corretamente, mas é significativamente mais barata de validar do que a aplicação real da função de transição de estado. O mecanismo mais próximo para conseguir isso são os zk-SNARKs (embora não precisemos realmente da parte “zk”, ou conhecimento nulo, um SNARK não-zk seria suficiente), mas os zk-SNARKs são notoriamente lentos em calcular em neste ponto.
Atualmente, muitos protocolos assumem que, com a rotação adequada do validador e um consenso tolerante a falhas bizantinas, não são possíveis forquilhas nem transições de estado inválidas. A razão pela qual essa suposição não é razoável é um tópico para um artigo separado.
Outro
Eu escrevo muito sobre blockchains e sharding, e também temos uma série de vídeos em que conversamos com os fundadores de protocolos escaláveis, como Cosmos e Solana, com mergulhos profundos na tecnologia. Você pode me seguir no twitter aqui .