O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs

Autor: 0xAlpha Cofundador @DeriProtocol; Compilador: DODO Research

Introdução

zk-SNARKs, ou “argumentos de conhecimento concisos e não interativos de conhecimento zero”, permitem que um verificador confirme que um provador tem certos conhecimentos específicos, conhecidos como testemunhas, que satisfazem relações específicas sem revelar nada sobre a própria testemunha.

A geração de zk-SNARKs para um problema específico consiste nas seguintes quatro fases:

• Converter um problema (ou função) em um circuito de porta aritmética.
• Este circuito é então traduzido em uma fórmula matricial.
• Esta fórmula matricial é posteriormente convertida num polinômio, que deve ser divisível por um polinômio mínimo específico.
• Finalmente, esta divisibilidade é representada em pontos de curva elíptica em campos finitos, onde ocorre a prova.

Os três primeiros passos simplesmente convertem a representação da declaração original. A etapa final usa criptografia homomórfica para projetar a instrução da etapa 3 no espaço criptográfico, permitindo que o provador verifique a instrução espelhada nele. Dado que esta projeção faz uso de criptografia assimétrica, não é viável rastrear a afirmação original da terceira etapa, garantindo exposição de conhecimento zero.

A formação matemática necessária para ler este artigo é equivalente ao nível de calouro de álgebra para os cursos STEM. O único conceito que pode ser desafiador é provavelmente a criptografia de curva elíptica. Para aqueles que não estão familiarizados com isso, pode ser pensado como uma função exponencial com uma cardinalidade especial, tendo em mente que seu inverso permanece sem solução.

Este artigo seguirá as seguintes regras de notação:

• Matriz: letras maiúsculas a negrito, por exemplo, A; Escreva explicitamente no formulário
• Vetor: letras minúsculas com setas, escritas de forma explícita [ ] ; Por padrão, todos os vetores são vetores colunares
• Escalar: Representação de letra regular

Vamos usar esta pergunta como exemplo:

f(x)=x^3+x^2+5 (1)

Digamos que Alice queira provar que conhece um. Vamos percorrer todo o procedimento que Alice precisa fazer para gerar zk-SNARKs para suas provas.

Esta pergunta pode parecer muito simples porque não envolve fluxo de controle (por exemplo, se-então-outro). No entanto, não é difícil converter uma função com um fluxo de controle em uma expressão aritmética. Por exemplo, vamos considerar a seguinte pergunta (ou “função” em uma linguagem de programação):

f(x, z):

if(z==1):

retornar x*x*x+x*x+5

senão:

retornar x*x+5

É fácil reescrever este problema na seguinte expressão aritmética (assumindo que z pertence a (0,1)), que não é muito mais complicada do que a equação (1).

f(x,z)=(z-1)(x^2+5)+z(x^3+x^2+5)

Neste artigo, continuaremos a usar a equação (1) como base para a discussão.

Passo 1: Circuito de porta aritmética

A equação (1) pode ser dividida nas seguintes operações aritméticas básicas:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-122a4a0e88-dd1a6f-cd5cc0.webp)

Isto corresponde ao seguinte circuito de porta aritmética:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-9001e3d244-dd1a6f-cd5cc0.webp)

Também nos referimos à equação (2) como um conjunto de 4 “restrições de primeira ordem”, cada uma das quais descreve a relação de uma porta aritmética em um circuito. Em geral, um conjunto de n restrições de primeira ordem pode ser generalizado como um procedimento aritmético quadrático (QAP), que será explicado a seguir.

Passo 2: Matriz

Primeiro, vamos definir um vetor “testemunha” da seguinte forma:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-1157f4c74a-dd1a6f-cd5cc0.webp)

onde y, s1, s2, s3 são os mesmos definidos na equação (2).

Em geral, para um problema com m entradas e n portas aritméticas (ou seja, n-1 etapas intermediárias e saída final), este vetor testemunha será (m+n+1) dimensional. Em um problema prático, o número n pode ser muito grande. Por exemplo, para uma função hash, n é geralmente alguns milhares.

Em seguida, vamos construir três matrizes n*(m+n+*1) A,B,C para que possamos reescrever a equação (2) da seguinte maneira:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a9e2164b2f-dd1a6f-cd5cc0.webp)

A equação (3) é apenas mais uma representação da equação (2): cada grupo (ai, bi, ci) corresponde a uma porta no circuito. Basta expandirmos inequivocamente a fórmula matricial para ver isto:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-630e507588-dd1a6f-cd5cc0.webp)

Assim, LHS=RHS é exatamente o mesmo que a equação (2), e cada linha da equação matricial corresponde a uma restrição de primeira ordem (ou seja, uma porta aritmética no circuito).

Nós pulamos as etapas de construção (A, B, C), que são relativamente simples. Só precisamos convertê-los em forma matricial de acordo com as restrições de primeiro nível correspondentes, de modo a determinar o conteúdo de cada linha de (A, B, C), OU SEJA, (AI, BI, CI). Tomemos a primeira linha como exemplo: é fácil ver que, para que a restrição de primeira ordem x seja multiplicada por x igual a s1 se mantenha, precisamos multiplicar [0,1,0,0,0,0], [0,1,0,0,0] e [0,0,0,1,0,0] com o vetor s.

Assim, conseguimos converter o circuito de porta aritmética em uma fórmula matricial, ou seja, equação (3). Ao mesmo tempo, também mudamos o objeto que precisa ser provado para ser dominado de um vetor testemunha.

Passo 3: Polinômios

Agora, vamos construir uma matriz PA n*(*n+m+*1) que define um conjunto de polinômios sobre z:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-94169f2b1d-dd1a6f-cd5cc0.webp)

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-2c37ea96a6-dd1a6f-cd5cc0.webp)

Estes são quatro conjuntos de equações lineares para seis variáveis que podem ser resolvidas por métodos tradicionais. No entanto, uma maneira mais eficiente de resolver AF neste caso é a interpolação lagrangiana, que se aproveita da especificidade do problema. Aqui pulamos o processo de resolução para PA, que é um pouco tedioso, mas direto.

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-fcac15b335-dd1a6f-cd5cc0.webp)

Assim:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-a7d3309d02-dd1a6f-cd5cc0.webp)

Passo 4: Pontos de curva de elipse

Reescreva a equação (4) para:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-f974fc7c93-dd1a6f-cd5cc0.webp)

onde i(z)=1 é apenas um polinômio trivial de ordem zero para z, que é usado para unificar a equação - todos os termos são quadráticos. A necessidade de o fazer tornar-se-á em breve clara. Note que esta equação contém apenas a adição e multiplicação do polinômio de z.

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-8fdea08104-dd1a6f-cd5cc0.webp)

A seguir, explicaremos as etapas reais com mais detalhes.

Encriptação de curva elíptica

A teoria geral das curvas elípticas está muito além do escopo deste artigo. Para os fins deste artigo, curvas elípticas são definidas como mapeamento do domínio primo Fp para a função E, onde E inclui pontos que satisfazem y^2=x^3+ax+b (chamados pontos de curva elíptica, ou ECPs para abreviar).

Note que, embora tenhamos falado de aritmética regular até agora, agora, quando convertemos para campos primos, as operações aritméticas em números são feitas de forma modular. Por exemplo, a+b=a+b(mod p), onde p é a ordem de Fp.

Por outro lado, a definição de adição de dois pontos de curva elíptica é mostrada na figura a seguir:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-baf3cc3cbe-dd1a6f-cd5cc0.webp)

Especificamente, a adição de dois ECPs, P e Q:

Encontre a intersecção da linha PQ e da curva R, definida como -(P+Q)

Vire para o ponto “espelho” R’ na curva para R.

Assim, definimos a adição de pontos de curva elíptica P+Q=R’:

Note-se que esta regra também se aplica a casos especiais, ou seja, quando um auto-aditivo ECP, onde a tangente do ponto será usada.

Agora suponha que escolhemos um ponto aleatório G e mapeiamos o número 1 para ele. (Este “mapeamento inicial” soa um pouco arbitrário.) Mais sobre isso mais tarde). Então, para qualquer n pertencer à Fp, definimos:

E(N)=G+G+G+…+G=G

Isso tem uma expressão de ação. As ações que definem +G são “geradores” e são indicadas como g. Então a definição acima é equivalente a:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-bb825d6ba2-dd1a6f-cd5cc0.webp)

Para aqueles que não estão familiarizados com curvas elípticas, você pode analogiar esse mapeamento a uma função exponencial regular onde o cardeal g substitui os números reais. As operações aritméticas comportam-se de forma semelhante. No entanto, uma diferença fundamental é que a função inversa de g^n não é computacionalmente viável. Ou seja, não há como calcular a versão da curva elíptica! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c989bcd81c-dd1a6f-cd5cc0.webp)。 Esta é, naturalmente, a base da criptografia de curva elíptica. Esse mapeamento é conhecido como criptografia unidirecional.

Note que dada uma curva elíptica, uma vez que selecionar G (e, portanto, Gerador g) é arbitrário (exceto para pontos no eixo x), há um número infinito de maneiras de mapeá-la. Escolher (G ou g) pode ser análogo à escolha da cardinalidade de uma função exponencial (2^x, 10^x, e^x, etc.) como parte do senso comum.

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-ce9f261ecc-dd1a6f-cd5cc0.webp)

No entanto, a equação (5) que Alice quer provar é quadrática e, portanto, não é suficientemente linear. Para lidar com termos quadráticos, precisamos definir multiplicação no espaço criptográfico. Isso é conhecido como uma função de emparelhamento, ou mapa bilinear, e será explicado a seguir.

Mapeamento bilinear

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/resized-social/moments-40baef27dd-146a4881e5-dd1a6f-cd5cc0)

Cadeia de referência comum

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-17e9a49fa0-dd1a6f-cd5cc0.webp)

Todo o processo é chamado de “chave de verificação”, ou VK para abreviar. Há apenas 7 pontos de curva elíptica (ECPs) envolvidos aqui, que precisam ser fornecidos ao verificador. É importante notar que, não importa quantas entradas e restrições de primeiro nível estejam envolvidas no problema, o VK é sempre composto por 7 ECPs.

Além disso, vale a pena mencionar que a “configuração confiável” e o processo de geração de PK e VK podem ser feitos uma vez para um determinado problema.

Prova & Verificação

Agora com a chave pública (PK), Alice calculará os seguintes pontos de curva elíptica (ECPs):

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-c7eacd57e6-dd1a6f-cd5cc0.webp)

Estes 9 pontos de curva elíptica são a chave para provas não interativas concisas de conhecimento zero (zk-SNARKs)!

Note que Alice está na verdade apenas fazendo algumas operações combinatórias lineares nos pontos da curva elíptica na chave pública. Isto é particularmente crítico e será verificado durante a validação.

Agora que Alice entregou a prova zk-SNARK, vamos finalmente entrar no processo de verificação, que é um processo de três etapas.

Em primeiro lugar, é importante certificar-se de que os primeiros 8 pontos da curva elíptica são realmente uma combinação linear desses pontos na cadeia de referência genérica.

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-4cf599e8c2-dd1a6f-cd5cc0.webp)

Se todas as três verificações forem verdadeiras, então a equação (5) é verificada, então acreditamos que Alice conhece a testemunha.

Vamos explicar a lógica por trás da equação. Tomemos como exemplo a primeira equação da primeira parte, que se mantém devido à natureza bilinear:

! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-0032ace846-dd1a6f-cd5cc0.webp)

No entanto, como Alice não sabe o valor do símbolo alfa, ela é incapaz de calcular essa adição explicitamente. A única maneira que ela poderia chegar a um par que satisfizesse a equação (EA, EA’) era usar o mesmo conjunto de vetores s, calcular! [O Poder das Provas de Conhecimento Zero: Descodificação Matemática zk-SNARKs] (https://img-cdn.gateio.im/webp-social/moments-40baef27dd-933d054c72-dd1a6f-cd5cc0.webp).

Referências

“Zk-SNARKs: Sob o Capô” (Vitalik Buterin)

“A Review of Zero Knowledge Proofs” (Thomas Chen, Abby Lu, Jern Kunpittaya e Alan Luo)

“Por que e como zk-SNARK funciona: explicação definitiva” (Maksym Petkus)

Website: Provas de Conhecimento Zero

Wikipedia: Curva elíptica

Wikipedia: Campo finito

Wikipedia: Criptografia baseada em emparelhamento