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 III: O conhecimento do teste de coeficiente e da suposição

Ariel Gabizon | Mar 28, 2017

<< Part II

Na Parte II, vimos como Alice pode cegamente avaliar a ocultação \(E(P(s))\) de seu polinômio \(P\) de grau \(d,\) em um ponto \(s\) pertencente a Bob. Chamamos essa avaliação de "cega", porque Alice não descobriu \(s\) no processo.

No entanto, havia algo faltando nesse protocolo - o fato de que Alice é capaz de calcular \(E(P(s))\) não garante que ela realmente enviará \(E(P(s))\) para Bob em vez de algum valor completamente não relacionado.

Assim, precisamos de uma maneira de "forçar" Alice a seguir corretamente o protocolo. Explicaremos na parte IV exatamente como conseguimos isso. Neste post, nós nos concentramos em explicar a ferramenta básica necessária para isso - que chamamos aqui o teste de Conhecimento de Coeficiente (KC).

Como antes, denotamos por \(g\) um gerador de um grupo \(G\) de ordem \(|G|=p\) onde o registro discreto é difícil. Será conveniente a partir deste post em diante para escrever o nosso grupo de forma aditiva ao invés de multiplicativamente. Isto é, para \(\alpha\in\mathbb{F}_p,\) \(\alpha\cdot g\) denota o resultado da soma \(\alpha\) cópias de \(g.\)

O teste KC

Para \(\alpha\in\mathbb{F}_p^*\) [1], vamos chamar um par de elementos \((a,b)\) em \(G\) um alfabeto se \(a,b \neq 0\) e \(b=\alpha\cdot a.\)

O teste KC prossegue como se segue.

  1. Bob escolhe aleatoriamente \(\alpha\in\mathbb{F}_p^*\) e \(a\in G.\) ele calcula \(b=\alpha\cdot a.\)
  2. Ele envia para Alice o par de "desafio" \((a,b).\) Note que \((a,b)\) é um \(\alpha\)-pair.
  3. Alice agora deve responder com um par diferente \((a',b')\) que também é um \(\alpha\)-pair.
  4. Bob aceita a resposta de Alice somente se \((a',b')\) é realmente um \(\alpha\)-pair. (Como ele sabe \(\alpha\) ele pode verificar se \(b'=\alpha\cdot a'.)\)

Agora, vamos pensar como Alice poderia responder com sucesso ao desafio. Vamos supor por um segundo que ela sabia \(\alpha.\) Nesse caso, ela poderia simplesmente escolher qualquer \(a'\) em \(G,\) E calcular \(b'=\alpha\cdot a';\) e retornar \((a',b')\) como seu novo \(\alpha\)-pair.

No entanto, como a única informação sobre \(\alpha\) que ela tem é \(\alpha\cdot a\) e \(G\) tem um problema de registro discreto difícil, esperamos que Alice não consiga encontrar \(\alpha.\)

Então, como ela pode responder com sucesso ao desafio sem saber \(\alpha?\)

Aqui está a maneira natural de fazê-lo: Alice simplesmente escolhe alguns \(\gamma\in\mathbb{F}_p^*,\) e responde com \((a',b')=(\gamma\cdot a,\gamma\cdot b).\)

Neste caso, nós temos:

\(b'=\gamma \cdot b = \gamma \alpha \cdot a = \alpha (\gamma\cdot a) =\alpha \cdot a',\)

Assim de fato \((a',b')\) é um \(\alpha\)-pair como requerido.

Note que se Alice responde usando esta estratégia, ela sabe a razão entre \(a\) e \(a'\) . Ou seja, ela conhece o coeficiente \(\gamma\) tal que \(a'=\gamma\cdot a.\)

O Conhecimento de Coeficiente e Suposição [2] (KCA) afirma que este é sempre o caso, a saber:

KCA: Se Alice retorna uma resposta válida *|(a',b')| para o desafio de Bob |(a,b)| com probabilidade não negligenciável sobre as escolhas de Bob de* \(a,\alpha\), Então ela sabe \(\gamma\) tal que \(a'=\gamma\cdot a.\)

O teste KC e de suposição serão ferramentas importantes na Parte IV.

O que "Alice sabe" significa exatamente?

Você pode se perguntar como podemos expressar o KCA em termos matemáticos precisos; especificamente como formalizamos a noção de que "Alice sabe \(\gamma\)" em uma definição matemática?

Isto é feito aproximadamente como segue: Dizemos que, além de Alice, temos outra parte que chamamos de Alice's Extractor. Alice's Extractor tem acesso ao estado interior de Alice.

Em seguida, formulamos o KCA como dizendo que: sempre que Alice com êxito responde com um \(\alpha\)-pair \((a',b'),\) saídas do extrator de Alice \(\gamma\) tal que \(a'=\gamma\cdot a.\) [3]

[1]\(\mathbb{F}_p^*\) denota os elementos não nulos de \(\mathbb{F}_p\). É o mesmo que \(\mathbb{Z}_p^*\) descrito na Parte I.
[2]Isso é normalmente chamado de Conhecimento de Suposição Exponente na literatura, como tradicionalmente foi usado para grupos escritos multiplicativamente.
[3]A definição totalmente formal precisa dar ao Extrator "um pouco de folga" e afirma, em vez disso, que a probabilidade de que Alice responda com sucesso, mas o extrator não produz tais \(\gamma\) é insignificante.

cryptography, zkSNARKs, explainers | Veja todas as tags