Fragmento de Blockchain

Olá a todos, sou um dos desenvolvedores do Near Protocol, que, entre outras coisas, implementa sharding, e neste artigo quero contar em detalhes o que é sharding no blockchain, como ele funciona e abordar vários problemas que surgem ao tentar construí-lo.

É sabido que o Ethereum, a plataforma dApps mais popular, processa menos de 20 transações por segundo. Devido a essa restrição, o preço das transações e o tempo para confirmá-las são muito altos: apesar do fato de um bloco ser publicado no Ethereum uma vez a cada 10 a 12 segundos, de acordo com a ETH Gas Station, o tempo entre o envio de uma transação e como ela realmente se encaixa no bloco é uma média de 1,2 minutos. Baixa largura de banda, preços altos e confirmação de transação longa não permitem o lançamento de nenhum serviço de alto desempenho no Ethereum.

O principal motivo pelo qual o Ethereum não pode processar mais de 20 transações por segundo é porque todos os nós no Ethereum precisam verificar todas as transações. Nos cinco anos desde o lançamento do Ethereum, muitas idéias foram propostas para resolver este problema. Essas soluções podem ser divididas em dois grupos: aqueles que oferecem delegar transações para um pequeno grupo de nós com hardware muito bom e aqueles que oferecem cada nó para processar apenas um subconjunto de todas as transações. Um exemplo da primeira abordagem é o Thunder , no qual os blocos são criados por apenas um nó, o que permite, de acordo com os desenvolvedores, receber 1200 transações por segundo, o que é 100 vezes mais que o Ethereum. Outros exemplos da primeira categoria são Algorand , SpaceMesh , Solana . Todos esses protocolos aprimoram vários aspectos do protocolo e permitem realizar mais transações do que no Ethereum, mas todos são limitados pela velocidade de uma máquina (embora muito poderosa).

A segunda abordagem, na qual cada nó processa apenas um subconjunto de transações, é chamada Sharding. É assim que a Ethereum Foundation planeja aumentar a largura de banda do Ethereum.

Neste post, mostrarei como o Sharding funciona no Blockchain usando o exemplo de vários protocolos atualmente em desenvolvimento.

O sharding mais fácil

Na implementação mais simples, em vez de suportar uma blockchain, daremos suporte a várias e chamaremos cada uma dessas blockchain de "fragmento". Cada shard é suportado por um conjunto independente de nós que verifica transações e cria blocos. A seguir, chamarei esses validadores de nós.

Cada fragmento é responsável por um subconjunto de contratos e contas. Por enquanto, suponha que as transações sempre operem apenas com contratos e contas no mesmo fragmento. Um design tão simplificado é suficiente para mostrar alguns problemas e recursos interessantes do sharding.

Nomeação de Validadores e Blockchain Central

O primeiro problema com o fato de que cada fragmento tem seus próprios validadores é que, se tivermos 10 shadras, cada fragmento agora é 10 vezes menos confiável do que uma blockchain seria. Portanto, se um blockchain com validadores X decide fazer um hard fork em um sistema de shard com 10 shards e quebra os validadores X entre 10 shards, agora existem apenas validadores X / 10 em cada shard, e obter controle sobre o shard exige um controle acima de 5,1% (51 % / 10) validadores.

O que leva à primeira pergunta interessante: quem atribui validadores a shards? Ter controle sobre 5,1% dos validadores é um problema apenas se todos os 5,1% dos validadores estiverem no mesmo fragmento. Se os próprios validadores não puderem escolher a qual shard eles estão atribuídos, obter controle sobre 5,1% dos validadores antes de serem atribuídos aos shards não permitirá que eles obtenham controle sobre nenhum shards.

Quase todos os projetos de sharding propostos existentes usam alguma fonte de números aleatórios para atribuir validadores a shards. A obtenção de números aleatórios em um sistema distribuído no qual os participantes não confiam um no outro não é um problema completamente resolvido hoje, que não abordaremos neste artigo, e simplesmente assuma que temos uma fonte de números aleatórios.

Tanto o recebimento de números aleatórios quanto a nomeação de validadores são cálculos em uma escala de todo o sistema que não são específicos para nenhum fragmento específico. Para esses cálculos, os projetos modernos de blockchain de fragmentos têm um blockchain dedicado adicional que existe apenas para realizar cálculos em todo o sistema. Além dos números aleatórios e da nomeação de validadores, esses cálculos podem incluir a obtenção de hashes dos últimos blocos dos shards e armazená-los; processamento de garantias em sistemas de Prova de Aposta e estudo de evidências de comportamento inadequado com a seleção associada dessas garantias; rebalanceamento de fragmentos, se essa função for fornecida. Esse blockchain é chamado de cadeia Beacon no Ethereum 2.0 e Near Protocol, a cadeia Relay no PolkaDot e o Cosmos Hub no Cosmos.

Neste post, chamaremos esse blockchain de "blockchain central". A existência de uma blockchain central nos leva ao próximo tópico interessante - fragmentação quadrática.

Fragmentação quadrática

O sharding é frequentemente apresentado como uma solução que é dimensionada infinitamente com o número crescente de nós. Provavelmente, você pode realmente criar um sistema com essa propriedade, mas os sistemas com uma blockchain central têm um limite máximo no número de shards e, como resultado, não têm escalabilidade infinita. É fácil entender o porquê: o blockchain central realiza alguns cálculos, como atribuir validadores e preservar os últimos estados de shard, cuja complexidade é proporcional ao número de shards. Como o próprio blockchain central não é fragmentado e seu rendimento é limitado pelo rendimento de cada nó, o número de shards que ele pode suportar é limitado.

Vamos ver como a taxa de transferência de todo o sistema muda se a potência dos nós que o suportam aumenta k vezes. Cada shard poderá processar k vezes mais transações, e o blockchain central poderá suportar k vezes mais shards. Assim, a taxa de transferência de todo o sistema aumentará k ^ 2 vezes. Daí o nome "fragmentação quadrática".

É difícil prever quanto shard pode suportar o blockchain central hoje, mas provavelmente no futuro próximo não chegaremos perto do limite de transações para um blockchain fragmentado com sharding quadrático. Provavelmente, em breve chegaremos ao limite de quantos nós são necessários para suportar um número tão grande de shards.

Estilhaçamento de estado

Status são todas as informações sobre todas as contas e contratos. Até agora, falamos sobre sharding em geral, sem especificar o que exatamente é sharding. Os nós no blockchain executam as três tarefas a seguir: 1) realizam transações 2) encaminham transações e blocos para outros nós e 3) armazenam o estado e o histórico do blockchain. Cada uma dessas três tarefas está associada a uma carga cada vez maior nos nós:

1. A necessidade de realizar transações requer mais poder computacional, com um aumento no número de transações;
2. A necessidade de encaminhar transações requer mais largura de banda de rede à medida que as transações crescem;
3. A necessidade de manter estado e histórico requer mais espaço em disco à medida que o tamanho do estado e / ou histórico aumenta. É importante observar que, diferentemente dos dois primeiros pontos, a quantidade de espaço em disco necessário aumenta mesmo que o número de transações por unidade de tempo não seja alterado.

A partir da lista acima, pode parecer que o espaço em disco é o maior problema, pois apenas o espaço em disco aumenta mesmo que o número de transações não aumente, mas na prática não é. Hoje, o estado do Ethereum ocupa cerca de 100 GB, que podem ser facilmente salvos em qualquer máquina moderna, mas o número de transações que o Ethereum pode processar é limitado a várias dezenas por segundo, dependendo do poder e da rede da computação.

O Zilliqa é o projeto mais famoso que fragmenta a computação e a rede, mas não afirma. O sharding de computação é mais simples que o estado de sharding, porque todos os nós têm todo o estado e ainda podem executar facilmente contratos que causam outros contratos ou afetam contas em diferentes shards. Nesses aspectos, o design de Zilliqa é muito simplificado. As críticas ao design em inglês podem ser lidas aqui .

Embora o sharding de estado sem cálculos de sombreamento tenha sido proposto, eu não conheço nenhum projeto que realmente faça isso, então assumiremos que o sharding de estado implica cálculos de sharding.

Na prática, o fato de o estado ser fragmentado de alguma forma isola os fragmentos, permitindo que eles sejam cadeias independentes, como definimos acima. Os validadores nos shards armazenam apenas um estado específico para o shard, e apenas as transações que afetam esse estado são executadas e encaminhadas. Isso reduz a carga no processador, disco e rede linearmente com o número de shards, mas traz novos problemas, como transações entre shard.

Transações entre fragmentos

Até agora, vimos os shards como blockchains independentes em termos de como eles executam transações. Com esse design, por exemplo, é impossível concluir uma transação que transfira dinheiro entre duas contas em dois fragmentos diferentes, ou causar contato em um fragmento de um contrato em outro. Eu gostaria de apoiar os dois cenários.

Por uma questão de simplicidade, consideraremos apenas as transações que transferem dinheiro e assumiremos que cada participante tem uma conta em exatamente um fragmento. Se um participante de um fragmento desejar transferir dinheiro para um participante no mesmo fragmento, os validadores desse fragmento poderão processar essa transação e aplicá-la ao estado. Mas se, por exemplo, Alice tiver uma conta no fragmento 1 e desejar enviar dinheiro para Bob com uma conta no fragmento 2, nem os validadores de fragmento 1 (que não podem adicionar dinheiro a Bob) nem os validadores de fragmento 2 (que não podem obter o dinheiro de Alice ) não pode concluir a transação e atualizar o estado.

Existem dois grandes grupos de abordagens para resolver esse problema:

1. Síncrono : para qualquer transação que envolva vários shards, blocos em shards contendo atualizações de estado para essa transação são produzidos simultaneamente e validadores nesses shards trabalham juntos para criar esses blocos. O design mais elaborado dessa abordagem, conhecido por mim, é o Merge Blocks, descrito (em inglês) aqui .

   
   

2. Assíncrona : uma transação entre fragmentos é executada em shards que afeta de forma assíncrona: a parte da transação que adiciona dinheiro a Bob é executada no fragmento # 2 quando os validadores no fragmento têm alguma evidência de que a parte da transação que subtrai dinheiro de Alice foi executada em fragmento # 1. Essa abordagem é mais popular nos sistemas desenvolvidos atualmente devido ao fato de não exigir sincronização adicional entre os shards para a produção de blocos. Hoje, esses sistemas são oferecidos no Cosmos, Ethereum Serenity, Near Protocol, Kadena e outros. O problema dessa abordagem é que, se os blocos forem produzidos independentemente, é provável que um dos blocos que contém a atualização de estado da transação não esteja na cadeia canônica em seu fragmento e, portanto, a transação será parcialmente parcialmente concluída. Por exemplo, considere a figura abaixo. Ele mostra dois fragmentos nos quais os garfos ocorreram e uma transação entre fragmentos, cuja atualização de estado é refletida nos blocos A e X ', respectivamente. Se as cadeias AB e V'-X'-Y'-Z 'forem canônicas em seus fragmentos, a transação será totalmente finalizada. Se as cadeias A'-B'-C'-D 'e VX forem canônicas, a transação será completamente cancelada, o que é aceitável. Mas se, por exemplo, AB e VX se tornarem canônicos, uma parte da transação será finalizada, a outra será cancelada e a transação será parcialmente concluída.

   
   

O cenário descrito acima é um dos grandes problemas no sharding, no qual todas as soluções propostas não são ideais. Vamos tocar um pouco abaixo.

Mau comportamento

Agora que descobrimos como o blockchain do shard funciona e estudamos os conceitos de blockchain central, a nomeação de validadores e as transações entre shards, no final deste artigo, veremos outro tópico interessante: o que um participante que tenta atacar o sistema pode fazer se conseguir obter controle sobre um número suficientemente grande de validadores em um fragmento.

Forquilhas direcionadas

Se o participante tiver controle suficiente sobre o fragmento, ele poderá criar garfos de propósito. Para criar garfos, não importa qual consenso é usado nos fragmentos, em particular, não importa se é BFT ou não, se um número suficiente de validadores for controlado pelo invasor, ele poderá criar um garfo. Por exemplo, o objetivo da bifurcação pode ser reverter uma transação que pagou por algo fora da blockchain.

Alega-se que ganhar controle de 50% do shard é mais fácil do que 50% de toda a rede (por exemplo, porque um participante pode tentar hackear ou subornar validadores depois de ter sido designado ao shard). Por definição, as transações entre fragmentos mudam de estado em vários fragmentos. Tais mudanças cairão em alguns blocos nas cadeias de blocos dos fragmentos correspondentes. É necessário que todos esses blocos sejam finalizados (ou seja, pertençam à cadeia canônica em seus respectivos fragmentos) ou que todos não sejam finalizados (ou seja, não pertençam à cadeia canônica em seus fragmentos). Como assumimos que alguns participantes com más intenções podem, em princípio, obter controle sobre o fragmento, não podemos assumir que os garfos não ocorrerão, mesmo que o consenso bizantino tenha sido alcançado ou que um grande número de blocos tenha sido construído no topo do bloco com a transação.

Esse problema tem muitas soluções, a mais simples das vezes é salvar o hash do último bloco no shard no blockchain central. O algoritmo de seleção de cadeia canônica em shards é então alterado para que nenhum alvo que contenha o último bloco armazenado no canonical blockchain central. Então, para evitar completamente situações em que a transação foi parcialmente concluída devido ao fato de alguns dos blocos que contêm sua atualização de estado estarem fora das cadeias canônicas, você pode alterar o algoritmo para executar transações entre shards, para que o shard A não aceite a prova da transação no shard B até o bloco contendo a atualização de estado para a transação no fragmento B não foi salvo no blockchain central.

Criando blocos inválidos

Se o participante conseguiu obter controle sobre um número suficientemente grande de validadores no shard, ele pode tentar criar um bloco completamente inválido. Por exemplo, suponha que antes do bloco, o estado era tal que Alice tivesse 10 tokens e, em Bob - 0, o bloco contém apenas uma transação, que envia 10 tokens da conta de Alice para a conta de Bob, mas no novo estado reflete 0 tokens de Alice e 1000 com o Bob.

Em um blockchain clássico e não fragmentado, é impossível criar um bloco assim, porque todos os participantes, como aqueles que criam blocos e aqueles que simplesmente usam o blockchain, verificam todos os blocos e descartam imediatamente qualquer bloco que contenha tais erros. Mesmo que os validadores controlados pelo invasor possam construir a cadeia mais rapidamente, isso não permitirá que eles passem a cadeia mais longa que contém o bloco inválido como o canônico, porque todos os participantes da rede descartam imediatamente o bloco inválido e qualquer bloco que foi construído no topo. Os validadores honestos continuarão construindo sobre o último bloco válido e todos os participantes da rede verão sua cadeia como canônica.

A figura acima mostra cinco validadores, três dos quais estão sob o controle do atacante. Eles criaram o bloco inválido A 'e continuaram a construir a cadeia no topo. Dois validadores privados descartaram imediatamente o bloco A 'como inválido e continuaram a construir sobre o último bloco válido que eles conheciam, criando assim um fork. Como há menos validadores em uma cadeia honesta do que em uma cadeia desonesta, sua cadeia é mais curta. No entanto, no blockchain clássico não compartilhado, todos os participantes do sistema validam todos os blocos que veem. Assim, qualquer participante que use o blockchain verá que A 'é inválido, descartá-lo e, portanto, descartará B', C 'e D' como construído no topo do bloco inválido e, portanto, todos os participantes verão AB como uma cadeia canônica.

Em um design de fragmento, nenhum participante pode validar todos os blocos em todas as cadeias de blocos. - , , , - .

, , . , , ( ).

, :

1. - . , 2/3 . , , , . , , , - , . , .
2. - , , , , , . , zk-SNARKs ( zk, zero-knowledge, , non-zk SNARKs). , zk-SNARKs , .

, , , , . — .

Eu escrevo muito sobre blockchain e sharding em inglês. Também entrevistamos periodicamente autores de outros protocolos, como Cosmos e Solana, aprofundando detalhes técnicos. Se você estiver interessado no tópico, poderá seguir novas postagens e vídeos assinando meu Twitter @AlexSkidanov .