1. Introdução
ZK-SNARK é um sistema de prova criptográfica que permite a uma entidade provar que algo é verdadeiro sem revelar outras informações.
ZK-SNARKs são úteis em diversas aplicações e campos, como blockchain e computação verificável. Um aplicativo blockchain notável é usado em ZK-Rollups.
ZK-Rollups são blockchains de segunda camada construídos sobre outros blockchains (como Ethereum) que utilizam ZK-SNARKs (ou outros sistemas de prova criptográfica) para provar a validade das transições de estado. Ou seja, toda vez que uma nova atualização da rede é feita (um novo lote de transações é adicionado), um novo estado da rede é calculado e uma prova da validade desse estado é gerada. A questão é que apenas uma entidade é necessária para gerar esta prova, e qualquer pessoa pode então confiar na sua validade.
As propriedades desejadas fornecidas pelo ZK-Rollups são geralmente (i) escalabilidade e/ou (ii) proteção de privacidade. ZK-Rollups às vezes são chamados de Rollups de eficácia quando apenas escalabilidade é necessária.
Para calcular provas em ZK-Rollups projetados para estender o EVM do Ethereum, o ZK-EVM pode ser usado. Estritamente definido, ZK-EVM é um conjunto de programas criptográficos (circuitos) responsáveis por gerar provas de conhecimento zero (ZKP), embora às vezes coloquialmente também se refira ao ZK-Rollup universal compatível com EVM como um todo.
2.Definição ZK-SNARK
Um SNARK é uma prova concisa de que uma determinada afirmação é verdadeira. Formalmente, demonstra o conhecimento do rastreamento de execução de um algoritmo que produz uma solução correta para um determinado problema. Em vez disso, demonstra conhecimento de valores não públicos e não constantes que realizam o rastreamento. Esses valores como um todo são frequentemente chamados de testemunhas. Os elementos da testemunha, ou seja, as partes da entrada do algoritmo, constituem testemunhas independentes porque existem antes da execução do algoritmo e não são determinados por outros elementos do rastreamento de execução. O valor público não constante do rastreamento de execução, que especifica a instância do problema que o algoritmo resolve, é chamado de declaração pública.
ZK-SNARK significa Argumento de conhecimento sucinto e não interativo de conhecimento zero.
S - Simplicidade
Simplicidade – a prova é “curta” e o tempo de verificação é “rápido”:
Uma prova “curta” significa que o tamanho da prova é sublinear, em relação ao tamanho da testemunha.
O tempo de verificação “rápido” significa que o tempo de execução do verificador deve (i) ser sublinear no tamanho da testemunha e (ii) ser linear na reivindicação pública.
Mas, na verdade, queremos que seja não apenas "conciso", mas também "nível log polinomial".
Isto significa que o tamanho da prova e o tempo de verificação são quase independentes do tamanho da testemunha.
Prove que o tamanho de π não deve crescer mais rápido do que alguma constante vezes o quadrado do logaritmo do tamanho da testemunha w (para w suficientemente grande):
O tamanho da prova depende do protocolo ZK-SNARK específico. Para Plonky2 é O(log^2(|w|)), mas esse é o "pior" caso. Por exemplo, para PLONK e Groth16 clássicos, o tamanho da prova é O(1), que é uma constante.
O tempo de verificação t_v não deve ser maior do que algumas constantes vezes o quadrado do logaritmo da testemunha w, e linear no tamanho da declaração pública x (x e w são grandes o suficiente quando apenas um deles muda de tamanho).
N - Não interativo - A geração da prova ocorre sem receber nenhum dado do verificador.
ARK - Prova de Conhecimento - Semelhante às provas regulares, mas o som é válido apenas contra provadores limitados polinomialmente, enquanto nas provas o som é válido contra provadores computacionalmente ilimitados. Discutiremos o conceito de som na próxima seção.
ZK - Conhecimento Zero - Sem divulgação de testemunhas.
3. Propriedades dos ZK-SNARKs
ZK-SNARKs possuem três propriedades principais, conforme descrito abaixo:
Completude: Se o provador conhece a trajetória correta de execução do algoritmo, então o verificador deve acreditar que o provador possui esse conhecimento.
Solidez do conhecimento: a menos que o provador realmente conheça a trajetória de execução correta, o provador não pode convencer o verificador de que a conhece, mas há uma probabilidade muito pequena.
Conhecimento zero: O verificador não sabe nada sobre a trajetória de execução, exceto que ela está correta.
4.Sistema de prova PLONKish ZK-SNARK
4.1 Introdução aos PLONKish ZK-SNARKs e suas funções
Para ser aplicado a um determinado algoritmo, o sistema de prova ZK-SNARK precisa conhecer o sistema de equações no corpo finito. Essas equações descrevem a relação entre os valores na tabela de trajetória de execução do algoritmo. estrutura de dados que armazena a trajetória de execução) para garantir que o cálculo seja Integridade. A linguagem usada para expressar esse sistema de equações (também chamado de sistema de restrições) é chamada de aritmética.
O sistema de prova PLONKish ZK-SNARK usa aritmética com maior poder expressivo do que os sistemas de prova mais antigos. A primeira nos permite usar equações de sistema de restrição de forma polinomial arbitrária sobre as variáveis de restrição, enquanto para sistemas de prova mais antigos (ou seja, sistemas baseados em R1CS) essas equações tinham a forma de polinômios lineares e quadráticos. Esse recurso faz com que o sistema de prova PLONKish ZK-SNARK tenha um impacto positivo na eficiência computacional do provador e facilita a aplicação a vários algoritmos. Portanto, muitos sistemas de prova PLONKish ZK-SNARK surgiram nos últimos anos, como o clássico PLONK, Halo2, Kimchi, Plonky2, HyperPlonk, etc.
No Taiko, usamos uma variante do sistema de prova Halo2 baseado no esquema de comprometimento polinomial KZG.
O sistema de prova PLONKish ZK-SNARK consiste em três componentes:
4.2 Plano de compromisso
O esquema de promessa permite que um committer publique um valor, chamado promessa, que vincula o committer a uma mensagem sem revelar a mensagem em si. O committer pode então abrir o compromisso e expor a mensagem comprometida, ou alguma parte dela, ao verificador, que pode verificar se a informação exposta é consistente com o compromisso.
Diferentes autores descrevem um número diferente de algoritmos que constituem um esquema de compromisso. No entanto, devemos mencionar pelo menos quatro desses algoritmos:
Setup: recebe alguns parâmetros iniciais como entrada e gera parâmetros de configuração. As configurações especificam (i) com o que nos comprometemos (por exemplo, para o esquema de compromisso polinomial unário, especificamos o domínio do coeficiente e o grau máximo do polinômio com o qual nos comprometemos) e (ii) o nível de segurança em bits. Podemos simplesmente definir o nível de segurança da seguinte forma: Se leva tempo O(2^n) para quebrar um sistema de criptografia, então o sistema de criptografia tem um nível de segurança de n bits.
Promessa: Uma promessa que gera mensagens com base em parâmetros definidos.
Abertura parcial: Gera uma prova de abertura parcial específica para uma parte selecionada da mensagem (por exemplo, o valor de um polinômio unário confirmado para algum parâmetro), bem como define os parâmetros.
Validação: Use um atestado parcialmente aberto e defina parâmetros para verificar se as informações expostas pelo provador são a parte especificada da mensagem correspondente ao compromisso especificado.
*Para alguns esquemas de confirmação, os algoritmos "setup" e "open" podem não existir (por exemplo, ao usar uma função hash para confirmar valores grandes).
O plano de compromisso deve ter as seguintes características:
Vinculação: Uma vez que o provador se compromete com uma mensagem específica, ele ficará vinculado à mensagem com a qual se comprometeu;
Esconder: Uma promessa de não revelar qualquer informação sobre a mensagem. A ocultação pode ser perfeita, ou seja, uma prova parcialmente aberta não revela nenhuma informação sobre a parte não questionada da mensagem (por exemplo, compromisso KZG), ou não perfeita, ou seja, uma prova parcialmente aberta revela alguma parte das informações acima mencionadas (por exemplo, baseada em FRI comprometimento polinomial).
Os esquemas de compromisso podem ser divididos em vários tipos com base no objeto alvo: compromisso de conjunto de elemento único;
Esquemas de compromisso polinomial são o único tipo usado diretamente no sistema de prova PLONKish ZK-SNARK. Para os sistemas de prova acima (como PLONK clássico, Halo2, Kimchi, Plonky2, etc.), o esquema de compromisso polinomial univariado é muito importante. No entanto, existem agora alguns novos métodos PLONKish ZK-SNARK baseados em esquemas de compromisso polinomial multilinear (por exemplo, HyperPlonk).
4.3 Prova Oracle Interativa
Uma prova de oráculo interativo é uma prova interativa em que o verificador tem "acesso ao oráculo" para obter as mensagens do provador, pode consultá-las de forma probabilística e não precisa ler todas as mensagens do provador.
4.4 Heurística Fiat-Shamir
A heurística Fiat-Shamir fornece uma maneira de transformar argumentos interativos (moeda pública) em argumentos não interativos. Intuitivamente, a ideia é substituir o desafio aleatório do validador pelo hash da mensagem anterior, mas os detalhes geralmente não são especificados.
*Public Coin Protocol é um protocolo onde os validadores enviam apenas elementos aleatórios.
4.5 Princípio de funcionamento do sistema de prova ZK-SNARK estilo PLONK
No sistema de prova ZK-SNARK, um método de prova Oracle interativo modificado é usado para provar o conhecimento da testemunha, que usa compromissos polinomiais para fornecer acesso Oracle à mensagem do provador e torná-la livre de interação por meio da heurística Fiat-Shamir. Nesta seção, explicaremos o construtor fornecido em detalhes.
Lembre-se de que a aplicação do sistema de prova ZK-SNARK a um algoritmo requer a construção de um sistema de restrições correspondente. Para poder construí-lo, definimos a estrutura da tabela de rastreamento de execução do algoritmo e os valores constantes nela. Usamos o termo "circuito" para nos referirmos à estrutura complexa de uma tabela de rastreamento de execução preenchida apenas com constantes e o sistema de restrições correspondente. Para gerar uma prova ZK-SNARK para uma instância de execução de um algoritmo, precisamos sintetizar uma instância de circuito para ele que seja uma instância correspondente do circuito do algoritmo e da tabela de rastreamento de execução (ou seja, uma tabela que especifica constantes, testemunhas, e valores de declaração pública) combinação.
Consideremos a estrutura da tabela de rastreamento usada por um sistema de prova ZK-SNARK estilo PLONK. Todas as colunas dessa tabela pertencem a um dos três tipos, que nomeamos de acordo com a terminologia usada no Halo2 e descrevemos a seguir:
Colunas fixas - suas células contêm constantes da tabela de rastreamento de execução;
Coluna de instância - usada para armazenar valores de declaração pública;
Coluna de sugestões - onde todos os dados das testemunhas são armazenados (incluindo valores de testemunhas independentes e resultados secretos calculados).
Para resumir, notamos o seguinte:
Tabela de rastreamento de execução (tipo PLONKish) = colunas fixas + colunas de instância + colunas de sugestão = tabela de rastreamento de execução contendo apenas constantes + instância de circuito de restrição = circuito + testemunhas em sua tabela + declarações públicas em sua tabela; declaração pública, valor de testemunha independente) → Instância do circuito Aplicar o sistema de prova ZK-SNARK a um determinado algoritmo = descrever o circuito + definir o processo de síntese.
Por que o termo “circuito” é amplamente utilizado neste contexto? Inicialmente, quando apenas sistemas de prova ZK-SNARK baseados em R1CS estavam disponíveis, era conveniente representar o sistema de restrições na forma de um circuito aritmético, cuja saída deveria ser zero. Acreditamos que no contexto dos SNARKs PLONKish o termo “circuito” é usado por razões históricas. De qualquer forma, vamos considerar brevemente o circuito aritmético usado para versões mais antigas do ZK-SNARK.
O circuito aritmético para SNARKs baseados em R1CS define um polinômio de n variáveis sobre um corpo finito e possui um esquema de avaliação. Inicialmente, é representado como um gráfico acíclico direcionado (DAG):
inclui:
Entrada pública x, usada para especificar o valor da declaração pública;
Entrada secreta w, usada para especificar o valor da testemunha independente;
Portas aritméticas usadas para especificar adição e multiplicação em campos finitos.
Vejamos um exemplo de circuito aritmético sobre o corpo dos números racionais.
Começamos de baixo e trabalhamos com as portas mais baixas do diagrama, ou seja, (2 x 4 = 8) e (4 + 11 = 15), salvando esses valores como valores intermediários;
Em seguida, subimos uma linha (para a segunda linha) e calculamos a soma dos dois valores intermediários (que obtivemos na etapa anterior), que é (8 + 15 = 23);
Como temos apenas três portões e passamos por todos eles, 23 é o nosso resultado final.
Depois que o sistema de prova PLONKish ZK-SNARK sintetiza a instância do circuito, as colunas de cada tabela de rastreamento de execução da instância são codificadas como polinômios sobre campos finitos da seguinte maneira. Suponha que C_j(x) seja um polinômio que descreve a coluna j e ω seja uma raiz primitiva 2^k-ésimo, onde k é escolhido de forma que 2^k seja ligeiramente maior que a altura inicial da instância da tabela. A instância da tabela é preenchida com linhas aleatórias (apenas com células diferentes de zero nas colunas sugeridas) para conter 2 ^ k linhas e C_j (ω ^ i) é definido como o valor da i-ésima linha da j-ésima coluna da instância da tabela fornecida. A função do preenchimento para propriedades de conhecimento zero será explicada posteriormente.
A afirmação "ω é uma raiz primitiva 2 ^ k-ésimo" significa que ω ^ (2 ^ k) = 1, e temos ω ^ t ≠ 1 para qualquer número inteiro positivo t menor que 2 ^ k.
O sistema de restrições é convertido na forma de equação polinomial, substituindo as variáveis nele contidas pelos polinômios correspondentes obtidos dos polinômios da coluna, substituindo "x vezes ω elevado a alguma potência" no lugar de x.
Por exemplo, consideremos a equação do sistema de restrições s(i) * (a(i) * b(i) - c(i+1)) = 0. Isso significa que se s(i) for diferente de zero, então a(i) * b(i) deve ser igual a c(i+1). Aqui, a, b e c são as colunas sugeridas, s é a coluna fixa e i é o número da linha atual.
Esta restrição pode ser aplicada a todas as 2^k linhas da seguinte maneira. Sejam S(x), A(x), B(x) e C(x) polinômios nas colunas a, b, c e s, respectivamente. Portanto, esperamos:
Isso significa que todos os elementos deste conjunto devem ser raízes de S(x) * (A(x) * B(x) - C(x * ω)). Portanto, este polinômio deve ser divisível por:
Porque ω é uma raiz primitiva de ordem 2^k.
Z(x) = x^(2^k) - 1 é chamado de "polinômio desaparecido" porque é 0 para todos os x que são elementos do grupo multiplicativo cíclico gerado por ω. Portanto, S(x) * (A(x) * B(x) - C(x * ω)) mod Z(x) = 0 significa que as restrições acima são válidas para todas as 2^k linhas.
Suponha que P_0(x), P_1(x), ... , P_m(x) sejam restrições aplicadas a todas as 2^k linhas e sejam consistentes com o polinômio S(x) * (A(x) * B(x) considerado acima) - C(x * ω)) tem uma forma semelhante. Se α for escolhido aleatoriamente pelo verificador do corpo finito, então
Isso significa que com probabilidade extremamente alta todas essas restrições são satisfeitas para todas as 2 ^ k linhas. Esta equação significa que podemos encontrar um polinômio quociente T(x) tal que
Portanto, para que o verificador acredite que o provador conhece o conteúdo da tabela de rastreamento de execução que satisfaz todas as m restrições com uma probabilidade muito alta, basta provar que para um α selecionado aleatoriamente, o provador tem as ocorrências P_0 (x), P_1(x ),..., os polinômios de coluna sugeridos e os polinômios quocientes T(x) em P_m(x) satisfazem esta equação polinomial. O verificador pode fazer isso pedindo ao provador que encontre o valor de um determinado polinômio em um ponto aleatório escolhido pelo verificador dentre os pontos não-raiz ζ de Z(x), e avalie ambos os lados dessa equação naquele ponto. ζ. Acredito que o provador provavelmente conhece esses polinômios. Este método pode ser provado pelo lema de Schwartz-Zippel.
Para tornar a geração de provas não interativa, todos os valores aleatórios gerados pelo verificador na versão interativa devem ser obtidos utilizando a heurística Fiat-Shamir.
Para vincular o provador ao seu polinômio de proposta e ao polinômio quociente T(x), um esquema de compromisso polinomial é usado. O provador faz compromissos sobre esses polinômios, abre esses compromissos em ζ (ou em ζ * ω^q se alguma restrição afetar as linhas i e i + q) e cria uma prova que inclui (I) esses compromissos, (II) O valor do polinômio em ζ (ou sobre ζ * ω^q se necessário) e (III) a prova aberta correspondente. Na verdade, para tornar a prova mais curta, use abertura múltipla, ou seja, gere uma pequena prova para os valores de todos os pontos polinomiais. Portanto, a prova é concisa.
Para satisfazer a propriedade de conhecimento zero, as linhas selecionadas aleatoriamente pelo provador são anexadas à instância da tabela de rastreamento de execução, perfazendo sua altura de 2 ^ k linhas. Essas linhas possuem apenas células diferentes de zero na coluna de sugestões porque apenas a coluna de sugestões contém os dados que queremos ocultar. Faça isso antes de construir os polinômios da coluna proposta para que o número de pares de "valores de parâmetro" revelados durante o período de abertura do compromisso seja menor que o número de pares adicionados aleatoriamente para cada polinômio. Portanto, para cada polinômio da coluna da proposta, a quantidade de informações necessárias para recuperá-la após a abertura do compromisso é maior que a quantidade de informações testemunhas. Esta situação resulta em conhecimento zero.
Durante a fase de pré-processamento, todas as instâncias do circuito em execução realizam alguns dos mesmos cálculos, incluindo a configuração e o cálculo de polinômios de coluna fixa e seus compromissos para o esquema de compromisso polinomial. A parte dos dados produzida por esses cálculos é usada pelo verificador e costuma ser chamada de chave de verificação. Da mesma forma, o conceito de chave de prova pode ser definido. O esquema de compromisso polinomial subjacente determina se as configurações de confiança são feitas durante a fase de pré-processamento.