Novo artigo de Vitalik: O possível futuro do protocolo Ethereum The Verge

Na verdade, levaremos anos para obter provas de validade do consenso do Ethereum.

Título original: 《Possible futures of the Ethereum protocol, part 4: The Verge》

Autor: Vitalik Buterin

Tradução: Mensh, ChainCatcher

 

Agradecimentos especiais a Justin Drake, Hsia-wei Wanp, Guillaume Ballet, Icinacio, Rosh Rudolf, Lev Soukhanoy, Ryan Sean Adams e Uma Roy pelo feedback e revisão.

Uma das funcionalidades mais poderosas do blockchain é que qualquer pessoa pode rodar um nó em seu próprio computador e verificar a correção da blockchain. Mesmo que 9596 nós que executam o consenso da cadeia (PoW, PoS) concordem imediatamente em mudar as regras e comecem a produzir blocos de acordo com as novas regras, qualquer pessoa rodando um nó de validação completa recusará aceitar a cadeia. Os mineradores que não pertencem a essa conspiração automaticamente convergirão para uma cadeia que continua seguindo as regras antigas e continuarão a construir sobre ela, e os usuários que fazem validação completa seguirão essa cadeia.

Essa é a diferença fundamental entre blockchain e sistemas centralizados. No entanto, para que essa característica se mantenha, rodar um nó de validação completa precisa ser realmente viável para um número suficiente de pessoas. Isso vale tanto para os proponentes (pois, se eles não validarem a cadeia, não estarão contribuindo para a execução das regras do protocolo) quanto para usuários comuns. Hoje, é possível rodar um nó em um notebook de consumo (incluindo o notebook usado para escrever este artigo), mas fazer isso ainda é difícil. O objetivo do The Verge é mudar esse cenário, tornando o custo computacional de validar completamente a cadeia muito baixo, de modo que cada carteira de celular, carteira de navegador e até mesmo smartwatches validem por padrão.

Roteiro do The Verge 2023

Originalmente, "Verge" referia-se à migração do armazenamento de estado do Ethereum para árvores Verkle — uma estrutura de árvore que permite provas mais compactas, possibilitando a validação sem estado dos blocos do Ethereum. Um nó pode validar um bloco Ethereum sem armazenar nenhum estado do Ethereum (saldos de contas, código de contratos, armazenamento, etc.) em seu disco rígido, ao custo de alguns centenas de KB de dados de prova e algumas centenas de milissegundos extras para validar uma prova. Hoje, Verge representa uma visão maior, focada em alcançar a validação do Ethereum com máxima eficiência de recursos, incluindo não apenas a tecnologia de validação sem estado, mas também o uso de SNARKs para validar toda a execução do Ethereum.

Além do foco de longo prazo em SNARKs para validar toda a cadeia, outro novo problema é se as árvores Verkle são a melhor tecnologia. Árvores Verkle são vulneráveis a ataques de computadores quânticos, então, se substituirmos as atuais árvores KECCAK Merkle Patricia por árvores Verkle, teremos que substituí-las novamente no futuro. O método auto-substituível das árvores Merkle é pular diretamente para STARKs usando ramos Merkle, colocando-os em uma árvore binária. Historicamente, devido ao overhead e à complexidade técnica, essa abordagem era considerada inviável. No entanto, recentemente, vimos a Starkware provar 1,7 milhão de hashes Poseidon por segundo em um notebook, e, com o surgimento de tecnologias como GKB, o tempo de prova para hashes mais "tradicionais" também está diminuindo rapidamente. Portanto, no último ano, "Verge" tornou-se mais aberto, com várias possibilidades.

The Verge: Objetivos-chave

• Clientes sem estado: o espaço de armazenamento necessário para clientes de validação completa e nós marcadores não deve exceder alguns GB.
• (A longo prazo) Validar completamente a cadeia (consenso e execução) em um smartwatch. Baixe alguns dados, valide o SNARK, pronto.

Neste capítulo

• Clientes sem estado: Verkle ou STARKs
• Provas de validade da execução EVM
• Provas de validade do consenso

Validação sem estado: Verkle ou STARKs

Qual problema queremos resolver?

Hoje, clientes Ethereum precisam armazenar centenas de gigabytes de dados de estado para validar blocos, e esse número cresce a cada ano. Os dados de estado bruto aumentam cerca de 30GB por ano, e cada cliente precisa armazenar dados extras para atualizar eficientemente as tríades.

Isso reduz o número de usuários capazes de rodar nós de validação completa do Ethereum: embora discos rígidos grandes o suficiente para armazenar todo o estado do Ethereum e até anos de histórico estejam amplamente disponíveis, os computadores que as pessoas compram normalmente vêm com apenas algumas centenas de gigabytes de armazenamento. O tamanho do estado também traz grande atrito ao processo de inicialização de um nó: o nó precisa baixar todo o estado, o que pode levar horas ou dias. Isso gera vários efeitos em cadeia. Por exemplo, aumenta muito a dificuldade de os operadores de nós atualizarem suas configurações. Tecnicamente, é possível fazer upgrades sem downtime — iniciar um novo cliente, esperar sincronizar, depois desligar o antigo e transferir as chaves — mas, na prática, isso é tecnicamente complexo.

Como funciona?

Validação sem estado é uma técnica que permite que um nó valide blocos sem possuir todo o estado. Em vez disso, cada bloco vem com uma testemunha, que inclui: (i) valores, códigos, saldos, armazenamento em posições específicas do estado que o bloco acessará; (ii) provas criptográficas de que esses valores estão corretos.

Na prática, implementar validação sem estado requer mudar a estrutura da árvore de estado do Ethereum. Isso porque a atual árvore Merkle Patricia é extremamente desfavorável para qualquer esquema de prova criptográfica, especialmente no pior caso. Seja "ramificação" Merkle "pura" ou a possibilidade de "embrulhar" em STARKs, ambas são afetadas. A principal dificuldade vem de algumas fraquezas do MPT:

1. É uma árvore hexária (cada nó tem 16 filhos). Isso significa que, em uma árvore de tamanho N, uma prova precisa em média de 32*(16-1)*log16(N) = 120*log2(N) bytes, ou cerca de 3840 bytes para uma árvore de 2^32 itens. Para uma árvore binária, seriam apenas 32*(2-1)*log2(N) = 32*log2(N) bytes, ou cerca de 1024 bytes.

2. O código não é Merklizado. Isso significa que, para provar qualquer acesso ao código da conta, é preciso fornecer todo o código, até 24000 bytes.

 

Podemos calcular o pior caso da seguinte forma:

30000000 gas / 2400 (custo de leitura de conta fria) * (5 * 488 + 24000) = 330000000 bytes

O custo de ramificação é um pouco menor (usando 5*480 em vez de 8*480), pois, quando há muitas ramificações, a parte superior se repete. Mas, mesmo assim, a quantidade de dados a ser baixada em um slot é completamente irrealista. Se tentarmos embrulhar isso em um STARK, enfrentamos dois problemas: (i) KECCAK não é amigável a STARKs; (ii) 330MB de dados significam que precisamos provar 5 milhões de chamadas à função round do KECCAK, o que pode ser inviável para qualquer hardware exceto os mais potentes, mesmo que consigamos tornar a prova STARK de KECCAK mais eficiente.

Se substituirmos diretamente a árvore hexária por uma binária e Merklizarmos o código adicionalmente, o pior caso se torna aproximadamente 30000000/2400*32*(32-14+8) = 10400000 bytes (14 é a subtração dos bits redundantes para 2^14 ramificações, e 8 é o comprimento da prova para o bloco de código folha). Vale notar que isso requer mudar o custo de gas, cobrando por cada bloco de código acessado; EIP-4762 faz exatamente isso. 10,4 MB é bem melhor, mas ainda é muito para muitos nós baixarem em um slot. Portanto, precisamos de técnicas mais avançadas. Existem duas soluções líderes: árvores Verkle e árvores de hash binárias STARKed.

Árvores Verkle

Árvores Verkle usam compromissos vetoriais baseados em curvas elípticas para provas mais curtas. A chave é que, independentemente da largura da árvore, cada parte da prova para uma relação pai-filho tem apenas 32 bytes. A única limitação para a largura da árvore é que, se for muito larga, a eficiência computacional da prova diminui. A implementação proposta para o Ethereum tem largura 256.

Assim, o tamanho de cada ramificação na prova se torna 32 - log256(N) = 4*log2(N) bytes. Portanto, o tamanho máximo teórico da prova é aproximadamente 30000000 / 2400 *32* (32 -14 + 8) / 8 = 130000 bytes (devido à distribuição desigual dos blocos de estado, o cálculo real difere um pouco, mas como aproximação inicial é aceitável).

Outro ponto a notar é que, em todos os exemplos acima, esse "pior caso" não é o pior possível: um caso ainda pior é um atacante "minerando" dois endereços para terem prefixos comuns longos na árvore e lendo dados de um deles, o que pode dobrar o comprimento da ramificação no pior caso. Mas, mesmo assim, o comprimento máximo da prova em árvores Verkle é de 2,6MB, o que está de acordo com os dados de verificação no pior caso atualmente.

Também aproveitamos essa observação para outra coisa: tornamos o custo de acessar espaços de armazenamento "adjacentes" muito baixo: seja muitos blocos de código do mesmo contrato ou slots de armazenamento adjacentes. O EIP-4762 define adjacência e cobra apenas 200 gas por acesso adjacente. Nesse caso, o tamanho máximo da prova se torna 30000000 / 200*32 - 4800800 bytes, ainda dentro da tolerância. Se quisermos reduzir esse valor por segurança, podemos aumentar um pouco o custo do acesso adjacente.

Árvore de hash binária STARKed

O princípio dessa técnica é autoexplicativo: basta fazer uma árvore binária, obter uma prova máxima de 10,4 MB, provar os valores do bloco e depois substituir a prova por um STARK. Assim, a prova contém apenas os dados provados, mais um overhead fixo de 100-300kB do STARK real.

O principal desafio aqui é o tempo de verificação. Podemos fazer o mesmo cálculo acima, mas contando hashes em vez de bytes. Um bloco de 10,4 MB significa 330000 hashes. Se adicionarmos a possibilidade de um atacante "minerar" endereços com prefixos comuns longos, o pior caso chega a cerca de 660000 hashes. Portanto, se conseguirmos provar 200.000 hashes por segundo, está tudo bem.

Em notebooks de consumo usando o hash Poseidon, esses números já são atingidos, e o hash Poseidon foi projetado especificamente para ser amigável a STARKs. No entanto, o sistema Poseidon ainda é relativamente novo, então muitos não confiam totalmente em sua segurança. Portanto, há dois caminhos realistas:

1. Analisar rapidamente a segurança do Poseidon em larga escala e se familiarizar o suficiente para implantá-lo no L1
2. Usar funções de hash mais "conservadoras", como SHA256 ou BLAKE

Para provar funções de hash conservadoras, o círculo STARK da Starkware, no momento da escrita, só consegue provar 10-30k hashes por segundo em notebooks de consumo. Mas a tecnologia STARK está avançando rapidamente. Mesmo hoje, técnicas baseadas em GKR mostram que essa velocidade pode aumentar para a faixa de 100-200k.

Casos de uso de testemunhas além da validação de blocos

Além da validação de blocos, há outros três casos de uso críticos que exigem validação sem estado mais eficiente:

• Mempool: quando uma transação é transmitida, os nós na rede P2P precisam validar a transação antes de retransmiti-la. Hoje, isso inclui verificar assinaturas, saldo suficiente e nonce correto. No futuro (por exemplo, com abstração de conta nativa, como EIP-7701), isso pode envolver rodar código EVM que acessa algum estado. Se o nó for sem estado, a transação precisa vir com provas dos objetos de estado.
• Listas de inclusão: é um recurso proposto que permite que validadores de prova de participação (possivelmente pequenos e simples) forcem o próximo bloco a incluir uma transação, independentemente da vontade dos construtores de bloco (possivelmente grandes e complexos). Isso enfraquece a capacidade de atores poderosos manipularem a blockchain atrasando transações. Mas, para isso, os validadores precisam validar a validade das transações na lista de inclusão.
• Clientes leves: se quisermos que usuários acessem a cadeia via carteiras (como Metamask, Rainbow, Rabby, etc.), eles precisam rodar um cliente leve (como Helios). O módulo central do Helios fornece ao usuário a raiz de estado verificada. Para uma experiência totalmente sem confiança, o usuário precisa de provas para cada chamada RPC (por exemplo, para uma chamada eth_call, o usuário precisa de provas de todos os estados acessados durante a chamada).

Todos esses casos de uso têm algo em comum: precisam de muitas provas, mas cada uma é pequena. Portanto, provas STARK não fazem sentido prático para eles; o mais realista é usar ramos Merkle diretamente. Outra vantagem dos ramos Merkle é que são atualizáveis: dada uma prova de um objeto de estado enraizado no bloco B, se recebermos um sub-bloco B2 e sua testemunha, podemos atualizar a prova para enraizá-la em B2. Provas Verkle também são nativamente atualizáveis.

Quais são as conexões com pesquisas existentes:

• Verkle trees
• Artigo original de John Kuszmaul sobre árvores Verkle
• Starkware
• Artigo Poseidon2
• Ajtai (função de hash rápida alternativa baseada em dureza de lattice)
• Verkle.info

O que mais pode ser feito?

O trabalho principal restante é

1. Mais análise das consequências do EIP-4762 (mudanças no custo de gas sem estado)

2. Mais trabalho para completar e testar o programa de transição, que é a principal parte da complexidade de qualquer implementação sem estado

3. Mais análise de segurança para Poseidon, Ajtai e outras funções de hash "amigáveis a STARK"

4. Desenvolver ainda mais protocolos STARK ultraeficientes para funções de hash "conservadoras" (ou "tradicionais"), como abordagens baseadas em Binius ou GKR.

Além disso, em breve decidiremos entre três opções: (i) árvores Verkle, (ii) funções de hash amigáveis a STARK e (iii) funções de hash conservadoras. Suas características podem ser resumidas na tabela abaixo:

Além desses "números principais", há outros fatores importantes a considerar:

• Hoje, o código das árvores Verkle já está bastante maduro. Usar qualquer outro código além de Verkle atrasaria a implantação, provavelmente adiando um hard fork. Isso não é um problema, especialmente se precisarmos de tempo extra para análise de funções de hash ou implementação de validadores, ou se houver outras funcionalidades importantes que queremos incluir no Ethereum mais cedo.
• Atualizar a raiz de estado usando hashes é mais rápido do que usando árvores Verkle. Isso significa que métodos baseados em hash podem reduzir o tempo de sincronização de nós completos.
• Árvores Verkle têm propriedades interessantes de atualização de testemunhas — as testemunhas Verkle são atualizáveis. Isso é útil para mempool, listas de inclusão e outros casos de uso, e pode ajudar na eficiência da implementação: se um objeto de estado for atualizado, é possível atualizar a testemunha da penúltima camada sem ler o conteúdo da última camada.
• Árvores Verkle são mais difíceis de provar em SNARKs. Se quisermos reduzir o tamanho da prova para alguns milhares de bytes, provas Verkle trazem dificuldades. Isso porque a verificação da prova Verkle introduz muitas operações de 256 bits, exigindo que o sistema de prova tenha muito overhead ou uma estrutura interna personalizada com partes de prova Verkle de 256 bits. Isso não é um problema para o sem estado em si, mas traz mais dificuldades.

Se quisermos obter atualização de testemunha Verkle de forma segura contra quânticos e razoavelmente eficiente, outro caminho possível é usar árvores Merkle baseadas em lattice.

Se, no pior caso, a eficiência do sistema de prova não for suficiente, podemos usar a ferramenta inesperada do gas multidimensional para compensar: definir limites de gas separados para (i) calldata; (ii) computação; (iii) acesso ao estado e possivelmente outros recursos. Gas multidimensional aumenta a complexidade, mas, em troca, limita mais estritamente a razão entre o caso médio e o pior caso. Com gas multidimensional, o número máximo de ramificações a serem provadas pode cair de 12500 para, por exemplo, 3000. Isso faria com que BLAKE3 fosse (apertadamente) suficiente mesmo hoje.

Gas multidimensional permite que os limites de recursos do bloco se aproximem mais dos limites do hardware subjacente

Outra ferramenta inesperada é atrasar o cálculo da raiz de estado para o slot após o bloco. Assim, temos 12 segundos inteiros para calcular a raiz de estado, o que significa que, mesmo no caso mais extremo, 60000 hashes por segundo de tempo de prova são suficientes, novamente tornando BLAKE3 apenas suficiente.

A desvantagem desse método é aumentar a latência do cliente leve em um slot, mas há técnicas mais inteligentes para reduzir essa latência para apenas a latência de geração da prova. Por exemplo, a prova pode ser transmitida na rede assim que for gerada por qualquer nó, sem esperar pelo próximo bloco.

Como isso interage com outras partes do roteiro?

Resolver o problema do sem estado aumenta muito a dificuldade do staking solo. Se houver tecnologia para reduzir o saldo mínimo de staking solo, como Orbit SSF ou estratégias de camada de aplicação como staking em squads, isso se tornará mais viável.

Se o EOF for introduzido ao mesmo tempo, a análise de gas multidimensional se torna mais fácil. Isso porque a principal complexidade de execução do gas multidimensional vem de lidar com chamadas filhas que não transmitem todo o gas do pai, e o EOF simplesmente torna tais chamadas filhas ilegais, tornando o problema trivial (e a abstração de conta nativa fornecerá uma alternativa interna para o uso atual de gas parcial).

Há também uma sinergia importante entre validação sem estado e expiração de histórico. Hoje, clientes precisam armazenar quase 1TB de dados históricos; isso é várias vezes o tamanho dos dados de estado. Mesmo que o cliente seja sem estado, a visão de um cliente quase sem armazenamento não será alcançada a menos que possamos remover a responsabilidade de armazenar dados históricos. O primeiro passo nessa direção é o EIP-4444, que também significa armazenar dados históricos em torrents ou na Portal Network.

Provas de validade da execução EVM

Qual problema queremos resolver?

O objetivo de longo prazo da validação de blocos Ethereum é claro — deve ser possível validar um bloco Ethereum por: (i) baixar o bloco, ou até mesmo apenas uma pequena parte da amostragem de disponibilidade de dados do bloco; (ii) validar uma pequena prova de que o bloco é válido. Isso seria uma operação de baixíssimo recurso, possível em clientes móveis, carteiras de navegador e até mesmo em outra cadeia (sem a parte de disponibilidade de dados).

Para isso, precisamos de provas SNARK ou STARK para (i) a camada de consenso (prova de participação) e (ii) a camada de execução (EVM). O primeiro é um desafio por si só, que deve ser resolvido com melhorias contínuas na camada de consenso (por exemplo, para finalização de slot único). O segundo requer provas de execução EVM.

O que é e como funciona?

Formalmente, na especificação do Ethereum, a EVM é definida como uma função de transição de estado: você tem um estado anterior S, um bloco B, e está calculando um estado posterior S' = STF(S, B). Se o usuário estiver usando um cliente leve, ele não possui S e S' completos, nem E; em vez disso, ele possui uma raiz de estado anterior R, uma raiz de estado posterior R' e um hash de bloco H.

• Entrada pública: raiz de estado anterior R, raiz de estado posterior R', hash do bloco H
• Entrada privada: corpo do bloco B, objetos do estado acessados pelo bloco Q, os mesmos objetos após a execução do bloco Q', provas de estado (como ramos Merkle) P
• Afirmação 1: P é uma prova válida de que Q contém partes do estado representado por R
• Afirmação 2: Se rodarmos STF em Q, (i) o processo de execução acessa apenas objetos internos a Q, (ii) o bloco é válido, (iii) o resultado é Q'
• Afirmação 3: Se recalcularmos a nova raiz de estado usando Q' e as informações de P, obtemos R'

Se isso existir, podemos ter um cliente leve que valida completamente a execução EVM do Ethereum. Isso já reduz bastante os recursos do cliente. Para um cliente Ethereum totalmente validado, também precisamos fazer o mesmo para o consenso.

Provas de validade para execução EVM já existem e são amplamente usadas em L2. Mas, para torná-las viáveis no L1, ainda há muito trabalho a ser feito.

Quais são as conexões com pesquisas existentes?

• EFPSE ZK-EVM (descontinuado devido a alternativas melhores)
• Zeth, que compila a EVM para a RISC-0 ZK-VM
• Projeto de verificação formal do ZK-EVM

O que mais pode ser feito?

Hoje, as provas de validade dos sistemas de contabilidade eletrônica têm duas deficiências: segurança e tempo de verificação.

Uma prova de validade segura precisa garantir que o SNARK realmente verifica o cálculo da EVM e que não há vulnerabilidades. As duas principais técnicas para aumentar a segurança são múltiplos validadores e verificação formal. Múltiplos validadores significa ter várias implementações independentes de provas de validade, como múltiplos clientes; se um bloco for provado por um subconjunto suficientemente grande dessas implementações, o cliente aceita o bloco. Verificação formal envolve usar ferramentas normalmente usadas para provar teoremas matemáticos, como Lean4, para provar que a prova de validade só aceita execuções corretas da especificação EVM subjacente (por exemplo, semântica EVM K ou a especificação da camada de execução do Ethereum escrita em python (EELS)).

Tempo de verificação suficientemente rápido significa que qualquer bloco Ethereum pode ser verificado em menos de 4 segundos. Hoje, estamos longe desse objetivo, embora estejamos mais próximos do que imaginávamos há dois anos. Para alcançá-lo, precisamos avançar em três direções:

• Paralelização — atualmente, o verificador EVM mais rápido pode provar um bloco Ethereum em média em 15 segundos. Isso é feito paralelizando entre centenas de GPUs e, no final, agregando o trabalho delas. Teoricamente, sabemos como criar um verificador EVM que prova um cálculo em O(log(N)) tempo: uma GPU faz cada etapa, depois fazemos uma "árvore de agregação":

Implementar isso tem desafios. Mesmo no pior caso, em que uma transação muito grande ocupa todo o bloco, a divisão do cálculo não pode ser por transação, mas por opcode (da EVM ou da máquina virtual subjacente, como RISC-V). Garantir que a "memória" da VM seja consistente entre as diferentes partes da prova é um desafio chave na implementação. Mas, se conseguirmos implementar essa prova recursiva, sabemos que, mesmo sem outras melhorias, pelo menos o problema de latência do provador estará resolvido.

• Otimização do sistema de prova — novos sistemas de prova, como Orion, Binius, GRK e outros, provavelmente levarão a mais uma grande redução no tempo de verificação de cálculos genéricos.
• Outras mudanças no custo de gas da EVM — muitas coisas na EVM podem ser otimizadas para favorecer os provadores, especialmente no pior caso. Se um atacante puder construir um bloco que bloqueie o provador por dez minutos, não adianta conseguir provar um bloco Ethereum comum em 4 segundos. As mudanças necessárias na EVM podem ser divididas em:
• Mudanças no custo de gas — se uma operação leva muito tempo para ser provada, mesmo que seja relativamente rápida de calcular, ela deve ter um custo de gas alto. O EIP-7667 foi proposto para lidar com os piores casos: ele aumenta muito o custo de gas das funções de hash (tradicionais), pois seus opcodes e pré-compilados são relativamente baratos. Para compensar, podemos reduzir o custo de gas de opcodes EVM com baixo custo de prova, mantendo a vazão média.
• Substituição de estruturas de dados — além de substituir a árvore de estado por métodos mais amigáveis a STARKs, precisamos substituir a lista de transações, árvore de recibos e outras estruturas caras de provar. O EIP de Etan Kissling que move as estruturas de transações e recibos para SSZ é um passo nessa direção.

Além disso, as duas ferramentas mencionadas na seção anterior (gas multidimensional e raiz de estado atrasada) também podem ajudar aqui. Mas, vale notar que, ao contrário da validação sem estado, usar essas duas ferramentas significa que já temos tecnologia suficiente para o que precisamos atualmente, enquanto, mesmo com essas técnicas, a verificação completa do ZK-EVM ainda requer mais trabalho — apenas menos trabalho.

Um ponto não mencionado acima é o hardware do provador: usar GPU, FPGA e ASIC para gerar provas mais rapidamente. Fabric Cryptography, Cysic e Accseal são três empresas que avançam nessa área. Isso é muito valioso para L2, mas dificilmente será um fator decisivo para L1, pois há um forte desejo de manter o L1 altamente descentralizado, o que significa que a geração de provas deve estar dentro do alcance razoável dos usuários do Ethereum, sem depender de gargalos de hardware de uma única empresa. L2 pode fazer escolhas mais agressivas.

Há ainda mais trabalho a ser feito nessas áreas:

• Provas paralelas exigem que diferentes partes do sistema de prova possam "compartilhar memória" (como tabelas de lookup). Sabemos como fazer isso, mas precisa ser implementado.
• Precisamos de mais análise para encontrar o conjunto ideal de mudanças no custo de gas para minimizar o tempo de verificação no pior caso.
• Precisamos de mais trabalho em sistemas de prova

Os possíveis trade-offs são:

• Segurança vs. tempo do provador: escolher funções de hash mais agressivas, sistemas de prova mais complexos ou hipóteses de segurança mais ousadas pode reduzir o tempo do provador.
• Descentralização vs. tempo do provador: a comunidade precisa concordar sobre as "especificações" do hardware do provador. É aceitável exigir grandes entidades como provadores? Queremos que um notebook de consumo de ponta prove um bloco Ethereum em 4 segundos? Algo intermediário?
• Grau de quebra de compatibilidade retroativa: outras deficiências podem ser compensadas por mudanças mais agressivas no custo de gas, mas isso pode aumentar desproporcionalmente o custo de certos aplicativos, forçando desenvolvedores a reescrever e reimplantar código para manter a viabilidade econômica. Da mesma forma, essas duas ferramentas também têm sua própria complexidade e desvantagens.

Como isso interage com outras partes do roteiro?

A tecnologia central necessária para provas de validade EVM no L1 é amplamente compartilhada com outros dois campos:

• Provas de validade em L2 (ou seja, "ZK rollup")
• Método sem estado de "prova de hash binária STARK"

Se conseguirmos implementar provas de validade no L1, finalmente poderemos ter staking solo fácil: até mesmo os computadores mais fracos (incluindo celulares ou smartwatches) poderão fazer staking. Isso aumenta ainda mais o valor de resolver outras restrições do staking solo (como o limite mínimo de 32ETH).

Além disso, provas de validade EVM no L1 podem aumentar muito o limite de gas do L1.

Provas de validade do consenso

Qual problema queremos resolver?

Se quisermos validar completamente um bloco Ethereum com SNARK, a execução da EVM não é a única parte que precisamos provar. Também precisamos provar o consenso, ou seja, a parte do sistema que lida com depósitos, saques, assinaturas, atualização de saldo dos validadores e outros elementos da prova de participação do Ethereum.

O consenso é muito mais simples que a EVM, mas enfrenta o desafio de não termos convolução EVM L2, então, de qualquer forma, a maior parte do trabalho precisa ser feita. Portanto, qualquer implementação de prova do consenso do Ethereum precisa ser feita "do zero", embora o sistema de prova em si possa ser construído sobre trabalho compartilhado.

O que é e como funciona?

A Beacon Chain é definida como uma função de transição de estado, assim como a EVM. A função de transição de estado é composta principalmente por três partes:

• ECADD (para verificar assinaturas BLS)
• Pairing (para verificar assinaturas BLS)
• Hash SHA256 (para ler e atualizar o estado)

Em cada bloco, precisamos provar 1-16 ECADD BLS12-381 para cada validador (pode ser mais de um, pois assinaturas podem estar em vários conjuntos). Isso pode ser mitigado com técnicas de pré-cálculo de subconjuntos, então podemos dizer que cada validador só precisa provar um ECADD BLS12-381. Atualmente, há 30000 assinaturas de validadores por slot. No futuro, com a finalização de slot único, isso pode mudar em duas direções: se formos pela rota "força bruta", o número de validadores por slot pode aumentar para 1 milhão. Por outro lado, se usarmos Orbit SSF, o número de validadores ficará em 32768 ou até 8192.

Como funciona a agregação BLS: verificar a assinatura total requer apenas um ECADD por participante, não um ECMUL. Mas 30000 ECADDs ainda é muita prova.

Quanto ao pairing, atualmente há até 128 provas por slot, exigindo 128 verificações de pairing. Com o ElP-7549 e outras mudanças, isso pode cair para 16 por slot. O número de pairings é pequeno, mas o custo é altíssimo: cada pairing leva milhares de vezes mais tempo para rodar (ou provar) do que um ECADD.

Um dos principais desafios de provar operações BLS12-381 é que não há uma curva conveniente com ordem igual ao tamanho do campo BLS12-381, o que aumenta bastante o overhead para qualquer sistema de prova. Por outro lado, as árvores Verkle propostas para o Ethereum são construídas com a curva Bandersnatch, tornando o próprio BLS12-381 a curva usada no sistema SNARK para provar ramos Verkle. Uma implementação simples pode provar 100 adições G1 por segundo; para velocidade suficiente, quase certamente será necessário usar técnicas inteligentes como GKR.

Para hashes SHA256, o pior caso hoje é o bloco de transição de época, onde toda a árvore de balanço curto dos validadores e muitos balanços de validadores são atualizados. A árvore de balanço curto de cada validador tem apenas um byte, então há 1 MB de dados para re-hash. Isso equivale a 32768 chamadas SHA256. Se mil validadores tiverem saldo acima ou abaixo de um limite, será necessário atualizar o saldo efetivo nos registros dos validadores, o que equivale a mil ramos Merkle, ou cerca de dez mil hashes. O mecanismo de embaralhamento requer 90 bits por validador (11 MB de dados), mas isso pode ser calculado a qualquer momento em uma época. Com finalização de slot único, esses números podem variar. O embaralhamento pode se tornar desnecessário, embora Orbit possa restaurar essa necessidade em certa medida.

Outro desafio é a necessidade de recuperar todo o estado dos validadores, incluindo chaves públicas, para validar um bloco. Para 1 milhão de validadores, só ler as chaves públicas requer 48 milhões de bytes, mais os ramos Merkle. Isso exige milhões de hashes por época. Se precisarmos provar a validade do PoS, uma abordagem realista é algum tipo de computação incremental verificável: armazenar uma estrutura de dados separada no sistema de prova, otimizada para busca eficiente e para provar atualizações nessa estrutura.

Em resumo, há muitos desafios. Para enfrentá-los da forma mais eficiente, provavelmente será necessário um redesenho profundo da Beacon Chain, possivelmente junto com a transição para finalização de slot único. Esse redesenho pode incluir:

• Mudança de função de hash: atualmente, usamos o SHA256 "completo", então, devido ao padding, cada chamada corresponde a duas chamadas da função de compressão. Se mudarmos para SHA256 compress, ganhamos pelo menos 2x. Se mudarmos para Poseidon, podemos ganhar 100x, resolvendo todos os nossos problemas (pelo menos para hashes): a 1,7 milhão de hashes por segundo (54MB), até 1 milhão de registros de validadores podem ser "lidos" em segundos.
• Se for Orbit, armazenar diretamente os registros embaralhados dos validadores: se escolhermos um número fixo de validadores (como 8192 ou 32768) para o comitê de um slot, colocamos todos juntos no estado, minimizando os hashes necessários para ler todas as chaves públicas dos validadores na prova. Isso também permite atualizar todos os balanços de forma eficiente.
• Agregação de assinaturas: qualquer esquema de agregação de assinaturas de alta performance envolverá alguma prova recursiva, com diferentes nós da rede provando subconjuntos de assinaturas. Isso naturalmente distribui o trabalho de prova entre vários nós, reduzindo muito o trabalho do "provador final".
• Outros esquemas de assinatura: para assinaturas Lamport+Merkle, precisamos de 256 + 32 hashes para verificar uma assinatura; multiplicando por 32768 signatários, temos 9437184 hashes. Otimizando o esquema de assinatura, podemos melhorar ainda mais esse resultado por um pequeno fator constante. Se usarmos Poseidon, isso pode ser provado em um único slot. Mas, na prática, usar agregação recursiva será mais rápido.

Quais são as conexões com pesquisas existentes?

• Provas sucintas de consenso Ethereum (apenas para o comitê de sincronização)
• Helios dentro do SP1 sucinto
• Pré-compilado sucinto BLS12-381
• Verificação de assinatura agregada BLS baseada em Halo2

O que mais precisa ser feito, e quais são os trade-offs:

Na prática, levaremos anos para obter provas de validade do consenso do Ethereum. Isso coincide com o tempo necessário para implementar finalização de slot único, Orbit, mudanças no esquema de assinatura e análise de segurança suficiente para confiar em funções de hash "agressivas" como Poseidon. Portanto, a abordagem mais sensata é resolver esses outros problemas e considerar a compatibilidade com STARKs durante esse processo.

O principal trade-off provavelmente será na ordem das operações, entre uma abordagem mais gradual de reforma da camada de consenso do Ethereum e uma abordagem mais agressiva de "mudar tudo de uma vez". Para a EVM, a abordagem gradual faz sentido, pois minimiza a interferência na compatibilidade retroativa. Para a camada de consenso, o impacto na compatibilidade retroativa é menor, e repensar mais "abrangentemente" os detalhes da Beacon Chain para otimizar a compatibilidade com SNARKs pode ser benéfico.

Como isso interage com outras partes do roteiro?

Ao redesenhar o PoS do Ethereum a longo prazo, a compatibilidade com STARKs deve ser uma prioridade, especialmente para finalização de slot único, Orbit, mudanças no esquema de assinatura e agregação de assinaturas.