Os zk-SNARKs (Zero-knowledge, Succinct, Non-interactive ARguments of Knowledge) são poderosos primitivos criptográficos que permitem que uma parte, o provador, convença outra parte, o verificador, de que uma determinada declaração é verdadeira sem revelar nada além da validade da declaração. Eles ganharam ampla atenção devido a suas aplicações em computação privada verificável, fornecendo prova da correção da execução de programas de computador e ajudando a dimensionar blockchains. Acreditamos que os SNARKs terão um impacto significativo na formação do nosso mundo, conforme descrevemos em nosso post. O SNARKs funciona como um guarda-chuva para diferentes tipos de sistemas de prova, usando diferentes esquemas de compromisso polinomial (PCS), esquemas de aritmetização, provas de oráculo interativo (IOP) ou provas verificáveis probabilisticamente (PCP). No entanto, as ideias e os conceitos básicos datam de meados da década de 1980. O desenvolvimento se acelerou significativamente após a introdução do Bitcoin e do Ethereum, que provaram ser um caso de uso empolgante e poderoso, pois é possível dimensioná-los usando provas de conhecimento zero (geralmente chamadas de provas de validade para esse caso de uso específico). Os SNARKs são uma ferramenta essencial para a escalabilidade do blockchain. Como Ben-Sasson descreve, nos últimos anos houve uma explosão cambriana de provas criptográficas. Cada sistema de prova oferece vantagens e desvantagens e foi projetado com determinadas compensações em mente. Avanços no hardware, melhores algoritmos, novos argumentos e dispositivos resultam em um desempenho aprimorado e no surgimento de novos sistemas. Muitos deles são usados na produção, e continuamos ampliando os limites. Teremos um sistema de prova geral para todas as aplicações ou vários sistemas adequados a diferentes necessidades? Acreditamos que é improvável que um sistema de prova domine todos eles porque:

1. A diversidade de aplicativos.
2. Os tipos de restrições que temos (em relação à memória, tempos de verificação, tempos de prova).
3. A necessidade de robustez (se um sistema de prova for quebrado, ainda teremos outros).

Mesmo que os sistemas de prova mudem muito, todos eles oferecem uma propriedade significativa: as provas podem ser verificadas rapidamente. Ter uma camada que verifica as provas e pode ser facilmente adaptada para lidar com novos sistemas de prova resolve as dificuldades associadas à mudança da camada de base, como a Ethereum. Fornecer uma visão geral das diferentes características dos SNARKs:

• Pressupostos criptográficos: funções hash resistentes a colisões, problema de log discreto em curvas elípticas, conhecimento do expoente.
• Configuração transparente versus confiável.
• Tempo do provador: linear vs. superlinear.
• Tempo do verificador: tempo constante, logarítmico, sublinear, linear.
• Tamanho da prova.
• Facilidade de recursão.
• Esquema de aritmetização.
• Polinômios univariados versus polinômios multivariados.

Esta postagem analisará as origens dos SNARKs, alguns blocos de construção fundamentais e a ascensão (e queda) de diferentes sistemas de prova. A postagem não tem a intenção de ser uma análise exaustiva dos sistemas de prova. Em vez disso, concentramo-nos naqueles que tiveram um impacto sobre nós. É claro que esses desenvolvimentos só foram possíveis graças ao excelente trabalho e às ideias dos pioneiros desse campo.

Fundamentos

Como mencionamos, as provas de conhecimento zero não são novas. As definições, os fundamentos, os teoremas importantes e até mesmo os protocolos importantes foram estabelecidos a partir de meados da década de 1980. Algumas das principais ideias e protocolos que usamos para criar SNARKs modernos foram propostos na década de 1990 (o protocolo sumcheck) ou mesmo antes do advento do Bitcoin (GKR em 2007). Os principais problemas com sua adoção estavam relacionados à falta de um caso de uso poderoso (a Internet não era tão desenvolvida na década de 1990) e à quantidade de poder computacional necessário.

Provas de conhecimento zero: as origens (1985/1989)

O campo das provas de conhecimento zero apareceu na literatura acadêmica com o artigo de Goldwasser, Micali e Rackoff. Para uma discussão sobre as origens, o senhor pode ver o vídeo a seguir. O artigo introduziu as noções de completude, solidez e conhecimento zero, fornecendo construções para a residuosidade quadrática e a não residuosidade quadrática.

Protocolo Sumcheck (1992)

O protocolo sumcheck foi proposto por Lund, Fortnow, Karloff e Nisan em 1992. É um dos blocos de construção mais importantes para provas interativas sucintas. Ele nos ajuda a reduzir uma reivindicação sobre a soma das avaliações de um polinômio multivariado a uma única avaliação em um ponto escolhido aleatoriamente.

Goldwasser-Kalai-Rothblum (GKR) (2007)

O protocolo GKR é um protocolo interativo que tem um verificador que é executado linearmente no número de portas de um circuito, enquanto o verificador é executado sublinearmente no tamanho do circuito. No protocolo, o provador e o verificador concordam com um circuito aritmético de fan-in-two em um campo finito de profundidade d, com a camada d correspondendo à camada de entrada e a camada 0 sendo a camada de saída. O protocolo começa com uma reivindicação referente à saída do circuito, que é reduzida a uma reivindicação sobre os valores da camada anterior. Usando a recursão, podemos transformar isso em uma afirmação sobre as entradas do circuito, que pode ser verificada facilmente. Essas reduções são obtidas por meio do protocolo sumcheck.

Esquema de compromisso polinomial KZG (2010)

Kate, Zaverucha e Goldberg apresentaram em 2010 um esquema de compromisso para polinômios usando um grupo de emparelhamento bilinear. O compromisso consiste em um único elemento de grupo, e o responsável pelo compromisso pode abrir o compromisso de forma eficiente para qualquer avaliação correta do polinômio. Além disso, devido às técnicas de loteamento, a abertura pode ser feita para várias avaliações. Os compromissos da KZG forneceram um dos blocos de construção básicos para vários SNARKs eficientes, como Pinocchio, Groth16 e Plonk. Ele também está no centro do EIP-4844. Para ter uma intuição sobre as técnicas de batching, o senhor pode ver nosso post sobre a ponte Mina-Ethereum.

SNARKs práticos usando curvas elípticas

As primeiras construções práticas de SNARKs surgiram em 2013. Isso exigia uma etapa de pré-processamento para gerar as chaves de comprovação e verificação, e eram específicas do programa/circuito. Essas chaves podem ser muito grandes e dependem de parâmetros secretos que devem permanecer desconhecidos pelas partes; caso contrário, elas poderiam forjar provas. A transformação do código em algo que pudesse ser comprovado exigia a compilação do código em um sistema de restrições polinomiais. No início, isso tinha que ser feito manualmente, o que consome muito tempo e é propenso a erros. Os avanços nessa área tentaram eliminar alguns dos principais problemas:

1. Ter provadores mais eficientes.
2. Reduzir a quantidade de pré-processamento.
3. Ter configurações universais em vez de específicas para o circuito.
4. Evite ter configurações confiáveis.
5. Desenvolver maneiras de descrever circuitos usando uma linguagem de alto nível, em vez de escrever as restrições polinomiais manualmente.

Pinocchio (2013)

Pinocchio é o primeiro zk-SNARK prático e utilizável. O SNARK é baseado em programas aritméticos quadráticos (QAP). O tamanho da prova era originalmente de 288 bytes. A cadeia de ferramentas do Pinocchio forneceu um compilador de código C para circuitos aritméticos, que foi posteriormente transformado em um QAP. O protocolo exigia que o verificador gerasse as chaves, que são específicas do circuito. Ele usou emparelhamentos de curvas elípticas para verificar as equações. A assintótica para geração de provas e configuração de chaves foi linear no tamanho da computação, e o tempo de verificação foi linear no tamanho das entradas e saídas públicas.

Groth 16 (2016)

Groth apresentou um novo argumento de conhecimento com maior desempenho para problemas descritos por um R1CS. Ele tem o menor tamanho de prova (apenas três elementos de grupo) e verificação rápida envolvendo três emparelhamentos. Isso também envolve uma etapa de pré-processamento para obter a string de referência estruturada. A principal desvantagem é que ele exige uma configuração confiável diferente para cada programa que queremos provar, o que é inconveniente. Groth16 foi usado no ZCash.

Bulletproofs & IPA (2016)

Um dos pontos fracos do KZG PCS é que ele exige uma configuração confiável. Bootle et al. introduziram um sistema eficiente de argumento de conhecimento zero de aberturas de compromissos de Pedersen que satisfazem uma relação de produto interno. O argumento do produto interno tem um provador linear, com comunicação e interação logarítmicas, mas com verificação em tempo linear. Eles também desenvolveram um esquema de compromisso polinomial que não exige uma configuração confiável. Os PCS que usam essas ideias são usados por Halo 2 e Kimchi.

Sonic, Marlin e Plonk (2019)

O Sonic, o Plonk e o Marlin resolvem o problema da configuração confiável por programa que tínhamos no Groth16, introduzindo cadeias de referência estruturadas universais e atualizáveis. O Marlin fornece um sistema de prova baseado no R1CS e é o núcleo do Aleo.

Plonk introduziu um novo esquema de aritmetização (mais tarde chamado de Plonkish) e o uso da verificação do grande produto para as restrições de cópia. O Plonkish também permitiu a introdução de portões especializados para determinadas operações, os chamados portões personalizados. Vários projetos têm versões personalizadas do Plonk, incluindo Aztec, zkSync, Polygon ZKEVM, Mina's Kimchi, Plonky2, Halo 2 e Scroll, entre outros.

Pesquisas (2018/2020)

Gabizon e Williamson introduziram o plookup em 2020, usando a verificação do grande produto para provar que um valor está incluído em uma tabela de valores pré-computados. Embora os argumentos de pesquisa tenham sido apresentados anteriormente em Arya, a construção exigia a determinação das multiplicidades para as pesquisas, o que torna a construção menos eficiente. O artigo do PlonkUp mostrou como introduzir o argumento plookup no Plonk. O problema com esses argumentos de pesquisa é que eles forçavam o provador a pagar o preço de toda a tabela, independentemente do número de pesquisas. Isso implica um custo considerável para tabelas grandes, e muito esforço foi dedicado para reduzir o custo do provador apenas ao número de pesquisas que ele usa.
Haböck apresentou o LogUp, que usa a derivada logarítmica para transformar a verificação do grande produto em uma soma de recíprocos. O LogUp é crucial para o desempenho no Polygon ZKEVM, onde é necessário dividir a tabela inteira em vários módulos STARK. Esses módulos precisam ser vinculados corretamente, e as pesquisas entre tabelas impõem isso. A introdução do LogUp-GKR usa o protocolo GKR para aumentar o desempenho do LogUp. O Caulk foi o primeiro esquema com tempo do provador sublinear no tamanho da tabela, usando o tempo de pré-processamento O(NlogN) e o armazenamento O(N), em que N é o tamanho da tabela. Vários outros esquemas se seguiram, como Baloo, flookup, cq e caulk+. O Lasso apresenta vários aprimoramentos, evitando o comprometimento com a tabela se ela tiver uma determinada estrutura. Além disso, o provador do Lasso paga apenas pelas entradas da tabela acessadas pelas operações de pesquisa. O Jolt utiliza o Lasso para comprovar a execução de uma máquina virtual por meio de pesquisas.

Spartan (2019)

O Spartan fornece um IOP para circuitos descritos usando o R1CS, aproveitando as propriedades de polinômios multivariados e o protocolo sumcheck. Usando um esquema de compromisso polinomial adequado, ele resulta em um SNARK transparente com um provador de tempo linear.

HyperPlonk (2022)

O HyperPlonk baseia-se nas ideias do Plonk usando polinômios multivariados. Em vez de quocientes para verificar a aplicação das restrições, ele se baseia no protocolo sumcheck. Ele também suporta restrições de alto grau sem prejudicar o tempo de execução do provador. Como ele se baseia em polinômios multivariados, não há necessidade de realizar FFTs, e o tempo de execução do provador é linear no tamanho do circuito. O HyperPlonk apresenta um novo IOP de permutação adequado para campos menores e um protocolo de abertura de lote baseado em verificação de soma, que reduz o trabalho do provador, o tamanho da prova e o tempo do verificador.

Esquemas de dobragem (2008/2021)

A Nova apresenta a ideia de um esquema de dobragem, que é uma nova abordagem para obter uma computação incrementalmente verificável (IVC). O conceito de IVC remonta a Valiant, que mostrou como mesclar duas provas de comprimento k em uma única prova de comprimento k. A ideia é que podemos provar qualquer computação de longa duração provando recursivamente que a execução da etapa i para a etapa I+1+1 está correta e verificando uma prova que mostre que a transição da etapa i

-1-1para a etapa i estava correto. O Nova lida bem com cálculos uniformes; posteriormente, foi ampliado para lidar com diferentes tipos de circuitos com a introdução do Supernova. O Nova usa uma versão relaxada do R1CS e trabalha com curvas elípticas amigáveis. O trabalho com ciclos amigáveis de curvas (por exemplo, as curvas de Pasta) para obter a IVC também é usado no Pickles, o principal componente da Mina para obter um estado sucinto. No entanto, a ideia de dobrar é diferente da verificação recursiva do SNARK. A ideia do acumulador está mais profundamente ligada ao conceito de provas em lote. Halo introduziu a noção de acumulação como uma alternativa à composição de provas recursivas. O Protostar fornece um esquema de IVC não uniforme para o Plonk que suporta portas de alto grau e pesquisas de vetores.

Uso de funções hash resistentes a colisões

Na mesma época em que Pinocchio foi desenvolvido, havia algumas ideias para gerar circuitos/esquemas de aritmetização que pudessem provar a correção da execução de uma máquina virtual. Embora o desenvolvimento da aritmetização de uma máquina virtual pudesse ser mais complexo ou menos eficiente do que escrever circuitos dedicados para alguns programas, ele oferecia a vantagem de que qualquer programa, por mais complicado que fosse, poderia ser comprovado mostrando que foi executado corretamente na máquina virtual. As ideias do TinyRAM foram aprimoradas posteriormente com o design da vm Cairo e das máquinas virtuais subsequentes (como zk-evms ou zkvms de uso geral). O uso de funções de hash resistentes a colisões eliminou a necessidade de configurações confiáveis ou o uso de operações de curva elíptica, à custa de provas mais longas.

TinyRAM (2013)

Em SNARKs para C, eles desenvolveram um SNARK baseado em um PCP para provar a correção da execução de um programa em C, que é compilado para o TinyRAM, um computador com conjunto de instruções reduzido. O computador usava uma arquitetura Harvard com memória de acesso aleatório endereçável em nível de byte. Aproveitando o não determinismo, o tamanho do circuito é quasilinear no tamanho da computação, lidando com eficiência com loops arbitrários e dependentes de dados, fluxo de controle e acessos à memória.

STARKs (2018)

Os STARKs foram apresentados por Ben Sasson et al. em 2018. Eles alcançam O(log2n)(log2)

com provador e verificador rápidos, não requerem uma configuração confiável e são conjecturados como seguros pós-quânticos. Eles foram usados pela primeira vez pela Starkware/Starknet, juntamente com o Cairo vm. Entre suas principais introduções estão a representação intermediária algébrica (AIR) e o protocolo FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). Ele também é usado por outros projetos (Polygon Miden, Risc0, Winterfell, Neptune) ou recebeu adaptações de alguns componentes (Boojum do zkSync, Plonky2, Starky).

Ligero (2017)

Ligero apresenta um sistema de prova que consegue provas cujo tamanho é

O(√n), em que n é o tamanho do circuito. Ele organiza os coeficientes polinomiais em forma de matriz e usa códigos lineares.
O Brakedown se baseia no Ligero e introduz a ideia de esquemas de compromisso polinomial agnóstico de campo.

Alguns novos desenvolvimentos

O uso de diferentes sistemas de prova na produção mostrou os méritos de cada uma das abordagens e levou a novos desenvolvimentos. Por exemplo, a aritmetização plonkish oferece uma maneira simples de incluir portas personalizadas e argumentos de pesquisa; o FRI demonstrou ótimo desempenho como PCS, levando ao Plonky. Da mesma forma, o uso da verificação do grande produto no AIR (levando ao AIR aleatório com pré-processamento) melhorou seu desempenho e simplificou os argumentos de acesso à memória. Os compromissos baseados em funções de hash ganharam popularidade, com base na velocidade das funções de hash no hardware ou na introdução de novas funções de hash compatíveis com o SNARK.

Novos esquemas de compromisso polinomial (2023)

Com o advento de SNARKs eficientes baseados em polinômios multivariados, como o Spartan ou o HyperPlonk, houve um interesse crescente em novos esquemas de compromisso adequados a esse tipo de polinômios. A Binius, a Zeromorph e a Basefold propõem novas formas de se comprometer com polinômios multilineares. O Binius oferece a vantagem de ter zero de sobrecarga para representar tipos de dados (enquanto muitos sistemas de prova usam pelo menos elementos de campo de 32 bits para representar bits únicos) e funciona em campos binários. O compromisso adapta a frenagem, que foi projetada para ser independente do campo. O Basefold generaliza o FRI para códigos que não sejam Reed-Solomon, levando a um PCS independente de campo.

Sistemas de restrição personalizáveis (2023)

O CCS generaliza o R1CS e, ao mesmo tempo, captura a aritmetização do R1CS, do Plonkish e do AIR sem sobrecargas. O uso do CCS com o Spartan IOP produz o SuperSpartan, que suporta restrições de alto grau sem que o provador tenha que incorrer em custos criptográficos que aumentam com o grau da restrição. Em particular, o SuperSpartan produz um SNARK para AIR com um provador de tempo linear.

Conclusão

Esta postagem descreve os avanços dos SNARKs desde sua introdução em meados da década de 1980. Os avanços em ciência da computação, matemática e hardware, juntamente com a introdução do blockchain, levaram a SNARKs novos e mais eficientes, abrindo a porta para muitos aplicativos que poderiam transformar nossa sociedade. Pesquisadores e engenheiros propuseram melhorias e adaptações aos SNARKs de acordo com suas necessidades, concentrando-se no tamanho da prova, no uso da memória, na configuração transparente, na segurança pós-quântica, no tempo do provador e no tempo do verificador. Embora houvesse originalmente duas linhas principais (SNARKs vs. STARKs), a fronteira entre ambas começou a desaparecer, tentando combinar as vantagens dos diferentes sistemas de prova. Por exemplo, a combinação de diferentes esquemas de aritmetização com novos esquemas de compromisso polinomial. Podemos esperar que novos sistemas de prova continuem a surgir, com maior desempenho, e será difícil para alguns sistemas que exigem algum tempo de adaptação acompanhar esses desenvolvimentos, a menos que possamos usar facilmente essas ferramentas sem precisar alterar alguma infraestrutura central.

Isenção de responsabilidade：

1. Este artigo foi reimpresso de[lambdaclass], Todos os direitos autorais pertencem ao autor original[LambdaClass]. Se houver alguma objeção a essa reimpressão, entre em contato com a equipe do Gate Learn, que tratará do assunto imediatamente.
2. Isenção de responsabilidade: Os pontos de vista e opiniões expressos neste artigo são de responsabilidade exclusiva do autor e não constituem consultoria de investimento.
3. As traduções do artigo para outros idiomas são feitas pela equipe do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.