a16z: Por que blockchains sem estado não podem existir

Autor: Miranda Christ (estudante de doutorado em ciência da computação na Universidade de Columbia/estagiário de pesquisa de criptografia a16z), Joseph Bonneau (a16zcrypto) Fonte: a16z crypto; Compilador: Yvonne, MarsBit

À medida que o blockchain suporta mais usuários e transações mais frequentes, cresce a quantidade de informações (“estado”) armazenadas pelos validadores para verificar as transações. Por exemplo, no Bitcoin, o estado consiste em um conjunto de saídas de transações não gastas (utxo). No Ethereum, o estado consiste no saldo de cada conta e no código e armazenamento de cada contrato inteligente.

Esta carga de armazenamento tornar-se-ia incontrolável para uma blockchain com contas ou UTXOs suficientes para suportar as transações reais do dia-a-dia da maioria das pessoas, tornando difícil ser um validador e uma ameaça à descentralização. É tentador olhar para a criptografia como uma solução, e ferramentas como árvores Merkle e provas de conhecimento zero nos ajudaram a alcançar objetivos anteriormente inacreditáveis.

Este é exatamente o objetivo de um “blockchain sem estado”. No entanto, apesar de muito trabalho nesta área, ainda estão longe de serem práticos. Mas acontece que este atraso no progresso é inerente – a lacuna entre estas estruturas e a praticidade nunca poderá ser superada. Nosso trabalho recente mostra que qualquer esquema de blockchain sem estado, por mais inteligente que seja, não é viável sem medidas adicionais para gerenciar o estado. Como demonstramos no final deste artigo, este resultado improvável não deve ser desanimador.

estado sem estado

Hoje, o tamanho do estado é grande, mas administrável. Por exemplo, um nó Bitcoin armazena cerca de 7 GB de dados e um nó Ethereum armazena cerca de 650 GB de dados. No entanto, a carga de armazenamento em nós completos aumenta aproximadamente linearmente com o rendimento da cadeia (transações por segundo, ou TPS), que atualmente é inaceitavelmente baixo. De acordo com a concepção actual, o estado necessário para suportar verdadeiramente as transacções diárias (centenas de milhares a milhões de TPS) tornar-se-á incontrolável, exigindo a utilização de vários terabytes ou mesmo petabytes de espaço de armazenamento.

Isto levou as pessoas a procurar formas técnicas de reduzir drasticamente a quantidade de estado exigido pelos validadores - uma blockchain sem estado exigiria que os validadores armazenassem apenas um estado de tamanho constante, independentemente do rendimento da transação. (Na verdade, o termo é um nome impróprio: ainda existe um estado, pequeno o suficiente para acomodar qualquer taxa de transferência futura - geralmente de tamanho constante.) Esse requisito de armazenamento leve tornará mais fácil a execução de nós validadores; de maneira otimista, todos poderão executar um nó em seu próprio computador. telefone. Dado que o aumento do número de validadores aumentará a segurança da cadeia, é importante reduzir as barreiras à entrada dos validadores.

Apesar de muitas pesquisas sobre blockchains sem estado (por exemplo, Todd, Buterin, Boneh et al., Srinivasan et al.), eles estão longe de ser práticos e, até onde sabemos, nenhum foi implantado. O problema fundamental com todos os blockchains sem estado conhecidos é que eles exigem que os usuários armazenem dados adicionais chamados testemunhas para ajudar os validadores a verificar as transações envolvendo suas contas. Por exemplo, esta testemunha poderia ser uma prova de inclusão Merkle, mostrando que a conta do utilizador e o seu saldo estão incluídos no compromisso estatal global. Quando um usuário faz uma transação, ele envia essa testemunha a um validador, mostrando que sua conta tem saldo suficiente.

Ao contrário do armazenamento de chaves privadas que nunca precisam ser alteradas, essas testemunhas mudam frequentemente, mesmo para usuários que não estão realizando transações ativamente, colocando uma carga irreal sobre os usuários. Da mesma forma, imagine se você tivesse que monitorar constantemente todas as outras transações de cartão de crédito globalmente e atualizar alguns dados locais de acordo para usar seu próprio cartão de crédito. Para que um blockchain seja prático, os usuários devem poder permanecer offline, interagindo com o blockchain apenas ao enviar transações. Em muitos casos, como carteiras de hardware, atualizar testemunhas não é apenas inconveniente, mas impossível.

Isso leva a uma questão de pesquisa natural: podemos construir uma blockchain sem estado que não precise atualizar testemunhas (ou raramente precise atualizar testemunhas)? Para responder a essa pergunta, desenvolvemos uma nova estrutura teórica (que pode ser um Sistema à Prova de Revogação), que generaliza blockchains sem estado. Utilizando este quadro, demonstramos um resultado conclusivamente impossível: o compromisso entre um estado global compacto e atualizações frequentes de testemunhas é fundamental. Nossa técnica de prova é teórica da informação, o que significa que os computadores do futuro não serão poderosos o suficiente para resolver este problema: a lacuna entre a estrutura de blockchain sem estado e a praticidade nunca será superada.

Antecedentes da pesquisa

Para ajudar a desenvolver a intuição para resultados impossíveis, primeiro descreveremos a construção natural, mas ineficiente, de uma blockchain sem estado usando árvores Merkle. Nosso objetivo é que os validadores determinem se uma transação enviada por um usuário é válida — por exemplo, se o usuário tem um saldo de conta grande o suficiente para fazer a transação. Em um esquema de blockchain sem estado, os validadores armazenam um estado de tamanho constante. Quando os usuários fazem uma transação, eles devem incluir uma testemunha na transação. Um validador pode usar o estado atual e o par (transação, testemunha) enviado pelo usuário para verificar se o usuário possui saldo de conta suficiente para fazer a transação.

Primeiro construímos uma árvore Merkle onde cada par (a, b) (ID da conta, saldo) é incluído como uma folha. O estado de tamanho constante V armazenado pelos validadores é a raiz desta árvore, que atua como um compromisso para o conjunto de pares de saldos de contas. Cada usuário mantém sua prova Merkle de inclusão do par (ID da conta, saldo) como testemunha. A prova Merkle de inclusão de uma folha (a, b) consiste em nós parceiros (v 1,…, vk) ao longo de seu caminho até a raiz da árvore. Dada uma transação feita por um usuário usando a conta a e reivindicando um saldo b, um validador pode verificar se b é de fato o saldo da conta a verificando se (a, b) prova (v 1 , …, vk ) com seu estado atual V . Nesse caso, o validador executará a transação e deverá atualizar o saldo da conta de acordo. Uma propriedade conveniente das árvores Merkle é que, dada a prova de contenção Merkle de uma folha, é fácil calcular a raiz resultante quando essa folha muda. Em outras palavras, um validador pode calcular facilmente um estado atualizado V' que captura o novo saldo da conta a após a transação ser executada.

A abordagem da árvore Merkle tem duas desvantagens principais. Primeiro, o número de usuários testemunhas é relativamente grande, crescendo logaritmicamente no número total de contas no sistema. Idealmente, eles deveriam ser de tamanho constante, o que podemos conseguir usando esquemas como acumuladores RSA (Boneh et al. no contexto de blockchains sem estado).

A segunda desvantagem é mais difícil de evitar: sempre que outros usuários fazem uma transação, o comprovante do par conta-saldo muda. Lembre-se de que a prova de uma folha consiste em nós parceiros no caminho daquela folha até a raiz da árvore. Se alguma outra folha mudar, um desses nós muda, causando problemas na prática. A maioria dos usuários de blockchain deseja manter passivamente suas moedas em uma carteira, fazendo login apenas quando desejam fazer uma transação. No entanto, na prática desta blockchain sem estado, os utilizadores devem monitorizar constantemente as transações de outras pessoas para manter as suas testemunhas atualizadas. (Embora terceiros possam realizar esse monitoramento em nome dos usuários, isso se desvia do modelo padrão de blockchain sem estado. Discutiremos essa questão no final deste artigo.) Na verdade, esse é um problema para blockchains sem estado. Um desafio intransponível que representa um fardo pesado para os usuários.

Nossa conclusão: a apatridia é impossível

Este fenômeno não é exclusivo das estruturas de árvore Merkle - todos os esquemas de blockchain sem estado conhecidos exigem que os usuários atualizem suas testemunhas com frequência. Ilustramos isso neste artigo. Mais precisamente, mostramos que o número de utilizadores que devem actualizar a sua testemunha cresce aproximadamente linearmente com o número total de transacções efectuadas por todos os utilizadores.

Isso significa que mesmo que a usuária Alice não tenha feito nenhuma transação, seu testemunho pode precisar ser alterado com as transações de outros usuários. Contanto que o estado compacto armazenado pelos validadores seja muito pequeno para capturar o estado completo (ou seja, o conjunto de todos os saldos das contas), aumentar o tamanho do estado compacto não ajuda muito. Traçamos essa relação seguindo o teorema abaixo, juntamente com o número de alterações de testemunhas necessárias por dia para blockchains de diferentes rendimentos. Esses gráficos mostram quantas vezes a testemunha precisa mudar para obter um blockchain sem estado ideal. Aqui, o campo de dados refere-se ao número total de contas (no modelo de conta) ou UTXO (no modelo UTXO).

No centro da nossa prova está um argumento da teoria da informação. Um princípio central da teoria da informação proposta por Claude Shannon é que se Alice escolher aleatoriamente um objeto de um conjunto de tamanho 2n e desejar dizer a Bob qual objeto ela escolheu, ela deverá enviar a ele pelo menos n bits. Se houver um esquema de blockchain sem estado onde os usuários raramente atualizam suas testemunhas, então Alice pode dizer a Bob qual objeto ela escolheu em menos de n bits – Shannon prova que isso é impossível. Portanto, tal blockchain sem estado não pode existir.

Para simplificar, descreveremos aqui uma prova de uma afirmação um pouco mais fraca: não pode haver uma blockchain sem estado onde os usuários nunca precisem atualizar suas testemunhas. A ideia principal é que Alice codifique sua mensagem para Bob usando um esquema de blockchain sem estado. Inicialmente, Alice e Bob conhecem os pares completos de saldos de contas para todos os n usuários. Suponha que cada conta tenha pelo menos uma moeda. Tanto Alice quanto Bob também conhecem o estado sucinto V do blockchain sem estado e as testemunhas wi de todos os pares de saldo de conta (ai, bi). Alice e Bob também concordam com um mapeamento entre mensagens e conjuntos de contas. Alice escolheria um conjunto de contas A correspondente à sua mensagem e gastaria tokens dessas contas. Ela usará o blockchain sem estado para se comunicar com Bob no conjunto que ela escolher e, a partir desse conjunto, ele poderá aprender quais são as mensagens dela.

Codificação: Alice gasta um token de cada uma das contas de A. Usando um esquema de blockchain sem estado, Alice calcula um estado atualizado V' e envia V' para Bob.

Decodificação: Para cada i, Bob verifica se Verify( wi , ( ai , bi )) . Bob gera o conjunto de contas B de modo que Verify( wi , ( ai , bi )) = false.

Bob gera com sucesso o mesmo conjunto que Alice escolheu: B = A. Primeiro, observe que se Alice gastou um token da conta ai, nenhuma outra testemunha de seu saldo antigo deverá ser aceita - caso contrário, Alice seria capaz de gastar o dobro. Portanto, para cada conta ai em A, Verify( wi , ( ai , bi )) = false, e Bob incluirá essa conta em B. Por outro lado, Bob nunca incluirá em B a conta identificada por Alice. Não há como gastar uma moeda, porque os saldos dessas contas permanecem os mesmos e (lembre-se da declaração imprecisa que estávamos tentando provar) suas testemunhas nunca mudam. Portanto, B é exatamente igual a A.

Finalmente, a contradição é resolvida calculando o número de bits que Alice deve enviar para Bob. Existem 2n subconjuntos possíveis de contas que ela pode escolher e, de acordo com a lei de Shannon, ela deveria enviar pelo menos n bits para Bob. No entanto, ela envia apenas um estado V' de tamanho constante, muito menor que n bits.

(Os leitores familiarizados com criptografia podem notar que encobrimos alguns detalhes aqui; por exemplo, a decodificação de Bob falha com probabilidade insignificante. Nosso artigo inclui uma prova completa.)

Embora descrevamos nossas provas em termos de blockchains sem estado, Alice e Bob podem realizar comunicações excessivamente eficientes semelhantes usando várias outras estruturas de dados autenticadas (por exemplo, acumuladores, compromissos vetoriais). Formalizamos tais estruturas de dados usando uma nova abstração, que chamamos de sistemas de prova reversíveis.

IMPACTO DOS RESULTADOS

Nossos resultados mostram que você não pode “criptografar o estado” – não existe uma solução mágica que nos permita construir uma blockchain sem estado onde os usuários nunca precisem atualizar suas testemunhas. O estado não desaparece, mas é transferido do validador para o usuário e enviado ao usuário na forma de testemunhas atualizadas com frequência.

Existem algumas soluções potenciais, mas estas fogem do modelo blockchain estritamente sem estado. Este modelo permite que um terceiro (nem usuário nem validador) seja responsável por armazenar o estado completo. Essa parte é chamada de Nó de Serviço de Prova (com as verificações mais rigorosas de Srinivasan et al.) e usa o estado completo para gerar testemunhas atualizadas em nome dos usuários. Os usuários podem então usar essas testemunhas para realizar transações, assim como em um blockchain normal sem estado, onde os validadores ainda armazenam apenas um estado compacto. O mecanismo de incentivo do sistema, especialmente a forma como os usuários compensam os nós de prova de serviço, é uma interessante direção de pesquisa aberta.

Embora nossa discussão até agora tenha se concentrado em blockchains L1, nossos resultados também têm implicações para sistemas L2, como servidores rollup. Um rollup (seja otimista ou ZK) normalmente pega um estado grande e o confirma usando um valor pequeno armazenado em L1. Este estado inclui todas as contas de usuário em L2. Queremos que esses usuários possam sacar fundos diretamente em L1 (sem a cooperação dos servidores L2), publicando uma testemunha do saldo de sua conta corrente. Esta configuração também é uma instância do sistema de prova reversível em nosso modelo. Na verdade, pode-se argumentar que blockchains sem estado já estão implementados na prática na forma de rollups L2.

Infelizmente, isto significa que os nossos resultados de impossibilidade se aplicam diretamente. A testemunha de retirada de rollup de um usuário deve mudar frequentemente, caso contrário, quase todo o estado L2 teria que ser gravado em L1. Como resultado, as coleções hoje normalmente assumem um comitê de disponibilidade de dados (às vezes chamado de “comitê de validade”) que funciona como um “nó de serviço de prova” que ajuda os usuários a computar novas testemunhas quando estiverem prontos para sair. Nossas descobertas sugerem que os avisos aos usuários na documentação do Ethereum – “Sem acesso aos dados de transação, os usuários não podem computar as provas Merkle necessárias para provar a propriedade dos fundos e realizar saques.” – sempre serão aplicáveis.

À medida que os sistemas blockchain se desenvolvem, será ainda mais importante desenvolver formas mais eficientes de gerenciar o estado do blockchain. Embora nossos resultados para a exclusão de blockchains sem estado possam parecer negativos, os resultados de impossibilidade são úteis para os projetistas de blockchain, pois nos dizem para concentrar nossa pesquisa em outro lugar, idealmente nos ajudando a encontrar soluções viáveis mais rapidamente.