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

Compilado por: DODO Research

Autor: 0xAlpha Cofundador @DeriProtocol

Introdução

zk-SNARK, ou argumento sucinto de conhecimento não interativo de conhecimento zero, permite que um verificador confirme que um provador possui certos conhecimentos (chamados testemunhas) que satisfazem relações específicas sem revelar qualquer informação sobre o próprio conhecimento.

Gerar um zk-SNARK para um problema específico envolve as quatro etapas seguintes:

• Converter um problema (ou função) num circuito aritmético.
• Este circuito é depois traduzido numa equação matricial.
• Esta equação matricial é posteriormente convertida num 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 campo finito, onde a prova ocorre.

Os três primeiros passos transformam apenas a representação da declaração original. O último passo projeta a declaração do terceiro passo num espaço encriptado usando encriptação homomórfica, permitindo ao provador verificar as declarações espelhadas. Dado que esta projeção utiliza encriptação assimétrica, não é possível voltar atrás da declaração no passo 3 para a declaração original, garantindo a exposição ao conhecimento zero.

A base 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 aqueles que não estão familiarizados com isto, pode pensar nisso como uma função exponencial com uma base especial, tendo em mente que o seu inverso 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 em formas explícitas []; todos os vetores são vetores de coluna por padrão\ Escalares: Representados por letras regulares

Vamos tomar a seguinte pergunta como exemplo:

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

Suponha que a Alice queira provar que sabe a verdade. Vamos percorrer todo o procedimento que a Alice precisa fazer para gerar um zk-SNARK para a sua prova.
Esta pergunta pode parecer demasiado simples porque não envolve fluxo de controlo (por exemplo, se-então). No entanto, não é difícil converter funções com fluxo de controlo em expressões aritméticas. Por exemplo, considere o seguinte problema (ou “função” em linguagens de programação):

f (x, z):
if (z==1):
retornar xxx+xx+5
senão:
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 a nossa discussão.

Passo 1: Circuito Aritmético

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

Isto 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.

Passo 2: Matrix

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

onde y, s1, s2 e s3 são definidos como na equação (2).
Tipicamente, para um problema com m entradas e n portas aritméticas (i.e. n-1 passos intermédios 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 de hash, n é normalmente na casa dos milhares.

Em seguida, 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 outra representação da equação (2): cada conjunto (ai, bi, ci) corresponde a uma porta no circuito. Podemos ver isto expandindo explicitamente a equação da matriz:

Portanto LHS=RHS é exatamente o mesmo que a equação (2), e cada linha da equação da matriz corresponde a uma restrição primária (ou seja, uma porta aritmética no circuito).

Saltámos os degraus do edifício (A, B, C), que são realmente relativamente simples. Só precisamos 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 ver facilmente que para fazer 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 numa equação matricial, ou seja, a equação (3). Ao mesmo tempo, também mudamos o objeto que precisa ser provado para ser dominado para o vetor testemunha s.

Passo 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:

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

Então podemos reescrever A como:

Estes são quatro conjuntos de equações lineares que envolvem seis variáveis que podem ser resolvidas usando métodos tradicionais. No entanto, uma maneira mais eficiente de resolver a PA neste caso é a interpolação lagrangiana, que explora as peculiaridades do problema. Aqui pulamos o processo de resolução de PA, o que é um pouco tedioso mas simples.

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

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

Passo 3: Ponto de 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. Note que esta equação contém apenas a adição e multiplicação de polinómios em z.

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

A seguir, explicaremos os passos práticos com mais detalhes.

Criptografia de curva elíptica

A teoria geral das curvas elípticas vai muito além do âmbito deste artigo. Para os fins aqui apresentados, uma curva elíptica é definida como mapeamentos de um campo primo 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).

Por favor, note que embora tenhamos discutido aritmética regular até agora, ao fazer a transição para um campo primo, as operações aritméticas em 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 como mostrado abaixo:

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

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':

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

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

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

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

Depois de definir a adição, a seguinte relação linear torna-se evidente:

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

No entanto, como a equação (5) que Alice quer provar está na forma quadrática, não é suficientemente linear. Para lidar com termos quadráticos, precisamos definir a multiplicação no espaço encriptado. Isto chama-se emparelhamento, ou mapa bilinear, que explicarei na secção seguinte.

Mapa Bilinear

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

Cadeia de referência comum

Tudo isto é denominado a “chave de prova” (PK). Note que a representação dos vetores dentro de E () deve ser entendida como vetores de pontos de curva elíptica, onde cada ponto é mapeado a partir do elemento vetorial correspondente. Assim, estes 11 vetores compreendem na verdade 62 (=42+63+63+63) pontos de curva elíptica. Estes 62 ECP serão fornecidos a Alice, a provadora. Num cenário geral, para um problema com m entradas e n 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 chama-se “chave de verificação” (VK). Apenas 7 pontos de curva elíptica (ECPs) estão envolvidos aqui, que precisam ser fornecidos ao verificador. Deve notar-se 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 a pena mencionar 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 calculará os seguintes pontos de curva elíptica (ECPs):

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

Note que a Alice está essencialmente apenas a realizar 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 facto as 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 de autor pertencem ao autor original [0xAlpha Co-fundador @ DeriProtocol]. Se houver objeções a esta reimpressão, contacte a equipa do Gate Learn, e eles tratarão disso imediatamente.
2. Isenção de responsabilidade: As opiniões e opiniões expressas neste artigo são exclusivamente do autor e não constituem nenhum conselho de investimento.
3. As traduções do artigo para outras línguas são feitas pela equipa do Gate Learn. A menos que mencionado, é proibido copiar, distribuir ou plagiar os artigos traduzidos.