Preâmbulo
Você está pronto para explorar um lado mais complexo do zk-SNARK? Na seção anterior, aprendemos alguns conceitos mais avançados, como o Circuito Aritmético e o Programa Aritmético Quadrático. Nesta seção, expandiremos nosso conhecimento nos aprofundando em outro conceito poderoso: Emparelhamentos de Curvas Elípticas.
Observação: compreender profundamente um tópico como emparelhamentos de curvas elípticas às vezes pode ser um desafio para muitos. No entanto, é por isso que temos este artigo – para ajudá-lo a obter pelo menos uma perspectiva básica sobre isto.
Meu objetivo não é apenas explicar detalhadamente pares de curvas elípticas , mas também tornar o assunto mais interessante e fácil de entender. Esperamos que, através deste artigo, você veja o poder dos pares de curvas elípticas na matemática e na criptografia em geral, bem como em suas aplicações específicas em zk-SNARKs em particular.
Curvas elípticas
As curvas elípticas fazem parte do campo da Criptografia de Curvas Elípticas. Este é um assunto complexo que não é fácil de ser compreendido por todos. Para entendê-los melhor, dê uma olhada no meu artigo anterior sobre ECC.
A criptografia de curva elíptica envolve “pontos” no espaço bidimensional, cada “ponto” caracterizado por um par de coordenadas (x, y).
Existem regras específicas para a realização de operações matemáticas como adição e subtração entre pontos, permitindo calcular as coordenadas de um novo ponto quando outros pontos são conhecidos.
Exemplo: Calcule as coordenadas R = P + Q
Você também pode multiplicar um ponto por um número inteiro adicionando repetidamente o ponto a si mesmo tantas vezes quanto esse número inteiro.
Por exemplo: P * n = P + P +… + P
Isso fornece uma maneira eficiente de realizar operações matemáticas na criptografia de curva elíptica
Em uma curva elíptica, existe um ponto especial chamado “ponto no infinito” (O), equivalente a zero no cálculo de pontos, é sempre verdade que P + O = P.
Uma curva também tem uma “ordem”; existe um número n tal que P * n = O para todo P ( P * (n+1) = P, P * (7*n + 5) = P * 5 e assim por diante).
Existe também um “ponto gerador” (G), que se entende representar o número 1 de alguma forma. Em teoria, qualquer ponto da curva (exceto O) poderia ser G.
Emparelhamentos
Os emparelhamentos permitem testes de equações mais complexos em pontos de curvas elípticas.
Por exemplo:
você pode verificar se p * q é igual a r apenas de P, Q e R.
Embora informações sobre p possam vazar de P, esse vazamento é cuidadosamente controlado.
Os emparelhamentos permitem testar restrições quadráticas.
Por exemplo: Testar e(P, Q) * e(G, G * 5) = 1 é na verdade testar p * q + 5 = 0.
é uma operação matemática chamada pareamento. Os matemáticos também chamam isso de mapeamento bilinear. “Bilinear” aqui obedecerá às seguintes regras:
Observe que você pode usar os operadores + e * de qualquer forma, desde que obedeçam às seguintes regras:
e
Se P, Q, R e S são números simples, é fácil criar uma operação simples de emparelhamento com a expressão:
Os resultados são os seguintes:
Isso é paralelismo !
No entanto, essas operações simples de emparelhamento não são adequadas para criptografia porque operam em números inteiros simples e são muito fáceis de analisar.
Depois de saber um número e seu resultado ao realizar a operação de pareamento, você poderá calcular e encontrar facilmente o número restante.
Usamos operações matemáticas como “caixas pretas”, onde apenas operações básicas podem ser realizadas sem análise ou compreensão adicional. É por isso que as curvas elípticas e a operação de emparelhamento em curvas elípticas se tornam importantes na criptografia.
Campos Primários e Campos de Extensão
É possível criar um mapa bilinear (Mapas Bilineares) em pontos de curva elíptica — ou seja, criar uma função
onde P e Q são pontos de curva elíptica e o resultado é um tipo de elemento chamado F_p¹²
Primeiro, vamos entender os campos principais e os campos de extensão.
A curva elíptica na imagem acima é tão bonita porque a equação da curva é definida usando números reais comuns.
No entanto, na criptografia, o uso de números reais comuns pode levar ao uso de logaritmos para “retroceder” e estragar tudo, pois a quantidade de espaço necessária para armazenar e representar números pode aumentar arbitrariamente. Portanto, usamos números em campos primos.
Um campo primo consiste no conjunto de números 0, 1, 2… p-1, onde p é primo e as diversas operações são definidas da seguinte forma:
Todas as operações são realizadas módulo p
A divisão é um caso especial; normalmente, 3/2 não é um número inteiro, e agora só quero lidar com números inteiros, então, em vez disso, tento encontrar o número x tal que
x * 2 = 3.
Isso pode ser feito usando o Algoritmo Euclidiano Estendido. Por exemplo, se p = 7, então:
A seguir, falaremos sobre campos de extensão.
Um exemplo comum que você encontra frequentemente em livros de matemática é o campo de número complexo, onde o campo de número real é “estendido” com o elemento adicional sqrt(-1) = i.
Os campos de extensão funcionam pegando um campo existente e, em seguida, “adicionando” um novo elemento e definindo um relacionamento entre esse novo elemento e os elementos já no campo original (por exemplo, i² + 1 = 0).
O importante é que esta equação não seja verdadeira para nenhum número do corpo original, e então considere todas as combinações lineares dos elementos do campo original e do novo elemento recém-criado.
Também podemos estender campos principais
Por exemplo, estendendo o campo principal mod 7 que descrevemos acima com i, podemos fazer o seguinte:
Se você quiser ver toda a matemática feita no código, campos principais e extensões de campo são feitos aqui
Emparelhamentos de curvas elípticas
O emparelhamento de curva elíptica é um mecanismo que pega dois pontos de duas curvas elípticas e mapeia esses pontos em um único número.
Você pode pensar neste mapeamento como equivalente à multiplicação de pontos em uma curva elíptica.
Matematicamente, o emparelhamento de curva elíptica é definido como o mapeamento de dois pontos em uma curva elíptica para um elemento em outro grupo como um campo finito:
Aqui e está emparelhamento, E1 e E2 são curvas elípticas e 𝐹 é um corpo finito.
Observe que Curvas Elípticas E1 e E2 não precisam ser diferentes.
Depois que a concatenação ocorre, o resultado é que um elemento de outro grupo não pode ser reutilizado na próxima concatenação.
Os pares de curvas elípticas têm certas propriedades chamadas mapeamentos bilineares:
Aqui P, Q e R são pontos na curva elíptica e 𝑎∈𝑍, 𝑏∈𝑍
Usando esses “mapeamentos bilineares”, podemos “mover” os coeficientes 𝑎 e 𝑏 nessas duas curvas, mantendo o mesmo mapeamento:
Fonte: https://muens.io/elliptic-curve-pairing
Podemos imaginar o pareamento de curvas elípticas como um mapeamento de G2 x G1 -> Gt, onde:
G1 é uma curva elíptica, onde os pontos satisfazem uma equação de forma
e ambas as coordenadas são elementos de F_p (são números simples, mas as operações são realizadas no módulo de um número primo específico)
G2 também é uma curva elíptica, onde os pontos satisfazem a mesma equação de G1, mas suas coordenadas pertencem ao corpo F_p¹² (definimos um novo “número mágico” w, definido por um polinômio de grau 12 como:
Gt é o tipo de objeto no qual entra o resultado da curva elíptica. Nas curvas que consideramos, Gt é F_p¹² (o mesmo número complexo forte usado em G2)
Aqui deve satisfazer a bilinearidade:
Junto com dois outros critérios importantes:
Computabilidade eficiente: Compatibilidade eficiente significa ser capaz de calcular operações compostas rapidamente e sem muita complexidade. Por exemplo, se apenas pegarmos o logaritmo discreto dos pontos e multiplicá-los para criar uma concatenação, isso se tornaria computacionalmente muito difícil. assim como quebrar a cifra da curva elíptica original. Portanto, uma operação composta é considerada computacionalmente eficiente se puder ser computada de forma eficiente sem impor muita carga computacional.
Não degenerescência: A não degenerescência garante que a concatenação não seja uma concatenação inútil, ou seja, não retorna apenas um valor fixo independente dos pontos de entrada. Por exemplo: Se pretendemos, o significado composto é e(P, Q) = 1. para todos P e Q, o que não fornece nenhuma informação útil sobre a relação entre pontos na curva elíptica. Portanto, uma concatenação é considerada não degenerativa se fornecer informações úteis sobre o relacionamento entre os pontos de entrada.
Então, como fazer isso?
Primeiro, precisamos entender o conceito de divisor, outra forma de representar uma função sobre pontos em uma curva elíptica.
Um divisor de uma função conta essencialmente os zeros e os números infinitos da função. Para entender o que isso significa, vejamos alguns exemplos. Vamos fixar alguns pontos P = (P_x, P_y) e considerar a seguinte função:
O divisor là [P] + [-P] – 2 * [O]
[P] + [Q] não é o mesmo que [P + Q]. As razões são as seguintes:
A função é zero em P porque quando x é P_x, então x – P_x = 0.
A função é zero em -P porque -P e P têm a mesma coordenada x.
A função vai para o infinito assim como x vai para o infinito, então dizemos que a função é infinita em O.
O motivo está na equação da curva elíptica:
y cresce até o infinito cerca de “1,5 vezes” mais rápido que x para poder acompanhar x^3 . Portanto, se uma função linear tiver apenas x, ela será representada como infinito com multiplicidade de 2, mas se tiver y, será representada como infinito com multiplicidade de 3.
Agora, considere uma “função de linha”:
Onde a, b e c são cuidadosamente escolhidos para que a linha passe pelos pontos P e Q na curva elíptica.
Devido à forma como a adição funciona em uma curva elíptica, isso também significa que ela passa pelo ponto -P-Q. Esta função também vai para o infinito dependendo de x e y, dividindo assim as possibilidades
Cada “função racional” (uma função definida usando apenas um número finito de operações +, -, *, / nas coordenadas de um ponto) corresponde exclusivamente a um divisor, sujeito à condição de multiplicação por uma constante (ou seja, se duas funções F e G têm o mesmo divisor, então F = G * k onde k é uma constante).
A divisão do produto de duas funções é igual à soma das divisões de cada função, então
então
Fonte do artigo: Equipe Tech/Research Alphatrue
Fonte de referência:
https://medium.com/@VitalikButerin/exploring-elliptic-curve-pairings-c73c1864e627