Introdução

Em nosso post anterior, apresentamos o conceito de SNARK e as propriedades básicas necessárias. Tendo em mente o objetivo principal desta série de posts, a saber: como construir zk-SNARKs para qualquer cálculo, apresentamos neste post a criação de um SNARK para provar o conhecimento de um polinômio. Faremos isso passo a passo partindo de uma construção que não atenderá a todos os requisitos e finalizando um protocolo que será um SNARK “completo” de conhecimento zero.

ZK-SNARKs para polinômios

Construiremos um zk-SNARK passo a passo, partindo de uma construção mais simples que não seja um SNARK, e depois aprimorando-a com novas técnicas até atingirmos nossos objetivos.

Primeiro passo: o lema de Schwartz — Zippel

Queremos criar um protocolo que permita a um provador P convencer um verificador V do conhecimento de um determinado polinômio de grau n com coeficientes em um corpo finito F. Em outras palavras, P quer convencer V de que ele conhece um polinômio da forma

Vamos assumir que a_1, a_2, … , a_n ∈ F são as n raízes deste polinômio, portanto p(x) pode ser escrito como

Suponhamos que V conheça d < n raízes do polinômio p(x).

Então podemos reformular nosso problema: agora P quer provar para V que ele conhece um polinômio h(x) tal que

O polinômio t(x) será chamado de polinômio alvo. Observe que tem a forma

A primeira versão do nosso zk-SNARK é baseada no lema de Schwartz — Zippel: seja F um corpo ef: F^m → F um polinômio multivariável de grau n. Então, para qualquer conjunto finito S ⊆ F:

O que o lema mostra é que se tomarmos u ∈ Sm uniformemente ao acaso, a probabilidade de u ser um conjunto de raízes para f é no máximo n / |S|. Observe que esta probabilidade é pequena se considerarmos S como o corpo finito F. O tamanho do campo seria muito grande comparado a n.

Pode parecer contraditório, mas este lema nos permite provar o conhecimento de um polinômio f. Não precisamos provar que conhecemos todos os coeficientes de p, mas apenas que sabemos como calcular o par (s, f(s)) para qualquer s ∈ Fm. O lema Schwartz — Zippel fornece a eficiência exigida em nosso zk-SNARK.

primeiro protocolo

Lembramos que P conhece o polinômio p(x) e V conhece d < n raízes de p(x) ou, equivalentemente, V conhece o polinômio alvo t(x). P também conhece t(x).

Nossa primeira abordagem é a seguinte:

1. V toma um valor aleatório s e calcula t = t(s). V envia s para P.
2. P calcula o polinômio

4. V verifica se a igualdade p = t · h.

Este protocolo está correto, pois se P conhece o polinômio p(x), ele pode calcular h(x) e, portanto, P também pode calcular os valores h e p tais que p = h · t. Por outro lado, este protocolo também é eficiente, devido ao lema de Schwartz — Zippel.

No entanto, este protocolo não é robusto, pois o provador pode calcular t = t(s) usando o polinômio alvo, mesmo que P não conheça p(x). Ele pode pegar um h aleatório e calcular p = h · t e enviar o par (h, p) para V que aceitaria o par como válido.

Observamos que o ponto crítico que permite P enganar V é que P conhece o ponto de avaliação s. Este truque seria impossível se P pudesse avaliar p sem conhecer o ponto de avaliação s. Isso nos leva ao segundo passo: ofuscação homomórfica, ou ocultação homomórfica.

Segundo passo: ofuscação homomórfica

Para tornar nosso protocolo robusto, precisamos ser capazes de avaliar um polinômio em um ponto, sem conhecer esse ponto.

Faremos isso contando com a dificuldade do problema do logaritmo discreto. Para um computador clássico, o problema do logaritmo discreto é computacionalmente inviável: em um grupo cíclico G, de ordem p e gerado por um elemento g, determinando um elemento a tal que = ga (mod p) para um conhecido.

Portanto, assumindo a dureza do polinômio logarítmico discreto, podemos ofuscar um valor a calculando = ga (mod p). Um receptor de sozinho não pode aprender o valor a. O ponto interessante desta técnica é que a exponenciação tem algumas propriedades homomórficas:

O produto de dois valores ofuscados é igual ao ofuscamento da soma dos valores associados em claro.

Se quisermos avaliar um polinômio

em um ponto x = s sem deixar o avaliador saber o ponto exato, precisamos ofuscar todo o polinômio:

Também precisamos calcular as potências, de 1 ao grau do polinômio, de todos os valores ofuscados para x = r, ou seja:

Observe que com todos esses elementos, agora podemos calcular a avaliação ofuscada do polinômio p em um ponto x = r. De fato:

Um exemplo de ocultação homomórfica

Vamos considerar o campo finito F = ℤ127 eg = 3 um gerador. Vamos supor que P conheça o polinômio p(x) = 4x2 + 3x + 1 e que V queira que P avalie o polinômio no ponto x = 2 sem deixar que P conheça o ponto. Podemos fazê-lo através dos seguintes passos:

1. V calcula todas as potências de x = 2 de 0 até o grau do polinômio, n = 2:

1. b. 32 (mod 127) = 9

1. c. 34 (mod 127) = 81

e envia o par (9, 81) para P.

2. P pode calcular a avaliação de p(x) em x = 2 sem saber o valor de x, de fato, usando a informação recebida de V ele pode calcular:

segundo protocolo

Agora que sabemos como ofuscar pontos para que o provador possa avaliar o polinômio naquele ponto ofuscado, vamos melhorar o primeiro protocolo. Lembramos que P conhece o polinômio p(x) e V conhece d < n raízes de p(x) ou, equivalentemente, V conhece o polinômio alvo t(x). P também conhece t(x).

Nosso segundo protocolo é o seguinte:

1. V toma um valor aleatório s e calcula t = t(s).
2. V calcula e envia para P as seguintes potências:

4. Usando os valores , P calcula g^p = g^{p(s)} e g^h = g*{h(s)} usando as instruções do exemplo anterior.

5. P envia g^p e g^h para V.

6. V verifica se a seguinte identidade é válida: g^p = (g^h)^t

Observe que a falha detectada no primeiro protocolo foi corrigida, mas este segundo protocolo ainda não é robusto. De fato, P ainda pode usar os valores zp e zh tais que z_p = (z_h)^t e enviá-los para V como se fossem g^p e g^h. P poderia fazer isso tomando um r aleatório, calculando z_h = g^r e configurando z_p = (g^t)^r. O valor z_p pode ser calculado usando os poderes ofuscados enviados por V.

Para evitar essa situação, precisamos garantir que g^p e g^h sejam calculados usando apenas as potências ofuscadas enviadas por V.

Terceiro passo: a hipótese do conhecimento do expoente

Há uma suposição comum ao definir um SNARK: vamos considerar um número primo q tal que 2q + 1 também é um número primo. Consideremos um gerador de ℤ_{2q + 1}. Dados q, g e g' = g^, queremos encontrar um par (x, y) tal que x ≠ g, y ≠ g' e y = x^. A suposição de conhecimento do expoente (KEA) diz que a única maneira de encontrar o par (x, y) é tomando um valor c ∈ ℤ_q, calculando primeiro x = g^c e depois tomando y = (g')^ c.

O KEA significa que se alguém quiser obter o par (x, y), a única maneira de fazer isso é conhecer um expoente c tal que x = g^c. Em outras palavras, só podemos obter o par (x, y) com a propriedade KEA usando potências de g.

Usando o KEA, o protocolo abaixo garante que P retorne uma determinada potência de g, um gerador de um subgrupo multiplicativo, entregue por V:

1. V pega um valor aleatório e calcula g' = g^ (mod 2q + 1).
2. V envia o par (g, g') para P e pede um par (b, b') tal que (b, b') = (g, g').
3. P pega um valor c e calcula b = g^c (mod 2q + 1), b' = (g')^c (mod 2q + 1) e envia o par (b, b') para V.
4. V verifica se b' = b^ (mod 2q + 1).

P usou a mesma potência c para g e g' e só foi capaz de usar valores fornecidos por V.

Terceiro protocolo

Estamos prontos para construir um protocolo adequado que garantirá que o provador P produzirá potências do valor s no domínio ofuscado.

1. V toma um valor aleatório s e calcula t = t(s).
2. V pega um valor aleatório e calcula t( · s).
3. V calcula a seguinte série de valores ofuscados e os envia para P.
4. V calcula a seguinte série de valores ofuscados

5. P calcula o polinômio h(x).

6. Usando , P calcula p(s) eh(s) junto com g^p = g^{p(s)} e g^h = g^{h(s)}.

7. Usando , P calcula p(s) eh(s) junto com g^{p'} = g^{p( · s)}.

8. P envia g^p, g^h e g^{p'} para V.

9. V verifica se P fez os cálculos dos valores ofuscados usando apenas as informações que ele enviou a ele. Para fazer isso, V verifica se g^p = g^{p'}.

10. V verifica se a seguinte identidade é válida: g^p = (g^h)^{t(s)}.

Este protocolo agora satisfaz as propriedades exigidas por um SNARK: é correto, é robusto e é eficiente. As próximas seções tratarão da não interatividade e do conhecimento zero.

Observação: As etapas 6 e 7 no protocolo acima são executadas de acordo com o exemplo de ocultação homomórfica.

conhecimento zero

No protocolo que apresentamos até agora, os coeficientes ci do polinômio conhecido por P são muito específicos, e V poderia tentar aprender algumas informações sobre eles usando gp, gh e gp' provenientes de P. Portanto, para garantir que P que V não vai aprender nada, P precisa esconder esses valores.

A estratégia para ocultar os valores enviados por P segue os passos usados ​​anteriormente: P pega um aleatório e o utiliza para ocultar os valores enviados na comunicação com V. Para ser mais preciso, ao invés de enviar g^p, g^h e g ^{p'}, P calcula e envia (g^p)^, (g^h)^ e (g^{p'})^. Então V executa a verificação nos valores ocultos em .

O procedimento de verificação que V precisa executar ainda é válido com esta ocultação, de fato:

Portanto, para tornar o terceiro protocolo de conhecimento zero, substitui-se a etapa 8 para que P possa enviar os valores ofuscados.

Não interatividade

Os diferentes protocolos que apresentamos requerem a interação entre o provador e o verificador, e isso porque a correção dos protocolos depende dos valores secretos s e escolhidos pelo verificador.

Se quisermos repetir qualquer um dos protocolos acima com outro verificador V', V' precisaria escolher novos valores s' e '. Usar os valores gerados por V pode permitir que P trapaceie se ele for conivente com V e V revelar os valores s e para P.

Para evitar a situação acima, precisamos que nosso protocolo seja não interativo e podemos alcançá-lo usando parâmetros públicos, confiáveis ​​e reutilizáveis. Isso pode ser feito ofuscando esses parâmetros usando um gerador g. No entanto, mesmo que as técnicas de ofuscação utilizadas sejam homomórficas, elas apenas permitem a adição de mensagens claras usando o produto de valores ocultos, mas não permitem realizar o produto de valores claros no domínio ofuscado, e esta etapa é crucial na verificação a exatidão do polinômio e suas raízes.

Vamos introduzir emparelhamentos para resolver este problema. Lembremos que um pareamento tem a seguinte propriedade:

Essa propriedade permite verificar a igualdade de produtos no domínio ofuscado.

Portanto, para tornar nossos protocolos não interativos, o primeiro passo é pegar os valores aleatórios secretos s e e ofuscar: g^, e .

Uma vez calculadas essas potências, podemos nos livrar dos valores secretos s e e transmitir seus valores ofuscados, conhecidos como Common Reference String (CRS). Os valores CRS geralmente são armazenados como:

1. Chave de avaliação: (, ).
2. Chave de verificação: (g^, g^{t(s)}).

Protocolo final: zk-SNARK para o conhecimento de um polinômio

Agora definimos um zk-SNARK para provar conhecimento sobre um polinômio p(x) de grau n dado um polinômio alvo t(x).

Configuração de parâmetro

1. Cada parte leva dois valores secretos s e aleatoriamente.
2. Cada parte calcula g, e .
3. Os valores s e são destruídos.
4. Um transmite a chave de avaliação ( e ).
5. Um transmite a chave de verificação g^, g^{t(s)}.

1. Assumindo que P conhece p(x), P calcula o polinômio h(x).
2. P avalia p(x) eh(x) e calcula gp(s) e gh(s) usando os valores contidos na chave de avaliação.
3. P calcula o valor g^{p( · s)} usando a chave de avaliação.
4. P assume um valor aleatório .
5. P transmite a prova π = (g^{ · p(s)}, g^{ · h(s)}, g^{ · p( · s)}) = (g^{ · p }, g^{ · h}, g^{ · p'}).

Assumindo que V tem acesso a π = (g^{ · p}, g^{ · h}, g^{ · p'}), ele verifica se

Conseguimos definir um protocolo que satisfaça todas as propriedades exigidas na definição de um zk-SNARK: sucinto (já que a prova é apenas verificar um polinômio em um ponto), conhecimento zero e não interativo (já que faz uso de um CRS ).

Geração do CRS

Os Zk-SNARKs podem se tornar não interativos usando um conjunto de valores ocultos, conhecido como Common Reference String (CRS). Esses valores ocultos, que no nosso caso são da forma e , vêm de valores secretos, s e , que devem ser destruídos assim que os valores ocultos forem derivados. Observe que a geração do CRS é crítica, pois se alguém delegar sua geração a um terceiro participante, todos precisam confiar que o participante destruirá os valores s e . O terceiro representa um único ponto de falha.

Se quisermos evitar o ponto único de falha, precisamos de uma forma distribuída para gerar o CRS em que um único participante honesto seja suficiente para garantir que os valores s e não possam ser recuperados.

Vamos usar o CRS para o SNARK que construímos em nosso exemplo anterior. Lembramos que usando s e como segredos, precisamos calcular os valores ocultos e as potências g^, e .

Em nosso novo protocolo, substituiremos os valores s e , gerados por um único terceiro, pelos valores s_{ABC} e _{ABC} gerados por três usuários A, B e C. Estender o mecanismo para n usuários é direto .

O protocolo segue:

1. O usuário A gera o par (sA, A), calcula e transmite:

3. Transmissões B:

4. C pega um par aleatório (sC, C), calcula e transmite:

Este protocolo gera os valores ocultos para s_{ABC} = s_A · s_B · s_C e _{ABC} = _A · _B · _C sem nenhum participante conhecer este par de valores.

No entanto, precisamos de um protocolo que permita aos participantes verificar se esses valores ocultos foram calculados corretamente. Precisamos garantir que os valores gerados por cada usuário satisfaçam os requisitos, ou seja, o conjunto de valores são potências de gs, para o valor s de cada usuário, e que o conjunto foi calculado corretamente. Para isso, verificamos que cada (g^s)^i é efetivamente a i-ésima potência de gs. Isso pode ser feito verificando se as seguintes igualdades são válidas. Esta verificação é realizada por cada participante para todos os valores sU e U associados a cada participante U:

Esta não é a única verificação necessária. Também precisamos verificar se cada participante usa os valores corretos do participante anterior. Para fazer isso, cada participante usará parâmetros públicos ocultos de um usuário combinados com as saídas de outro participante. Por exemplo, C pode verificar os valores intermediários do CRS gerado por B, usando as informações do CRS de A, verificando o seguinte:

Conclusão

Até agora aprendemos a criar um SNARK, do zero e com todos os detalhes, para provar o conhecimento de um polinômio. Em nosso próximo post, o último, vamos estender a construção acima para qualquer cálculo. Para tanto, introduziremos dois conceitos-chave: programas aritméticos quadráticos, QAPs e sistemas de restrição de nível 1, R1CS, embora este último não seja introduzido especificamente (aparecerá como uma mensagem subliminar).

Referências

Jordi Herrera Joancomartí, Cristina Pérez Solà, Criptografia avançada. Notas de aula. Universidade Aberta da Catalunha, 2022.