Prova de conhecimento zero

Na criptografia, uma prova de conhecimento zero (também conhecida como prova ZK ou ZKP, do inglês zero-knowledge proof) é um protocolo no qual uma parte (o provador) pode convencer outra parte (o verificador) de que uma determinada afirmação é verdadeira, sem transmitir ao verificador qualquer informação além do mero fato de que a afirmação é verdadeira. A intuição por trás da não trivialidade das provas de conhecimento zero é que é trivial provar a posse de uma informação relevante simplesmente revelando-a; a parte difícil é provar essa posse sem revelar a informação (ou qualquer aspecto dela).

Considerando que alguém deve ser capaz de gerar uma prova de alguma afirmação apenas quando estiver de posse de certa informação secreta conectada à afirmação, o verificador, mesmo após ter se convencido da veracidade da afirmação por meio de uma prova de conhecimento zero, deve, no entanto, permanecer incapaz de provar a afirmação a terceiros.

As provas de conhecimento zero podem ser interativas, o que significa que o provador e o verificador trocam mensagens de acordo com algum protocolo, ou não interativas, o que significa que o verificador é convencido por uma única mensagem do provador e nenhuma outra comunicação é necessária. No modelo padrão, a interação é exigida, exceto para provas triviais de problemas BPP. Nos modelos de string aleatória comum e oráculo aleatório, existem provas de conhecimento zero não interativas. A Heurística de Fiat–Shamir pode ser usada para transformar certas provas de conhecimento zero interativas em não interativas.

Exemplos abstratos

A prova da carta vermelha

Um exemplo de prova de conhecimento zero sem matemática é se Peggy quiser provar a Victor que ela tirou uma carta vermelha de um baralho padrão de 52 cartas, sem revelar qual carta vermelha específica ela possui. Victor observa Peggy tirar uma carta ao acaso do baralho embaralhado, mas ela mantém a carta virada para baixo para que ele não possa vê-la.

Para provar que sua carta é vermelha sem revelar sua identidade, Peggy pega as 51 cartas restantes do baralho e mostra sistematicamente a Victor todas as 26 cartas pretas (as 13 de espadas e 13 de paus) uma a uma, colocando-as viradas para cima na mesa. Como um baralho padrão contém exatamente 26 cartas vermelhas e 26 pretas, e Peggy demonstrou que todas as cartas pretas permanecem no baralho, Victor pode concluir com certeza que a carta escondida de Peggy deve ser vermelha.

Esta prova é de conhecimento zero porque Victor aprende apenas que a carta de Peggy é vermelha, mas não obtém informações sobre se é de copas ou ouros, ou qual carta vermelha específica ela possui. A prova seria igualmente convincente se Peggy estivesse com o Ás de Copas ou o Dois de Ouros. Além disso, mesmo que a interação fosse gravada, a gravação não revelaria a carta específica de Peggy a observadores futuros, mantendo a propriedade de conhecimento zero.

Se Peggy estivesse mentindo e na verdade tivesse uma carta preta, ela seria incapaz de produzir todas as 26 cartas pretas do restante do baralho, tornando a decepção impossível. Isso demonstra a solidez do sistema de prova. Este tipo de prova física de conhecimento zero usando cartas de baralho padrão pertence a uma classe mais ampla de protocolos criptográficos baseados em cartas que permitem aos participantes realizar computações seguras usando objetos cotidianos.

Onde está o Wally?

Outro exemplo bem conhecido de prova de conhecimento zero é o exemplo "Onde está o Wally?". Neste exemplo, o provador quer provar ao verificador que sabe onde Wally está em uma página de um livro Onde está Wally?, sem revelar sua localização ao verificador.

O provador começa pegando uma grande cartolina preta com um pequeno buraco, do tamanho do Wally. A cartolina tem o dobro do tamanho do livro em ambas as direções, para que o verificador não possa ver em que parte da página o provador a está colocando. O provador então posiciona a cartolina sobre a página de modo que Wally apareça no buraco.

O verificador pode agora olhar pelo buraco e ver o Wally, mas não consegue ver nenhuma outra parte da página. Portanto, o provador provou ao verificador que sabe onde Wally está, sem revelar qualquer outra informação sobre sua localização.

Este exemplo não é uma prova de conhecimento zero perfeita, porque o provador revela algumas informações sobre a localização de Wally, como a posição de seu corpo. No entanto, é uma ilustração decente do conceito básico de uma prova de conhecimento zero.

A caverna de Ali Babá

Peggy segue pelo caminho A ou B, enquanto Victor espera do lado de fora.

Victor escolhe aleatoriamente um caminho de saída.

Peggy aparece confiavelmente na saída que Victor nomeia.

Existe uma história bem conhecida que apresenta as ideias fundamentais das provas de conhecimento zero, publicada pela primeira vez em 1990 por Jean-Jacques Quisquater e outros em seu artigo "Como explicar protocolos de conhecimento zero para seus filhos". As duas partes na história são Peggy como a provadora da afirmação, e Victor, o verificador da afirmação.

Nesta história, Peggy descobriu a palavra secreta usada para abrir uma porta mágica em uma caverna. A caverna tem o formato de um anel, com a entrada de um lado e a porta mágica bloqueando o lado oposto. Victor quer saber se Peggy conhece a palavra secreta; mas Peggy, sendo uma pessoa muito reservada, não quer revelar seu conhecimento (a palavra secreta) a Victor nem revelar o fato de seu conhecimento ao mundo em geral.

Eles rotulam os caminhos da entrada como A e B. Primeiro, Victor espera do lado de fora da caverna enquanto Peggy entra. Peggy segue pelo caminho A ou B; Victor não tem permissão para ver qual caminho ela toma. Então, Victor entra na caverna e grita o nome do caminho que deseja que ela use para retornar, seja A ou B, escolhido ao acaso. Desde que ela realmente conheça a palavra mágica, isso é fácil: ela abre a porta, se necessário, e retorna pelo caminho desejado.

No entanto, suponha que ela não soubesse a palavra. Então, ela só seria capaz de retornar pelo caminho nomeado se Victor desse o nome do mesmo caminho pelo qual ela entrou. Como Victor escolheria A ou B ao acaso, ela teria 50% de chance de adivinhar corretamente. Se eles repetissem esse truque muitas vezes, digamos 20 vezes seguidas, a chance de ela antecipar com sucesso todos os pedidos de Victor seria reduzida para 1 em 2²⁰, ou 9,54 × 10⁻⁷.

Assim, se Peggy aparece repetidamente na saída que Victor nomeia, ele pode concluir que é extremamente provável que Peggy, de fato, conheça a palavra secreta.

Observação externa

Em relação a observadores terceiros: mesmo que Victor esteja usando uma câmera escondida que grave toda a transação, a única coisa que a câmera registrará é, em um caso, Victor gritando "A!" e Peggy aparecendo em A ou, no outro caso, Victor gritando "B!" e Peggy aparecendo em B. Uma gravação desse tipo seria trivial para quaisquer duas pessoas falsificarem (bastando que Peggy e Victor concordem previamente com a sequência de As e Bs que Victor gritará). Tal gravação certamente nunca será convincente para ninguém além dos participantes originais. Na verdade, até mesmo uma pessoa que esteve presente como observadora no experimento original não deveria se convencer, já que Victor e Peggy poderiam ter orquestrado todo o "experimento" do início ao fim.

Além disso, se Victor escolher seus As e Bs jogando uma moeda diante da câmera, este protocolo perde sua propriedade de conhecimento zero; o lançamento da moeda na câmera provavelmente seria convincente para qualquer pessoa que assistisse à gravação mais tarde. Assim, embora isso não revele a palavra secreta a Victor, torna possível para Victor convencer o mundo em geral de que Peggy possui esse conhecimento — contrariando os desejos declarados de Peggy. No entanto, a criptografia digital geralmente "joga moedas" baseando-se em um gerador de números pseudoaleatórios, que é semelhante a uma moeda com um padrão fixo de caras e coroas conhecido apenas pelo proprietário da moeda. Se a moeda de Victor se comportasse dessa maneira, então novamente seria possível que Victor e Peggy tivessem forjado o experimento, portanto, usar um gerador de números pseudoaleatórios não revelaria o conhecimento de Peggy ao mundo da mesma forma que usar uma moeda lançada.

Peggy poderia provar a Victor que conhece a palavra mágica, sem revelá-la a ele, em uma única tentativa. Se Victor e Peggy forem juntos à entrada da caverna, Victor pode observar Peggy entrar por A e sair por B. Isso provaria com certeza que Peggy conhece a palavra mágica, sem revelá-la a Victor. No entanto, tal prova poderia ser observada por um terceiro ou gravada por Victor, e tal prova seria convincente para qualquer pessoa. Em outras palavras, Peggy não poderia refutar tal prova alegando que coludiu com Victor e, portanto, ela não teria mais controle sobre quem está ciente de seu conhecimento.

Duas bolas e o amigo daltônico

Imagine que Victor seja daltônico para vermelho e verde (enquanto Peggy não é) e Peggy tenha duas bolas: uma vermelha e uma verde, mas idênticas em todos os outros aspectos. Para Victor, as bolas parecem completamente idênticas. Victor está cético de que as bolas sejam realmente distinguíveis. Peggy quer provar a Victor que as bolas são de cores diferentes, mas nada mais. Em particular, Peggy não quer revelar qual bola é a vermelha e qual é a verde.

Aqui está o sistema de prova: Peggy entrega as duas bolas para Victor e ele as coloca atrás das costas. Em seguida, ele pega uma das bolas, traz para a frente e a exibe. Depois, ele a coloca atrás das costas novamente e escolhe revelar apenas uma das duas bolas, escolhendo uma das duas ao acaso com probabilidade igual. Ele perguntará a Peggy: "Eu troquei a bola?". Todo esse procedimento é repetido quantas vezes for necessário.

Ao olhar para as cores das bolas, Peggy pode, é claro, dizer com certeza se ele as trocou ou não. Por outro lado, se as bolas fossem da mesma cor e, portanto, indistinguíveis, a capacidade de Peggy de determinar se ocorreu uma troca não seria melhor do que um palpite aleatório. Como a probabilidade de Peggy ter tido sucesso aleatório em identificar cada troca/não troca é de 50%, a probabilidade de ter tido sucesso aleatório em todas as trocas/não trocas aproxima-se de zero.

Ao longo de várias tentativas, a taxa de sucesso convergiria estatisticamente para 50%, e Peggy não conseguiria obter um desempenho significativamente melhor do que o acaso. Se Peggy e Victor repetirem esta "prova" várias vezes (por exemplo, 20 vezes), Victor deverá ficar convencido de que as bolas são de fato cores diferentes.

A prova acima é de conhecimento zero porque Victor nunca aprende qual bola é verde e qual é vermelha; de fato, ele não obtém conhecimento sobre como distinguir as bolas.

Definição

Uma prova de conhecimento zero de alguma afirmação deve satisfazer três propriedades:

1. Completude (Completeness): se a afirmação for verdadeira, um verificador honesto (ou seja, aquele que segue o protocolo corretamente) será convencido desse fato por um provador honesto.
2. Solidez (Soundness): se a afirmação for falsa, nenhum provador trapaceiro pode convencer um verificador honesto de que ela é verdadeira, exceto com uma pequena probabilidade.
3. Conhecimento zero (Zero-knowledge): se a afirmação for verdadeira, nenhum verificador aprende nada além do fato de que a afirmação é verdadeira. Em outras palavras, apenas conhecer a afirmação (e não o segredo) é suficiente para imaginar um cenário que mostre que o provador conhece o segredo. Isso é formalizado mostrando que cada verificador possui algum simulador que, recebendo apenas a afirmação a ser provada (e sem acesso ao provador), pode produzir uma transcrição que "pareça" uma interação entre um provador honesto e o verificador em questão.

As duas primeiras propriedades são de sistemas de provas interativas mais gerais. A terceira é o que torna a prova de conhecimento zero.

Provas de conhecimento zero não são provas no sentido matemático do termo, porque existe uma pequena probabilidade, o erro de solidez, de que um provador trapaceiro consiga convencer o verificador de uma afirmação falsa. Em outras palavras, provas de conhecimento zero são "provas" probabilísticas em vez de provas determinísticas. No entanto, existem técnicas para reduzir o erro de solidez a valores insignificantes (por exemplo, adivinhar corretamente cem ou mil decisões binárias tem um erro de solidez de 1/2¹⁰⁰ ou 1/2¹⁰⁰⁰, respectivamente. À medida que o número de bits aumenta, o erro de solidez diminui em direção a zero).

Uma definição formal de conhecimento zero deve usar algum modelo computacional, sendo o mais comum o de uma Máquina de Turing. Sejam P, V e S máquinas de Turing. Um sistema de prova interativa com (P,V) para uma linguagem L é de conhecimento zero se, para qualquer verificador em tempo polinomial probabilístico (PPT) ${\hat {V}}$, existir um simulador PPT S tal que:

$\forall x\in L,z\in \{0,1\}^{*},\operatorname {View} _{\hat {V}}\left[P(x)\leftrightarrow {\hat {V}}(x,z)\right]=S(x,z),$

onde View_{${\hat {V}}$}[P(x)↔${\hat {V}}$(x,z)] é um registro das interações entre P(x) e V(x,z). O provador P é modelado como tendo poder de computação ilimitado (na prática, P geralmente é uma Máquina de Turing probabilística). Intuitivamente, a definição afirma que um sistema de prova interativa (P,V) é de conhecimento zero se, para qualquer verificador ${\hat {V}}$, existir um simulador eficiente S (dependendo de ${\hat {V}}$) que possa reproduzir a conversa entre P e ${\hat {V}}$ em qualquer entrada dada. A string auxiliar z na definição desempenha o papel de "conhecimento prévio" (incluindo as moedas aleatórias de ${\hat {V}}$). A definição implica que ${\hat {V}}$ não pode usar nenhuma string de conhecimento prévio z para extrair informações de sua conversa com P, porque se S também receber esse conhecimento prévio, ele poderá reproduzir a conversa entre ${\hat {V}}$ e P exatamente como antes. ^{[carece de fontes]}

A definição dada é a de conhecimento zero perfeito. O conhecimento zero computacional é obtido exigindo que as visões do verificador ${\hat {V}}$ e do simulador sejam apenas computacionalmente indistinguíveis, dada a string auxiliar.

Exemplos práticos

Logaritmo discreto de um valor dado

Essas ideias podem ser aplicadas a uma aplicação criptográfica mais realista. Peggy quer provar a Victor que conhece o logaritmo discreto de um determinado valor em um determinado grupo.

Por exemplo, dado um valor y, um número primo grande p e um gerador $g$, ela quer provar que conhece um valor x tal que g^x ≡ y (mod p), sem revelar x. De fato, o conhecimento de x poderia ser usado como prova de identidade, já que Peggy poderia ter tal conhecimento por ter escolhido um valor aleatório x que não revelou a ninguém, computado y = g^x mod p e distribuído o valor de y a todos os verificadores potenciais, de modo que, em um momento posterior, provar o conhecimento de x equivale a provar a identidade como Peggy.

O protocolo procede da seguinte forma: em cada rodada, Peggy gera um número aleatório r, calcula C = g^r mod p e revela isso a Victor. Após receber C, Victor emite aleatoriamente um dos dois seguintes pedidos: ou ele solicita que Peggy revele o valor de r, ou o valor de (x + r) mod (p − 1).

Victor pode verificar qualquer uma das respostas; se ele solicitou r, pode então calcular g^r mod p e verificar se corresponde a C. Se ele solicitou (x + r) mod (p − 1), então pode verificar se C é consistente com isso, calculando g^{(x + r) mod (p − 1)} mod p e verificando se corresponde a (C · y) mod p. Se Peggy de fato conhece o valor de x, ela pode responder a qualquer um dos desafios possíveis de Victor.

Se Peggy soubesse ou pudesse adivinhar qual desafio Victor vai emitir, ela poderia facilmente trapacear e convencer Victor de que conhece x quando não conhece: se ela sabe que Victor vai solicitar r, ela procede normalmente: escolhe r, calcula C = g^r mod p e revela C a Victor; ela será capaz de responder ao desafio de Victor. Por outro lado, se ela sabe que Victor solicitará (x + r) mod (p − 1), então ela escolhe um valor aleatório r′, calcula C′ ≡ g^r′ · (g^x)⁻¹ mod p e revela C′ a Victor como o valor de C que ele está esperando. Quando Victor a desafia a revelar (x + r) mod (p − 1), ela revela r′, para o qual Victor verificará a consistência, já que ele, por sua vez, calculará g^r′ mod p, que corresponde a C′ · y, uma vez que Peggy multiplicou pelo inverso multiplicativo modular de y.

No entanto, se em qualquer um dos cenários acima Victor emitir um desafio diferente daquele que ela esperava e para o qual ela fabricou o resultado, ela será incapaz de responder ao desafio sob a suposição da inviabilidade de resolver o log discreto para este grupo. Se ela escolheu r e revelou C = g^r mod p, ela será incapaz de produzir um (x + r) mod (p − 1) válido que passe na verificação de Victor, dado que ela não conhece x. E se ela escolheu um valor r′ que se passa por (x + r) mod (p − 1), então ela teria que responder com o logaritmo discreto do valor que ela revelou – mas Peggy não conhece esse logaritmo discreto, já que o valor C que ela revelou foi obtido através de aritmética com valores conhecidos, e não computando uma potência com um expoente conhecido.

Assim, um provador trapaceiro tem uma probabilidade de 0,5 de trapacear com sucesso em uma rodada. Ao executar um número suficientemente grande de rodadas, a probabilidade de um provador trapaceiro ter sucesso pode ser tornada arbitrariamente baixa.

Para mostrar que a prova interativa acima fornece conhecimento zero além do fato de que Peggy conhece x, pode-se usar argumentos semelhantes aos usados na prova acima de completude e solidez. Especificamente, um simulador, digamos Simon, que não conhece x, pode simular a troca entre Peggy e Victor pelo seguinte procedimento. Primeiro, Simon lança aleatoriamente uma moeda honesta. Se o resultado for "cara", ele escolhe um valor aleatório r, calcula C = g^r mod p e revela C como se fosse uma mensagem de Peggy para Victor. Então Simon também produz uma mensagem "solicite o valor de r" como se fosse enviada de Victor para Peggy, e imediatamente produz o valor de r como se fosse enviado de Peggy para Victor. Uma única rodada está completa. Por outro lado, se o resultado do lançamento da moeda for "coroa", Simon escolhe um número aleatório r′, calcula C′ = g^r′ · y⁻¹ mod p e revela C′ como se fosse uma mensagem de Peggy para Victor. Então Simon produz "solicite o valor de (x + r) mod (p − 1)" como se fosse uma mensagem de Victor para Peggy. Finalmente, Simon produz o valor de r′ como se fosse a resposta de Peggy para Victor. Uma única rodada está completa. Pelos argumentos anteriores ao provar a completude e a solidez, a comunicação interativa simulada por Simon é indistinguível da correspondência real entre Peggy e Victor. A propriedade de conhecimento zero é, assim, garantida.

Ciclo hamiltoniano para um grafo grande

O esquema a seguir é de autoria de Manuel Blum.

Neste cenário, Peggy conhece um ciclo hamiltoniano para um grafo grande G. Victor conhece G, mas não o ciclo (por exemplo, Peggy gerou G e o revelou a ele). Acredita-se que encontrar um ciclo hamiltoniano dado um grafo grande seja computacionalmente inviável, já que sua versão de decisão correspondente é conhecida por ser NP-completo. Peggy provará que conhece o ciclo sem simplesmente revelá-lo (talvez Victor esteja interessado em comprá-lo, mas queira uma verificação primeiro, ou talvez Peggy seja a única que conhece essa informação e está provando sua identidade para Victor).

Para mostrar que Peggy conhece esse ciclo hamiltoniano, ela e Victor jogam várias rodadas de um jogo:

• No início de cada rodada, Peggy cria H, um grafo que é isomórfico a G (ou seja, H é exatamente como G, exceto que todos os vértices têm nomes diferentes). Como é trivial traduzir um ciclo hamiltoniano entre grafos isomórficos com isomorfismo conhecido, se Peggy conhece um ciclo hamiltoniano para G, ela também deve conhecer um para H.
• Peggy se compromete com H. Ela poderia fazer isso usando um esquema de compromisso criptográfico. Alternativamente, ela poderia numerar os vértices de H. Em seguida, para cada aresta de H, em um pequeno pedaço de papel, ela anota os dois vértices que a aresta une. Então ela coloca todos esses pedaços de papel virados para baixo em uma mesa. O objetivo deste compromisso é que Peggy não consiga mudar H enquanto, ao mesmo tempo, Victor não tenha nenhuma informação sobre H.
• Victor então escolhe aleatoriamente uma de duas perguntas para fazer a Peggy. Ele pode pedir que ela mostre o isomorfismo entre H e G (veja Problema do isomorfismo de grafos), ou ele pode pedir que ela mostre um ciclo hamiltoniano em H.
• Se for pedido a Peggy que mostre que os dois grafos são isomórficos, ela primeiro descobre todo o H (por exemplo, virando todos os pedaços de papel que colocou na mesa) e então fornece as traduções de vértices que mapeiam G para H. Victor pode verificar que eles são de fato isomórficos.
• Se for pedido a Peggy que prove que conhece um ciclo hamiltoniano em H, ela traduz seu ciclo hamiltoniano de G para H e descobre apenas as arestas do ciclo hamiltoniano. Ou seja, Peggy vira exatamente |V(G)| dos pedaços de papel que correspondem às arestas do ciclo hamiltoniano, deixando o restante ainda virado para baixo. Isso é suficiente para Victor verificar que H de fato contém um ciclo hamiltoniano.

É importante que o compromisso com o grafo seja tal que Victor possa verificar, no segundo caso, que o ciclo é realmente feito de arestas de H. Isso pode ser feito, por exemplo, comprometendo-se com cada aresta (ou a falta dela) separadamente.

Completude

Se Peggy de fato conhece um ciclo hamiltoniano em G, ela pode facilmente satisfazer a exigência de Victor tanto para o isomorfismo do grafo produzindo H a partir de G (com o qual ela se comprometeu no primeiro passo) quanto para um ciclo hamiltoniano em H (que ela pode construir aplicando o isomorfismo ao ciclo em G).

Conhecimento zero

As respostas de Peggy não revelam o ciclo hamiltoniano original em G. Em cada rodada, Victor aprenderá apenas o isomorfismo de H para G ou um ciclo hamiltoniano em H. Ele precisaria de ambas as respostas para um único H para descobrir o ciclo em G, de modo que a informação permanece desconhecida enquanto Peggy puder gerar um H distinto em cada rodada. Se Peggy não conhecesse um ciclo hamiltoniano em G, mas de alguma forma soubesse com antecedência o que Victor pediria para ver em cada rodada, ela poderia trapacear. Por exemplo, se Peggy soubesse antecipadamente que Victor pediria para ver o ciclo hamiltoniano em H, ela poderia gerar um ciclo hamiltoniano para um grafo não relacionado. Da mesma forma, se Peggy soubesse antecipadamente que Victor pediria para ver o isomorfismo, ela poderia simplesmente gerar um grafo isomórfico H (no qual ela também não conhece um ciclo hamiltoniano). Victor poderia simular o protocolo sozinho (sem Peggy) porque ele sabe o que pedirá para ver. Portanto, Victor não obtém nenhuma informação sobre o ciclo hamiltoniano em G a partir das informações reveladas em cada rodada.

Solidez

Se Peggy não conhece a informação, ela pode adivinhar qual pergunta Victor fará e gerar um grafo isomórfico a G ou um ciclo hamiltoniano para um grafo não relacionado, mas como ela não conhece um ciclo hamiltoniano para G, ela não pode fazer as duas coisas. Com essa adivinhação, sua chance de enganar Victor é de 2⁻ⁿ, onde n é o número de rodadas. Para todos os fins realistas, é inviavelmente difícil derrotar uma prova de conhecimento zero com um número razoável de rodadas desta maneira.

Variantes de conhecimento zero

Diferentes variantes de conhecimento zero podem ser definidas formalizando o conceito intuitivo do que se entende por saída do simulador "parecendo-se" com a execução do protocolo de prova real das seguintes maneiras:

• Falamos de conhecimento zero perfeito se as distribuições produzidas pelo simulador e pelo protocolo de prova forem distribuídas exatamente da mesma forma. Este é, por exemplo, o caso do primeiro exemplo acima.
• Conhecimento zero estatístico significa que as distribuições não são necessariamente exatamente as mesmas, mas são estatisticamente próximas, o que significa que sua diferença estatística é uma função negligenciável.
• Falamos de conhecimento zero computacional se nenhum algoritmo eficiente puder distinguir as duas distribuições.

Tipos de conhecimento zero

Existem vários tipos de provas de conhecimento zero:

• Prova de conhecimento: o conhecimento está oculto no expoente, como no exemplo mostrado acima.
• Prova de testemunha-indistinguível: os verificadores não podem saber qual testemunha é usada para produzir a prova.

Esquemas de prova de conhecimento zero podem ser construídos a partir de várias primitivas criptográficas, como Criptografia baseada em hash, Criptografia baseada em pareamento, Computação multipartidária ou Criptografia baseada em reticulados.

Aplicações

Geralmente, provas de conhecimento zero são usadas em protocolos para impor o comportamento honesto enquanto se mantém a privacidade. Basicamente, a ideia é forçar um usuário a provar, usando uma prova de conhecimento zero, que seu comportamento está correto de acordo com o protocolo.

Sistemas de autenticação

A pesquisa em provas de conhecimento zero foi motivada por sistemas de autenticação onde uma parte quer provar sua identidade a uma segunda parte através de alguma informação secreta (como uma senha), mas não quer que a segunda parte aprenda nada sobre esse segredo. Isso é chamado de "Prova de conhecimento de conhecimento zero". No entanto, uma senha é normalmente muito pequena ou insuficientemente aleatória para ser usada em muitos esquemas de provas de conhecimento de conhecimento zero. Uma Prova de senha de conhecimento zero é um tipo especial de prova de conhecimento de conhecimento zero que aborda o tamanho limitado das senhas.^{[carece de fontes]}

Em abril de 2015, foi introduzido o protocolo de provas um-de-muitos (um protocolo Sigma). Em agosto de 2021, a Cloudflare, uma empresa americana de infraestrutura web e segurança, decidiu usar o mecanismo de provas um-de-muitos para verificação web privada usando hardware de fornecedores.

Desarmamento nuclear

Em 2016, o Laboratório de Física de Plasma de Princeton e a Universidade de Princeton demonstraram uma técnica que pode ter aplicabilidade em futuras negociações de desarmamento nuclear. Ela permitiria que inspetores confirmassem se um objeto é ou não de fato uma arma nuclear sem registrar, compartilhar ou revelar o funcionamento interno, que pode ser secreto.

Blockchains

As provas de conhecimento zero foram aplicadas nos protocolos Zerocoin e Zerocash, que culminaram no nascimento das criptomoedas Zcoin (posteriormente renomeada como Firo em 2020) e Zcash em 2016. O Zerocoin possui um modelo de mixagem integrado que não confia em nenhum par ou provedor de mixagem centralizado para garantir o anonimato. Os usuários podem transacionar em uma moeda base e podem ciclar a moeda para dentro e para fora de Zerocoins. O protocolo Zerocash usa um modelo semelhante (uma variante conhecida como Prova de conhecimento zero não interativa), exceto que ele pode ocultar o valor da transação, enquanto o Zerocoin não pode.

Em 2018, foram introduzidos os Bulletproofs. Os Bulletproofs são uma melhoria das provas de conhecimento zero não interativas onde uma configuração confiável não é necessária.

Identidade

Devido às assinaturas assimétricas em documentos como passaportes e e-mails, provas de conhecimento zero podem ser feitas sobre as identidades das pessoas a fim de verificar informações sobre si mesmas de forma privada. Por exemplo, você pode provar a um site que tem mais de 18 anos, sem revelar outros detalhes como seu nome exato ou país de origem, provando em conhecimento zero que possui um passaporte assinado por uma chave governamental válida para um valor de idade superior a 18. De forma similar, ao fazer provas de conhecimento zero das assinaturas DKIM de seus e-mails, as pessoas podem provar que solicitaram ou transferiram um domínio ou ingresso de show, que possuem uma conta em um serviço de rede social ou que encomendaram algo em um serviço de e-commerce. A propriedade de conhecimento zero permite que as pessoas mantenham sua própria identidade e endereço de e-mail privados ao fazer isso. Isso pode ser usado para viabilizar eleições privadas e justas, mercados secundários de baixas taxas, e serviços de denúncia (whistleblowing).

SQL

Uma linha de trabalho relacionada aplica provas de conhecimento zero à análise de bancos de dados por meio dos chamados "coprocessadores" de conhecimento zero: sistemas off-chain que executam consultas e retornam tanto o resultado quanto uma prova de que a computação foi realizada corretamente em dados não adulterados. Protótipos acadêmicos mostraram como produzir provas ZK para consultas SQL ad-hoc enquanto ocultam entradas e garantem a correção do resultado (por exemplo, ZKSQL).

História

As provas de conhecimento zero foram concebidas pela primeira vez em 1985 por Shafi Goldwasser, Silvio Micali e Charles Rackoff em seu artigo "The Knowledge Complexity of Interactive Proof-Systems". Este artigo introduziu a hierarquia IP de sistemas de prova interativa (veja Sistema de prova interativa) e concebeu o conceito de complexidade de conhecimento, uma medida da quantidade de conhecimento sobre a prova transferida do provador para o verificador. Eles também forneceram a primeira prova de conhecimento zero para um problema concreto, o de decidir não resíduos quadráticos mod m. Juntamente com um artigo de László Babai e Shlomo Moran, este artigo histórico inventou os sistemas de prova interativa, pelos quais todos os cinco autores ganharam o primeiro Prêmio Gödel em 1993.

Nas suas próprias palavras, Goldwasser, Micali e Rackoff dizem:

De particular interesse é o caso onde este conhecimento adicional é essencialmente 0 e mostramos que [é] possível provar interativamente que um número é um não resíduo quadrático mod m liberando 0 conhecimento adicional. Isso é surpreendente, pois nenhum algoritmo eficiente para decidir a quadraticidade residual mod m é conhecido quando a fatoração de m não é fornecida. Além disso, todas as provas NP conhecidas para este problema exibem a fatoração prima de m. Isso indica que adicionar interação ao processo de prova pode diminuir a quantidade de conhecimento que deve ser comunicada para provar um teorema.

O problema do não resíduo quadrático tem tanto um algoritmo NP quanto um co-NP, e por isso reside na interseção de NP e co-NP. Isso também era verdade para vários outros problemas para os quais provas de conhecimento zero foram posteriormente descobertas, como um sistema de prova não publicado de Oded Goldreich verificando que um módulo de dois primos não é um Inteiro de Blum.

Oded Goldreich, Silvio Micali e Avi Wigderson foram um passo além, mostrando que, assumindo a existência de criptografia inquebrável, pode-se criar um sistema de prova de conhecimento zero para o problema de coloração de grafos com três cores, que é NP-completo. Como todo problema em NP pode ser eficientemente reduzido a este problema, isso significa que, sob esta suposição, todos os problemas em NP possuem provas de conhecimento zero. A razão para a suposição é que, como no exemplo acima, seus protocolos exigem criptografia. Uma condição suficiente comumente citada para a existência de criptografia inquebrável é a existência de funções de mão única, mas é concebível que alguns meios físicos também possam alcançá-la.

Além disso, eles também mostraram que o Problema do não isomorfismo de grafos, o complemento do Problema do isomorfismo de grafos, possui uma prova de conhecimento zero. Este problema está em co-NP, mas não é atualmente conhecido por estar em NP ou em qualquer classe prática. De forma mais geral, Russell Impagliazzo e Moti Yung, bem como Ben-Or et al., demonstrariam que, também assumindo funções de mão única ou criptografia inquebrável, existem provas de conhecimento zero para todos os problemas em IP = PSPACE, ou em outras palavras, qualquer coisa que possa ser provada por um sistema de prova interativa pode ser provada com conhecimento zero.

Não querendo fazer suposições desnecessárias, muitos teóricos buscaram uma forma de eliminar a necessidade de funções de mão única. Uma forma de fazer isso foi com sistemas de prova interativa multi-provador (veja Sistema de prova interativa), que possuem múltiplos provadores independentes em vez de apenas um, permitindo que o verificador "interrogue" os provadores isoladamente para evitar ser enganado. Pode-se mostrar que, sem quaisquer suposições de intratabilidade, todas as linguagens em NP têm provas de conhecimento zero em tal sistema.

Acontece que, em um ambiente semelhante à Internet, onde múltiplos protocolos podem ser executados simultaneamente, construir provas de conhecimento zero é mais desafiador. A linha de pesquisa que investiga provas de conhecimento zero concorrentes foi iniciada pelo trabalho de Dwork, Naor e Sahai. Um desenvolvimento particular nesse sentido foi a criação de protocolos de prova de testemunha-indistinguível. A propriedade de testemunha-indistinguibilidade está relacionada com a de conhecimento zero, contudo, protocolos de testemunha-indistinguíveis não sofrem dos mesmos problemas de execução concorrente.

Outra variante de provas de conhecimento zero são as provas de conhecimento zero não interativas. Blum, Feldman e Micali mostraram que uma string aleatória comum compartilhada entre o provador e o verificador é suficiente para alcançar conhecimento zero computacional sem exigir interação.

Protocolos

Os protocolos de prova de conhecimento zero interativos ou não interativos (por exemplo, zk-SNARK) mais populares podem ser categorizados amplamente em quatro categorias: Argumentos de Conhecimento Não Interativos Sucintos (SNARK), Argumentos de Conhecimento Transparentes Escalonáveis (STARK), Delegação de Polinômios Verificável (VPD) e Argumentos Não Interativos Sucintos (SNARG). Uma lista de protocolos e bibliotecas de prova de conhecimento zero é fornecida abaixo, juntamente com comparações baseadas em transparência, universalidade, segurança pós-quântica plausível e paradigma de programação. Um protocolo transparente é aquele que não requer nenhuma configuração confiável (trusted setup) e utiliza aleatoriedade pública. Um protocolo universal é aquele que não requer uma configuração confiável separada para cada circuito. Finalmente, um protocolo plausivelmente seguro pós-quântico é aquele que não é suscetível a ataques conhecidos envolvendo algoritmos quânticos.

Sistemas de prova de conhecimento zero (ZKP)

Sistema ZKP	Ano de publicação	Protocolo	Transparente	Universal	Seguro Pós-Quântico (Plausível)	Paradigma de Programação
Pinocchio	2013	zk-SNARK	Não	Não	Não	Procedural
Geppetto	2015	zk-SNARK	Não	Não	Não	Procedural
TinyRAM	2013	zk-SNARK	Não	Não	Não	Procedural
Buffet	2015	zk-SNARK	Não	Não	Não	Procedural
ZoKrates	2018	zk-SNARK	Não	Não	Não	Procedural
xJsnark	2018	zk-SNARK	Não	Não	Não	Procedural
vRAM	2018	zk-SNARG	Não	Sim	Não	Assembly
vnTinyRAM	2014	zk-SNARK	Não	Sim	Não	Procedural
MIRAGE	2020	zk-SNARK	Não	Sim	Não	Circuitos Aritméticos
Sonic	2019	zk-SNARK	Não	Sim	Não	Circuitos Aritméticos
Marlin	2020	zk-SNARK	Não	Sim	Não	Circuitos Aritméticos
PLONK	2019	zk-SNARK	Não	Sim	Não	Circuitos Aritméticos
SuperSonic	2020	zk-SNARK	Sim	Sim	Não	Circuitos Aritméticos
Bulletproofs	2018	Bulletproofs	Sim	Sim	Não	Circuitos Aritméticos
Hyrax	2018	zk-SNARK	Sim	Sim	Não	Circuitos Aritméticos
Halo	2019	zk-SNARK	Sim	Sim	Não	Circuitos Aritméticos
Virgo	2020	zk-SNARK	Sim	Sim	Sim	Circuitos Aritméticos
Ligero	2017	zk-SNARK	Sim	Sim	Sim	Circuitos Aritméticos
Aurora	2019	zk-SNARK	Sim	Sim	Sim	Circuitos Aritméticos
zk-STARK	2019	zk-STARK	Sim	Sim	Sim	Assembly
Zilch	2021	zk-STARK	Sim	Sim	Sim	Orientado a Objetos
Hyperbridge	2024	zk-SNARK	Sim	Sim	Sim	Circuitos Aritméticos

Vulnerabilidades de segurança em sistemas de conhecimento zero

Embora as provas de conhecimento zero ofereçam uma maneira segura de verificar informações, os circuitos aritméticos que as implementam devem ser cuidadosamente projetados. Se esses circuitos não tiverem restrições suficientes, eles podem introduzir vulnerabilidades de segurança sutis, porém críticas.

Uma das classes mais comuns de vulnerabilidades nesses sistemas é a lógica sub-restringida (under-constrained), onde restrições insuficientes permitem que um provador mal-intencionado produza uma prova para uma afirmação incorreta que ainda assim passa na verificação. Uma sistematização de ataques conhecidos de 2024 descobriu que aproximadamente 96% dos bugs documentados na camada de circuito em sistemas baseados em SNARK deviam-se a circuitos sub-restringidos.

Essas vulnerabilidades surgem frequentemente durante a tradução da lógica de alto nível para sistemas de restrição de baixo nível, particularmente ao usar linguagens de domínio específico, como Circom ou Gnark. Pesquisas recentes demonstraram que provar formalmente o determinismo — garantindo que as saídas de um circuito sejam determinadas exclusivamente pelas suas entradas — pode eliminar classes inteiras dessas vulnerabilidades.

Máquinas virtuais de conhecimento zero

Máquinas virtuais de conhecimento zero (zkVMs) são computadores virtuais de propósito geral projetados para executar código e gerar provas de conhecimento zero que verificam, de forma off-chain e sem revelar entradas privadas, que o código foi executado corretamente e produziu o resultado alegado. Uma prova é um arquivo binário compacto e estruturado que pode ser verificado eficientemente por qualquer pessoa usando a ferramenta verificadora da zkVM sem reexecutar a computação original.

As zkVMs trazem benefícios tanto de desenvolvimento quanto de segurança. Usando uma zkVM, os desenvolvedores podem executar e verificar computações complexas off-chain, evitando altos custos de "taxas de gás" on-chain (taxas de processamento de blockchain) e mantendo a privacidade do código ou dos dados. Diversas zkVMs desenvolvidas recentemente, como as da RISC Zero e Succinct Labs, suportam o conjunto de instruções RISC-V, o que permite aos programadores escreverem código em linguagens de programação populares, como Rust, em vez de usarem uma linguagem de circuito de domínio específico, como o Circom. Outras zkVMs adotam abordagens diferentes, visando WebAssembly (WASM) ou implementando conjuntos de instruções customizados otimizados para desempenho de conhecimento zero ou integração com ambientes de blockchain específicos.

Ver também

• Esquema de identificação de Feige–Fiat–Shamir —
• Paradoxo da informação de Arrow — onde a informação proprietária perde valor de mercado uma vez revelada
• Protocolo criptográfico —
• Prova checável probabilisticamente —
• Prova de conhecimento — classe de prova interativa
• Prova de conhecimento zero não interativa —
• Prova de senha de conhecimento zero —
• Prova de testemunha-indistinguível —
• Tópicos em criptografia —

Ligações externas

• O cientista da computação Amit Sahai explica a prova de conhecimento zero em 5 níveis de dificuldade (em inglês) no YouTube