a16z: Sobre a impossibilidade de "Blockchain sem estado"

Originalmente escrito por Miranda Christ e Joseph Bonneau

Compilação do texto original: Deep Tide TechFlow

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

À medida que a blockchain cresce com contas ou UTXOs suficientes para suportar transações diárias reais para uma parcela considerável da população, esta carga de armazenamento se tornará incontrolável, tornando difícil tornar-se um validador e uma ameaça à descentralização. Uma solução tentadora é recorrer à criptografia, onde ferramentas como árvores Merkle e provas de conhecimento zero nos ajudam a alcançar coisas que antes eram inimagináveis.

Este é exatamente o objetivo de um “blockchain sem estado”. Mas apesar de muitas pesquisas sobre eles, ainda estão longe de serem práticos. Mas acontece que este atraso no progresso é inerente – a lacuna entre estas construções e a praticidade nunca será superada. Nosso trabalho recente mostra que qualquer proposta de blockchain sem estado, por mais inteligente que seja, não é viável sem medidas adicionais para gerenciar o estado. Contudo, como mostramos no final deste artigo, este resultado de improbabilidade não deve ser desanimador.

sem status

Hoje, o estado é enorme, 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), o que ainda é inaceitável hoje. Tal como concebido actualmente, o estado necessário para suportar verdadeiramente as transacções diárias (dezenas a centenas de milhares de transacções por segundo) tornar-se-ia incontrolável, exigindo gigabytes ou mesmo petabytes de armazenamento.

Isto motivou as pessoas a encontrar formas técnicas de reduzir significativamente a quantidade de estado exigida pelos validadores. Crucial é a implementação de uma blockchain sem estado, que exigiria que os validadores armazenassem apenas estados de tamanho constante, independentemente do rendimento da transação (na verdade, o termo é um termo impróprio: ainda há estado, pequeno o suficiente, para ser prático em qualquer futuro). rendimento - geralmente tamanho constante). Esse requisito de armazenamento leve facilitará a execução de um nó validador; de maneira otimista, todos poderão executar um nó em seus telefones. Dado que aumentar o número de validadores aumenta a segurança da cadeia, é importante diminuir a barreira à entrada dos validadores.

Apesar de muitas pesquisas sobre blockchains sem estado (por exemplo, por Todd, Buterin, Boneh et al., e 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 e o saldo do usuário estão incluídos no compromisso estatal global. Quando os usuários realizam transações, eles enviam essa testemunha aos validadores para mostrar que suas contas possuem 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 irrealista sobre os usuários. Da mesma forma, imagine se você monitorasse constantemente todas as outras transações de cartão de crédito globalmente e atualizasse 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 ser capazes de interagir com o blockchain offline e somente ao enviar transações. Em muitos casos, como carteiras de hardware, atualizar testemunhas não é apenas inconveniente, mas impossível.

Isso nos leva a uma questão de pesquisa natural: podemos construir uma blockchain sem estado que não exija atualizações frequentes de testemunhas (ou que exija apenas atualizações esporádicas de testemunhas)? Para responder a esta questão, desenvolvemos uma nova estrutura teórica (Sistema de Prova Revogável) que generaliza blockchains sem estado. Utilizando este quadro, demonstramos um resultado improvável: o compromisso entre um estado global compacto e atualizações frequentes de testemunhas é inerentemente difícil de conciliar. 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 construção de blockchain sem estado e a praticidade nunca será superada.

Antecedentes da nossa pesquisa

Para ajudar a entender nossos resultados de impossibilidade, primeiro descrevemos uma maneira natural, mas ineficiente, de construir blockchains sem estado usando árvores Merkle. Nosso objetivo é permitir que os validadores determinem se uma transação enviada por um usuário é válida – por exemplo, se o usuário tem saldo suficiente na conta 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 um nó folha. O estado de tamanho constante V armazenado pelos validadores é a raiz desta árvore, que atua como um compromisso para um conjunto de pares de saldos de contas. Cada usuário mantém seu testemunho como prova de inclusão Merkle. Uma prova Merkle de inclusão para uma folha (a,b) consiste em nós parceiros (v1,...,vk) ao longo do caminho daquela folha até a raiz da árvore. Dada uma transação pela conta a e um saldo reivindicado b, um verificador pode verificar se b é de fato o saldo da conta a, verificando a prova (v1,...,vk) de (a,b) em relação ao seu estado atual V. Nesse caso, o validador executa a transação e deve atualizar o saldo da conta de acordo. Uma propriedade conveniente das árvores Merkle é que, dada uma prova Merkle de inclusão de uma folha, é fácil calcular a raiz do resultado quando essa folha muda. Em outras palavras, o verificador pode calcular facilmente um estado atualizado V' que captura o novo saldo da conta a após a transação ser executada.

Este esquema de árvore Merkle tem duas desvantagens principais. Primeiro, o testemunho de um usuário é relativamente grande, crescendo logaritmicamente com o número total de contas no sistema. Idealmente, eles deveriam ter tamanho constante, e podemos conseguir isso usando esquemas como acumuladores RSA.

A segunda desvantagem é mais difícil de evitar: cada vez que outro usuário faz uma transação, o comprovante do par de saldo da conta muda. Lembre-se de que a prova para um nó folha consiste nos nós parceiros no caminho desse nó folha até a raiz da árvore. Se os outros nós folha mudarem, um dos nós mudará, causando um problema real. A maioria dos usuários de blockchain deseja manter passivamente suas moedas em carteiras e só ficar online quando desejam fazer transações. No entanto, em uma blockchain sem estado, os usuários devem monitorar constantemente as transações de outras pessoas para manter as informações de suas testemunhas atualizadas. Embora um terceiro possa realizar esse monitoramento em nome do usuário, isso se desvia do modelo padrão de blockchain sem estado. Na prática, este é um desafio intransponível para blockchains sem estado, colocando um fardo pesado sobre os usuários.

Nossa conclusão: a apatridia não é possível

Este fenômeno não se aplica apenas a este tipo de estrutura de árvore Merkle - todos os esquemas de blockchain sem estado conhecidos exigem que os usuários atualizem suas informações de testemunhas com frequência, o que demonstramos aqui. Mais precisamente, mostramos que o número de usuários que devem atualizar suas informações de testemunhas cresce aproximadamente linearmente com o número total de transações feitas por todos os usuários.

Isso significa que mesmo que a usuária Alice não faça nenhuma transação, suas informações de testemunha podem precisar ser alteradas 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 mostrada abaixo com base em nosso teorema, juntamente com o número de alterações de testemunhas necessárias por dia para blockchains com diferentes rendimentos. Esses gráficos mostram o número de vezes que um blockchain sem estado ideal precisaria alterar as informações da testemunha. Aqui, o universo de dados refere-se ao número total de contas no modelo de conta ou ao número total de UTXOs 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, formalizado por Claude Shannon, é que se Alice escolhe aleatoriamente um objeto de um conjunto de tamanho 2n e deseja dizer a Bob qual objeto ela escolheu, ela deve enviar a ele pelo menos n bits. Se existir um esquema de blockchain sem estado onde os usuários raramente atualizam suas informações de testemunha, Alice pode dizer a Bob qual objeto ela escolheu com menos de n bits, o que é impossível, como Shannon provou. Portanto, tal blockchain sem estado não existe.

Para simplificar, descrevemos aqui uma prova de uma afirmação um pouco mais fraca: não existe blockchain sem estado onde os usuários nunca precisem atualizar suas informações de testemunhas. A questão é que Alice usa um esquema de blockchain sem estado para codificar sua mensagem para Bob. Inicialmente, Alice e Bob conhecem o conjunto completo de pares 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 escolherá um conjunto A de contas correspondente à sua mensagem e gastará as moedas dessas contas. Ela usará o blockchain sem estado para comunicar a Bob o conjunto de sua escolha, a partir do qual ele poderá aprender sobre ela.

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

Decodificação: Para cada i, Bob verifica se Verify(wi, (ai, bi)) é verdadeiro. 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 gastar uma moeda da conta ai, o testemunho do seu saldo antigo não deverá mais ser aceito – 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 contas das quais Alice não gastou moedas, porque os saldos dessas contas permanecem os mesmos e (lembre-se da declaração relaxada que queremos provar) suas testemunhas nunca mudarão. Portanto, B é exatamente igual a A.

Finalmente, resolvemos nossa contradição calculando o número de bits que Alice deveria enviar para Bob. Existem 2^n subconjuntos que ela pode escolher, então, 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, que é muito menor que n bits.

Embora tenhamos usado um blockchain sem estado ao descrever nossa prova, Alice e Bob podem realizar uma comunicação eficiente semelhante usando uma variedade de outras estruturas de dados autenticadas, incluindo acumuladores, compromissos de vetores e dicionários autenticados. Formalizamos tais estruturas de dados usando uma nova abstração que chamamos de sistema de prova reversível.

Efeito do resultado

Nossos resultados mostram que não é possível “eliminar o estado criptograficamente” e que não existe solução mágica para um esquema de compromisso que nos permita construir uma blockchain sem estado onde os usuários nunca precisem atualizar suas testemunhas. O estado não desaparece, mas é transferido dos validadores e enviado aos usuários na forma de atualizações frequentes de testemunhas.

Existem algumas outras soluções promissoras que se desviam do modelo blockchain estritamente sem estado. Um relaxamento natural deste modelo é permitir que terceiros (nem usuários nem validadores) sejam responsáveis por armazenar o estado completo. Esse terceiro, chamado nó de serviço de prova, usa o estado completo para gerar as informações de testemunha mais recentes para o usuário. Os usuários podem então realizar transações usando essas testemunhas como em um blockchain sem estado normal, onde os validadores ainda armazenam apenas estados compactos. O mecanismo de incentivo deste 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. Rollups (sejam otimistas ou ZK) normalmente armazenam um compromisso com um estado grande em L1 com um valor pequeno. Este estado inclui todas as contas de usuário em L2. Queremos que estes utilizadores possam levantar fundos diretamente em L1 (sem a cooperação dos servidores L2), publicando uma testemunha do saldo da sua conta corrente. Esta configuração também é um exemplo de 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 L2 Rollups.

Infelizmente, porém, isto significa que os nossos resultados de impossibilidade se aplicam diretamente. A testemunha de busca 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, os Rollups hoje normalmente assumem a existência de um comitê de disponibilidade de dados (às vezes chamado de "validium"), semelhante a um "nó de serviço de prova" que ajuda os usuários a computar novas testemunhas quando estiverem prontos para puxar. Nossos resultados mostram que o aviso aos usuários na documentação do Ethereum: “Sem dados de transação, os usuários não podem computar provas Merkle para provar a propriedade de fundos e realizar saques.” sempre se aplicará.