Explique em detalhes as duas novas ferramentas SNARK lançadas pela a16z crypto

Este artigo vem de um 16z, o autor original: Justin Thaler, compilado pela tradutora do Odaily Planet Daily, Jessica.

Em 10 de agosto, uma criptomoeda 16 z lançou novas ferramentas baseadas em SNARK Lasso e Jolt, que juntas representam uma nova abordagem para o design SNARK que pode melhorar o desempenho de cadeias de ferramentas amplamente implantadas em uma ordem de magnitude ou mais; fornecendo melhor, mais conveniente experiência do desenvolvedor e facilitar a auditoria.

SNARK (Succinct Non-Interactive Argument of Knowledge) é um protocolo criptográfico pelo qual qualquer pessoa pode provar a um verificador não confiável que conhece uma "testemunha" que satisfaz certas propriedades.

• Um caso de uso proeminente na Web 3 é o L2 provar ao L1 que conhece a assinatura digital que autoriza uma série de transações, de modo que a própria assinatura não precise ser armazenada e verificada pela rede L1, melhorando a escalabilidade.
• Os aplicativos fora do blockchain incluem: provar rapidamente a validade de todas as saídas produzidas por dispositivos de hardware não confiáveis, garantindo que os usuários possam confiar neles. Os indivíduos podem provar, sem conhecimento de causa, que uma autoridade confiável lhes emitiu credenciais comprovando que têm idade suficiente para acessar conteúdo com restrição de idade sem revelar sua data de nascimento. Qualquer pessoa que envie dados criptografados pela rede pode provar aos administradores que os dados estão em conformidade com a política de rede sem revelar mais detalhes.

Embora muitos SNARKs continuem sendo um custo atraente para o verificador, os SNARKs normalmente ainda introduzem cerca de seis ordens de magnitude de sobrecarga na computação do provador. O trabalho extra suportado pelo provador é altamente paralelizado, mas a sobrecarga de milhões de vezes limita severamente o escopo de aplicação dos SNARKs.

**SNARK com mais vantagens de desempenho irá acelerar o L 2 e também permitir que os construtores desbloqueiem aplicativos ainda não previstos. **É por isso que estamos introduzindo duas novas tecnologias relacionadas: Lasso, um novo parâmetro de pesquisa que pode aumentar significativamente o custo do provador; Jolt, que usa Lasso para fornecer uma nova estrutura para o chamado zkVM E um design de front-end mais amplo para projetar SNARKs. Juntos, eles melhoram o desempenho, a experiência do desenvolvedor e a auditabilidade dos projetos SNARK, que por sua vez melhoram as compilações na web 3.

Nossa implementação inicial do Lasso demonstrou acelerações de mais de 10x em comparação com os parâmetros de pesquisa na popular cadeia de ferramentas SNARK halo 2. Quando a base de código do Lasso estiver totalmente otimizada, esperamos uma aceleração de aproximadamente 40 vezes. O Jolt inclui outras inovações além do Lasso, e esperamos que ele atinja uma aceleração semelhante ou melhor do que o zkVM existente.

Encontrar parâmetros, Lasso e Jolt

Um front-end SNARK é um compilador que converte um programa de computador em um circuito que um back-end SNARK pode ingerir. (Observação: um circuito é um modelo de computação extremamente limitado em que as únicas "operações primitivas" disponíveis são a adição e a multiplicação.)

Uma ferramenta-chave nos projetos SNARK modernos é um protocolo chamado parâmetros de pesquisa, que permite que um provador não confiável envie criptograficamente um grande vetor e prove que cada entrada desse vetor está contida em algum meio de tabela predeterminado. Os parâmetros de pesquisa podem ajudar a manter os circuitos pequenos, processando com eficiência as operações que não são calculadas naturalmente por pequenas adições e multiplicações.

No entanto, como Barry Whitehat, da Ethereum Foundation, disse no ano passado, "se pudermos definir circuitos com eficiência usando apenas parâmetros de pesquisa, isso levará a ferramentas e circuitos mais simples". O circuito que projetamos realiza apenas pesquisas. Com o tempo, os parâmetros de pesquisa "se tornarão mais eficientes do que as restrições polinomiais para quase tudo".

Essa visão contrasta fortemente com a maneira como as coisas funcionam hoje, em que os desenvolvedores implantam SNARKs escrevendo programas usando linguagens específicas de domínio especiais que compilam os programas em restrições polinomiais ou codificando manualmente as restrições diretamente. Essa cadeia de ferramentas é muito trabalhosa e fornece muita área de superfície para que bugs críticos de segurança se infiltrem. Mesmo com ferramentas e circuitos complexos, o desempenho dos SNARKs ainda é lento, o que limita sua aplicabilidade.

Lasso e Jolt abordam todas as três questões principais: desempenho, experiência do desenvolvedor e auditabilidade e, juntos, eles concretizam a visão de encontrar a singularidade. Lasso e Jolt também forçam a repensar grande parte da sabedoria aceita no design SNARK.

Depois de fornecer o histórico necessário, o seguinte revisita algumas ideias comuns sobre o desempenho do SNARK e explica como elas podem ser otimizadas à luz de inovações como Lasso e Jolt.

Fundo de design SNARK: por que tão lento?

A maioria dos back-ends SNARK tem o provador comprometido criptograficamente com o valor de cada porta no circuito usando um esquema de compromisso polinomial. O provador então prova que o valor enviado realmente corresponde à execução correta do verificador de testemunhas.

Refiro-me ao trabalho do provador de um esquema de compromisso polinomial como o custo de compromisso. **SNARKs têm custos de prova adicionais de esquemas de compromisso polinomial. Mas os custos de compromisso costumam ser o gargalo. **Lasso e Jolt também. Se um SNARK é projetado onde o custo de compromisso não é o principal custo do provador, isso não significa que o esquema de compromisso polinomial seja barato. Em vez disso, significa que outros custos são mais altos do que deveriam ser.

Intuitivamente, o objetivo dos compromissos é aumentar criptograficamente com segurança a simplicidade dos sistemas de prova. Quando um provador envia um grande vetor de valores, é mais ou menos como se o provador estivesse enviando o vetor inteiro para o verificador, assim como os sistemas de prova normais enviam toda a testemunha para o verificador. Os esquemas de compromisso podem conseguir isso sem forçar os validadores a realmente receber toda a testemunha - o que significa que o objetivo do esquema de compromisso no projeto SNARK é controlar os custos do validador.

Mas esses métodos criptográficos são muito caros para o provador, especialmente em comparação com os métodos de teoria da informação que o SNARK usa fora dos esquemas de compromisso polinomial. Os métodos da teoria da informação dependem apenas de operações de campo finito. E uma operação de campo é muito mais rápida do que o tempo necessário para enviar um elemento de campo arbitrário.

Compromissos de computação envolvem múltiplas exponenciações (também conhecidas como multiplicações escalares múltiplas, ou MSMs) ou FFTs e hashes Merkle, dependendo do esquema de compromisso polinomial usado. Lasso e Jolt podem usar qualquer esquema de compromisso polinomial, mas têm um custo particularmente atraente quando instanciados usando esquemas baseados em MSM, como IPA/Bulletproofs, KZG/PST, Hyrax, Dory ou Zeromorph.

Por que Lasso e Jolt são importantes

Lasso é um novo parâmetro de pesquisa em que o provador promete menos e menores valores do que o trabalho anterior. Isso pode ser uma aceleração de 20x ou mais, onde a aceleração de 2 a 4x vem de menos valores confirmados e outra aceleração de 10x vem do fato de que todos os valores confirmados no Lasso são pequenos. Ao contrário de muitos parâmetros de pesquisa anteriores, Lasso (e Jolt) também evita FFTs, que ocupam muito espaço e podem ser um gargalo para grandes instâncias.

Além disso, o Lasso funciona mesmo com tabelas enormes, desde que essas tabelas sejam "estruturadas" (no sentido técnico preciso). Essas tabelas são muito grandes para qualquer um implementar explicitamente, mas o Lasso paga apenas pelos elementos da tabela que ele realmente acessa. Em particular, em comparação com os parâmetros de pesquisa anteriores, se a tabela for estruturada, nenhuma das partes precisará confirmar todos os valores na tabela de forma criptografada.

Lasso utiliza dois conceitos estruturais diferentes: decomposability e estruturas LDE. (LDE é um acrônimo para um conceito técnico chamado Low Degree Extended Polynomial.) A decomposição significa aproximadamente que uma única pesquisa de uma tabela pode ser respondida executando um número menor de pesquisas em uma tabela menor. Este é um requisito mais rigoroso do que a estrutura LDE, mas Lasso é particularmente eficaz quando aplicado a tabelas decomponíveis.

Solavanco

Jolt (Just One Lookup Table) é um novo frontend desbloqueado pela capacidade do Lasso de usar enormes tabelas de pesquisa. Jolt tem como alvo a abstração da máquina virtual/CPU, também conhecida como ISA (Arquitetura do Conjunto de Instruções). SNARKs que suportam esta abstração são chamados de zkVM. Por exemplo, considere o conjunto de instruções RISC-V (incluindo a extensão de multiplicação) que o projeto RISC-Zero também visa. Este é um popular ISA de código aberto desenvolvido pela comunidade de arquitetura de computadores sem SNARKs em mente.

Para cada instrução RISC-V fi, a ideia principal de Jolt é criar uma tabela de consulta contendo toda a tabela de avaliação de fi. Basicamente, para cada instrução RISC-V, a tabela de pesquisa resultante é decomponível e o laço se aplica.

Revisitando a sabedoria aceita no design SNARK

Lasso e Jolt também subvertem parte da sabedoria aceita no design SNARK.

**# 1. SNARKs de grande área são um desperdício. Todos devem usar FRI, Ligero, Brakedown ou variantes, pois evitam técnicas de curvas elípticas que geralmente são aplicáveis a grandes escalas. **

O tamanho do campo aqui corresponde aproximadamente ao tamanho dos números que aparecem na prova SNARK. Como a adição e a multiplicação de números muito grandes são caras, a ideia de que SNARKs em grandes campos são um desperdício significa que devemos nos esforçar para projetar protocolos que nunca tenham grandes números. Os compromissos baseados em MSM usam curvas elípticas, que normalmente são definidas em campos grandes (de tamanho ~2 256), portanto, essas promessas têm uma reputação de baixo desempenho.

Se faz sentido usar campos pequenos (mesmo que sejam uma opção) depende muito do aplicativo. Lasso e Jolt vão ainda mais longe. Eles mostram que, mesmo com um esquema de compromisso baseado em MSM, o trabalho do provador pode ser quase independente do tamanho do campo. Isso ocorre porque, para compromissos baseados em MSM, o tamanho dos valores confirmados é mais importante do que o tamanho dos campos nos quais esses valores residem.

Os SNARKs existentes fazem o provador se comprometer com muitos elementos de campo aleatórios. Por exemplo, o provador em um backend SNARK popular chamado Plonk compromete cerca de 7 elementos de campo aleatórios (e outros elementos de campo não aleatórios) por porta de circuito. Esses elementos de campo aleatórios podem ser grandes mesmo que todos os valores que aparecem nos cálculos comprovados sejam pequenos.

Em contraste, Lasso e Jolt exigem apenas que o provador envie um valor pequeno (o provador de Lasso também envia menos valores do que o parâmetro de pesquisa anterior). Isso melhora muito o desempenho dos esquemas baseados em MSM. No mínimo, Lasso e Jolt devem desmantelar a noção de que a comunidade deve abandonar os compromissos baseados em MSM nos casos em que o desempenho do provador é importante.

**#2 Um conjunto de instruções mais simples leva a um zkVM mais rápido. **

A complexidade do Jolt (por instrução) depende apenas do tamanho de entrada da instrução, desde que a tabela de avaliação para cada instrução seja decomponível. Jolt demonstrou que instruções surpreendentemente complexas são decomponíveis, especialmente todas as RISC-V.

Isso é contrário à crença comum de que máquinas virtuais mais simples (zkVM) necessariamente levam a circuitos menores e provadores mais rápidos associados (cada etapa da VM). Esta é a motivação por trás de zkVMs particularmente simples, como o Cairo VM, que são projetados especificamente para serem compatíveis com SNARK.

De fato, para máquinas virtuais mais simples, o Jolt atinge um custo de comprometimento menor para o provador do que os SNARKs anteriores. Por exemplo, para a execução da VM Cairo, o provador SNARK envia 51 elementos de campo em cada etapa da VM. Os SNARKs implantados pelo Cairo atualmente trabalham em campos de 251 bits (63 bits é o limite inferior rígido no tamanho do campo que um SNARK pode usar). O provador de Jolt funciona em aproximadamente 60 elementos de campo por etapa (definindo mais de tipos de dados de 64 bits) para CPUs RISC-V. Depois de considerar o fato de que os elementos de campo enviados são pequenos, o custo do Jolt prover é aproximadamente equivalente ao custo de enviar 6 elementos de campo aleatórios de 256 bits.

**#3 Não há penalidade de desempenho por quebrar cálculos grandes em pequenos pedaços. **

Com base nessa visão, os projetos atuais decompõem qualquer circuito grande em pequenos blocos, provam cada bloco separadamente e agregam recursivamente os resultados por meio de SNARKs. Essas implantações usam essa abordagem para aliviar os gargalos de desempenho em SNARKs populares. Por exemplo, SNARKs baseados em FRI requerem cerca de 100 GB de espaço de prova, mesmo para pequenos circuitos. Eles também exigem FFT, uma operação ultralinear que pode se tornar um gargalo se os SNARKs forem aplicados "simultaneamente" a grandes circuitos.

A realidade é que alguns SNARKs (como Lasso e Jolt) exibem economias de escala (em vez das deseconomias de escala encontradas nos SNARKs atualmente implantados). Isso significa que quanto maior a declaração sendo provada, menor a sobrecarga do provador em relação à verificação direta de testemunhas (ou seja, o trabalho necessário para avaliar um circuito de testemunhas sem garantir a exatidão). No nível técnico, as economias de escala vêm de dois lugares.

Aceleração de Pippenger para MSMs de tamanho n: melhoria do fator log( n ) sobre o algoritmo ingênuo. Quanto maior n, maior a melhoria.

Em parâmetros de pesquisa como Lasso, o provador paga um custo "único" que depende do tamanho da tabela de pesquisa, mas não tem nada a ver com o número de valores pesquisados. O custo único do provador é amortizado em todas as pesquisas na tabela. Blocos maiores significam mais pesquisas, o que significa melhor amortização.

A maneira popular de lidar com grandes circuitos hoje é quebrar as coisas nas menores partes possíveis. A principal restrição no tamanho de cada parte é que elas não podem ser tão pequenas que a prova de agregação recursiva se torne um gargalo para o provador.

Lasso e Jolt propõem uma abordagem essencialmente oposta. As pessoas devem usar SNARKs que tenham economias de escala. Em seguida, divida a computação grande em partes tão grandes quanto possível e repita os resultados. A principal limitação no tamanho de cada fragmento é o espaço de prova, que cresce à medida que o fragmento fica maior.

**#4 Restrições de altura são necessárias para SNARKs eficientes. **

Jolt usa R 1 CS como sua representação intermediária. Não há nenhum benefício em usar restrições Altura ou Personalizadas no Jolt. A maior parte do custo do provador em Jolt reside na pesquisa do parâmetro Lasso, em vez de provar a satisfatibilidade do sistema de restrição resultante que considera a pesquisa garantida.

Jolt é universal, por isso não perde sua versatilidade. Como tal, ele contraria o foco intenso dos desenvolvedores nas restrições de altura do projeto (geralmente especificadas manualmente) em um esforço para extrair um desempenho aprimorado dos SNARKs populares de hoje.

Claro, alguns contextos ainda podem se beneficiar de altura ou restrições personalizadas. Um exemplo importante é o Minroot VDF, cuja restrição de 5 graus pode reduzir o custo de compromisso por um fator de cerca de 3.

**#5 Esquemas de comprometimento polinomial esparso são caros e devem ser evitados sempre que possível. **

Esta é a principal crítica ao sistema de retenção recentemente introduzido chamado CCS e aos SNARKs que o suportam - Spartan e Marlin, o CCS é uma generalização clara de todos os sistemas de retenção predominantes na prática hoje.

Essa crítica é infundada. Na verdade, o núcleo técnico de Lasso e Jolt é o esquema de compromisso polinomial esparso em Spartan - Spark. O próprio Spark é uma conversão genérica de qualquer esquema de compromisso polinomial (não esparso) para um que suporte polinômios esparsos.

O Lasso otimiza e estende o Spark para garantir que o provador se comprometa apenas com valores "pequenos", mas mesmo sem essas otimizações a crítica não é justificada. Na verdade, o provador de Spartan se compromete com menos elementos de campo (aleatórios) do que os SNARKs (como Plonk, que evita compromissos polinomiais esparsos).

A abordagem da Spartan tem vantagens adicionais de desempenho, especialmente para circuitos com estruturas repetitivas. Para esses circuitos, as portas de adição não aumentam o trabalho criptográfico do provador espartano. Este trabalho só cresce com o número de variáveis em um determinado sistema de restrições, não com o número de restrições. Ao contrário de Plonk, os provadores espartanos não precisam enviar várias "cópias" diferentes da mesma variável.

Estamos otimistas de que Lasso e Jolt mudarão drasticamente a maneira como os SNARKs são projetados, melhorando o desempenho e a capacidade de auditoria. Esta é uma ferramenta chave com a incrível capacidade de minimizar o custo de compromisso do provador.