a16z lança o Lattice Jolt: provas 3x mais rápidas com segurança pós-quantum

Autor: a16z crypto

Tradução: Deep潮 TechFlow

Leitura destacada da Shenchao: O zkVM sempre foi criticado por ter "provas muito lentas e muito grandes". Nesta ocasião, a16z substituiu curvas elípticas por criptografia baseada em reticulados, aumentando diretamente a velocidade das provas em 3 vezes e reduzindo o tamanho das provas para abaixo de 100 KB. Este é o único esquema pós-quântico atualmente capaz de superar em velocidade os esquemas tradicionais baseados em curvas elípticas, impactando diretamente os custos de validação na cadeia e aplicações de privacidade.

Hoje lançamos oficialmente o Lattice Jolt, a versão mais recente do nosso zkVM (máquina virtual de conhecimento zero) de código aberto. O Jolt já era o zkVM mais rápido e mais simples atualmente, e sua arquitetura permanece inalterada. Mas a criptografia subjacente foi substituída: das curvas elípticas para a criptografia de reticulados. Essa única mudança traz simultaneamente três benefícios:

• Jolt torna-se pós-quântico seguro.
• Velocidade do prover e do verifier aumentada em 2 a 3 vezes.
• Lattice Jolt tornou-se o comprovante mais curto entre todos os zkVM pós-quânticos: atualmente menos de 100 KB, com potencial para mais compressão no futuro. Como os comprovantes precisam ser gravados na cadeia e transmitidos entre redes, quanto menor o comprovante, menor o custo de verificação.

Esses recursos cobrem todos os cenários de uso do zkVM. O mesmo prover, em uma GPU, consegue processar bilhões de ciclos de CPU e, em um telefone, comprovar milhões de ciclos. Em ambos os casos, os desenvolvedores escrevem programas comuns, sem precisar codificar manualmente circuitos que exigem conhecimento especializado. É por isso que dizemos que o Jolt é um "SNARK universal".

Mas a história maior é o significado do Lattice Jolt para o design e a adoção de SNARKs. Atualmente, quase todos os SNARKs pós-quânticos já em produção no mercado são baseados em hash. O Lattice Jolt demonstrou que SNARKs baseados em reticulados podem ser mais rápidos e mais compactos. As assinaturas digitais estão passando pela mesma transição: esquemas baseados em hash são uma escolha conservadora, mas os esquemas baseados em reticulados são os que o mundo está implantando em larga escala. Prevemos que os SNARKs seguirão o mesmo caminho, e a segunda metade deste post explicará o porquê.

O esquema de compromisso polinomial anterior do Jolt era o Dory, o único componente do sistema que dependia da criptografia de curva elíptica. O Lattice Jolt substituiu o Dory pelo Akita, um novo esquema de compromisso polinomial baseado na hipótese Module-SIS. O Lattice Jolt se alinha com a segurança completa de 128 bits com base nessa hipótese padrão e bem estudada.

Module-SIS e seu irmão Module-LWE pertencem à mesma família de suposições, e a infraestrutura digital mundial está migrando em direção a essa família. Essas suposições sustentam não apenas o padrão de assinatura digital ML-DSA, mas também o padrão de estabelecimento de chave ML-KEM, que já é o primitivo pós-quântico mais amplamente implantado globalmente.

O desenvolvimento e a implementação do Akita são liderados por pesquisadores e engenheiros da LayerZero, em colaboração com pesquisadores da Universidade Carnegie Mellon e da Universidade da Califórnia do Sul, além da nossa equipe de engenharia e pesquisa da a16z crypto.

Lattice Jolt não é apenas pós-quântico seguro, mas também mais rápido que a versão de curva elíptica que substituiu.

O aceleramento vem principalmente de uma razão simples. A curva elíptica força o Jolt a operar em um campo de 256 bits, enquanto a criptografia baseada em reticulados alcança o mesmo nível de segurança em um campo de 128 bits. O trabalho principal do provador Jolt é a multiplicação de elementos de campo (essencialmente multiplicação de números extremamente grandes), então reduzir o tamanho dos números pela metade torna cada multiplicação várias vezes mais rápida.

Jolt com Dory já está rápido: nossa última atualização de desempenho mostrou que o Jolt consegue provar cerca de 700 mil ciclos RISC-V (RV64IMAC) por segundo em um laptop, e otimizações subsequentes levaram a versão curva do Jolt além de 1 milhão de ciclos por segundo.

Lattice Jolt pode provar mais de 2 milhões de ciclos por segundo na mesma máquina.

Durante a maior parte dos últimos seis meses, não apenas desenvolvemos o Akita e o integramos ao Jolt, como também reescrevemos completamente a base de código do Jolt. Embora o Jolt já funcionasse bem na GPU anteriormente, esta reescrita tornou a implementação da GPU mais fácil de construir e otimizar.

O primeiro resultado é a implementação do Apple Metal, que trouxe grande aceleração para o hardware da Apple. (Metal é o framework da Apple usado para executar código na GPU integrada em dispositivos como MacBook e iPhone.)

• O Lattice Jolt acelerado por GPU pode provar mais de 10 milhões de ciclos RV64IMAC por segundo no MacBook.
• O Lattice Jolt apenas com CPU pode provar mais de 2 milhões de ciclos por segundo na mesma máquina.
• Mesmo a versão curva do Jolt agora consegue alcançar cerca de 4 milhões de ciclos por segundo em MacBooks com Metal.

Ou seja, com um único lançamento, o Jolt no MacBook passou de cerca de 1 milhão de ciclos por segundo (versão curva, CPU pura) para mais de 10 milhões de ciclos por segundo (versão grade, com Metal).

Visto no contexto geral: há quatro anos, quando escrevemos pela primeira vez sobre o custo do SNARK prover, provar um cálculo era milhões de vezes mais caro do que executá-lo diretamente. O Lattice Jolt reduziu esse custo para cerca de dez mil vezes. E ainda não chegamos ao fim — ainda existem oportunidades de otimização tanto no nível de engenharia quanto de protocolo.

O tamanho da prova e a velocidade do prover são igualmente importantes. Com menos de 100 KB, as provas do Lattice Jolt são significativamente menores do que outras zkVM pós-quânticas, cujas provas variam de mais de 200 KB até cerca de 600 KB ou mais.

Após a troca para o格, o uso de memória do Jolt, que já era excelente, melhorou ainda mais: o uso de espaço do prover caiu de cerca de 300 bytes por ciclo para 200 bytes. Isso significa que você pode provar milhões de ciclos RISC-V em seu telefone.

Um artigo complementar será lançado em breve, adicionando ao Lattice Jolt a propriedade de zero knowledge, necessária para aplicações de privacidade.

Ao longo dos anos, a atenção da comunidade SNARK (e praticamente todas as implantações em produção) foi direcionada aos SNARKs baseados em hash, como um caminho para a segurança pós-quântica.

Mas sempre houve uma linha contínua de pesquisa em SNARKs e compromissos de rede, abrangendo LaBRADOR, Greyhound, LatticeFold, SuperNeo e o antecessor direto do Akita, Hachi. O Lattice Jolt se baseia nessa pesquisa, introduzindo a camada de compromissos de rede em arquiteturas de zkVM de alto desempenho, enquanto comprova que os SNARKs baseados em rede são inigualáveis em velocidade e compactação.

Isso não deveria surpreender. Como mencionado anteriormente, o mesmo padrão já ocorreu antes com assinaturas digitais.

Cientistas da criptografia construíram assinaturas com base em muitas suposições. Assinaturas baseadas em hash são geralmente consideradas a escolha mais conservadora: suas suposições de segurança são simples e antigas. Mas o mundo está se movendo principalmente em direção a assinaturas baseadas em reticulados, pois são mais curtas e rápidas:

• As assinaturas ML-DSA são de aproximadamente alguns KB.
• A alternativa de assinatura digital SLH-DSA padronizada pelo NIST é muito maior.
• Para criptografia e troca de chaves, a situação é mais clara: não há esquemas de hash disponíveis (prova-se que é impossível), e a implantação pós-quântica é esmagadoramente baseada em reticulados. O ML-KEM (padrão principal de estabelecimento de chaves determinado pelo NIST em 2024) já está implantado por padrão em navegadores principais e aplicativos de comunicação, sendo amplamente utilizado em conexões TLS na web.

A analogia entre SNARK e assinaturas não é superficial. Assinaturas digitais são, por natureza, provas de conhecimento da chave privada de uma mensagem autorizada. O SNARK expande esse paradigma de uma declaração estreita para qualquer cálculo. Portanto, seria estranho se o mapa criptográfico de longo prazo dos SNARKs fosse completamente diferente do das assinaturas e da criptografia.

Também há um mal-entendido aqui que merece esclarecimento: os SNARKs baseados em hash são frequentemente descritos como uma escolha pós-quantum conservadora porque “dependem apenas de funções hash”. Isso só é verdade se a função hash subjacente não for algébrica.

Atualmente, a maioria das implantações de SNARK baseadas em hash depende de construções de hash algébrico amigáveis ao SNARK (como o Poseidon) para provar com baixo custo que o hash foi avaliado corretamente. Isso é especialmente importante para recursão (onde recursão se refere à prova de que você possui uma prova válida de SNARK). Essas construções possuem mais estrutura do que funções de hash padrão, e sua análise criptográfica ainda não está madura.

Em resumo, não temos confiança na segurança das funções de hash algébricas. Mesmo assim, elas ainda são amplamente utilizadas em sistemas SNARK de produção. (No entanto, houve um sinal de progresso: a Ethereum Foundation anunciou recentemente que abandonará seu uso.)

A suposição oculta da álgebra hash não é a única utilizada nos SNARKs baseados em hash já implantados: muitos sistemas historicamente usaram limites especulativos de gap de proximidade para definir níveis específicos de segurança, em vez de usar limites completamente comprovados. Alguns desses limites considerados os mais fortes foram posteriormente demonstrados como incorretos.

Mesmo evitando os SNARKs baseados em hash mencionados acima, seus objetivos de segurança geralmente são inferiores a 128 bits, pois a segurança completa de 128 bits impõe uma sobrecarga de desempenho significativa. Por quê? SNARKs baseados em hash não conseguem atingir segurança de 128 bits em um corpo de 128 bits, pois seu erro de confiabilidade escala como n/|F|, onde n é aproximadamente o tamanho da declaração provada e |F| é o tamanho do corpo. Portanto, provar uma declaração de um bilhão de passos em um corpo de 128 bits resulta em uma perda de cerca de 30 bits de segurança, deixando-a abaixo de 100 bits. Em contraste, o erro de confiabilidade do Lattice Jolt escala como log(n)/|F|, preservando quase toda a segurança completa de 128 bits no mesmo corpo (a pequena perda log(n) pode ser recuperada por técnicas padrão).

Ironicamente, alguns sistemas promovidos como escolhas "conservadoras" pós-quânticas dependem simultaneamente de funções de hash algébricas, limites especulativos de gap de proximidade e níveis de segurança alvo abaixo de 128 bits. Portanto, embora os SNARKs baseados em hash sejam uma direção importante, eles não se tornam automaticamente opções de baixo risco, como muitos acreditam.

Sempre acreditamos que o Jolt não deveria estar vinculado a uma única base criptográfica. Devemos ter SNARKs maduros e de alto desempenho baseados em curvas, funções hash e reticulados. Diferentes suposições e características de desempenho serão adequadas para diferentes cenários.

Mas, se considerado o assinatura digital, o SNARK baseado em reticulados se tornará a escolha pós-quantum mais amplamente implantada.

Jolt está em uma posição excepcional para essa transição. O design original do Jolt aproveita as propriedades das curvas elípticas que são particularmente úteis para compromissos, incluindo compromissos rápidos para vetores esparsos. Compromissos de reticulados possuem as mesmas propriedades: quando a maioria das entradas do vetor é zero ou pequena, o custo de comprometer o vetor é baixo, e o Jolt quase exclusivamente compromete esse tipo de vetor. Essa característica nos permite substituir o Dory pelo Akita, mantendo o restante do Jolt inalterado.

Vamos construir uma versão do Jolt baseada em hash. No entanto, em comparação com as versões do Jolt baseadas em curvas e em reticulados, a versão baseada em hash é menos eficiente em termos de espaço, produz provas maiores e apresenta diversos problemas complexos. Isso ocorre porque os trabalhos mais promissores em SNARKs baseados em hash operam no corpo binário. Essa base numérica facilita a prova da avaliação de funções de hash, mas não corresponde ao modo aritmético dos processadores. Essa incompatibilidade torna a prova de multiplicações comuns de CPU cara. Mesmo assim, o ecossistema deve ter um zkVM para cada principal família de suposições, assim como ocorre no campo de assinaturas digitais.

O Lattice Jolt atende a todas as necessidades dos construtores para um zkVM: pós-quântico, transparente, rápido, compacto e eficiente em espaço. Ele leva a rota de pesquisa em SNARKs de rede da LaBRADOR até o Hachi para um zkVM de nível produtivo, sem abrir mão de nenhuma das vantagens que tornaram o Jolt inicialmente rápido.

Nosso objetivo não é apenas tornar o zkVM mais rápido disponível de código aberto para qualquer um, mas também eliminar significativamente a necessidade de otimização manual de SNARKs para aplicações específicas. Isso não exige que o Jolt seja tão rápido quanto provadores manualmente otimizados. Esse é um objetivo impossível, assim como exigir que uma CPU iguale um ASIC dedicado em cada tarefa. Basta que o Jolt seja rápido o suficiente para oferecer uma experiência de usuário aceitável.

Para as afirmações “pequenas” relacionadas à prova do cliente (onde circuitos otimizados manualmente atualmente dominam esses cenários), o critério chave é gerar a prova em menos de um segundo no celular. O Jolt já está próximo de alcançar isso, e muitas soluções de aceleração estão em andamento.

A era do SNARK chegou.

Este conteúdo é fornecido apenas para fins informativos e não deve ser confiado como aconselhamento jurídico, comercial, de investimento ou fiscal. Em relação a esses assuntos, você deve consultar seu próprio consultor. Qualquer menção a valores mobiliários ou ativos digitais é apenas para fins ilustrativos e não constitui aconselhamento de investimento nem uma oferta de serviços de consultoria de investimento. Além disso, este conteúdo não é direcionado a nenhum investidor ou potencial investidor e não deve, em nenhuma circunstância, ser usado como base para tomar decisões de investimento em qualquer fundo gerido pela a16z. (A oferta para investir em fundos da a16z é feita exclusivamente por meio do memorando privado do fundo, contrato de subscrição e outros documentos relacionados, e você deve ler integralmente esses documentos.) Os investimentos mencionados, citados ou descritos não representam todos os investimentos realizados pelos veículos geridos pela a16z, e não há garantia de que esses investimentos gerarão lucros ou de que futuros investimentos terão características ou resultados semelhantes. A lista de investimentos realizados pelos fundos geridos pela Andreessen Horowitz (excluindo investimentos cuja divulgação pública não foi autorizada pelo emissor e investimentos em ativos digitais listados que não foram divulgados) está disponível em https://a16z.com/investments/.

Os gráficos fornecidos neste texto são apenas para referência e não devem ser utilizados como base para qualquer decisão de investimento. Desempenhos passados não indicam resultados futuros. Este conteúdo reflete as condições na data mencionada. Qualquer previsão, estimativa, declaração prospectiva, meta, perspectiva e/ou opinião expressa neste material pode ser alterada a qualquer momento, sem aviso prévio, e pode diferir ou ser oposta às opiniões expressas por outras pessoas. Para mais informações importantes, consulte https://a16z.com/disclosures.