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 Part I: Ocultação Homomórfica

Ariel Gabizon | Feb 28, 2017

As construções do zk-SNARKs envolve uma cuidadora combinação de vários ingredientes. Entender completamente como esses ingredientes funcionam juntos pode demorar um tempo.

Se eu tiver que escolher um ingrediente cujo papel é mais proeminente, seria o que aqui eu chamarei de Homomorphic Hiding (HH) [1]. Neste post, explicaremos o que é um HH e então dar um exemplo para mostrar porque ele é útil e como é construído.

Um HH \(E(x)\) de um número \(x\) é uma função que satisfaz as seguintes propriedades:

Aqui está um exemplo simples do porquê HH é útil para provas de conhecimento-nulo: Suponha que Alice quer provar a Bob que ela conhece os números \(x,y\) que são \(x+y=7\) (Claro que não é tão emocionante assim descobrir \(x,y,\), mas este é um bom exemplo para explicar o conceito em si).

  1. Alice envia \(E(x)\) e \(E(y)\) para Bob.
  2. Bob calcula \(E(x+y)\) a partir desses valores (o que ele é capaz de fazer uma vez que \(E\) é um HH).
  3. Bob também calcula \(E(7),\) e agora verifica se \(E(x+y)=E(7).\) Ele aceita a prova de Alice somente se a igualdade persistir.

Como diferentes entradas são mapeadas por \(E\) para diferentes ocultações, Bob de fato aceita a prova somente se Alice enviou ocultações de \(x,y\) tal que \(x+y=7.\) Por outro lado, Bob não descobre \(x\) e \(y,\) pois ele só tem acesso às ocultações [2].

Agora vejamos um exemplo de como essas ocultações são construídas. Na verdade, não podemos construí-los para números inteiros regulares com adição regular, mas precisamos examinar os grupos finitos:

Deixemos \(n\) ser um inteiro. Quando escrevemos \(A\;\mathrm{mod}\;n\) para um inteiro \(A,\) queremos dizer tomar o restante de \(A\) após dividir por \(n.\) Por exemplo, \(9\;\mathrm{mod}\; 7 = 2\) e \(13\; \mathrm{mod}\;12 = 1.\) Podemos usar a operação \(\mathrm{mod}\; n\) para definir uma operação de adição nos números \(\{0,\ldots,n-1\}:\) Fazemos adição regular, mas depois aplicamos \((\mathrm{mod}\; n)\) No resultado para obter um número no intervalo \(\{0,\ldots,n-1\}.\) Às vezes escrevemos \((\mathrm{mod}\; n)\) No lado direito para esclarecer que estamos usando este tipo de adição. Por exemplo, \(2+3 = 1\; (\mathrm{mod} \;4).\) Chamamos o conjunto de elementos \(\{0,\ldots,n-1\}\) juntamente com esta operação de adição, o grupo \(\mathbb{Z}_n\).

Para um primo \(p\), podemos usar a operação \(\mathrm{mod}\;p\) para também definir uma operação de multiplicação sobre os números \(\{1,\ldots,p-1\}\) de modo que o resultado da multiplicação também esteja sempre no conjunto \(\{1,\ldots,p-1\}\) - executando a multiplicação regular de inteiros, e então tomando o resultado | mod p. [3] Por exemplo, \(2\cdot 4=1\; (\mathrm{mod}\; 7).\)

Este conjunto de elementos juntamente com esta operação é referido como \(\mathbb{Z}_p^*\). \(\mathbb{Z}_p^*\) tem as seguintes propriedades úteis:

  1. É um grupo cíclico; o que significa que existe algum elemento \(g\) em \(\mathbb{Z}_p^*\) chamado um gerador tal que todos os elementos de \(\mathbb{Z}_p^*\) possam ser escritos como \(g^a\) para alguns \(a\) em \(\{0,..,p-2\}\), onde definimos \(g^0=1.\)
  2. Este discreto problema de logaritmo é considerado difícil em \(\mathbb{Z}_p^*\). Isto significa que, quando p é grande, dado um elemento \(h\) em \(\mathbb{Z}_p^*\) é difícil encontrar o inteiro \(a\) em \(\{0,..,p-2\}\) tal que \(g^a=h\;(\mathrm{mod}\;p).\)
  3. Como ''expoentes somam quando os elementos são multiplicados'', temos para \(a,b\) em \(\{0,..,p-2\}\) \(g^a\cdot g^b = g^{a+b\;(\mathrm{mod}\;p-1)}.\)

Usando essas propriedades, agora construímos um HH que ''suporta adição'' - significando que \(E(x+y)\) é computável de \(E(x)\) e \(E(y)\) assumimos que a entrada \(x\) de \(E\) é de \(\mathbb{Z}_{p-1}\), então está no intervalo \(\{0,\ldots,p-2\}.\) Definimos \(E(x)=g^x\) Para cada tal \(x\), e afirmam que \(E\) é um HH: A primeira propriedade implica que diferentes \(x\)'s em \(\mathbb{Z}_{p-1}\) são mapeadas para diferentes saídas. A segunda propriedade implica que dado \(E(x)=g^x\) é difícil encontrar \(x\). Finalmente, usando a terceira propriedade, dado \(E(x)\) e \(E(y)\) Podemos calcular \(E(x+y)\) como \(E(x+y) = g^{x+y\;\mathrm{mod}\; p-1} = g^x\cdot g^y = E(x)\cdot E(y).\)

[1]Ocultação Homomórfica não é um termo usado formalmente na criptografia, e é introduzido aqui para propósitos didáticos. É semelhante a, mas mais fraco que, a noção bem conhecida de um compromisso computacional oculto. A diferença é que um HH é uma função determinística da entrada, visto que um compromisso usa aleatoriedade adicional. Como consequência, HHs essencialmente ''ocultam a maioria dos x's'' enquanto compromissos ''ocultam todo x''.
[2]Bob não descobre algumas informações sobre x e y. Por exemplo, ele pode escolher um x aleatório, e verificar se x=x', calculando E(x'). Por esta razão, o protocolo acima não é realmente um protocolo de conhecimento-nulo, e só é usado aqui para fins explicativos. Na verdade, como veremos em posts posteriores, HH é usado em última instância em snarks para ocultar desafios verificadores ao invés de provar segredos.
[3]Quando p não é um primo é problemático definir multiplicação desta forma. Uma questão é que o resultado da multiplicação pode ser zero mesmo quando ambos os argumentos não são zero. Por exemplo, quando p=4, podemos obter 2*2=0(mod 4).