Bem vindo! Novo em Zcash?
A rede Zcash é jovem, mas está evoluindo rapidamente! Cadastre-se e estaremos em contato com mais informações sobre como você pode começar a usar Zcash!

Idioma

Explicando SNARKs Parte IV: Como fazer avaliação cega de polinômios verificáveis

Ariel Gabizon | Apr 11, 2017

<< Parte III

Nesta parte, construímos as partes II e III para desenvolver um protocolo para Avaliação cega verificável de polinômios, que iremos definir em breve. Na Parte V, vamos começar a ver como tal protocolo pode ser usado para construir SNARKs, então tenha um pouco mais de tempo para a conexão com SNARKs :).

Suponha, como na Parte II, que Alice tem um polinômio \(P\) de grau \(d\) e Bob tem um ponto \(s\in\mathbb{F}_p\) que ele escolheu aleatoriamente. Queremos construir um protocolo que permita a Bob descobrir \(E(P(s))\), isto é, o esconderijo de \(P\) avaliada em \(s\), com duas propriedades adicionais:

  1. Cegueira: Alice não vai descobrir \(s\) (e Bob não descobrirá \(P\)).
  2. Verificabilidade: a probabilidade de que Alice envie um valor fora da forma \(E(P(s))\) para \(P\) de grau \(d\) que ela conhece, mas Bob ainda aceita - é insignificante.

Isto é o que chamamos de avaliação cega verificável de um polinômio. O protocolo na Parte II nos deu o primeiro item, mas não o segundo. Para obter verificabilidade, precisamos de uma versão estendida do Conhecimento de Coeficiente de Assunção (KCA) que foi apresentado na Parte III.

As propriedades de verificabilidade e cegueira são úteis em conjunto porque fazem que Alice decida qual polinômio \(P\) ela usará sem ver \(s\). [1] _ Isso, de certo modo, compromete Alice com um "polinômio de resposta" sem ver o "ponto de desafio" \(s\). Esta intuição ficará mais clara nas próximas partes da série.

Um KCA expandido

O KCA como nós o definimos na Parte III essencialmente diz o seguinte: Se Bob dá a Alice um pouco de|alphapair| \((a,b = \alpha\cdot a)\) e então Alice gera outro \(\alpha\)-pair \((a',b')\), Então ela sabe \(c\) tal que a'=ac. Em outras palavras, Alice conhece a relação entre \(a'\) e \(a\).

Agora, suponha que em vez de um, Bob envia a Alice várias \(\alpha\)-pairs \((a_1,b_1),\ldots,(a_d,b_d)\) (para o mesmo \(\alpha\)); e que, novamente, após receber esses pares, Alice é desafiada a gerar algum outro \(\alpha\)-pair \((a',b')\). Lembre-se que o ponto principal é que Alice deve fazê-lo embora ela não conheça \(\alpha\).

Como vimos na Parte III, uma maneira natural para Alice gerar tal \(\alpha\)-pair, seria tomar um dos pares \((a_i,b_i)\) que ela recebeu de Bob, e multiplicar ambos os elementos por alguns \(c\in\mathbb{F}^*_p\); se \((a_i,b_i)\) era um \(\alpha\)-pair, então \((c\cdot a_i,c\cdot b_i)\) será um também. Mas pode Alice gerar \(\alpha\)-pairs em mais maneiras agora que recebeu multiple \(\alpha\)-pairs? Talvez usando vários dos \(\alpha\)-pairs recebidos simultaneamente para obter um novo?

A resposta é sim: por exemplo, Alice pode escolher dois valores \(c_1,c_2\in \mathbb{F}_p\) e calcular o par \((a',b')=(c_1\cdot a_1 + c_2\cdot a_2, c_1\cdot b_1 + c_2\cdot b_2)\). Uma computação fácil mostra que, contanto que \(a'\) é não-zero, este é também um \(\alpha\)-pair:

\(b' = c_1\cdot b_1 + c_2 \cdot b_2 = c_1 \alpha \cdot a_1 + c_2\alpha\cdot a_2 = \alpha (c_1\cdot a_1 + c_2\cdot a_2) = \alpha\cdot a'.\)

Mais geralmente, Alice pode tomar qualquer combinação linear dos pares dados \(d\) - que é escolher qualquer c1-d em Fp e definir \((a',b')=(\sum_{i=1}^d c_i a_i,\sum_{i=1}^d c_ib_i)\).

Note que, se Alice usa essa estratégia para gerar seu \(\alpha\)-pair ela saberá alguma relação linear entre \(a'\) e \(a_1,\ldots,a_d\); isto é, ela sabe \(c_1,\ldots,c_d\) tal que \(a'=\sum_{i=1}^d c_i\cdot a_i\).

O KCA estendido afirma, essencialmente, que esta é a única maneira que Alice pode gerar um \(\alpha\)-pair; ou seja, sempre que ela tiver êxito, ela saberá tal relação linear entre \(a'\) e \(a_1,\ldots,a_d\). Mais formalmente, suponha que \(G\) é um grupo de tamanho \(p\) com gerador \(g\) escrito aditivamente como na Parte III. O d-power Conhecimento Coeficiente de Assunção (d-KCA) [2] em \(G\) é a seguinte:

KCA : Suponha que Bob escolhe aleatório \(\alpha\in\mathbb{F}_p^*\) e \(s\in\mathbb{F}_p\), e envia para Alice o *|alphapairs| |galpg-sdgalpsdg|. *Suponha que Alice então emite outro \(\alpha\)-pair \((a',b')\). Então, exceto com probabilidade insignificante, Alice sabe *| c1-dinFp | *tal que \(\sum_{i=0}^d c_i s^i\cdot g = a'\).

Observe que no d-KCA Bob não envia um conjunto arbitrário de \(\alpha\)-pairs, mas um com uma certa "estrutura polinomial". Isso será útil no protocolo abaixo.

O Verifiable Blind Evaluation Protocol

Suponha que a nossa HH é o mapeamento \(E(x)=x\cdot g\) para um gerador \(g\) de \(G\) como acima.

Por simplicidade, apresentamos o protocolo para este particular \(E\):

  1. Bob escolhe um aleatório \(\alpha\in\mathbb{F}_p^*\), e envia para Alice os esconderijos \(1,s,\ldots,s^d\) (de \(1,s,\ldots,s^d\)) e também os esconderijos \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\) (de \(\alpha,\alpha s,\ldots,\alpha s^d\)).
  2. Alice calcula \(a=P(s)\cdot g\) e \(b=\alpha P(s)\cdot g\) usando os elementos enviados no primeiro passo, e envia ambos para Bob.
  3. Bob verifica que \(b=\alpha \cdot a\), e aceita se e somente se esta igualdade se mantiver.

Em primeiro lugar, note que, dados os coeficientes de \(P\), \(P(s)\cdot g\) é uma combinação linear de \(g,s\cdot g,\ldots,s^d\cdot g\); e \(\alpha P(s)\cdot g\) é uma combinação linear de \(\alpha\cdot g,\alpha s \cdot g,\ldots,\alpha s^d\cdot g\). Assim, de forma semelhante ao protocolo da Parte II, Alice pode de fato calcular esses valores das mensagens de Bob para um polinômio \(P\) que ela conhece.

Em segundo lugar, pela d-KCA se Alice envia \(a\), \(b\) tal que \(b=\alpha \cdot a\) então quase certamente ela sabe \(c_1,\ldots,c_d\in\mathbb{F}_p\) tal que \(a=\sum_{i=0}^d c_is^i\cdot g\). Nesse caso, \(a=P(s)\cdot g\) para o polinômio \(P(X)=\sum_{i=0}^d c_i\cdot X^i\) conhecido por Alice. Em outras palavras, a probabilidade de que Bob aceita no Passo 3, enquanto ao mesmo tempo Alice não sabe tal \(P\) é insignificante.

Para resumir, usando o d-KCA nós desenvolvemos um protocolo para avaliação cega verificável de polinômios. Nos próximos posts, veremos como esta construção de blocos vem atuar nas construções de SNARK.

[1] Na prova totalmente formal, as coisas são um pouco mais sutis, como Alice faz ver alguma informação sobre \(s\) antes de decidir sobre o \(P\) dela - por exemplo, ⇥os esconderijos de \(s,\ldots,s^d\).

[2]O d-KCA foi introduzido em um artigo de Jens Groth.

cryptography, zkSNARKs, explainers | Veja todas as tags