Bem vindo! Novo em Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with monthly highlights on ecosystem growth, network development and how to get started with Zcash!

Idioma

Explicando SNARKs Parte VII: Emparelhamentos de curvas elípticas

Ariel Gabizon | Jun 07, 2017

<< Parte VI

Na Parte VI, vimos um esboço do Protocolo Pinóqui zk-SNARK. Sentíamos falta de duas coisas - um HH que suporta a adição e a multiplicação que são necessárias para as verificações do verificador, e uma transição de um protocolo interativo para um sistema não-interativo de prova.

Neste post, veremos que, usando curvas elípticas, podemos obter uma limitada, mas suficiente para nossos propósitos, forma de HH que suporta a multiplicação. Em seguida, mostraremos que esse HH limitado também é suficiente para converter o nosso protocolo no sistema não-interativo desejado.

Começamos com a introdução sobre curvas elípticas e explicando como elas nos dão o HH necessário.

Curvas elípticas e seus pares

Assuma \(p\) é um primo maior que \(3\), e tire algum \(u,v\in\mathbb{F}_p\) de modo que \(4u^3+27v^2\neq 0\). Observamos a equação

\(Y^2=X^3 +u\cdot X +v\)

Uma curva elíptica \({\mathcal C}\) é o conjunto de pontos \((x,y)\) [1] que satisfazem essa equação. Essas curvas nos dão uma maneira interessante de construir grupos. Os elementos do grupo serão os pontos \((x,y)\in \mathbb{F}^2_p\) que estão na curva, isto é, que satisfazem a equação, juntamente com um ponto especial \({\mathcal O}\), que por razões técnicas às vezes é designado como "ponto no infinito", e serve como o elemento de identidade, isto é, o zero do grupo.

Agora, a questão é como nós adicionamos dois pontos \(P=(x_1,y_1),Q=(x_2,y_2)\) para obter um terceiro? A regra de adição é derivada de um objeto algo abstrato chamado grupo divisor de classe da curva. Para nossos propósitos, tudo o que você precisa saber sobre esse grupo de classe divisora ​​é que ele impõe a seguinte restrição na definição de adição: A soma de pontos em qualquer linha deve ser zero, ou seja, \({\mathcal O}\).

Vamos ver como a regra de adição é derivada dessa restrição. Olhe para uma linha vertical, definida por uma equação da forma \(X=c\). Suponha que esta linha cruze a curva em um ponto \(P=(x_1,y_1)\). Porque a equação da curva é da forma \(Y^2=f(X)\), se \(Y^2=f(X)\) está na curva, então o ponto \(Q:=(x_1,-y_1)\) também está. Além disso, uma vez que é uma linha vertical e a equação da curva é de grau dois em \(Y\), podemos ter certeza de que estes são os únicos pontos onde a linha e a curva se cruzam.

Test |P+Q=O --> P=-Q|

Assim, devemos ter \(P+Q={\mathcal O}\) que significa \(P=-Q\); isto é, \(Q\) é o inverso de \(P\) no grupo.

Agora vejamos os pontos \(P\) e \(Q\) que têm uma primeira coordenada diferente - isto é, \(x_1\neq x_2\), e veja como adicioná-los. Passamos uma linha através de \(P\) e \(Q\).

Test |P+Q+R=0|

Como a curva é definida por um polinômio de grau três em \(X\) e já cruza essa linha (não vertical) em dois pontos, é garantida a intersecção a linha em um terceiro ponto, que denotamos \(R=(x,y)\), e nenhum outro ponto.

Portanto, devemos ter \(P+Q+R={\mathcal O}\), o que significa \(P+Q=-R\); e agora sabemos que \(-R\) é obtido de \(R\) lançando a segunda coordenada de \(y\) para \(-y\).

Assim, derivamos a regra de adição para o nosso grupo: pontos dados \(P\) e \(Q\), passe uma linha através deles e, em seguida, pegue o ponto "espelho" do terceiro ponto de interseção da linha como resultado de adição. [2]

Este grupo geralmente é chamado \({\mathcal C}(\mathbb{F}_p)\) - pois é constituído por pontos na curva \({\mathcal C}\) com coordenadas em \(\mathbb{F}_p\); mas vamos denotá-lo por \(G_1\) de agora em diante. Suponha por simplicidade que o número de elementos em \(G_1\) é um número primo \(r\), e é diferente de \(p\). Isso é muitas vezes o caso, por exemplo, na curva que o Zcash está usando atualmente. Nesse caso, qualquer elemento \(g\in G_1\) diferente de \({\mathcal O}\) gera \(G_1\).

O menor número inteiro \(k\) de modo que \(r\) divida \(p^k-1\) é chamado de grau de incorporação da curva. É conjecturado que quando \(k\) não é muito pequeno, digamos, pelo menos \(6\), então o problema de logaritmo discreto em \(G_1\), por exemplo encontrando \(\alpha\) a partir de \(g\) e \(\alpha \cdot g\), é muito difícil. (Nas curvas BN [3] atualmente usadas por Zcash \(k=12\).)

O grupo multiplicativo de \(\mathbb{F}_{p^k}\) contém um subgrupo de ordem \(r\) que denotamos \(G_T\). Podemos observar pontos de curva com coordenadas em \(\mathbb{F}_{p^k}\) e não apenas em \(\mathbb{F}_p\). Sob a mesma regra de adição, esses pontos também formam um grupo junto com \({\mathcal O}\) chamado \({\mathcal C}(\mathbb{F}_{p^k})\). Observe que \({\mathcal C}(\mathbb{F}_{p^k})\) contém claramente \(G_1\). Além de \(G_1\), \({\mathcal C}(\mathbb{F}_{p^k})\) conterá um subgrupo adicional \(G_2\) da ordem \(r\) (Na verdade \(r-1\) subgrupos adicionais de ordem \(r\)).

Conserto de geradores \(g\in G_1,h\in G_2\). Acontece que existe um mapa eficiente, denominado vinculação reduzida Tate, tirando um par de elementos de \(G_1\) e \(G_2\) em um elemento de \(G_T\),

de tal modo que

  1. \(\mathrm{Tate}(g,h)=\mathbf{g}\) para um gerador \(\mathbf{g}\) of \(G_T\), e
  2. dado um par de elementos \(a,b \in \mathbb{F}_r\), nós temos \(\mathrm{Tate}(a\cdot g,b\cdot h)=\mathbf{g}^{ab}\).

Definindo \(\mathrm{Tate}\) está um pouco além do escopo desta série, e baseia-se em conceitos de geometria algébrica, mais proeminente que de divisores. Aqui está um esboço da definição de \(\mathrm{Tate}\)'s: [4]

Para \(a\in\mathbb{F}_p\) o polinômio \((X-a)^r\) tem um zero de multiplicidade \(r\) no ponto \(a\), e nenhuns outros zeros. Por um ponto \(P\in G_1\), os divisores nos permitem provar que existe uma função \(f_P\) da curva para \(\mathbb{F}_p\) que também tem, em algum sentido preciso, um zero de multiplicidade \(r\) em \(P\) e nenhuns outros zeros. \(\mathrm{Tate}(P,Q)\) é então definido como \(f_P(Q)^{(p^k-1)/r}\).

Pode não parecer claro o que essa definição tem a ver com as propriedades declaradas, e, de fato, a prova de que \(\mathrm{Tate}\) tem essas propriedades são bastante complexas.

Definindo \(E_1(x) := x\cdot g, E_2(x):=x\cdot h, E(x):=x\cdot \mathbf{g}\), obtemos uma versão fraca de um HH que suporte adição e multiplicação: \(E_1,E_2,E\) são HHs que suportam a adição, e dado os esconderijos \(E_1(x)\), \(E_2(y)\) podemos calcular \(E(xy)\). Em outras palavras, se tivermos os esconderijos "certos" de \(x\) e \(y\) podemos obter um (diferente) esconderijo de \(xy\). Mas, por exemplo, se tivéssemos esconderijos de \(x,y,z\) não conseguiríamos o esconderijo de \(xyz\).

Passamos a discutir sistemas de prova não-interativos. Começamos por explicar exatamente o que queremos dizer com "não-interativo".

Prova não-interativa no modelo de referência de comum

A noção mais forte e intuitiva de uma prova não-interativa é provavelmente o seguinte. Para provar uma certa reivindicação, aquele que quer provar transmite uma única mensagem a todas as partes, sem comunicação prévia de qualquer tipo; e qualquer pessoa que lesse esta mensagem estaria convencida do pedido feito por quem quer provar. Isso pode ser mostrado na impossibilidade na maioria dos casos. [5]

Uma noção ligeiramente relaxada de prova não-interativa é permitir uma sequência de referência comum (CRS). No modelo CRS, antes de serem construídas todas as provas, há uma fase de configuração onde uma sequência de caracteres é construída de acordo com um determinado processo randomizado e transmitida para todas as partes. Esta cadeia é chamada de CRS e é usada para ajudar a construir e verificar as provas. O pressuposto é que a aleatoriedade utilizada na criação do CRS não é conhecida por qualquer parte - pois o conhecimento dessa aleatoriedade pode permitir a construção de provas de afirmações falsas.

Vamos explicar como no modelo CRS podemos converter o protocolo de avaliação cega verificável da Parte IV em um sistema de prova não-interativo. Como o protocolo da Parte VI consistia em alguns desses subprotocolos ele pode ser transformado em um sistema de prova não-interativo de forma semelhante.

Um protocolo de avaliação não-interativa

A versão não-interativa do protocolo de avaliação basicamente consiste em publicar a primeira mensagem de Bob como o CRS. Lembre-se de que o propósito do protocolo é obter o esconder \(E(P(s))\) do polinômio de Alice \(P\) em um \(s\in\mathbb{F}_r\) escolhido aleatoriamente.

Configuração: Aleatoriamente \(\alpha\in \mathbb{F}_r^*,s\in\mathbb{F}_r\) são escolhidos e o CRS:

\((E_1(1),E_1(s),\ldots,E_1(s^d),\) \(E_2(\alpha),E_2(\alpha s),\ldots,E_2(\alpha s^d))\)
é publicado.

Prova: Alice calcula \(a=E_1(P(s))\) and \(b=E_2(\alpha P(S))\) usando os elementos do CRS e o fato de que \(E_1\) e \(E_2\) suportam combinações lineares.

Verification: Fix the \(x,y\in \mathbb{F}_r\) de tal modo que \(a=E_1(x)\) and \(b=E_2(y)\). Bob computes \(E(\alpha x)=\mathrm{Tate}(E_1(x),E_2(\alpha))\) and \(E(y)=\mathrm{Tate}(E_1(1),E_2(y))\), and checks that they are equal. (If they are equal it implies \(\alpha x =y\).)

Como explicado na Parte IV, Alice só pode construir \(a,b\) que passará a etapa de verificação se \(a\) é o esconderijo de \(P(s)\) para um polinômio \(P\) de grau \(d\) conhecida por ela. A principal diferença aqui é que Bob não precisa saber \(\alpha\) para checar a verificação, pois ele pode usar o emparelhamento função para calcular \(E(\alpha x)\) apenas de \(E_1(x)\) e \(E_2(\alpha)\). Assim, ele não precisa construir e enviar a primeira mensagem, e esta mensagem simplesmente pode ser corrigida no CRS.

[1]Você pode perguntar "O conjunto de pontos de onde?". Queremos dizer o conjunto de pontos com coordenadas no fechamento algébrico de \(\mathbb{F}_p\). Além disso, a curva possui uma versão afim e projetiva. Quando nos referimos à versão projetiva também incluímos o "ponto no infinito" \({\mathcal O}\) como um elemento da curva.
[2]Não abordamos o caso de adicionar \(P\) para si mesmo. Isso é feito usando a linha que é tangente à curva em \(P\), e tomando \(R\) para ser o segundo ponto de interseção desta linha com a curva.
[3]https://eprint.iacr.org/2005/133.pdf
[4]O emparelhamento que a Zcash realmente usa é o emparelhamento ideal da Ate, que é baseado no vínculo reduzido da Tate , E pode ser calculado de forma mais eficiente do que \(\mathrm{Tate}\).
[5]Nos termos da teoria da complexidade computacional, pode-se mostrar que apenas os idiomas no BPP possuem provas de conhecimento nulo não-interativas neste sentido forte. O tipo de reivindicações que precisamos provar em transações Zcash, por exemplo 'conheço uma pré-imagem de hash desta string', corresponde à classe de complexidade NP que se acredita ser muito maior do que o BPP.
[6]As imagens utilizadas foram tiradas do seguinte artigo e são usadas sob a licença creative commons.

cryptography, zkSNARKs, explainers | Veja todas as tags