Greetings! New to Zcash?
The Zcash network is young, but evolving quickly! Sign up and we'll be in touch with more information about how you can get started with Zcash!

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.