O envelope que não se troca.
A primeira peça é um envelope lacrado: quem prova se compromete com um conteúdo antes de saber qual pergunta vai receber. Depois, quando abrir, não pode ter trocado nada.
No computador, o envelope é uma impressão digital do texto: uma conta (aqui, SHA-256) que transforma qualquer texto num número de 64 caracteres. Mudar uma única letra muda a impressão inteira, e não se conhece jeito de achar dois textos com a mesma impressão. O nome técnico é compromisso.
Falta um detalhe. Se o conteúdo for curto ("rosa", "azul", "amarelo"), quem vê o lacre poderia testar as três palavras e descobrir. Por isso junta-se ao conteúdo um sal: bytes sorteados que ficam guardados com quem prova e só aparecem na hora de abrir.
Lacre e abra
Por que você não aprende nada.
No mapa, quem confere escolhe uma divisa ao acaso, e quem prova abre só aqueles dois envelopes. Se ela sabe pintar, as duas cores são sempre diferentes. Se está blefando, existe pelo menos uma divisa com as duas cores iguais, e a cada rodada há uma chance de você escolher justamente essa.
O que você vê em cada rodada? Duas cores diferentes. Mas as cores trocam de nome a cada rodada, então "rosa e azul" hoje não diz nada sobre qual região é rosa. Qualquer pessoa poderia ter inventado essa conversa sozinha, sorteando duas cores diferentes, sem conhecer pintura nenhuma. É isso que "conhecimento zero" quer dizer: o que você recebe poderia ter sido fabricado sem o segredo, então não carrega o segredo.
O que convence você não são as cores; é que ela nunca falha, rodada após rodada, numa pergunta que não tinha como prever.
O desafio que ninguém controla.
A versão com conversa tem um problema prático: você precisa estar lá, escolhendo divisas. E quem assistir depois não tem como saber se você e quem prova não combinaram as perguntas. A saída, de 1986, é trocar você por uma conta: a divisa de cada rodada é tirada da impressão digital dos próprios envelopes daquela rodada. Quem prova não consegue escolher envelopes que produzam o desafio que lhe convém, porque mudar um envelope embaralha o resultado inteiro.
Assim a prova vira um arquivo: todas as rodadas, com os lacres e os pares abertos. Qualquer um refaz as contas e confere, a qualquer hora, sem falar com quem gerou. O preço é que quem blefa agora pode tentar em casa quantas vezes quiser antes de mandar, então a chance de escapar precisa ser absurdamente pequena: com 1 divisa ruim em 13, são 1.109 rodadas para chegar a 1 chance em 2128, o padrão de segurança usado em criptografia.
Gere e confira uma prova de 1.109 rodadas
Esta prova de mapa ocupa uns 314 KB. A prova de idade da bancada, feita com um sistema moderno, ocupa 164 bytes e se confere em 1,4 ms. Os sistemas modernos fazem o mesmo trabalho com uma matemática mais compacta; a lógica de lacrar, desafiar e responder continua lá dentro.
Qualquer regra vira uma conta.
Pintar mapas parece brincadeira, mas não é à toa que ele aparece aqui: desde 1986 se sabe que qualquer afirmação que um computador consegue conferir pode ser traduzida num mapa para pintar, e portanto provada sem mostrar. Na prática ninguém passa pelo mapa, que ficaria enorme. Os sistemas atuais escrevem a regra diretamente como uma sequência de contas pequenas e provam que todas elas fecham.
A prova de idade, por exemplo, é um programa de duas regras. O órgão emissor lacrou a data de nascimento quando emitiu o documento; o lacre é público. O celular prova que conhece uma data que bate com aquele lacre e que essa data está a pelo menos 18 anos do ano atual.
# a prova de idade, escrita como conta público: ano = 2026, lacre_do_documento segredo: nascimento, sal regra 1: lacre(nascimento, sal) é igual a lacre_do_documento regra 2: ano − nascimento é pelo menos 18 # vira 2.184 contas pequenas; a prova diz que todas fecham
Na nossa bancada, essas duas regras viraram 2.184 contas pequenas (restrições, no nome técnico), provadas em 26 ms. Provar que se está numa lista de um milhão de nomes vira 13.261; provar que se conhece o texto por trás de uma impressão SHA-256, 200.599.
O que uma prova precisa cumprir.
Quem sabe, convence
Se a afirmação é verdadeira e quem prova tem o segredo, quem confere aceita. No mapa: quem sabe pintar nunca é pega.
Quem não sabe, não convence
Se a afirmação é falsa, quem confere recusa, a não ser por uma sorte que se faz tão pequena quanto se queira. No mapa: 1 chance em 13 de ser pega por rodada, somando rodada a rodada.
Quem confere não aprende nada
Além de "a afirmação é verdadeira", nada. Tudo o que ele viu poderia ter sido fabricado sem o segredo. No mapa: pares de cores diferentes, ao acaso.
Para ir adiante.
Onde esta página simplifica.
O sal tem de ser secreto e novo
Reaproveitar o sal entre rodadas, ou sorteá-lo mal, deixa o lacre ser adivinhado. O espécime sorteia 16 bytes novos por envelope, com o gerador do próprio navegador.
Não implemente sozinho
Esta página é demonstração. Provas de verdade têm detalhes sutis (como o desafio é calculado, o que entra na impressão digital) em que um erro pequeno destrói a garantia. Use bibliotecas abertas e auditadas.
A prova de mapa é grande
1.109 rodadas e centenas de KB para uma afirmação pequena. Serve para ver o mecanismo; para uso real, sistemas modernos fazem o mesmo em centenas de bytes.
A conversa inventada tem uma condição
"Qualquer um poderia ter fabricado a conversa" vale para quem confere seguindo o protocolo. Resultados formais cobrem também quem confere tentando espiar; eles estão nas fontes.
Isto se aplica ao seu caso?
Conte em duas linhas o que você precisa decidir ou medir. A primeira conversa serve para ver se a medição resolve o seu caso, e, se não resolve, dizemos.
- Goldwasser, Micali e Rackoff, "The knowledge complexity of interactive proof systems" (STOC 1985): a definição de conhecimento zero.
- Goldreich, Micali e Wigderson, "Proofs that yield nothing but their validity" (FOCS 1986; Journal of the ACM, 1991): a prova da pintura de mapas com três cores, e que toda afirmação conferível por computador cabe nela.
- Fiat e Shamir, "How to prove yourself: practical solutions to identification and signature problems" (CRYPTO 1986): trocar quem confere por uma conta, e a prova virar uma mensagem só.
- SHA-256: NIST FIPS 180-4. No espécime, via a Web Crypto API do navegador; cada lacre é SHA-256 de "cor|sal", com 16 bytes de sal. O desafio de cada rodada da prova de uma mensagem são os 4 primeiros bytes de SHA-256(lacres da rodada | número da rodada), módulo 13.
- Restrições e tempos da prova de idade: bancada própria (gnark v0.16.3, Groth16, BN254, Apple M2), na página bancada.