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 II: Avaliação Cega de Polinômios

Ariel Gabizon | Mar 13, 2017

<< Part I

Neste post, lembramos a noção de um polinômio, e explicamos a noção de "avaliação cega" de um polinômio, e como ele é implementado usando Ocultação Homomórfica (HH). (Veja Part I para uma explicação sobre o que é HH.⇥) Em postagens futuras, veremos que a avaliação cega é uma ferramenta central nas construções SNARK.

Denotamos por \(\mathbb{F}_p\) o campo de tamanho \(p\); ou seja, os elementos de \(\mathbb{F}_p\) são \(\{0,\ldots,p-1\}\) e adição e multiplicação são feitas \(\mathrm{mod}\;p\) como explicado na Parte I.

Polinômios e combinações lineares

Lembre-se que um polinômio \(P\) de grau \(d\) sobre \(\mathbb{F}_p\) é uma expressão da forma

\(P(X) = a_0 + a_1\cdot X + a_2\cdot X^2 + \ldots + a_d\cdot X^d\), for some \(a_0,\ldots,a_d\in\mathbb{F}_p.\)

Podemos avaliar \(P\) em um ponto \(s\in {\mathbb{F}_p}\) substituindo \(s\) para \(X\), e computando a soma resultante

\(P(s) = a_0 + a_1\cdot s + a_2\cdot s^2 + \ldots + a_d\cdot s^d\)

Para alguém que sabe \(P,\) o valor \(P(s)\) é uma combinação linear dos valores \(1,s,\ldots,s^d\) - quando a combinação linear significa apenas "soma ponderada", no caso de \(P(s)\) os "pesos" são \(a_0,\ldots,a_d.\)

No último post, vimos a HH \(E\) definida por \(E(x)=g^x\) onde \(g\) era um gerador de um grupo com um problema difícil e discreto de log. Mencionamos que este HH "suporta adição" no sentido de que \(E(x+y)\) Pode ser calculado a partir de \(E(x)\) e \(E(y)\). Observamos aqui que ele também "suporta combinações lineares"; significando que, dado \(a,b,E(x),E(y),\) nós podemos computar \(E(ax+by)\). Este é simplesmente o por quê

\(E(ax+by)=g^{ax+by}=g^{ax}\cdot g^{by} = (g^x)^a\cdot (g^y)^b = E(x)^a\cdot E(y)^b.\)

Avaliação cega de um polinômio

Suponha que Alice tem um polinômio \(P\) de grau \(d\), e Bob tem um ponto \(s\in\mathbb{F}_p\) que ele escolheu aleatoriamente. Bob deseja descobrir \(E(P(s))\), isto é, a HH da avaliação de \(P\) em \(s.\) duas maneiras simples de fazer isso são:

  • Alice envia \(P\) para Bob, e ele calcula \(E(P(s))\) ele mesmo
  • Bob envia \(s\) para Alice; ela calcula \(E(P(s))\) e envia para Bob.

No entanto, no problema de avaliação cega queremos que Bob descubra \(E(P(s))\) sem descobrir \(P\) - o que impede a primeira opção; E, o mais importante, nós não queremos que Alice aprenda \(s\), que exclui o segundo [1].

Usando HH, podemos realizar avaliação cega como segue.

  1. Bob envia para Alice as ocultações \(E(1),E(s),\ldots,E(s^d).\)
  2. Alice computa \(E(P(s))\) a partir dos elementos enviados no primeiro passo, e envia \(E(P(s))\) para Bob. (Alice pode fazer isso desde que \(E\) suporta combinações lineares, e \(P(s)\) é uma combinação linear de \(1,s,\ldots,s^d.)\)

Note que, como apenas as ocultações foram enviados, nem Alice descobriu \(s\) [2], nem Bob descobriu \(P\).

Por que isso é útil?

Postagens posteriores irão entrar em mais detalhes sobre como a avaliação cega é usada em SNARKs. A intuição geral é que o verificador tem um polinômio "correto" em mente, e deseja verificar o provador sabe disso. Fazendo o provador avaliar cegamente seu polinômio em um ponto aleatório não conhecido por eles, Garante que o provador dará a resposta errada com alta probabilidade se seu polinômio não for o correto. Isso, por sua vez, baseia-se no Lema Schwartz-Zippel afirmando que "diferentes polinômios são diferentes na maioria dos pontos".

[1]A principal razão que não queremos enviar \(P\) para Bob, é simplesmente que ele é grande - (d+1) elementos, onde, por exemplo, d~2000000 no protocolo Zcash atual; Isso tem, em última análise, a ver com a parte "sucinta" de SNARKs. É verdade que a seqüência de ocultações que Bob está enviando para Alice acima é tão longo, mas ele vai revelar esta seqüência pode ser "hard-coded" nos parâmetros do sistema, enquanto a mensagem de Alice será diferente para cada prova SNARK .
[2]Na verdade, a ocultação só garante \(s\) não sendo recuperável a partir de \(E(s)\), mas aqui queremos reivindicar que também não é recuperável a partir da seqüência \(E(s),\ldots,E(s^d)\) que potencialmente contém mais informações sobre \(s\). Isto decorre da hipótese D-Power Diffie-Hellman, que acaba sendo uma suposição necessária para a segurança SNARK.