Este artigo irá decodificar esta tecnologia usando a matemática, ilustrando como ela pode provar a veracidade do conhecimento sem revelar qualquer informação.

Compilado por: DODO Research

Autor: Cofundador da 0xAlpha @DeriProtocol

Introdução

Zk-SNARK, ou argumento de conhecimento sucinto e não interativo de conhecimento zero, permite que um verificador confirme que um provador possui certo conhecimento (chamado de testemunhas) que satisfaz relacionamentos específicos sem revelar qualquer informação sobre o conhecimento em si.

A geração de um zk-SNARK para um problema específico envolve as quatro etapas a seguir:

• Converta um problema (ou função) em um circuito aritmético.
• Este circuito é então traduzido em uma equação matricial.
• Esta equação matricial é posteriormente convertida em um polinômio que deve ser divisível por um polinômio mínimo específico.
• Finalmente, esta divisibilidade é expressa em pontos de curva elíptica sobre um corpo finito, onde ocorre a prova.

Os três primeiros passos apenas transformam a representação da afirmação original. A última etapa projeta a declaração da terceira etapa em um espaço criptografado usando criptografia homomórfica, permitindo ao provador verificar as declarações espelhadas nele contidas. Dado que esta projeção utiliza criptografia assimétrica, não é viável voltar da declaração da etapa 3 para a declaração original, garantindo exposição de conhecimento zero.

A formação matemática necessária para ler este artigo é comparável ao nível de álgebra esperado dos estudantes universitários STEM do primeiro ano. O único conceito que pode ser desafiador pode ser a criptografia de curva elíptica. Para quem não está familiarizado com isto, pode pensar nela como uma função exponencial com uma base especial, tendo em mente que a sua inversa permanece sem solução.

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

Matrizes: letras maiúsculas em negrito, por exemplo A; escrito em formas explícitas \
Vetores: Letra minúscula com setas, escrita de forma explícita [ ]; todos os vetores são vetores de coluna por padrão \
Escalares: representados por letras regulares

Tomemos como exemplo a seguinte questão:

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

Suponha que Alice queira provar que conhece uma verdade. Percorreremos todo o procedimento que Alice precisa realizar para gerar um zk-SNARK para sua prova.
Esta questão pode parecer muito simples porque não envolve fluxo de controle (por exemplo, if-then-else). Entretanto, não é difícil converter funções com fluxo de controle em expressões aritméticas. Por exemplo, considere o seguinte problema (ou “função” em linguagens de programação):

f(x, z):
se(z==1):
retornar xxx+xx+5
outro:
retornar xx+5

Reescrever este problema na seguinte expressão aritmética (assumindo que z pertence a (0,1)) não é mais complexo 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 nossa discussão.

Etapa 1: Circuito Aritmético

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

Isso corresponde ao seguinte circuito aritmético:

Também nos referimos à equação (2) como um conjunto de 4 “restrições primárias”, cada restrição descrevendo a relação de uma porta aritmética no circuito. Em geral, um conjunto de n restrições primárias pode ser resumido como um programa aritmético quadrático (QAP), que será explicado a seguir.

Etapa 2: Matriz

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

onde y, s1, s2 e s3 são definidos como na equação (2).
Normalmente, para um problema com m entradas e n portas aritméticas (ou seja, n-1 etapas intermediárias e a saída final), este vetor testemunha será (m+n+1) dimensional. Em casos do mundo real, o número n pode ser extremamente grande. Por exemplo, para funções hash, n geralmente está na casa dos milhares.

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

A equação (3) é apenas mais uma representação da equação (2): cada conjunto (ai, bi, ci) corresponde a uma porta do circuito. Podemos ver isso expandindo explicitamente a equação matricial:

Portanto, LHS=RHS é exatamente igual à equação (2), e cada linha da equação matricial corresponde a uma restrição primária (isto é, uma porta aritmética no circuito).

Pulamos as etapas de construção (A, B, C), que na verdade são relativamente simples. Precisamos apenas convertê-los em matriz de acordo com as restrições primárias correspondentes para determinar o conteúdo de cada linha de (A, B, C), ou seja, (ai, bi, ci). Tomando a primeira linha como exemplo: podemos facilmente ver que para tornar a primeira restrição primária x multiplicada por x igual a s1, precisamos multiplicar [0,1,0,0,0], [0, 1,0, 0,0] e [0,0,0,1,0,0] pelo vetor s.

Assim, convertemos com sucesso o circuito aritmético em uma equação matricial, nomeadamente a equação (3). Ao mesmo tempo, também alteramos o objeto que precisa ser provado para ser dominado para os vetores testemunhas.

Etapa 3: Polinômios

Agora, vamos construir uma matriz n(n+m+*1) PA, que define um conjunto de polinômios em relação a z:

Garantindo que a funçãoassume os seguintes valores em {1, 2, 3, 4} satisfaz as condições:

Então podemos reescrever A como:

São quatro conjuntos de equações lineares envolvendo seis variáveis que podem ser resolvidas usando métodos tradicionais. Porém, uma forma mais eficiente de resolver PA neste caso é a interpolação Lagrangiana, que explora as peculiaridades do problema. Aqui pulamos o processo de resolução de PA, que é um pouco tedioso, mas direto.

Da mesma forma, construímos PB e PC separadamente para B e C. Então podemos reescrever a equação matricialdo seguinte modo:

Observando cada linha separadamente, fica evidente que essas quatro linhas correspondem à mesma expressão avaliada em quatro pontos diferentes. Portanto, a equação matricial acima é equivalente a:

Etapa 3: Ponto da Curva Elíptica

Reescreva a equação (4) como:

onde i(z)=1 é apenas um polinômio trivial de grau zero em z usado para unificar as equações - todos os termos são quadráticos. A necessidade disso ficará clara em breve. Observe que esta equação contém apenas a adição e multiplicação de polinômios em z.

Observe que as operações aritméticas, adição (+) e multiplicação (X), também são mapeadas para operações correspondentes no corpo finito de pontos de curva elíptica. Os símbolos e são usados para evitar confusão e indicar que se trata de operações de campo redefinidas.

A seguir, explicaremos as etapas práticas com mais detalhes.

Criptografia de curva elíptica

A teoria geral das curvas elípticas vai muito além do escopo deste artigo. Para os propósitos deste documento, uma curva elíptica é definida como mapeamentos de um campo principal Fp para a função E, onde E inclui pontos tais que y^2=x^3+ax+b (chamados pontos de curva elíptica, ou ECPs, para abreviar) .

Observe que, embora tenhamos discutido aritmética regular até agora, ao fazer a transição para um corpo primo, as operações aritméticas com números são realizadas usando aritmética modular. Por exemplo, a+b=a+b(mod p), onde p é a ordem de Fp.

Por outro lado, a adição de dois pontos de curva elíptica é definida conforme mostrado abaixo:

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

Encontre a intersecção da linha PQ e da curva R e defina-a como -(P+Q)
Vire para o ponto “espelho” R' de R na curva.
Portanto definimos a adição de pontos de curva elíptica P+Q=R':

Observe que esta regra também se aplica ao caso especial em que é utilizada a adição de um ECP, caso em que será utilizada a tangente a esse ponto.

Agora suponha que selecionamos aleatoriamente um ponto G e mapeamos o número 1 para ele. (Este “mapeamento inicial” parece um pouco arbitrário. Discutiremos isso mais tarde). E para qualquer n pertencente a Fp, definimos:

E(N)=G+G+G+…..+G=G multiplicado por n

Existe uma expressão de operação. Defina a operação +G como “gerador”, denotado como g. Então a definição acima é equivalente a:

Após definir a adição, a seguinte relação linear torna-se evidente:

Portanto, qualquer relacionamento linear (ou restrição) em Fp será preservado no espaço criptografado B através deste mapeamento. Por exemplo, a equação l + m = n em Fp levará a

Contudo, como a equação (5) que Alice quer provar está na forma quadrática, ela não é suficientemente linear. Para lidar com termos quadráticos, precisamos definir a multiplicação no espaço criptografado. Isso é chamado de emparelhamento ou mapa bilinear, que explicarei na seção a seguir.

Mapa bilinear

Suponha que G1, G2 e GT sejam grupos de ordem prima g. Uma função de emparelhamento, ou mapa bilinear, é definida da seguinte forma:

String de referência comum

Este conjunto é denominado “chave de prova” (PK). Observe que a representação de vetores dentro de E() deve ser entendida como vetores de pontos de curvas elípticas, onde cada ponto é mapeado a partir do elemento vetorial correspondente. Assim, esses 11 vetores compreendem, na verdade, 62 (=42+63+63+63) pontos de curva elíptica. Estas 62 PAE serão fornecidas a Alice, a provadora. Em um cenário geral, para um problema com m entradas en restrições primárias, o PK conterá 2n + 3(m+n+1)*3 = 11n + 9m + 9 ECPs.

Simultaneamente, serão realizados os seguintes cálculos:

Todo o processo é denominado “chave de verificação” (VK). Apenas 7 pontos de curva elíptica (ECPs) estão envolvidos aqui, os quais precisam ser fornecidos ao verificador. Deve-se notar que não importa quantas entradas e restrições primárias estejam envolvidas no problema, o VK é sempre composto por 7 ECPs.

Além disso, vale ressaltar que a “configuração confiável” e o processo de geração de PK e VK só precisam ser feitos uma vez para um problema específico.

Prova e Verificação

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

Esses 9 pontos da curva elíptica são cruciais para um argumento de conhecimento sucinto e não interativo de conhecimento zero (zk-SNARK)!

Observe que Alice está essencialmente realizando combinações lineares nos pontos da curva elíptica na chave pública. Isto é particularmente crítico e será rigorosamente verificado durante a verificação.

Agora, Alice apresenta a prova zk-SNARK, levando-nos finalmente ao processo de verificação, que acontece em três etapas.

Primeiro, é necessário confirmar que os primeiros 8 pontos da curva elíptica são de fato combinações lineares desses pontos na cadeia de referência comum.

Isenção de responsabilidade:

1. Este artigo foi reimpresso de [chaincatcher]. Todos os direitos autorais pertencem ao autor original [0xAlpha Cofundador @ DeriProtocol]. Se houver objeções a esta reimpressão, entre em contato com a equipe do Gate Learn e eles cuidarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e pontos de vista expressos neste artigo são exclusivamente do autor e não constituem qualquer conselho 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.