Idioma

Parâmetros Zcash e Como Eles Serão Gerados

Ariel Gabizon | Sep 22, 2016

Em sua essência, Zcash é uma tecnologia de privacidade que se baseia em uma ferramenta de criptografia inovadora chamada de zkSNARK - uma pequena prova de conhecimento-nulo que é extremamente barata. Zcash é a primeira a empregar esta ferramenta poderosa em grande escala. Por isso que trabalhar com zkSNARKs, uma fase de configuração é necessária, onde são gerados os "parâmetros do sistema". Esta fase de configuração é semelhante à fase de instalação de um sistema de criptografia de chave pública, mas com um porém: Como no sistema de criptografia de chave pública, um par (\(\mathsf{privkey},\) \(\mathsf{pubkey)}\) é gerado, mas, em seguida \(\mathsf{privkey}\) é destruída . De fato, será essencial para a integridade do sistema que, após a fase de instalação ninguém possua a \(\mathsf{privkey}.\)

\(\mathsf{pubkey}\) corresponde ao parâmetro de sistema necessário. \(\mathsf{privkey}\) corresponde ao que chamamos de "lixo tóxico" neste artigo, e isto permite a falsificação novas moedas (mas não permite violar a privacidade de outra transações dos usuários).

Para reduzir o risco, Zcash desenhou um protocolo multi-jogador onde \(\mathsf{pubkey}\) será gerado. O protocolo tem a propriedade que \(\mathsf{privkey}\) corresponda à concatenação de todos os participantes com segredos aleatórios. Assim, \(\mathsf{privkey}\) serão destruídos, a menos que todos os participantes sejam desonestos ou comprometidos.

O objetivo deste post é para dar uma explicação simplificada do que \(\mathsf{pubkey}\) parece e como o protocolo para a geração da chave funciona.

Com o que \(\mathsf{pubkey}\) se parece

Suponha \(g\) é um gerador de um grupo \(G\) onde o log discreto é difícil. Então assumimos que \(G\) tem ordem \(r\) por algum primo \(r,\) e escrevemos um grupo de operações aditivo. Assim, para \(s\in \mathbb{F}\), onde \(\mathbb{F}\) é o campo de tamanho \(r\), nós podemos escrever \(s\cdot g\) para denotar a multiplicação escalar de \(g\) by \(s\); ou seja \(s\cdot g\) é obtida pela adição \(s\) cópias de \(g\). Uma versão simplificada do (\(\mathsf{privkey},\) \(\mathsf{pubkey)}\) que é \(\mathsf{privkey}\) e é simplesmente um elemento uniformemente aleatório \(s\in \mathbb{F}^*\) e \(\mathsf{pubkey}\) é a sequência de elementos do grupo

\(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g)\)

Acima, \(\mathbb{F}^*\) denota o conjunto de todos os elementos diferentes de zero de \(\mathbb{F}.\)

Como \(\mathsf{pubkey}\) é gerada

Vamos dizer algumas palavras mais tarde sobre porque \(\mathsf{pubkey}\) se parece com isso e como ele é usado, mas vamos nos concentrar agora na elaboração do protocolo para a geração da \(\mathsf{pubkey}.\)

Vamos corrigir \(d=2\) pela simplicidade; e também omitir o primeiro elemento \(g\) da \(\mathsf{pubkey}\), como é simples gerar isso. Suponha que temos duas partes Alice e Bob, que deseja gerar uma chave pública válida \(\mathsf{pubkey}=\) \((s\cdot g, s^2\cdot g)\) para o sistema. Eles desejam fazê-lo de uma maneira que irá garantir que nenhum deles saberá \(s.\) Vamos torná-lo mais simples em primeiro lugar: suponha que eles só querem gerar \(s\cdot g\) (novamente, de uma forma que nem saberá \(s)\). Eles usam o seguinte protocolo:

  1. Alice escolhe um aleatório \(a\in \mathbb{F}^*\), e envia \(M_1:= a\cdot g\) para Bob.
  2. Bob, em seguida, escolhe um aleatório \(b\in \mathbb{F}^*\), e multiplica por \(M_1\) by \(b\). Ele envia de volta a mensagem \(M:= b\cdot M_1\) como sua produção conjunta.

No final do protocolo, temos \(M=b\cdot a \cdot g = (a b)\cdot g\). Vamos denotar \(s:= a b\).

Observe que

  • Bob não aprende \(a\) a partir da mensagem \(M_1,\) como estamos assumindo o log discreto é hard \(G\). Mesmo para Alice e \(b.\) Em particular, nem sabe \(s\) que é o produto de \(a\) e \(b\).
  • Para qualquer valor fixo de \(a\in \mathbb{F}^*\), \(a b\) é um elemento aleatório de \(\mathbb{F}^*\) quando \(b\) é aleatório. Assim, mesmo que Alice trapaceia no sentido de que ela não escolheu \(a\) aleatoriamente como ela deveria, por exemplo, ela sempre escolhe \(a=4\), \(s\) que será aleatório. O mesmo é verdadeiro para trapaceiro Bob e não escolhe um aleatório \(b.\)

Então, enquanto um deles segue o protocolo corretamente, :\(M=s\cdot g\) vai ser da forma certa.

Agora vamos tentar usar uma ideia semelhante para a geração de \((s\cdot g, s^2\cdot g)\):

  1. Alice escolhe um aleatório \(a\in \mathbb{F}^*,\) e envia \((A,B)\) onde \(A:= a\cdot g\) e \(B := a^2\cdot g.\)
  2. Bob escolhe um aleatório \(b\in \mathbb{F}^*,\) e envia \(M=(b\cdot A, b^2\cdot B).\)

Se Alice e Bob seguir o protocolo, nós temos \(M= (b a \cdot g, b^2 a^2 \cdot g) = ( a b\cdot g, (a b)^2\cdot g).\) Portanto, este vetor é da forma certa para \(s:= ab.\)

Aqui está um problema: E se Bob trapaceia e multiplica \(B\) por alguns \(c\neq b^2\)? Então, nós temos \((ab\cdot g, a^2 c \cdot g),\) que não é da forma \((s\cdot g, s^2\cdot g)\) para qualquer \(s.\) Precisamos verificar de alguma forma que o nosso vetor de saída é da forma \((s\cdot g, s^2\cdot g)\) para alguns \(s.\) Em muitos grupos, esta conjectura não será eficiente factível - este é o que é chamado a Diffie-Hellman. No entanto, em nosso meio, estamos trabalhando com um grupo que tem um emparelhamento bilinear. Este é o mapa \(e:G\times G\to G_T,\) em um grupo \(G_T\) também de ordem \(r\) com gerador \(\mathbf{g},\) escrito multiplicativamente, tal que

\(e(a\cdot g, b\cdot g) = \mathbf{g}^{ab}\)

para qualquer \(a,b\in\mathbb{F}.\) Isso nos dá a seguinte maneira de verificar se a saída \(M\) tem a forma certa. Nós simplesmente verificamos se

\(e(g,B) = e(A,A).\)

Vamos ver que se ninguém for enganado, este cheque vai passar. Quando ninguém engana temos \(A=s\cdot g,\) e \(B=s^2\cdot g.\) Assim

\(e(g,B) = e(g,s^2\cdot g) =\mathbf{g}^{s^2}\),

e também

\(e(A,A) = e(s\cdot g,s\cdot g) = \mathbf{g}^{s^2}.\)

Pode-se fazer um cálculo semelhante ao ver que quando \(M\) não é desta forma, estes dois valores serão diferentes e o teste irá falhar.

Como \(\mathsf{pubkey}\) é usado

Lembre-se que a polinomial \(P\) de grau \(d\) sobre \(\mathbb{F}\) é uma expressão da forma

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

Podemos avaliar um polinômio em um ponto \(s\in \mathbb{F}\) substituindo \(s\) para \(X,\) e calcular a soma resultante. Um fato útil é que, se \(P\) e \(Q\) são diferentes polinômios de grau no máximo \(d,\) eles podem concordar em no máximo \(d\) pontos. Na Zcash o remetente precisa construir dois graus \(d\) polinômios \(P\) e \(Q\) de certa forma, e um monte de mágica matemática garante que eles podem fazer o mesmo polinomial, isto é, obter \(P=Q,\) somente se a transação for válida.

\(\mathsf{pubkey}\) can now be used to test if \(P\) e \(Q\) are equal at a point \(s\) not known by the sender. Say

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

e

\(Q(X) = b_0 + b_1\cdot X + b_2\cdot X^2 + \ldots + b_d\cdot X^d\)

Usando \(\mathsf{pubkey}=\) \((g,s\cdot g, s^2\cdot g,\ldots, s^d\cdot g),\) o verificador pode computar

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

e compute \(Q(s)\cdot g\) similarly. The verifier can then check if they are equal.

Since the sender of a non-valid transaction has to construct distinct \(P\) e \(Q\) without knowing \(s,\) the chance that \(P(s)=Q(s)\) is very small.

References

Our zkSNARKS use SCIPR Lab's implementation of the Pinnochio protocol, which in turn is based on the work of Gennaro, Gentry, Parno e Raykova. Our protocol for parameter generation builds on a previous work of Ben-Sasson, Chiesa, Green, Tromer e Virza.