O nosso ponto de vista altamente subjetivo sobre a história das provas de conhecimento zero

Os argumentos de conhecimento sucintos, não interactivos e de conhecimento zero (zk-SNARKs) são poderosos primitivos criptográficos que permitem a uma parte, o provador, convencer outra parte, o verificador, de que uma dada afirmação é verdadeira sem revelar mais nada para além da validade da afirmação. Ganharam uma atenção generalizada devido às suas aplicações na computação privada verificável, fornecendo provas da correção da execução de programas de computador e ajudando a escalar cadeias de blocos. Pensamos que os SNARKs terão um impacto significativo na formação do nosso mundo, como descrevemos no nosso post. O SNARKs funciona como um guarda-chuva para diferentes tipos de sistemas de prova, utilizando diferentes esquemas de compromisso polinomial (PCS), esquemas de aritmetização, provas de oráculo interactivas (IOP) ou provas verificáveis probabilisticamente (PCP). No entanto, as ideias e os conceitos de base remontam a meados da década de 1980. O desenvolvimento acelerou significativamente após a introdução do Bitcoin e do Ethereum, que provaram ser um caso de utilização interessante e poderoso, uma vez que pode escalá-los utilizando provas de conhecimento zero (geralmente designadas provas de validade para este caso de utilização específico). Os SNARKs são uma ferramenta essencial para a escalabilidade da cadeia de blocos. Como descreve Ben-Sasson, nos últimos anos assistiu-se a uma explosão cambriana de provas criptográficas. Cada sistema de prova oferece vantagens e desvantagens e foi concebido tendo em conta determinados compromissos. Os avanços no hardware, os melhores algoritmos, os novos argumentos e os gadgets resultam num melhor desempenho e no nascimento de novos sistemas. Muitos deles são utilizados na produção, e continuamos a alargar os limites. Teremos um sistema de prova geral para todas as aplicações ou vários sistemas adaptados a diferentes necessidades? Pensamos que é improvável que um sistema de prova seja o rei de todos, porque:

1. A diversidade das aplicações.
2. Os tipos de restrições que temos (relativamente à memória, tempos de verificação, tempos de prova).
3. A necessidade de robustez (se um sistema de prova se avariar, ainda temos outros).

Mesmo que os sistemas de prova mudem muito, todos eles oferecem uma propriedade importante: 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 o Ethereum. Dar uma visão geral das diferentes características dos SNARKs:

• Pressupostos criptográficos: funções hash resistentes a colisões, problema do logaritmo discreto em curvas elípticas, conhecimento do expoente.
• Configuração transparente ou de confiança.
• 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.

Este post vai analisar as origens dos SNARKs, alguns blocos de construção fundamentais e a ascensão (e queda) de diferentes sistemas de prova. O post não pretende ser uma análise exaustiva dos sistemas de prova. Em vez disso, concentramo-nos naqueles que tiveram um impacto sobre nós. Naturalmente, estes desenvolvimentos só foram possíveis graças ao grande trabalho e às ideias dos pioneiros neste domínio.

Fundamentos

Como referimos, as provas de conhecimento zero não são novas. As definições, os fundamentos, os teoremas importantes e até os protocolos importantes foram estabelecidos a partir de meados da década de 1980. Algumas das ideias-chave e protocolos que utilizamos para construir SNARKs modernos foram propostos nos anos 90 (o protocolo sumcheck) ou mesmo antes do advento da Bitcoin (GKR em 2007). Os principais problemas com a sua adoção estavam relacionados com a falta de um caso de utilização poderoso (a Internet não estava tão desenvolvida na década de 1990) e com a quantidade de potência computacional necessária.

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

O domínio 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, pode ver o seguinte vídeo. O documento 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 elementos mais importantes para a construção de provas interactivas sucintas. Ajuda-nos a reduzir uma reivindicação sobre a soma das avaliações de um polinómio multivariado a uma única avaliação num ponto escolhido aleatoriamente.

Goldwasser-Kalai-Rothblum (GKR) (2007)

O protocolo GKR é um protocolo interativo que tem um verificador que funciona de forma linear no número de portas de um circuito, enquanto o verificador funciona de forma sublinear no tamanho do circuito. No protocolo, o provador e o verificador chegam a acordo sobre um circuito aritmético de "fan-in-two" sobre um campo finito de profundidade d, correspondendo a camada d à camada de entrada e a camada 0 à camada de saída. O protocolo começa com uma reivindicação relativa à saída do circuito, que se reduz a uma reivindicação sobre os valores da camada anterior. Usando a recursão, podemos transformar isto numa afirmação sobre as entradas do circuito, que pode ser verificada facilmente. Estas reduções são obtidas através do protocolo sumcheck.

Esquema de compromisso polinomial KZG (2010)

Kate, Zaverucha e Goldberg introduziram em 2010 um esquema de compromisso para polinómios utilizando um grupo de emparelhamento bilinear. O compromisso consiste num único elemento de grupo, e o autor pode abrir o compromisso de forma eficiente para qualquer avaliação correcta do polinómio. Para além disso, graças às técnicas de batching, a abertura pode ser feita para várias avaliações. Os compromissos KZG forneceram um dos blocos de construção básicos para vários SNARKs eficientes, tais como Pinocchio, Groth16 e Plonk. Está também no centro do EIP-4844. Para ter uma ideia das técnicas de batching, pode ver o nosso post sobre a ponte Mina-Ethereum.

SNARKs práticos utilizando curvas elípticas

As primeiras construções práticas de SNARKs surgiram em 2013. Estas exigiam uma etapa de pré-processamento para gerar as chaves de prova e de verificação e eram específicas do programa/circuito. Estas chaves podem ser bastante grandes e dependem de parâmetros secretos que devem permanecer desconhecidos das partes; caso contrário, poderiam forjar provas. A transformação do código em algo que pudesse ser provado exigia a compilação do código num sistema de restrições polinomiais. Inicialmente, isto tinha de ser feito manualmente, o que consome muito tempo e é propenso a erros. Os avanços neste domínio tentaram eliminar alguns dos principais problemas:

1. Tenha provadores mais eficientes.
2. Reduza a quantidade de pré-processamento.
3. Ter configurações universais em vez de específicas para cada circuito.
4. Evite ter configurações de confiança.
5. Desenvolvimento de formas de descrever circuitos utilizando uma linguagem de alto nível, em vez de escrever manualmente as restrições polinomiais.

Pinóquio (2013)

Pinóquio é 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 fornece um compilador de código C para circuitos aritméticos, que foi posteriormente transformado num QAP. O protocolo exigia que o verificador gerasse as chaves, que são específicas do circuito. Utilizou emparelhamentos de curvas elípticas para verificar as equações. As assíntotas para a geração de provas e configuração de chaves foram lineares 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 introduziu um novo argumento de conhecimento com maior desempenho para problemas descritos por um R1CS. Tem o tamanho de prova mais pequeno (apenas três elementos de grupo) e uma verificação rápida que envolve três emparelhamentos. Envolve também uma etapa de pré-processamento para obter a cadeia de referência estruturada. A principal desvantagem é que requer uma configuração de confiança diferente para cada programa que queremos provar, o que é inconveniente. Groth16 foi utilizado no ZCash.

Bulletproofs & IPA (2016)

Um dos pontos fracos do KZG PCS é o facto de necessitar de uma configuração de confiança. Bootle et al. introduziram um sistema eficiente de argumentação 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. Desenvolveram também um esquema de compromisso polinomial que não requer uma configuração de confiança. Os PCS que utilizam estas ideias são utilizados por Halo 2 e Kimchi.

Sonic, Marlin e Plonk (2019)

O Sonic, o Plonk e o Marlin resolvem o problema da configuração de confiança por programa que tínhamos no Groth16, introduzindo cadeias de referência estruturadas universais e actualizáveis. O Marlin fornece um sistema de prova baseado no R1CS e está no centro do Aleo.

Plonk introduziu um novo esquema de aritmetização (mais tarde designado por Plonkish) e a utilização da verificação do grande produto para as restrições de cópia. O Plonkish também permitiu a introdução de portas especializadas para determinadas operações, as chamadas portas personalizadas. Vários projectos 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, utilizando a verificação do grande produto para provar que um valor está incluído numa 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 documento PlonkUp mostrou como introduzir o argumento plookup no Plonk. O problema com estes argumentos de pesquisa é que obrigavam o provador a pagar o preço de toda a tabela, independentemente do seu número de pesquisas. Este facto implica um custo considerável para tabelas de grande dimensão, tendo sido dedicado um grande esforço para reduzir o custo do provador apenas ao número de pesquisas que utiliza.
Haböck introduziu o LogUp, que utiliza a derivada logarítmica para transformar a verificação do grande produto numa 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. Estes módulos têm de estar corretamente ligados e as pesquisas em tabelas cruzadas garantem-no. A introdução do LogUp-GKR utiliza o protocolo GKR para aumentar o desempenho do LogUp. Caulk foi o primeiro esquema com tempo de provador sublinear no tamanho da tabela, usando tempo de pré-processamento O(NlogN) e armazenamento O(N), onde N é o tamanho da tabela. Seguiram-se vários outros esquemas, como o Baloo, o flookup, o cq e o caulk+. O Lasso apresenta várias melhorias, evitando que se comprometa com a tabela se esta tiver uma determinada estrutura. Além disso, o provador Lasso só paga pelas entradas da tabela acedidas pelas operações de pesquisa. O Jolt utiliza o Lasso para provar a execução de uma máquina virtual através de pesquisas.

Spartan (2019)

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

HyperPlonk (2022)

O HyperPlonk baseia-se nas ideias do Plonk utilizando polinómios multivariados. Em vez de quocientes para verificar a aplicação das restrições, baseia-se no protocolo sumcheck. Também suporta restrições de grau elevado sem prejudicar o tempo de execução do provador. Uma vez que se baseia em polinómios multivariados, não há necessidade de efetuar FFTs e o tempo de execução do provador é linear no tamanho do circuito. O HyperPlonk introduz um novo IOP de permutação adequado para campos mais pequenos e um protocolo de abertura de lotes baseado na verificação da soma, que reduz o trabalho do provador, o tamanho da prova e o tempo do verificador.

Regimes de dobragem (2008/2021)

A Nova introduz 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 fundir duas provas de comprimento k numa única prova de comprimento k. A ideia é que podemos provar qualquer computação de longa duração provando recursivamente que a execução do passo i para o passo I+1+1 está correcta e verificando uma prova que mostra que a transição do passo i

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

Utilizar funções hash resistentes a colisões

Na mesma altura em que Pinóquio foi desenvolvido, surgiram 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, oferecia a vantagem de qualquer programa, por mais complicado que fosse, poder ser provado mostrando que era executado corretamente na máquina virtual. As ideias da TinyRAM foram mais tarde melhoradas com o design da vm Cairo, e máquinas virtuais subsequentes (tais como zk-evms ou zkvms de uso geral). A utilização de funções hash resistentes a colisões eliminou a necessidade de configurações de confiança ou a utilização de operações de curva elíptica, à custa de provas mais longas.

TinyRAM (2013)

Em SNARKs para C, desenvolveram um SNARK baseado num PCP para provar a correção da execução de um programa C, que é compilado para o TinyRAM, um computador de conjunto de instruções reduzido. O computador utilizava uma arquitetura Harvard com memória de acesso aleatório endereçável ao nível dos bytes. Tirando partido do não determinismo, o tamanho do circuito é quase linear em relação ao tamanho da computação, tratando eficazmente loops arbitrários e dependentes de dados, fluxo de controlo e acessos à memória.

STARKs (2018)

Os STARK foram introduzidos por Ben Sasson et al. em 2018. Alcançam O(log2n)(log2)

com provador e verificador rápidos, não requerem uma configuração de confiança e são conjecturados como sendo seguros pós-quânticos. Foram utilizadas pela primeira vez pela Starkware/Starknet, juntamente com a vm Cairo. Entre as suas principais introduções contam-se a representação algébrica intermédia (AIR) e o protocolo FRI (Fast Reed-Solomon Interactive Oracle Proof of Proximity). É também utilizado por outros projectos (Polygon Miden, Risc0, Winterfell, Neptune) ou sofreu adaptações de alguns componentes (Boojum da zkSync, Plonky2, Starky).

Ligero (2017)

Ligero apresenta um sistema de prova que permite obter provas cujo tamanho é

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

Alguns novos desenvolvimentos

A utilização de diferentes sistemas de prova na produção mostrou os méritos de cada uma das abordagens e conduziu a novos desenvolvimentos. Por exemplo, a aritmetização plonkish oferece uma forma simples de incluir portas personalizadas e argumentos de pesquisa; o FRI demonstrou um ótimo desempenho como PCS, levando ao Plonky. Do mesmo modo, a utilização da verificação do grande produto na AIR (que conduziu a uma AIR aleatória com pré-processamento) melhorou o 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 em hardware ou na introdução de novas funções de hash compatíveis com o SNARK.

Novos regimes de compromisso polinomiais (2023)

Com o advento de SNARKs eficientes baseados em polinómios multivariados, como o Spartan ou o HyperPlonk, tem havido um interesse crescente em novos esquemas de compromisso adequados a este 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 não ter qualquer sobrecarga para representar tipos de dados (enquanto muitos sistemas de prova utilizam pelo menos elementos de campo de 32 bits para representar bits únicos) e funciona com campos binários. O compromisso adapta a travagem, que foi concebida para ser independente do terreno. A Basefold generaliza a FRI a outros códigos para além do Reed-Solomon, conduzindo a um PCS independente do campo.

Sistemas de restrições personalizáveis (2023)

O CCS generaliza o R1CS, capturando o R1CS, o Plonkish e a aritmetização do AIR sem sobrecargas. Utilizando o CCS com o Spartan IOP, obtém-se o SuperSpartan, que suporta restrições de grau elevado sem que o provador tenha de 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

Este post descreve os avanços dos SNARKs desde a sua introdução em meados da década de 1980. Os avanços na ciência da computação, matemática e hardware, juntamente com a introdução da cadeia de blocos, levaram a SNARKs novos e mais eficientes, abrindo a porta a muitas aplicações que poderiam transformar a nossa sociedade. Os investigadores e engenheiros propuseram melhorias e adaptações aos SNARKs de acordo com as suas necessidades, centrando-se no tamanho da prova, na utilização da memória, na configuração transparente, na segurança pós-quântica, no tempo do provador e no tempo do verificador. Embora existissem 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, combinando diferentes esquemas de aritmetização com novos esquemas de compromisso polinomial. É de esperar que continuem a surgir novos sistemas de prova, com maior desempenho, e será difícil para alguns sistemas que requerem algum tempo de adaptação acompanhar estes desenvolvimentos, a menos que possamos utilizar facilmente estas ferramentas sem ter de alterar alguma infraestrutura de base.

Declaração de exoneração de responsabilidade：

1. Este artigo foi reimpresso de[lambdaclass], Todos os direitos autorais pertencem ao autor original[LambdaClass]. Se houver objecções a esta reimpressão, contacte a equipa da Gate Learn, que tratará prontamente do assunto.
2. Declaração de exoneração de responsabilidade: Os pontos de vista e opiniões expressos neste artigo são da exclusiva responsabilidade do autor e não constituem um conselho de investimento.
3. As traduções do artigo para outras línguas são efectuadas pela equipa Gate Learn. A menos que seja mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.