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 220, ou 9,54 × 10−7.

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/2100 ou 1/21000, 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) , existir um simulador PPT S tal que:

onde View[P(x)↔(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 , existir um simulador eficiente S (dependendo de ) que possa reproduzir a conversa entre P e em qualquer entrada dada. A string auxiliar z na definição desempenha o papel de "conhecimento prévio" (incluindo as moedas aleatórias de ). A definição implica que 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 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 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 , ela quer provar que conhece um valor x tal que gx ≡ 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 = gx 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 = gr 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 gr 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 = gr 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′ ≡ gr′ · (gx)−1 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á gr′ 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 = gr 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 = gr 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′ = gr′ · y−1 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−n, 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:

Tipos de conhecimento zero

Existem vários tipos de provas de conhecimento zero:

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 ZKPAno de publicaçãoProtocoloTransparenteUniversalSeguro Pós-Quântico (Plausível)Paradigma de Programação
Pinocchio2013zk-SNARKNãoNãoNãoProcedural
Geppetto2015zk-SNARKNãoNãoNãoProcedural
TinyRAM2013zk-SNARKNãoNãoNãoProcedural
Buffet2015zk-SNARKNãoNãoNãoProcedural
ZoKrates2018zk-SNARKNãoNãoNãoProcedural
xJsnark2018zk-SNARKNãoNãoNãoProcedural
vRAM2018zk-SNARGNãoSimNãoAssembly
vnTinyRAM2014zk-SNARKNãoSimNãoProcedural
MIRAGE2020zk-SNARKNãoSimNãoCircuitos Aritméticos
Sonic2019zk-SNARKNãoSimNãoCircuitos Aritméticos
Marlin2020zk-SNARKNãoSimNãoCircuitos Aritméticos
PLONK2019zk-SNARKNãoSimNãoCircuitos Aritméticos
SuperSonic2020zk-SNARKSimSimNãoCircuitos Aritméticos
Bulletproofs2018BulletproofsSimSimNãoCircuitos Aritméticos
Hyrax2018zk-SNARKSimSimNãoCircuitos Aritméticos
Halo2019zk-SNARKSimSimNãoCircuitos Aritméticos
Virgo2020zk-SNARKSimSimSimCircuitos Aritméticos
Ligero2017zk-SNARKSimSimSimCircuitos Aritméticos
Aurora2019zk-SNARKSimSimSimCircuitos Aritméticos
zk-STARK2019zk-STARKSimSimSimAssembly
Zilch2021zk-STARKSimSimSimOrientado 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

Referências

  1. 1 2 3 Goldwasser, S.; Micali, S.; Rackoff, C. (1989), «The knowledge complexity of interactive proof systems» (PDF), SIAM Journal on Computing, ISSN 1095-7111, 18 (1): 186–208, doi:10.1137/0218012
  2. ↑ Goldreich, Oded (2001). Foundations of Cryptography Volume I. [S.l.]: Cambridge University Press. p. 184. ISBN 978-0-511-54689-1. doi:10.1017/CBO9780511546891
  3. ↑ Goldreich, Oded (2001). Foundations of Cryptography Volume I. [S.l.]: Cambridge University Press. p. 247. ISBN 978-0-511-54689-1. doi:10.1017/CBO9780511546891
  4. ↑ Goldreich, Oded (2001). Foundations of Cryptography Volume I. [S.l.]: Cambridge University Press. p. 299. ISBN 978-0-511-54689-1. doi:10.1017/CBO9780511546891
  5. 1 2 Blum, Manuel; Feldman, Paul; Micali, Silvio (1988). «Non-interactive zero-knowledge and its applications». Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88 (PDF). [S.l.: s.n.] pp. 103–112. ISBN 978-0-89791-264-8. doi:10.1145/62212.62222. Consultado em 2 de junho de 2022. Cópia arquivada (PDF) em 14 de dezembro de 2018
  6. 1 2 Wu, Huixin; Wang, Feng (2014). «A Survey of Noninteractive Zero Knowledge Proof System and Its Applications». The Scientific World Journal. 2014. PMC 4032740Acessível livremente. PMID 24883407. doi:10.1155/2014/560484Acessível livremente
  7. ↑ «Playing Card Cryptography». Four Years Remaining. Consultado em 4 de junho de 2025
  8. 1 2 3 Murtagh, Jack (1 de julho de 2023). «Where's Wally? How to Mathematically Prove You Found Him without Revealing Where He Is». Scientific American. Consultado em 2 de outubro de 2023
  9. ↑ Quisquater, Jean-Jacques; Guillou, Louis C.; Berson, Thomas A. (1990). «How to Explain Zero-Knowledge Protocols to Your Children». Advances in Cryptology — CRYPTO' 89 Proceedings (PDF). Col: Lecture Notes in Computer Science. 435. [S.l.: s.n.] pp. 628–631. ISBN 978-0-387-97317-3. doi:10.1007/0-387-34805-0_60 [ligação inativa]
  10. ↑ Chalkias, Konstantinos. «Demonstrate how Zero-Knowledge Proofs work without using maths». CordaCon 2017 (em inglês). Consultado em 13 de setembro de 2017
  11. ↑ Feige, Uriel; Fiat, Amos; Shamir, Adi (1 de junho de 1988). «Zero-knowledge proofs of identity». Journal of Cryptology (em inglês). 1 (2): 77–94. ISSN 1432-1378. doi:10.1007/BF02351717Acessível livremente
  12. ↑ Ishai, Yuval; Kushilevitz, Eyal; Ostrovsky, Rafail; Sahai, Amit (2007). «Zero-Knowledge from Secure Multiparty Computation» (PDF). STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ISBN 978-1-59593-631-8. doi:10.1145/1250790.1250794. Consultado em 25 de setembro de 2025
  13. ↑ Chaum, David; Evertse, Jan-Hendrik; van de Graaf, Jeroen (1988). «An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations». Advances in Cryptology — EUROCRYPT '87. Col: Lecture Notes in Computer Science. 304. [S.l.: s.n.] pp. 127–141. ISBN 978-3-540-19102-5. doi:10.1007/3-540-39118-5_13
  14. ↑ Blum, Manuel (1986). «How to Prove a Theorem So No One Else Can Claim It» (PDF). ICM Proceedings: 1444–1451. CiteSeerX 10.1.1.469.9048Acessível livremente. Cópia arquivada (PDF) em 3 de janeiro de 2023
  15. ↑ Sahai, Amit; Vadhan, Salil (1 de março de 2003). «A complete problem for statistical zero knowledge» (PDF). Journal of the ACM. 50 (2): 196–249. CiteSeerX 10.1.1.4.3957Acessível livremente. doi:10.1145/636865.636868. Cópia arquivada (PDF) em 25 de junho de 2015
  16. ↑ Abascal, Jackson; Faghihi Sereshgi, Mohammad Hossein; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de outubro de 2020). «Is the Classical GMW Paradigm Practical? The Case of Non-Interactive Actively Secure 2PC». Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security. Col: CCS '20. Virtual Event, USA: Association for Computing Machinery. pp. 1591–1605. ISBN 978-1-4503-7089-9. doi:10.1145/3372297.3423366
  17. ↑ Groth, J; Kohlweiss, M (14 de abril de 2015). «One-Out-of-Many Proofs: Or How to Leak a Secret and Spend a Coin». Advances in Cryptology - EUROCRYPT 2015. Col: Lecture Notes in Computer Science. 9057. Berlin, Heidelberg: EUROCRYPT 2015. pp. 253–280. ISBN 978-3-662-46802-9. doi:10.1007/978-3-662-46803-6_9. hdl:20.500.11820/f6ec5d8f-cfda-4f56-9bd0-d9222b8d9a43Acessível livremente
  18. ↑ «Introducing Zero-Knowledge Proofs for Private Web attestation with Cross/Multi-Vendor Hardware». The Cloudflare Blog (em inglês). 12 de agosto de 2021. Consultado em 18 de agosto de 2021
  19. ↑ «PPPL and Princeton demonstrate novel technique that may have applicability to future nuclear disarmament talks - Princeton Plasma Physics Lab». www.pppl.gov. Cópia arquivada em 3 de julho de 2017
  20. 1 2 Hellwig, Daniel; Karlic, Goran; Huchzermeier, Arnd (3 de maio de 2020). «Privacy and Anonymity». Build Your Own Blockchain. Col: Management for Professionals. [S.l.]: SpringerLink. p. 112. ISBN 978-3-030-40142-9. doi:10.1007/978-3-030-40142-9_5. Consultado em 3 de dezembro de 2020
  21. ↑ Hurst, Samantha (28 de outubro de 2020). «Zcoin Announces Rebranding to New Name & Ticker "Firo"». Crowdfund Insider. Consultado em 4 de novembro de 2020. Cópia arquivada em 1 de novembro de 2020
  22. ↑ Bonneau, J; Miller, A; Clark, J; Narayanan, A (2015). «SoK: Research Perspectives and Challenges for Bitcoin and Cryptocurrencies». 2015 IEEE Symposium on Security and Privacy. San Jose, California: [s.n.] pp. 104–121. ISBN 978-1-4673-6949-7. doi:10.1109/SP.2015.14
  23. ↑ Ben-Sasson, Eli; Chiesa, Alessandro; Garman, Christina; Green, Matthew; Miers, Ian; Tromer, Eran; Virza, Madars (18 de maio de 2014). «Zerocash: Decentralized Anonymous Payments from Bitcoin» (PDF). IEEE. Consultado em 26 de janeiro de 2016
  24. 1 2 Bünz, B; Bootle, D; Boneh, A (2018). «Bulletproofs: Short Proofs for Confidential Transactions and More». 2018 IEEE Symposium on Security and Privacy (SP). San Francisco, California: [s.n.] pp. 315–334. ISBN 978-1-5386-4353-2. doi:10.1109/SP.2018.00020Acessível livremente
  25. ↑ «Circuits». OpenPassport docs. Self Labs. Consultado em 18 de janeiro de 2026
  26. ↑ Gupta, Aayush; Suegami, Sora; Panda, Sampriti (12 de dezembro de 2022). «ZK Email». ZK Email. Consultado em 18 de janeiro de 2026
  27. ↑ Foss, Nate; Ernst, David; Tavernier, Florent; Colin, Rémi. «New Democratic Primary». New Democratic Primary (em inglês). New Democratic Primary. Consultado em 18 de janeiro de 2026
  28. ↑ Rose, Anna; Gupta, Aayush (19 de março de 2025). «Making ZK More Human with ZK Email». Zero Knowledge Podcast. Episódio 353. Transcript. Consultado em 18 de janeiro de 2026
  29. ↑ Gupta, Aayush (14 de dezembro de 2022). «ZK Email + ZK JWTs». Consultado em 18 de janeiro de 2026
  30. ↑ Li, X.; others (2023). «ZKSQL: Verifiable and Efficient Query Evaluation with Zero-Knowledge Proofs» (PDF). Proceedings of the VLDB Endowment. 16 (8): 1804–1817. doi:10.14778/3594512.3594513
  31. ↑ Goldreich, Oded (1985). «A zero-knowledge proof that a two-prime moduli is not a Blum integer». Unpublished Manuscript
  32. ↑ Goldreich, Oded; Micali, Silvio; Wigderson, Avi (1991). «Proofs that yield nothing but their validity». Journal of the ACM. 38 (3): 690–728. CiteSeerX 10.1.1.420.1478Acessível livremente. doi:10.1145/116825.116852
  33. ↑ Russell Impagliazzo, Moti Yung: Direct Minimum-Knowledge Computations. CRYPTO 1987: 40–51
  34. ↑ Ben-Or, Michael; Goldreich, Oded; Goldwasser, Shafi; Hastad, Johan; Kilian, Joe; Micali, Silvio; Rogaway, Phillip (1990). «Everything provable is provable in zero-knowledge». In: Goldwasser, S. Advances in Cryptology – CRYPTO '88. Col: Lecture Notes in Computer Science. 403. [S.l.]: Springer-Verlag. pp. 37–56
  35. ↑ Ben-Or, Michael; Goldwasser, Shafi; Kilian, Joe; Widgerson, Avi (1988). «Multi-prover interactive proofs: How to remove intractability». Proceedings of the twentieth annual ACM symposium on Theory of computing - STOC '88. [S.l.: s.n.] pp. 113–131. ISBN 0-89791-264-0. doi:10.1145/62212.62223
  36. ↑ Dwork, Cynthia; Naor, Moni; Sahai, Amit (2004). «Concurrent Zero Knowledge». Journal of the ACM. 51 (6): 851–898. CiteSeerX 10.1.1.43.716Acessível livremente. doi:10.1145/1039488.1039489
  37. ↑ Feige, Uriel; Shamir, Adi (1990). «Witness indistinguishable and witness hiding protocols». Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. [S.l.: s.n.] pp. 416–426. CiteSeerX 10.1.1.73.3911Acessível livremente. ISBN 978-0-89791-361-4. doi:10.1145/100216.100272
  38. 1 2 Mouris, Dimitris; Tsoutsos, Nektarios Georgios (2021). «Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs». IEEE Transactions on Information Forensics and Security. 16: 3269–3284. Bibcode:2021ITIF...16.3269M. ISSN 1556-6021. doi:10.1109/TIFS.2021.3074869
  39. ↑ Parno, B.; Howell, J.; Gentry, C.; Raykova, M. (maio de 2013). «Pinocchio: Nearly Practical Verifiable Computation». 2013 IEEE Symposium on Security and Privacy. [S.l.: s.n.] pp. 238–252. ISBN 978-0-7695-4977-4. doi:10.1109/SP.2013.47
  40. ↑ Costello, Craig; Fournet, Cedric; Howell, Jon; Kohlweiss, Markulf; Kreuter, Benjamin; Naehrig, Michael; Parno, Bryan; Zahur, Samee (maio de 2015). «Geppetto: Versatile Verifiable Computation». 2015 IEEE Symposium on Security and Privacy. [S.l.: s.n.] pp. 253–270. ISBN 978-1-4673-6949-7. doi:10.1109/SP.2015.23. hdl:20.500.11820/37920e55-65aa-4a42-b678-ef5902a5dd45Acessível livremente
  41. ↑ Ben-Sasson, Eli; Chiesa, Alessandro; Genkin, Daniel; Tromer, Eran; Virza, Madars (2013). «SNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge». Advances in Cryptology – CRYPTO 2013. Col: Lecture Notes in Computer Science. 8043. [S.l.: s.n.] pp. 90–108. ISBN 978-3-642-40083-4. doi:10.1007/978-3-642-40084-1_6. hdl:1721.1/87953Acessível livremente
  42. ↑ Wahby, Riad S.; Setty, Srinath; Ren, Zuocheng; Blumberg, Andrew J.; Walfish, Michael (2015). «Efficient RAM and Control Flow in Verifiable Outsourced Computation». Proceedings 2015 Network and Distributed System Security Symposium. ISBN 978-1-891562-38-9. doi:10.14722/ndss.2015.23097
  43. ↑ Eberhardt, Jacob; Tai, Stefan (julho de 2018). «ZoKrates - Scalable Privacy-Preserving Off-Chain Computations». 2018 IEEE International Conference on Internet of Things (IThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData). [S.l.: s.n.] pp. 1084–1091. ISBN 978-1-5386-7975-3. doi:10.1109/Cybermatics_2018.2018.00199
  44. ↑ Kosba, Ahmed; Papamanthou, Charalampos; Shi, Elaine (maio de 2018). «XJsnark: A Framework for Efficient Verifiable Computation». 2018 IEEE Symposium on Security and Privacy (SP). [S.l.: s.n.] pp. 944–961. ISBN 978-1-5386-4353-2. doi:10.1109/SP.2018.00018Acessível livremente
  45. ↑ Zhang, Yupeng; Genkin, Daniel; Katz, Jonathan; Papadopoulos, Dimitrios; Papamanthou, Charalampos (maio de 2018). «VRAM: Faster Verifiable RAM with Program-Independent Preprocessing». 2018 IEEE Symposium on Security and Privacy (SP). [S.l.: s.n.] pp. 908–925. ISBN 978-1-5386-4353-2. doi:10.1109/SP.2018.00013Acessível livremente
  46. ↑ Ben-Sasson, Eli; Chiesa, Alessandro; Tromer, Eran; Virza, Madars (20 de agosto de 2014). «Succinct non-interactive zero knowledge for a von Neumann architecture». USENIX Association. Proceedings of the 23rd USENIX Conference on Security Symposium: 781–796. ISBN 978-1-931971-15-7
  47. ↑ Kosba, Ahmed; Papadopoulos, Dimitrios; Papamanthou, Charalampos; Song, Dawn (2020). «MIRAGE: Succinct Arguments for Randomized Algorithms with Applications to Universal zk-SNARKs». Cryptology ePrint Archive
  48. ↑ Maller, Mary; Bowe, Sean; Kohlweiss, Markulf; Meiklejohn, Sarah (6 de novembro de 2019). «Sonic: Zero-Knowledge SNARKs from Linear-Size Universal and Updatable Structured Reference Strings». Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security. [S.l.]: Association for Computing Machinery. pp. 2111–2128. ISBN 978-1-4503-6747-9. doi:10.1145/3319535.3339817. hdl:20.500.11820/739b94f1-54f0-4ec3-9644-3c95eea1e8f5Acessível livremente
  49. ↑ Chiesa, Alessandro; Hu, Yuncong; Maller, Mary; Mishra, Pratyush; Vesely, Noah; Ward, Nicholas (2020). «Marlin: Preprocessing zkSNARKs with Universal and Updatable SRS». Advances in Cryptology – EUROCRYPT 2020. Col: Lecture Notes in Computer Science (em inglês). 12105. [S.l.]: Springer International Publishing. pp. 738–768. ISBN 978-3-030-45720-4. doi:10.1007/978-3-030-45721-1_26
  50. ↑ Gabizon, Ariel; Williamson, Zachary J.; Ciobotaru, Oana (2019). «PLONK: Permutations over Lagrange-bases for Oecumenical Noninteractive arguments of Knowledge». Cryptology ePrint Archive
  51. ↑ Bünz, Benedikt; Fisch, Ben; Szepieniec, Alan (2020). «Transparent SNARKs from DARK Compilers». Advances in Cryptology – EUROCRYPT 2020. Col: Lecture Notes in Computer Science (em inglês). 12105. [S.l.]: Springer International Publishing. pp. 677–706. ISBN 978-3-030-45720-4. doi:10.1007/978-3-030-45721-1_24
  52. ↑ Wahby, Riad S.; Tzialla, Ioanna; Shelat, Abhi; Thaler, Justin; Walfish, Michael (maio de 2018). «Doubly-Efficient zkSNARKs Without Trusted Setup». 2018 IEEE Symposium on Security and Privacy (SP). [S.l.: s.n.] pp. 926–943. ISBN 978-1-5386-4353-2. doi:10.1109/SP.2018.00060Acessível livremente
  53. ↑ Bowe, Sean; Grigg, Jack; Hopwood, Daira (2019). «Recursive Proof Composition without a Trusted Setup». Cryptology ePrint Archive
  54. ↑ Zhang, Jiaheng; Xie, Tiancheng; Zhang, Yupeng; Song, Dawn (maio de 2020). «Transparent Polynomial Delegation and Its Applications to Zero Knowledge Proof». 2020 IEEE Symposium on Security and Privacy (SP). [S.l.: s.n.] pp. 859–876. ISBN 978-1-7281-3497-0. doi:10.1109/SP40000.2020.00052Acessível livremente
  55. ↑ Ames, Scott; Hazay, Carmit; Ishai, Yuval; Venkitasubramaniam, Muthuramakrishnan (30 de outubro de 2017). «Ligero». Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security. [S.l.]: Association for Computing Machinery. pp. 2087–2104. ISBN 978-1-4503-4946-8. doi:10.1145/3133956.3134104
  56. ↑ Ben-Sasson, Eli; Chiesa, Alessandro; Riabzev, Michael; Spooner, Nicholas; Virza, Madars; Ward, Nicholas P. (2019). «Aurora: Transparent Succinct Arguments for R1CS». Advances in Cryptology – EUROCRYPT 2019. Col: Lecture Notes in Computer Science (em inglês). 11476. [S.l.]: Springer International Publishing. pp. 103–128. ISBN 978-3-030-17652-5. doi:10.1007/978-3-030-17653-2_4
  57. ↑ Ben-Sasson, Eli; Bentov, Iddo; Horesh, Yinon; Riabzev, Michael (2019). «Scalable Zero Knowledge with No Trusted Setup». Advances in Cryptology – CRYPTO 2019. Col: Lecture Notes in Computer Science (em inglês). 11694. [S.l.]: Springer International Publishing. pp. 701–732. ISBN 978-3-030-26953-1. doi:10.1007/978-3-030-26954-8_23
  58. ↑ Nwosu, Emmanuel (25 de novembro de 2025). «Hyperbridge says it is building a hyperstructure for crypto bridges». TechCabal (em inglês). Consultado em 1 de dezembro de 2025
  59. ↑ Chaliasos, Stefanos; Ernstberger, Jens; Theodore, David; Wong, David; Jahanara, Mohammad; Livshits, Benjamin (2024). «SoK: What Don't We Know? Understanding Security Vulnerabilities in SNARKs». SEC '24: Proceedings of the 33rd USENIX Conference on Security Symposium. [S.l.: s.n.] pp. 3855–3872. ISBN 978-1-939133-44-1. arXiv:2402.15293Acessível livremente
  60. ↑ Pailoor, Shankara; Chen, Yanju; Wang, Franklyn; Rodríguez, Clara; Van Geffen, Jacob; Morton, Jason; Chu, Michael; Gu, Brian; Feng, Yu; Dillig, Işıl (2023). «Automated Detection of Under-Constrained Circuits in Zero-Knowledge Proofs». Proceedings of the ACM on Programming Languages. 7: 1510–1532. doi:10.1145/3591282Acessível livremente
  61. ↑ Diamond, Tyler (20 de junho de 2025). «An introduction to zero-knowledge virtual machines (zkVMs)». Veridise. Consultado em 10 de fevereiro de 2026
  62. ↑ Bruestle, J.; Gafni, P. (29 de julho de 2023). «RISC Zero zkVM: scalable, transparent arguments of RISC-V integrity». Draft. Consultado em 9 de fevereiro de 2026

Ligações externas