a16z lança Lattice Jolt: provas 3x mais rápidas e resistentes a ataques quânticos

Autor: a16z crypto

Compilação: TechFlow

Introdução da TechFlow: As zkVMs têm sido criticadas por serem "lentas a provar e volumosas". A a16z substituiu as curvas elípticas por criptografia baseada em reticulados, tornando as provas 3x mais rápidas e reduzindo o tamanho para menos de 100 KB. Esta é atualmente a única solução pós-quântica que supera em velocidade os esquemas tradicionais de curvas elípticas, com impacto direto nos custos de verificação on-chain e nas aplicações de privacidade.

Hoje lançamos oficialmente o Lattice Jolt, a versão mais recente da nossa zkVM (máquina virtual de conhecimento zero) de código aberto. O Jolt já era a zkVM mais rápida e simples disponível, e a sua arquitetura permanece inalterada. Mas a criptografia subjacente mudou: de curvas elípticas para criptografia baseada em reticulados. Esta única alteração traz três benefícios:

• O Jolt torna-se pós-quântico seguro.
• A velocidade do provador e do verificador aumenta 2 a 3 vezes.
• O Lattice Jolt passa a ter a prova mais curta entre todas as zkVMs pós-quânticas: atualmente menos de 100 KB, com potencial para compressão adicional. As provas precisam de ser publicadas on-chain e transmitidas entre redes; quanto menor a prova, menor o custo de verificação.

Estas características abrangem todos os casos de uso da zkVM. O mesmo provador pode processar milhares de milhões de ciclos de CPU em GPUs e provar milhões de ciclos em telemóveis. Em ambos os casos, os programadores escrevem programas normais, sem necessidade de criar circuitos manualmente, o que exigiria conhecimentos especializados. É 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 em produção são baseados em funções de hash. O Lattice Jolt demonstra que os SNARKs baseados em reticulados podem ser mais rápidos e compactos. As assinaturas digitais estão a passar pela mesma transição: os esquemas de hash são a escolha conservadora, mas os esquemas de reticulados são os que o mundo está a implementar em grande escala. Prevemos que os SNARKs sigam o mesmo caminho, e a segunda metade deste artigo explica porquê.

Substituir curvas elípticas por reticulados

O esquema de compromisso polinomial anterior do Jolt, chamado Dory, era o único componente do sistema que dependia de criptografia de curvas elípticas. O Lattice Jolt substitui o Dory pelo Akita, um novo esquema de compromisso polinomial baseado na hipótese de reticulados Module-SIS. O Lattice Jolt baseia-se nesta hipótese padrão e bem estudada, visando segurança total de 128 bits.

O Module-SIS e o seu irmão Module-LWE pertencem à mesma família de hipóteses para a qual a infraestrutura digital mundial está a migrar. Estas hipóteses sustentam não só o padrão de assinatura digital ML-DSA, mas também o padrão de estabelecimento de chaves ML-KEM, que já é a primitiva pós-quântica mais amplamente implementada a nível global.

O desenvolvimento e a implementação do Akita foram liderados por investigadores e engenheiros da LayerZero, com a participação de investigadores da Carnegie Mellon University, da University of Southern California e das nossas equipas de engenharia e investigação na a16z crypto.

Porque é que o Lattice Jolt é mais rápido

O Lattice Jolt não é apenas pós-quântico seguro; é mais rápido do que a versão de curvas elípticas que substitui.

A aceleração vem principalmente de uma razão simples. As curvas elípticas obrigam o Jolt a trabalhar em corpos de 256 bits, enquanto a criptografia de reticulados atinge o mesmo nível de segurança em corpos de 128 bits. O trabalho principal do provador do Jolt é a multiplicação de elementos do corpo (essencialmente multiplicação de números muito grandes), pelo que reduzir o tamanho dos números para metade torna cada multiplicação várias vezes mais rápida.

O Jolt com Dory já era rápido: a nossa última atualização de desempenho mostrou que o Jolt provava cerca de 700.000 ciclos RISC-V (RV64IMAC) por segundo num portátil, e otimizações posteriores levaram a versão de curvas do Jolt para além de 1 milhão de ciclos por segundo.

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

Durante grande parte dos últimos seis meses, não só desenvolvemos o Akita e o integrámos no Jolt, como também reescrevemos a base de código do Jolt de raiz. O Jolt já funcionava bem em GPUs, mas esta reescrita tornou a implementação em GPU mais fácil de construir e otimizar.

O primeiro resultado é uma implementação em Apple Metal, que traz uma enorme aceleração para o hardware da Apple. (Metal é a estrutura da Apple para executar código nas GPUs integradas em dispositivos como MacBooks e iPhones.)

• O Lattice Jolt acelerado por GPU prova mais de 10 milhões de ciclos RV64IMAC por segundo num MacBook.
• O Lattice Jolt puramente em CPU prova mais de 2 milhões de ciclos por segundo na mesma máquina.
• Até a versão de curvas do Jolt com Metal num MacBook atinge agora cerca de 4 milhões de ciclos por segundo.

Ou seja, num único lançamento, o Jolt num MacBook passou de cerca de 1 milhão de ciclos por segundo (versão de curvas, apenas CPU) para mais de 10 milhões de ciclos por segundo (versão de reticulados, com Metal).

Colocando estes números em perspetiva: há quatro anos, quando escrevemos pela primeira vez sobre os custos de um provador SNARK, 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 chegámos ao limite; há espaço para otimizações a nível de engenharia e de protocolo.

O tamanho da prova é tão importante como a velocidade do provador. Com menos de 100 KB, a prova do Lattice Jolt já é muito menor do que a de outras zkVMs pós-quânticas, cujas provas variam de mais de 200 KB até cerca de 600 KB ou mais.

A mudança para reticulados também melhorou a já excelente pegada de memória do Jolt: o uso de espaço do provador caiu de cerca de 300 bytes por ciclo para 200 bytes. Isto significa que é possível provar milhões de ciclos RISC-V num telemóvel.

Um artigo complementar será publicado em breve, adicionando conhecimento zero ao Lattice Jolt, uma propriedade necessária para aplicações de privacidade.

Porquê reticulados em vez de hashes

Durante anos, a atenção da comunidade SNARK (e praticamente todas as implementações em produção) centrou-se em SNARKs baseados em hashes como caminho para a segurança pós-quântica.

Mas também tem havido uma linha contínua de investigação em SNARKs e compromissos baseados em reticulados, incluindo LaBRADOR, Greyhound, LatticeFold, SuperNeo e o antecessor direto do Akita, o Hachi. O Lattice Jolt baseia-se nesta investigação, trazendo a camada de compromissos de reticulados para uma arquitetura zkVM de alto desempenho e demonstrando que os SNARKs baseados em reticulados são incomparáveis em velocidade e compacidade.

Isto não deveria ser surpreendente. Como referido, o mesmo padrão já ocorreu com as assinaturas digitais.

Os criptógrafos construíram assinaturas com base em muitas hipóteses. As assinaturas baseadas em hash são geralmente consideradas a escolha mais conservadora: as suas hipóteses de segurança são simples e antigas. Mas o mundo está a migrar principalmente para assinaturas de reticulados, porque são mais curtas e rápidas:

• As assinaturas ML-DSA têm cerca de alguns KB.
• A alternativa de hash padronizada pelo NIST, SLH-DSA, é várias vezes maior.
• Para encriptação e troca de chaves, a situação é ainda mais clara: não existe qualquer opção baseada em hash (está provado que é impossível), e a implementação pós-quântica é esmagadoramente baseada em reticulados. O ML-KEM (o principal padrão de estabelecimento de chaves finalizado pelo NIST em 2024) já é implementado por defeito nos principais navegadores e aplicações de mensagens, sendo utilizado em inúmeras ligações TLS na Internet.

A analogia entre SNARKs e assinaturas não é superficial. Uma assinatura digital é essencialmente uma prova de conhecimento de uma chave privada sobre uma mensagem autorizada. Os SNARKs estendem este paradigma de uma afirmação restrita para computação arbitrária. Portanto, seria estranho se o panorama criptográfico de longo prazo dos SNARKs fosse completamente diferente do das assinaturas e da encriptação.

Há também um equívoco que vale a pena esclarecer: os SNARKs baseados em hash são frequentemente descritos como a escolha pós-quântica conservadora porque "dependem apenas de funções de hash". Isto só é verdade se a função de hash subjacente for não algébrica.

Atualmente, a maioria das implementações de SNARKs baseados em hash depende de construções de hash algébricas amigáveis a SNARKs (como Poseidon) para provar a avaliação correta do hash a baixo custo. Isto é especialmente importante para a recursão (aqui, recursão significa provar que se possui uma prova SNARK válida). Estas construções têm mais estrutura do que as funções de hash padrão, e a sua criptoanálise ainda é imatura.

Em suma, não temos confiança na segurança das funções de hash algébricas. Apesar disso, são hoje amplamente utilizadas em sistemas SNARK de produção. (No entanto, há um sinal de progresso: a Ethereum Foundation anunciou recentemente que deixará de as utilizar.)

As hashes algébricas não são a única hipótese oculta nos SNARKs baseados em hash implementados: muitos sistemas historicamente usam limites especulativos de proximity-gap para definir níveis de segurança concretos, em vez de limites totalmente comprovados. Alguns dos limites considerados mais fortes foram posteriormente provados errados.

Mesmo evitando as especulações acima, os SNARKs baseados em hash têm frequentemente objetivos de segurança abaixo de 128 bits, porque a segurança total de 128 bits acarreta custos de desempenho significativos. Porquê? Os SNARKs baseados em hash não conseguem atingir 128 bits de segurança em corpos de 128 bits, porque o seu erro de solidez escala com n/|F|, onde n é aproximadamente o tamanho da afirmação a provar e |F| é o tamanho do corpo. Assim, provar uma afirmação de mil milhões de passos num corpo de 128 bits perde cerca de 30 bits de segurança, ficando abaixo de 100 bits. Em contraste, o erro de solidez do Lattice Jolt escala com log(n)/|F|, preservando quase toda a segurança de 128 bits no mesmo corpo (a pequena perda de log(n) pode ser recuperada com técnicas padrão).

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

Um Jolt, três fundações: curvas, reticulados e hashes

Sempre acreditámos que o Jolt não deve estar vinculado a uma única fundação criptográfica. Devemos ter SNARKs maduros e de alto desempenho baseados em curvas, hashes e reticulados. Diferentes hipóteses e características de desempenho serão adequadas a diferentes cenários.

Mas, tomando as assinaturas digitais como referência, os SNARKs baseados em reticulados tornar-se-ão a escolha pós-quântica mais amplamente implementada.

O Jolt está numa posição invulgarmente vantajosa nesta transição. O design original do Jolt aproveitou propriedades das curvas elípticas particularmente úteis para compromissos, incluindo o compromisso rápido de vetores esparsos. Os compromissos de reticulados têm a mesma propriedade: quando a maioria das entradas de um vetor é zero ou pequena, o custo de comprometer o vetor é baixo, e o Jolt compromete quase exclusivamente este tipo de vetores. Esta propriedade permitiu-nos substituir o Dory pelo Akita, mantendo o resto do Jolt inalterado.

Vamos construir uma versão do Jolt baseada em hashes. Mas, em comparação com o Jolt baseado em curvas e em reticulados, a versão baseada em hashes é menos eficiente em espaço, tem provas maiores e apresenta várias complexidades. Isto porque os SNARKs baseados em hashes mais promissores trabalham em corpos binários. Este sistema numérico facilita a prova da avaliação de hashes, mas não corresponde à forma como a CPU faz aritmética. Esta incompatibilidade torna cara a prova de multiplicações normais da CPU. Mesmo assim, o ecossistema deve ter zkVMs sob cada família principal de hipóteses, tal como no domínio das assinaturas digitais.

SNARK universal

O Lattice Jolt satisfaz de uma só vez todas as necessidades dos construtores de zkVMs: pós-quântico, transparente, rápido, compacto e eficiente em espaço. Traz a linha de investigação de SNARKs de reticulados, de LaBRADOR a Hachi, para uma zkVM de nível de produção, sem abdicar de nenhuma das vantagens que originalmente tornaram o Jolt rápido.

O nosso objetivo não é apenas disponibilizar a zkVM de maior desempenho em código aberto para qualquer pessoa, mas também eliminar em grande parte a necessidade de otimizar manualmente SNARKs para aplicações específicas. Isto não exige que o Jolt seja tão rápido como provadores otimizados manualmente. Esse é um objetivo impossível, como exigir que uma CPU iguale ASICs dedicados em todas as tarefas. Exige apenas que o Jolt seja suficientemente rápido para proporcionar uma experiência de utilizador aceitável.

Para afirmações "pequenas" relacionadas com provas do lado do cliente (onde os circuitos otimizados manualmente dominam atualmente), o critério chave é gerar uma prova num telemóvel em cerca de um segundo. O Jolt já está perto de o conseguir, e há muitos esquemas de aceleração em curso.

A era dos SNARKs de reticulados chegou.